Quelles en sont les raisons pour lesquelles les preuves à divulgation nulle (zero-knowledge proofs) connaissent une innovation continue et durable ?

Rédaction : LambdaClass

Traduction : mutourend ; Yiping, IOSG Ventures

1. Introduction

Les preuves succinctes et non interactives à connaissance nulle (zk-SNARKs) sont une primitive cryptographique puissante permettant à un prouveur de convaincre un vérificateur de la validité d'une assertion sans révéler aucune information supplémentaire. Grâce à leurs applications dans le calcul privé vérifiable, la preuve de l'exécution correcte de programmes informatiques et l'extension des blockchains, les zk-SNARKs ont suscité un vif intérêt. Nous pensons, comme décrit dans cet article, qu'ils auront un impact majeur sur le façonnement du monde. Les zk-SNARKs englobent divers types de systèmes de preuve utilisant différents schémas d'engagements polynomiaux, différentes arithmétisations, ou encore des preuves interactives avec oracle ou des preuves probabilistement vérifiables. Toutefois, ces idées fondamentales remontent au milieu des années 1980.

Depuis le lancement du Bitcoin et d'Ethereum, le développement des zk-SNARKs s'est considérablement accéléré grâce à leur capacité à étendre les blockchains via des preuves à connaissance nulle (souvent appelées preuves d'efficacité pour ce cas particulier). Ils jouent un rôle crucial dans l'évolutivité des blockchains. Comme l'a souligné 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 inconvénients, conçu selon des compromis spécifiques. Les progrès matériels, algorithmiques, ainsi que de nouveaux outils et protocoles améliorent continuellement les performances et donnent naissance à de nouveaux systèmes. De nombreux systèmes sont déjà déployés, repoussant toujours plus loin les limites. Aura-t-on un jour un système universel valable pour toutes les applications, ou plusieurs adaptés à des besoins distincts ? Nous pensons peu probable qu'un seul système domine tous les autres, notamment pour trois raisons :

1) La diversité des applications.

2) Les contraintes variées (mémoire, temps de vérification, temps de génération).

3) Le besoin de robustesse (si un système est compromis, d'autres subsistent).

Même si les systèmes de preuve évoluent fortement, ils offrent tous une propriété clé : une vérification rapide. Avoir une couche capable de vérifier les preuves et facilement adaptable aux nouveaux systèmes résout les difficultés liées à la modification de la couche de base (comme Ethereum). Cet article décrit les caractéristiques principales des SNARKs :

1) Hypothèses cryptographiques : fonctions de hachage résistantes aux collisions, problème du logarithme discret sur courbes elliptiques, knowledge of exponent.

2) Transparence vs configuration fiable.

3) Temps de génération de la preuve : linéaire vs superlinéaire.

4) Temps de vérification : constant, logarithmique, sous-linéaire, linéaire.

5) Taille de la preuve.

6) Facilité de récursion.

7) Schéma d'arithmétisation.

8) Polynômes univariés vs multivariés.

Cet article explore les origines des SNARKs, quelques briques fondamentales, ainsi que l’émergence (et disparition) de différents systèmes de preuve. Il ne s'agit pas d'une analyse exhaustive, mais d’un focus sur ceux ayant eu un impact significatif. Bien entendu, ces avancées reposent sur le travail pionnier des chercheurs du domaine.

2. Fondements

Les preuves à connaissance nulle ne sont pas nouvelles. Définitions, bases, théorèmes importants et protocoles clés datent des années 1980. Certaines idées fondamentales utilisées aujourd'hui dans les SNARKs modernes ont été proposées dans les années 1990 (protocole sumcheck), voire avant Bitcoin (GKR en 2007). Leur utilisation était alors freinée par le manque d'applications puissantes (l'internet n'était pas mature) et par les capacités de calcul insuffisantes.

1) Preuves à connaissance nulle : origines (1985/1989).

Le domaine des preuves à connaissance nulle a émergé avec l'article de Goldwasser, Micali et Rackoff, « The knowledge complexity of interactive proof systems », introduisant les notions de complétude, de solidité et de zéro-connaissance, avec des constructions autour des résidus quadratiques. Pour plus de détails historiques, voir la vidéo ZKP MOOC Lecture 1 : Introduction and History of ZKP (janvier 2023).

2) Protocole Sumcheck (1992).

Proposé par Lund, Fortnow, Karloff et Nisan dans « Algebraic Methods for Interactive Proof Systems », le protocole sumcheck est l'une des briques essentielles des preuves interactives succinctes. Il permet de réduire la somme des évaluations d'un polynôme multivarié à l'évaluation ponctuelle en un point aléatoire.

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

Le protocole GKR (« Delegating Computation: Interactive Proofs for Muggles ») est un protocole interactif où le prouveur opère en temps linéaire selon le nombre de portes du circuit, tandis que le vérificateur agit en temps sous-linéaire. Le prouveur et le vérificateur conviennent d'un circuit arithmétique sur un corps fini, à deux entrées par porte, de profondeur d, la couche d correspondant aux entrées, la couche 0 à la sortie. Le protocole commence par une affirmation sur la sortie, ramenée progressivement à une affirmation sur les valeurs intermédiaires, puis aux entrées, vérifiables directement. Ces réductions s'appuient sur le protocole sumcheck.

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

Kate, Zaverucha et Goldberg ont introduit en 2010, dans « Constant-Size Commitments to Polynomials and Their Applications », un schéma d'engagement polynomial utilisant des groupes à couplage bilinéaire. L'engagement tient en un seul élément de groupe, et l'ouverture peut être effectuée efficacement pour toute évaluation correcte. Grâce à des techniques de regroupement (batching), plusieurs évaluations peuvent être vérifiées ensemble. KZG est une brique clé de nombreux SNARKs efficaces (Pinocchio, Groth16, Plonk) et au cœur de l'EIP-4844. Voir par exemple le pont ZK entre Mina et Ethereum pour une illustration du batching.

3. SNARKs pratiques utilisant les courbes elliptiques

La première construction pratique de SNARK 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 à un programme ou circuit donné. Ces clés peuvent être volumineuses et dépendent de paramètres secrets connus de personne ; sinon, des preuves frauduleuses seraient possibles. Transformer du code en format prouvable exigeait initialement une compilation manuelle en contraintes polynomiales, longue et sujette aux erreurs. Les progrès visent à résoudre ces problèmes :

1) Prouveurs plus efficaces.

2) Réduction du prétraitement.

3) Configurations universelles plutôt que spécifiques à un circuit.

4) Éviter les configurations fiables.

5) Permettre la description des circuits via des langages de haut niveau.

Actuellement, les principaux SNARKs utilisant les courbes elliptiques sont :

1) Pinocchio (2013)

2) Groth16 (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 (Folding schemes) (2008/2021)

3.1 Pinocchio (2013)

Pinocchio (« Nearly Practical Verifiable Computation ») est le premier zk-SNARK pratique et 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 du code C vers des circuits arithmétiques, puis vers QAP. Le protocole exige que le vérificateur génère des clés spécifiques au circuit. Il utilise des couplages sur courbes elliptiques pour vérifier les équations. Le coût asymptotique du prouveur et de la configuration est linéaire en taille du calcul, celui du vérificateur linéaire en taille des entrées/sorties publiques.

3.2 Groth16 (2016)

L'article de Groth (2016) « On the Size of Pairing-based Non-interactive Arguments » introduit un nouveau système de preuve améliorant les performances pour les problèmes exprimés via R1CS. Il offre la plus petite taille de preuve (trois éléments de groupe) et une vérification rapide (trois couplages). Une étape de prétraitement produit une chaîne de référence structurée. Son principal défaut : chaque programme requiert une configuration fiable différente, peu pratique. Groth16 a été utilisé par ZCash. Voir aussi le blog « An overview of the Groth 16 proof system ».

3.3 Bulletproofs & IPA (2016)

Un point faible de KZG est son besoin de configuration fiable. Bootle et al. (2016) ont introduit dans « Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting » un système efficace de preuve à connaissance nulle pour des ouvertures d'engagements Pedersen respectant une relation de produit scalaire. Ce système a un prouveur linéaire, communication et interaction logarithmiques, mais vérification linéaire. Il permet aussi un schéma d'engagement polynomial sans configuration fiable. IPA inspire Halo2 et Kimchi.

3.4 Sonic, Marlin et Plonk (2019)

Sonic, Plonk et Marlin résolvent le problème de configuration spécifique par programme en introduisant une chaîne de référence structurée, universelle et actualisable. Marlin fournit un système basé sur R1CS, cœur d'Aleo.

Plonk introduit un nouveau schéma d'arithmétisation (plus tard appelé Plonkish) et un contrôle de produits globaux (grand-product check) pour les contraintes de copie. Plonkish autorise des portes spécialisées (custom gates). De nombreux projets utilisent des variantes de Plonk : Aztec, ZK-Sync, Polygon ZKEVM, Kimchi de Mina, Plonky2, Halo2, Scroll... Voir le blog « All you wanted to know about Plonk ».

3.5 Lookups (2018/2020)

Gabizon et Williamson ont introduit en 2020 plookup, utilisant un grand-product check pour prouver qu'une valeur appartient à une table précalculée. Bien que des arguments de lookup existaient auparavant (Arya), ils exigeaient de connaître les multiplicités, ce qui était inefficace. L'article PlonkUp montre comment intégrer plookup à Plonk. Un problème majeur : le prouveur paie le coût de toute la table, indépendamment du nombre de recherches. Des tables grandes deviennent coûteuses, motivant de nombreuses recherches pour réduire ce coût au nombre d'accès réels.

Haböck a introduit LogUp, utilisant la dérivée logarithmique pour transformer un contrôle de produit en somme d'inverses. LogUp est crucial pour les performances du ZKEVM Polygon plonky2 (« Beyond Limits: Pushing the Boundaries of ZK-EVM »), qui doit découper la table complète en plusieurs modules STARK, correctement liés via des lookups inter-tables. LogUp-GKR combine GKR pour améliorer les performances de LogUp. Caulk est le premier argument de lookup dont le temps du prouveur est sous-linéaire en taille de table, avec un prétraitement O(N log N) et un stockage O(N). D'autres suivront : Baloo, flookup, cq, caulk+. Lasso apporte plusieurs améliorations, évitant de s'engager sur la table entière si elle a une structure connue, et chargeant le prouveur uniquement pour les entrées réellement consultées. Jolt exploite Lasso pour prouver l'exécution d'une machine virtuelle via lookup.

3.6 Spartan (2019)

Spartan propose un IOP pour des circuits décrits en R1CS, exploitant les polynômes multivariés et le protocole sumcheck. Avec un bon schéma d'engagement polynomial, il donne un SNARK transparent avec un prouveur linéaire.

3.7 HyperPlonk (2022)

HyperPlonk s'inspire de Plonk mais utilise des polynômes multivariés. Il ne repose pas sur un quotient pour vérifier les contraintes, mais sur le protocole sumcheck. Il supporte des contraintes de haut degré sans nuire au temps du prouveur. N'utilisant pas de FFT, son temps de génération est linéaire en taille du circuit. HyperPlonk introduit un nouvel IOP de permutation adapté aux petits corps et un protocole d'ouverture groupée basé sur sumcheck, réduisant 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 de folding, une nouvelle méthode pour le calcul vérifiable incrémental (IVC). Le concept d'IVC remonte à Valiant, montrant comment combiner deux preuves de longueur k en une seule de longueur k. L'idée est de prouver une exécution longue en vérifiant récursivement que le passage de l'étape i à i+1 est correct, tout en vérifiant la preuve du passage précédent (i−1 à i).

Nova gère bien les calculs uniformes ; Supernova l'étend à des circuits hétérogènes. Nova utilise une version souple de R1CS et fonctionne sur des courbes compatibles. L'utilisation de cycles de courbes amicales (ex. courbes Pasta) pour l'IVC est aussi utilisée dans Pickles, brique fondamentale de Mina assurant un état concis. Toutefois, le folding diffère de la vérification récursive de SNARKs. L'idée d'accumulateur est plus liée au regroupement (batching) de preuves. Halo introduit l'accumulation comme alternative à la composition récursive de preuves. Protostar fournit un schéma IVC non uniforme pour Plonk, supportant des portes de haut degré et des lookups vectoriels.

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

Parallèlement à Pinocchio, des idées ont émergé pour arithmétiser des machines virtuelles, permettant de prouver l'exécution correcte de programmes quelconques. Bien que l'arithmétisation d'une VM soit souvent plus complexe ou moins efficace que des circuits dédiés, elle permet de prouver n'importe quel programme. Les idées de TinyRAM ont évolué vers Cairo VM, puis d'autres VMs (zk-EVMs, zkvms génériques). L'usage de fonctions de hachage résistantes aux collisions supprime le besoin de configuration fiable ou de courbes elliptiques, au prix de preuves plus longues.

1) TinyRAM (2013)

Dans « SNARKs for C », un SNARK basé sur des PCP est développé pour prouver l'exécution correcte de programmes C compilés vers TinyRAM (ordinateur à jeu d'instructions réduit). Cette machine suit une architecture Harvard avec une mémoire RAM adressable par octets. Grâce à la non-déterminisme, la taille du circuit croît quasi-linéairement avec le calcul, gérant efficacement boucles, flux de contrôle et accès mémoire arbitraires.

2) STARKs (2018)

Les STARKs ont été proposés par Ben Sasson et al. en 2018. Ils offrent une taille de preuve O(log²n), un prouveur et un vérificateur rapides, aucune configuration fiable, et sont considérés post-quantiques sécurisés. Ils sont d'abord utilisés par Starkware/Starknet avec la VM Cairo. Leurs composants clés sont :

• La représentation algébrique intermédiaire (AIR)

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

Les STARKs sont aussi utilisés par d'autres projets (Polygon Miden, Risc0, Winterfell, Neptune) ou adaptés (Boojum de ZK-Sync, Plonky2, Starky).

3) Ligero (2017)

• Ligero introduit un système de preuve avec taille O(√n), n étant la taille du circuit. Il organise les coefficients polynomiaux en matrices et utilise des codes linéaires.

• Brakedown s'appuie sur Ligero et introduit l'idée d'un schéma d'engagement polynomial indépendant du corps.

5. Nouvelles avancées en ZKP

L'usage en production de divers systèmes met en lumière leurs forces et stimule de nouveaux développements. Par exemple, l'arithmétisation Plonkish simplifie l'inclusion de portes personnalisées et d'arguments de lookup ; FRI comme PCS excelle en performance, surpassant Plonky. De même, l'usage du grand-product check dans AIR (donnant des AIR randomisés avec prétraitement) améliore les performances et simplifie les arguments d'accès mémoire. Les engagements basés sur le hachage se popularisent — tant pour leur rapidité matérielle que par l'introduction de nouvelles fonctions de hachage adaptées aux SNARKs.

1) Nouveaux schémas d'engagements polynomiaux (2023)

Avec l'émergence de SNARKs efficaces utilisant des polynômes multivariés (Spartan, HyperPlonk), l'intérêt croît pour de nouveaux engagements adaptés. Binius, Zeromorph et Basefold proposent des formes nouvelles pour les polynômes multilinéaires. Binius a l'avantage d'un coût nul pour représenter certains types de données (contrairement à beaucoup de systèmes utilisant des éléments de 32 bits pour un bit), et opère sur des corps binaires. L'engagement Binius s'inspire de Brakedown, conçu indépendant du corps. Basefold généralise FRI à d'autres codes que Reed-Solomon, créant un PCS indépendant du corps.

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

CCS généralise R1CS tout en englobant naturellement R1CS, Plonkish et AIR, sans surcoût. Combiné à l'IOP Spartan, il donne SuperSpartan, supportant des contraintes de haut degré sans que le coût cryptographique augmente avec le degré. En particulier, SuperSpartan produit un SNARK pour AIR avec un prouveur en temps linéaire.

6. Conclusion

Cet article retrace l'évolution des SNARKs depuis les années 1980. Les progrès en informatique, mathématiques et matériel, combinés à l'avènement des blockchains, ont permis de nouveaux SNARKs plus efficaces, ouvrant la voie à de nombreuses applications transformatrices. Chercheurs et ingénieurs améliorent continuellement les SNARKs selon leurs besoins, en ciblant taille des preuves, usage mémoire, transparence, sécurité post-quantique, temps du prouveur et du vérificateur.

Bien qu'il existât initialement deux lignes (SNARK vs STARK), les frontières s'estompent, cherchant à combiner les forces de différents systèmes. On voit ainsi des combinaisons d'arithmétisations variées avec de nouveaux engagements polynomiaux. De nouveaux systèmes émergeront, avec des performances accrues. Certains systèmes, difficiles à adapter, risquent d'être distancés, sauf si les outils permettent une intégration aisée sans modifier l'infrastructure de base.