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 des STARKs utilisaient des champs de 256 bits, ce qui rendait ces protocoles compatibles avec les signatures basées sur des courbes elliptiques. Cependant, cette conception est moins efficace, le traitement de grands nombres gaspillait beaucoup de puissance de calcul. Pour résoudre ce problème, les STARKs ont commencé à se tourner vers l'utilisation de champs plus petits : d'abord Goldilocks, puis 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, il est possible de résoudre le problème du ZK-EVM efficace. Alors, comment ces technologies fonctionnent-elles ? Comment établir des preuves sur de petits champs ? Cet article explorera ces détails, en mettant particulièrement l'accent sur la solution Circle STARKs.
Questions fréquentes sur l'utilisation de 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 fonction des résultats d'évaluation du polynôme à des points aléatoires. Cela simplifie considérablement le processus de preuve.
Par exemple, supposons qu'il soit nécessaire de générer un engagement pour un polynôme A, satisfaisant A^3(x) + x - A(ωx) = x^N. Le protocole peut exiger de choisir des coordonnées aléatoires r et prouver que A(r) + r - A(ωr) = r^N. Ensuite, en rétro-propagation, A(r) = c, prouvant que 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 ait fourni A. Dans le protocole de grands champs, il est possible de choisir un nombre aléatoire de 256 bits comme r. Mais dans les STARKs de petits champs, il n'y a qu'environ 2 milliards de valeurs r disponibles, l'attaquant peut essayer toutes les possibilités.
Ce problème a deux solutions :
Effectuer plusieurs contrôles aléatoires
Champs d'extension
Des contrôles aléatoires répétés sont simples et efficaces, mais présentent des problèmes d'efficacité. Les champs d'extension sont similaires aux pluriels, mais basés sur un corps fini. Introduire une nouvelle valeur α qui satisfait α^2 = une certaine valeur, crée une nouvelle structure mathématique. Cela nous permet d'avoir plus de valeurs au choix, augmentant ainsi la sécurité.
FRI Régulier
La première étape du protocole FRI consiste généralement à arithmétiser, en transformant le problème de calcul en l'équation P(X,Y,Z)=0, où P est un polynôme et X, Y, Z sont des paramètres. Résoudre l'équation correspond à résoudre le problème original.
Pour prouver la validité de la solution, il faut prouver que la valeur proposée est un polynôme raisonnable et qu'il a un degré maximal. Utilisez la technique de combinaison linéaire aléatoire:
Supposons qu'il y ait des valeurs d'évaluation du polynôme A, il faut prouver que son degré est < 2^20.
D est une combinaison linéaire aléatoire de B et C : D = B + rC
Essentiellement, B isole les coefficients pairs, tandis que C isole les coefficients impairs. B et C peuvent restaurer A. 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, en tant que combinaison aléatoire, doit avoir un degré égal au degré de A.
FRI répète ce processus de simplification, simplifiant le problème de moitié à chaque fois. Ce design détecte efficacement les entrées non conformes.
Circle FRI
Voici l'ingéniosité des STARKs de Circle. Étant donné un nombre premier p, il est possible de trouver un groupe de taille p ayant des propriétés similaires à un rapport de deux pour un. Ce groupe est composé de points qui satisfont des conditions spécifiques, comme l'ensemble des points pour lesquels x^2 mod p égale 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, en convergeant tous les points en une seule ligne droite :
f0(x) = (F(x,y) + F(x,-y))/2
Puis effectuer une combinaison linéaire aléatoire pour obtenir un polynôme unidimensionnel P(x).
À partir du deuxième tour, le mappage devient :
f0(2x^2-1) = (F(x) + F(-x))/2
Cette correspondance 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 doublement des points.
FFTs circulaires
Le groupe Circle prend également en charge FFT, la méthode de construction est similaire à celle de FRI. Cependant, l'objet traité par Circle FFT est l'espace de Riemann-Roch, et non des polynômes stricts.
En tant que développeur, vous pouvez essentiellement ignorer ce point. Les STARKs nécessitent simplement de stocker le polynôme sous forme d'un ensemble de valeurs d'évaluation. La FFT est principalement utilisée pour l'extension de faible degré : étant donné N valeurs, générez k*N valeurs sur le même polynôme.
Quotienting
Dans les STARKs de Circle, en raison de l'absence de fonctions linéaires à point unique, il est nécessaire d'utiliser des techniques différentes pour remplacer les opérations commerciales traditionnelles. En prouvant par évaluation à deux points, on ajoute un point virtuel.
Si le polynôme P est égal à y1 en x1 et à y2 en x2, choisissez la fonction d'interpolation L qui est égale en ces deux points. Ensuite, montrez que P-L est nul en ces deux points, en divisant L pour obtenir le quotient Q qui est un polynôme.
Polynômes disparus
Le polynôme d'oubli dans Circle STARKs est :
Z1(x,y) = y
Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1
Cela peut être dérivé de la fonction de pliage : utiliser plusieurs fois x → 2x^2 - 1.
Inverser l'ordre des bits
Dans Circle STARKs, l'ordre de bit inverse doit être ajusté : inverser chaque bit sauf le dernier, en utilisant le dernier bit pour décider de l'inversion des autres bits.
Circle STARKs est très efficace. Les calculs impliquent généralement :
Arithmetic natif de la logique métier
L'arithmétique native de la cryptographie
Rechercher les paramètres
L'efficacité dépend de l'utilisation optimale de l'espace de suivi de calcul. Le champ de 31 bits réduit le gaspillage. Binius mélange des champs de différentes tailles avec une efficacité supérieure, mais le concept est plus complexe.
Conclusion
Les STARKs de Circle ne sont pas complexes pour les développeurs. Comprendre les mathématiques sous-jacentes prend du temps, mais la complexité est bien cachée. C'est aussi un moyen de comprendre d'autres FFTs spéciaux.
Actuellement, l'efficacité de la couche de base STARKs est proche de sa limite. Les directions d'optimisation futures pourraient inclure :
Maximiser l'efficacité des fonctions de hachage et des primitives cryptographiques de base
Construction récursive pour augmenter la parallélisation
Machine virtuelle arithmétique pour améliorer l'expérience de développement
Cette page peut inclure du contenu de tiers fourni à des fins d'information uniquement. Gate ne garantit ni l'exactitude ni la validité de ces contenus, n’endosse pas les opinions exprimées, et ne fournit aucun conseil financier ou professionnel à travers ces informations. Voir la section Avertissement pour plus de détails.
Exploration des STARKs circulaires : la révolution de la preuve efficace apportée par les petits champs
Exploration approfondie des STARKs de Circle
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 des STARKs utilisaient des champs de 256 bits, ce qui rendait ces protocoles compatibles avec les signatures basées sur des courbes elliptiques. Cependant, cette conception est moins efficace, le traitement de grands nombres gaspillait beaucoup de puissance de calcul. Pour résoudre ce problème, les STARKs ont commencé à se tourner vers l'utilisation de champs plus petits : d'abord Goldilocks, puis 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, il est possible de résoudre le problème du ZK-EVM efficace. Alors, comment ces technologies fonctionnent-elles ? Comment établir des preuves sur de petits champs ? Cet article explorera ces détails, en mettant particulièrement l'accent sur la solution Circle STARKs.
Questions fréquentes sur l'utilisation de 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 fonction des résultats d'évaluation du polynôme à des points aléatoires. Cela simplifie considérablement le processus de preuve.
Par exemple, supposons qu'il soit nécessaire de générer un engagement pour un polynôme A, satisfaisant A^3(x) + x - A(ωx) = x^N. Le protocole peut exiger de choisir des coordonnées aléatoires r et prouver que A(r) + r - A(ωr) = r^N. Ensuite, en rétro-propagation, A(r) = c, prouvant que 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 ait fourni A. Dans le protocole de grands champs, il est possible de choisir un nombre aléatoire de 256 bits comme r. Mais dans les STARKs de petits champs, il n'y a qu'environ 2 milliards de valeurs r disponibles, l'attaquant peut essayer toutes les possibilités.
Ce problème a deux solutions :
Des contrôles aléatoires répétés sont simples et efficaces, mais présentent des problèmes d'efficacité. Les champs d'extension sont similaires aux pluriels, mais basés sur un corps fini. Introduire une nouvelle valeur α qui satisfait α^2 = une certaine valeur, crée une nouvelle structure mathématique. Cela nous permet d'avoir plus de valeurs au choix, augmentant ainsi la sécurité.
FRI Régulier
La première étape du protocole FRI consiste généralement à arithmétiser, en transformant le problème de calcul en l'équation P(X,Y,Z)=0, où P est un polynôme et X, Y, Z sont des paramètres. Résoudre l'équation correspond à résoudre le problème original.
Pour prouver la validité de la solution, il faut prouver que la valeur proposée est un polynôme raisonnable et qu'il a un degré maximal. Utilisez la technique de combinaison linéaire aléatoire:
Essentiellement, B isole les coefficients pairs, tandis que C isole les coefficients impairs. B et C peuvent restaurer A. 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, en tant que combinaison aléatoire, doit avoir un degré égal au degré de A.
FRI répète ce processus de simplification, simplifiant le problème de moitié à chaque fois. Ce design détecte efficacement les entrées non conformes.
Circle FRI
Voici l'ingéniosité des STARKs de Circle. Étant donné un nombre premier p, il est possible de trouver un groupe de taille p ayant des propriétés similaires à un rapport de deux pour un. Ce groupe est composé de points qui satisfont des conditions spécifiques, comme l'ensemble des points pour lesquels x^2 mod p égale 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, en convergeant tous les points en une seule ligne droite : f0(x) = (F(x,y) + F(x,-y))/2
Puis effectuer une combinaison linéaire aléatoire pour obtenir un polynôme unidimensionnel P(x).
À partir du deuxième tour, le mappage devient : f0(2x^2-1) = (F(x) + F(-x))/2
Cette correspondance 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 doublement des points.
FFTs circulaires
Le groupe Circle prend également en charge FFT, la méthode de construction est similaire à celle de FRI. Cependant, l'objet traité par Circle FFT est l'espace de Riemann-Roch, et non des polynômes stricts.
En tant que développeur, vous pouvez essentiellement ignorer ce point. Les STARKs nécessitent simplement de stocker le polynôme sous forme d'un ensemble de valeurs d'évaluation. La FFT est principalement utilisée pour l'extension de faible degré : étant donné N valeurs, générez k*N valeurs sur le même polynôme.
Quotienting
Dans les STARKs de Circle, en raison de l'absence de fonctions linéaires à point unique, il est nécessaire d'utiliser des techniques différentes pour remplacer les opérations commerciales traditionnelles. En prouvant par évaluation à deux points, on ajoute un point virtuel.
Si le polynôme P est égal à y1 en x1 et à y2 en x2, choisissez la fonction d'interpolation L qui est égale en ces deux points. Ensuite, montrez que P-L est nul en ces deux points, en divisant L pour obtenir le quotient Q qui est un polynôme.
Polynômes disparus
Le polynôme d'oubli dans Circle STARKs est : Z1(x,y) = y Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1
Cela peut être dérivé de la fonction de pliage : utiliser plusieurs fois x → 2x^2 - 1.
Inverser l'ordre des bits
Dans Circle STARKs, l'ordre de bit inverse doit être ajusté : inverser chaque bit sauf le dernier, en utilisant le dernier bit pour décider de l'inversion des autres bits.
16 tailles de séquence inversée 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 :
L'efficacité dépend de l'utilisation optimale de l'espace de suivi de calcul. Le champ de 31 bits réduit le gaspillage. Binius mélange des champs de différentes tailles avec une efficacité supérieure, mais le concept est plus complexe.
Conclusion
Les STARKs de Circle ne sont pas complexes pour les développeurs. Comprendre les mathématiques sous-jacentes prend du temps, mais la complexité est bien cachée. C'est aussi un moyen de comprendre d'autres FFTs spéciaux.
Actuellement, l'efficacité de la couche de base STARKs est proche de sa limite. Les directions d'optimisation futures pourraient inclure :