Explorer Circle STARKs

Ces dernières années, la tendance dans la conception des protocoles STARKs est de se tourner vers l'utilisation de champs plus petits. Les premières implementations de STARKs utilisaient des champs de 256 bits, mais cette conception avait une efficacité relativement faible. Pour remédier à ce problème, les STARKs ont commencé à utiliser des champs plus petits, comme Goldilocks, Mersenne31 et BabyBear.

Cette transformation améliore considérablement la vitesse de preuve. Par exemple, Starkware peut prouver 620 000 hachages 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 d'un 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. Les Circle STARKs possèdent des propriétés uniques compatibles avec le champ Mersenne31.

Questions fréquentes sur l'utilisation des petits champs

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

Pour prévenir les attaques, nous devons choisir des points aléatoires après que l'attaquant ait fourni un polynôme. Dans les STARKs de petits champs, il n'y a qu'environ 2 milliards de points aléatoires disponibles, ce qui n'est pas sécurisé pour un attaquant déterminé.

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 des problèmes d'efficacité. Les champs étendus sont similaires aux pluriels, mais basés sur un domaine fini. Cela nous permet d'opérer dans un domaine plus large, améliorant ainsi la sécurité.

FRI Régulier

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

FRI utilise une mappage un-à-deux pour réduire de moitié la taille de l'ensemble de données. Ce mappage est répétable, ce qui nous permet de continuer à réduire la taille de l'ensemble de données.

Circle FRI

La subtilité des STARKs circulaires réside dans le fait que, étant donné un nombre premier p, il est possible de trouver un groupe de taille p, possédant une propriété de type bijection similaire. Ce groupe est composé de points satisfaisant des conditions spécifiques.

À partir du deuxième tour, le mappage change :

f_0(2x^2-1) = (F(x) + F(-x))/2

Cette transformation réduit à chaque fois la taille de l'ensemble de moitié. Chaque x représente deux points : (x,y) et (x,-y). (x→2x^2-1) est la règle de multiplication des points.

FFT Circulaires

Le groupe Circle prend également en charge FFT, dont la construction est similaire à celle de FRI. Cependant, l'objet traité par Circle FFT n'est pas un polynôme strict, mais un espace de Riemann-Roch.

En tant que développeur, on peut presque ignorer ce point. Les STARKs ne requièrent que le stockage des polynômes en tant que valeurs d'évaluation. Le seul endroit où il est nécessaire d'utiliser la FFT est pour effectuer une extension de faible degré.

Quotienting

Dans le STARK du groupe circle, en raison de l'absence de fonction linéaire réalisable par un point unique, il est nécessaire d'utiliser des techniques différentes pour remplacer les opérations commerciales traditionnelles. Il est généralement nécessaire d'évaluer à deux points pour prouver.

Polynomies évanouissantes

Dans le STARK circulaire, le polynôme de disparition 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

Les STARKs circulaires nécessitent un ajustement de l'ordre inversé pour refléter leur structure de pliage spéciale. Chaque bit, à l'exception du dernier, doit être inversé, le dernier bit étant utilisé pour déterminer si les autres bits doivent être inversés.

Efficacité

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

1. Arithmetic natif pour la logique métier
2. Arithmétique native pour la cryptographie
3. Rechercher les paramètres

L'essentiel est de tirer pleinement parti de l'espace dans le suivi des calculs. Un champ de taille 2^31 réduit l'espace gaspillé.

Conclusion

Circle STARKs n'est pas plus complexe pour les développeurs que les STARKs conventionnels. Bien que les mathématiques sous-jacentes soient complexes, elles sont essentiellement cachées pour les développeurs.

Comprendre Circle FRI et FFTs peut servir de voie pour comprendre d'autres FFTs spéciaux.

En combinant Mersenne31, BabyBear et la technologie des corps binaires, nous rapprochons de la limite d'efficacité de la couche de base des STARKs. Les directions d'optimisation futures pourraient inclure :

• Maximiser l'efficacité des fonctions de hachage par l'arithmétique
• Effectuer une construction récursive pour activer plus de parallélisation
• Machine virtuelle arithmétique pour améliorer l'expérience développeur