Notre point de vue très subjectif sur l'histoire de Zero-Knowledge Proofs

Les arguments de la connaissance (zk-SNARKS), succinct et non interactif à connaissance nulle sont de puissantes primitives cryptographiques qui permettent à une partie, le prouveur, de convaincre une autre partie, le vérificateur, qu'une déclaration est vraie sans rien révéler d'autre que sa validité. Ils ont attiré l'attention du public grâce à leurs applications dans le domaine du calcul privé vérifiable, en prouvant l'exactitude de l'exécution de programmes informatiques et en aidant à faire évoluer les blockchains. Nous pensons que les SNARKs auront un impact significatif sur le façonnement de notre monde, comme nous le décrivons dans notre billet. SNarkS regroupe différents types de systèmes de preuve, en utilisant différents schémas d'engagement polynomial (PCS), des schémas d'arithmétisation, des preuves Oracle interactives (IOP) ou des preuves vérifiables par probabilité (PCP). Cependant, les idées et concepts de base remontent au milieu des années 1980. Le développement s'est considérablement accéléré après l'introduction du Bitcoin et de l'Ethereum, qui se sont révélés être un cas d'utilisation passionnant et puissant, car vous pouvez les redimensionner en utilisant des preuves à connaissance nulle (généralement appelées preuves de validité pour ce cas d'utilisation en particulier). Les SNARKs sont un outil essentiel à l'évolutivité de la blockchain. Comme le décrit Ben-Sasson, nous avons assisté ces dernières années à une explosion cambrienne de preuves cryptographiques. Chaque système de preuve présente des avantages et des inconvénients et a été conçu dans un souci de compromis. Les avancées en matière de matériel, de meilleurs algorithmes, de nouveaux arguments et de nouveaux gadgets améliorent les performances et donnent naissance à de nouveaux systèmes. Beaucoup d'entre eux sont utilisés en production, et nous repoussons sans cesse les limites. Disposerons-nous d'un système de preuve général pour toutes les applications ou de plusieurs systèmes adaptés à différents besoins ? Nous pensons qu'il est peu probable qu'un seul système de preuve les règle toutes parce que :

1. La diversité des candidatures.
2. Les types de contraintes que nous avons (concernant la mémoire, les temps de vérification, les temps de vérification).
3. Le besoin de robustesse (si un système de preuve tombe en panne, il en reste d'autres).

Même si les systèmes de preuve changent beaucoup, ils présentent tous une propriété importante : les preuves peuvent être vérifiées rapidement. Le fait de disposer d'une couche qui vérifie les preuves et qui peut être facilement adaptée aux nouveaux systèmes de preuves permet de résoudre les difficultés liées à la modification de la couche de base, comme Ethereum. Pour donner un aperçu des différentes caractéristiques des SNARKs :

• Hypothèses cryptographiques : fonctions de hachage résistantes aux collisions, problème de log discret sur des courbes elliptiques, connaissance de l'exposant.
• Configuration transparente ou fiable.
• Durée de la preuve : linéaire ou superlinéaire.
• Heure de vérification : temps constant, logarithmique, sublinéaire, linéaire.
• Taille de l'épreuve.
• Facilité de récursivité.
• Schéma d'arithmétisation.
• Polynômes univariés ou multivariés.

Ce billet abordera les origines des SNARK, certains éléments fondamentaux et l'essor (et la chute) de différents systèmes de preuve. Le billet ne prétend pas être une analyse exhaustive des systèmes de preuve. Nous nous concentrons plutôt sur ceux qui ont eu un impact sur nous. Bien entendu, ces développements n'ont été possibles que grâce à l'excellent travail et aux idées des pionniers de ce domaine.

Principes fondamentaux

Comme nous l'avons mentionné, les preuves de connaissance nulle ne sont pas nouvelles. Les définitions, les fondements, les théorèmes importants et même les protocoles importants ont été établis au milieu des années 1980. Certaines des idées et protocoles clés que nous utilisons pour créer des SNARK modernes ont été proposés dans les années 1990 (le protocole Sumcheck) ou même avant l'avènement du Bitcoin (GKR en 2007). Les principaux problèmes liés à son adoption étaient liés à l'absence d'un cas d'utilisation puissant (Internet n'était pas aussi développé dans les années 1990) et à la quantité de puissance de calcul nécessaire.

Des preuves sans connaissance : les origines (1985/1989)

Le domaine des preuves de connaissance zéro a fait son apparition dans la littérature universitaire avec l'article de Goldwasser, Micali et Rackoff. Pour une discussion sur les origines, vous pouvez regarder la vidéo suivante. L'article a introduit les notions de complétude, de solidité et de connaissance nulle, en fournissant des constructions pour la résiduité quadratique et la non-résiduité quadratique.

Protocole Sumcheck (1992)

Le protocole Sumcheck a été proposé par Lund, Fortnow, Karloff et Nissan en 1992. C'est l'un des éléments les plus importants pour des preuves interactives succinctes. Cela nous aide à réduire le montant des évaluations d'un polynôme multivarié à une évaluation unique à un moment choisi au hasard.

Goldwasser-Kalai-Rothblum (GKR) (2007)

Le protocole GKR est un protocole interactif qui possède un prouveur qui fonctionne de manière linéaire en termes de nombre de portes d'un circuit, tandis que le vérificateur fonctionne de manière sous-linéaire en termes de taille du circuit. Dans le protocole, le prouveur et le vérificateur s'accordent sur un circuit arithmétique de ventilateur en deux sur un champ fini de profondeur d, la couche d correspondant à la couche d'entrée et la couche 0 à la couche de sortie. Le protocole commence par une réclamation concernant la sortie du circuit, qui est réduite à une réclamation concernant les valeurs de la couche précédente. En utilisant la récursivité, nous pouvons en faire une réclamation sur les entrées du circuit, qui peuvent être vérifiées facilement. Ces réductions sont obtenues via le protocole Sumcheck.

Schéma d'engagement polynomial KZG (2010)

Kate, Zaverucha et Goldberg ont introduit en 2010 un système d'engagement pour les polynômes utilisant un groupe d'appariement bilinéaire. L'engagement consiste en un seul élément de groupe, et le validateur peut l'ouvrir efficacement à toute évaluation correcte du polynôme. De plus, grâce aux techniques de traitement par lots, plusieurs évaluations peuvent être ouvertes. Les engagements du KZG ont fourni l'un des éléments de base de plusieurs SNARK efficaces, tels que Pinocchio, Groth16 et Plonk. Il est également au cœur de l'EIP-4844. Pour avoir une idée des techniques de traitement par lots, vous pouvez consulter notre article sur le pont Mina-Ethereum.

Des SNARKs pratiques utilisant des courbes elliptiques

Les premières constructions pratiques pour SNArks sont apparues en 2013. Elles nécessitaient une étape de prétraitement pour générer les clés de vérification et de vérification, et elles étaient spécifiques au programme/au circuit. Ces clés pouvaient être assez volumineuses et dépendaient de paramètres secrets qui devaient rester inconnus des parties ; sinon, elles pourraient falsifier des preuves. Pour transformer le code en quelque chose qui puisse être prouvé, il fallait le compiler selon un système de contraintes polynomiales. Au début, cela devait être fait manuellement, ce qui prend du temps et est sujet à des erreurs. Les avancées dans ce domaine ont permis de résoudre certains des principaux problèmes :

1. Ayez des étalons plus efficaces.
2. Réduisez la quantité de prétraitement.
3. Avoir des configurations universelles plutôt que spécifiques à un circuit.
4. Évitez d'avoir des configurations fiables.
5. Développer des moyens de décrire les circuits en utilisant un langage de haut niveau, au lieu d'écrire les contraintes polynomiales manuellement.

Pinocchio (2013)

Pinocchio est le premier ZK-SNARK pratique et utilisable. Le SNARK est basé sur des programmes d'arithmétique quadratique (QAP). À l'origine, la taille de la preuve était de 288 octets. La chaîne d'outils de Pinocchio fournissait un compilateur allant du code C aux circuits arithmétiques, qui a ensuite été transformé en QAP. Le protocole exigeait que le vérificateur génère les clés, qui sont spécifiques au circuit. Il a utilisé des paires de courbes elliptiques pour vérifier les équations. Les asymptotiques pour la génération de preuves et la configuration des clés étaient linéaires en termes de taille de calcul, et le temps de vérification était linéaire en ce qui concerne la taille des entrées et sorties publiques.

Groth 16 (2016)

Groth a introduit un nouvel argument en termes de connaissances en améliorant les performances pour résoudre les problèmes décrits par un R1CS. Il possède la plus petite taille d'épreuve (seulement trois éléments de groupe) et une vérification rapide impliquant trois paires. Cela implique également une étape de prétraitement pour obtenir la chaîne de référence structurée. Le principal inconvénient est que cela nécessite une configuration fiable différente pour chaque programme, ce que nous voulons prouver, ce qui n'est pas pratique. Groth16 a été utilisé dans ZCash.

Bulletproofs & IPA (2016)

L'un des points faibles du KZG PCS est qu'il nécessite une configuration fiable. Bootle et coll. a introduit un système efficace d'argumentation à connaissance nulle pour les ouvertures des engagements de Pedersen qui répondent à une relation interne avec le produit. L'argument du produit interne repose sur un prouveur linéaire, avec une communication et une interaction logarithmiques, mais avec une vérification temporelle linéaire. Ils ont également développé un système d'engagement polynomial qui ne nécessite pas de configuration fiable. Les PC utilisant ces idées sont utilisés par Halo 2 et Kimchi.

Sonic, Marlin et Plonk (2019)

Sonic, Plonk et Marlin résolvent le problème de la configuration fiable par programme que nous avions dans Groth16, en introduisant des chaînes de référence structurées universelles et actualisables. Marlin fournit un système de preuve basé sur le R1CS et il est au cœur d'Aleo.

Plonk a introduit un nouveau schéma d'arithmétisation (appelé plus tard Plonkish) et l'utilisation de la vérification globale pour les contraintes de copie. Plonkish a également autorisé l'introduction de portails spécialisés pour certaines opérations, appelés portails personnalisés. Plusieurs projets proposent des versions personnalisées de Plonk, notamment Aztec, zkSync, Polygon ZKEVM, Mina's Kimchi, Plonky2, Halo 2 et Scroll, entre autres.

Recherches (2018/2020)

Gabizon et Williamson ont introduit Plookup en 2020, en utilisant le contrôle général du produit pour prouver qu'une valeur est incluse dans un tableau de valeurs précalculé. Bien que les arguments de recherche aient déjà été présentés dans Arya, la construction a nécessité de déterminer les multiplicités des recherches, ce qui la rend moins efficace. L'article de PlonkUp expliquait comment introduire l'argument de recherche dans Plonk. Le problème avec ces arguments de recherche, c'est qu'ils ont obligé le prouveur à payer le prix pour l'ensemble de la table, quel que soit le nombre de recherches qu'il a effectuées. Cela implique un coût considérable pour les grandes tables, et de nombreux efforts ont été consacrés à réduire le coût du serveur d'essai au nombre de recherches qu'il utilise.
Haböck a introduit LogUp, qui utilise la dérivée logarithmique pour transformer le résultat global en une somme de réciproques. LogUp est crucial pour les performances du Polygon ZKEVM, où l'ensemble du tableau doit être divisé en plusieurs modules STARK. Ces modules doivent être correctement liés, et les recherches croisées le font respecter. L'introduction de LogUp-GKR utilise le protocole GKR pour améliorer les performances de LogUp. Caulk a été le premier schéma à placer le temps de preuve sous linéaire dans la taille de la table en utilisant le temps de prétraitement O (NLogn) et le stockage O (N), où N est la taille de la table. Plusieurs autres programmes ont suivi, tels que Baloo, Flookup, CQ et Caulk+. Lasso propose plusieurs améliorations, en évitant de s'engager dans le tableau s'il possède 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 d'une machine virtuelle via des recherches.

Spartan (2019)

Spartan fournit une IOP pour les circuits décrits à l'aide du R1CS, en tirant parti des propriétés des polynômes multivariés et du protocole Sumcheck. En utilisant un schéma d'engagement polynomial approprié, il en résulte un SNARK transparent avec un dispositif d'essai temporel linéaire.

HyperPlonk (2022)

HyperPlonk s'inspire des idées de Plonk en utilisant des polynômes multivariés. Au lieu de quotients pour vérifier l'application des contraintes, cela s'appuie sur le protocole Sumcheck. Il prend également en charge des contraintes de haut niveau sans nuire à la durée de fonctionnement de l'appareil d'essai. Comme il repose sur des polynômes multivariés, il n'est pas nécessaire de réaliser des FFT, et le temps de fonctionnement du prouveur est linéaire en termes de taille de circuit. HyperPlonk introduit une nouvelle IOP par permutation adaptée aux petits champs et un protocole d'ouverture de lots basé sur la vérification de la somme, qui réduit le travail du prouveur, la taille de l'épreuve et le temps du vérificateur.

Schémas de pliage (2008/2021)

Nova introduit l'idée d'un schéma de pliage, une nouvelle approche permettant de réaliser des calculs vérifiables de manière incrémentielle (IVC). Le concept d'IVC remonte à Valiant qui a montré comment fusionner deux preuves de longueur k en une seule preuve de longueur k. L'idée est que nous pouvons prouver n'importe quel calcul de longue durée en prouvant de manière récursive que l'exécution de l'étape i à l'étape I+1+1 est correcte et en vérifiant une preuve démontrant que la transition entre l'étape i

−1−1 à l'étape I était correcte. Nova gère bien les calculs uniformes ; elle a ensuite été étendue pour gérer différents types de circuits avec l'introduction de Supernova. Nova utilise une version décontractée du R1CS et utilise des courbes elliptiques amicales. Utiliser des cycles de courbes amicaux (par exemple, les courbes des pâtes) pour obtenir une IVC est également utilisé dans Pickles, la principale pierre angulaire de Mina pour obtenir un état succinct. Cependant, l'idée du pliage diffère de celle de la vérification récursive SNARK. L'idée de l'accumulateur est plus étroitement liée au concept des preuves par lots. Halo a introduit la notion d'accumulation comme alternative à la composition de preuves récursive. Protostar propose un schéma IVC non uniforme pour Plonk qui prend en charge les portes à haut degré et les recherches vectorielles.

Utilisation de fonctions de hachage résistantes aux collisions

À peu près à la même époque que Pinocchio a été développé, des idées ont été proposées pour générer des circuits/des schémas d'arithmétisation susceptibles de prouver l'exactitude de l'exécution d'une machine virtuelle. Même s'il peut être plus complexe ou moins efficace de développer l'arithmétisation d'une machine virtuelle que d'écrire des circuits dédiés pour certains programmes, cela présentait l'avantage de pouvoir prouver n'importe quel programme, aussi complexe soit-il, en démontrant qu'il était correctement exécuté sur la machine virtuelle. Les idées de TinyRam ont ensuite été améliorées avec la conception de la machine virtuelle Cairo et des machines virtuelles suivantes (telles que zk-evms ou zkvms à usage général). L'utilisation de fonctions de hachage résistantes aux collisions a supprimé le besoin de configurations fiables ou d'opérations sur les courbes elliptiques, au détriment de preuves plus longues.

TinyRam (2013)

Dans SNARKs pour C, ils ont développé un SNARK basé sur un PCP pour prouver l'exactitude de l'exécution d'un programme en C, qui est compilé sur TinyRAM, un ordinateur à jeu d'instructions réduit. L'ordinateur utilisait une architecture Harvard avec une mémoire à accès aléatoire adressable au niveau des octets. En tirant parti du non-déterminisme, la taille du circuit est quasi linéaire par rapport à celle du calcul, ce qui permet de gérer efficacement les boucles arbitraires et dépendantes des données, le flux de contrôle et les accès à la mémoire.

StarKs (2018)

Les STARK ont été introduites par Ben Sasson et al. en 2018. Ils obtiennent O (log2n) (log2)

les tailles d'épreuve, avec un prouveur et un vérificateur rapides, ne nécessitent pas de configuration fiable et sont supposées être sécurisées après le quantum. Ils ont d'abord été utilisés par Starkware/Starknet, en même temps que la machine virtuelle Cairo. Parmi ses principales introductions figurent la représentation algébrique intermédiaire (AIR) et le protocole FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity). Il est également utilisé par d'autres projets (Polygon Miden, Risc0, Winterfell, Neptune) ou certains composants ont été adaptés (Boojum de zkSync, Plonky2, Starky).

Léger (2017)

Ligero introduit un système de preuves qui permet d'obtenir des preuves dont la taille est

O (√ n), où n est la taille du circuit. Il organise les coefficients polynomiaux sous forme de matrice 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 terrain.

Quelques nouveautés

L'utilisation de différents systèmes de preuve en production a démontré les mérites de chacune des approches et a donné lieu à de nouveaux développements. Par exemple, l'arithmétisation plonkish permet d'inclure des portes personnalisées et des arguments de recherche en toute simplicité. Le FRI s'est révélé très performant en tant que PCS, d'où Plonky. De même, l'utilisation de l'enregistrement général du produit dans AIR (qui a conduit à un AIR aléatoire avec prétraitement) a amélioré ses performances et simplifié les arguments d'accès à la mémoire. Les engagements basés sur des fonctions de hachage gagnent en popularité, en raison de la rapidité des fonctions de hachage sur le matériel ou de l'introduction de nouvelles fonctions de hachage compatibles avec Snark.

Nouveaux schémas d'engagement polynomial (2023)

Avec l'avènement de SNARK efficaces basés sur des polynômes multivariés, tels que Spartan ou HyperPlonk, les nouveaux schémas d'engagement adaptés à ce type de polynômes suscitent un intérêt croissant. Binius, Zeromorph et Basefold proposent tous de nouvelles formes pour s'engager dans des polynômes multilinéaires. Binius a l'avantage de n'avoir aucune surcharge 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 des bits individuels) et fonctionne sur des champs binaires. L'engagement adapte la répartition, qui a été conçue pour être indépendante du terrain. Basefold généralise le FRI à des codes autres que Reed-Solomon, ce qui permet d'obtenir un PCS indépendant du terrain.

Systèmes de contraintes personnalisables (2023)

Le CCS généralise le R1CS tout en capturant les arithmétisations R1CS, Plonkish et AIR sans frais généraux. L'utilisation du CCS avec Spartan IOP permet d'obtenir SuperSpartan, qui prend en charge des contraintes de haut niveau sans avoir à utiliser le prouveur pour des coûts cryptographiques qui varient en fonction du degré de la contrainte. SuperSpartan produit notamment un SNARK pour AIR avec un chronométreur linéaire.

Conclusion

Ce billet décrit les avancées des SNARK depuis leur introduction au milieu des années 1980. Les progrès de l'informatique, des mathématiques et du matériel informatique, associés à l'introduction de la blockchain, ont permis de créer de nouveaux SNARK plus efficaces, ouvrant la voie à de nombreuses applications susceptibles de transformer notre société. Des chercheurs et des ingénieurs ont proposé des améliorations et des adaptations aux SNARK en fonction de leurs besoins, en mettant l'accent sur la taille de la preuve, l'utilisation de la mémoire, la configuration transparente, la sécurité post-quantique, le temps de démonstration et le temps de vérification. Alors qu'il y avait deux lignes principales à l'origine (SNarkS contre StarkS), la frontière entre les deux a commencé à s'estomper, en essayant de combiner les avantages des différents systèmes de preuve. Par exemple, combiner différents schémas d'arithmétisation avec de nouveaux schémas d'engagement polynomial. Nous pouvons nous attendre à ce que les nouveaux systèmes de preuve continuent de se développer, avec des performances accrues, et il sera difficile pour certains systèmes qui ont besoin d'un certain temps pour s'adapter à ces évolutions, à moins de pouvoir utiliser facilement ces outils sans avoir à modifier certaines infrastructures de base.

Avertissement：

1. Cet article est reproduit depuis [lambdaclass]. Tous les droits d'auteur appartiennent à l'auteur original [LambdaClass]. En cas d'objection à cette réimpression, contactez l'équipe de Gate Learn, elle s'en occupera rapidement.
2. Avertissement en matière de responsabilité : Les points de vue et opinions exprimés dans cet article sont uniquement ceux de l'auteur et ne constituent en aucun cas un conseil d'investissement.
3. Les traductions de l'article dans d'autres langues sont effectuées par l'équipe de Gate Learn. Sauf mention contraire, il est interdit de copier, de distribuer ou de plagier les articles traduits.