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 implémentations de STARKs utilisaient des champs de 256 bits, mais cette conception était moins efficace. Pour améliorer l'efficacité, les STARKs ont commencé à utiliser des champs plus petits, tels que Goldilocks, Mersenne31 et BabyBear.

L'utilisation de petits champs peut considérablement améliorer la vitesse de preuve. Par exemple, Starkware peut prouver 620 000 hachages Poseidon2 par seconde sur un ordinateur portable M3. Cependant, les petits champs présentent également de nouveaux défis, notamment comment garantir la sécurité dans un espace de choix limité.

Cet article explorera Circle STARKs, une nouvelle solution compatible avec le champ Mersenne31. Circle STARKs résout les problèmes de sécurité posés par les petits champs en opérant sur le groupe de points sur le cercle.

Circle FRI

L'idée centrale de Circle FRI est de définir un groupe de points de taille p sur un cercle, ce groupe a la propriété d'une correspondance deux à un. Les points du groupe satisfont à l'équation x^2 + y^2 = 1 (mod p).

Le processus de mappage de Circle FRI est le suivant :

1. D'abord, convergez tous les points sur l'axe des x.
2. Effectuer une combinaison linéaire aléatoire pour obtenir le polynôme unidimensionnel P(x)
3. À partir de la deuxième ronde, utilisez le mapping f_0(2x^2-1) = (F(x) + F(-x))/2

Ce processus réduit à chaque fois la taille de l'ensemble des points de moitié, similaire au FRI conventionnel.

FFTs circulaires

Le groupe Circle prend également en charge FFT, sa construction est similaire à celle de Circle FRI. La différence réside dans le fait que Circle FFT ne traite pas des polynômes au sens strict, mais plutôt de l'espace de Riemann-Roch.

Les coefficients de sortie de Circle FFT sont spécifiques à la base de Circle FFT : {1, y, x, xy, 2x^2 - 1, 2x^2y - y, ...}

En tant que développeur, vous pouvez ignorer ces détails mathématiques et stocker simplement le polynôme sous forme d'un ensemble de valeurs d'évaluation.

Autres détails techniques

• L'évaluation des opérations commerciales dans STARKs circulaires doit être effectuée à deux points.
• La méthode de construction des polynômes disparus est différente
• Utiliser un ordre inversé modifié pour s'adapter à la structure de pliage des STARKs de Circle

Efficacité

Circle STARKs est très efficace sur le champ premier de 31 bits :

• A pleinement tiré parti de l'espace de calcul
• Applicable pour la logique commerciale et le calcul cryptographique
• Support des opérations de tableau de recherche efficaces

En comparaison, la solution Binius est légèrement plus efficace, mais le concept est plus complexe.

Résumé

Les STARKs circulaires ne sont pas plus complexes pour les développeurs que les STARKs conventionnels. Ils offrent une solution élégante pour les STARKs à petits champs, avec l'espoir de faire progresser la technologie STARK vers une efficacité supérieure.

Les orientations d'optimisation futures des STARKs pourraient inclure :

• Optimiser les fonctions de hachage et autres primitives cryptographiques
• Améliorer la parallélisation en utilisant la construction récursive
• Améliorer l'arithmétique de la machine virtuelle pour améliorer l'expérience de développement