STARK : Preuve par polynômes
TechFlow SélectionTechFlow Sélection
STARK : Preuve par polynômes
Comment fonctionne exactement cette nouvelle preuve à connaissance nulle ?
Dédié à des analyses Web3 approfondiesBeaucoup de gens ont entendu parler des ZK-SNARKS, une technologie de preuve à connaissance nulle générale et concise, applicable à divers scénarios allant de la computation vérifiable aux cryptomonnaies nécessitant une confidentialité. Cependant, vous ne savez peut-être pas encore qu’il existe maintenant un nouveau membre dans la famille : les ZK-STARKs. Le « T » signifie « transparent » (« transparent » en français), car les ZK-STARKs résolvent un inconvénient majeur des ZK-SNARKs : leur dépendance à un « setup de confiance » (trusted setup). Les ZK-STARKs reposent également sur des hypothèses cryptographiques plus simples, évitant l'utilisation de courbes elliptiques, d'appariements ou de l'hypothèse de connaissance de l'exposant (knowledge-of-exponent assumption), et s'appuient entièrement sur du hachage et la théorie de l'information. Cela signifie qu’ils restent sûrs même face à des attaquants disposant d’ordinateurs quantiques.
Bien sûr, cela a un coût : la taille d’une preuve passe de 288 octets (b) à plusieurs centaines de kilo-octets (ko). Bien que ce coût puisse ne pas toujours être justifié, dans certains cas — notamment pour les applications blockchain exigeant un niveau élevé de minimisation de la confiance — cela peut valoir le coup. Et si jamais les courbes elliptiques venaient à être cassées, ou si les ordinateurs quantiques devenaient réalité, alors ces coûts seraient certainement compensés.
Alors, comment fonctionnent précisément ces nouvelles preuves à connaissance nulle ? Avant d’y répondre, revenons un instant sur ce que font exactement les preuves succinctes et générales à connaissance nulle. Supposons que vous ayez une fonction publique \( f \), une entrée privée \( x \) et une sortie publique \( y \). Vous souhaitez prouver que vous connaissez un \( x \) tel que \( f(x) = y \), sans révéler ce qu’est \( x \) (note du traducteur : par exemple, vous voulez prouver que vous connaissez le code d’un coffre-fort sans divulguer le code lui-même). De plus, afin que la preuve soit concise, vous souhaitez qu’elle puisse être vérifiée beaucoup plus rapidement que l’exécution directe de \( f \).
Examinons quelques exemples concrets :
-
\( f \) est un calcul qui prend deux semaines sur un ordinateur classique, mais seulement deux heures sur un centre de données. Vous pouvez envoyer la tâche (le code de \( f \)) au centre de données, qui exécute le calcul et renvoie la réponse \( y \) accompagnée d'une preuve. Vous pouvez alors vérifier cette preuve en quelques millisecondes et être certain que \( y \) est bien la bonne réponse.
-
Vous avez une transaction chiffrée de la forme « X1 est mon ancien solde, X2 est ton ancien solde, X3 est mon nouveau solde, X4 est ton nouveau solde ». Vous souhaitez construire une preuve que cette transaction est valide (c’est-à-dire que les soldes anciens et nouveaux sont non négatifs, et que la diminution de mon solde correspond exactement à l’augmentation du tien). Ici, \( x \) pourrait être une paire de clés cryptographiques, \( f \) une fonction intégrant la transaction publiquement, déchiffrant avec les clés, effectuant les vérifications, et retournant 1 si tout est bon, sinon 0. La valeur \( y \) serait donc nécessairement 1.
-
Vous avez une blockchain similaire à Ethereum et venez de télécharger le dernier bloc. Vous voulez construire une preuve que ce bloc est valide, qu’il est bien le dernier de la chaîne, et que chaque bloc précédent est également valide. Vous demandez à un nœud complet connu de fournir une telle preuve. Ici, \( x \) représente toute la blockchain (ou une partie), \( f \) est une fonction qui traite chaque bloc, vérifie sa validité, et retourne le hachage du dernier bloc, tandis que \( y \) est le hachage du bloc que vous venez de télécharger.
Quel est donc le défi fondamental dans tous ces cas ? En réalité,
la garantie de connaissance nulle (c’est-à-dire de confidentialité) est (relativement !) facile à assurer. Il existe plusieurs façons de transformer n’importe quel calcul en un problème équivalent au coloriage d’un graphe, où un coloriage valide du graphe correspond à une solution du problème initial, puis d’utiliser un protocole classique de preuve à connaissance nulle pour prouver que l’on possède un tel coloriage, sans le révéler. Un excellent article de Matthew Green datant de 2014 explique bien ces détails.
En revanche, la concision est bien plus difficile à obtenir. Intuitivement, il est très dur de prouver succinctement des faits liés à un calcul, car les calculs sont extrêmement fragiles. Si vous avez un calcul long et complexe, et que vous modifiez ne serait-ce qu’un seul bit au milieu, dans de nombreux cas, cela suffit à produire un résultat complètement différent. Ainsi, il semble difficile de pouvoir simplement échantillonner aléatoirement une partie du calcul pour vérifier sa validité, car on risquerait facilement de rater ce fameux « un mauvais bit » (one evil bit). Pourtant, grâce à des méthodes mathématiques sophistiquées, il s’avère que c’est possible.
L’intuition générale du protocole repose sur des mathématiques similaires à celles utilisées dans le codage correcteur d’erreurs (comme le erasure coding), souvent employé pour rendre les données résistantes aux pannes. Si vous avez des données, vous pouvez les encoder comme des points sur une droite. En choisissant quatre points sur cette droite, n’importe lesquels deux suffisent à reconstruire la droite entière — et donc à retrouver les deux autres points. Mieux encore, si vous modifiez même légèrement les données initiales, au moins trois des quatre points seront différents. Vous pouvez étendre cela : encoder vos données dans un polynôme de degré 1 000 000, puis choisir 2 000 000 points dessus. Alors, n’importe quel ensemble de 1 000 001 points permettra de reconstruire le polynôme d’origine — et donc tous les autres points — et toute modification mineure des données changera au moins 1 000 000 points. L’algorithme décrit ici exploite massivement cette idée via les polynômes pour amplifier les erreurs.
Un exemple simple
Supposons que vous souhaitiez prouver que vous avez un polynôme \( P \) tel que pour tout \( x \) entre 1 et 1 million, \( P(x) \) est un entier compris entre 0 et 9 inclus. C’est un exemple simple de ce qu’on appelle communément un « contrôle d’intervalle » (range check). On peut imaginer cela comme une vérification après une transaction bancaire, garantissant qu’un solde reste positif. Si \( 1 \leq P(x) \leq 9 \), cela pourrait aussi faire partie de la vérification d’une grille de sudoku valide.
La méthode « classique » pour prouver cela consisterait à parcourir chacun des 1 000 000 points et à vérifier individuellement chaque valeur. Mais nous voulons savoir s’il est possible de construire une preuve vérifiable en moins de 1 000 000 étapes. Vérifier aléatoirement quelques valeurs de \( P \) ne suffit pas : un faussaire pourrait concevoir un \( P \) qui satisfait la condition pour 999 999 valeurs, mais pas pour la dernière, et un échantillonnage aléatoire aurait de fortes chances de rater ce point critique. Que pouvons-nous faire alors ?
Transformons le problème mathématiquement. Soit \( C(x) \) un polynôme de vérification de contrainte tel que \( C(x) = 0 \) si \( 0 \leq x \leq 9 \), et \( C(x) \neq 0 \) sinon. Une façon simple de construire \( C(x) \) est : \( x \cdot (x-1) \cdot (x-2) \cdot \ldots \cdot (x-9) \).
Le problème devient alors : prouver que vous connaissez \( P \) tel que \( C(P(x)) = 0 \) pour tout \( x \) entre 1 et 1 000 000. Soit \( Z(x) = (x-1) \cdot (x-2) \cdot \ldots \cdot (x-1\,000\,000) \). Un fait mathématique connu est que tout polynôme nul sur les entiers de 1 à 1 000 000 est divisible par \( Z(x) \). Le problème se reformule donc ainsi : prouver que vous connaissez \( P \) et \( D \) tels que \( C(P(x)) = Z(x) \cdot D(x) \) pour tout \( x \). (Note : si vous connaissez un \( C(P(x)) \) valide, calculer \( D(x) \) en divisant par \( Z(x) \) n’est pas trop difficile — via la division euclidienne de polynômes ou des algorithmes plus rapides basés sur la transformée de Fourier rapide.) Nous avons ainsi transformé l’énoncé initial en un problème mathématiquement plus clair et plus facile à prouver.
Comment procéder pour la preuve ? Imaginons un échange en trois étapes entre le prouveur et le vérificateur :
- Le prouveur envoie certaines informations
- Le vérificateur envoie une demande
- Le prouveur envoie davantage d’informations
D’abord, le prouveur soumet (c’est-à-dire construit un arbre de Merkle et envoie la racine au vérificateur) les valeurs de \( P(x) \) et \( D(x) \) pour tout \( x \) allant de 1 à 1 milliard (oui, 1 milliard). Cela inclut 1 million de points où \( 0 \leq P(x) \leq 9 \), et 999 millions de points potentiellement hors contrainte.
Nous supposons que le vérificateur connaît déjà les valeurs de \( Z(x) \) pour tous ces points ; dans ce schéma, \( Z(x) \) agit comme une clé de vérification publique que tout le monde doit connaître à l’avance. (Le client n’a pas besoin de stocker intégralement \( Z(x) \), il peut simplement garder la racine de l’arbre de Merkle de \( Z(x) \), et le prouveur fournit alors les branches nécessaires pour chaque valeur interrogée ; ou alors, \( Z(x) \) peut être très facile à calculer pour un \( x \) donné.) Après avoir reçu la soumission (la racine de Merkle), le vérificateur choisit aléatoirement 16 valeurs de \( x \) entre 1 et 1 milliard, et demande au prouveur de fournir les branches de Merkle correspondantes pour \( P(x) \) et \( D(x) \). Le prouveur les fournit, et le vérificateur vérifie :
-
Que les branches correspondent bien à la racine fournie précédemment
-
Que \( C(P(x)) = Z(x) \cdot D(x) \) dans les 16 cas
Nous savons que cette preuve assure la complétude : si vous connaissez vraiment un \( P(x) \) valide, calculez correctement \( D(x) \), et construisez honnêtement la preuve, alors les 16 vérifications réussiront. Mais qu’en est-il de la solidité ?
Autrement dit, si un prouveur malveillant soumet un mauvais \( P(x) \), quelle est la probabilité minimale qu’il soit détecté ? Analysons : \( C(P(x)) \) est un polynôme de degré au plus 10 000 000.
On sait que deux polynômes différents de degré \( N \) peuvent coïncider en au plus \( N \) points. Ainsi, un polynôme de degré 1 000 000 diffère d’un autre polynôme (par exemple \( Z(x) \cdot D(x) \)) en au moins 990 000 000 points. Par conséquent, même avec un seul contrôle, la probabilité de détecter un mauvais \( P(x) \) est de 99 %. Avec 16 vérifications indépendantes, cette probabilité monte à \( 1 - 10^{-32} \). Autrement dit, tromper ce protocole est aussi difficile que de trouver une collision de hachage.
Que venons-nous d’analyser ? Nous avons utilisé les polynômes pour « amplifier » les erreurs présentes dans toute mauvaise solution, transformant ainsi un problème nécessitant un million de vérifications directes en un protocole vérifiable en une seule étape avec une probabilité de 99 % de détecter une erreur.
Nous pouvons transformer ce mécanisme en trois étapes en une preuve non interactive, où le prouveur diffuse la preuve et n’importe qui peut la vérifier, en utilisant l’heuristique de Fiat-Shamir. Le prouveur construit d’abord l’arbre de Merkle des valeurs \( P(x) \) et \( D(x) \), puis calcule la racine. Cette racine sert ensuite de source d’entropie pour déterminer aléatoirement quelles branches de l’arbre doivent être fournies. Le prouveur diffuse alors la racine et les branches comme preuve. Tout le calcul est fait côté prouveur. Le calcul de la racine à partir des données, puis son utilisation pour sélectionner les branches à révéler, remplace efficacement la nécessité d’un vérificateur interactif.
Pour un prouveur malveillant ne possédant pas de \( P(x) \) valide, la seule chose qu’il puisse faire est d’essayer continuellement de construire une preuve jusqu’à ce qu’il ait assez de chance pour trouver une racine dont les branches sélectionnées passent les vérifications. Mais étant donné que la solidité est de \( 1 - 10^{-32} \) (c’est-à-dire qu’un faux \( P(x) \) a moins d’une chance sur \( 10^{32} \) de passer), cela pourrait prendre des milliards d’années à un attaquant.
Approfondissement
Pour illustrer la puissance de cette technique, utilisons-la pour faire quelque chose d’inhabituel : prouver que vous connaissez le millionième nombre de Fibonacci. Pour cela, nous allons prouver que vous connaissez un polynôme \( P \) représentant une bande de calcul, où \( P(x) \) est le \( x \)-ième nombre de Fibonacci. Le polynôme de vérification de contrainte portera désormais sur trois coordonnées : \( C(x_1, x_2, x_3) = x_3 - x_2 - x_1 \) (notez que pour une suite de Fibonacci, \( C(P(x), P(x+1), P(x+2)) = 0 \) pour tout \( x \)).
-Fibonacci-
Le problème reformulé devient : vérifier que vous connaissez \( P \) et \( D \) tels que \( C(P(x), P(x+1), P(x+2)) = Z(x) \cdot D(x) \). Pour chacun des 16 cas audités, le prouveur doit fournir les branches de Merkle pour \( P(x) \), \( P(x+1) \), \( P(x+2) \) et \( D(x) \). Le prouveur doit aussi fournir des branches pour prouver que \( P(0) = P(1) = 1 \). Sinon, le processus reste identique.
Pour implémenter cela en pratique, deux problèmes restent à résoudre. Premièrement, ce schéma n’est pas efficace pour les grands nombres, car ils deviennent vite énormes. Par exemple, le millionième nombre de Fibonacci contient 208 988 bits. Pour atteindre la concision en pratique, il faut remplacer les opérations sur les entiers par des opérations dans un corps fini — un système de nombres respectant les mêmes règles algébriques (comme \( a \cdot (b+c) = a\cdot b + a\cdot c \)), mais où chaque nombre occupe une taille fixe. Prouver le millionième nombre de Fibonacci nécessiterait alors une conception plus élaborée réalisant l’arithmétique sur grands entiers dans ce cadre de corps fini.
Le corps fini le plus simple est l’arithmétique modulaire : pour un nombre premier \( N \), remplacer chaque \( a + b \) par \( (a + b) \mod N \), faire de même pour la soustraction et la multiplication, et utiliser l’inverse modulaire pour la division (par exemple, si \( N = 7 \), alors \( 3 + 4 = 0 \), \( 2 + 6 = 1 \), \( 3 \times 4 = 5 \), \( 4 / 2 = 2 \), \( 5 / 2 = 6 \)). Vous pouvez en apprendre davantage sur ces systèmes numériques ici (recherchez « prime field ») ou via Wikipédia (recherchez « finite fields » et « prime fields » ; cela peut sembler complexe, lié à l’algèbre abstraite, mais ne vous laissez pas impressionner).
Deuxièmement, vous avez peut-être remarqué que dans mon esquisse de preuve de solidité, j’ai ignoré une attaque possible : que se passe-t-il si, au lieu de fournir des valeurs provenant d’un polynôme de degré raisonnable (1 000 000 pour \( P \), 9 000 000 pour \( D \)), un attaquant soumet des valeurs arbitraires, non issues d’un polynôme ? Dans ce cas, un \( C(P(x)) \) invalide différerait d’un \( C(P(x)) \) valide en au moins 990 millions de points, mais un attaquant pourrait essayer de contourner cela. Par exemple, il pourrait générer pour chaque \( x \) une valeur aléatoire \( p \), calculer \( d = C(p) / Z(x) \), puis soumettre ces \( p \) et \( d \) comme s’ils venaient de vrais polynômes. Ces valeurs ne viendraient pas d’un polynôme de faible degré, mais elles passeraient quand même les tests.
Il s’avère que, bien que les outils soient complexes, cette possibilité peut être efficacement contrée, et c’est là que réside l’innovation mathématique clé des STARKs. Cependant, cette solution a une limite : bien qu’on puisse rejeter les données très éloignées d’un polynôme de degré 1 000 000 (par exemple, celles nécessitant de modifier 20 % des valeurs pour en devenir un), on ne peut pas exclure des polynômes ne différant que d’un ou deux points. Ainsi, ces outils fournissent une preuve de proximité — prouvant que la majorité des points de \( P \) et \( D \) sont proches d’un polynôme.
Par conséquent, bien qu’il y ait deux « pièges », cela suffit pour construire une preuve valable. Premièrement, le vérificateur doit vérifier davantage de points, pour tenir compte des erreurs dues à cette approximation. Deuxièmement, si l’on effectue des « vérifications de conditions aux limites » (boundary constraint checking), comme prouver que \( P(0) = P(1) = 1 \) dans l’exemple de Fibonacci, alors il faut étendre la preuve de proximité pour garantir non seulement que la majorité des points sont sur un même polynôme, mais aussi que ces points spécifiques (ou ceux que l’on veut vérifier) y sont bien inclus.
Dans la prochaine partie de cette série, je traiterai plus en détail la solution au problème de la vérification de proximité.
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
@VitalikButerin
