Initialement publiéen anglais par StarkWare le 17 Juillet, 2019. Part 3 sur 4
Veuillez noter que cet article contient de nombreuses notations mathématiques. Comme tous les téléphones mobiles ne les prennent pas entièrement en charge, nous vous recommandons de le lire sur un ordinateur.
Introduction
Voici la troisième partie de notre plongée en profondeur dans StarkDEX, où nous décrivons le système de preuve générique STARK, dont l'implémentation de StarkDEX est une instance. Si vous ne l'avez pas encore fait et que vous souhaitez comprendre l'ensemble du système StarkDEX, nous vous recommandons de lire les parties 1 et 2, mais vous pouvez également lire cet article. Nous vous recommandons également de lire notre série STARK Math pour une discussion plus approfondie des constructions mathématiques nécessaires à la compréhension de cet article.
Dans cet article, nous décrivons le système de preuve STARK comme un protocole interactif entre deux parties, le prouveur et le vérifieur Le prouveur envoie une série de messages pour tenter de convaincre le vérifeur qu'un certain calcul sur une entrée donnée a été effectué correctement (l'énoncé prouvé). Le vérifieur répond aux messages par des valeurs aléatoires. Finalement, le vérifieur accepte la preuve si le calcul a été effectué correctement, ou la rejette (avec une forte probabilité) si ce n'est pas le cas.
Bien que nous décrivions le système comme un protocole interactif, il est à noter que dans la version Alpha de StarkDEX, cette interactivité est finalement remplacée par une transformation en un système non interactif dans lequel le prouveur fournit une preuve et le vérifieur décide de l'accepter ou de la rejeter.
Systèmes de preuve STARK
Si vous souhaitez rafraîchir votre compréhension des traces d'exécution et des contraintes polynomiales, jetez un coup d'œil à nos articles Arithmétisation I & II de la série Stark Math.
La trace
(ndlr: dans le sens informatique)
La trace d'exécution d'un calcul, ou trace en abrégé, est une séquence d'états de la machine, un par cycle d'horodatage. Si le calcul nécessite w registres et dure N cycles, la trace d'exécution peut être représentée par un tableau de taille N x w. Étant donné une déclaration concernant l'exactitude d'un calcul, le vérifieur calcule d'abord l’origine.
On désigne les colonnes de la trace par f₁, f₂,..., fs. Chaque fⱼ est de longueur N=2ⁿ, pour un certain n fixé. Les valeurs dans les cellules de la trace sont des éléments dans un grand champ F. Dans notre version Alpha, F est un champ premier de 252 bits. Le domaine d'évaluation de la trace est défini comme , où g est un générateur dans un sous-groupe du groupe multiplicatif de F. En fait, nous énumérons les lignes de la trace par les éléments de . Chaque colonne de trace est interprétée comme N évaluations ponctuelles d'un polynôme de degré inférieur à N sur le domaine d'évaluation de la trace. Ces polynômes sont appelés polynômes de colonne de trace ou polynômes de colonne en bref. Trace Low Degree Extension & Commitment Comme nous l'avons mentionné plus haut, chaque colonne de trace est considérée comme N évaluations d'un polynôme de degré inférieur à N. Afin d'obtenir un protocole sécurisé, chacun de ces polynômes est évalué sur un domaine plus large, que nous appelons le domaine d'évaluation. Par exemple, dans notre StarkDEX Alpha, la taille du domaine d'évaluation est généralement de 16*N. Nous désignons cette évaluation sous le nom de trace Low Degree Extension (LDE) et le rapport entre la taille du domaine d'évaluation et le domaine de la trace sous le nom de blowup factor (ceux qui sont familiers avec la notation de la théorie des codes remarqueront que le blowup factor est 1/rate et que la LDE est en fait simplement un code Reed-Solomon de la trace). Après la génération de la trace LDE, le prouveur s'engage sur celle-ci. Dans tout le système, les engagements sont mis en œuvre en construisant un arbre de Merkle sur la série d'éléments de champ et en envoyant la racine de Merkle au vérifieur. Cette dernière implique quelques considérations techniques concernant la sérialisation des éléments de champ et la sélection de la fonction de hachage, ignorées ici pour des raisons de clarté. Les feuilles de l'arbre de Merkle sont sélectionnées de telle sorte que si un désengagement est susceptible d'impliquer plusieurs éléments de champ ensemble, ils sont regroupés dans une seule feuille de Merkle. Dans le cas de la trace LDE, cela implique que nous regroupons tous les éléments de champ dans la "ligne" de la trace LDE (l'évaluation de tous les polynômes de colonne à un point gⁱ) en une seule feuille de Merkle. Les contraintes Une trace d'exécution est valide si (1) certaines contraintes de limites sont respectées et (2) chaque paire d'états consécutifs satisfait aux contraintes dictées par le calcul. Par exemple, si à l'instant t le calcul doit additionner les contenus des 1er et 2ème registres et placer le résultat dans le 3ème registre, la contrainte pertinente serait Trace[t,1]+Trace[t,2]-Trace[t+1, 3] = 0. Les contraintes sont exprimées sous forme de polynômes composés sur les cellules de trace qui sont satisfaites si et seulement si le calcul est correct. On les appelle donc les contraintes polynomiales de la représentation intermédiaire algébrique (RIA) sur la trace. Par exemple, dans le contexte de la preuve de l'exécution correcte d'un lot de transactions dans un échange décentralisé (DEX), les contraintes sont telles qu'elles sont toutes satisfaites si et seulement si un lot de transactions est valide. Examinons quelques exemples de différentes contraintes sur les cellules de trace. f₂(x)-a = 0 pour x=g⁷ (la valeur dans la colonne 2 ligne g⁷ est égale à a). f₆²(x) -f₆(g³x) = 0 pour tout x (la valeur au carré de chaque ligne de la colonne 6 est égale à la valeur trois lignes plus loin). f₃(x) -f₄(gx) = 0 pour tous les x sauf g⁵ (la valeur de chaque ligne de la colonne 3 est égale à la valeur de la colonne 4 un rang avant, dans toutes les lignes sauf la ligne g⁵). f₂(x) -2*f₅(x) = 0 pour tout x dans une ligne impaire (la valeur de chaque ligne impaire dans la colonne 2 est égale à deux fois la valeur de la même ligne impaire dans la colonne 5). Rappelons que notre objectif est de prouver l'exactitude d'un calcul. En écrivant un ensemble de contraintes polynomiales qui sont satisfaites si et seulement si le calcul est valide, nous réduisons le problème original à prouver que les contraintes polynomiales sont satisfaites. Des contraintes polynomiales au problème de test à faible degré Ensuite, nous représentons chaque contrainte comme une fonction rationnelle. La contrainte (1) ci-dessus est traduite en C'est un polynôme de degré au plus deg(f₂)-1 si et seulement si la contrainte (1) tient (voir le post
Initialement publiéen anglais par StarkWare le 17 Juillet, 2019. Part 3 sur 4
Veuillez noter que cet article contient de nombreuses notations mathématiques. Comme tous les téléphones mobiles ne les prennent pas entièrement en charge, nous vous recommandons de le lire sur un ordinateur.
Introduction
Voici la troisième partie de notre plongée en profondeur dans StarkDEX, où nous décrivons le système de preuve générique STARK, dont l'implémentation de StarkDEX est une instance. Si vous ne l'avez pas encore fait et que vous souhaitez comprendre l'ensemble du système StarkDEX, nous vous recommandons de lire les parties 1 et 2, mais vous pouvez également lire cet article. Nous vous recommandons également de lire notre série STARK Math pour une discussion plus approfondie des constructions mathématiques nécessaires à la compréhension de cet article.
Dans cet article, nous décrivons le système de preuve STARK comme un protocole interactif entre deux parties, le prouveur et le vérifieur Le prouveur envoie une série de messages pour tenter de convaincre le vérifeur qu'un certain calcul sur une entrée donnée a été effectué correctement (l'énoncé prouvé). Le vérifieur répond aux messages par des valeurs aléatoires. Finalement, le vérifieur accepte la preuve si le calcul a été effectué correctement, ou la rejette (avec une forte probabilité) si ce n'est pas le cas.
Bien que nous décrivions le système comme un protocole interactif, il est à noter que dans la version Alpha de StarkDEX, cette interactivité est finalement remplacée par une transformation en un système non interactif dans lequel le prouveur fournit une preuve et le vérifieur décide de l'accepter ou de la rejeter.
Systèmes de preuve STARK
Si vous souhaitez rafraîchir votre compréhension des traces d'exécution et des contraintes polynomiales, jetez un coup d'œil à nos articles Arithmétisation I & II de la série Stark Math.
La trace
(ndlr: dans le sens informatique)
La trace d'exécution d'un calcul, ou trace en abrégé, est une séquence d'états de la machine, un par cycle d'horodatage. Si le calcul nécessite w registres et dure N cycles, la trace d'exécution peut être représentée par un tableau de taille N x w. Étant donné une déclaration concernant l'exactitude d'un calcul, le vérifieur calcule d'abord l’origine.
On désigne les colonnes de la trace par f₁, f₂,..., fs. Chaque fⱼ est de longueur N=2ⁿ, pour un certain n fixé. Les valeurs dans les cellules de la trace sont des éléments dans un grand champ F. Dans notre version Alpha, F est un champ premier de 252 bits. Le domaine d'évaluation de la trace est défini comme , où g est un générateur dans un sous-groupe du groupe multiplicatif de F. En fait, nous énumérons les lignes de la trace par les éléments de . Chaque colonne de trace est interprétée comme N évaluations ponctuelles d'un polynôme de degré inférieur à N sur le domaine d'évaluation de la trace. Ces polynômes sont appelés polynômes de colonne de trace ou polynômes de colonne en bref. Trace Low Degree Extension & Commitment Comme nous l'avons mentionné plus haut, chaque colonne de trace est considérée comme N évaluations d'un polynôme de degré inférieur à N. Afin d'obtenir un protocole sécurisé, chacun de ces polynômes est évalué sur un domaine plus large, que nous appelons le domaine d'évaluation. Par exemple, dans notre StarkDEX Alpha, la taille du domaine d'évaluation est généralement de 16*N. Nous désignons cette évaluation sous le nom de trace Low Degree Extension (LDE) et le rapport entre la taille du domaine d'évaluation et le domaine de la trace sous le nom de blowup factor (ceux qui sont familiers avec la notation de la théorie des codes remarqueront que le blowup factor est 1/rate et que la LDE est en fait simplement un code Reed-Solomon de la trace). Après la génération de la trace LDE, le prouveur s'engage sur celle-ci. Dans tout le système, les engagements sont mis en œuvre en construisant un arbre de Merkle sur la série d'éléments de champ et en envoyant la racine de Merkle au vérifieur. Cette dernière implique quelques considérations techniques concernant la sérialisation des éléments de champ et la sélection de la fonction de hachage, ignorées ici pour des raisons de clarté. Les feuilles de l'arbre de Merkle sont sélectionnées de telle sorte que si un désengagement est susceptible d'impliquer plusieurs éléments de champ ensemble, ils sont regroupés dans une seule feuille de Merkle. Dans le cas de la trace LDE, cela implique que nous regroupons tous les éléments de champ dans la "ligne" de la trace LDE (l'évaluation de tous les polynômes de colonne à un point gⁱ) en une seule feuille de Merkle. Les contraintes Une trace d'exécution est valide si (1) certaines contraintes de limites sont respectées et (2) chaque paire d'états consécutifs satisfait aux contraintes dictées par le calcul. Par exemple, si à l'instant t le calcul doit additionner les contenus des 1er et 2ème registres et placer le résultat dans le 3ème registre, la contrainte pertinente serait Trace[t,1]+Trace[t,2]-Trace[t+1, 3] = 0. Les contraintes sont exprimées sous forme de polynômes composés sur les cellules de trace qui sont satisfaites si et seulement si le calcul est correct. On les appelle donc les contraintes polynomiales de la représentation intermédiaire algébrique (RIA) sur la trace. Par exemple, dans le contexte de la preuve de l'exécution correcte d'un lot de transactions dans un échange décentralisé (DEX), les contraintes sont telles qu'elles sont toutes satisfaites si et seulement si un lot de transactions est valide. Examinons quelques exemples de différentes contraintes sur les cellules de trace. f₂(x)-a = 0 pour x=g⁷ (la valeur dans la colonne 2 ligne g⁷ est égale à a). f₆²(x) -f₆(g³x) = 0 pour tout x (la valeur au carré de chaque ligne de la colonne 6 est égale à la valeur trois lignes plus loin). f₃(x) -f₄(gx) = 0 pour tous les x sauf g⁵ (la valeur de chaque ligne de la colonne 3 est égale à la valeur de la colonne 4 un rang avant, dans toutes les lignes sauf la ligne g⁵). f₂(x) -2*f₅(x) = 0 pour tout x dans une ligne impaire (la valeur de chaque ligne impaire dans la colonne 2 est égale à deux fois la valeur de la même ligne impaire dans la colonne 5). Rappelons que notre objectif est de prouver l'exactitude d'un calcul. En écrivant un ensemble de contraintes polynomiales qui sont satisfaites si et seulement si le calcul est valide, nous réduisons le problème original à prouver que les contraintes polynomiales sont satisfaites. Des contraintes polynomiales au problème de test à faible degré Ensuite, nous représentons chaque contrainte comme une fonction rationnelle. La contrainte (1) ci-dessus est traduite en C'est un polynôme de degré au plus deg(f₂)-1 si et seulement si la contrainte (1) tient (voir le post
pour plus de détails). Pour comprendre la conversion des contraintes (2), (3) et (4), rappelons d'abord que l'ensemble suivant {x∈ F| xᴺ-1=0} est exactement tout x dans le groupe multiplicatif de F. Par conséquent, nous obtenons les réductions suivantes: La contrainte (2) tient si et seulement si la fonction rationnelle suivante est un polynôme de degré au plus 2*deg(f₆)-N: La contrainte (3) tient si et seulement si la fonction rationnelle suivante est un polynôme de degré au plus max{deg(f₃), deg(f₄)} - N+1: La contrainte (4) tient si et seulement si la fonction rationnelle suivante est un polynôme de degré au plus max{deg(f₂), deg(f₅)} - N/2: Représentées sous forme de fonctions rationnelles, les contraintes sont telles que chaque numérateur définit une règle pertinente devant être appliquée sur les cellules de la trace, et chaque dénominateur définit le domaine dans lequel la règle correspondante doit tenir. Comme le vérifieur doit évaluer ces fonctions rationnelles, il est important, pour la concision du protocole STARK, que les domaines soient tels que leur dénominateur correspondant puisse être évalué efficacement, comme dans les quatre exemples ci-dessus. Polynôme de composition Afin de prouver efficacement la validité de la trace d'exécution, nous nous efforçons d'atteindre les trois objectifs suivants : Composer les contraintes sur les polynômes de la trace pour les appliquer à la trace. Ajuster les degrés des contraintes à un seul degré afin qu'elles puissent être combinées en un seul polynôme de ce degré. Combiner les contraintes en un seul polynôme (plus grand), appelé polynôme de composition, afin qu'un seul test de faible degré puisse être utilisé pour attester de leur (faible) degré. Dans cette section, nous décrivons comment les opérations ci-dessus sont effectuées. Ajustement du degré Afin d'assurer la solidité, nous devons montrer que toutes les contraintes individuelles composées avec les polynômes de la colonne de trace sont de faible degré. Pour cette raison, nous ajustons le degré des contraintes au plus haut degré D de toutes les contraintes (et si D n'est pas une puissance de 2, jusqu'à la puissance de 2 la plus proche supérieure à D). Par conséquent, cela devient également le degré du polynôme de composition. L'ajustement du degré est effectué comme suit: Étant donné une contrainte Cⱼ(x) de degré Dⱼ, nous ajoutons au polynôme de composition un terme de la forme suivante : où 𝛼ⱼ et βⱼ sont des éléments de champ aléatoire envoyés par le vérifieur. En conséquence, si le polynôme de composition est de faible degré, il s'ensuit automatiquement que les contraintes individuelles sont également de faible degré Dⱼ comme souhaité. Le résultat est un polynôme de composition de la forme: où k est le nombre de contraintes. Combinaison des contraintes Une fois que le prouveur s'est engagé sur la trace LDE, le vérifieur fournit des coefficients aléatoires pour créer une combinaison linéaire aléatoire des contraintes résultant dans le Polynôme de Composition. Au lieu de vérifier la cohérence de chaque contrainte individuellement sur les éléments de la trace, il suffit d'appliquer un test de faible degré au Polynôme de Composition qui représente toutes les contraintes appliquées en une fois à toutes les colonnes de la trace. Comme les contraintes utilisées dans notre version Alpha sont de degré deux ou moins, le degré du polynôme de composition est 2N. Par conséquent, nous pouvons représenter le polynôme de composition H(x) comme une seule colonne d'évaluations de longueur 2N ou, comme nous préférons le faire, comme deux colonnes H₁(x) et H₂(x) de longueur N, où H(x)=H₁(x²)+xH₂(x²). Engagement sur le polynôme de composition Ensuite, le prouveur effectue encore une autre extension de bas degré des deux colonnes du polynôme de composition représentant H₁ et H₂. Comme ces colonnes sont de la même longueur N que les colonnes de la trace, nous les appelons parfois la trace du polynôme de composition et nous abordons leur extension et leur engagement de la même manière que pour la trace d'exécution. Pour ce faire, nous les étendons par le même facteur d'expansion, nous regroupons les rangées (de paires d'éléments de champ) en feuilles d'un arbre de Merkle, nous calculons les valeurs de hachage et nous envoyons la racine de l'arbre comme engagement. Contrôle de cohérence sur un point aléatoire (la méthode DEEP) Notons que la valeur de H(x) pour un point (élément de champ) donné z peut être obtenue de deux manières : à partir de H₁(z²) et H₂(z²) ou en calculant la combinaison linéaire de contraintes mentionnée ci-dessus. Ce calcul induit un ensemble de points sur les colonnes de trace qui doit être calculé afin de compléter le calcul requis. L'ensemble des points nécessaires pour calculer H(x) pour un seul point est appelé un
masque
. Ainsi, étant donné un point x=z, nous pouvons vérifier la cohérence entre H et la trace si on nous donne les valeurs de H₁(z²) et H₂(z²) et les valeurs du masque induit sur la trace. À cette phase, le vérifieur envoie un point z∊F échantillonné aléatoirement. Le vérifieur renvoie les évaluations de H₁(z²) et H₂(z²), ainsi que l'évaluation des éléments pertinents du masque nécessaire au calcul de H(z). Dénotez que ces ensembles de valeurs envoyées par le prouveur par {yⱼ}. Pour un prouveur honnête, la valeur de chaque yⱼ est égale à fₖ(zgˢ) où k est la colonne de la cellule correspondante et
s
est son décalage en ligne. Le vérifieur peut alors calculer H(z) de deux façons : en se basant sur H₁ et H₂ (en utilisant H(z)=H₁(z²)+z*H₂(z²)) et en se basant sur les valeurs de masque yⱼ. On vérifie que les deux résultats sont identiques. Il reste à montrer que les valeurs envoyées par le prouveur dans cette phase sont correctes (c'est-à-dire effectivement égales aux valeurs de masque du point z), ce qui sera fait dans la section suivante. Cette méthode de vérification de la cohérence entre deux polynômes par l'échantillonnage d'un point aléatoire dans un grand domaine est appelée Domain Extension for Eliminating Pretenders (DEEP). Le lecteur intéressé peut trouver plus de détails dans
DEEP-FRI. Polynôme de composition DEEP Pour vérifier que les valeurs DEEP envoyées par le prouveur sont correctes, nous créons un deuxième ensemble de contraintes et le traduisons ensuite en un problème de test de faible degré de manière similaire au polynôme de composition défini ci-dessus. Pour chaque valeur yⱼ nous définissons la contrainte suivante: La fonction rationnelle est un polynôme de degré deg(fₖ)-1 si et seulement si fₖ(zgˢ) = yⱼ. On désigne la taille du masque par M. Le vérifieur échantillonne M+2 éléments aléatoires du champ {𝛼ⱼ}ⱼ . Nous désignons le polynôme qui fait l'objet du test à faible degré comme le polynôme de composition DEEP. Il est défini comme suit: (notez que dans le premier terme k et zgˢ ne sont bien sûr pas des constantes mais dépendent de j). Il s'agit d'une combinaison linéaire (aléatoire) de contraintes de la forme: où f est soit un polynôme trace-colonne, soit un polynôme H₁ / H₂. Ainsi, prouver que cette combinaison linéaire est de faible degré implique de prouver le faible degré des polynômes de la colonne de trace et celui des polynômes de H₁ et H₂, ainsi que le fait que les valeurs de DEEP sont correctes. Test du bas degré
Le protocole FRI pour les tests à faible degré
Pour les tests de faible degré, nous utilisons une variante optimisée d'un protocole connu sous le nom de FRI (qui signifie Fast Reed-Solomon Interactive Oracle Proof of Proximity), et le lecteur intéressé peut en savoir plus à ce sujet
sur le sujet, le protocole se compose de deux phases : une phase de validation et une phase d'interrogation. Phase d'engagement Dans la version FRI de base, le prouveur scinde le polynôme de contraintes DEEP original, noté ici p₀(x) en deux polynômes de degré inférieur à d/2, g₀(x) et h₀(x), satisfaisant p₀(x)=g₀(x²)+x
h₀(x²). Le vérifieur échantillonne une valeur aléatoire 𝛼₀, l'envoie au prouveur, et demande au prouveur de s'engager sur le polynôme p₁(x)=g₀(x) + 𝛼₀
h₀(x). Notons que p₁(x) est de degré inférieur à d/2. Nous continuons ensuite récursivement en divisant p₁(x) en g₁(x) et h₁(x), puis en choisissant une valeur 𝛼₁, en construisant p₂(x) et ainsi de suite. A chaque fois, le degré du polynôme est divisé par deux. Ainsi, après log(d) étapes, on se retrouve avec un polynôme constant, et le prouveur peut simplement envoyer la valeur constante au vérifieur. Comme le lecteur peut s'y attendre, tous les engagements ci-dessus sur les évaluations polynomiales sont faits en utilisant le schéma d'engagement de Merkle tel que décrit ci-dessus. Pour que le protocole ci-dessus fonctionne, nous avons besoin de la propriété que pour chaque z dans le domaine L, il est certain que -z est aussi dans L. De plus, l'engagement sur p₁(x) ne sera pas sur L mais sur L²={x² : x ∊ L}. Puisque nous appliquons itérativement l'étape FRI, L² devra également satisfaire la propriété {z, -z}, et ainsi de suite. Ces exigences algébriques sont satisfaites par notre choix d'utiliser un coset multiplicatif comme domaine d'évaluation. Phase d'interrogation Nous devons maintenant vérifier que le prouveur n'a pas triché. Le vérifieur échantillonne un z aléatoire dans L et interroge p₀(z) et p₀(-z). Ces deux valeurs suffisent à déterminer les valeurs de g₀(z²) et h₀(z²), comme le montrent les deux équations linéaires suivantes dans les deux "variables" g₀(z²) et h₀(z²): Le vérifieur peut résoudre ce système d'équations et en déduire les valeurs de g₀(z²) et h₀(z²). Il s'ensuit qu'il peut calculer la valeur de p₁(z²) qui est une combinaison linéaire des deux. Maintenant, le vérifieur interroge p₁(z²) et s'assure qu'elle est égale à la valeur calculée ci-dessus. Cela sert d'indication que l'engagement sur p₁(x), qui a été envoyé par le prouveur dans la phase de commit, est bien le bon. Le vérifieur peut continuer, en interrogeant p₁(-z²) (rappelons que (-z²)∊ L² et que l'engagement sur p₁(x) était donné sur L²) et en déduire p₂(z⁴). Le vérifieur continue ainsi jusqu'à utiliser toutes ces requêtes pour finalement déduire la valeur de P_h(z), pour h=log(d). Mais, rappelons que P_h(z) est un polynôme constant dont la valeur constante a été envoyée par le prouveur dans la phase de validation, avant de choisir z. Le vérifieur doit vérifier que la valeur envoyée par le prouveur est bien égale à la valeur que le vérifieur a calculée à partir des requêtes aux fonctions précédentes. Toutes les réponses aux requêtes reçues par le vérifieur doivent également être vérifiées pour leur cohérence avec les engagements de Merkle envoyés par le prouveur pendant la phase de validation. Par conséquent, le prouveur envoie des informations de désengagement (chemins de Merkle) avec ces réponses pour permettre au vérifieur d'appliquer cela. De plus, le vérifieur doit également assurer la cohérence entre le polynôme p0 et les traces originales dont il est issu (fⱼ et Hⱼ's). Pour cela, pour une des deux valeurs interrogées p₀(z) et p₀(-z) dans la phase d'interrogation, le prouveur envoie également les valeurs de fⱼ et Hⱼ induites par le polynôme de composition DEEP ainsi que leurs dégagements. Ensuite, le vérifieur vérifie la cohérence de ces valeurs avec les engagements sur les traces, calcule la valeur de p₀ et vérifie sa cohérence avec la valeur p₀(z) envoyée par le prouveur. Afin d'atteindre la solidité requise du protocole, la phase d'interrogation est répétée plusieurs fois. Pour un facteur de blowup de 2ⁿ, chaque requête contribue grossièrement à n bits de sécurité. Transformation en protocole non interactif (Fiat-Shamir) Jusqu'à présent, le protocole décrit ci-dessus est décrit comme un protocole interactif. Dans notre version Alpha, nous transformons le protocole interactif en une version non interactive, de sorte que le prouveur génère une preuve sous la forme d'un fichier (ou d'une représentation binaire équivalente) et que le vérifieur la reçoive pour en vérifier l'exactitude (on-chain). La suppression de l'interactivité est obtenue par la
, une méthode qui combine une preuve Oracle interactive (IOP), telle que le protocole décrit ci-dessus, avec une fonction de hachage cryptographique afin d'obtenir une preuve cryptographique. Pour en savoir plus sur ce mécanisme, consultez notre article de blog. Les idées fondamentales derrière cette construction sont que le prouveur simule la réception du caractère aléatoire du vérifieur. Cela se fait en extrayant le caractère aléatoire d'une fonction de hachage qui est appliquée aux données antérieures envoyées par le vérifieur (et jointes à la preuve). Une telle construction est fréquemment appelée
une chaîne de hachage
. Dans notre version Alpha, la chaîne de hachage est initialisée en hachant l'entrée publique connue à la fois du prouveur et du vérifieur. D'autres détails techniques sont omis pour des raisons de simplicité. Optimisation de la longueur des preuves En plus de la description du protocole ci-dessus, nous utilisons plusieurs techniques d'optimisation afin de réduire la taille de la preuve. Ces techniques sont décrites dans les sous-sections suivantes.
Saut de couche FRI
Au lieu de s'engager sur chacune des couches FRI dans la phase d'engagement du protocole FRI, le prouveur peut sauter des couches et ne s'engager que sur un sous-ensemble d'entre elles. Ce faisant, le vérifieur économise la création de certains arbres de Merkle, ce qui signifie que dans la phase d'interrogation, il a moins de chemins de désengagement à envoyer au vérifieur. Il y a cependant un compromis à faire. Si, par exemple, le vérifieur ne commet que sur une couche sur trois, il doit, pour répondre à une requête, décommander 8 éléments de la première couche (au lieu des 2 qu'il envoie dans le cas standard). Le prouveur prend ce fait en considération dans la phase d'engagement. Il regroupe les éléments voisins dans chaque feuille de l'arbre de Merkle. Ainsi, le coût de sauter des couches est d'envoyer plus d'éléments de champ, mais pas plus de chemins d'authentification.
Dernière couche FRI
Une autre optimisation FRI utilisée pour réduire la taille de la preuve consiste à terminer le protocole FRI avant que la dernière couche n'atteigne une valeur constante. Dans ce cas, au lieu de demander au prouveur d'envoyer uniquement la valeur constante de la dernière couche comme engagement, il envoie à la place les coefficients du polynôme représentant la dernière couche. Cela permet au vérifieur de compléter le protocole comme avant, sans avoir besoin d'engagements (et d'envoyer des désengagements pour les éléments de champ dans les dernières couches plus petites). Dans notre version Alpha, la phase d'engagement du FRI se termine généralement lorsqu'elle atteint un polynôme pⱼ de degré inférieur à 64. Le nombre exact peut varier en fonction de la taille de la trace.
Broyage
Comme mentionné ci-dessus, chaque requête ajoute un certain nombre de bits à la sécurité (solidité) de la preuve. Cependant, cela implique également l'envoi de plus de dégagements par le prouveur, ce qui augmente la taille de la preuve. Un mécanisme pour réduire le besoin de nombreuses requêtes est d'augmenter le coût de la génération d'une fausse preuve par un prouveur malveillant. Nous y parvenons en ajoutant au protocole ci-dessus une exigence selon laquelle, après tous les engagements pris par le prouveur, il trouve également un nonce de 256 bits qui, haché avec l'état de la chaîne de hachage, donne un modèle prédéfini d'une longueur requise. La longueur du modèle définit une certaine quantité de travail que le prouveur doit effectuer avant de générer le caractère aléatoire représentant les requêtes. Par conséquent, un prouveur malveillant qui tente de générer des requêtes favorables devra répéter le processus de broyage chaque fois qu'un engagement est modifié. D'un autre côté, un prouveur honnête n'a besoin d'effectuer le broyage qu'une seule fois. Dans notre version Alpha, nous utilisons un modèle avec un certain motif qui contient le nombre de bits pour lesquels le broyage a été effectué et un motif fixe. Ceci est similaire au broyage effectué sur de nombreuses blockchains. Le nonce trouvé par le prouveur est envoyé au vérifieur comme partie de la preuve et, à son tour, le vérifieur vérifie sa cohérence avec l'état de la chaîne de hachage en exécutant la fonction de hachage une fois. Dans notre version Alpha, le prouveur est tenu d'effectuer un broyage de 32 bits. Par conséquent, le nombre de requêtes nécessaires pour atteindre un certain niveau de sécurité peut être réduit. Avec un blowup factor de 2⁴, cela permet de réduire le nombre de requêtes par 8. Le nombre de bits utilisés pour le broyage est communiqué au vérifieur en tant que paramètre. En cas d'incohérence entre la preuve et ce paramètre, le vérifieur rejette la preuve. Colonnes périodiques De nombreuses primitives cryptographiques impliquent l'utilisation de certaines constantes de liste. Lorsque nous appliquons la même primitive cryptographique plusieurs fois, nous obtenons une liste périodique de constantes. Une option pour utiliser cette liste dans une DAR est d'ajouter ses valeurs à la trace et de fournir des contraintes qui garantiront que les valeurs sont correctes. Cependant, ceci est un gaspillage car le vérifieur connaît la liste des valeurs et donc calculer la LDE et s'engager sur elles n'a pas de sens. Au lieu de cela, nous utilisons une technique que nous appelons les colonnes périodiques. La structure périodique de chacune de ces colonnes conduit à un polynôme de colonne qui peut être représenté succinctement. Dans la représentation classique d'un polynôme a₀+a₁
x+a₂
x²+...aₙ*xⁿ comme vecteur de son coefficient (a₀,...,aₖ) la représentation succincte signifie que la plupart des aⱼ sont des zéros. Cela permet au vérifieur de calculer efficacement les évaluations ponctuelles de ces polynômes. Résumé Ceci conclut la description du système de preuve STARK générique utilisé par le système StarkDEX. Le système de preuve STARK tel que décrit conserve les avantages connus tels que la transparence (l'élimination d'une configuration de confiance), la vérification hautement évolutive et la sécurité post-quantique. En outre, il comprend plusieurs nouvelles contributions et optimisations qui réduisent considérablement la taille de la preuve et améliorent le pouvoir expressif des énoncés prouvables de manière efficace d'une manière qui n'a pas été décrite auparavant dans la littérature. Dans le prochain et dernier article de cette série, nous décrirons comment nous avons construit la représentation intermédiaire algébrique (AIR) pour StarkDEX. Comme toujours, si vous avez des questions ou des commentaires, parlez-nous ici ou sur twitter @StarkWareLTD. Kineret Segal & Gideon Kaempfer
pour plus de détails). Pour comprendre la conversion des contraintes (2), (3) et (4), rappelons d'abord que l'ensemble suivant {x∈ F| xᴺ-1=0} est exactement tout x dans le groupe multiplicatif de F. Par conséquent, nous obtenons les réductions suivantes: La contrainte (2) tient si et seulement si la fonction rationnelle suivante est un polynôme de degré au plus 2*deg(f₆)-N: La contrainte (3) tient si et seulement si la fonction rationnelle suivante est un polynôme de degré au plus max{deg(f₃), deg(f₄)} - N+1: La contrainte (4) tient si et seulement si la fonction rationnelle suivante est un polynôme de degré au plus max{deg(f₂), deg(f₅)} - N/2: Représentées sous forme de fonctions rationnelles, les contraintes sont telles que chaque numérateur définit une règle pertinente devant être appliquée sur les cellules de la trace, et chaque dénominateur définit le domaine dans lequel la règle correspondante doit tenir. Comme le vérifieur doit évaluer ces fonctions rationnelles, il est important, pour la concision du protocole STARK, que les domaines soient tels que leur dénominateur correspondant puisse être évalué efficacement, comme dans les quatre exemples ci-dessus. Polynôme de composition Afin de prouver efficacement la validité de la trace d'exécution, nous nous efforçons d'atteindre les trois objectifs suivants : Composer les contraintes sur les polynômes de la trace pour les appliquer à la trace. Ajuster les degrés des contraintes à un seul degré afin qu'elles puissent être combinées en un seul polynôme de ce degré. Combiner les contraintes en un seul polynôme (plus grand), appelé polynôme de composition, afin qu'un seul test de faible degré puisse être utilisé pour attester de leur (faible) degré. Dans cette section, nous décrivons comment les opérations ci-dessus sont effectuées. Ajustement du degré Afin d'assurer la solidité, nous devons montrer que toutes les contraintes individuelles composées avec les polynômes de la colonne de trace sont de faible degré. Pour cette raison, nous ajustons le degré des contraintes au plus haut degré D de toutes les contraintes (et si D n'est pas une puissance de 2, jusqu'à la puissance de 2 la plus proche supérieure à D). Par conséquent, cela devient également le degré du polynôme de composition. L'ajustement du degré est effectué comme suit: Étant donné une contrainte Cⱼ(x) de degré Dⱼ, nous ajoutons au polynôme de composition un terme de la forme suivante : où 𝛼ⱼ et βⱼ sont des éléments de champ aléatoire envoyés par le vérifieur. En conséquence, si le polynôme de composition est de faible degré, il s'ensuit automatiquement que les contraintes individuelles sont également de faible degré Dⱼ comme souhaité. Le résultat est un polynôme de composition de la forme: où k est le nombre de contraintes. Combinaison des contraintes Une fois que le prouveur s'est engagé sur la trace LDE, le vérifieur fournit des coefficients aléatoires pour créer une combinaison linéaire aléatoire des contraintes résultant dans le Polynôme de Composition. Au lieu de vérifier la cohérence de chaque contrainte individuellement sur les éléments de la trace, il suffit d'appliquer un test de faible degré au Polynôme de Composition qui représente toutes les contraintes appliquées en une fois à toutes les colonnes de la trace. Comme les contraintes utilisées dans notre version Alpha sont de degré deux ou moins, le degré du polynôme de composition est 2N. Par conséquent, nous pouvons représenter le polynôme de composition H(x) comme une seule colonne d'évaluations de longueur 2N ou, comme nous préférons le faire, comme deux colonnes H₁(x) et H₂(x) de longueur N, où H(x)=H₁(x²)+xH₂(x²). Engagement sur le polynôme de composition Ensuite, le prouveur effectue encore une autre extension de bas degré des deux colonnes du polynôme de composition représentant H₁ et H₂. Comme ces colonnes sont de la même longueur N que les colonnes de la trace, nous les appelons parfois la trace du polynôme de composition et nous abordons leur extension et leur engagement de la même manière que pour la trace d'exécution. Pour ce faire, nous les étendons par le même facteur d'expansion, nous regroupons les rangées (de paires d'éléments de champ) en feuilles d'un arbre de Merkle, nous calculons les valeurs de hachage et nous envoyons la racine de l'arbre comme engagement. Contrôle de cohérence sur un point aléatoire (la méthode DEEP) Notons que la valeur de H(x) pour un point (élément de champ) donné z peut être obtenue de deux manières : à partir de H₁(z²) et H₂(z²) ou en calculant la combinaison linéaire de contraintes mentionnée ci-dessus. Ce calcul induit un ensemble de points sur les colonnes de trace qui doit être calculé afin de compléter le calcul requis. L'ensemble des points nécessaires pour calculer H(x) pour un seul point est appelé un
masque
. Ainsi, étant donné un point x=z, nous pouvons vérifier la cohérence entre H et la trace si on nous donne les valeurs de H₁(z²) et H₂(z²) et les valeurs du masque induit sur la trace. À cette phase, le vérifieur envoie un point z∊F échantillonné aléatoirement. Le vérifieur renvoie les évaluations de H₁(z²) et H₂(z²), ainsi que l'évaluation des éléments pertinents du masque nécessaire au calcul de H(z). Dénotez que ces ensembles de valeurs envoyées par le prouveur par {yⱼ}. Pour un prouveur honnête, la valeur de chaque yⱼ est égale à fₖ(zgˢ) où k est la colonne de la cellule correspondante et
s
est son décalage en ligne. Le vérifieur peut alors calculer H(z) de deux façons : en se basant sur H₁ et H₂ (en utilisant H(z)=H₁(z²)+z*H₂(z²)) et en se basant sur les valeurs de masque yⱼ. On vérifie que les deux résultats sont identiques. Il reste à montrer que les valeurs envoyées par le prouveur dans cette phase sont correctes (c'est-à-dire effectivement égales aux valeurs de masque du point z), ce qui sera fait dans la section suivante. Cette méthode de vérification de la cohérence entre deux polynômes par l'échantillonnage d'un point aléatoire dans un grand domaine est appelée Domain Extension for Eliminating Pretenders (DEEP). Le lecteur intéressé peut trouver plus de détails dans
DEEP-FRI. Polynôme de composition DEEP Pour vérifier que les valeurs DEEP envoyées par le prouveur sont correctes, nous créons un deuxième ensemble de contraintes et le traduisons ensuite en un problème de test de faible degré de manière similaire au polynôme de composition défini ci-dessus. Pour chaque valeur yⱼ nous définissons la contrainte suivante: La fonction rationnelle est un polynôme de degré deg(fₖ)-1 si et seulement si fₖ(zgˢ) = yⱼ. On désigne la taille du masque par M. Le vérifieur échantillonne M+2 éléments aléatoires du champ {𝛼ⱼ}ⱼ . Nous désignons le polynôme qui fait l'objet du test à faible degré comme le polynôme de composition DEEP. Il est défini comme suit: (notez que dans le premier terme k et zgˢ ne sont bien sûr pas des constantes mais dépendent de j). Il s'agit d'une combinaison linéaire (aléatoire) de contraintes de la forme: où f est soit un polynôme trace-colonne, soit un polynôme H₁ / H₂. Ainsi, prouver que cette combinaison linéaire est de faible degré implique de prouver le faible degré des polynômes de la colonne de trace et celui des polynômes de H₁ et H₂, ainsi que le fait que les valeurs de DEEP sont correctes. Test du bas degré
Le protocole FRI pour les tests à faible degré
Pour les tests de faible degré, nous utilisons une variante optimisée d'un protocole connu sous le nom de FRI (qui signifie Fast Reed-Solomon Interactive Oracle Proof of Proximity), et le lecteur intéressé peut en savoir plus à ce sujet
sur le sujet, le protocole se compose de deux phases : une phase de validation et une phase d'interrogation. Phase d'engagement Dans la version FRI de base, le prouveur scinde le polynôme de contraintes DEEP original, noté ici p₀(x) en deux polynômes de degré inférieur à d/2, g₀(x) et h₀(x), satisfaisant p₀(x)=g₀(x²)+x
h₀(x²). Le vérifieur échantillonne une valeur aléatoire 𝛼₀, l'envoie au prouveur, et demande au prouveur de s'engager sur le polynôme p₁(x)=g₀(x) + 𝛼₀
h₀(x). Notons que p₁(x) est de degré inférieur à d/2. Nous continuons ensuite récursivement en divisant p₁(x) en g₁(x) et h₁(x), puis en choisissant une valeur 𝛼₁, en construisant p₂(x) et ainsi de suite. A chaque fois, le degré du polynôme est divisé par deux. Ainsi, après log(d) étapes, on se retrouve avec un polynôme constant, et le prouveur peut simplement envoyer la valeur constante au vérifieur. Comme le lecteur peut s'y attendre, tous les engagements ci-dessus sur les évaluations polynomiales sont faits en utilisant le schéma d'engagement de Merkle tel que décrit ci-dessus. Pour que le protocole ci-dessus fonctionne, nous avons besoin de la propriété que pour chaque z dans le domaine L, il est certain que -z est aussi dans L. De plus, l'engagement sur p₁(x) ne sera pas sur L mais sur L²={x² : x ∊ L}. Puisque nous appliquons itérativement l'étape FRI, L² devra également satisfaire la propriété {z, -z}, et ainsi de suite. Ces exigences algébriques sont satisfaites par notre choix d'utiliser un coset multiplicatif comme domaine d'évaluation. Phase d'interrogation Nous devons maintenant vérifier que le prouveur n'a pas triché. Le vérifieur échantillonne un z aléatoire dans L et interroge p₀(z) et p₀(-z). Ces deux valeurs suffisent à déterminer les valeurs de g₀(z²) et h₀(z²), comme le montrent les deux équations linéaires suivantes dans les deux "variables" g₀(z²) et h₀(z²): Le vérifieur peut résoudre ce système d'équations et en déduire les valeurs de g₀(z²) et h₀(z²). Il s'ensuit qu'il peut calculer la valeur de p₁(z²) qui est une combinaison linéaire des deux. Maintenant, le vérifieur interroge p₁(z²) et s'assure qu'elle est égale à la valeur calculée ci-dessus. Cela sert d'indication que l'engagement sur p₁(x), qui a été envoyé par le prouveur dans la phase de commit, est bien le bon. Le vérifieur peut continuer, en interrogeant p₁(-z²) (rappelons que (-z²)∊ L² et que l'engagement sur p₁(x) était donné sur L²) et en déduire p₂(z⁴). Le vérifieur continue ainsi jusqu'à utiliser toutes ces requêtes pour finalement déduire la valeur de P_h(z), pour h=log(d). Mais, rappelons que P_h(z) est un polynôme constant dont la valeur constante a été envoyée par le prouveur dans la phase de validation, avant de choisir z. Le vérifieur doit vérifier que la valeur envoyée par le prouveur est bien égale à la valeur que le vérifieur a calculée à partir des requêtes aux fonctions précédentes. Toutes les réponses aux requêtes reçues par le vérifieur doivent également être vérifiées pour leur cohérence avec les engagements de Merkle envoyés par le prouveur pendant la phase de validation. Par conséquent, le prouveur envoie des informations de désengagement (chemins de Merkle) avec ces réponses pour permettre au vérifieur d'appliquer cela. De plus, le vérifieur doit également assurer la cohérence entre le polynôme p0 et les traces originales dont il est issu (fⱼ et Hⱼ's). Pour cela, pour une des deux valeurs interrogées p₀(z) et p₀(-z) dans la phase d'interrogation, le prouveur envoie également les valeurs de fⱼ et Hⱼ induites par le polynôme de composition DEEP ainsi que leurs dégagements. Ensuite, le vérifieur vérifie la cohérence de ces valeurs avec les engagements sur les traces, calcule la valeur de p₀ et vérifie sa cohérence avec la valeur p₀(z) envoyée par le prouveur. Afin d'atteindre la solidité requise du protocole, la phase d'interrogation est répétée plusieurs fois. Pour un facteur de blowup de 2ⁿ, chaque requête contribue grossièrement à n bits de sécurité. Transformation en protocole non interactif (Fiat-Shamir) Jusqu'à présent, le protocole décrit ci-dessus est décrit comme un protocole interactif. Dans notre version Alpha, nous transformons le protocole interactif en une version non interactive, de sorte que le prouveur génère une preuve sous la forme d'un fichier (ou d'une représentation binaire équivalente) et que le vérifieur la reçoive pour en vérifier l'exactitude (on-chain). La suppression de l'interactivité est obtenue par la
, une méthode qui combine une preuve Oracle interactive (IOP), telle que le protocole décrit ci-dessus, avec une fonction de hachage cryptographique afin d'obtenir une preuve cryptographique. Pour en savoir plus sur ce mécanisme, consultez notre article de blog. Les idées fondamentales derrière cette construction sont que le prouveur simule la réception du caractère aléatoire du vérifieur. Cela se fait en extrayant le caractère aléatoire d'une fonction de hachage qui est appliquée aux données antérieures envoyées par le vérifieur (et jointes à la preuve). Une telle construction est fréquemment appelée
une chaîne de hachage
. Dans notre version Alpha, la chaîne de hachage est initialisée en hachant l'entrée publique connue à la fois du prouveur et du vérifieur. D'autres détails techniques sont omis pour des raisons de simplicité. Optimisation de la longueur des preuves En plus de la description du protocole ci-dessus, nous utilisons plusieurs techniques d'optimisation afin de réduire la taille de la preuve. Ces techniques sont décrites dans les sous-sections suivantes.
Saut de couche FRI
Au lieu de s'engager sur chacune des couches FRI dans la phase d'engagement du protocole FRI, le prouveur peut sauter des couches et ne s'engager que sur un sous-ensemble d'entre elles. Ce faisant, le vérifieur économise la création de certains arbres de Merkle, ce qui signifie que dans la phase d'interrogation, il a moins de chemins de désengagement à envoyer au vérifieur. Il y a cependant un compromis à faire. Si, par exemple, le vérifieur ne commet que sur une couche sur trois, il doit, pour répondre à une requête, décommander 8 éléments de la première couche (au lieu des 2 qu'il envoie dans le cas standard). Le prouveur prend ce fait en considération dans la phase d'engagement. Il regroupe les éléments voisins dans chaque feuille de l'arbre de Merkle. Ainsi, le coût de sauter des couches est d'envoyer plus d'éléments de champ, mais pas plus de chemins d'authentification.
Dernière couche FRI
Une autre optimisation FRI utilisée pour réduire la taille de la preuve consiste à terminer le protocole FRI avant que la dernière couche n'atteigne une valeur constante. Dans ce cas, au lieu de demander au prouveur d'envoyer uniquement la valeur constante de la dernière couche comme engagement, il envoie à la place les coefficients du polynôme représentant la dernière couche. Cela permet au vérifieur de compléter le protocole comme avant, sans avoir besoin d'engagements (et d'envoyer des désengagements pour les éléments de champ dans les dernières couches plus petites). Dans notre version Alpha, la phase d'engagement du FRI se termine généralement lorsqu'elle atteint un polynôme pⱼ de degré inférieur à 64. Le nombre exact peut varier en fonction de la taille de la trace.
Broyage
Comme mentionné ci-dessus, chaque requête ajoute un certain nombre de bits à la sécurité (solidité) de la preuve. Cependant, cela implique également l'envoi de plus de dégagements par le prouveur, ce qui augmente la taille de la preuve. Un mécanisme pour réduire le besoin de nombreuses requêtes est d'augmenter le coût de la génération d'une fausse preuve par un prouveur malveillant. Nous y parvenons en ajoutant au protocole ci-dessus une exigence selon laquelle, après tous les engagements pris par le prouveur, il trouve également un nonce de 256 bits qui, haché avec l'état de la chaîne de hachage, donne un modèle prédéfini d'une longueur requise. La longueur du modèle définit une certaine quantité de travail que le prouveur doit effectuer avant de générer le caractère aléatoire représentant les requêtes. Par conséquent, un prouveur malveillant qui tente de générer des requêtes favorables devra répéter le processus de broyage chaque fois qu'un engagement est modifié. D'un autre côté, un prouveur honnête n'a besoin d'effectuer le broyage qu'une seule fois. Dans notre version Alpha, nous utilisons un modèle avec un certain motif qui contient le nombre de bits pour lesquels le broyage a été effectué et un motif fixe. Ceci est similaire au broyage effectué sur de nombreuses blockchains. Le nonce trouvé par le prouveur est envoyé au vérifieur comme partie de la preuve et, à son tour, le vérifieur vérifie sa cohérence avec l'état de la chaîne de hachage en exécutant la fonction de hachage une fois. Dans notre version Alpha, le prouveur est tenu d'effectuer un broyage de 32 bits. Par conséquent, le nombre de requêtes nécessaires pour atteindre un certain niveau de sécurité peut être réduit. Avec un blowup factor de 2⁴, cela permet de réduire le nombre de requêtes par 8. Le nombre de bits utilisés pour le broyage est communiqué au vérifieur en tant que paramètre. En cas d'incohérence entre la preuve et ce paramètre, le vérifieur rejette la preuve. Colonnes périodiques De nombreuses primitives cryptographiques impliquent l'utilisation de certaines constantes de liste. Lorsque nous appliquons la même primitive cryptographique plusieurs fois, nous obtenons une liste périodique de constantes. Une option pour utiliser cette liste dans une DAR est d'ajouter ses valeurs à la trace et de fournir des contraintes qui garantiront que les valeurs sont correctes. Cependant, ceci est un gaspillage car le vérifieur connaît la liste des valeurs et donc calculer la LDE et s'engager sur elles n'a pas de sens. Au lieu de cela, nous utilisons une technique que nous appelons les colonnes périodiques. La structure périodique de chacune de ces colonnes conduit à un polynôme de colonne qui peut être représenté succinctement. Dans la représentation classique d'un polynôme a₀+a₁
x+a₂
x²+...aₙ*xⁿ comme vecteur de son coefficient (a₀,...,aₖ) la représentation succincte signifie que la plupart des aⱼ sont des zéros. Cela permet au vérifieur de calculer efficacement les évaluations ponctuelles de ces polynômes. Résumé Ceci conclut la description du système de preuve STARK générique utilisé par le système StarkDEX. Le système de preuve STARK tel que décrit conserve les avantages connus tels que la transparence (l'élimination d'une configuration de confiance), la vérification hautement évolutive et la sécurité post-quantique. En outre, il comprend plusieurs nouvelles contributions et optimisations qui réduisent considérablement la taille de la preuve et améliorent le pouvoir expressif des énoncés prouvables de manière efficace d'une manière qui n'a pas été décrite auparavant dans la littérature. Dans le prochain et dernier article de cette série, nous décrirons comment nous avons construit la représentation intermédiaire algébrique (AIR) pour StarkDEX. Comme toujours, si vous avez des questions ou des commentaires, parlez-nous ici ou sur twitter @StarkWareLTD. Kineret Segal & Gideon Kaempfer
Starknet France
No comments yet