Préambule
Il s'agit de la quatrième partie d'une série d'articles explorant zk-SNARK, une technologie qui permet de prouver l'exactitude d'une connaissance sans avoir à révéler d'informations secrètes. Dans les parties précédentes, nous avons appris certains concepts complexes tels que le programme arithmétique quadratique et les appariements de courbes elliptiques (copier le lien de la partie 3 dans ce texte en gras).
Le programme d'arithmétique quadratique permet de représenter les problèmes de calcul à l'aide de polynômes, et les appariements de courbes elliptiques fournissent un outil de codage utile pour vérifier l'exactitude des données. En les combinant avec un autre algorithme, nous pouvons permettre au prouveur de prouver qu'il connaît la solution à un QAP particulier sans rien révéler d'autre. Cela garantit la confiance sans révéler de données sensibles.
Cet article se concentrera sur le protocole Pinocchio pour QAP , qui permet de prouver qu'une variable satisfait à certaines conditions sans avoir à révéler des détails sur la valeur de la variable.
Cette preuve est facile à créer et peut être authentifiée sans vérifier chaque étape de calcul, garantissant ainsi la confidentialité et la sécurité des données dans les applications blockchain et d'autres domaines nécessitant une authentification sécurisée et haute performance sans révéler d'informations privées.
Construction du protocole Pinocchio à connaissance non nulle
Nous commençons par illustrer le fonctionnement du protocole Pinocchio comme suit :
Soit G un groupe d'ordre premier p. Soit E : Fp → G un codage homomorphe. Comme suit:
pour un générateur g
Mettre
L'expression ci-dessus est une "carte bilinéaire" d'une courbe elliptique. Supposons que le prouveur P connaisse un témoin, comme indiqué ci-dessous.
pour le circuit arithmétique original. En simplifiant, elle connaîtra un polynôme tel que
À ce stade, nous trouverons encore cela un peu déroutant, n’est-ce pas ! Ne vous inquiétez pas, lisez attentivement chaque ligne et étudiez les formules, je vous explique l'idée principale de ce protocole juste en dessous !
V(verifier) veut tester P(Prover) à un point aléatoire (point aléatoire) z ∈ Fp par rapport aux valeurs du polynôme ci-dessus. P est interrogé pour la valeur de
et h(z) à un certain hasard z ∈ Fp. P encodera de manière homomorphe) ces valeurs et les enverra à V . Grâce aux propriétés de la carte homomorphe et bilinéaire, V peut vérifier que la valeur codée de manière homomorphe satisfait la même équation (20) ci-dessus.
Si tel est le cas, le vérificateur peut être sûr que le prouveur connaît réellement un témoin sans en avoir connaissance. Vous trouverez ci-dessous des informations plus détaillées sur l’idée principale qui vient d’être décrite.
La première étape du protocole consiste à créer une chaîne de référence commune (CRS), qui contient des codages homomorphes de multiples de z.
CRS aura deux objectifs :
Premièrement, le prouveur peut générer des codages homomorphes pour sa preuve en utilisant des combinaisons linéaires (combinaisons linéaires) des éléments de groupe du CRS sans connaître z.
Deuxièmement, la configuration d'un CRS élimine le besoin pour V de générer manuellement z et d'envoyer un message chiffré de z à P. Cela permet à cette preuve d'être totalement non interactive, car une fois le CRS est créé, P est en mesure de produire évidence convaincante.
Nous pouvons considérer CRS comme deux ensembles d'éléments de groupe public :
La clé d'évaluation, qui contient les éléments de groupe nécessaires à la construction de la preuve, et la clé de vérification, qui contient les éléments nécessaires à la vérification.
Chaîne de référence commune :
Choisissez au hasard α, βu, βv, βw, γ, z ∈ F ∗ p .
Mettez en œuvre le CRS ci-dessous, puis supprimez tous les éléments de groupe utilisés dans sa création (déchets toxiques).
Message du prouveur :
Supposons que Prover a le polynôme suivant :
Tout d'abord le Prouveur calcule h(x). Ensuite, la preuve du prouveur comprend les éléments suivants :
Vérification:
Dès réception de la preuve du prouveur, le vérificateur vérifie d'abord si les termes u(z), v(z), w(z), h(z) sont construits comme des combinaisons linéaires de calcul de termes dans CRS ou non, effectuez les 4 vérifications suivantes :
Vérifiez ensuite que chaque terme u(z), v(z), w(z) est généré à l'aide des mêmes coefficients linéaires :
Cela peut être vérifié en vérifiant l’équation suivante :
Enfin, nous vérifions la condition clé qui caractérise le critère de divisibilité polynomiale :
Nous avons construit avec succès le protocole Pinocchio à connaissance non nulle si et seulement si tous les contrôles de (21) à (26) sont valables.
Ensuite, nous passerons à l'étape d'analyse du protocole Pinocchio à connaissance non nulle !
Analyse du protocole Pinocchio à connaissance non nulle
Tout d'abord, nous devons apprendre la connaissance de l'hypothèse des exposants.
Supposons qu'Alice reçoive une paire d'éléments de groupe (x, αx)
Nous appelons une telle paire α−séparée. Ensuite, pour Alice, générer une autre paire α−séparée (y, αy) est irréalisable, sauf à la générer de la manière suivante :
Étant donné n paires séparées par α, si Alice renvoie une autre paire séparée par α, il doit s'agir d'une combinaison linéaire des paires séparées par α d'origine avec une probabilité élevée.
Pour en revenir à notre protocole, la principale condition que V doit vérifier est la condition de divisibilité polynomiale :
Cependant, en plus de cette équation, il devrait y avoir d’autres équations que le vérificateur doit également vérifier.
En effet, il est possible pour le prouveur de générer des valeurs qui satisfont à cette équation, mais ne sont pas générées à partir d'un témoin réel pour le circuit arithmétique. Pour garantir cela, Verifier a besoin d'un moyen de vérifier que les polynômes utilisés par Prover sont en réalité une combinaison linéaire des polynômes sous-jacents dans le CRS.
L'hypothèse de « connaissance de l'exposant » est utile car si une paire d'éléments de groupe envoyés par le prouveur et une paire donnée sont toutes deux α− séparées, la paire du prouveur doit être générée comme une combinaison linéaire des paires α− séparées données.
Par conséquent, le vérificateur peut utiliser une fonction de concaténation pour tester efficacement que ces deux paires sont toutes deux séparées α−, afin de garantir que le prouveur est généré à l'aide d'une représentation vraiment satisfaisante du circuit arithmétique. Plus précisément, pour deux paires (x, αx), (y, αy), ce qui suit est vrai :
Le vérificateur peut l'utiliser pour effectuer les vérifications suivantes :
En utilisant cette idée, le vérificateur doit vérifier trois choses :
À partir de là, nous pouvons prouver que le protocole Pinocchio satisfait à deux propriétés : l'exhaustivité et la solidité (cette preuve est assez compliquée, vous pouvez en savoir plus sur les documents sources que j'ai mis ci-dessous pour mieux comprendre ! )
Modification du protocole Pinocchio sans connaissance
Essentiellement, si le vérificateur V génère sa propre preuve s' = (s'₁, s'₂, …, s'ₙ), il peut calculer E(u'(z)), E (v'(z)), E (w'(z)), E(h'(z)) selon le protocole du prouveur.
Si ces valeurs diffèrent de E(u(z)), E(v(z)), E(w(z)), E(h(z)), que le prouveur calcule en s, alors le vérificateur conclut que la preuve du prouveur n'est pas (Explication des SNARKs Partie VI : Le protocole Pinocchio)
Pour éliminer cette violation de « connaissance nulle », le prouveur P ajoute un décalage aléatoire aux polynômes u, v et w (Pinocchio : Calcul presque pratique vérifiable)
Le décalage aléatoire sera un multiple de t(x), de sorte que tout reste le même mod t(x). Pour δ₁, δ₂, δ₃ aléatoires appartenant à Fp, sélectionnés au hasard :
Ensuite, P les évaluera à z à l'aide de CRS et soumettra des termes décalés (termes décalés) dans sa preuve à la place des termes non décalés correspondants.
Ainsi, l'étape de modification du protocole Pinocchio sans connaissance est terminée. À ce stade, tout le monde se sent confus =))))))
Mais c'est tout, merci encore d'avoir lu jusqu'ici. Si vous avez aimé cet article, n'oubliez pas de le suivre et de laisser une salve d'applaudissements.
Ainsi se termine ma série d'articles sur "Découverte de zk-SNARK" . J'espère que vous laisserez vos contributions afin que je puisse m'améliorer et être motivé pour écrire les prochains articles !
Source de l'article : Équipe Tech/Research AlphaTrue
Source de référence:
Chen, T., Lu, H., Kunpittaya, T. et Luo, A. (2022). Une revue de zk-snarks. Préimpression arXiv arXiv:2202.06877. https://arxiv.org/pdf/2202.06877.pdf