Explorer Circle STARKs

Ces dernières années, la conception du protocole STARKs a tendance à utiliser des champs plus petits. Les premières implémentations de STARKs utilisaient un champ de 256 bits, compatible avec les signatures basées sur des courbes elliptiques. Mais cette conception est moins efficace et le traitement de grands nombres gaspille la puissance de calcul. Pour résoudre ce problème, STARKs a commencé à se tourner vers l'utilisation de champs plus petits : d'abord Goldilocks, puis 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 nous faisons confiance à Poseidon2 en tant que fonction de hachage, nous pouvons résoudre le défi de développer un ZK-EVM efficace. Alors, comment ces technologies fonctionnent-elles ? Comment ces preuves sont-elles établies sur des champs plus petits ? Cet article explorera ces détails, en mettant particulièrement l'accent sur la solution Circle STARKs.

Problèmes courants liés à l'utilisation de champs mathématiques plus petits

Lors de la création d'une preuve basée sur un hachage, une technique importante consiste à prouver les résultats de l'évaluation d'un polynôme à des points aléatoires, validant ainsi indirectement les propriétés du polynôme. Cela peut grandement simplifier le processus de preuve.

Par exemple, supposons qu'il soit nécessaire de générer un engagement pour le polynôme A, qui doit satisfaire A^3(x) + x - A(ωx) = x^N. Le protocole peut demander de choisir des coordonnées aléatoires r et de prouver que A(r) + r - A(ωr) = r^N. Ensuite, on peut rétro-pousser A(r) = c, prouvant que Q = (A - c)/(X - r) est un polynôme.

Pour éviter les attaques, il est nécessaire de choisir r après que l'attaquant ait fourni A. Dans les protocoles basés sur des courbes elliptiques, un nombre aléatoire de 256 bits peut être choisi. Cependant, dans les STARKs à des champs plus petits, seulement environ 2 milliards de valeurs r sont disponibles, ce qui permet à l'attaquant de les casser par la méthode de force brute.

Il y a deux solutions :

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

Les vérifications aléatoires multiples sont simples et efficaces, mais présentent des problèmes d'efficacité. Les corps étendus sont similaires aux corps complexes, mais basés sur des corps finis. Une nouvelle valeur α est introduite, déclarant que α^2 = une certaine valeur. Cela permet d'effectuer des calculs plus complexes sur des corps finis. Les corps étendus ne sont utilisés que dans des scénarios comme le protocole FRI, la plupart des opérations mathématiques restant effectuées sur le champ de base.

FRL régulier

Lors de la construction de SNARK ou STARK, la première étape est l'arithmétisation, qui consiste à transformer le problème de calcul en équations polynomiales. Pour prouver qu'il existe une solution, il faut démontrer que les valeurs proposées sont des polynômes raisonnables et ont un degré maximal. Pour ce faire, on utilise la technique des combinaisons linéaires aléatoires appliquées progressivement :

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érez 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

En essence, B isole les coefficients pairs, C isole les coefficients impairs. Donnés B et C, A peut être récupéré. Si le degré de A est <2^20, les degrés de B et C sont respectivement le degré de A et le degré de A - 1. D en tant que combinaison linéaire aléatoire, le degré doit être le degré de A.

FRI simplifie le processus de vérification en réduisant le problème de prouver un polynôme de degré d à celui de prouver 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é.

Pour réaliser une réduction progressive du domaine, utilisez un mappage bijectif. Ce mappage permet de réduire de moitié la taille du jeu de données et est répétable. En commençant par le sous-groupe multiplicatif, appliquez l'opération de mise au carré à l'ensemble S, le nouvel ensemble S^2 conserve la même propriété. Cela permet une réduction continue de la taille du jeu de données, jusqu'à ce qu'il ne reste finalement qu'une seule valeur.

Le module BabyBear permet à son sous-groupe multiplicatif maximal d'inclure toutes les valeurs non nulles, la taille du sous-groupe étant de 2k-1. Il est possible de choisir un sous-groupe de taille 2^k, puis d'appliquer la méthode FRI pour réduire progressivement le degré du polynôme à 15. Le module Mersenne31 donne une taille de sous-groupe multiplicatif de 2^31-1, qui ne peut être divisé par 2 qu'une seule fois, après quoi les techniques susmentionnées ne peuvent plus être utilisées.

Le domaine Mersenne31 est adapté aux calculs sur CPU/GPU 32 bits. Ses caractéristiques de module permettent à de nombreuses opérations d'être effectuées efficacement avec des opérations sur les bits. Dans le domaine Mersenne31, les opérations arithmétiques sont environ 1,3 fois plus rapides que dans le domaine BabyBear. Si le FRI peut être réalisé dans le domaine Mersenne31, cela améliorera considérablement l'efficacité des calculs.

Circle FRI

La beauté des STARKs circulaires réside dans le fait qu'étant donné un nombre premier p, il est possible de trouver un groupe de taille p, présentant des caractéristiques similaires à celles d'un couple un à deux. Ce groupe est composé de points satisfaisant 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)

La forme double est : 2 * (x,y) = (2x^2 - 1, 2xy)

Nous nous concentrons sur les points aux positions impaires sur le cercle. D'abord, nous convergons 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 le polynôme unidimensionnel P(x).

À partir du deuxième tour, le mappage devient : f0(2x^2-1) = (F(x) + F(-x))/2

Cette transformation 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.

FFTs circulaires

Le groupe Circle prend également en charge FFT, la méthode de construction est similaire à FRI. L'objet traité par Circle FFT est l'espace 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 que de stocker les polynômes en tant qu'ensemble de valeurs d'évaluation. FFT est utilisé pour une faible expansion : étant donné N valeurs, générer k*N valeurs sur le même polynôme.

Opérations commerciales

Dans le protocole STARK, une opération courante consiste à effectuer une multiplication sur des points spécifiques. Par exemple, prouver P(x)=y:

1. Calculer le 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 point unique, il est nécessaire d'utiliser différentes techniques pour remplacer les méthodes d'opération commerciale traditionnelles. En prouvant par l'évaluation à deux points, on ajoute un point virtuel qui n'a pas besoin d'être pris en compte.

Si le polynôme P est égal à y1 en x1 et à y2 en x2, choisissez la fonction d'interpolation L qui est égale à y1 en x1 et à y2 en x2 : L = ((y2 - y1)/(x2 - x1)) * (x - x1) + y1

Ensuite, prouver que P - L est nul en ces deux points, en prouvant que le quotient Q est un polynôme en divisant L par L.

Polynomiale disparue

Dans STARK, les équations polynomiales ont généralement la forme C(P(x), P(next(x))) = Z(x) · H(x), Z(x) est nul sur tout le domaine d'évaluation.

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

Les polynômes disparus peuvent être dérivés des fonctions pliées : le STARK conventionnel utilise x → x^2, tandis que le STARK circulaire utilise x → 2x^2 - 1.

Ordre inverse

Dans les STARKs, l'évaluation des polynômes est généralement organisée dans l'ordre inverse des bits. Par exemple, lorsque n=16 : {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

Ce tri permet aux valeurs des groupes précoces dans le processus d'évaluation FRI d'être adjacentes dans le tri, économisant de l'espace.

Dans les STARKs de Circle, la structure des plis est légèrement différente. Pour ajuster l'ordre inverse afin de refléter cette structure, il faut inverser chaque bit sauf le dernier, en utilisant le dernier bit pour décider s'il faut inverser les autres bits.

Taille 16 de l'ordre inversé pliable: {0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}

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
3. Recherche des paramètres : méthode de calcul générale et efficace

L'efficacité dépend de l'utilisation optimale de l'espace de suivi des calculs. La taille du champ Circle STARKs est de 2^31, ce qui entraîne un gaspillage d'espace minimal.

Binius est meilleur que Circle STARKs, permettant de mélanger des champs de différentes tailles, ce qui permet un emballage de bits plus efficace. Mais le coût est que le concept est plus complexe, tandis que le concept de Circle STARKs est relativement simple.

Conclusion

Circle STARKs ne sont pas plus complexes pour les développeurs que les STARKs. Comprendre Circle FRI et Circle FFTs peut servir de voie pour comprendre d'autres FFTs spéciaux.

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 directions d'optimisation des STARKs à l'avenir pourraient inclure :

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