Vitalik : Principe interne des zk-SNARKs
TechFlow SélectionTechFlow Sélection
Vitalik : Principe interne des zk-SNARKs
Cet article suppose que vous connaissez déjà ces deux concepts, ainsi que les bases des zk-SNARKs et leur fonctionnement.
Dédié à des analyses Web3 approfondies*Note : Cet article a été rédigé en février 2017
Cet article explique comment fonctionne la technologie sous-jacente des zk-SNARKs. Les articles précédents sur les programmes quadratiques arithmétiques et les appariements de courbes elliptiques sont à lire absolument ; nous supposerons ici que vous maîtrisez ces deux concepts ainsi que les bases des zk-SNARKs et leur objectif. Voir également une autre introduction aux zk-SNARKs, l'article de Christian Reitwiessner.
Dans nos articles précédents, nous avons introduit les programmes quadratiques arithmétiques (QAP), une méthode permettant de représenter n'importe quel problème de calcul sous forme d'équations polynomiales. Nous avons aussi présenté les appariements de courbes elliptiques, qui autorisent une forme très limitée de chiffrement homomorphe unidirectionnel, permettant notamment de vérifier des égalités. Maintenant, nous allons reprendre là où nous nous étions arrêtés, et utiliser les appariements de courbes elliptiques ainsi que d'autres astuces mathématiques pour permettre à un prouveur de démontrer qu’il connaît une solution à un QAP spécifique, sans révéler aucune information sur cette solution.
Nous allons nous concentrer ici sur le protocole Pinocchio de Parno, Gentry, Howell et Raykova publié en 2013 (souvent appelé PGHR13) ; il existe quelques variations du mécanisme de base, donc les schémas zk-SNARK effectivement implémentés peuvent différer légèrement, mais les principes fondamentaux restent généralement les mêmes.
Commençons par une hypothèse clé : l'hypothèse de connaissance de l'exposant (KEA). Nous aurons besoin de cette hypothèse pour expliquer le mécanisme de sécurité sous-jacent.
KEA1 : Pour tout adversaire A recevant en entrée q, g, g^a, puis retournant un couple (C, Y) tel que Y = C^a, il existe nécessairement un « extracteur » A', qui, avec les mêmes entrées que A, peut retourner c tel que g^c = C.
Cette hypothèse signifie essentiellement que si vous obtenez une paire de points P et Q tels que P * k = Q, et que vous obtenez un point C, alors il est impossible de produire le point correspondant C * k sauf si C est « dérivé » de P d'une certaine manière. Cela peut sembler évident, mais cette hypothèse ne découle en réalité d'aucune autre hypothèse classique utilisée pour prouver la sécurité des protocoles sur courbes elliptiques (comme le problème du logarithme discret), ce qui signifie que la sécurité des zk-SNARKs repose sur une hypothèse légèrement plus faible que celle de la cryptographie sur courbes elliptiques — bien qu'elle reste suffisamment solide pour que la plupart des cryptographes l'acceptent.
Voyons maintenant comment l'utiliser. Supposons que tombe du ciel une paire de points (P, Q) telle que P * k = Q, mais que personne ne connaisse la valeur de k. Supposons ensuite que je produise une paire de points (R, S) telle que R * k = S. Alors, selon l'hypothèse KEA, la seule façon dont j'ai pu obtenir cette paire est d'avoir multiplié P et Q par un certain facteur r que je connais. Remarquez aussi que grâce aux propriétés extraordinaires des appariements de courbes elliptiques, on peut vérifier que R * k = S sans connaître k — il suffit simplement de vérifier que e(R, Q) = e(P, S).
Faisons quelque chose de plus intéressant. Supposons que dix paires de points tombent du ciel : (P₁, Q₁), (P₂, Q₂), ..., (P₁₀, Q₁₀), toutes satisfaisant Pᵢ * k = Qᵢ. Supposons que je vous donne ensuite une paire (R, S) telle que R * k = S. Que savez-vous alors ? Vous savez que R est une combinaison linéaire de la forme P₁·i₁ + P₂·i₂ + ... + P₁₀·i₁₀, et que je connais les coefficients i₁, i₂, ..., i₁₀. Autrement dit, la seule façon d'obtenir une telle paire (R, S) est de prendre des multiples des P₁, P₂, ..., P₁₀, de les additionner, et d'effectuer le même calcul sur les Q₁, Q₂, ..., Q₁₀.
Remarquez que, pour toute combinaison linéaire particulière que vous souhaiteriez vérifier sur les points P₁...P₁₀, vous ne pouvez pas créer les points Q₁...Q₁₀ associés sans connaître k. Et si vous connaissez k, alors vous pouvez créer une paire (R, S) telle que R * k = S pour n'importe quel R désiré, sans passer par une combinaison linéaire. Par conséquent, la personne ayant créé ces points doit être digne de confiance, et une fois les dix points créés, la valeur de k doit être définitivement effacée. C’est là que provient le concept de « configuration de confiance » (trusted setup) (note du traducteur : la configuration de confiance désigne une opération ponctuelle au démarrage d’un système zkSNARK, qui n’a besoin d’être effectuée qu’une seule fois).
Rappelons qu’une solution à un QAP est un ensemble de polynômes (A, B, C) tels que A(x) * B(x) - C(x) = H(x) * Z(x), où :
A est une combinaison linéaire d'un ensemble de polynômes {A₁, ..., Aₘ}
B est la combinaison linéaire des {B₁, ..., Bₘ} avec les mêmes coefficients
C est la combinaison linéaire des {C₁, ..., Cₘ} avec les mêmes coefficients
Les ensembles {A₁, ..., Aₘ}, {B₁, ..., Bₘ}, {C₁, ..., Cₘ} et le polynôme Z font partie de l'énoncé du problème.
Toutefois, dans la plupart des cas réels, A, B et C sont extrêmement grands ; pour des fonctions comme les hachages, qui comportent des milliers de portes logiques, les polynômes (ainsi que les coefficients de combinaison linéaire) peuvent contenir des milliers de termes. Plutôt que de demander au prouveur de fournir directement la combinaison linéaire, nous utilisons la technique décrite ci-dessus pour prouver que ce qu’il fournit est bien une combinaison linéaire, sans rien révéler d’autre.
Vous avez peut-être remarqué que la technique décrite s’applique aux points de courbes elliptiques, pas aux polynômes. En pratique, nous ajoutons donc les valeurs suivantes à la configuration de confiance :
G * A₁(t), G * A₁(t) * k_a
G * A₂(t), G * A₂(t) * k_a
...
G * B₁(t), G * B₁(t) * k_b
G * B₂(t), G * B₂(t) * k_b
...
G * C₁(t), G * C₁(t) * k_c
G * C₂(t), G * C₂(t) * k_c
...
Vous pouvez considérer t comme le « point secret » où les polynômes sont évalués. G est un « générateur » (un point aléatoire fixé sur la courbe elliptique, intégré au protocole), tandis que t, k_a, k_b et k_c sont des « déchets toxiques », des nombres qui doivent être effacés à tout prix, car quiconque les possède pourrait fabriquer de faux témoignages. À présent, si quelqu’un vous fournit une paire (P, Q) telle que P * k_a = Q (rappel : nous n’avons pas besoin de connaître k_a pour vérifier cela, grâce aux tests d’appariement), alors vous savez qu’il s’agit d’une combinaison linéaire des polynômes Aᵢ évalués en t.
Jusqu’ici, le prouveur doit donc fournir :
π_a = G * A(t), π'_a = G * A(t) * k_a
π_b = G * B(t), π'_b = G * B(t) * k_b
π_c = G * C(t), π'_c = G * C(t) * k_c
Notez que le prouveur n’a pas besoin de connaître (et ne devrait surtout pas connaître !) t, k_a, k_b ou k_c pour calculer ces valeurs ; il devrait pouvoir les déduire uniquement à partir des points ajoutés à la configuration de confiance.
L’étape suivante consiste à s’assurer que les trois combinaisons linéaires ont les mêmes coefficients. Nous pouvons y parvenir en ajoutant un autre ensemble de valeurs à la configuration de confiance : G * (Aᵢ(t) + Bᵢ(t) + Cᵢ(t)) * b, où b est un autre nombre considéré comme « déchet toxique » et qui doit être supprimé après la fin de la configuration. Le prouveur peut alors créer une combinaison linéaire de ces valeurs avec les mêmes coefficients, et utiliser la même technique d’appariement pour vérifier que cette valeur correspond bien à A + B + C fourni.
Enfin, nous devons prouver que A * B - C = H * Z. Nous utilisons à nouveau un test d’appariement :
e(π_a, π_b) / e(π_c, G) ?= e(π_h, G * Z(t))
où π_h = G * H(t). Si vous ne voyez pas le lien entre cette équation et A * B - C = H * Z, revenez lire l'article sur les appariements.
Nous avons vu ci-dessus comment convertir A, B et C en points sur une courbe elliptique ; G est simplement le générateur (c’est-à-dire que le point G sur la courbe elliptique joue le rôle du nombre 1). Nous pouvons ajouter G * Z(t) à la configuration de confiance. Calculer H est plus difficile ; H est juste un polynôme, et pour chaque solution à un QAP, ses coefficients sont impossibles à prévoir à l’avance. Nous devons donc ajouter davantage de données à la configuration de confiance ; en particulier la séquence suivante :
G, G * t, G * t², G * t³, G * t⁴, ...
Dans la configuration de confiance de Zcash, cette séquence contient environ 2 millions d’éléments ; imaginez la puissance de calcul nécessaire pour garantir que vous pouvez calculer H(t). Cela permet au prouveur de fournir au vérificateur toutes les informations nécessaires à la vérification finale.
Il reste un dernier détail à aborder. La plupart du temps, nous ne voulons pas simplement prouver abstraitement qu’une solution existe pour un problème donné ; nous voulons souvent prouver la validité d’une solution spécifique (par exemple, prouver que si le mot « cow » est haché un million de fois avec SHA3, le résultat commence par 0x73064fe5), ou qu’une solution existe sous certaines contraintes. Par exemple, dans une mise en œuvre monétaire, les montants des transactions et les soldes des comptes sont chiffrés, et vous devez prouver que vous connaissez une clé de déchiffrement k telle que :
decrypt(old_balance, k) ≥ decrypt(tx_value, k)
decrypt(old_balance, k) - decrypt(tx_value, k) = decrypt(new_balance, k)
Les valeurs old_balance, tx_value et new_balance chiffrées doivent être publiques, car ce sont les valeurs concrètes que nous observons à un moment donné ; seule la clé de déchiffrement doit rester secrète. Des modifications mineures du protocole permettent de créer une « clé de vérification personnalisée », correspondant à certaines contraintes spécifiques sur les entrées.
Faisons maintenant un pas en arrière. Voici l'algorithme complet de vérification, fourni par Ben Sasson, Tromer, Virza et Chiesa :
La première ligne traite la paramétrisation ; en substance, vous pouvez voir cela comme la création d'une « clé de vérification personnalisée » pour une instance spécifique du problème avec certains paramètres fixés. La deuxième ligne vérifie les combinaisons linéaires de A, B et C ; la troisième vérifie que les combinaisons linéaires ont les mêmes coefficients ; la quatrième vérifie que A * B - C = H * Z.
En résumé, le processus de vérification comprend quelques multiplications sur courbe elliptique (une par variable d'entrée « publique ») et cinq vérifications d'appariement, dont une inclut une multiplication supplémentaire. La preuve fournie contient huit points sur des courbes elliptiques : un point chacun pour A(t), B(t) et C(t), un point pour b*(A(t)+B(t)+C(t)) noté π_k, et un point pour H(t) noté π_h. Sept de ces points sont sur la courbe F_p (32 octets chacun, car la coordonnée y peut être compressée en 1 bit), et dans l'implémentation de Zcash, un autre point (π_b) est sur la courbe tordue F_p² (64 octets), ce qui donne une taille totale d'environ 288 octets.
Les deux parties les plus coûteuses en calcul pour générer une preuve sont :
- Calculer (A * B - C) / Z pour obtenir H (des algorithmes basés sur la transformée de Fourier rapide peuvent faire cela en temps sous-quadratique, mais c'est encore très lourd)
- Effectuer les multiplications et additions sur courbe elliptique pour construire les valeurs A(t), B(t), C(t), H(t) et leurs points appariés
Générer une preuve est difficile parce que, dans une preuve à divulgation nulle de connaissance, chaque porte logique binaire du calcul initial doit être transformée en opérations cryptographiques via des courbes elliptiques. Ce fait, combiné à la complexité super-linéaire de la transformée de Fourier rapide, fait que générer une preuve pour une transaction Zcash prend environ 20 à 40 secondes.
Une autre question très importante est : peut-on rendre la configuration de confiance un peu moins... dépendante de la confiance ? Malheureusement, nous ne pouvons pas l’éliminer complètement ; l’hypothèse KEA exclut justement la possibilité de former des paires indépendantes (Pᵢ, Pᵢ * k) sans connaître k. Toutefois, nous pouvons améliorer grandement la sécurité en utilisant un calcul multipartite N-sur-N — c’est-à-dire concevoir la configuration de confiance comme une collaboration entre N participants, où tant qu’au moins un participant a bien supprimé ses « déchets toxiques », tout va bien.
Pour vous donner une idée de la manière dont cela fonctionne, voici un algorithme simple permettant de prendre un ensemble existant (G, G * t, G * t², G * t³, ...) et d’y « intégrer » votre propre secret, de sorte que pour tricher, il faille connaître à la fois votre secret et l’ancien secret (ou l’ensemble des anciens secrets).
L’ensemble de sortie est simple :
G, (G * t) * s, (G * t²) * s², (G * t³) * s³, ...
Remarquez qu’à part le fait que t * s devient désormais le « déchet toxique » au lieu de t, vous pouvez recréer l’ensemble entier à partir de l’ancien ensemble et de s, et le nouvel ensemble a exactement les mêmes propriétés fonctionnelles que l’ancien. Tant que ni vous ni ceux qui ont créé l’ensemble précédent n’avez conservé vos déchets toxiques, et que vous ne collaborez pas plus tard, le groupe est « sécurisé ».
Appliquer cela à une configuration complète est beaucoup plus difficile, car plusieurs valeurs sont en jeu, et l’algorithme nécessite plusieurs tours entre les participants. C’est un domaine de recherche active : simplifier davantage les algorithmes de calcul multipartite, réduire le nombre de tours ou augmenter le parallélisme, afin que davantage de personnes puissent participer à la configuration. Il est facile de comprendre pourquoi une configuration à six participants pourrait inquiéter certains, mais une configuration avec des milliers de participants est presque équivalente à une absence totale de confiance — si vous êtes vraiment paranoïaque, vous pouvez même y participer vous-même, et vous assurer personnellement que vous avez bien supprimé vos déchets toxiques.
Un autre domaine de recherche actif consiste à atteindre les mêmes objectifs sans utiliser d’appariements ni de configuration de confiance. Consultez la récente présentation d’Eli Ben Sasson (attention : elle est mathématiquement complexe, au moins autant que les SNARKs !).
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
