Programme arithmétique quadratique : essai sur les preuves à divulgation nulle
TechFlow SélectionTechFlow Sélection
Programme arithmétique quadratique : essai sur les preuves à divulgation nulle
La compréhension des zk-SNARKs est effectivement assez difficile, notamment parce que l'ensemble du système comporte de nombreux éléments mobiles qui doivent être assemblés pour fonctionner correctement.
Dédié à des analyses Web3 approfondiesRédaction : Vitalik Buterin
Date de publication : 10 décembre 2016
Récemment, il y a eu beaucoup d'intérêt pour la technologie sous-jacente aux zk-SNARKs (preuves à connaissance nulle), et de plus en plus de tentatives sont faites pour démystifier ce que beaucoup appellent des « mathématiques lunaires », car sa complexité est considérée comme extrêmement difficile à comprendre.
Comprendre les zk-SNARKs est effectivement assez difficile, surtout parce qu'il y a trop de composants interdépendants qui doivent tous fonctionner ensemble, mais si nous décomposons cette technologie pièce par pièce, elle devient plus facile à saisir.
Cet article ne prétend pas être une introduction complète aux zk-SNARKs ; il suppose que vous avez les connaissances préalables suivantes :
1 - Vous connaissez les zk-SNARKs et leurs principes généraux ;
2 - Vous avez suffisamment de base en mathématiques pour comprendre quelques notions élémentaires sur les polynômes (par exemple, si P(x) + Q(x) = (P + Q)(x), où P et Q représentent des polynômes, et que vous êtes déjà familier avec ce type de notation, alors vous remplissez les conditions pour poursuivre la lecture).
Carte conceptuelle des zk-SNARKs, réalisée par Eran Tromer
Comme indiqué dans l'image ci-dessus, on peut diviser ces preuves à connaissance nulle en deux étapes allant du haut vers le bas. Tout d'abord, les zk-SNARKs ne peuvent pas être appliqués directement à n'importe quel problème computationnel ; au contraire, vous devez convertir le problème en la bonne « forme » d'opérations. Cette forme s'appelle un « Programme Arithmétique Quadratique » (QAP). Convertir le code d'une fonction en cette forme est déjà une étape cruciale. Parallèlement au processus de transformation du code en QAP, un autre processus permet, si l'on dispose d'une entrée pour ce code, de créer une solution correspondante (parfois appelée « témoignage » du QAP). C'est précisément de cela que traite cet article.
Après cela, il existe un autre processus assez complexe permettant de créer une véritable « preuve à connaissance nulle » à partir de ce QAP, ainsi qu'un processus distinct pour vérifier la preuve reçue d'autrui, mais ces détails dépassent le cadre de cet article.
Dans l'exemple ci-dessous, nous choisirons un problème très simple :
Trouver la solution d'une équation cubique : x**3 + x + 5 == 35 (indice : la réponse est 3).
Ce problème est simple, mais important, car il vous permet de voir comment toutes les mécaniques fonctionnent.
On peut décrire cette équation en langage de programmation comme suit :
def qeval(x):
y = x**3
return x + y + 5
Le langage de programmation simplifié utilisé ici supporte les opérations arithmétiques de base (+, -, *, /), les puissances entières (x^7, mais pas x*y) et l'affectation de variables. Il est suffisamment puissant pour théoriquement exécuter tout calcul (à condition que le nombre d'étapes soit borné ; les boucles ne sont pas autorisées). Notez que les opérations modulo (%) et les comparateurs (<, >, ≤, ≥) ne sont pas pris en charge, car il n'existe aucune méthode efficace pour réaliser modulo ou des comparaisons directes dans des groupes cycliques finis (merci ; s’il existait une telle méthode, la cryptographie à courbe elliptique serait brisée plus vite que par « recherche dichotomique » ou « théorème des restes chinois »).
Vous pouvez étendre le langage pour inclure modulo et comparaison via la décomposition binaire (par exemple : 13 = 2**3 + 2**2 + 1 = 8 + 4 + 1) comme entrée auxiliaire, prouver la validité de cette décomposition, puis effectuer des calculs mathématiques dans un circuit binaire ; la vérification d'égalité (==) est également faisable dans les corps finis, voire même plus simple, mais nous ne discuterons pas de ces deux détails maintenant. On pourrait aussi étendre le langage pour supporter les conditions (par exemple transformer l'instruction : if x < 5: y = 7; else: y = 9; en forme arithmétique : y = 7 * (x < 5) + 9 * (x >= 5)), mais notez que les deux « chemins » de la condition doivent être exécutés, ce qui entraîne une importante surcharge si vous avez plusieurs conditions imbriquées.
Maintenant, passons pas à pas à travers ce processus. Si vous souhaitez implémenter cela vous-même, j'ai fourni un code d'exemple en Python ici (à but purement éducatif ; non prêt à produire des QAPs pour des zk-SNARKs réels !)
Étape 1 : Aplatir
La première étape est un processus d’« aplatissement », où nous décomposons le code initial (qui peut contenir des expressions et instructions arbitrairement complexes) en expressions simples de deux formes uniquement :
1- x = y (y pouvant être une variable ou un nombre)
2- x = y(op)z (op pouvant être +, -, *, / ; y et z pouvant être des variables, des nombres ou des sous-expressions).
Vous pouvez voir ces expressions comme des portes logiques dans un circuit. Le résultat de l’aplatissement de l’expression x**3 + x + 5 est le suivant :
sym_1 = x * x
y = sym_1 * x // équivaut à y = x**3
sym_2 = y + x
~out = sym_2 + 5
Chaque ligne ci-dessus peut être vue comme une porte logique dans un circuit. Comparé au code original, nous avons introduit deux variables intermédiaires sym_1 et sym_2, ainsi qu’une variable redondante ~out pour représenter la sortie. Il est clair que la séquence d’instructions « aplaties » est équivalente au code initial.
Étape 2 : Conversion en R1CS
Nous allons maintenant le convertir en ce qu’on appelle un système de contraintes à rang 1 (R1CS). Un R1CS est une suite de triplets de vecteurs (a, b, c). Une solution à un R1CS est un vecteur s qui doit satisfaire l’équation :
s . a * s . b - s . c = 0
où . désigne le produit scalaire.
Par exemple, voici un R1CS satisfaisant :
a = (5,0,0,0,0,1),
b = (1,0,0,0,0,0),
c = (0,0,1,0,0,0),
s = (1,3,35,9,27,30),
(Note du traducteur : premier 35 = 1×5 + 30×1, deuxième 35 = 35×1)
L'exemple ci-dessus n'est qu'une seule contrainte. Nous allons maintenant convertir chaque porte logique (chaque instruction « aplatie ») en une contrainte (un triplet de vecteurs (a, b, c)). La méthode de conversion dépend de l'opération (+,-,*,/) et du fait que les paramètres soient des variables ou des nombres. En plus des cinq variables après aplatissement ('x', '~out', 'sym_1', 'y', 'sym_2'), nous devons introduire une variable redondante ~one en première position pour représenter le nombre 1. Pour notre système, les six composantes du vecteur correspondent à (l'ordre peut varier tant qu'il est cohérent) :
'~one', 'x', '~out', 'sym_1', 'y', 'sym_2'
Première porte
sym_1 = x * x, soit x*x - sym_1 = 0
On obtient le triplet suivant :
a = [0, 1, 0, 0, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 1, 0, 0]
Si le deuxième élément du vecteur solution s vaut 3 et le quatrième vaut 9, alors cela fonctionne quelle que soit la valeur des autres éléments, car : a = 3×1, b = 3×1, c = 9×1, donc a × b = c. De même, si le deuxième élément de s vaut 7 et le quatrième vaut 49, cela passe aussi le test. Ce premier test vérifie simplement la cohérence entre les entrées et sorties de la première porte.
Deuxième porte
y = sym_1 * x, soit sym_1 * x - y = 0
On obtient le triplet suivant :
a = [0, 0, 0, 1, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 0, 1, 0]
Troisième porte
sym_2 = y + x, la porte d'addition doit être transformée en : (x + y) * 1 - sym_2 = 0
On obtient le triplet suivant :
a = [0, 1, 0, 0, 1, 0]
b = [1, 0, 0, 0, 0, 0] correspondant à la constante 1, utilisant ~one
c = [0, 0, 0, 0, 0, 1]
Quatrième porte
~out = sym_2 + 5, soit (sym_2 + 5) * 1 - ~out = 0
On obtient le triplet suivant :
a = [5, 0, 0, 0, 0, 1]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 1, 0, 0, 0]
Supposons maintenant que x = 3. D'après la première porte, sym_1 = 9 ; d'après la deuxième, y = 27 ; d'après la troisième, sym_2 = 30 ; d'après la quatrième, ~out = 35. Donc selon l'ordre : '~one', 'x', '~out', 'sym_1', 'y', 'sym_2', on obtient :
s = [1, 3, 35, 9, 27, 30]
En supposant différentes valeurs de x, on obtiendra différents vecteurs s, mais tous peuvent être utilisés pour vérifier les (a, b, c).
Nous avons maintenant un R1CS de quatre contraintes. Le R1CS complet est donc :
A
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 1, 0]
[5, 0, 0, 0, 0, 1]
B
[0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
C
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0]
Étape 3 : Du R1CS au QAP
L'étape suivante consiste à convertir ce R1CS en forme QAP, qui implémente exactement la même logique, mais utilise des polynômes au lieu de produits scalaires. Nous procédons ainsi : passer de 4 triplets de vecteurs de longueur 6 à 6 triplets de polynômes de degré 3, où chaque coordonnée x représente une contrainte. Autrement dit, si nous évaluons les polynômes en x=1, nous obtenons le premier triplet de vecteurs ; en x=2, le second, etc.
Nous utilisons l'interpolation de Lagrange pour cette transformation. L'interpolation de Lagrange résout le problème suivant : étant donné un ensemble de points (des couples (x,y)), trouver un polynôme passant par tous ces points. Nous décomposons le problème : pour chaque coordonnée x, nous créons un polynôme valant la coordonnée y désirée en ce point x, et 0 aux autres coordonnées x pertinentes, puis additionnons tous ces polynômes.
Faisons un exemple. Supposons vouloir un polynôme passant par (1,3), (2,2) et (3,4). Commençons par créer un polynôme passant par (1,3), (2,0) et (3,0). Il se trouve qu’un polynôme « s’annulant » en x=2 et x=3 est facile à construire :
y = (x - 2) * (x - 3)
Comme illustré ci-dessous :
Puis, on « étire » verticalement avec :
y = (x - 2) * (x - 3) * 3 / ((1 - 2) * (1 - 3))
Ce qui donne après simplification :
y = 1.5 * x**2 - 7.5 * x + 9
Ce polynôme passe bien par (1,3), (2,0) et (3,0), comme montré ci-dessous :
En combinant avec les points (2,2) et (3,4), on obtient :
y = 1.5 * x**2 - 5.5 * x + 7
Voilà l'équation souhaitée. L'algorithme ci-dessus nécessite O(n³) temps, car pour chacun des n points, multiplier les polynômes prend O(n²). Avec un peu de réflexion, cela peut être réduit à O(n²), et encore davantage avec la transformée de Fourier rapide, etc. — une optimisation cruciale lorsque les fonctions utilisées dans les zk-SNARKs comportent souvent des milliers de portes.
Je donne ici directement la formule d'interpolation de Lagrange :
Le polynôme de degré n-1 passant par n points (x₁,y₁), (x₂,y₂), ..., (xₙ,yₙ) est :
Par exemple, le polynôme passant par (1,3), (2,2), (3,4) est :
Une fois cette formule maîtrisée, nous pouvons continuer. Nous devons maintenant convertir les quatre triplets de vecteurs de longueur 6 en six ensembles de polynômes, chaque ensemble contenant trois polynômes de degré 3. Nous évaluons chaque contrainte à une coordonnée x différente. Ici, nous avons quatre contraintes, donc nous utiliserons x = 1, 2, 3, 4.
Appliquons maintenant l'interpolation de Lagrange pour convertir le R1CS en forme QAP. Calculons d'abord le polynôme correspondant aux premières composantes des vecteurs a des quatre contraintes, c’est-à-dire trouvons le polynôme passant par (1,0), (2,0), (3,0), (4,0). De même pour les autres composantes.
Voici directement les résultats :
Polynômes A
[-5.0, 9.166, -5.0, 0.833]
[8.0, -11.333, 5.0, -0.666]
[0.0, 0.0, 0.0, 0.0]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]
[-1.0, 1.833, -1.0, 0.166]
Polynômes B
[3.0, -5.166, 2.5, -0.333]
[-2.0, 5.166, -2.5, 0.333]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
Polynômes C
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[-1.0, 1.833, -1.0, 0.166]
[4.0, -4.333, 1.5, -0.166]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]
Les coefficients sont donnés en ordre croissant. Par exemple, le premier polynôme est : 0.833 * x³ - 5 * x² + 9.166 * x - 5. En évaluant ces dix-huit polynômes en x=1, on retrouve les trois vecteurs de la première contrainte :
(0, 1, 0, 0, 0, 0),
(0, 1, 0, 0, 0, 0),
(0, 0, 0, 1, 0, 0),
...
De même, en x=2, 3, 4, on retrouve les parties restantes du R1CS.
Étape 4 : Vérification du QAP
En convertissant le R1CS en QAP, nous pouvons vérifier simultanément toutes les contraintes via des opérations polynomiales, plutôt que de tester chaque contrainte individuellement comme dans le R1CS. Comme illustré ci-dessous :
Ici, le test du produit scalaire étant une suite d'additions et multiplications de polynômes, le résultat est lui-même un polynôme. Si ce polynôme vaut 0 en chaque coordonnée x correspondant à une porte logique, alors toutes les contraintes sont satisfaites. S’il a une valeur non nulle quelque part, alors les flux entrants/sortants de la porte sont incohérents.
Notons que le polynôme résultant n’a pas besoin d’être identiquement nul — en général, il ne l’est pas. Il peut avoir n’importe quel comportement aux points ne correspondant à aucune porte, tant qu’il s’annule à tous les points associés à une porte. Pour vérifier la validité, nous n’évaluons pas le polynôme t = A . s * B . s - C . s en chaque point ; au contraire, nous divisons t par un autre polynôme Z, puis vérifions que Z divise t exactement, c’est-à-dire que la division t / Z n’a pas de reste.
Z est défini comme (x - 1) * (x - 2) * (x - 3) * ... — le polynôme le plus simple s’annulant à tous les points correspondant aux portes. Un fait fondamental d’algèbre : tout polynôme nul en ces points est multiple de ce polynôme minimal. Si un polynôme est multiple de Z, il s’annule en tous ces points. Cette équivalence simplifie grandement notre tâche.
Calculons maintenant le test du produit scalaire avec les polynômes ci-dessus.
D'abord, obtenons les polynômes intermédiaires :
A . s = [43.0, -73.333, 38.5, -5.166]
B . s = [-3.0, 10.333, -5.0, 0.666]
C . s = [-41.0, 71.666, -24.5, 2.833]
(Note du traducteur :
43.0 = -5×1 + 8×3 + 0×35 -6×9 +4×27 -1×30,
-73.333 = 9.166×1 -11.333×3 +0×35 +9.5×9 -7×27 +1.833×30,
...
-3 = 3×1 -2×3 +0×35 +0×9 +0×27 +0×30
...)
En calculant A . s * B . s - C . s, on obtient :
t = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]
(Note du traducteur :
A . s = [43.0, -73.333, 38.5, -5.166] = -5.166 x³ + 38.5 x² -73.333 x + 43,
B . s = [-3.0, 10.333, -5.0, 0.666] = 0.666 x³ -5 x² +10.333 x -3.0,
C . s = [-41.0, 71.666, -24.5, 2.833] = 2.833 x³ -24.5 x² +71.666 x -41.0
Le calcul de A . s * B . s - C . s donne les coefficients ci-dessus, classés par puissance croissante.)
Cliquez ici pour voir le calcul
Le polynôme minimal est :
Z = (x - 1) * (x - 2) * (x - 3) * (x - 4)
Soit :
Z = [24, -50, 35, -10, 1]
Effectuons maintenant la division polynomiale :
h = t / Z = [-3.666, 17.055, -3.444]
h doit être divisible sans reste.
Cliquez ici pour vérifier en sens inverse
Nous avons trouvé une solution au QAP. Si nous tentions de falsifier les variables dans le R1CS qui a conduit à cette solution QAP — par exemple, en changeant le dernier chiffre de s de 30 à 31 — alors le polynôme t échouerait au test (dans ce cas, en x=3, il vaudrait 1 au lieu de 0), et ne serait pas divisible par Z ; la division t/Z donnerait un reste, par exemple [-5.0, 8.833, -4.5, 0.666].
Notez que ceci n'est qu'un exemple très simple ; dans le monde réel, les opérations arithmétiques ont lieu dans des corps finis avec des nombres inhabituels, où toutes les lois algébriques que nous connaissons et aimons restent valides, mais toutes les valeurs sont des éléments d’un ensemble fini, généralement des entiers compris entre 0 et n-1. Par exemple, si n=13, alors 1/2 = 7 (car 7×2 ≡ 1 mod 13), 3×5 = 2, etc. L’utilisation de l’arithmétique modulaire élimine les problèmes d’erreurs d’arrondi et permet une intégration harmonieuse avec les courbes elliptiques, ce qui rend finalement les protocoles zk-SNARK véritablement sécurisés.
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
