1. Introduction
ZK-SNARK est un système de preuve cryptographique qui permet à une entité de prouver que quelque chose est vrai sans révéler d'autres informations.
Les ZK-SNARK sont utiles dans plusieurs applications et domaines, tels que la blockchain et l'informatique vérifiable. Une application blockchain notable est utilisée dans ZK-Rollups.
Les ZK-Rollups sont des blockchains de deuxième couche construites au-dessus d'autres blockchains (telles que Ethereum) qui utilisent des ZK-SNARK (ou d'autres systèmes de preuve cryptographique) pour prouver la validité des transitions d'état. Autrement dit, chaque fois qu'une nouvelle mise à jour du réseau est effectuée (un nouveau lot de transactions est ajouté), un nouvel état du réseau est calculé et une preuve de la validité de cet état est générée. Le fait est qu’une seule entité est nécessaire pour générer cette preuve, et tout le monde peut alors avoir confiance en sa validité.
Les propriétés souhaitées fournies par ZK-Rollups sont généralement (i) l'évolutivité et/ou (ii) la protection de la vie privée. Les ZK-Rollups sont parfois appelés Rollups d'efficacité lorsque seule l'évolutivité est requise.
Pour calculer des preuves dans les ZK-Rollups conçus pour étendre l'EVM d'Ethereum, ZK-EVM peut être utilisé. Strictement défini, ZK-EVM est un ensemble de programmes cryptographiques (circuits) chargés de générer des preuves de connaissance nulle (ZKP), bien que parfois familièrement, il fasse également référence au ZK-Rollup universel compatible EVM dans son ensemble.
2.Définition de ZK-SNARK
Un SNARK est une preuve concise qu'une certaine affirmation est vraie. Formellement, cela démontre la connaissance de la trace d'exécution d'un algorithme qui produit une solution correcte à un problème. Il démontre plutôt une connaissance des valeurs non publiques et non constantes qui effectuent le suivi. Ces valeurs dans leur ensemble sont souvent appelées témoins. Les éléments du témoin, c'est-à-dire les parties de l'entrée de l'algorithme, constituent des témoins indépendants car ils existent avant l'exécution de l'algorithme et ne sont pas déterminés par d'autres éléments de la trace d'exécution. La valeur publique non constante de la trace d'exécution, qui spécifie l'instance de problème résolue par l'algorithme, est appelée une instruction publique.
ZK-SNARK signifie Zero-Knowledge Succinct Non-Interactive Knowledge Argument.
S - Simplicité
Simplicité - la preuve est « courte » et le temps de vérification est « rapide » :
Une preuve « courte » signifie que la taille de la preuve est sous-linéaire, par rapport à la taille du témoin.
Un temps de vérification « rapide » signifie que le temps d'exécution du vérificateur doit (i) être sous-linéaire dans la taille du témoin, et (ii) être linéaire dans la revendication publique.
Mais en fait, nous voulons que ce soit non seulement « concis », mais aussi « au niveau log-polynomial ».
Cela signifie que la taille de la preuve et le temps de vérification sont presque indépendants de la taille du témoin.
Montrer que la taille de π ne doit pas croître plus vite que quelques fois constantes le carré du logarithme de la taille du témoin w (pour w suffisamment grand) :
La taille de la preuve dépend du protocole ZK-SNARK spécifique. Pour Plonky2, c'est O(log^2(|w|)), mais c'est le "pire" cas. Par exemple, pour PLONK classique et Groth16, la taille de la preuve est O(1), qui est une constante.
Le temps de vérification t_v ne doit pas être supérieur à quelques fois constantes le carré du logarithme du témoin w, et linéaire dans la taille de la déclaration publique x (x et w sont suffisamment grands lorsqu'un seul d'entre eux change de taille).
N - Non interactif - La génération de la preuve se produit sans recevoir aucune donnée du vérificateur.
ARK - Preuve de connaissances - Semblable aux preuves classiques, mais le son n'est valable que contre les prouveurs polynomialement limités, alors que dans les preuves, le son est valable contre les prouveurs informatiques illimités. Nous discuterons du concept de son dans la section suivante.
ZK - Zero Knowledge - Aucune divulgation de témoin.
3. Propriétés des ZK-SNARK
Les ZK-SNARK ont trois propriétés principales, décrites ci-dessous :
Complétude : si le prouveur connaît la trajectoire d'exécution correcte de l'algorithme, alors le vérificateur doit croire que le prouveur a cette connaissance.
Solidité des connaissances : à moins que le prouveur ne connaisse réellement la trajectoire d'exécution correcte, le prouveur ne peut pas convaincre le vérificateur qu'il la connaît, mais il existe une très faible probabilité.
Connaissance nulle : le vérificateur ne sait rien de la trajectoire d'exécution, sauf qu'elle est correcte.
4. Système de preuve PLONKish ZK-SNARK
4.1 Introduction aux PLONKish ZK-SNARK et à leurs fonctions
Pour être appliqué à un certain algorithme, le système de preuve ZK-SNARK doit connaître le système d'équations sur le corps fini. Ces équations décrivent la relation entre les valeurs dans la table de trajectoire d'exécution de l'algorithme (la). structure de données qui stocke la trajectoire d'exécution) pour garantir que le calcul est intègre. Le langage utilisé pour exprimer ce système d’équations (également appelé système de contraintes) s’appelle l’arithmétique.
Le système de preuve PLONKish ZK-SNARK utilise l'arithmétique avec une puissance d'expression plus élevée que les anciens systèmes de preuve. La première nous permet d'utiliser des équations de système de contraintes de forme polynomiale arbitraire sur les variables de contrainte, alors que pour les systèmes de preuve plus anciens (c'est-à-dire les systèmes basés sur R1CS), ces équations étaient sous forme de polynômes linéaires et quadratiques. Cette fonctionnalité permet au système de preuve PLONKish ZK-SNARK d'avoir un impact positif sur l'efficacité informatique du prouveur et facilite son application à divers algorithmes. Par conséquent, de nombreux systèmes de preuve PLONKish ZK-SNARK sont apparus ces dernières années, tels que les classiques PLONK, Halo2, Kimchi, Plonky2, HyperPlonk, etc.
Dans Taiko, nous utilisons une variante du système de preuve Halo2 basée sur le schéma d'engagement polynomial KZG.
Le système d'épreuve PLONKish ZK-SNARK se compose de trois composants :
4.2 Plan d'engagement
Le schéma de promesse permet à un committer de publier une valeur, appelée promesse, qui lie le committer à un message sans révéler le message lui-même. Le committer peut ensuite ouvrir l'engagement et exposer le message validé, ou une partie de celui-ci, au vérificateur, qui peut vérifier si les informations exposées sont cohérentes avec l'engagement.
Différents auteurs décrivent un nombre différent d'algorithmes qui composent un schéma d'engagement. Cependant, il convient de mentionner au moins quatre de ces algorithmes :
Configuration : prend certains paramètres initiaux en entrée et génère des paramètres de configuration. Les paramètres spécifient (i) ce à quoi nous nous engageons (par exemple, pour le schéma d'engagement polynomial unaire, nous spécifions le domaine de coefficients et le degré maximum du polynôme auquel nous nous engageons), et (ii) le niveau de sécurité en bits. Nous pouvons simplement définir le niveau de sécurité comme suit : s'il faut un temps O(2^n) pour casser un système de cryptage, alors le système de cryptage a un niveau de sécurité de n bits.
Promesse : une promesse qui génère des messages basés sur des paramètres définis.
Ouverture partielle : génère une preuve d'ouverture partielle spécifique à une partie sélectionnée du message (par exemple, la valeur d'un polynôme unaire validé pour certains paramètres), ainsi que la définition des paramètres.
Validation : utilisez une attestation partiellement ouverte et définissez des paramètres pour vérifier si les informations exposées par le prouveur correspondent à la partie spécifiée du message correspondant à l'engagement spécifié.
*Pour certains schémas d'engagement, les algorithmes « setup » et « open » peuvent ne pas exister (par exemple, lors de l'utilisation d'une fonction de hachage pour valider des valeurs importantes).
Le plan d’engagement doit avoir les caractéristiques suivantes :
Liaison : une fois que le prouveur s'est engagé sur un message spécifique, il sera lié au message dans lequel il s'est engagé ;
Masquage : Une promesse de ne révéler aucune information sur le message. Le masquage peut être parfait, c'est-à-dire qu'une preuve partiellement ouverte ne révèle aucune information sur la partie non interrogée du message (par exemple, l'engagement KZG), ou non parfait, c'est-à-dire qu'une preuve partiellement ouverte révèle une partie des informations susmentionnées (par exemple, basée sur FRI). engagement polynomial).
Les schémas d'engagement peuvent être divisés en plusieurs types en fonction de l'objet cible : engagement à élément unique ; engagement vectoriel ; engagement polynomial ;
Les schémas d'engagement polynomiaux sont le seul type directement utilisé dans le système de preuve PLONKish ZK-SNARK. Pour les systèmes de preuve ci-dessus (comme PLONK classique, Halo2, Kimchi, Plonky2, etc.), le schéma d'engagement polynomial univarié est très important. Cependant, il existe désormais de nouvelles méthodes PLONKish ZK-SNARK basées sur des schémas d'engagement polynomiaux multilinéaires (par exemple HyperPlonk).
4.3 Preuve Oracle interactive
Une preuve oracle interactive est une preuve interactive dans laquelle le vérificateur a « accès à l'oracle » pour obtenir les messages du prouveur, peut les interroger de manière probabiliste et n'a pas besoin de lire l'intégralité des messages du prouveur.
4.4 Heuristique de Fiat-Shamir
L'heuristique Fiat-Shamir fournit un moyen de transformer des arguments interactifs (monnaie publique) en arguments non interactifs. Intuitivement, l'idée est de remplacer le défi aléatoire du validateur par le hachage du message précédent, mais les détails ne sont généralement pas précisés.
*Public Coin Protocol est un protocole dans lequel les validateurs n'envoient que des éléments aléatoires.
4.5 Principe de fonctionnement du système de preuve ZK-SNARK de style PLONK
Dans le système de preuve ZK-SNARK, une méthode de preuve Oracle interactive modifiée est utilisée pour prouver les connaissances du témoin, qui utilise des engagements polynomiaux pour fournir à Oracle un accès au message du prouveur et le rend sans interaction grâce à l'heuristique de Fiat-Shamir. Dans cette section, nous expliquerons le constructeur donné en détail.
Rappelons que l'application du système de preuve ZK-SNARK à un algorithme nécessite de construire un système de contraintes correspondant. Pour pouvoir le construire, nous définissons la structure de la table de trace d'exécution de l'algorithme et les valeurs constantes qu'elle contient. Nous utilisons le terme « circuit » pour désigner la structure complexe d'une table de trace d'exécution peuplée uniquement de constantes et du système de contraintes correspondant. Afin de générer une preuve ZK-SNARK pour une instance d'exécution d'un algorithme, nous devons synthétiser une instance de circuit pour celle-ci qui est une instance correspondante du circuit de l'algorithme et de la table de trace d'exécution (c'est-à-dire une table qui spécifie les constantes, les témoins, et valeurs de déclaration publique).
Considérons la structure de la table de suivi utilisée par un système de preuve ZK-SNARK de style PLONK. Toutes les colonnes d'un tel tableau appartiennent à l'un des trois types, que nous nommons selon la terminologie utilisée dans Halo2 et décrivons comme suit :
Colonnes fixes - leurs cellules contiennent des constantes de la table de trace d'exécution ;
Colonne Instance - utilisée pour stocker les valeurs de déclaration publique ;
Colonne de suggestion - où sont stockées toutes les données des témoins (y compris les valeurs des témoins indépendants et les résultats secrets calculés).
Pour résumer, notons ce qui suit :
Table de trace d'exécution (type PLONKish) = colonnes fixes + colonnes d'instance + colonnes de suggestions ; circuit = table de trace d'exécution contenant uniquement des constantes + système de contraintes ; instance de circuit = circuit + témoins dans sa table + déclarations publiques dans sa table ; déclaration publique, valeur de témoin indépendant) → Instance de circuit ; Appliquer le système de preuve ZK-SNARK à un certain algorithme = décrire le circuit + définir le processus de synthèse.
Pourquoi le terme « circuit » est-il largement utilisé dans ce contexte ? Initialement, lorsque seuls les systèmes de preuve ZK-SNARK basés sur R1CS étaient disponibles, il était pratique de représenter le système de contraintes sous la forme d'un circuit arithmétique dont la sortie devait être nulle. Nous pensons que dans le contexte des SNARK PLONKish, le terme « circuit » est utilisé pour des raisons historiques. Quoi qu'il en soit, considérons brièvement le circuit arithmétique utilisé pour les anciennes versions de ZK-SNARK.
Le circuit arithmétique pour les SNARK basés sur R1CS définit un polynôme à n variables sur un champ fini et dispose d'un schéma d'évaluation. Initialement, il est représenté sous la forme d'un graphe acyclique orienté (DAG) :
il comprend:
Entrée publique x, utilisée pour spécifier la valeur de la déclaration publique ;
Entrée secrète w, utilisée pour spécifier la valeur du témoin indépendant ;
Portes arithmétiques utilisées pour spécifier l'addition et la multiplication sur des champs finis.
Regardons un exemple de circuit arithmétique sur le domaine des nombres rationnels.
Nous partons du bas et travaillons avec les portes les plus basses du diagramme, c'est-à-dire (2 x 4 = 8) et (4 + 11 = 15), en enregistrant ces valeurs comme valeurs intermédiaires ;
Ensuite, nous montons d'une ligne (jusqu'à la deuxième ligne) et calculons la somme des deux valeurs intermédiaires (que nous avons obtenues à l'étape précédente), qui est (8 + 15 = 23) ;
Puisque nous n’avons que trois portes et que nous les avons toutes franchies, 23 est notre résultat final.
Une fois que le système de preuve PLONKish ZK-SNARK a synthétisé l'instance de circuit, les colonnes de la table de trace d'exécution de chaque instance sont codées sous forme de polynômes sur des champs finis de la manière suivante. Supposons que C_j(x) soit un polynôme décrivant la colonne j et que ω soit une racine primitive 2^k-ième, où k est choisi de telle sorte que 2^k soit légèrement plus grand que la hauteur initiale de l'instance de table. L'instance de table est remplie de lignes aléatoires (uniquement avec des cellules non nulles dans les colonnes suggérées) pour contenir 2^k lignes, et C_j(ω^i) est défini sur la valeur de la i-ème ligne du j-ème colonne de l’instance de table donnée. Le rôle du remplissage pour les propriétés à connaissance nulle sera expliqué plus tard.
L'énoncé « ω est une racine primitive 2^k-ième » signifie que ω^(2^k) = 1, et nous avons ω^t ≠ 1 pour tout entier positif t inférieur à 2^k.
Le système de contraintes est converti sous forme d'équation polynomiale en remplaçant les variables qu'il contient par les polynômes correspondants obtenus à partir des polynômes de colonne, en substituant "x fois ω élevé à une certaine puissance" à la place de x.
Par exemple, considérons l'équation du système de contraintes s(i) * (a(i) * b(i) - c(i+1)) = 0. Cela signifie que si s(i) est non nul, alors a(i) * b(i) doit être égal à c(i+1). Ici, a, b et c sont les colonnes suggérées, s est la colonne fixe et i est le numéro de ligne actuel.
Cette contrainte peut être appliquée à toutes les 2^k lignes comme suit. Soit S(x), A(x), B(x) et C(x) des polynômes dans les colonnes a, b, c et s respectivement. Nous espérons donc :
Cela signifie que tous les éléments de cet ensemble doivent être des racines de S(x) * (A(x) * B(x) - C(x * ω)). Ce polynôme doit donc être divisible par :
Parce que ω est une racine primitive d'ordre 2^k.
Z(x) = x^(2^k) - 1 est appelé un « polynôme de disparition » car il vaut 0 pour tous les x qui sont des éléments du groupe multiplicatif cyclique généré par ω. Par conséquent, S(x) * (A(x) * B(x) - C(x * ω)) mod Z(x) = 0 signifie que les contraintes ci-dessus sont valables pour les 2^k lignes.
Supposons que P_0(x), P_1(x), ... , P_m(x) soient des contraintes appliquées à toutes les 2^k lignes et soient cohérentes avec le polynôme S(x) * (A(x) * B(x) considéré ci-dessus ) - C(x * ω)) a une forme similaire. Si α est choisi au hasard par le vérificateur dans le corps fini, alors
Cela signifie qu'avec une probabilité extrêmement élevée, toutes ces contraintes sont satisfaites pour les 2^k lignes. Cette équation signifie que l’on peut trouver un polynôme quotient T(x) tel que
Par conséquent, pour que le vérificateur puisse croire que le prouveur connaît le contenu de la table de trace d'exécution qui satisfait toutes les m contraintes avec une très forte probabilité, il suffit de prouver que pour un α sélectionné aléatoirement, le prouveur a les occurrences P_0 (x), P_1(x ),..., les polynômes de colonne et les polynômes de quotient suggérés T(x) dans P_m(x) satisfont cette équation polynomiale. Le vérificateur peut le faire en demandant au prouveur de trouver la valeur d'un polynôme donné en un point aléatoire choisi par le vérificateur parmi les points non racine ζ de Z(x), et d'évaluer les deux côtés de cette équation à ce point. ζ. Je pense que le prouveur connaît probablement ces polynômes. Cette méthode peut être prouvée par le lemme de Schwartz-Zippel.
Pour rendre la génération de preuves non interactive, toutes les valeurs aléatoires générées par le vérificateur dans la version interactive doivent être obtenues à l'aide de l'heuristique de Fiat-Shamir.
Pour lier le prouveur à son polynôme de proposition et au polynôme quotient T(x), un schéma d'engagement polynomial est utilisé. Le prouveur prend des engagements sur ces polynômes, ouvre ces engagements en ζ (ou sur ζ * ω^q si une contrainte affecte les lignes i et i + q), et crée une preuve qui inclut (I) ces engagements, (II) La valeur du polynôme en ζ (ou sur ζ * ω^q si nécessaire) et (III) la preuve ouverte correspondante. En fait, pour raccourcir la preuve, utilisez l'ouverture multiple, c'est-à-dire générez une petite preuve pour les valeurs de tous les points polynomiaux. La preuve est donc concise.
Pour satisfaire la propriété de connaissance nulle, des lignes sélectionnées au hasard par le prouveur sont ajoutées à l'instance de la table de trace d'exécution, ce qui fait que sa hauteur est de 2 ^ k lignes. Ces lignes ne contiennent que des cellules non nulles dans la colonne de suggestion, car seule la colonne de suggestion contient les données que nous souhaitons masquer. Faites cela avant de construire les polynômes des colonnes de proposition de sorte que le nombre de paires de « valeurs de paramètre » révélées pendant la période d'ouverture de l'engagement soit inférieur au nombre de paires ajoutées aléatoirement pour chaque polynôme. Par conséquent, pour chaque polynôme de colonne de proposition, la quantité d'informations nécessaires pour la récupérer après l'ouverture de l'engagement est supérieure à la quantité d'informations du témoin. Cette situation aboutit à une connaissance nulle.
Pendant la phase de prétraitement, toutes les instances du circuit d'exécution effectuent certains des mêmes calculs, notamment la configuration et le calcul des polynômes à colonnes fixes et leurs engagements pour le schéma d'engagement polynomial. La partie des données produites par ces calculs est utilisée par le vérificateur et est souvent appelée clé de vérification. De même, la notion de clé de preuve peut être définie. Le schéma d'engagement polynomial sous-jacent détermine si les paramètres de confiance sont définis pendant la phase de prétraitement.