Cet article décode cette technologie à l'aide des mathématiques, en illustrant comment elle peut prouver la vérité d'une connaissance sans révéler aucune information.

Compilé par : DODO Research

Auteur : 0xAlpha Co-fondateur @DeriProtocol

Introduction

Zk-SNARK, ou argument de connaissance succinct et non interactif à connaissance nulle, permet à un vérificateur de confirmer qu'un prouveur possède certaines connaissances (appelées témoins) qui satisfont à des relations spécifiques sans révéler d'informations sur les connaissances elles-mêmes.

La génération d'un zk-SNARK pour un problème spécifique comprend les quatre étapes suivantes :

• Convertir un problème (ou une fonction) en un circuit arithmétique.
• Ce circuit est ensuite traduit en une équation matricielle.
• Cette équation matricielle est ensuite convertie en un polynôme qui doit être divisible par un polynôme minimal spécifique.
• Enfin, cette divisibilité est exprimée en points de courbes elliptiques sur un corps fini, où la preuve a lieu.

Les trois premières étapes ne font que transformer la représentation de l'énoncé original. La dernière étape projette la déclaration de la troisième étape dans un espace crypté à l'aide d'un cryptage homomorphique, ce qui permet au prouveur de vérifier les déclarations en miroir qui s'y trouvent. Étant donné que cette projection utilise un cryptage asymétrique, il n'est pas possible de revenir de la déclaration de l'étape 3 à la déclaration d'origine, ce qui garantit l'exposition à la connaissance zéro.

Le bagage mathématique requis pour lire cet article est comparable au niveau d'algèbre attendu des étudiants de première année des STEM. Le seul concept qui pourrait poser problème est celui de la cryptographie à courbe elliptique. Pour ceux qui ne la connaissent pas, vous pouvez la considérer comme une fonction exponentielle avec une base spéciale, en gardant à l'esprit que son inverse n'est pas résolu.

Cet article suivra les règles de notation suivantes :

Matrices : Lettres majuscules en gras, par exemple A ; écrit sous forme explicite \N
Vecteurs : Lettre minuscule avec flèches, écrite sous forme explicite [ ] ; tous les vecteurs sont des vecteurs-colonnes par défaut \N- Scalaires
Scalaires : Représentées par des lettres normales

Prenons l'exemple de la question suivante :

f(x)=x^3+x^2+5 (1)

Supposons qu'Alice veuille prouver qu'elle connaît une vérité. Nous allons passer en revue l'ensemble de la procédure qu'Alice doit suivre pour générer un zk-SNARK pour sa preuve.
Cette question peut sembler trop simple parce qu'elle n'implique pas de flux de contrôle (par exemple, if-then-else). Cependant, il n'est pas difficile de convertir les fonctions avec flux de contrôle en expressions arithmétiques. Par exemple, considérez le problème suivant (ou la "fonction" dans les langages de programmation) :

f(x, z) :
if(z==1) :
returnxxx+xx+5
else :
return xx+5

La réécriture de ce problème sous la forme de l'expression arithmétique suivante (en supposant que z appartient à (0,1)) n'est pas plus complexe 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 notre discussion.

Étape 1 : Circuit arithmétique

L'équation (1) peut être décomposée en opérations arithmétiques de base :

Cela correspond au circuit arithmétique suivant :

Nous nous référons également à l'équation (2) comme un ensemble de 4 "contraintes primaires", chaque contrainte décrivant la relation d'une porte arithmétique dans le circuit. En général, un ensemble de n contraintes primaires peut être résumé sous la forme d'un programme arithmétique quadratique (PAQ), qui sera expliqué plus loin.

Étape 2 : Matrice

Tout d'abord, définissons un vecteur "témoin" comme suit :

où y, s1, s2 et s3 sont définis comme dans l'équation (2).
Typiquement, pour un problème avec m entrées et n portes arithmétiques (c'est-à-dire n-1 étapes intermédiaires et la sortie finale), ce vecteur témoin sera de (m+n+1) dimensions. Dans le monde réel, le nombre n peut être extrêmement élevé. Par exemple, pour les fonctions de hachage, n est généralement de l'ordre du millier.

Construisons ensuite trois matrices n(m+n+1) A, B, C afin de pouvoir réécrire l'équation (2) comme suit :

L'équation (3) n'est qu'une autre représentation de l'équation (2) : chaque ensemble (ai, bi, ci) correspond à une porte du circuit. Nous pouvons le constater en développant explicitement l'équation matricielle :

LHS=RHS est donc exactement identique à l'équation (2), et chaque ligne de l'équation matricielle correspond à une contrainte primaire (c'est-à-dire une porte arithmétique dans le circuit).

Nous avons sauté les étapes de la construction (A, B, C), qui sont en fait relativement simples. Il suffit de les convertir en matrice selon les contraintes primaires correspondantes pour déterminer le contenu de chaque ligne de (A, B, C), c'est-à-dire (ai, bi, ci). Prenons la première ligne comme exemple : nous pouvons facilement voir que pour rendre la première contrainte primaire x multipliée par x égale à s1, nous devons multiplier [0,1,0,0,0], [0, 1,0,0,0] et [0,0,0,0,1,0,0] par le vecteur s.

Nous avons donc réussi à convertir le circuit arithmétique en une équation matricielle, à savoir l'équation (3). Dans le même temps, nous avons également changé l'objet qui doit être prouvé pour être maîtrisé pour le vecteur témoin.

Étape 3 : Polynômes

Construisons maintenant une matrice n(n+m+*1) PA, qui définit un ensemble de polynômes concernant z :

S'assurer que la fonctionprend les valeurs suivantes à {1, 2, 3, 4} satisfait aux conditions :

Nous pouvons alors réécrire A comme suit :

Il s'agit de quatre séries d'équations linéaires impliquant six variables qui peuvent être résolues à l'aide de méthodes traditionnelles. Toutefois, l'interpolation lagrangienne, qui exploite les particularités du problème, est un moyen plus efficace de résoudre l'AP dans ce cas. Nous sautons ici le processus de résolution de l'AP, qui est un peu fastidieux mais simple.

De même, nous construisons PB et PC séparément pour B et C. Nous pouvons alors réécrire l'équation matriciellecomme suit :

En observant chaque ligne séparément, il est évident que ces quatre lignes correspondent à la même expression évaluée en quatre points différents. Par conséquent, l'équation matricielle ci-dessus est équivalente à :

Étape 3 : Point de courbe elliptique

Réécrivez l'équation (4) comme suit :

où i(z)=1 est juste un polynôme trivial de degré zéro en z utilisé pour unifier les équations - tous les termes sont quadratiques. La nécessité de cette mesure apparaîtra clairement dans un instant. Notez que cette équation ne contient que l'addition et la multiplication de polynômes en z.

Veuillez noter que les opérations arithmétiques, l'addition (+) et la multiplication (X), sont également mises en correspondance avec les opérations correspondantes dans le domaine fini des points de la courbe elliptique. Les symboles et sont utilisés pour éviter toute confusion et indiquer qu'il s'agit d'opérations de terrain redéfinies.

Ensuite, nous expliquerons plus en détail les étapes pratiques.

Cryptographie à courbe elliptique

La théorie générale des courbes elliptiques dépasse largement le cadre de cet article. Aux fins du présent document, une courbe elliptique est définie comme un mappage d'un corps premier Fp à la fonction E, où E comprend des points tels que y^2=x^3+ax+b (appelés points de la courbe elliptique, ou ECP en abrégé).

Veuillez noter que si nous avons parlé d'arithmétique normale jusqu'à présent, lorsque vous passez à un champ de nombres premiers, les opérations arithmétiques sur les nombres sont effectuées à l'aide de l'arithmétique modulaire. Par exemple, a+b=a+b(mod p), où p est l'ordre de Fp.

D'autre part, l'addition de deux points de courbe elliptique est définie comme indiqué ci-dessous :

Plus précisément, l'addition de P et Q de deux PCU :

Trouvez l'intersection de la ligne PQ et de la courbe R et définissez-la comme -(P+Q).
Passez au point "miroir" R' de R sur la courbe.
Nous définissons donc l'addition des points de la courbe elliptique P+Q=R' :

Notez que cette règle s'applique également au cas particulier où l'addition d'une ECP est utilisée, auquel cas la tangente à ce point sera utilisée.

Supposons maintenant que nous choisissions au hasard un point G et que nous lui attribuions le chiffre 1. (Cette "cartographie initiale" semble un peu arbitraire. Nous en discuterons plus tard). Et pour tout n appartenant à Fp, on définit :

E(N)=G+G+G+.....+G=G multiplié par n

Il existe une expression d'opération. Définissez l'opération +G comme "générateur", noté g. La définition ci-dessus est alors équivalente à :

Après avoir défini l'addition, la relation linéaire suivante devient évidente :

Par conséquent, toute relation linéaire (ou contrainte) dans Fp sera préservée dans l'espace crypté B grâce à cette correspondance. Par exemple, l'équation l + m = n dans Fp conduira à

Cependant, comme l'équation (5) qu'Alice veut prouver est sous forme quadratique, elle n'est pas suffisamment linéaire. Pour traiter les termes quadratiques, nous devons définir la multiplication dans l'espace crypté. C'est ce qu'on appelle un appariement, ou une carte bilinéaire, que j'expliquerai dans la section suivante.

Carte bilinéaire

Supposons que G1, G2 et GT soient des groupes d'ordre premier g. Une fonction d'appariement, ou carte bilinéaire, est définie comme suit :

Chaîne de référence commune

Cet ensemble est appelé "clé de preuve" (PK). Notez que la représentation des vecteurs dans E() doit être comprise comme des vecteurs de points de la courbe elliptique, où chaque point est mappé à partir de l'élément vectoriel correspondant. Ainsi, ces 11 vecteurs comprennent en réalité 62 ( =42+63+63+63 ) points de la courbeelliptique. Ces 62 PCU seront fournies à Alice, le prouveur. Dans un scénario général, pour un problème comportant m entrées et n contraintes primaires, le PK contiendra 2n + 3(m+n+1)*3 = 11n + 9m + 9 ECP.

Les calculs suivants seront effectués simultanément :

L'ensemble du processus est appelé "clé de vérification" (VK). Seuls 7 points de courbe elliptique (ECP) sont concernés, qui doivent être fournis au vérificateur. Il convient de noter que, quel que soit le nombre d'entrées et de contraintes primaires impliquées dans le problème, VK est toujours composé de 7 ECP.

En outre, il convient de mentionner que la "configuration de confiance" et le processus de génération des PK et VK ne doivent être effectués qu'une seule fois pour un problème spécifique.

Démonstration et vérification

En possession de la clé publique (PK), Alice calculera les points de courbe elliptique (ECP) suivants :

Ces 9 points de la courbe elliptique sont cruciaux pour un argument de connaissance succinct et non interactif (zk-SNARK) !

Notez qu'Alice se contente d'effectuer des combinaisons linéaires sur les points de la courbe elliptique dans la clé publique. Ce point est particulièrement important et sera rigoureusement contrôlé lors de la vérification.

Alice présente maintenant la preuve zk-SNARK, ce qui nous amène enfin au processus de vérification, qui se déroule en trois étapes.

Tout d'abord, il est nécessaire de confirmer que les 8 premiers points de la courbe elliptique sont bien les combinaisons linéaires des points de la chaîne de référence commune.

Clause de non-responsabilité：

1. Cet article est repris de[chaincatcher]. Tous les droits d'auteur appartiennent à l'auteur original[0xAlpha Co-founder @ DeriProtocol]. 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.