Rejoignez-Nous sur

Comprendre PLONK

Tradeoffs

News

Comprendre PLONK

Un merci spécial à Justin Drake, Karl Floersch, Hsiao-wei Wang, Barry Whitehat, Dankrad Feist et Zac Williamson pour leur examen

Très récemment, Ariel Gabizon, Zac Williamson et Oana Ciobotaru ont annoncé un nouveau schéma de preuve à utilisation zéro, à usage général, appelé PINARD, signifiant le quasi-backronyme fastidieux «Permutations sur les bases de Lagrange pour des arguments œcuméniques non interactifs de la connaissance». Tandis que des améliorations à usage général preuve de la connaissance zéro les protocoles ont été venant pour années, que PLONK (et le plus ancien mais plus complexe SONIQUE et le plus récent Marlin) apporte une série d’améliorations susceptibles d’améliorer considérablement la convivialité et les progrès de ce type de preuves en général.

La première amélioration est que, bien que PLONK nécessite toujours une procédure d’installation sécurisée similaire à celle requise pour la SNARK à Zcash, il s’agit d’une configuration sécurisée «universelle et modifiable». Cela signifie deux choses: tout d’abord, au lieu d’avoir une configuration sécurisée distincte pour chaque programme pour lequel vous voulez prouver quoi que ce soit, il existe une seule configuration sécurisée pour le schéma complet, après quoi vous pouvez utiliser le schéma avec n’importe quel programme (jusqu’à une valeur maximale). taille choisie lors de la configuration). Deuxièmement, il existe un moyen pour plusieurs parties de participer à la configuration sécurisée de manière à ce qu'elle soit sécurisée tant que l'une d'entre elles est honnête, et cette procédure multipartite est entièrement séquentielle: une première personne participe, puis la seconde, puis le troisième… L’ensemble des participants n’a même pas besoin d’être connu à l’avance; les nouveaux participants pourraient simplement s’ajouter à la fin. Cela permet à la configuration sécurisée d’avoir un grand nombre de participants, ce qui la rend très sûre dans la pratique.

La deuxième amélioration est que la «cryptographie de fantaisie» sur laquelle il s'appuie est un composant normalisé unique, appelé «engagement polynomial». PLONK utilise des «engagements de Kate», basés sur une configuration de confiance et des appariements de courbes elliptiques, mais vous pouvez le remplacer par d'autres schémas, tels que VEN (qui ferait transformez PLONK en une sorte de STARK) ou DARK (basé sur des groupes d’ordre caché). Cela signifie que le schéma est théoriquement compatible avec tout compromis (réalisable) entre la taille de la preuve et les hypothèses de sécurité.


Tradeoffs

Cela signifie que les cas d'utilisation qui nécessitent des compromis différents entre la taille de la preuve et les hypothèses de sécurité (ou les développeurs qui ont des positions idéologiques différentes sur cette question) peuvent toujours partager l'essentiel du même outil pour «l'arithmétisation» – le processus de conversion d'un programme en. un ensemble d'équations polynomiales que les engagements polynpomiaux sont ensuite utilisés pour vérifier. Si ce type de système est adopté à grande échelle, nous pouvons donc nous attendre à des progrès rapides dans l’amélioration des techniques de calcul commun.

Comment fonctionne PLONK

Commençons par une explication du fonctionnement de PLONK, dans un format quelque peu abstrait qui se concentre sur les équations polynomiales sans expliquer immédiatement comment ces équations sont vérifiées. Un ingrédient clé de PLONK, comme c'est le cas dans le QAP utilisés dans les SNARK, est une procédure pour convertir un problème de la forme “donnez-moi une valeur X tel qu'un programme spécifique P que je vous donne, lorsque évalué avec X en entrée, donne un résultat spécifique Y”Dans le problème“ donne-moi un ensemble de valeurs qui satisfasse à un ensemble d'équations mathématiques ”. Le programme P peut représenter beaucoup de choses; par exemple, le problème pourrait être «donnez-moi une solution à ce sudoku», que vous encoderiez en définissant P être un vérificateur de sudoku plus quelques valeurs initiales codées et paramétrées Y à 1 (c.-à-d. «oui, cette solution est correcte»), et une contribution satisfaisante X serait une solution valable pour le sudoku. Ceci est fait en représentant P en tant que circuit avec des portes logiques pour addition et multiplication, et le convertir en un système d'équations dans lequel les variables sont les valeurs de tous les fils et il existe une équation par porte (par exemple. x6 = x4 * x7 pour la multiplication, x8 = x5 + x9 pour addition).

Voici un exemple du problème de trouver x tel que P(x) = x**3 + x + 5 = 35 (allusion: x = 3):


Circuit

Nous pouvons étiqueter les portes et les fils comme suit:


Circuit2

Sur les portes et les fils, nous avons deux types de contraintes: contraintes de porte (équations entre des fils reliés à la même porte, par exemple. a1 * b1 = c1) et contraintes de copie (revendications concernant l’égalité des différents fils n'importe où dans le circuit, par exemple. a0 = a1 = b1 = b2 = a3 ou c0 = a1). Nous devrons créer un système d'équations structuré, qui réduira finalement à un très petit nombre d'équations polynomiales, pour représenter les deux.

Dans PLONK, la configuration de ces équations est la suivante. Chaque équation est de la forme suivante (pensez: L = gauche, R = droite, O = sortie, M = multiplication, C = constante):


eq0v2

Chaque Q la valeur est une constante; les constantes dans chaque équation (et le nombre d'équations) seront différentes pour chaque programme. Chaque valeur de petite lettre est une variable fournie par l'utilisateur: aje est le fil d’entrée gauche de la iième porte, bje est le bon fil d’entrée, et cje est le fil de sortie de la iième porte. Pour une porte d'addition, nous définissons:


eq1

Brancher ces constantes dans l’équation et simplifier nous donne une idéeje + bje – oje = 0, qui est exactement la contrainte que nous voulons. Pour une porte de multiplication, nous définissons:


eq3

Pour un réglage constant de la porte aje à une constante x, nous fixons:


eq3p5

Vous avez peut-être remarqué que chaque extrémité d'un fil, ainsi que chaque fil d'un ensemble de fils, doit clairement avoir la même valeur (par exemple, x), correspond à une variable distincte; rien jusqu’à présent n’a forcé la sortie d’une porte à être identique à l’entrée d’une autre porte (ce que nous appelons des «contraintes de copie»). PLONK a bien sûr un moyen de faire respecter les contraintes de copie, mais nous y reviendrons plus tard. Alors maintenant, nous avons un problème où un prouveur veut prouver qu'il a un tas de xuneje, Xbje et xcje valeurs qui satisfont un tas d'équations qui sont de la même forme. C’est toujours un gros problème, mais contrairement à «Trouver une entrée satisfaisante pour ce programme informatique», c’est un très structuré gros problème, et nous avons des outils mathématiques pour le «compresser».

Des systèmes linéaires aux polynômes

Si vous avez lu STARK ou PAQSi tout va bien, le mécanisme décrit dans la section suivante vous semblera quelque peu familier, mais si vous ne l’avez pas fait, cela vous convient également. L’ingrédient principal ici est de comprendre un polynôme comme un outil mathématique pour encapsuler un tas de valeurs dans un seul objet. Typiquement, nous pensons aux polynômes sous forme de «coefficient», c'est-à-dire une expression comme:


eq4

Mais nous pouvons également afficher les polynômes dans le «formulaire d'évaluation». Par exemple, on peut penser à ce qui précède comme étant «le» polynôme de degré <4 avec évaluations (-2, 1, 0, 1) aux coordonnées (0, 1, 2, 3) respectivement.


polynomial graph

Maintenant, voici la prochaine étape. Les systèmes de nombreuses équations de la même forme peuvent être réinterprétés comme une seule équation sur des polynômes. Par exemple, supposons que nous ayons le système:


eq5

Définissons quatre polynômes sous forme d’évaluation: L(x) est le degré <3 polynôme qui évalue à (2, 1, 8) aux coordonnées (0, 1, 2)et à ces mêmes coordonnées M(x) évalue à (-1, 4, -1), R(w) à (3, -5, -1) et O(x) à (8, 5, -2) (vous pouvez définir directement les polynômes de cette manière; vous pouvez utiliser Interpolation de Lagrange convertir en forme de coefficient). Maintenant, considérons l'équation:


eq6v2

Ici, Z(x) est un raccourci pour (x-0) * (x-1) * (x-2) – le polynôme minimal (non trivial) qui renvoie zéro dans le domaine d'évaluation (0, 1, 2). Une solution à cette équation (x1 = 1, x2 = 6, x3 = 4, H(x) = 0) est également une solution au système d'équations d'origine, sauf que le système d'origine n'a pas besoin H(x). Notez également que dans ce cas, H(x) est commodément nul, mais dans des cas plus complexes H peut avoir besoin d'être différent de zéro.

Nous savons maintenant que nous pouvons représenter un grand ensemble de contraintes dans un petit nombre d'objets mathématiques (les polynômes). Mais dans les équations que nous avons faites ci-dessus pour représenter les contraintes du fil de grille, le x1, X2, X3 les variables sont différentes par équation. Nous pouvons gérer cela en transformant les variables elles-mêmes en polynômes plutôt qu'en constantes de la même manière. Et nous obtenons:


eq7v2

Comme avant, chacun Q Le polynôme est un paramètre qui peut être généré à partir du programme en cours de vérification, et le a, b, c Les polynômes sont les entrées fournies par l'utilisateur.

Copier les contraintes

Revenons maintenant à la «connexion» des fils. Jusqu'ici, tout ce que nous avons, c'est un ensemble d'équations disjointes sur les valeurs disjointes qui sont indépendamment faciles à satisfaire: les portes constantes peuvent être satisfaites en définissant la valeur à la constante et les portes d'addition et de multiplication peuvent simplement être satisfaites en réglant tous les fils à zéro! Pour rendre le problème réellement problématique (et représenter réellement le problème encodé dans le circuit d'origine), nous devons ajouter une équation qui vérifie les «contraintes de copie»: contraintes telles que a(5) = c(7), c(10) = c(12), etc. Cela nécessite une ruse astucieuse.

Notre stratégie consistera à concevoir un «accumulateur de paires de coordonnées», un polynôme p(x) qui fonctionne comme suit. Tout d'abord, laissez X(x) et Y(x) être deux polynômes représentant le x et y les coordonnées d'un ensemble de points (par exemple, pour représenter l'ensemble ((0, -2), (1, 1), (2, 0), (3, 1)) vous pouvez définir X (x) = x et Y (x) = x3 – 5x2 + 7x – 2). Notre objectif sera de laisser p(x) représente tous les points jusqu’à la position donnée (mais non comprise), p(0) commence à 1, p(1) ne représente que le premier point, p(2) le premier et le second, etc. Nous le ferons en sélectionnant «au hasard» deux constantes, v1 et v2et la construction p(x) en utilisant les contraintes p(0) = 1 et p(x+1) = p(x) * (v1 + X(x) + v2 * Y(x)) au moins dans le domaine (0, 1, 2, 3). Par exemple, laisser v1 = 3 et v2 = 2, on a:


polynomial graph3

X (x)01234
Y (x)-2121
v1 + x (x) + v2 * y (x)-1658
p (x)1-1-6-30-240

Notez que (à part la première colonne), chaque valeur de p (x) est égale à la valeur à gauche multipliée par la valeur à gauche et au-dessus de celle-ci.

Le résultat qui nous intéresse est p(4) = -240. Considérons maintenant le cas où, au lieu de X (x) = x, définissons X (x) = 2/3 X3 – 4x2 + 19/3 x (c’est-à-dire le polynôme qui évalue à (0, 3, 2, 1) aux coordonnées (0, 1, 2, 3)). Si vous exécutez la même procédure, vous constaterez que vous obtenez également p(4) = -240. Ce n'est pas une coïncidence (en fait, si vous choisissez au hasard v1 et v2 d'un champ suffisamment grand, il sera presque jamais arriver par hasard). Cela se produit plutôt parce que Y(1) = Y(3)Donc, si vous échangez les coordonnées X des points (1, 1) et (3, 1) vous ne changez pas le ensemble de points, et parce que l’accumulateur code un ensemble (la multiplication ne se souciant pas de l’ordre), la valeur à la fin sera la même.

Nous pouvons maintenant commencer à voir la technique de base que nous allons utiliser pour prouver les contraintes de copie. Premièrement, considérons le cas simple où nous souhaitons prouver uniquement les contraintes de copie dans un ensemble de fils (par exemple, nous voulons prouver a(1) = a(3)). Nous allons faire deux accumulateurs de coordonnées: un où X (x) = x et Y (x) = un (x), et l'autre où Y (x) = un (x) mais X '(x) est le polynôme qui évalue à la permutation qui retourne (ou réorganise autrement) les valeurs dans chaque contrainte de copie; dans le a(1) = a(3) cas cela signifierait que la permutation commencerait 0 3 2 1 4.... Le premier accumulateur serait compresser ((0, a(0)), (1, a(1)), (2, a(2)), (3, a(3)), (4, a(4))..., la deuxième ((0, a(0)), (3, a(1)), (2, a(2)), (1, a(3)), (4, a(4)).... La seule façon dont les deux peuvent donner le même résultat est si a(1) = a(3).

Prouver les contraintes entre a, b et c, nous utilisons la même procédure, mais nous «accumulons» ensemble des points des trois polynômes. Nous assignons chacun de a, b, c une plage de coordonnées X (par exemple. a obtient Xune(x) = x ie. 0...n-1, b obtient Xb(x) = n + x, c'est-à-dire. n...2n-1, c obtient Xc(x) = 2n + x, c'est-à-dire. 2n...3n-1. Pour prouver les contraintes de copie qui sautent entre différents jeux de fils, les coordonnées X «alternatives» seraient des coupes d'une permutation entre les trois jeux. Par exemple, si on veut prouver a(2) = b(4) avec n = 5puis X ’une(x) aurait des évaluations 0 1 9 3 4 et X ’b(x) aurait des évaluations 5 6 7 8 2 (notez les 2 et 9 retournés, où 9 correspond au b4 câble).

Au lieu de vérifier l’égalité au sein d’un cycle de la procédure (c’est-à-dire en vérifiant p (4) = p ’(4) comme auparavant), nous vérifions le produit des trois parcours différents de chaque côté:


eq6p5

Le produit des trois évaluations p (n) de chaque côté s'accumule tout paires de coordonnées dans le a, b et c fonctionne de part et d’autre, ce qui nous permet de procéder au même contrôle qu’auparavant, sauf que nous pouvons maintenant vérifier les contraintes de copie non seulement entre les positions à l’intérieur de a, b ou c, mais aussi entre les jeux de fils (par exemple, comme dans a(2) = b(4)).

Et c’est tout ce qu’il ya à faire!

Mettre tous ensemble

En réalité, tout ce calcul est fait non pas sur des entiers, mais sur un corps premier; consultez la section «Un interlude mathématique modulaire» ici pour une description de ce que sont les champs principaux. En outre, pour des raisons mathématiques, il serait peut-être préférable de lire et de comprendre cet article sur la mise en œuvre de la FFT, au lieu de représenter des indices de fils avec x=0....n-1, nous utiliserons les pouvoirs de ω: 1, ω, ω2… .Ωn-1 où ω est une racine d'unité de haut niveau sur le terrain. Cela ne change rien au calcul, sauf que l'équation de vérification de contrainte d'accumulateur de paires de coordonnées change de p(x + 1) = p(x) * (v1 + X(x) + v2 * Y(x)) à p(ω * x) = p(x) * (v1 + X(x) + v2 * Y(x))et au lieu d'utiliser 0..n-1, n..2n-1, 2n..3n-1 comme coordonnées nous utilisonsje, g *je et g2 *jeg peut être un élément aléatoire d'ordre élevé sur le terrain.

Maintenant, écrivons toutes les équations que nous devons vérifier. Premièrement, le contrôle de satisfaction principal de la contrainte de porte:


eq7v2

Ensuite, la contrainte de transition d'accumulateur polynomial (note: pensez à «= Z (x) * H (x)» comme signifiant «est égal à zéro pour toutes les coordonnées dans un domaine particulier qui nous tient à cœur, mais pas nécessairement en dehors de celui-ci»):


eq8v2

Ensuite, les contraintes de début et de fin de l'accumulateur polynomial:


eq9v2

Les polynômes fournis par l'utilisateur sont:

  • Les assignations de fils a (x), b (x), c (x)
  • Les accumulateurs de coordonnées Pune(x), Pb(x), Pc(x), Pune'(x), Pb ’(x), Pc ’(X)
  • Les quotients H (x) et H1(x)… H6(X)

Les polynômes spécifiques au programme que le vérificateur et le vérificateur doivent calculer à l'avance sont les suivants:

  • QL(x), QR(x), QO(x), QM(x), QC(x), qui représentent ensemble les portes du circuit (notez que QC(x) code les entrées publiques, il peut donc être nécessaire de le calculer ou de le modifier au moment de l'exécution)
  • Les «polynômes de permutation» σune(x), σb(x) et σc(x), qui codent les contraintes de copie entre les a, b et c fils

Notez que le vérificateur n'a besoin que de stocker des engagements pour ces polynômes. Le seul polynôme restant dans les équations ci-dessus est Z (x) = (x – 1) * (x – ω) *… * (x –n-1) qui est conçu pour évaluer à zéro à tous ces points. Heureusement, ω peut être choisi pour rendre ce polynôme très facile à évaluer: la technique habituelle consiste à choisir pour satisfairen = 1, auquel cas Z (x) = ωn – 1.

La seule contrainte sur v1 et v2 est que l'utilisateur ne doit pas pouvoir choisir a (x), b (x) ou c (x) après v1 et v2 devenir connu, afin que nous puissions satisfaire cela en calculant v1 et v2 des hachages d'engagements à a (x), b (x) et c (x).

Nous avons donc transformé le problème de la satisfaction du programme en un simple problème de résolution de quelques équations avec des polynômes, et PLONK offre certaines optimisations qui nous permettent de supprimer de nombreux polynômes des équations ci-dessus dans lesquels je ne parlerai pas pour les préserver. simplicité. Mais les polynômes eux-mêmes, les paramètres spécifiques au programme et les entrées utilisateur, sont gros. La prochaine question est donc: comment pouvons-nous résoudre ce problème de manière à ce que la preuve soit courte?

Engagements polynomiaux

UNE engagement polynomial est un objet court qui "représente" un polynôme et vous permet de vérifier les évaluations de ce polynôme sans avoir à réellement contenir toutes les données qu'il contient. C'est-à-dire si quelqu'un vous engage c représentant P(x), ils peuvent vous donner une preuve qui peut vous convaincre, pour certains z, quelle est la valeur de P(z) est. Un autre résultat mathématique indique que, sur un champ suffisamment grand, si certains types d’équations (choisis avant z connu) sur les polynômes évalués aléatoirement z sont vraies, ces mêmes équations sont également vraies pour le polynôme tout entier. Par exemple, si P(z) * Q(z) + R(z) = S(z) + 5, alors nous savons qu’il est extrêmement probable que P(x) * Q(x) + R(x) = S(x) + 5 en général. En utilisant de tels engagements polynomiaux, nous pourrions très facilement vérifier toutes les équations polynomiales ci-dessus – prendre les engagements, les utiliser comme entrées pour générer z, prouver quelles sont les évaluations de chaque polynôme à z, puis exécutez les équations avec ces évaluations à la place des polynômes d’origine. Mais comment fonctionnent ces engagements?

Il y a deux parties: l'engagement envers le polynôme P(x) -> cet l'ouverture à une valeur P(z) chez certains z. Pour s’engager, il existe de nombreuses techniques; un exemple est VENet un autre est les engagements de Kate que je décrirai ci-dessous. Pour prouver une ouverture, il s’avère qu’il existe une astuce générique simple: «soustraire et diviser»: prouver que P(z) = a, tu le prouves


eq10

est également un polynôme (utilisant un autre engagement polynomial). Cela fonctionne parce que si le quotient est un polynôme (c’est-à-dire qu’il n’est pas fractionnaire), alors x - z est un facteur de P(x) - a, alors (P(x) - a)(z) = 0, alors P(z) = a. Essayez-le avec un polynôme, par exemple. P (x) = x3 + 2 * x2+5 avec (z = 6, a = 293), vous-même; et essayez (z = 6, a = 292) et voyez comment cela échoue (si vous êtes paresseux, consultez WolframAlpha ici contre ici). Notez également une optimisation générique: pour prouver plusieurs ouvertures de plusieurs polynômes à la fois, après avoir validé les sorties, faites le tour soustraction-division sur un combinaison linéaire aléatoire des polynômes et des sorties.

Alors, comment fonctionnent les engagements eux-mêmes? Les engagements de Kate sont, heureusement, beaucoup plus simples que FRI. Une procédure de configuration sécurisée génère un ensemble de points de courbe elliptiques G, G * s, G * s2 … G * sn, ainsi que G2 * s, où G et G2 sont les générateurs de deux groupes de courbes elliptiques et s est un secret qui est oublié une fois la procédure terminée (notez qu’il existe une version multipartite de cette configuration, qui est sécurisée tant qu’au moins un des participants oublie sa part du secret). Ces points sont publiés et considérés comme «la clé de preuve» du schéma; quiconque ayant besoin d'un engagement polynomial devra utiliser ces points. Un engagement envers un polynôme degré-d est obtenu en multipliant chacun des premiers d + 1 points de la clé de preuve par le coefficient correspondant dans le polynôme et en additionnant les résultats.

Notez que cela fournit une «évaluation» de ce polynôme au s, sans savoir s. Par exemple, x3 + 2x2+5 serait représenté par (G * s3) + 2 * (G * s2) + 5 * G. On peut utiliser la notation (P) se référer à P codé de cette manière (ie. G * P(s)). En faisant le tour soustraction-division, vous pouvez prouver que les deux polynômes satisfont réellement la relation en utilisant appariements de courbes elliptiques: regarde ça e((P) - G * a, G2) = e((Q), (x) - G2 * z) comme proxy pour vérifier que P(x) - a = Q(x) * (x - z).

Mais plus récemment, d'autres types d'engagements polynomiaux ont également été annoncés. Un nouveau schéma appelé DARK («Arguments de la connaissance diophantiens») utilise des «groupes d’ordre cachés» tels que groupes de classe mettre en œuvre un autre type d'engagement polynomial. Les groupes d’ordre masqués sont uniques car ils vous permettent de compresser des nombres arbitrairement grands en éléments de groupe, même des nombres beaucoup plus grands que la taille de l’élément de groupe, d’une manière qui ne peut pas être «usurpée»; constructions de VDF à accumulateurs il est possible de construire en plus des preuves aux engagements polynomiaux. Une autre option consiste à utiliser des pare-balles, en utilisant des groupes de courbes elliptiques classiques, mais la vérification prend beaucoup plus de temps. Étant donné que les engagements polynomiaux sont beaucoup plus simples que les systèmes à preuve absolue de connaissances, nous pouvons nous attendre à ce que davantage de systèmes de ce type soient créés à l'avenir.

résumer

Pour terminer, revoyons le schéma. Étant donné un programme P, vous le convertissez en circuit et générez un ensemble d’équations ressemblant à ceci:


eq0v2

Vous convertissez ensuite cet ensemble d'équations en une seule équation polynomiale:


eq7v2

Vous générez également à partir du circuit une liste de contraintes de copie. À partir de ces contraintes de copie, vous générez les trois polynômes représentant les indices de fil permutés: σune(x), σb(x), σc(X). Pour générer une preuve, calculez les valeurs de tous les fils et convertissez-les en trois polynômes: a (x), b (x), c (x). Vous calculez également six polynômes «accumulateur de paire de coordonnées» dans le cadre de l'argument de contrôle de permutation. Enfin, vous calculez les cofacteurs Hje(X).

Il existe un ensemble d'équations entre les polynômes à vérifier; vous pouvez le faire en prenant des engagements envers les polynômes, en les ouvrant au hasard z (avec des preuves que les ouvertures sont correctes), et exécuter les équations sur ces évaluations à la place des polynômes d'origine. La preuve elle-même ne représente que quelques engagements et ouvertures et peut être vérifiée à l'aide de quelques équations. Et c’est tout ce qu’il ya à faire!



Traduction de l’article de : Article Original

BlockBlog

Le Meilleur de l'Actualité Blockchain Francophone & Internationale | News, Guides, Avis & Tutoriels pour s'informer et démarrer facilement avec Bitcoin, les Crypto-Monnaies et le Blockchain. En Savoir Plus sur L'Équipe BlockBlog

Commenter cet Article

Commenter cet Article

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Plus dans News

Les Plus Populaires

Acheter des Bitcoin

Acheter des Alt-Coins

Sécuriser vos Cryptos

Vêtements et Produits Dérivés

Top