Explorez les véritables raisons derrière l'émergence d'innovations intemporelles dans des preuves sans connaissance

Written par: lambdaclass

compilé par: mutourend; yiping, iOSG Ventures

1. une sorte de primitive cryptographique puissante qui permet à un prouveur de convaincre un vérificateur de l'exactitude d'une déclaration sans révéler aucune information au-delà de la déclaration. Les zk-SNARK ont reçu une large attention en raison de leurs applications dans le calcul privé vérifiable, la preuve de l'exactitude de l'exécution de programmes informatiques et les extensions de blockchain. Nous pensons que les zk-SNARK, comme nous le décrivons dans notre article, auront un impact significatif sur le façonnement du monde. Les zk-SNARK couvrent différents types de systèmes de preuve, utilisant différents schémas d'engagement polynomial, schémas arithmétiques, preuves oracles interactives ou preuves probabilistes testables. Mais ces idées et concepts de base remontent au milieu des années 1980.

Le développement des zk-SNARK s'est considérablement accéléré depuis le lancement de Bitcoin et Ethereum en raison de leur capacité à évoluer grâce à l'utilisation de preuves de connaissance nulle (souvent appelées preuves de validité pour ce cas d'utilisation spécifique). Les zk-SNARK jouent un rôle crucial dans l'évolutivité de la blockchain. Comme le décrit Ben-Sasson, ces dernières années ont vu une explosion cambrienne des preuves cryptographiques. Chaque système de preuve présente des avantages et des inconvénients et est conçu en tenant compte de compromis spécifiques. Les progrès du matériel, des algorithmes, des nouvelles preuves et des outils continuent d'améliorer les performances et conduisent à la création de nouveaux systèmes. Beaucoup de ces systèmes sont déjà utilisés et nous continuons à repousser les limites. Aurons-nous un système d’épreuves universel qui fonctionne pour toutes les applications, ou y aura-t-il plusieurs systèmes adaptés à différents besoins ? Nous pensons qu'il est très peu probable qu'un système de preuve domine tous les autres, pour des raisons telles que :

1) Diversité des applications.

2) Différents types de restrictions (concernant la mémoire, le temps de vérification, le temps de preuve).

3) Le besoin de robustesse (si un système de preuve est cassé, il existe d'autres systèmes de preuve).

Bien que les systèmes de preuves puissent subir des changements importants, ils partagent toujours une propriété importante : la vérifiabilité rapide des preuves. Les difficultés liées au changement de couches de base telles qu'Ethereum sont résolues dans une couche capable de vérifier les preuves et de s'adapter facilement aux nouveaux systèmes de preuves. Cet article fournira un bref aperçu des différentes caractéristiques des SNARK.

1) Hypothèses cryptographiques : fonction de hachage résistante aux collisions, problème de logarithme discret sur courbe elliptique, connaissance de l'exposant.

2) Paramètres transparents ou fiables.

3) Longueur de preuve : linéaire vs superlinéaire.

4) Temps du validateur : temps constant, logarithmique, sublinéaire, linéaire.

5) format preuve.

6) Facile à récurer.

7) Schéma arithmétique.

8) Polynôme univariable vs polynôme multivariable.

Cet article explorera les origines des SNARK, quelques éléments de base et l'ascension (et la chute) de différents systèmes de preuve. Cet article n’a pas pour objectif de fournir une analyse exhaustive des systèmes de preuve. Concentrez-vous plutôt sur ceux qui ont un impact sur nous. Bien entendu, ces développements n’ont été possibles que grâce au travail et aux idées de pionniers dans le domaine.

2. Connaissances de base

Les preuves sans connaissance ne sont pas nouvelles. Des définitions, des fondements, des théorèmes importants et même des protocoles importants ont été élaborés à partir du milieu des années 1980. Certaines des idées et protocoles clés utilisés pour construire des SNARK modernes ont été proposés dans les années 1990 (protocole sumcheck), avant même l'existence de Bitcoin (GKR en 2007). Les principaux problèmes liés à son utilisation sont liés au manque de cas d’usage solides (Internet n’a pas été développé dans les années 1990) et à la puissance de calcul requise.

1) Preuve de connaissance zéro : Origines (1985/1989).

Le domaine des preuves à connaissance nulle a émergé dans la littérature académique avec l'article "La complexité des connaissances des systèmes de preuve interactifs" de Goldwasser, Micali et Rackoff. Pour une discussion sur les origines, regardez la vidéo de janvier 2023 ZKP MOOC Lecture 1 : Introduction et histoire du ZKP. Cet article introduit les concepts de ploïdie, de fiabilité et de connaissance nulle, et fournit la construction de la résiduosité quadratique et de la non-résiduosité quadratique.

2) Protocole Sumcheck (1992).

Le protocole sumcheck a été proposé par Lund, Fortnow, Karloff et Nisan dans l'article de 1992 sur les méthodes algébriques pour les systèmes de preuve interactifs. C’est l’un des éléments constitutifs les plus importants des preuves interactives concises. Cela nous aide à réduire l’exigence d’une sommation d’évaluation polynomiale multivariée à une seule évaluation de points sélectionnés au hasard.

3) Goldwasser-Kalai-Rothblum (GKR) (2007).

Le protocole GKR (voir l'article Delegating Computation: interactive Proofs for Moldgles) est un protocole interactif dans lequel le prouveur opère de manière linéaire avec le nombre de portes dans le circuit et le vérificateur opère de manière sublinéaire avec la taille du circuit. Dans le protocole, le prouveur et le vérificateur s'accordent sur le circuit de fonctionnement en éventail du champ fini de profondeur d dd, où la couche d dd correspond à la couche d'entrée et la couche 0 00 correspond à la couche de sortie. Le protocole commence par une déclaration sur la sortie du circuit, qui se réduit à une déclaration sur la valeur de la couche précédente. Grâce à la récursion, cela peut être transformé en une déclaration des entrées du circuit, qui peut être facilement vérifiée. Ces réductions sont mises en œuvre via le protocole sumcheck.

4) Schéma d'engagement polynomial KZG (2010).

Kate, Zaverucha et Goldberg ont introduit un schéma d'engagement polynomial utilisant des groupes d'appariement bilinéaires dans 2010 Constant-Size Commitments to Polynomials and Their Applications. Un engagement consiste en un seul élément de groupe, et le committer ouvre effectivement un engagement à toute évaluation correcte du polynôme. De plus, grâce à la technologie batching, plusieurs évaluations peuvent être ouvertes. L'engagement KZG fournit l'un des éléments de base de plusieurs SNARK efficaces, tels que Pinocchio, Groth16 et Plonk. C'est également le cœur de l'EIP-4844. Pour comprendre intuitivement la technologie de traitement par lots, voir Pont Mina vers Ethereum ZK.

3. SNARKs pratiques utilisant des courbes elliptiques

La première construction pratique de SNARKs est apparue en 2013. Ces constructions nécessitent des étapes de prétraitement pour générer des preuves et des clés de vérification et sont spécifiques au programme/circuit. Ces clés peuvent être très volumineuses et dépendre de paramètres secrets inconnus de tous ; sinon, des preuves peuvent être falsifiées. Transformer du code en code prouvable nécessite de compiler le code dans un système de contraintes polynomiales. Au départ, cela devait être fait manuellement, ce qui prenait du temps et était sujet aux erreurs. Les avancées dans le domaine tentent d'éliminer certains problèmes majeurs :

1) Avoir des prouveurs plus efficaces.

2) Réduisez la quantité de prétraitement.

3) Ayez des configurations génériques plutôt que spécifiques à un circuit.

4) Évitez les paramètres de confiance.

5) Développer des moyens de décrire des circuits en utilisant des langages de haut niveau au lieu d'écrire manuellement des contraintes polynomiales.

Actuellement, les solutions SNARK pratiques utilisant des courbes elliptiques sont :

1) Pinocchio (2013)

2) Groth 16 (2016)

3) Bulletproofs & IPA (2016)

4) Sonic, Marlin et Plonk (2019)

5) Lookups (2018/2020)

6) Spartan (2019)

7) HyperPlonk (2022)

8) Schémas de pliage (2008/2021)

3.1 Pinocchio (2013)

Pinocchio (voir l'article Pinocchio : Calcul vérifiable presque pratique) est le premier zk-SNARK pratique et utilisable. SNARK est basé sur des programmes arithmétiques quadratiques (QAP). La taille de la preuve est initialement de 288 octets. La chaîne d'outils de Pinocchio fournit un compilateur du code C aux circuits arithmétiques et une traduction ultérieure vers QAP. Le protocole exige que le vérificateur génère des clés spécifiques au circuit. Il utilise des paires de courbes elliptiques pour vérifier les équations. Les asymptotiques asymptotiques pour la génération de preuves et la configuration des clés évoluent linéairement avec la taille du calcul, et la durée de la vérification évolue linéairement avec la taille des entrées et sorties publiques.

3.2 Groth 16 (2016)

L'article de Groth de 2016 sur la taille des arguments non interactifs basés sur des appariements introduit un nouvel argument de connaissances qui améliore les performances des problèmes décrits par R1CS. Il a une taille de preuve minimale (seulement trois éléments de groupe) et une vérification rapide impliquant trois appariements. Cela implique également des étapes de prétraitement pour obtenir une chaîne de références structurées. Le principal inconvénient est que chaque programme à certifier nécessite une configuration de confiance différente, ce qui n'est pas pratique. Groth16 a été utilisé dans ZCash. Pour plus de détails, veuillez également consulter le blog Un aperçu du système de preuve Groth 16.

3.3 Bulletproofs & IPA (2016)

L'une des faiblesses de KZG PCS est qu'il nécessite une configuration fiable. L'article 2016 Arguments efficaces à connaissance nulle pour les circuits arithmétiques dans le paramètre de journal discret de Bootle et al. a introduit un système d'arguments efficace à connaissance nulle pour les ouvertures d'engagement de Pedersen qui satisfait la relation de produit interne. Les systèmes de preuve de produit interne ont un prouveur linéaire, avec communication et interaction logarithmiques, mais avec vérification de durée linéaire. Il a également développé un schéma d'engagement polynomial qui ne nécessite pas de configuration fiable. Halo 2 et Kimchi adoptent tous deux l'idée IPA PCS.

3.4 Sonic, Marlin et Plonk (2019)

Sonic, Plonk et Marlin résolvent le problème des paramètres de confiance pour chaque programme dans Groth16 en introduisant une chaîne de référence structurée commune et modifiable. Marlin fournit un système de preuve basé sur R1CS, qui est le cœur d'Aleo.

Plonk a introduit un nouveau schéma arithmétique (appelé plus tard Plonkish) et a utilisé une vérification de grand-produit pour les contraintes de copie. Plonkish permet également l'introduction de portes spécialisées pour certaines opérations, dites portes sur mesure. Plusieurs projets ont des versions personnalisées de Plonk, notamment Aztec, ZK-Sync, Polygon ZKEVM, Mina's Kimchi, Plonky2, Halo 2 et Scroll, entre autres. Voir le blog Tout ce que vous vouliez savoir sur Plonk.

3.5 Recherches (2018/2020)

Gabizon et Williamson ont introduit les plookups en 2020, en utilisant une grande vérification de produit pour prouver qu'une valeur est contenue dans une table de valeurs précalculée. Bien que des arguments de recherche aient été précédemment proposés dans Arya, leur construction nécessitait de déterminer les multiplicités des recherches, ce qui était moins efficace. L'article de PlonkUp montre comment introduire l'argument plookup dans Plonk. Le problème avec ces arguments de recherche est qu'ils obligent le prouveur à payer pour la table entière, quel que soit le nombre de recherches. Cela signifie que le coût des grandes tables est considérable et que de nombreux efforts ont été déployés pour réduire le coût du prouveur en fonction du nombre de recherches qu'il utilise.

Haböck présente LogUp, qui utilise des dérivées logarithmiques pour convertir les contrôles de produits en sommes de réciproques. LogUp est essentiel aux performances de Polygon plonky2 ZKEVM (Beyond Limits: Pushing the Boundaries of ZK-EVM), qui nécessite de diviser la table entière en plusieurs modules STARK. Les modules doivent être correctement liés et des recherches dans les tables sont nécessaires pour appliquer cette opération. L'introduction de LogUp-GKR exploite le protocole GKR pour améliorer les performances de LogUp. Caulk est le premier argument de recherche dont le temps de preuve a une relation sous-linéaire avec la taille de la table, avec un temps de prétraitement de O ( N log ⁡ N ) et un stockage de O ( N ), où N est la taille de la table. Plusieurs autres programmes ont suivi, tels que Baloo, flookup, cq et calfeutrage+. Lasso a proposé plusieurs améliorations pour éviter de commettre une table lorsqu'elle a une structure donnée. De plus, le prouveur de Lasso ne paie que pour les entrées de table accessibles par les opérations de recherche. Jolt exploite Lasso pour prouver l'exécution de la machine virtuelle via des recherches.

3.6 Spartan (2019)

Spartan fournit des IOP pour les circuits décrits à l'aide de R1CS, exploitant les propriétés des polynômes multivariables et le protocole sumcheck. En utilisant un schéma d'engagement polynomial approprié, il produit un SNARK transparent avec un prouveur de durée linéaire.

3.7 HyperPlonk (2022)

HyperPlonk est construit sur l'idée de Plonk utilisant des polynômes multivariables. Il ne s'appuie pas sur des quotients pour vérifier l'application des contraintes, mais s'appuie plutôt sur le protocole sumcheck. Il prend également en charge des contraintes de haut degré sans nuire au temps d'exécution du prouveur. Puisqu'il repose sur des polynômes multivariables, il n'est pas nécessaire d'effectuer une FFT et le temps d'exécution du prouveur évolue linéairement avec la taille du circuit. HyperPlonk introduit de nouvelles IOP de permutation adaptées aux domaines plus petits et un protocole d'ouverture par lots basé sur sumcheck, qui réduit le travail du prouveur, la taille de la preuve et le temps du vérificateur.

3.8 Schémas de pliage (2008/2021)

Nova introduit l'idée des schémas de pliage, qui est une nouvelle façon de mettre en œuvre le calcul incrémentiel vérifiable (IVC). Le concept d'IVC remonte à Valiant, qui a montré comment combiner 2 preuves de longueur k kk en une seule preuve de longueur k kk . L'idée est que la preuve récursive peut être utilisée pour prouver que l'exécution de l'étape i ii à l'étape i + 1 i+1i+1 est correcte, et pour vérifier la transition de l'étape i − 1 i-1i−1 à l'étape i ii est correct, prouvant ainsi le cas de tout calcul de longue durée.

Nova peut très bien gérer les calculs uniformes ; plus tard, avec l'introduction de Supernova, il a été étendu pour gérer différents types de circuits. Nova utilise une version décontractée de R1CS et travaille sur des courbes elliptiques conviviales. L'utilisation de cycles de courbes conviviaux (par exemple, les courbes Pasta) pour implémenter IVC est également utilisée dans Pickles, le module de base principal de Mina, pour obtenir des états concis. Cependant, l'idée du pliage est différente de la vérification récursive SNARK. L'idée des accumulateurs est plus profondément liée au concept de preuves par lots. Halo introduit le concept d'accumulation comme alternative aux combinaisons de preuves récursives. Protostar fournit une solution IVC non uniforme pour Plonk, prenant en charge les portes de haut degré et les recherches vectorielles.

4. SNARK utilisant des fonctions de hachage résistantes aux collisions

À peu près à la même époque que le développement de Pinocchio, il y avait quelques idées pour générer des circuits/schémas arithmétiques qui pourraient prouver l'exactitude de l'exécution d'une machine virtuelle. Bien que l'arithmétique du développement d'une machine virtuelle puisse être plus complexe ou moins efficace que l'écriture de circuits dédiés pour certains programmes, elle offre l'avantage que tout programme, aussi complexe soit-il, peut être prouvé en démontrant qu'il s'exécute correctement dans une machine virtuelle. Les idées de TinyRAM ont ensuite été affinées avec la conception de Cairo vm et des machines virtuelles ultérieures telles que zk-evms ou zkvms générique. L’utilisation d’une fonction de hachage résistante aux collisions élimine le besoin d’une configuration fiable ou l’utilisation de l’arithmétique de courbe elliptique, mais au prix de preuves plus longues.

1) TinyRAM (2013)

Dans SNARKs for C, un SNARK basé sur PCP est développé pour prouver l'exactitude de l'exécution d'un programme C compilé sur TinyRAM (Reduced Instruction Set Computer). L'ordinateur utilise l'architecture Harvard avec une mémoire vive adressable au niveau des octets. Tirant parti du non-déterminisme, la taille du circuit évolue de manière quasi-linéaire avec la taille du calcul, permettant une gestion efficace des boucles arbitraires liées aux données, du flux de contrôle et des accès à la mémoire.

2) STARKs (2018)

STARKs a été proposé par Ben Sasson et al. Son implémentation a une taille de preuve de O(log2n), a des prouveurs et vérificateurs rapides, ne nécessite pas de configuration fiable et est considérée comme sécurisée post-quantique. Il a été utilisé pour la première fois par Starkware/Starknet avec la machine virtuelle Cairo. Ses composants clés comprennent :

Représentation intermédiaire algébrique (AIR)

et le protocole FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity).

Les STARK sont également utilisés par d'autres projets (Polygon Miden, Risc0, Winterfell, Neptune), ou certaines adaptations de ceux-ci (ZK-Sync's Boojum, Plonky2, Starky).

3) Ligero (2017)

Ligero introduit un système de preuve dont la taille de preuve est O (racine n), où n est la taille du circuit. Il organise les coefficients polynomiaux sous forme matricielle et utilise des codes linéaires.

Brakedown s'appuie sur Ligero et introduit l'idée de schémas d'engagement polynomiaux indépendants du domaine.

5. Quelques nouveaux développements dans ZKP

L'utilisation de différents systèmes de preuve en production montre les avantages de chaque méthode et apporte de nouveaux développements. Par exemple, l'arithmétique Plonky fournit un moyen simple d'inclure des portes personnalisées et des arguments de recherche ; FRI affiche d'excellentes performances en tant que PCS, devant Plonky. De même, l'utilisation du grand contrôle de produit dans AIR (aboutissant à un AIR aléatoire avec prétraitement) améliore ses performances et simplifie l'accès mémoire aux arguments. Les promesses basées sur les fonctions de hachage ont fait leur chemin - soit sur la base de la vitesse des fonctions de hachage dans le matériel, soit sur l'introduction de nouvelles fonctions de hachage compatibles avec SNARK.

1) Nouveau schéma d'engagement polynomial (2023)

Avec l'émergence de SNARK efficaces basés sur des polynômes multivariés (tels que Spartan ou HyperPlonk), il existe un intérêt croissant pour de nouveaux schémas d'engagement adaptés à de tels polynômes. Binius, Zeromorph et Basefold proposent tous de nouvelles formes dédiées aux polynômes multilinéaires. Binius a l'avantage d'une surcharge nulle pour représenter les types de données (alors que de nombreux systèmes de preuve utilisent des éléments de champ d'au moins 32 bits pour représenter un seul bit) et fonctionne sur le domaine binaire. La promesse Binius est basée sur Brakedown et est conçue pour être indépendante du domaine. Basefold généralise FRI aux codes au-delà de Reed-Solomon, ce qui donne lieu à un PCS indépendant du domaine.

2) Systèmes de contraintes personnalisables (CCS) (2023)

CCS généralise R1CS tout en capturant l'arithmétique R1CS, Plonkish et AIR sans aucune surcharge. La combinaison de CCS avec Spartan IOP donne naissance à SuperSpartan, qui prend en charge des contraintes de haut degré sans obliger le prouveur à supporter des coûts cryptographiques qui évoluent avec le degré de contrainte. En particulier, SuperSpartan génère des SNARK pour AIR avec un prouveur en temps linéaire.

6. Conclusion

Cet article décrit les progrès de SNARK depuis son introduction au milieu des années 1980. Les progrès de l’informatique, des mathématiques et du matériel, associés à l’introduction de la blockchain, ont donné naissance à de nouveaux SNARK plus efficaces, ouvrant la porte à de nombreuses applications susceptibles de transformer notre société. Les chercheurs et les ingénieurs ont proposé des améliorations et des ajustements aux SNARK en fonction de leurs besoins, en se concentrant sur la taille de la preuve, l'utilisation de la mémoire, les paramètres de transparence, la sécurité post-quantique, le temps de preuve et le temps du vérificateur.

Bien qu'il y ait initialement deux lignes principales (SNARK et STARK), les frontières entre les deux ont commencé à s'estomper, en essayant de combiner les avantages de différents systèmes de preuve. Par exemple, combiner différents schémas arithmétiques avec de nouveaux schémas d'engagement polynomial. On peut s'attendre à ce que de nouveaux systèmes de preuve continuent d'émerger et que les performances s'améliorent, et il sera difficile pour certains systèmes qui nécessitent un certain temps d'adaptation de suivre ces évolutions, à moins que les outils puissent être facilement utilisés sans modifier certaines infrastructures de base. .

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!