Initialement publié en anglais par StarkWare le 14 Mars 2019.

« Nous devons aller plus loin »

Voici le troisième article de notre série STARK Math. Si vous n'avez pas lu le premier et le deuxième article, nous vous recommandons de le faire avant de poursuivre votre lecture. Attention, celui-ci est un peu plus mathématique que les précédents.

Récap

Dans le post précédent, nous avons présenté l'arithmétisation - le processus de transformation d'une déclaration d’intégrité computationnelle (CI) en une vérification de l'existence d'un polynôme de faible degré. Cette transformation nous permet de réaliser une vérification succincte, où le vérifieur de l'énoncé du CI nécessite exponentiellement moins de ressources que celles nécessaires pour une relecture naïve. Dans le post précédent, nous avons fait un zoom sur la première étape de cette transformation à travers l'exemple de la transformation d'une déclaration CI sur une séquence de Collatz en une origine d'exécution et un ensemble de contraintes polynomiales. Dans cet article, nous passons à l'étape suivante et montrons - en utilisant cette fois une séquence de Fibonacci - comment le prouveur peut combiner l’origine d'exécution et les contraintes polynomiales pour obtenir un polynôme qui est garanti de faible degré si et seulement si l’origine d'exécution satisfait les contraintes polynomiales avec lesquelles nous avons commencé. De plus, nous montrerons comment le domaine sur lequel le polynôme est considéré permet au vérifieur de l'évaluer succinctement. Nous aborderons également brièvement la manière dont les codes de correction d'erreurs jouent un rôle dans les STARKs.

Nous supposerons que vous êtes familier avec les groupes finis, les polynômes sur les champs finis et les articles précédents de cette série.

Requêtes et codes de correction d'erreurs

Rappelons que notre objectif est de permettre à un vérifieur de poser un très petit nombre de questions à un prouveur, et de décider d'accepter ou de rejeter la preuve avec un haut niveau d'exactitude garanti. Idéalement, le vérifieur voudrait demander au prouveur de fournir les valeurs à quelques endroits (aléatoires) de l’origine d'exécution, et vérifier que les contraintes polynomiales tiennent à ces endroits. Une origine d'exécution correcte passera naturellement ce test. Cependant, il n'est pas difficile de construire une origine d'exécution complètement erronée, qui ne viole les contraintes qu'à un seul endroit, et, ce faisant, d'atteindre un résultat complètement éloigné et différent. L'identification de cette faute par un petit nombre de requêtes aléatoires est hautement improbable.

Les techniques courantes qui traitent de problèmes similaires sont les codes de correction d'erreur.

Les codes de correction d'erreur transforment un ensemble de chaînes de caractères, dont certaines peuvent être très similaires les unes aux autres, en un ensemble de chaînes de caractères très différents par paires, en remplaçant les chaînes d'origine par des chaînes plus longues.

Il est intéressant de noter que les polynômes peuvent être utilisés pour construire de bons codes de correction des erreurs, puisque deux polynômes de degré d, évalués sur un domaine considérablement plus grand que d, sont différents presque partout¹. De tels codes sont appelés codes de Reed-Solomon.

En observant cela, nous pouvons étendre l’origine d'exécution en la considérant comme l'évaluation d'un polynôme sur un certain domaine, et l'évaluation de ce même polynôme sur un domaine beaucoup plus grand. En étendant de manière similaire une origine d'exécution incorrecte, on obtient une chaîne de caractères très différente, ce qui permet au vérifieur de distinguer ces cas à l'aide d'un petit nombre de requêtes.

Notre plan est donc de :

1. reformuler la trace d'exécution comme un polynôme,
2. l'étendre à un grand domaine,
3. transformer cela, en utilisant les contraintes polynomiales, en encore un autre polynôme qui est garanti d'être de faible degré si et seulement si l’origine d'exécution est valide.

Exemple fictif : Trace d'exécution booléenne

Supposons que l'énoncé de CI en question soit "Le prouveur a une séquence de 512 nombres, qui sont tous soit 0 soit 1", que nous voudrions vérifier en lisant beaucoup moins que 512 nombres.

Voyons quel type d’origine d'exécution et de contraintes polynomiales exprime cet exemple :

1. La trace d'exécution comporte 512 lignes, chaque ligne contenant une seule cellule contenant soit zéro soit un.
2. La contrainte polynomiale que nous utilisons ici est simplement Aᵢ⋅Aᵢ-Aᵢ=0, où Aᵢ désigne la i-ème cellule de cette origine d'exécution à une seule colonne (un nombre est égal à son carré si et seulement s'il vaut 0 ou 1).

Afin de reformuler cette trace d'exécution en termes de polynômes, nous précisons le domaine dans lequel nous allons travailler - nous optons pour Z₉₆₇₆₉, obtenu à partir de l'ensemble des entiers 0,1,...,96768 avec addition et multiplication modulo 96769. On choisit ensuite un sous-groupe G de Z₉₆₇₆₉* (on utilise F* pour désigner le groupe multiplicatif² de F) tel que |G|=512, et une génératrice³ g de G. L'existence d'un tel sous-groupe est garantie puisque 512 divise la taille de ce groupe (qui est 96768).

Nous considérons maintenant les éléments de l’origine d'exécution comme des évaluations d'un polynôme f(x) de degré inférieur à 512 de la manière suivante : la i-ème cellule contient l'évaluation de f sur la i-ème puissance du générateur.

Formellement :

Un tel polynôme de degré au plus 512 peut être calculé par interpolation, et nous procédons ensuite à son évaluation sur un domaine beaucoup plus grand⁴, formant un cas particulier de Reed-Solomon.

Enfin, nous utilisons ce polynôme pour en créer un autre, dont la faible divergence dépend de la satisfaction de la contrainte sur l’origine d'exécution.

Pour ce faire, nous devons prendre la tangente et discuter des racines des polynômes.

Racines des polynômes

Un fait de base concernant les polynômes et leurs racines est que si p(x) est un polynôme, alors p(a)=0 pour une certaine valeur a, si et seulement s'il existe un polynôme q(x) tel que (x-a)q(x)=p(x), et deg(p)=deg(q)+1.

De plus, pour tout x≠a, on peut évaluer q(x) par calcul :

Par induction, un fait similaire est vrai pour k racines. A savoir, si aᵢ est une racine de p pour tous les i=0..k-1, alors il existe un polynôme q de degré deg(p)-k, et dans toutes les valeurs sauf ces k, il est exactement égal à.

Assemblage

En reformulant la contrainte polynomiale en termes de f, on obtient le polynôme suivant :

Nous avons défini f tel que les racines de cette expression sont 1, g, g², ..., g⁵¹¹ si et seulement si les cellules de la trace d'exécution sont 0 ou 1. Nous pouvons définir :

Et nous savons du paragraphe précédent qu'il existe un polynôme de degré au plus 2·deg(f)-512 qui s'accorde avec p sur tout x ∉{1, g, g², ..., g⁵¹¹} si et seulement si l’origine d'exécution est bien une liste de 512 bits (c'est-à-dire 0 ou 1). Notez que précédemment, le proveur a étendu l’origine d'exécution à un domaine plus large, donc l'interrogation des valeurs du polynôme dans ce domaine est bien définie.

S'il existe un protocole par lequel le proveur peut convaincre⁵ le vérifieur que ce polynôme est de faible degré, tel que dans celui-ci le vérificateur ne demande que des valeurs en dehors de l’origine d'exécution, alors effectivement le vérifieur ne sera convaincu de la véracité de l'énoncé CI que lorsqu'il sera vrai. En fait, dans le prochain article, nous montrerons un protocole qui fait exactement cela, avec une très faible probabilité d'erreur. Pour l'instant, examinons un autre exemple, qui est encore simple, mais pas complètement trivial, et voyons comment la réduction fonctionne dans ce cas.

Fibonacci

L'exemple que nous utilisons ensuite est celui du calcul correct d'une suite de Fibonacci dans Z₉₆₇₆₉ à la 512ème place. Cette suite est définie formellement par :

Et notre affirmation (i.e., l'énoncé du CI) est que a₅₁₁=62215.

Nous pouvons créer une origine d'exécution pour cet énoncé CI en écrivant simplement les 512 nombres :

Les contraintes polynomiales que nous utilisons sont les suivantes :

Traduire en polynômes

Ici aussi, nous définissons un polynôme f(x) de degré au plus 512, tel que les éléments de l’origine d'exécution sont des évaluations de f en puissances d'un certain générateur g.

Formellement :

En exprimant les contraintes polynomiales en termes de f au lieu de A, nous obtenons :

Puisqu'une composition de polynômes est toujours un polynôme - substituer le Aᵢ dans les contraintes par f(gⁱ) signifie toujours que ce sont des contraintes polynomiales.

Notez que 1, 2, et 4 sont des contraintes qui se réfèrent à une seule valeur de f, nous les appelons des contraintes limites.

La relation de récurrence de Fibonacci, en revanche, incarne un ensemble de contraintes sur l'ensemble de l’origine d'exécution, et elle peut être reformulée alternativement comme suit :

L'utilisation d'un générateur pour indexer les rangs de l’origine d'exécution nous permet d'encoder la notion de "rang suivant" comme une simple relation algébrique. Si x est une ligne de la trace d'exécution, alors gx est la ligne suivante, g²x est la ligne suivante, g-¹x est la ligne précédente et ainsi de suite.

Le polynôme de la relation de récurrence : f(g²x)-f(gx)-f(x) est nul pour chaque x qui indexe une ligne dans l’origine d'exécution, à l'exception des deux dernières. Cela signifie que 1, g, g², ..., g⁵⁰⁹ sont toutes les racines de ce polynôme de relation de récurrence (et il est de degré au plus 510), donc nous pouvons construire q(x) comme suit :

Dans le jargon de STARK, ce polynôme est souvent appelé polynôme de composition. En effet, lorsque la trace d'exécution originale obéit à la relation de récurrence de Fibonacci, cette expression s'accorde avec un polynôme dont le degré est au plus 2 (rappelons que le degré de f est au plus 512) sur toutes les valeurs sauf ces 510 : 1, g, g², ..., g⁵⁰⁹ . Cependant, le terme polynôme de composition est quelque peu trompeur, car lorsque la trace d'exécution ne satisfait pas la contrainte polynomiale - les évaluations de cette expression diffèrent de n'importe quel polynôme de faible degré à de nombreux endroits. En d'autres termes, elle est proche d'un polynôme de bas degré si et seulement si l'IC original est correct, ce qui était notre objectif.

Ceci conclut la réduction promise, qui traduit le problème de vérifier si certaines contraintes polynomiales sont satisfaites sur une certaine trace d'exécution, au problème de vérifier si un certain polynôme (connu du prouveur) est de bas degré.

Succinctement

Une technique de vérification très efficace est la clé des STARK, et elle peut être considérée comme composée de deux parties : l'utilisation d'un petit nombre de requêtes et l'exécution par le vérifieur d'un petit calcul sur chaque requête. La première partie est réalisée grâce aux codes de correction d'erreurs, qui permettent d'effectuer des requêtes à très peu d'endroits, et la seconde partie a été en quelque sorte passée sous silence dans cet article, jusqu'à présent. Le travail du vérifieur peut-être résumé comme suit :

1. interroger le polynôme de composition à des endroits aléatoires,
2. vérifier le faible degré d'abstraction sur la base de ces interrogations.

La vérification succincte du faible degré d'égouttage sera traitée dans le prochain post, mais qu'entendons-nous exactement par "interroger le polynôme de composition" ? Le lecteur avide a pu se méfier de cette expression, et à juste titre. Le prouveur, après tout, peut être malveillant. Lorsque le vérifieur demande l'évaluation du polynôme de composition à un certain x, le vérifieur peut répondre avec l'évaluation d'un polynôme de degré vraiment bas, qui passera tout test de faible degré, mais qui n'est pas le polynôme de composition.

Pour éviter cela, le vérifieur interroge explicitement la trace d'exécution de Fibonacci à une certaine ligne w en demandant les valeurs de f à trois endroits : f(w), f(gw), f(g²w).

Le vérifieur peut maintenant calculer la valeur du polynôme de composition à w par :

Où le numérateur peut être calculé en utilisant les valeurs obtenues du vérificateur, et le dénominateur... eh bien, c'est là que le bât blesse (ce qui a été balayé sous le tapis).

D'un côté, le dénominateur est complètement indépendant de la trace d'exécution, donc le vérificateur peut le calculer avant même de communiquer avec le prouveur.

D'autre part, dans la pratique, la trace peut être composée de centaines de milliers de lignes, et le calcul du dénominateur coûterait cher au vérifieur en temps d'exécution.

C'est ici que l'arithmétisation est cruciale pour la concision - puisque le calcul de cette expression pour le cas spécial où les puissances de g forment un sous-groupe peut être fait très efficacement si on le remarque :

Cette égalité est vraie car les deux côtés sont des polynômes de degré |G| dont les racines sont exactement les éléments de G.

Le calcul du côté droit de cette équation semble nécessiter un nombre d'opérations qui est linéaire en |G|. Cependant, si nous recourons à l'exponentiation par élévation au carré, le côté gauche de cette équation peut être calculé en un temps d'exécution qui est logarithmique en |G|.

Et le dénominateur réel du polynôme de composition de Fibonacci en question peut être obtenu en le réécrivant comme suit :

Cette apparente technicité est au cœur de la capacité du vérifieur à s'exécuter en temps polylogarithmique, et elle n'est possible que parce que nous considérons la trace d'exécution comme des évaluations d'un polynôme sur un sous-groupe du champ, et que les contraintes polynomiales en question tiennent sur un sous-groupe.

Des astuces similaires peuvent être appliquées pour des traces d'exécution plus sophistiquées, mais il est essentiel que le motif répétitif de la contrainte coïncide avec un sous-groupe du champ.

Plus de contraintes, plus de colonnes !

Les exemples présentés dans ce post étaient délibérément simples, afin de mettre en évidence les aspects essentiels de l'arithmétisation. Une question naturelle qui se pose est la suivante : comment est traité le cas des colonnes multiples et des contraintes multiples. La réponse est simple : les colonnes multiples signifient simplement qu'il y a plus d'un polynôme à utiliser, et les polynômes de composition multiples - résultant des contraintes multiples - sont combinés en un seul polynôme, une combinaison linéaire aléatoire de tous ces polynômes, pour les besoins de la dernière phase de STARK, qui est un test de faible degré. Avec une forte probabilité, la combinaison linéaire est de faible degré si et seulement si toutes ses composantes le sont.

Conclusion

Nous avons montré comment, compte tenu d'une origine d'exécution et de polynômes de contraintes, le prouveur peut construire un polynôme de faible degré si et seulement si l'énoncé CI original tient. De plus, nous avons montré comment le vérifieur peut interroger les valeurs de ce polynôme de manière efficace, en s'assurant que le prouveur n'a pas remplacé le vrai polynôme par un faux de faible degré.

Dans le prochain post, qui entrera dans les détails des tests de faible degré, nous montrerons comment cette magie, qui consiste à interroger un petit nombre de valeurs et à déterminer si un polynôme est de faible degré, est réalisée.

Shir Peled

StarkWare

¹ Pour s'en convaincre, il suffit de remarquer que la différence entre des polynômes distincts de degré d est un polynôme non nul de degré d, donc qui a au plus d zéros.

² Rappel : le groupe multiplicatif est obtenu en omettant l'élément zéro du champ.

³ Un générateur est un élément du sous-groupe dont les puissances couvrent l'ensemble du sous-groupe.

⁴ Le choix de la taille de ce domaine se traduit directement par l'erreur de solidité, plus il est grand - plus l'erreur de solidité est petite.

⁵ Telle que le vérificateur est convaincu si et seulement si le prouveur ne triche pas.