Explorer Circle STARKs

Ces dernières années, la conception des protocoles STARKs tend à utiliser des champs plus petits. Les premières implémentations des STARKs utilisaient un champ de 256 bits pour effectuer des opérations modulo sur de grands nombres, ce qui était compatible avec les signatures basées sur des courbes elliptiques. Cependant, cette conception était peu efficace et gaspillait de la puissance de calcul dans le traitement de grands nombres. Pour résoudre ce problème, les STARKs ont commencé à utiliser des champs plus petits : Goldilocks, Mersenne31 et BabyBear.

Cette transformation a amélioré la vitesse de preuve. Par exemple, Starkware peut prouver 620 000 valeurs de hachage Poseidon2 par seconde sur un ordinateur portable M3. Tant que l'on fait confiance à Poseidon2 en tant que fonction de hachage, il est possible de résoudre le problème du développement efficace de ZK-EVM. Comment ces technologies fonctionnent-elles ? Comment établir des preuves sur de petits champs ? Cet article explorera ces détails, en se concentrant particulièrement sur le schéma Circle STARKs.

Questions fréquentes sur l'utilisation des petits champs

Lors de la création de preuves basées sur le hachage, une technique importante consiste à valider indirectement les propriétés du polynôme par l'évaluation du polynôme à des points aléatoires. Cela simplifie considérablement le processus de preuve.

Par exemple, supposons que nous devons prouver que le polynôme A satisfait A^3(x) + x - A(ωx) = x^N. Le protocole peut exiger de choisir des coordonnées aléatoires r et de prouver A(r) + r - A(ωr) = r^N. Ensuite, rétro-poussons A(r) = c, prouvant Q = (A - c)/(X - r) est un polynôme.

Pour prévenir les attaques, il est nécessaire de choisir r après que l'attaquant a fourni A. Dans un champ de 256 bits, c'est très simple : il suffit de choisir un nombre aléatoire de 256 bits. Mais dans un petit champ, il n'y a qu'environ 2 milliards de valeurs r possibles, et bien que le travail de l'attaquant soit considérable, il peut néanmoins essayer toutes les possibilités.

Il y a deux solutions :

1. Effectuer plusieurs contrôles aléatoires
2. Champ d'extension

Plusieurs vérifications simples et efficaces, mais il existe un problème d'efficacité. Les champs d'extension sont similaires aux pluriels, mais basés sur un domaine fini. Introduire une nouvelle valeur α satisfaisant une certaine relation, comme α^2 = une certaine valeur. Cela crée une nouvelle structure mathématique pouvant effectuer des calculs plus complexes sur un domaine fini. Le domaine d'extension n'est utilisé que lorsque des combinaisons linéaires aléatoires sont nécessaires, la plupart des calculs restant effectués dans le champ de base.

FRI classique

La première étape pour construire un SNARK ou un STARK est de transformer le problème de calcul en une équation polynomiale P(X,Y,Z)=0. La solution doit prouver que la valeur proposée est un polynôme raisonnable, et que son degré est limité. Cela se réalise par l'application progressive de combinaisons linéaires aléatoires :

1. Supposons qu'il y ait une valeur d'évaluation du polynôme A, il faut prouver que le degré est <2^20
2. Considérer B(x^2) = A(x) + A(-x), C(x^2) = (A(x) - A(-x))/x
3. D est une combinaison linéaire aléatoire de B et C : D = B + rC

B isolo les coefficients pairs d'A, C isolo les coefficients impairs. Données B et C, A peut être récupéré : A(x) = B(x^2) + xC(x^2). Si le degré de A < 2^20, les degrés de B et C sont respectivement le degré de A et le degré de A - 1. D comme combinaison aléatoire, le degré doit être celui de A.

FRI simplifie la vérification en réduisant la preuve d'un polynôme de degré d à une preuve d'un polynôme de degré d/2. Ce processus peut être répété plusieurs fois, chaque fois en réduisant le problème de moitié. Si la sortie à un certain stade ne correspond pas au degré attendu, alors cette vérification échouera.

FRI réduit à chaque étape le degré du polynôme et la taille de l'ensemble de points de moitié. Le premier est la clé du fonctionnement de FRI, le second permet à l'algorithme de s'exécuter très rapidement : le coût total de calcul est O(N) et non O(N*log(N)).

Pour réaliser une réduction progressive de l'espace, une correspondance deux à un est utilisée. Cette correspondance permet de réduire de moitié la taille de l'ensemble de données, et elle est répétable. En commençant par le sous-groupe multiplicatif, chaque élément x a également son multiple 2x dans l'ensemble. En prenant le carré de l'ensemble S, le nouvel ensemble S^2 conserve la même propriété. Cela permet une réduction continue de la taille de l'ensemble de données jusqu'à ce qu'il ne reste qu'une seule valeur.

La modularité de BabyBear permet à son groupe multiplicatif maximal d'inclure toutes les valeurs non nulles, d'une taille de 2^k-1. Cela convient parfaitement à la technique mentionnée ci-dessus, qui peut réduire efficacement le degré des polynômes par des mappings répétitifs. La taille du groupe multiplicatif de Mersenne31 est de 2^31-1, ne pouvant être divisé par 2 qu'une seule fois, après quoi cette technique ne peut plus être utilisée.

Le domaine Mersenne31 est très adapté aux calculs sur CPU/GPU 32 bits. Sa caractéristique de module ( comme 2^31-1) permet à de nombreux calculs de bénéficier d'opérations bit à bit efficaces : les résultats dépassant le module peuvent être réduits par décalage. La multiplication peut être traitée de manière efficace avec des instructions spécifiques au CPU. Les opérations arithmétiques de Mersenne31 sont environ 1,3 fois plus rapides que celles de BabyBear. Si FRI peut être implémenté sur Mersenne31, cela améliorera considérablement l'efficacité.

Circle FRI

L'ingéniosité des STARKs en cercle réside dans le fait que, pour un nombre premier p, il est possible de trouver un groupe de taille p ayant des caractéristiques similaires à celles d'un rapport de deux à un. Ce groupe est composé de points qui satisfont des conditions spécifiques, comme l'ensemble des points pour lesquels x^2 mod p est égal à une certaine valeur.

Ces points suivent la règle d'addition : (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1) Forme double : 2*(x,y) = (2x^2 - 1, 2xy)

Nous nous concentrons sur les points aux positions impaires sur le cercle. Tout d'abord, faisons converger tous les points sur une ligne droite : f0(x) = (F(x,y) + F(x,-y))/2

Ensuite, effectuez une combinaison linéaire aléatoire pour obtenir un polynôme unidimensionnel P(x).

À partir de la deuxième ronde, le mapping devient : f0(2x^2-1) = (F(x) + F(-x))/2

Cette application réduit la taille de l'ensemble de moitié à chaque fois. Chaque x représente deux points : (x,y) et (x,-y). (x → 2x^2 - 1) est la règle de multiplication des points. Nous convertissons les coordonnées x des deux points opposés sur le cercle en coordonnées x des points après multiplication.

FFTs circulaires

Le groupe Circle supporte également FFT, la méthode de construction est similaire à celle de FRI. La différence clé est que le Circle FFT ne traite pas des polynômes stricts, mais des espaces de Riemann-Roch : polynôme modulo cercle (x^2 + y^2 - 1 = 0).

Les coefficients de sortie de Circle FFT sont une base spécifique : {1, y, x, xy, 2x^2 - 1, 2x^2y - y, 2x^3 - x, 2x^3y - xy, 8x^4 - 8x^2 + 1...}

Les développeurs peuvent presque ignorer ce point. Les STARKs n'ont besoin de stocker les polynômes que comme un ensemble de valeurs d'évaluation. La FFT n'est utilisée que pour une faible extension : étant donné N valeurs, générer k*N valeurs sur le même polynôme.

Opérations commerciales

Les opérations courantes de STARK consistent à effectuer des calculs de quotient sur des points spécifiques. Par exemple, prouver P(x)=y peut être réalisé par les étapes suivantes :

1. Calcul du quotient : Q = (P - y)/(X - x)
2. Prouver que Q est un polynôme et non une fraction

Dans le groupe STARK de Circle, en raison de l'absence de fonction linéaire à un seul point, des techniques différentes sont nécessaires. Il est possible de construire une fonction tangente, mais elle a un multiplicité de 2 au point. Il est donc nécessaire d'évaluer à deux points pour prouver.

Si P est égal à y1 en x1 et égal à y2 en x2, nous choisissons la fonction d'interpolation L qui est égale en ces deux points. Ensuite, nous prouvons que P-L est nul en ces deux points, en prouvant que le quotient Q obtenu en divisant L par L est un polynôme.

Polynomiale de disparition

Les équations polynomiales que STARK essaie de prouver prennent généralement la forme C(P(x), P(next(x))) = Z(x) · H(x), Z(x) est identiquement égal à zéro sur le domaine d'évaluation original.

Dans STARK circulaire, la fonction correspondante est : Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

Ordre inverse

L'évaluation des polynômes dans les STARKs est généralement organisée en ordre bit inversé. Dans les STARKs en cercle, la structure de pliage est légèrement différente :

• Première étape : (x,y) associé à (x,-y)
• Deuxième étape : associer x avec -x
• Étapes suivantes : associer p et q, de sorte que Q^i(p) = -Q^i(q)

Pour ajuster l'ordre inverse, il faut inverser chaque chiffre sauf le dernier, en utilisant le dernier chiffre pour décider si les autres chiffres doivent être inversés.

Efficacité

Circle STARKs est très efficace. Les calculs impliquent généralement :

1. Arithmétique native : utilisée pour la logique métier
2. Arithmétique native : utilisée pour la cryptographie ( comme le hachage Poseidon )
3. Recherche de paramètres : méthode de calcul générale et efficace

La clé de l'efficacité réside dans l'utilisation optimale de l'espace de suivi des calculs. Ici, la taille du champ est de 2^31, le gaspillage d'espace n'est pas important. Des hachages comme Poseidon exploitent pleinement chaque bit de chaque chiffre dans n'importe quel champ.

Binius réalise un emballage de bits plus efficace en combinant des champs de différentes tailles, mais au prix d'une complexité conceptuelle plus élevée. Les STARKs de Circle sont conceptuellement relativement simples.

Conclusion

Les STARKs circulaires ne sont pas plus complexes pour les développeurs que les STARKs. La principale différence dans l'implémentation par rapport au FRI conventionnel réside dans les trois problèmes mentionnés ci-dessus. Bien que les mathématiques sous-jacentes soient complexes, cette complexité est bien dissimulée.

Comprendre les FRI et FFTs de Circle peut être une voie pour comprendre d'autres FFTs spéciaux, comme les FFTs de domaine binaire et les FFTs de courbes elliptiques.

En combinant des technologies telles que Mersenne31, BabyBear et Binius, nous nous rapprochons de la limite d'efficacité de la couche de base des STARKs. Les futures optimisations pourraient se concentrer sur :

1. Maximiser l'efficacité arithmétique des fonctions de hachage et des signatures, etc.
2. Construction récursive pour activer plus de parallélisation
3. Machine virtuelle arithmétique pour améliorer l'expérience des développeurs