Les zk-SNARKs sont un outil cryptographique puissant qui est devenu un élément de plus en plus essentiel des applications basées ou non sur la blockchain. Leur complexité est évidente, tant au niveau de la compréhension de leur fonctionnement que de leur utilisation efficace. Cet article explique comment les zk-SNARKs s'adaptent aux applications actuelles, donne des exemples de ce qu'ils peuvent et ne peuvent pas réaliser et propose des lignes directrices générales pour déterminer quand les zk-SNARKs conviennent à des applications spécifiques. Un accent particulier sera mis sur leur rôle dans la protection de la vie privée.

Que sont les zk-SNARKs ?

Imaginez que vous disposiez d'une entrée publique x, d'une entrée privée w et d'une fonction (publique) f(x,w) → {True,False}, qui valide les entrées. Avec zk-SNARKs, on peut prouver que l'on connaît un w, tel que pour un f et un x donnés, f(x,w) = True, tout cela sans révéler ce qu'est w en réalité. En outre, les vérificateurs peuvent authentifier la preuve beaucoup plus rapidement qu'ils ne pourraient calculer f(x,w) même s'ils connaissaient w.

Cela confère aux zk-SNARK deux attributs : la confidentialité et l'évolutivité. Comme nous l'avons mentionné, les exemples présentés dans cet article se concentrent principalement sur l'aspect de la protection de la vie privée.

Preuve d'adhésion

Supposons que vous possédiez un portefeuille Ethereum et que vous souhaitiez prouver que ce portefeuille est enregistré dans le cadre d'un système de preuve d'humanité, sans divulguer l'identité de la personne enregistrée. Cette fonction peut être décrite mathématiquement comme suit :

Entrée privée (w) : Votre adresse A, votre clé privée d'adresse k

Entrée publique (x) : ensemble d'adresses de tous les profils de preuve d'humanité vérifiés {H1…Hn}

Fonction de vérification f(x,w) :

Interprétez w comme une paire (A, σ) et x comme une liste de profils valide {H1…Hn}

Vérifiez que A est l'une des adresses de {H1…Hn}

Confirmer privtoaddr(k) = A

Si les deux vérifications sont réussies, il renvoie True. Si l'un d'entre eux échoue, il renvoie False.

Le prouveur génère son adresse A et la clé associée k, en fournissant w=(A,k) comme entrée privée pour f. Ils obtiennent l'entrée publique, qui est l'ensemble actuel des profils de preuve d'humanité vérifiés {H1…Hn}, à partir de la chaîne. Ils exécutent ensuite l'algorithme de preuve zk-SNARK, qui (en supposant que l'entrée est correcte) produit une preuve. Cette preuve est envoyée au vérificateur, avec la hauteur du bloc où il a récupéré la liste des profils vérifiés.

Le vérificateur lit également la chaîne, acquiert la liste {H1…Hn} à partir de la hauteur spécifiée par le prouveur et vérifie la preuve. Si la vérification est réussie, le vérificateur estime que le prouveur possède un profil de preuve d'humanité vérifié.

Avant d'aborder des exemples plus complexes, je vous recommande vivement de bien comprendre l'exemple ci-dessus.

Rendre les preuves d'adhésion plus efficaces

L'un des inconvénients du système de preuve susmentionné est que le vérificateur doit connaître l'ensemble du profil {H1…Hn}, ce qui nécessite un temps O(n) pour "introduire" cet ensemble dans le mécanisme zk-SNARK. Ce problème peut être résolu en utilisant la racine Merkle de la chaîne, qui englobe tous les profils, comme entrée publique (potentiellement juste la racine de l'État). Nous ajoutons une autre entrée privée, une preuve de Merkle M, confirmant que le compte A du prouveur se trouve dans la partie pertinente de l'arbre.

Caulk est une alternative très récente et plus efficace aux preuves de Merkle pour les preuves d'appartenance à ZK. À l'avenir, certains de ces cas d'utilisation pourraient faire l'objet d'une transition vers des solutions similaires à Caulk.

ZK-SNARKs et pièces de monnaie

Des projets comme Zcash et Tornado.cash nous permettent de posséder des monnaies qui protègent la vie privée. On pourrait penser qu'ils pourraient utiliser les "preuves humaines ZK" mentionnées, mais il ne s'agit pas de prouver l'accès à des preuves de profil humain ; il s'agit de prouver l'accès à des pièces de monnaie. C'est là que réside le problème : nous devons nous attaquer simultanément au problème de la protection de la vie privée et à celui de la double dépense. En d'autres termes, nous ne devrions pas dépenser deux fois la même pièce.

Voici comment résoudre le problème : Toute personne qui possède une pièce de monnaie a un secret privé "s". Ils calculent localement une "feuille" L=hash(s,1), qui est publiée sur la chaîne et devient une partie de l'état, N=hash(s,2), que nous appelons "nullifier". L'état est stocké dans un arbre de Merkle.

Pour dépenser une pièce, l'expéditeur doit produire un ZK-SNARK où :

• Les entrées publiques comprennent un annulateur N, la racine de Merkle actuelle ou récente R et une nouvelle feuille L' (destinée au destinataire qui dispose d'un secret s' transmis à l'expéditeur sous la forme L'=hash(s',1)).

• Les entrées privées comprennent un secret s, une feuille L et une branche de Merkle M.

La fonction de vérification contrôle :

• M est une branche de Merkle valide, prouvant que L est une feuille de l'arbre dont la racine est R, où R est la racine de Merkle de l'état actuel.

• hash(s,1)=L et hash(s,2)=N.

La transaction contient l'annulateur N et la nouvelle feuille L'. Nous ne prouvons rien au sujet de L', mais il est "mélangé" à la preuve pour empêcher toute modification par des tiers au cours de la transaction. Pour valider la transaction, la chaîne vérifie le ZK-SNARK et vérifie si N a été utilisé dans des transactions antérieures. En cas de succès, N est ajouté à l'ensemble des annulateurs épuisés, ce qui le rend à nouveau inutilisable. L' est ajouté à l'arbre de Merkle.

En utilisant les ZK-SNARKs, nous lions deux valeurs : L (apparaissant sur la chaîne lorsque la pièce est frappée) et N (apparaissant lorsqu'elle est dépensée), sans révéler quel L est lié à quel N. Le lien entre L et N n'est perceptible que si vous connaissez le s secret qui les génère. Chaque pièce frappée peut être utilisée une fois (car il n'y a qu'un seul N valide pour chaque L), mais la pièce spécifique utilisée à tout moment reste cachée.

Il s'agit là d'une primitive cruciale à saisir. De nombreux mécanismes que nous décrivons ci-dessous sont basés sur ce principe, bien qu'avec des objectifs différents.

Pièces à solde arbitraire

Ce qui précède peut être facilement étendu à des pièces dont le solde est arbitraire. Nous conservons le concept de "pièce", mais chaque pièce porte un solde (privé). Un moyen simple d'y parvenir est que chaque pièce dispose d'un stockage en chaîne, non seulement avec la feuille L, mais aussi avec un solde crypté. Chaque transaction consomme deux pièces et en crée deux nouvelles, ajoutant ainsi deux paires (feuille, solde chiffré) à l'état. Le ZK-SNARK vérifie également que la somme des soldes d'entrée est égale à la somme des soldes de sortie et que les deux soldes de sortie sont non négatifs.

ZK Anti-déni de service

Un outil anti-DOS intriguant : Imaginez que vous ayez une identité sur la chaîne qui ne soit pas facile à créer ; il pourrait s'agir d'un profil à l'épreuve des humains ou de 32 validateurs ETH, ou simplement d'un compte avec un solde ETH non nul. Nous pourrions créer un réseau peer-to-peer plus résistant aux DOS en n'acceptant que les messages qui prouvent que l'expéditeur a un profil. Chaque profil peut recevoir jusqu'à 1000 messages par heure. Si un expéditeur triche, son profil est supprimé de la liste. Mais comment garantir le respect de la vie privée ?

Tout d'abord, la configuration : k est la clé privée de l'utilisateur et A=privtoaddr(k) l'adresse correspondante. Une liste d'adresses valides est publique (par exemple, un registre de la chaîne). Jusqu'à présent, cela reflète l'exemple de la preuve humaine : vous devez prouver que vous détenez la clé privée d'une adresse sans révéler laquelle. Mais nous ne voulons pas seulement la preuve que vous figurez sur la liste. Nous avons besoin d'un protocole qui vous permette de prouver que vous êtes sur la liste mais qui limite vos preuves.

Nous diviserons le temps en périodes : chacune dure 3,6 secondes (soit 1000 périodes par heure). Notre objectif est de permettre à chaque utilisateur d'envoyer un seul message par période ; s'il en envoie deux au cours de la même période, il est pris. Pour tenir compte des sursauts occasionnels, ils peuvent utiliser des périodes récentes. Ainsi, si un utilisateur dispose de 500 périodes inutilisées, il peut envoyer 500 messages en une seule fois.

Protocole

Commençons par une version de base utilisant des nullités. Un utilisateur génère un annulateur avec (N = \text{hash}(k, e)) où (k) est sa clé et (e) un numéro d'époque, puis le publie avec le message (m). ZK-SNARK obscurcit ensuite le (\text{hash}(m)). Rien de ce qui concerne (m) n'est vérifié au cours de ce processus, ce qui permet de lier la preuve à un seul message. Si un utilisateur lie deux preuves à deux messages distincts en utilisant le même annulateur, il risque de se faire prendre.

Nous passons maintenant à une version plus complexe. Dans ce cas, le protocole suivant révèle leur clé privée au lieu de simplement confirmer que quelqu'un a utilisé deux fois la même époque. Notre technique pivot repose sur le principe selon lequel "deux points déterminent une ligne". La révélation d'un point sur une ligne ne révèle pas grand-chose, mais la révélation de deux points dévoile toute la ligne.

Pour chaque époque (e), nous choisissons une ligne (L_e(x) = \text{hash}(k, e) \time x + k). La pente de la droite est (\text{hash}(k, e)), et l'ordonnée à l'origine est (k), toutes deux inconnues du public. Pour produire un certificat pour le message (m), l'expéditeur fournit (y = L_e(\text{hash}(m)) = \text{hash}(k, e) \times \text{hash}(m) + k)), ainsi qu'une preuve ZK-SNARK que le calcul de (y) est exact.

En résumé, ZK-SNARK est le suivant :

Intrants publics :

• ({A_1…A_n}) : Une liste de comptes valides

• (M) : Le message validé par le certificat

• (E) : Le numéro d'époque du certificat

• (Y) : Évaluation de la fonction de ligne

Intrants privés :

• (K) : Votre clé privée

Fonction de vérification :

• Vérifier si (\text{privtoaddr}(k)) existe dans ({A_1…A_n})

• Confirmer (y = \text{hash}(k, e) \text{hash}(m) + k)

Mais que se passe-t-il si quelqu'un utilise une époque deux fois ? Ils révèleront deux valeurs (m_1) et (m_2) ainsi que leurs valeurs de certificat (y_1 = \text{hash}(k, e) \text{hash}(m_1) + k) et (y_2 = \text{hash}(k, e) \text{hash}(m_2) + k). Nous pouvons alors utiliser ces deux points pour récupérer la ligne et, par la suite, l'ordonnée à l'origine, qui est la clé privée.

Ainsi, si quelqu'un réutilise une époque, il révèle par inadvertance sa clé privée à tout le monde. Selon le contexte, cela peut conduire à un vol de fonds ou simplement à la diffusion de la clé privée et à son intégration dans un contrat intelligent, ce qui entraîne la suppression de l'adresse associée.

Un système viable de refus de service anonyme hors chaîne, adapté aux réseaux peer-to-peer de la blockchain, aux applications de chat et à d'autres systèmes similaires, n'exige aucune preuve de travail. Le projet RLN se concentre essentiellement sur ce concept, bien qu'avec des modifications mineures (à savoir, il utilise à la fois des annulateurs et la technique de la ligne à deux points, ce qui simplifie la détection des cas où une époque est réutilisée).

Réputation négative de ZK

Imaginez la création de 0chan, un forum en ligne comme 4chan qui offre un anonymat complet (vous n'avez même pas de nom permanent), mais qui dispose d'un système de réputation pour promouvoir un contenu de meilleure qualité. Un tel système pourrait être doté d'une DAO de gouvernance chargée de signaler les messages qui enfreignent les règles du système, introduisant ainsi un mécanisme à trois coups.

Le système de réputation peut prendre en charge les réputations positives ou négatives ; toutefois, la prise en compte des réputations négatives nécessite une infrastructure supplémentaire. Les utilisateurs doivent donc intégrer toutes les données de réputation dans leurs preuves, même si elles sont négatives. Nous nous concentrerons principalement sur ce cas d'utilisation difficile, qui s'apparente à ce que Unirep Social vise à mettre en œuvre.

Linked Post : Connaissances de base

Tout le monde peut poster en transmettant un message sur la chaîne qui contient le post, accompagné d'un ZK-SNARK. Ce ZK-SNARK sert à prouver que (i) vous possédez une identité externe unique qui vous autorise à créer un compte, ou (ii) que vous avez déjà publié des messages spécifiques. Plus précisément, ZK-SNARK fonctionne comme suit :

Intrants publics :

• Nul, N

• Dernière racine de l'état de la blockchain, R

• Contenu du message ("mélangé" à la preuve pour la lier au message, sans aucun calcul)

Intrants privés :

• Votre clé privée, k

• Une identité externe (adresse A) ou l'annulateur, Nprev, utilisé dans le message précédent.

• Une preuve de Merkle, M, que la chaîne contient A ou Nprev

• Le ième message que vous avez publié avec ce compte

Fonction de vérification :

1. Confirmez que M est une branche de Merkle valide, en prouvant que (A ou Nprev, selon ce qui est fourni) est une feuille d'un arbre dont la racine est R.

2. Vérifiez N = enc(i, k) où enc est une fonction de chiffrement (par exemple, AES).

3. Si i=0, vérifiez A=privtoaddr(k), sinon vérifiez Nprev=enc(i-1,k).

Outre la validation de la preuve, la chaîne vérifie également (i) que R est effectivement une racine d'état récente et (ii) que l'annulateur N n'a pas été utilisé auparavant. Jusqu'à présent, elle ressemble aux pièces de monnaie préservant la vie privée décrites précédemment, mais nous avons ajouté un processus permettant de "frapper" de nouveaux comptes et supprimé la possibilité d'"envoyer" votre compte à différentes clés. Au lieu de cela, tous les annulateurs sont générés à l'aide de la clé d'origine. Nous utilisons ici enc pour rendre l'annulateur réversible. Si vous disposez de la clé k, vous pouvez décrypter n'importe quel annulateur spécifique de la chaîne ; si le résultat est un index valide plutôt qu'un charabia aléatoire (par exemple, nous pouvons simplement vérifier dec(N) < 2^64), vous saurez que l'annulateur a été généré à l'aide de la clé k.

Ajout de réputation :

Dans ce système, la réputation est explicite et intégrée à la chaîne. Certains contrats intelligents disposent d'une méthode appelée addReputation, qui prend en entrée le nullifier libéré avec un post et le nombre d'unités de réputation à ajouter ou à soustraire.

Nous avons étendu les données stockées sur la chaîne pour chaque message. Au lieu de stocker uniquement l'annulateur N, nous stockons {N, h¯, u¯} où :

• h¯ = hash(h, r) où h représente la hauteur du bloc de la racine de l'état référencé dans la preuve.

• u¯ = hash(u, r) où u est le score de réputation du compte (commençant à 0 pour les nouveaux comptes).

R est une valeur aléatoire ajoutée pour éviter que h et u ne soient trouvés par une recherche par force brute. En termes cryptographiques, l'ajout de R fait du hachage un engagement caché.

Supposons qu'un poste utilise la racine R et stocke {N, h¯, u¯}. Dans sa preuve, il renvoie à un message précédent qui stocke les données {Nprev, h¯prev, u¯prev}. La preuve du message doit également parcourir toutes les entrées de réputation publiées entre hprev et h. Pour chaque annulateur N, la fonction de vérification déchiffre N à l'aide de la clé de l'utilisateur k. Si le décryptage produit un index valide, il applique la mise à jour de la réputation. Si le total de toutes les mises à jour de la réputation est égal à δ, cela prouve que u = uprev + δ.

Si nous souhaitons mettre en œuvre la règle "trois coups et vous êtes éliminé", ZK-SNARK garantirait également u > -3. Si nous voulons une règle selon laquelle un message avec un rep ≥ 100 reçoit une étiquette spéciale "message à forte réputation", cela peut être fait aussi.

Pour améliorer l'évolutivité de ce système, nous pouvons le diviser en deux types de messages : les messages postaux et les ACR. Un message serait hors chaîne, bien qu'il doive faire référence à une ACR réalisée au cours de la semaine écoulée. Les ACR seraient en chaîne, traversant toutes les mises à jour de la réputation depuis l'ACR précédente de l'éditeur. De cette manière, la charge sur la chaîne est réduite à une transaction par message par semaine, plus une transaction pour chaque message de réputation.

Responsabiliser les parties centralisées

Il est parfois nécessaire de concevoir un système avec un "opérateur" centralisé. Les raisons peuvent varier : parfois, c'est pour des raisons d'évolutivité, parfois pour des raisons de protection de la vie privée, notamment des données détenues par l'opérateur. Par exemple, le système de vote MACI résistant à la coercition exige que les électeurs soumettent leurs votes sur la chaîne, cryptés à l'aide d'une clé détenue par un opérateur centralisé. Cet opérateur décrypte tous les votes de la chaîne, les comptabilise et affiche le résultat final. Ils utilisent ZK-SNARK pour prouver que tout ce qu'ils ont fait était exact. Cette complexité supplémentaire est cruciale pour garantir une protection solide de la vie privée (appelée résistance coercitive) : les utilisateurs ne peuvent prouver à personne comment ils ont voté, même s'ils le voulaient. Grâce à la blockchain et à ZK-SNARK, notre niveau de confiance dans l'opérateur reste minime. Des opérateurs malveillants peuvent enfreindre la résistance coercitive, mais comme les votes sont affichés sur la blockchain, ils ne peuvent pas tricher en censurant les votes. Et comme ils doivent fournir un ZK-SNARK, ils ne peuvent pas tricher en calculant mal les résultats.

Combinaison de ZK-SNARK et de MPC

Une utilisation plus avancée des ZK-SNARK est celle des calculs nécessitant une preuve, avec des données distribuées entre deux ou plusieurs parties, et nous ne voudrions pas qu'une partie ait connaissance des données des autres. Dans un scénario à deux parties, les circuits brouillés peuvent répondre aux exigences de confidentialité ; pour N parties, des protocoles de calcul multipartites plus complexes peuvent être utilisés. Les ZK-SNARK peuvent être intégrés à ces protocoles pour des calculs multipartites vérifiables. Cela permet de mettre en place des systèmes de réputation avancés, permettant à plusieurs participants d'effectuer des calculs conjoints sur leurs données privées. Les mathématiques permettant d'y parvenir efficacement n'en sont qu'à leurs débuts.

Que ne pouvons-nous pas rendre privé ?

ZK-SNARKs est très efficace pour créer des systèmes dans lesquels les utilisateurs ont des états privés. Cependant, il ne peut pas maintenir un état aussi privé que celui que personne ne connaît. Pour qu'une information soit prouvée, le prouveur doit la connaître en clair. Uniswap est un exemple difficile à privatiser. Dans Uniswap, il existe une "entité" logique centrale - le compte du fournisseur de liquidités, qui n'appartient à personne, et toutes les transactions Uniswap se font avec ce compte. Vous ne pouvez pas cacher l'état de ce compte car quelqu'un doit détenir cet état en clair pour le prouver, et chaque transaction nécessiterait sa participation active. Vous pourriez utiliser les circuits brouillés de ZK-SNARK pour créer une version centralisée, sécurisée et privée d'Uniswap, mais il n'est pas certain que les avantages l'emportent sur les coûts. Il se peut même qu'elle n'offre aucun avantage réel : les contrats doivent informer les utilisateurs des prix des actifs, et les variations de prix par bloc peuvent révéler l'activité des transactions. Les blockchains peuvent mondialiser les informations de l'État et les ZK-SNARK peuvent les privatiser, mais il n'existe pas de méthode solide pour mondialiser et privatiser simultanément les informations de l'État.

Assembler les primitives

Dans les sections précédentes, nous avons vu des exemples d'outils qui sont puissants en eux-mêmes, mais qui peuvent également servir d'éléments de base pour d'autres applications. Les annulateurs, essentiels pour les monnaies, réapparaissent maintenant dans d'autres cas d'utilisation. La technique du "lien coercitif" utilisée dans la section sur la réputation négative a une large application. Elle est très efficace pour de nombreuses applications dans lesquelles le "profil" d'un utilisateur change au fil du temps de manière complexe, et où vous souhaitez obliger les utilisateurs à suivre les règles du système tout en préservant leur vie privée. Les utilisateurs pourraient même être chargés de représenter leur "état" interne à l'aide d'un arbre de Merkle privé complet. L'outil "commitment pool" mentionné peut être construit avec ZK-SNARK. Si certaines applications ne peuvent pas fonctionner entièrement sur la chaîne et nécessitent un opérateur centralisé, ces mêmes techniques peuvent permettre à l'opérateur de rester honnête. ZK-SNARK est un outil puissant qui allie les avantages de la responsabilité et de la protection de la vie privée. Bien qu'ils aient leurs limites, dans certains cas, des applications intelligentes peuvent contourner ces contraintes. J'espère que d'autres applications adopteront ZK-SNARK et que d'autres applications seront créées pour combiner ZK-SNARK avec d'autres formes de cryptage dans les années à venir.

Clause de non-responsabilité：

1. Cet article est repris de[Foresightnews]. Tous les droits d'auteur appartiennent à l'auteur original[Jacob Ko]. Si vous avez des objections à cette réimpression, veuillez contacter l'équipe de Gate Learn, qui s'en chargera rapidement.
2. Clause de non-responsabilité : Les points de vue et les opinions exprimés dans cet article sont uniquement ceux de l'auteur et ne constituent pas un conseil en investissement.
3. Les traductions de l'article dans d'autres langues sont effectuées par l'équipe de Gate Learn. Sauf mention contraire, il est interdit de copier, distribuer ou plagier les articles traduits.