Explorer Circle STARKs

Ces dernières années, la tendance de conception des protocoles STARKs s'oriente vers l'utilisation de champs plus petits. Les premières implémentations des STARKs utilisaient des champs de 256 bits, mais cette conception était moins efficace. Pour résoudre ce problème, les STARKs ont commencé à utiliser des champs plus petits, comme Goldilocks, Mersenne31 et BabyBear.

Cette transformation a considérablement amélioré la vitesse de preuve. Par exemple, Starkware peut prouver 620 000 valeurs de hachage Poseidon2 par seconde sur un ordinateur portable M3. Cela signifie que tant que l'on fait confiance à Poseidon2 en tant que fonction de hachage, le problème du ZK-EVM efficace peut être résolu.

Cet article explorera le fonctionnement de ces technologies, en se concentrant particulièrement sur le schéma Circle STARKs qui est compatible avec le champ Mersenne31.

Questions fréquentes sur l'utilisation des petits champs

Lors de la création d'une preuve basée sur un hachage, une technique importante consiste à vérifier indirectement les propriétés des polynômes par l'évaluation de polynômes en des points aléatoires. Cela simplifie considérablement le processus de preuve.

Pour éviter les attaques, nous devons choisir des points aléatoires après que l'attaquant ait fourni le polynôme. Dans un champ de 256 bits, c'est très simple, mais dans de petits champs, les valeurs aléatoires disponibles sont trop limitées, ce qui facilite l'attaque par force brute.

Il existe deux solutions :

1. Effectuer plusieurs contrôles aléatoires
2. Champs étendus

Les contrôles aléatoires multiples sont simples et efficaces, mais leur efficacité est relativement faible. Les champs d'extension sont similaires à des pluriels, permettant des calculs plus complexes sur des corps finis.

FRI régulier

La première étape du protocole FRI consiste à transformer le problème de calcul en équation polynomiale. Ensuite, il faut prouver que la solution polynomiale proposée satisfait effectivement l'équation et que son degré ne dépasse pas les exigences.

FRI vérifie en simplifiant le problème de prouver un polynôme de degré d en prouvant un polynôme de degré d/2. Ce processus peut être répété plusieurs fois, en simplifiant le problème de moitié à chaque fois.

La clé de FRI est d'utiliser un mappage un-à-deux pour réduire de moitié la taille de l'ensemble de données. Ce mappage doit pouvoir être appliqué de manière répétée, jusqu'à ce qu'il ne reste finalement qu'une seule valeur.

Circle FRI

La subtilité des STARKs circulaires réside dans le fait que, pour un nombre premier p, il est possible de trouver un groupe de taille p, possédant des caractéristiques similaires de bijection. Ce groupe est composé de points satisfaisant des conditions spécifiques.

Ces points suivent une règle d'addition, similaire aux fonctions trigonométriques ou à la multiplication des nombres complexes.

À partir du deuxième tour, le mappage change. 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, avec une méthode de construction similaire à FRI. Cependant, l'objet traité par Circle FFT n'est pas un polynôme au sens strict, mais un espace de Riemann-Roch.

En tant que développeur, vous pouvez presque ignorer ces détails. Il suffit de stocker le polynôme comme valeur d'évaluation et d'utiliser la FFT lorsque vous avez besoin d'une faible extensibilité.

Quotienting

Dans le STARK du groupe circle, en raison de l'absence de fonction linéaire à point unique, il est nécessaire d'utiliser des techniques différentes pour remplacer l'opération commerciale traditionnelle.

Nous prouvons en évaluant à deux points que l'ajout d'un point virtuel.

Polynômes disparus

Dans STARK circulaire, le polynôme d'effacement est :

Z_1(x,y) = y Z_2(x,y) = x
Z_{n+1}(x,y) = (2 * Z_n(x,y)^2) - 1

Inverser l'ordre des bits

Dans les STARKs, l'évaluation des polynômes est généralement effectuée dans l'ordre inverse. Dans les Circle STARKs, il est nécessaire d'ajuster cet ordre pour refléter sa structure de pliage particulière.

Efficacité

Circle STARKs est très efficace. L'essentiel est de tirer pleinement parti de l'espace dans le suivi des calculs pour effectuer un travail utile, sans laisser beaucoup d'inutilisé.

Comparé à Binius, le concept de Circle STARKs est plus simple, mais l'efficacité est légèrement inférieure.

Conclusion

Les STARKs de Circle ne sont pas plus complexes pour les développeurs que les STARKs conventionnels. Comprendre le FRI de Circle et les FFTs aide à comprendre d'autres FFTs spéciales.

L'optimisation future de STARK pourrait se concentrer sur :

1. Maximiser l'efficacité des fonctions de hachage et d'autres primitives cryptographiques de base
2. Construction récursive pour améliorer la parallélisation
3. Machine virtuelle arithmétique pour améliorer l'expérience de développement