IOSG : Quelle est la force motrice de l'innovation continue dans les preuves sans connaissance ?

Auteur : LambdaClass

Traduction : mutourend; Yiping, IOSG Ventures

1 Introduction

Les preuves de connaissances sans connaissance, succinctes et non interactives (zk-SNARK), sont une puissante primitive cryptographique qui permet aux prouveurs de convaincre le 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 des 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 sans connaissance (souvent appelées preuves de validité pour ce cas d'utilisation spécifique). Les zk-SNARK jouent un rôle essentiel dans l'évolutivité de la blockchain. Comme le dit Ben-Sasson, ces dernières années ont été marquées par 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 preuve puissent subir des changements importants, ils partagent tous une caractéristique importante : une vérifiabilité rapide. Les difficultés associées à la modification des couches de base telles qu'Ethereum peuvent être résolues en disposant d'une couche qui vérifie les preuves et peut s'adapter de manière flexible aux nouveaux systèmes de preuves. Cet article présentera brièvement les 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 : les origines (1985/1989).

Le domaine de la preuve à connaissance nulle est apparu 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 l'origine, vous pouvez regarder la vidéo de janvier 2023 ZKP MOOC Lecture 1 : Introduction et histoire du ZKP. Cet article introduit les concepts d'exhaustivité, de fiabilité et de connaissance nulle, et propose 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 de additionner les évaluations polynomiales multivariées à 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 Moldus) 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 parviennent à un accord 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 les engagements de taille constante envers les polynômes et leurs applications en 2010. 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) Avoir des configurations universelles 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) Recherches (2018/2020)

6) Spartan (2019)

7) HyperPlonk (2022)

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

3.1 Pinocchio (2013)

Pino cchio ( Voir l'article Pinocchio : Nearly Practical Verifiable Computation) 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 en 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 de génération de preuves et de configuration des clés sont asymptotiquement linéaires avec la taille du calcul, et la durée de la vérification est linéaire 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 l'étape de prétraitement consistant à 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. Dans l'article 2016 Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting de Bootle et al., un système d'argumentation efficace à connaissance nulle pour les ouvertures d'engagement de Pedersen qui satisfait la relation de produit interne a été introduit. 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 d'utiliser 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 pouvant être mise à jour. 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 de grandes vérifications de produits pour prouver qu'une certaine valeur est contenue dans un tableau de valeurs pré-calculé. Bien que des arguments de recherche aient été précédemment proposés dans Arya, leur construction nécessite de déterminer les multiplicités de recherches, ce qui est 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. Le lancement de LogUp-GKR exploite le protocole GKR pour améliorer les performances de LogUp. Caulk est le premier argument de recherche dans lequel le temps du prouveur a une relation sous-linéaire avec la taille de la table. Son temps de prétraitement est ‍O (N log ⁡ N) et le stockage est O (N), où N est la taille de la table. Plusieurs autres solutions ont suivi, telles 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 utilise Lasso pour prouver l'exécution de machines virtuelles via des recherches.

3.6 Spartan (2019)

Spartan fournit des IOP pour les circuits décrits à l'aide de R1CS, en 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 le quotient pour vérifier le respect des contraintes, mais 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 la charge de 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 au même moment où Pinocchio était développé, 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 de la 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 pour C, un SNARK basé sur PCP est développé pour prouver l'exactitude de l'exécution du programme C, qui est compilé dans 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 a une relation quasi-linéaire avec la taille du calcul, gérant ainsi efficacement les boucles arbitraires liées aux données, le flux de contrôle et les accès à la mémoire.

2) STARKs (2018)

• STARKs a été proposé par Ben Sasson et al. La taille de preuve qu'il implémente est O (log2n), il a des prouveurs et vérificateurs rapides, ne nécessite pas de configuration fiable et est considéré comme sûr 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 car PCS affiche d'excellentes performances, devant Plonky. De même, l'utilisation du grand contrôle de produit dans AIR (entraînant un AIR aléatoire avec prétraitement) améliore ses performances et simplifie les arguments d'accès à la mémoire. 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) Nouveaux schémas d'engagement polynomiaux (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 de représenter les types de données sans surcharge (alors que de nombreux systèmes de preuve utilisent au moins des éléments de champ de 32 bits pour représenter un seul bit) et fonctionne sur le champ binaire. Binius promet d'être basé sur Brakedown et est conçu pour être indépendant 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, capturant simultanément 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 de 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!