Auteur : 0xAlpha Co-fondateur @DeriProtocol ; Compilateur : DODO Research
Présentation
Les zk-SNARKs, ou « zero-knowledge concise non-interactive arguments of knowledge », permettent à un vérificateur de confirmer qu’un prouveur possède certaines connaissances spécifiques, connues sous le nom de témoins, qui satisfont des relations spécifiques sans rien révéler sur le témoin lui-même.
La génération de zk-SNARK pour un problème spécifique se compose des quatre phases suivantes :
- Convertir un problème (ou une fonction) en un circuit de grille arithmétique.
- Ce circuit est ensuite traduit en une formule matricielle.
- Cette formule matricielle est ensuite convertie en un polynôme, qui doit être divisible par un polynôme minimum spécifique.
- Enfin, cette divisibilité est représentée par des points de courbe elliptique dans des corps finis, où la preuve a lieu.
Les trois premières étapes convertissent simplement la représentation de l’instruction d’origine. La dernière étape utilise le chiffrement homomorphe pour projeter l’énoncé de l’étape 3 dans l’espace cryptographique, ce qui permet à l’étalon de vérifier l’instruction miroir dans celui-ci. Étant donné que cette projection utilise la cryptographie asymétrique, il n’est pas possible de remonter jusqu’à la déclaration originale de la troisième étape, ce qui garantit une exposition à connaissance nulle.
Les connaissances en mathématiques requises pour lire cet article sont équivalentes au niveau d’algèbre de première année pour les majeures en STIM. Le seul concept qui peut être difficile est probablement le chiffrement à courbe elliptique. Pour ceux qui ne sont pas familiers avec cela, elle peut être considérée comme une fonction exponentielle avec une cardinalité spéciale, tout en gardant à l’esprit que son inverse reste non résolu.
Cet article suivra les règles de notation suivantes :
- Matrice : lettres majuscules en gras, par exemple A ; Écrivez explicitement dans la forme
- Vecteur : lettres minuscules avec des flèches, écrites sous forme explicite [ ] ; Par défaut, tous les vecteurs sont des vecteurs colonnaires
- Scalaire : Représentation de lettres régulières
Prenons cette question à titre d’exemple :
f(x)=x^3+x^2+5 (1)
Disons qu’Alice veut prouver qu’elle en connaît un. Nous allons passer en revue toute la procédure qu’Alice doit suivre pour générer des zk-SNARK pour ses preuves.
Cette question peut sembler trop simple parce qu’elle n’implique pas de flux de contrôle (par exemple, si-alors-si). Cependant, il n’est pas difficile de convertir une fonction avec un flux de contrôle en une expression arithmétique. Par exemple, considérons la question suivante (ou « fonction » dans un langage de programmation) :
f(x, z) :
if(z==1) :
return x*x*x+x*x+5
autre:
return x*x+5
Il est facile de réécrire ce problème dans l’expression arithmétique suivante (en supposant que z appartient à (0,1)), ce qui n’est pas beaucoup plus compliqué que l’équation (1).
f(x,z)=(z-1)(x^2+5)+z(x^3+x^2+5)
Dans cet article, nous continuerons à utiliser l’équation (1) comme base de discussion.
Étape 1 : Circuit de grille arithmétique
L’équation (1) peut être décomposée en opérations arithmétiques de base suivantes :
! [Le pouvoir des preuves à divulgation nulle de connaissance : décoder mathématiquement les zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-122a4a0e88-dd1a6f-cd5cc0.webp)
Cela correspond au circuit de porte arithmétique suivant :
! [Le pouvoir des preuves à divulgation nulle de connaissance : décoder mathématiquement les zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-9001e3d244-dd1a6f-cd5cc0.webp)
Nous nous référons également à l’équation (2) comme un ensemble de 4 « contraintes du premier ordre », chacune décrivant la relation d’une porte arithmétique dans un circuit. En général, un ensemble de n contraintes du premier ordre peut être généralisé sous la forme d’une procédure arithmétique quadratique (PAQ), qui sera expliquée ci-dessous.
Étape 2 : Matrice
Tout d’abord, définissons un vecteur « témoin » comme suit :
! [Le pouvoir des preuves à divulgation nulle de connaissance : décoder mathématiquement les zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-1157f4c74a-dd1a6f-cd5cc0.webp)
où y, s1, s2, s3 sont les mêmes que ceux définis dans l’équation (2).
En général, pour un problème avec m entrées et n portes arithmétiques (c’est-à-dire n-1 étapes intermédiaires et sortie finale), ce vecteur témoin sera (m+n+1) dimensionnel. Dans un problème pratique, le nombre n peut être très grand. Par exemple, pour une fonction de hachage, n est généralement égal à quelques milliers.
Ensuite, construisons trois matrices n*(m+n+*1) A,B,C afin de pouvoir réécrire l’équation (2) comme suit :
! [Le pouvoir des preuves à divulgation nulle de connaissance : décoder mathématiquement les zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-a9e2164b2f-dd1a6f-cd5cc0.webp)
L’équation (3) n’est qu’une autre représentation de l’équation (2) : chaque groupe (ai, bi, ci) correspond à une porte dans le circuit. Il suffit de développer sans ambiguïté la formule matricielle pour voir ceci :
! [Le pouvoir des preuves à divulgation nulle de connaissance : décoder mathématiquement les zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-630e507588-dd1a6f-cd5cc0.webp)
Ainsi, LHS=RHS est exactement la même chose que l’équation (2), et chaque ligne de l’équation matricielle correspond à une contrainte du premier ordre (c’est-à-dire une porte arithmétique dans le circuit).
Nous avons sauté les étapes de construction (A, B, C), qui sont relativement simples. Il suffit de les convertir sous forme matricielle selon les contraintes de premier niveau correspondantes, de manière à déterminer le contenu de chaque ligne de (A, B, C), c’est-à-dire (ai, bi, ci). Prenons l’exemple de la première ligne : il est facile de voir que pour que la contrainte du premier ordre x soit multipliée par x égal à s1 tient, il faut multiplier [0,1,0,0,0,0], [0,1,0,0,0] et [0,0,0,1,0,0] avec le vecteur s.
Ainsi, nous avons réussi à convertir le circuit arithmétique de la porte en une formule matricielle, c’est-à-dire l’équation (3). Dans le même temps, nous avons également changé l’objet dont il faut prouver qu’il doit être maîtrisé en un vecteur témoin s.
Étape 3 : Polynômes
Maintenant, construisons une matrice n*(*n+m+*1) PA qui définit un ensemble de polynômes autour de z :
! [Le pouvoir des preuves à divulgation nulle de connaissance : décoder mathématiquement les zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-94169f2b1d-dd1a6f-cd5cc0.webp)
! [Le pouvoir des preuves à divulgation nulle de connaissance : décoder mathématiquement les zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-2c37ea96a6-dd1a6f-cd5cc0.webp)
Il s’agit de quatre ensembles d’équations linéaires pour six variables qui peuvent être résolues par des méthodes traditionnelles. Cependant, un moyen plus efficace de résoudre PA dans ce cas est l’interpolation lagrangienne, qui tire parti de la spécificité du problème. Ici, nous sautons le processus de résolution de PA, qui est un peu fastidieux mais simple.
! [Le pouvoir des preuves à divulgation nulle de connaissance : décoder mathématiquement les zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-fcac15b335-dd1a6f-cd5cc0.webp)
À l’intérieur :
! [Le pouvoir des preuves à divulgation nulle de connaissance : décoder mathématiquement les zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-a7d3309d02-dd1a6f-cd5cc0.webp)
Étape 4 : Points de la courbe d’ellipse
Réécrivez l’équation (4) comme suit :
! [Le pouvoir des preuves à divulgation nulle de connaissance : décoder mathématiquement les zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-f974fc7c93-dd1a6f-cd5cc0.webp)
où i(z)=1 n’est qu’un polynôme trivial d’ordre zéro pour z, qui est utilisé pour unifier l’équation - tous les termes sont quadratiques. La nécessité de le faire deviendra bientôt évidente. Notez que cette équation ne contient que l’addition et la multiplication du polynôme de z.
! [Le pouvoir des preuves à divulgation nulle de connaissance : décoder mathématiquement les zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-8fdea08104-dd1a6f-cd5cc0.webp)
Ensuite, nous expliquerons plus en détail les étapes réelles.
Chiffrement par courbe elliptique
La théorie générale des courbes elliptiques dépasse largement le cadre de cet article. Pour les besoins de cet article, les courbes elliptiques sont définies comme une correspondance entre le domaine premier Fp et la fonction E, où E inclut des points satisfaisant y^2=x^3+ax+b (appelés points de courbe elliptique, ou ECP en abrégé).
Notez que si nous avons parlé d’arithmétique régulière jusqu’à présent, maintenant que nous convertissons en corps premiers, les opérations arithmétiques sur les nombres sont effectuées de manière modulaire. Par exemple, a+b=a+b(mod p), où p est de l’ordre de Fp.
D’autre part, la définition de l’addition de deux points de courbe elliptique est illustrée dans la figure suivante :
! [Le pouvoir des preuves à divulgation nulle de connaissance : décoder mathématiquement les zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-baf3cc3cbe-dd1a6f-cd5cc0.webp)
Plus précisément, l’ajout de deux PCU, P et Q :
Trouvez l’intersection de la droite PQ et de la courbe R, définie par -(P+Q)
Basculez jusqu’au point « miroir » R’ sur la courbe pour R.
Nous définissons donc l’addition des points de courbe elliptique P+Q=R’ :
Notez que cette règle s’applique également à des cas particuliers, c’est-à-dire lorsqu’un ECP auto-additif, où la tangente du point sera utilisée.
Supposons maintenant que nous choisissions un point G au hasard et que nous y associions le nombre 1. (Cette « cartographie initiale » semble un peu arbitraire.) Nous y reviendrons plus tard). Ensuite, pour que tout n appartienne à Fp, on définisse :
E(N)=G+G+G+…+G=G
Il s’agit d’une expression d’action. Les actions qui définissent +G sont des « générateurs » et sont notées g. Dans ce cas, la définition ci-dessus est équivalente à :
! [Le pouvoir des preuves à divulgation nulle de connaissance : décoder mathématiquement les zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-bb825d6ba2-dd1a6f-cd5cc0.webp)
Pour ceux qui ne sont pas familiers avec les courbes elliptiques, vous pouvez comparer ce mappage à une fonction exponentielle régulière où le cardinal g remplace les nombres réels. Les opérations arithmétiques se comportent de la même manière. Cependant, une différence essentielle est que la fonction inverse de g^n n’est pas calculable. C’est-à-dire qu’il n’y a aucun moyen de calculer la version de la courbe elliptique ! [Le pouvoir des preuves à divulgation nulle de connaissance : décoder mathématiquement les zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-c989bcd81c-dd1a6f-cd5cc0.webp)。 C’est, bien sûr, la base de la cryptographie à courbe elliptique. Un tel mappage est connu sous le nom de chiffrement unidirectionnel.
Notez qu’étant donné une courbe elliptique, puisque la sélection de G (et donc du générateur g) est arbitraire (à l’exception des points sur l’axe des abscisses), il existe un nombre infini de façons de la cartographier. Le choix (G ou g) peut être analogue au choix de la cardinalité d’une fonction exponentielle (2^x, 10^x, e^x, etc.) dans le cadre du bon sens.
! [Le pouvoir des preuves à divulgation nulle de connaissance : décoder mathématiquement les zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-ce9f261ecc-dd1a6f-cd5cc0.webp)
Cependant, l’équation (5) qu’Alice veut prouver est quadratique et donc pas assez linéaire. Afin de traiter les termes quadratiques, nous devons définir la multiplication dans l’espace cryptographique. C’est ce qu’on appelle une fonction d’appariement, ou une carte bilinéaire, et nous l’expliquerons ci-dessous.
Cartographie bilinéaire
! [Le pouvoir des preuves à divulgation nulle de connaissance : décoder mathématiquement les zk-SNARKs] (https://img-cdn.gateio.im/resized-social/moments-40baef27dd-146a4881e5-dd1a6f-cd5cc0)
Chaîne de référence commune
! [Le pouvoir des preuves à divulgation nulle de connaissance : décoder mathématiquement les zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-17e9a49fa0-dd1a6f-cd5cc0.webp)
L’ensemble du processus est appelé « clé de vérification », ou VK en abrégé. Il n’y a que 7 points de courbe elliptique (ECP) impliqués ici, qui doivent être fournis au vérificateur. Il est important de noter que quel que soit le nombre d’entrées et de contraintes de premier niveau impliquées dans le problème, VK est toujours composé de 7 ECP.
De plus, il convient de mentionner que la « configuration de confiance » et le processus de génération de PK et de VK peuvent être effectués une seule fois pour un problème particulier.
Preuve et vérification
Maintenant, avec la clé publique (PK), Alice calculera les points de courbe elliptique (ECP) suivants :
! [Le pouvoir des preuves à divulgation nulle de connaissance : décoder mathématiquement les zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-c7eacd57e6-dd1a6f-cd5cc0.webp)
Ces 9 points de courbe elliptique sont la clé des preuves non interactives concises à connaissance nulle (zk-SNARKs) !
Notez qu’Alice ne fait en fait que quelques opérations combinatoires linéaires sur les points de la courbe elliptique dans la clé publique. Ceci est particulièrement critique et sera vérifié lors de la validation.
Maintenant qu’Alice a remis la preuve zk-SNARK, entrons enfin dans le processus de vérification, qui est un processus en trois étapes.
Tout d’abord, il est important de s’assurer que les 8 premiers points de la courbe elliptique sont vraiment une combinaison linéaire de ces points dans la chaîne de référence générique.
! [Le pouvoir des preuves à divulgation nulle de connaissance : décoder mathématiquement les zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-4cf599e8c2-dd1a6f-cd5cc0.webp)
Si les trois vérifications sont vraies, alors l’équation (5) est vérifiée, donc nous croyons qu’Alice connaît le témoin.
Expliquons le raisonnement derrière l’équation. Prenons l’exemple de la première équation de la première partie, qui est valable en raison de sa nature bilinéaire :
! [Le pouvoir des preuves à divulgation nulle de connaissance : décoder mathématiquement les zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-0032ace846-dd1a6f-cd5cc0.webp)
Cependant, comme Alice ne connaît pas la valeur du symbole alpha, elle n’est pas en mesure de calculer cette addition explicitement. La seule façon pour elle de trouver une paire qui satisfasse l’équation (EA, EA’) était d’utiliser le même ensemble de vecteurs s chacun, calculez ! [Le pouvoir des preuves à divulgation nulle de connaissance : décoder mathématiquement les zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-933d054c72-dd1a6f-cd5cc0.webp).
Références
« Zk-SNARKs : Sous le capot » (Vitalik Buterin)
« Un examen des preuves à connaissance nulle » (Thomas Chen, Abby Lu, Jern Kunpittaya et Alan Luo)
« Pourquoi et comment fonctionne zk-SNARK : explication définitive » (Maksym Petkus)
Site Web : Zero-Knowledge Proofs (en anglais seulement)
Wikipédia : Courbe elliptique
Wikipédia : Champ fini
Wikipédia : Cryptographie basée sur l’appariement
