zk-SNARKs : arguments succincts non interactifs

Un zk-SNARK (Zero-Knowledge Succinct Non-interactive ARgument of Knowledge) est une preuve qui : (1) est à divulgation nulle de connaissance, (2) est concise (preuve minuscule, vérification rapide quelle que soit la taille du calcul), (3) est non interactive (une seule chaîne de preuve).

Les protocoles Sigma conviennent aux affirmations simples (connaissance d'un logarithme discret). Pour des calculs complexes — « J'ai exécuté correctement cette fonction sur des données d'entrée privées » — il faut un système de preuve généraliste. Les SNARK prouvent des calculs quelconques en un temps de vérification O(1).

Le calcul est d'abord exprimé sous la forme d'un circuit arithmétique : un graphe orienté acyclique composé de portes d'addition et de multiplication sur un corps fini. Exemple : prouver que vous connaissez x tel que x^3 + x + 5 = 35 sans révéler x=3. Le circuit comporte environ 5 portes.

Un circuit arithmétique est converti en R1CS : un ensemble de contraintes (A*z)*(B*z) = C*z, où z est un vecteur contenant les valeurs de tous les fils. Chaque porte de multiplication devient une contrainte. Le prouveur doit trouver un z qui satisfait toutes les contraintes sans révéler les fils privés.

R1CS est converti en QAP : des polynômes A(x), B(x), C(x) tels que A(x)*B(x)-C(x) est divisible par un polynôme cible t(x) si et seulement si les contraintes sont satisfaites. Le prouveur montre qu'il connaît un quotient polynomial H(x) sans révéler le témoin.

Groth16 (2016) est le SNARK généraliste le plus efficace. Après une configuration de confiance (génération du CRS), le prouveur produit une preuve composée de 3 éléments de groupe (environ 192 octets pour BLS12-381). Vérification : 3 opérations d'appariement. La preuve a une taille constante, quelle que soit la taille du circuit.

Groth16 nécessite une configuration de confiance pour chaque circuit : générer un secret toxique (un secret aléatoire), calculer la chaîne de référence commune, puis détruire le secret toxique. Si ce secret subsiste, un adversaire peut forger des preuves. Les cérémonies multipartites (Powers of Tau) répartissent la confiance.

PLONK (2019) utilise une configuration de confiance universelle : une seule cérémonie fonctionne pour tous les circuits jusqu'à une limite de taille donnée. Aucune configuration propre à chaque circuit n'est nécessaire. Compromis : les preuves sont légèrement plus grandes que celles de Groth16. Utilisé dans les implémentations de ZK-EVM (Polygon Hermez, zkSync Era).

Les STARK (Scalable Transparent ARguments of Knowledge) ne nécessitent aucune configuration de confiance et utilisent des fonctions de hachage (sûres après l'arrivée des ordinateurs quantiques). Compromis : des preuves plus grandes (des dizaines de Ko contre 200 octets). Utilisés dans StarkWare/StarkNet et dans le langage Cairo. Les SNARK sont plus petits ; les STARK résistent aux attaques quantiques.

Groth16 utilise des appariements bilinéaires : e: G1 × G2 → GT, où e(a*P, b*Q) = e(P,Q)^{ab}. Cela permet de vérifier des identités polynomiales dans l'exposant sans révéler les valeurs. La courbe BLS12-381 est optimisée pour des appariements Groth16 efficaces.

Temps de génération d'une preuve Groth16 pour un circuit de 10^6 portes : environ 10 secondes sur un CPU moderne. Vérification : environ 1 ms. Cette asymétrie est intentionnelle : le prouveur (qui a effectué le calcul intensif) réalise le travail ; le vérificateur (le nœud de la chaîne de blocs) n'effectue presque aucun travail.

Quel est le principal inconvénient de Groth16 par rapport à PLONK ?

Les zk-SNARK prouvent des calculs quelconques au moyen de preuves de taille constante. Chaîne de traitement : calcul → circuit arithmétique → R1CS → QAP → preuve SNARK. Groth16 est le plus efficace (configuration de confiance pour chaque circuit) ; PLONK utilise une configuration universelle. Ensuite : applications des ZKP dans la chaîne de blocs.