TL;DR
- **Quel est le processus de construction de SNARK ? **
Problèmes à prouver-Circuits arithmétiques-R1CS-Polynômes
- **Pourquoi convertir en polynôme à la fin ? **
En raison des caractéristiques des polynômes, le temps de vérification est effectivement raccourci et la simplicité est atteinte.
- **Comment atteindre zéro connaissance ? **
Pour le dire simplement, dans le processus de dérivation du polynôme, deux autres nombres aléatoires sont sélectionnés, de sorte que le polynôme dérivé peut empêcher le vérificateur d’obtenir les coefficients du polynôme d’origine, c’est-à-dire l’entrée secrète du démonstrateur, de sorte que réaliser ZK.
- **Comment parvenir à la non-interaction ? **
Avant le début de la preuve, un tiers est introduit, c’est-à-dire un paramètre de confiance, qui attribue au vérificateur d’origine la tâche de choisir des nombres aléatoires pour le paramètre de confiance, réalisant ainsi la non-interaction entre le vérificateur et le prouveur.
La technologie ZK a attiré beaucoup d’attention dans le domaine du Web3 au cours des deux dernières années. À partir de Rollup, de plus en plus de projets sur différentes pistes essaient d’utiliser la technologie ZK. Parmi eux, SNARK et STARK sont les deux termes les plus couramment entendus. Afin de mieux comprendre l’application de la technologie ZK à un stade ultérieur, ** cet article simplifiera la logique de preuve de SNARK d’un point de vue non technique, puis utilisera * * Le zk Rollup de Scroll ** est utilisé comme exemple pour illustrer le fonctionnement du système de preuve zk. **
Le but de l’article est d’expliquer la logique de base, qui est facile à lire. Il essaiera d’éviter l’utilisation de la terminologie, et n’entrera pas dans les détails tels que les transformations mathématiques. Veuillez m’excuser pour toute omission.
En janvier 2012, Alessandro Chiesa, professeur à l’Université de Californie à Berkeley, a co-écrit un article sur SNARK et a proposé le terme zk-SNARK.
zk-SNARK, nom complet Zero-Knowledge-Succinct Non-Interactive Argument of Knowledge, est un système de preuve utilisant la technologie ZK. ** Il convient de noter que SNARK est le nom d’une classe de schémas et qu’il existe de nombreuses méthodes de combinaison différentes qui peuvent implémenter SNARK. **
- Zero-Knowledge (Zero-Knowledge): Le contenu que seul le prouveur connaît sera caché, et personne d’autre ne peut le voir sauf le prouveur.
- Court (Succinct) : La preuve générée est petite et le temps de vérification est rapide.
- Non interactif (non interactif) : Il y a peu ou pas d’interaction entre le démonstrateur et le vérificateur.
- Argument : La vérification du vérificateur n’est valable que pour le certificateur avec une puissance de calcul limitée, car le certificateur avec une super puissance de calcul peut falsifier la preuve, c’est-à-dire que le système a une fiabilité de calcul.
- Connaissance : Le démonstrateur ne peut calculer la preuve que s’il connaît des informations que le vérificateur ne connaît pas.
Ce que zk-SNARK doit résoudre est le “problème de vérification des calculs”, c’est-à-dire si le vérificateur peut vérifier efficacement les résultats des calculs sans connaître la confidentialité du prouveur.
Ce qui suit utilisera le processus de construction simplifié de zk-SNARK pour illustrer comment le système combine la connaissance zéro pour réaliser une vérification efficace. **
** Construction Zk-SNARK **
Transformer le problème à prouver en un polynôme
Pour le dire simplement, l’idée de SNARK est de convertir la preuve de savoir si l’énoncé est vrai ou non en la preuve de savoir si l’égalité polynomiale est vraie ou non.
Tout le processus de conversion : problèmes à vérifier ➡ circuit arithmétique ➡ R1CS ➡ polynôme ➡ conversion entre polynômes
Question à vérifier➡Circuit arithmétique
Pour prouver si une question est vraie par le calcul, la question à prouver doit d’abord être transformée en un problème de calcul, et tout calcul peut être décrit comme un circuit arithmétique.
Les circuits arithmétiques sont généralement composés de constantes, de “portes d’addition” et de “portes de multiplication”. Grâce à la superposition de portes, on peut construire des polynômes complexes.
Le polynôme construit par le circuit arithmétique dans la figure ci-dessus est : (Inp1+Inp2)*(-1) = Sortie
Le problème est en réalité extrêmement compliqué à transformer en un circuit arithmétique, on peut simplement le comprendre comme suit : entrer du contenu, le contenu est transformé par le circuit, et finalement sortir un résultat. Tout de suite:
Sur la base du concept de circuits arithmétiques, nous construisons un circuit arithmétique de génération de preuves, à savoir :
Le circuit contient deux ensembles d’entrées, l’entrée publique x et l’entrée secrète w. L’entrée publique x signifie que le contenu est une valeur fixe du problème à prouver, qui est connue à la fois du vérificateur et du prouveur, et l’entrée secrète w signifie que le contenu n’est connu que du prouveur.
Le circuit arithmétique que nous avons construit est C(x, w) = 0, c’est-à-dire l’entrée x et w à travers le circuit, et le résultat de sortie final est 0. Lorsque le prouveur et le vérificateur savent que la sortie du circuit est 0 et que l’entrée publique est x, le prouveur doit prouver qu’il connaît l’entrée secrète w.
Circuit arithmétique ➡R1CS
Nous avons finalement besoin d’un polynôme, mais le circuit arithmétique ne peut pas être directement converti en polynôme, et R1CS est nécessaire comme intermédiaire entre les deux, donc le circuit arithmétique est d’abord converti en R1CS.
R1CS, nom complet Rank-1 Constraints (système de contraintes du premier ordre), est un langage de description de circuits, qui est essentiellement une équation matrice-vecteur. Plus précisément, R1CS est une séquence de trois vecteurs (a,b,c), et la solution de R1CS est un vecteur s, où s doit satisfaire l’équation :
Parmi eux, représente l’opération du produit interne.
La conversion mathématique spécifique ici peut être trouvée dans Vatalik : Programmes d’arithmétique quadratique : de zéro à héros
Il suffit de savoir que le rôle de **R1CS est de limiter la description de chaque porte dans le circuit arithmétique, afin que les vecteurs entre chaque porte satisfassent la relation ci-dessus. **
R1CS➡Polynôme
Après avoir obtenu le milieu de R1CS, nous pouvons le convertir en un équivalent polynomial.
Les conversions équivalentes entre matrices et polynômes peuvent être effectuées comme indiqué dans la figure suivante :
polynôme
convertir en matrice
Selon la nature de la transformation équivalente ci-dessus, pour une matrice qui satisfait R1CS, nous pouvons utiliser la méthode d’interpolation de Lagrange pour restaurer chaque coefficient du polynôme. Sur la base de cette relation, nous pouvons dériver la matrice R1CS sous la forme d’une relation polynomiale, à savoir :
Remarque : A, B, C représentent respectivement un polynôme
Un polynôme correspond à une contrainte matricielle R1CS correspondant au problème que nous voulons prouver.Grâce à la conversion ci-dessus, nous pouvons savoir que si les polynômes satisfont la relation ci-dessus, cela signifie que notre matrice R1CS est correcte, indiquant ainsi que le prouveur est dans le circuit arithmétique. L’entrée secrète pour est également correcte.
Jusqu’ici, notre problème est simplifié comme suit : le vérificateur sélectionne au hasard un nombre x, et demande au certificateur de prouver que A(x) * B(x)=C(x) est vrai. Si c’est vrai, il signifie que l’entrée secrète du certificateur est correcte.
Conversion entre polynômes
Dans les circuits arithmétiques complexes, il y a des dizaines de milliers de portes, et nous devons vérifier si chaque porte satisfait la contrainte R1CS. En d’autres termes, nous devons vérifier l’égalité de A(x) * B(x)=C(x) plusieurs fois, mais l’efficacité de la vérification séparée est trop faible. Comment pouvons-nous vérifier l’exactitude de toutes les contraintes de porte à une fois ? le sexe ?
Pour faciliter la compréhension, nous introduisons un P(x), soit P(x) = A(x) * B(x) – C(x)
Nous savons que tout polynôme peut être décomposé en polynômes linéaires tant qu’il a une solution. Nous divisons donc P(x) en F(x) et H(x), à savoir :
Alors F(x) est public, ce qui signifie qu’il existe un H(x) = P(x)/F(x), donc le polynôme que l’on veut vérifier se transforme finalement en :
A(x) * B(x) – C(x) : Contient les coefficients du polynôme, connus uniquement du démonstrateur, c’est-à-dire l’entrée secrète.
F(x) : Un polynôme public connu à la fois du vérificateur et du démonstrateur, c’est-à-dire une entrée publique.
H(x) : le démonstrateur le sait par calcul, mais le vérificateur est inconnaissable.
**Le dernier problème à prouver est : l’équation polynomiale A(x) * B(x) – C(x) = F(x) * H(x), est vraie sur tout x. **
Maintenant, il suffit de vérifier le polynôme une fois pour vérifier que toutes les contraintes satisfont les relations matricielles.
** Ici, nous avons terminé la transformation du problème à prouver en un polynôme qui n’a besoin d’être vérifié qu’une seule fois, réalisant la simplicité du système. **
Mais la simplicité de cette implémentation est de raccourcir le temps de vérification du vérificateur, alors qu’en est-il de la taille de la preuve ?
** En termes simples, dans le protocole de preuve, la structure arborescente de Merkle est utilisée, ce qui réduit efficacement la taille de la preuve. **
Une fois l’ensemble du processus de conversion terminé, deux problèmes se poseront naturellement :
- Pourquoi convertir en polynôme ?
Parce que les polynômes permettent la simplicité de la preuve. Le problème de la preuve à connaissance nulle est de vérifier que les calculs satisfont plusieurs contraintes, et les polynômes peuvent vérifier plusieurs contraintes en un point. En d’autres termes, le vérificateur doit vérifier n fois pour confirmer le problème, mais n’a plus besoin de vérifier qu’une seule fois pour confirmer l’exactitude de la preuve avec une probabilité élevée.
- Pourquoi peut-on établir deux polynômes A(x) * B(x) – C(x )= F(x) * H(x) en vérifiant un point sur le polynôme ?
Ceci est déterminé par les caractéristiques des polynômes, c’est-à-dire que le résultat du calcul d’un polynôme en tout point peut être considéré comme la représentation de son identité unique. Pour deux polynômes, ils ne se croiseront qu’en un nombre fini de points.
Pour les deux polynômes de degré d ci-dessus : A(x) * B(x) – C(x) et F(x) * H(x), s’ils ne sont pas égaux, ils ne seront qu’au plus d points Intersection, c’est-à-dire que les solutions en d points sont les mêmes.
Après avoir terminé la conversion polynomiale, nous entrerons dans l’étape de preuve polynomiale.
** Démontrer que le polynôme est vrai **
A titre d’illustration, nous utilisons le polynôme P(x) = F(x) * H(x).
Maintenant, le problème que le démonstrateur veut prouver est : sur tout x, P(x) = F(x) * H(x).
Le processus de vérification du polynôme ci-dessus par le démonstrateur et le vérificateur est le suivant :
- Le vérificateur choisit un point de défi aléatoire x, en supposant x = s ;
- Après que le démonstrateur ait reçu s, calculez P(s) et H(s), et donnez ces deux valeurs au vérificateur ;
- Le vérificateur calcule d’abord F(s), puis calcule F(s) * H(s), et juge si F(s) * H(s) = P(s) est vrai, et si c’est vrai, la vérification est réussie.
Mais si nous réfléchissons bien, nous constaterons qu’il y a quelques problèmes dans le processus ci-dessus :
- Le démonstrateur peut connaître l’information de toute l’équation. S’il reçoit un point aléatoire s, il peut calculer F(s), puis construire une paire de faux P(x) et H(x), de sorte que P(s ) = F(s) * H(s) pour tromper le vérificateur.
- Le démonstrateur n’utilise pas les s donnés par le vérificateur pour calculer F(s) et H(s), mais calcule avec d’autres valeurs pour tromper le vérificateur.
- La valeur reçue par le vérificateur est calculée par l’entrée publique et l’entrée privée du prouveur.Si le vérificateur a une grande puissance de calcul, il peut casser l’entrée privée du prouveur.
Pour résoudre les problèmes ci-dessus, nous effectuons les optimisations suivantes :
- Une fois que le vérificateur a sélectionné un point aléatoire s, il effectue un cryptage homomorphe sur s. Le cryptage homomorphe signifie la solution calculée après cryptage = la solution cryptée après calcul ; sous cette forme de cryptage, le prouveur peut calculer la solution, mais ne peut pas construire faux P(x) et H(x).
- Lorsque le vérificateur choisit le point de défi s, un autre paramètre aléatoire λ est sélectionné pour générer une relation linéaire supplémentaire entre s et λ. Le vérificateur envoie à la fois s et λ après cryptage homomorphe au prouveur. Le prouveur renvoie la preuve, et le vérificateur doit vérifier la relation entre le paramètre aléatoire λ et s en plus de vérifier si la preuve est vraie.
- **Visant le problème que le vérificateur peut déchiffrer l’entrée secrète, nous pouvons introduire ZK. ** En regardant l’ensemble de la preuve, nous pouvons constater que pendant le processus de vérification, le prouveur n’envoie que la valeur polynomiale calculée au vérificateur, et le vérificateur peut déduire le coefficient du polynôme à travers la valeur, qui est l’entrée secrète du prouveur. Afin d’empêcher le vérificateur de repousser, nous pouvons sélectionner deux nombres aléatoires supplémentaires et ajouter un ensemble de valeurs lors de la dérivation des polynômes A, B et C de R1CS, de sorte que le polynôme restauré soit d’un ordre de plus que le polynôme d’origine. , de sorte que la vérification Le lecteur ne peut pas obtenir les informations du polynôme d’origine à partir du polynôme chiffré pour réaliser ZK.
Après optimisation, nous avons constaté que le système de preuve nécessite toujours une interaction entre le vérificateur et le prouveur, comment parvenir à la non-interaction ?
Mettre en œuvre non interactif
** Afin d’obtenir une non-interaction, SNARK introduit des paramètres de confiance (Configuration). **
En d’autres termes, avant le début de la preuve, le droit du vérificateur de choisir des points de défi aléatoires est remis à un tiers de confiance. Après que le tiers a choisi le paramètre aléatoire λ, il place le λ chiffré dans le circuit R1CS. manière, CRS (Common Reference String, chaîne de référence publique) est généré. Le vérificateur peut obtenir son propre Sv du CRS, et le prouveur peut obtenir son propre Sp du CRS.
Il convient de noter que λ doit être détruit après avoir généré Sv et Sp. Si λ est divulgué, il peut être utilisé pour falsifier des transactions via une fausse vérification.
** Flux de travail zk-SNARK **
Après avoir compris le processus de construction de SNARK, basé sur le circuit arithmétique que nous avons construit et qui peut générer des preuves, le processus de preuve de zk-SNARK est le suivant :
- Configuration : (circuit C, λ) = (Sv, Sp)
A travers le circuit C et le paramètre aléatoire λ, les paramètres aléatoires Sv et Sp utilisés par le prouveur et le vérificateur ultérieurs sont générés.
Le démonstrateur calcule la preuve Π à travers le paramètre aléatoire Sp, l’entrée publique x et l’entrée secrète w.
- Vérifier(Sv,x,Π) == (∃ w st C(x,w))
Le vérificateur vérifie si C(x,w)=0 existe via le paramètre aléatoire Sv, l’entrée publique x et la preuve Π. En même temps, vérifiez si la preuve est calculée par le circuit C ou non.
À ce stade, nous avons terminé l’explication de l’ensemble du zk-SNARK. Examinons le cas d’application réel.
Cas : prenez le rollup zk de Scroll comme exemple
Le rôle du système de preuve est de permettre au prouveur de convaincre le vérificateur de croire une chose ;
Pour le système de preuve zk, il est nécessaire que le vérificateur croie que la preuve Zero-Knowledge (preuve à connaissance zéro) calculée par l’algorithme zk est vraie.
Nous prenons le zk Rollup de Scroll comme exemple pour illustrer le fonctionnement du système de preuve zk.
Le cumul fait référence au calcul hors chaîne et à la vérification en chaîne. Pour zk Rollup, une fois la transaction exécutée hors chaîne, le prouveur doit générer un certificat zk pour la nouvelle racine d’état générée après l’exécution de la transaction, puis transmettre le certificat au contrat L1 Rollup pour une vérification en chaîne.
Il convient de noter qu’il existe deux types de blocs dans zk Rollup :
- Bloc L1 Rollup : le bloc soumis à Ethereum
- Bloc L2 : un bloc composé de transactions soumises par les utilisateurs sur L2
Voici le flux de travail du rollup zk de Scroll :
- L’utilisateur initie une transaction en L2, le séquenceur récupère la transaction, exécute la transaction hors chaîne et génère un bloc L2 et une nouvelle racine d’état ; en même temps, soumet les données de transaction et la nouvelle racine d’état au contrat Rollup sur Ethereum (la soumission des données de transaction concerne la disponibilité des données) ;
- Lorsque le bloc L2 est généré, le coordinateur recevra la piste d’exécution du bloc du séquenceur, puis attribuera au hasard la piste à n’importe quel rouleau ;
- Roller convertit la piste d’exécution reçue en circuits et génère un certificat de validité pour chaque circuit, puis renvoie le certificat au coordinateur ;
- Chaque fois que k blocs L2 sont générés, le coordinateur enverra une tâche d’agrégation à un autre rouleau pour agréger les épreuves de k blocs en une seule épreuve agrégée ;
- Le coordinateur soumet une seule preuve d’agrégation au contrat Rollup, et le contrat Rollup vérifie la preuve d’agrégation en combinaison avec la racine d’état et les données de transaction précédemment soumises. Si la vérification réussit, le bloc correspondant est considéré comme finalisé sur Scroll.
Comme le montre le processus ci-dessus, Roller est le prouveur dans le système et le contrat Rollup est le vérificateur. Roller génère une preuve zk pour les transactions exécutées hors chaîne ; le contrat Rollup vérifie la preuve, et si la vérification réussit, le contrat Rollup adoptera directement la racine d’état soumise comme sa nouvelle racine d’état.
