Historique du développement des technologies ZK
TechFlow SélectionTechFlow Sélection
Historique du développement des technologies ZK
Une chronologie linéaire de l'histoire du développement de la technologie ZK.
Dédié à des analyses Web3 approfondiesRédaction : Lambda Class
Traduction : Baiding, Faust, Nickqiao
Version originale en anglais publiée le 17 février 2024
Les preuves à connaissance nulle (ZK Proofs) sont des primitives cryptographiques puissantes permettant à une partie (le prouveur) de convaincre une autre partie (le vérificateur) qu'une affirmation donnée est vraie, sans divulguer aucune information privée. Ces dernières années, les ZK ont suscité un grand intérêt dans les domaines du calcul privé vérifiable, de la génération de preuves d'efficacité pour des programmes informatiques et des blockchains, apportant des contributions significatives au développement mondial.
Bien que les ZK soient une technologie émergente, leurs idées fondamentales remontent aux années 1980. Leur développement s'est considérablement accéléré avec l'avènement des blockchains comme Bitcoin et Ethereum, car celles-ci peuvent utiliser des SNARK et des STARK pour produire des preuves d'efficacité, améliorant ainsi fortement leur extensibilité, ce qui a rendu les ZK particulièrement populaires dans ce domaine.
Comme l’a souligné Eli Ben-Sasson, fondateur de Starkware, nous avons assisté ces dernières années à une « explosion cambrienne » des systèmes de preuve cryptographiques. Chaque système de preuve présente des avantages et inconvénients spécifiques, résultant de compromis effectués lors de sa conception. Les progrès matériels, les meilleurs algorithmes, les nouveaux protocoles et outils associés stimulent continuellement l'amélioration des performances des systèmes ZK et la naissance de nouveaux systèmes. De nombreux systèmes sont déjà utilisés concrètement, tandis que les frontières des ZK continuent d'être repoussées.
Cela pousse à se poser une question essentielle : existe-t-il un système de preuve ZK universel adapté à toutes les applications ? Nous pensons que cela est peu probable, pour trois raisons principales :
-
La diversité des applications ;
-
Les différents types de contraintes (mémoire, temps de vérification, temps de preuve) ;
-
Le besoin de robustesse (si un système de preuve est compromis, il faut pouvoir basculer vers un autre comme solution de secours).
Pour ces raisons, les systèmes de preuve ZK devraient naturellement être diversifiés. Mais même si les types de preuves sont nombreux, ils partagent tous une caractéristique marquante : les preuves ZK peuvent être vérifiées rapidement, et disposent d'une couche de vérification facilement adaptable aux nouveaux systèmes, afin de résoudre efficacement les difficultés liées à leur couche sous-jacente (comme Ethereum).
Dans le domaine ZK, zk-SNARK est fréquemment mentionné. Il s’agit d’une forme de mise en œuvre de la preuve à connaissance nulle, utilisant des outils mathématiques complexes tels que les appariements bilinéaires et les circuits arithmétiques pour produire des preuves efficaces. Les zk-SNARK se caractérisent par un processus de preuve simplifié et non interactif, nécessitant une seule communication entre le prouveur et le vérificateur. En outre, la taille des preuves zk-SNARK est très réduite et leur vérification extrêmement rapide, ce qui les rend adaptés aux environnements aux ressources limitées.
zk-STARK est une autre forme courante, conçue pour surmonter certaines limitations des zk-SNARK. zk-STARK ne dépend pas d’un paramètre de configuration confidentiel, utilise des constructions mathématiques plus transparentes — comme les engagements polynomiaux, les opérations sur corps finis ou les collisions de hachage — pour générer et vérifier les preuves. zk-STARK est plus évolutif que zk-SNARK, adapté à des calculs à grande échelle, avec une génération de preuve plus rapide, mais la taille de la preuve elle-même est généralement plus importante.
On peut dire que zk-SNARK et zk-STARK sont deux formes courantes de preuve à connaissance nulle, mais qu’elles diffèrent sur des aspects tels que la transparence, l’évolutivité et la taille des preuves.
Globalement, un système de preuve ZK comprend généralement deux composants principaux : PIOP (Preuve Interactive Oracle Polynomiale) et PCS (Schéma d'Engagement Polynomial). Parmi les schémas PIOP courants figurent PLONKish, GKR, etc., tandis que les schémas PCS incluent FRI, KZG, IPA, etc. Par exemple, la version Halo2 utilisée par Zcash repose sur Plonkish + IPA. Quant à zk-STARK, il peut être vu comme une variante particulière de zk-SNARK reposant sur FRI.
Plus précisément, différents types de systèmes de preuve utilisent différents schémas d'engagements polynomiaux (PCS), différentes méthodes d'arithmétisation, des Preuves Interactives Oracle (IOP) ou des Preuves Vérifiables Probabilistes (PCP).
En outre, les différents systèmes de preuve ZK varient selon plusieurs critères clés :
-
Hypothèses cryptographiques : fonctions de hachage résistantes aux collisions, problème du logarithme discret sur courbes elliptiques, connaissance de l'exposant
-
Configuration transparente vs configuration confidentielle
-
Temps de génération de la preuve : linéaire vs super-linéaire
-
Temps de vérification de la preuve : constant, logarithmique, sous-linéaire, linéaire
-
Taille de la preuve
-
Facilité de la récursion
-
Méthode d’arithmétisation
-
Polynômes univariés vs multivariés
Dans ce qui suit, nous aborderons brièvement les origines de la technologie ZK, explorerons ses blocs constitutifs fondamentaux et retracerons l'émergence et le déclin de divers systèmes de preuve. Cet article ne cherche pas à analyser en détail les systèmes eux-mêmes, mais met plutôt en lumière les personnes ayant eu un impact profond sur le domaine, car aucun secteur ne progresse sans les grandes idées des pionniers mises en pratique.
Évolution historique des zk-SNARK
Origines : années 1980-1990
Comme mentionné, les preuves à connaissance nulle ne sont pas un concept nouveau. Leurs définitions, bases fondamentales, théorèmes clés et protocoles importants sont apparus dès le milieu des années 1980, dans l'article fondateur de Goldwasser, Micali (fondateur d'Algorand) et Rackoff intitulé « The Knowledge Complexity of Interactive Proof Systems ».
Aujourd'hui, les idées et protocoles clés utilisés pour construire les zk-SNARK ont été développés dans les années 1990, comme le protocole Sumcheck, qui transforme l'affirmation sur la somme des évaluations d'un polynôme multivarié en une simple évaluation en un point choisi aléatoirement sur une courbe elliptique. Ce protocole a jeté les bases importantes de la technologie ZK.
Ainsi, les germes de la pensée ZK préexistent largement à l'apparition du Bitcoin, mais à l'époque, on manquait à la fois d'applications concrètes et de la puissance de calcul nécessaire, car Internet et le matériel informatique étaient encore peu développés dans les années 1990.
Protocole GKR (2007)
GKR (Goldwasser-Kalai-Rothblum) est un protocole interactif où le temps d'exécution du prouveur est linéaire par rapport au nombre de portes logiques dans le circuit, tandis que celui du vérificateur est sous-linéaire par rapport à la taille du circuit. Dans GKR, le prouveur et le vérificateur doivent s'accorder sur le résultat d'un circuit arithmétique à deux entrées sur un corps fini, de profondeur d, la couche d étant celle des entrées et la couche 0 celle de la sortie. Le protocole commence par une affirmation sur la sortie du circuit, puis la ramène récursivement à une affirmation sur la couche supérieure, jusqu'à ce que l'on aboutisse à une assertion sur les entrées du circuit, facile à vérifier. On peut dire que le protocole GKR est une version fortement simplifiée du protocole Sumcheck mentionné précédemment.
Schéma d'engagement polynomial KZG (2010)
En 2010, trois experts du domaine ZK — Kate du centre de recherche allemand MPI-SWS, Zaverucha de l'entreprise canadienne Certicom Research, et Goldberg de l'Université de Waterloo — ont publié conjointement un article intitulé « Constant-Size Commitments to Polynomials and Their Applications », présentant un schéma d'engagement polynomial utilisant des groupes à appariements bilinéaires, nommé KZG.
Cet engagement consiste en un seul élément de groupe, permettant au soumissionnaire de révéler efficacement toute bonne évaluation du polynôme. Grâce aux techniques de traitement par lots, plusieurs évaluations de polynômes peuvent être révélées simultanément. L'engagement KZG est devenu un composant fondamental de plusieurs systèmes de preuve ZK célèbres (comme Halo2 utilisé par l'équipe PSE d'Ethereum), jouant même un rôle central dans la proposition EIP-4844 d'Ethereum. Pour mieux comprendre la notion de traitement par lots, voir l'article sur le pont Mina-Ethereum.
Ressource : https://blog.lambdaclass.com/mina-to-ethereum-bridge/
Premiers systèmes zk-SNARK pratiques basés sur des courbes elliptiques (2013)
La première construction zk-SNARK pratique date de 2013. Elle nécessite une étape de prétraitement pour générer des clés de preuve et de vérification, spécifiques à chaque programme ou circuit, donc non généralistes. La taille de ces clés peut être très importante et dépend des paramètres secrets ; si ces derniers sont compromis, un attaquant peut fabriquer de fausses preuves. Dans ces systèmes zk-SNARK pratiques, convertir du code en une forme prouvable implique de compiler le code en un ensemble de contraintes polynomiales sous forme mathématique.
Initialement, ce processus devait être fait manuellement, ce qui était long et sujet aux erreurs. Les progrès techniques ultérieurs ont visé à résoudre les problèmes suivants :
- Produire des preuves plus efficaces
- Réduire le nombre d'étapes de prétraitement
- Obtenir une configuration universelle, non spécifique au circuit
- Éviter la configuration confidentielle
- Développer des méthodes permettant de décrire les circuits avec des langages de haut niveau, plutôt que d’écrire manuellement des contraintes polynomiales
Protocole Pinocchio (2013)
Pinocchio est le premier système zk-SNARK véritablement utilisable. Basé sur les Programmes Arithmétiques Quadratiques (QAP), il produit initialement des preuves de 288 octets. Sa chaîne d'outils inclut un compilateur capable de transformer du code C en circuits arithmétiques, puis en QAP. Pinocchio exige que le vérificateur génère des clés spécifiques au circuit, non universelles. La complexité temporelle asymptotique de la génération de preuve et de la configuration des clés est linéaire par rapport à l'échelle du calcul, tandis que le temps de vérification est linéaire par rapport à la taille des entrées et sorties publiques.
Groth16 (2016)
Groth a introduit un nouvel algorithme de preuve ZK offrant de meilleures performances sur les R1CS (Rank-1 Constraint System, ou système de contraintes de rang 1), une forme de contrainte polynomiale utilisée dans les zk-SNARK. Les preuves de Groth sont parmi les plus compactes (trois éléments de groupe seulement) et très rapides à vérifier, nécessitant seulement trois opérations d’appariement et une étape de prétraitement structurant la chaîne de référence. Toutefois, son principal inconvénient est que chaque programme à prouver requiert une configuration confidentielle distincte, ce qui est peu pratique en usage réel.
Par la suite, Groth16 a été adopté par ZCash, un projet blockchain axé sur la confidentialité (auquel Eli Ben-Sasson, fondateur de Starkware, a participé).
Bulletproofs et IPA (2016)
L’un des principaux inconvénients du schéma d’engagement polynomial KZG est son besoin d’une configuration confidentielle. Bootle et al. ont proposé un système de preuve à zéro connaissance efficace analysant l’ouverture d’engagements Pedersen satisfaisant une relation de produit interne. La preuve d’engagement interne a une complexité linéaire, le nombre d’interactions entre prouveur et vérificateur est logarithmique, bien que le temps de vérification reste linéaire. De plus, Bootle et al. ont développé un schéma d’engagement polynomial ne nécessitant pas de configuration confidentielle. Ces idées ont ensuite été adoptées par Halo2, Kimchi, etc.
Sonic, Marlin et Plonk (2019)
Sonic, Plonk et Marlin ont résolu le problème de Groth16, où chaque programme nécessite une configuration confidentielle, en introduisant une chaîne de référence structurée, universelle et mise à jour. Parmi eux, Marlin fournit un système de preuve basé sur R1CS, devenu la technologie centrale d'Aleo.
Plonk, quant à lui, introduit un nouveau schéma d’arithmétisation (plus tard appelé Plonkish) et utilise un « grand produit » pour vérifier les contraintes de copie. Plonkish permet aussi d’introduire des portes logiques spécialisées pour des opérations spécifiques, appelées « portes personnalisées ». De nombreux projets blockchain célèbres utilisent des versions personnalisées de Plonk, notamment Aztec, zkSync, Polygon zkEVM, Mina, l’équipe PSE d’Ethereum et Scroll.
Spartan (2019)
Spartan propose un IOP pour les circuits décrits via R1CS, exploitant les propriétés des polynômes multivariés et du protocole de vérification de somme. En combinant un schéma d’engagement polynomial approprié, il réalise un système zk-SNARK transparent dont le temps de génération de preuve est linéaire.
Lookups (2020)
Gabizon et Williamson ont proposé en 2020 dans un article plookup, utilisant un « grand produit » pour prouver qu’une valeur appartient à une table de vérité précalculée, montrant comment intégrer les paramètres plookup dans l’algorithme Plonk.
Cependant, ces arguments de recherche partagent un problème commun : le coût élevé pour le prouveur de construire la table complète. Ainsi, les travaux antérieurs autour des Lookups visaient surtout à réduire ce coût.
Plus tard, Haböck a introduit LogUp dans un article, utilisant la dérivée logarithmique pour transformer la vérification du « grand produit » en une somme d'inverses. LogUp a été crucial pour améliorer les performances de Polygon zkEVM, car il fallait diviser la table complète en plusieurs modules STARK, qui devaient être correctement liés. Les recherches croisées garantissent ce lien. L’introduction subséquente de LogUp-GKR a ensuite amélioré les performances de LogUp via le protocole GKR.
Caulk est la première méthode à rendre le temps de preuve sous-linéaire par rapport à la taille de la table, avec une complexité de prétraitement en O(NlogN) et une occupation mémoire en O(N), N étant la taille de la table. D'autres propositions sont ensuite apparues, telles que Baloo, flookup, cq et caulk+. De plus, Lasso a proposé plusieurs améliorations permettant d’éviter l’engagement sur la table quand celle-ci possède une structure particulière.
HyperPlonk (2022)
HyperPlonk a été présenté dans l'article « HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates ». S'inspirant de Plonk, il utilise des polynômes multivariés, remplaçant la division pour vérifier les contraintes par le protocole de vérification de somme. Il supporte également des contraintes de haut degré sans augmenter le temps de génération de la preuve.
Grâce aux polynômes multivariés, il n’est plus nécessaire d’utiliser la Transformée de Fourier Rapide (FFT), et le temps de génération de preuve devient linéaire par rapport à la taille du circuit. HyperPlonk introduit aussi un nouvel IOP de permutation adapté aux petits champs, et adopte un protocole basé sur la vérification de somme, réduisant ainsi le travail du prouveur, la taille de la preuve et le temps de vérification.
Systèmes de preuve ZK utilisant des fonctions de hachage résistantes aux collisions
En parallèle de Pinocchio en 2013, des approches alternatives ont été proposées pour générer des circuits / schémas d’arithmétisation capables de prouver l’exécution correcte d’une machine virtuelle sur des instructions. Bien que développer un schéma d’arithmétisation pour une VM soit plus complexe ou moins efficace que d’écrire un circuit dédié pour un programme, il offre un avantage majeur : quel que soit la complexité du programme, il suffit de prouver son exécution correcte dans la VM.
Certaines idées de TinyRAM ont été améliorées dans la conception de la machine virtuelle Cairo, puis étendues à zk-EVM et d’autres VMs génériques. L’utilisation de fonctions de hachage résistantes aux collisions dans les systèmes de preuve élimine le besoin de configuration confidentielle ou d’opérations sur courbes elliptiques, au prix d’un temps de preuve plus long.
TinyRAM (2013)
Dans « SNARKs for C », les auteurs ont développé un système de preuve basé sur les PCP (Preuves Vérifiables Probabilistes) pour prouver l’exécution correcte de programmes écrits en C. Le programme est compilé en TinyRAM, une VM simplifiée. Cette VM dispose d’une mémoire aléatoire adressable au niveau du byte, et sa taille de circuit croît quasi-linéairement avec l’échelle du calcul, permettant de gérer efficacement boucles, flux de contrôle et accès mémoire.
Ici, PCP signifie Preuve Vérifiable Probabiliste : le vérificateur peut lire aléatoirement une petite partie de la preuve et, avec une forte confiance, en valider la validité. Contrairement aux systèmes traditionnels où le vérificateur doit examiner toute la preuve, les PCP permettent une vérification efficace avec une quantité limitée de hasard.
Ligero (2017)
Ligero introduit un système de preuve produisant des preuves de taille O(√n), où n est la taille du circuit. Il organise les coefficients polynomiaux sous forme matricielle. Brakedown s’appuie sur Ligero et introduit la notion de schéma d’engagement polynomial indépendant du domaine.
STARKs (2018)
Les STARKs (Arguments Scalables et Transparents de Connaissance) ont été proposés en 2018 par Eli Ben-Sasson et al. Ils atteignent une complexité de preuve en O(log²n), offrent une vérification rapide, n’exigent aucune configuration confidentielle et sont supposés sûrs contre les ordinateurs quantiques. Ils sont adoptés par Starkware/Starknet avec la machine virtuelle Cairo. Leurs innovations clés incluent la Représentation Algébrique Intermédiaire (AIR) et le protocole FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity). De nombreux projets blockchain célèbres utilisent aussi les STARKs (comme Polygon Miden, RiscZero, Winterfell, Neptune, ZeroSync, zkSync, etc.).
Nouvelles directions
L'utilisation pratique de divers systèmes de preuve met en lumière les forces de chaque approche et pousse l'évolution des ZK. Par exemple, le schéma d’arithmétisation Plonkish offre une méthode simple pour intégrer des portes logiques personnalisées et des arguments de recherche ; FRI s’est imposé comme un excellent PCS, menant à la création de Plonky. De plus, l’utilisation de « grands produits » dans AIR (donnant lieu à l’AIR randomisé prétraité) améliore les performances et simplifie les paramètres d’accès mémoire. Les zk-STARK gagnent en popularité grâce à leur meilleure efficacité de génération et à l’introduction croissante de fonctions de hachage compatibles ZK.
Nouveaux schémas d’engagement polynomial (2023)
Avec l’émergence de SNARK efficaces basés sur des polynômes multivariés (comme Spartan ou HyperPlonk), l’intérêt pour de nouveaux schémas d’engagement adaptés croît. Binius, Zeromorph et Basefold proposent de nouvelles façons d’engager des polynômes multilinéaires. L’avantage de Binius est son absence de surcoût pour représenter certains types de données (contrairement à d’autres systèmes qui utilisent souvent des éléments de champ de 32 bits pour un seul bit), et son fonctionnement sur un corps binaire. Ce schéma d’engagement utilise brakedown, conçu pour être indépendant du domaine. Basefold généralise FRI au-delà des codes de Reed-Solomon, réalisant ainsi un schéma d’engagement polynomial indépendant du domaine (PCS).
L’indépendance du domaine est une propriété d’un schéma d’engagement polynomial, signifiant que le processus d’engagement ne dépend d’aucune caractéristique spécifique à un domaine particulier. Cela permet d’engager des polynômes sur n’importe quelle structure algébrique : corps finis, courbes elliptiques, voire anneaux d’entiers.
Systèmes de contraintes personnalisables (2023)
CCS généralise R1CS tout en englobant les arithmétisations R1CS, Plonkish et AIR sans surcoût. Combiné à l’IOP Spartan, CCS donne SuperSpartan, qui supporte des contraintes multidimensionnelles sans que le prouveur subisse un coût cryptographique proportionnel à l’ordre des contraintes. En particulier, SuperSpartan fournit un SNARK pour AIR avec un temps de preuve linéaire.
Conclusion
Cet article retrace les progrès de la technologie ZK depuis le milieu des années 1980. Les avancées en informatique, mathématiques et matériel, combinées à l’émergence des blockchains, ont conduit à de nouveaux systèmes de preuve ZK plus efficaces, ouvrant la voie à de nombreuses applications susceptibles de transformer la société.
Les chercheurs et ingénieurs améliorent continuellement les systèmes ZK selon divers critères : taille des preuves, utilisation mémoire, transparence, sécurité post-quantique, temps de preuve et de vérification. Bien que les deux grandes familles dominantes restent SNARK et STARK, la frontière entre elles s’estompe progressivement, et les avantages respectifs sont de plus en plus combinés, par exemple via des schémas d’arithmétisation variés et de nouveaux schémas d’engagement polynomial.
Nous pouvons anticiper l’émergence continue de nouveaux systèmes de preuve ZK, toujours plus performants. Pour les applications qui les utilisent, ignorer l’évolution technologique et ne pas constamment reconstruire avec les derniers algorithmes signifie que toute position de leadership actuelle ne sera que temporaire.
Bienvenue dans la communauté officielle TechFlow
Groupe Telegram :https://t.me/TechFlowDaily
Compte Twitter officiel :https://x.com/TechFlowPost
Compte Twitter anglais :https://x.com/BlockFlow_News
@class_lambda
