Ces dernières années, la tendance de la conception du protocole STARKs est de se tourner vers l'utilisation de champs plus petits. Les premières implémentations de production de STARKs utilisaient des champs de 256 bits, c'est-à-dire des opérations modulo sur de grands nombres. Cependant, cette conception est peu efficace, le traitement de grands nombres gaspillant beaucoup de puissance de calcul. Pour résoudre ce problème, les STARKs ont commencé à utiliser des 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 maintenant prouver 620 000 hachages Poseidon2 par seconde sur un ordinateur portable M3. Cela signifie que tant que nous faisons confiance à Poseidon2 en tant que fonction de hachage, nous pouvons résoudre le problème du développement efficace de ZK-EVM. Alors, comment ces technologies fonctionnent-elles ? Comment les preuves sur de petits champs sont-elles construites ? Cet article explorera ces détails, en se concentrant particulièrement sur les STARKs de Circle, une solution compatible avec le champ Mersenne31.
Problèmes courants lors de l'utilisation de petits champs
Lors de la création d'une preuve basée sur un hachage, une astuce importante consiste à valider indirectement les propriétés des polynômes en évaluant le polynôme à des points aléatoires. Cela peut grandement simplifier le processus de preuve.
Par exemple, supposons que le protocole exige que vous génériez un engagement pour un polynôme A, tel que A^3(x) + x - A(ωx) = x^N. Le protocole peut exiger que vous choisissiez des coordonnées aléatoires r et prouviez que A(r)^3 + r - A(ωr) = r^N. Ensuite, déduisez A(r) = c, vous prouveQ = (A - c)/(X - r) est un polynôme.
Pour prévenir les attaques, nous devons choisir r après que l'attaquant ait fourni A. Dans les protocoles basés sur les courbes elliptiques, c'est simple : nous pouvons choisir un nombre aléatoire de 256 bits comme r. Mais dans les STARKs à petits champs, il n'y a qu'environ 2 milliards de r disponibles, et l'attaquant pourrait les craquer par épuisement.
Cette question a deux solutions :
Effectuer plusieurs contrôles aléatoires
Champ d'extension
Des contrôles aléatoires multiples sont simples et efficaces, mais peuvent poser des problèmes d'efficacité. L'extension de domaine est similaire aux nombres complexes, mais est basée sur un domaine fini. Nous introduisons une nouvelle valeur α, déclarant que α^2 = une certaine valeur. Cela crée une nouvelle structure mathématique capable d'effectuer des calculs plus complexes sur un domaine fini.
Grâce à l'extension de domaine, nous disposons d'un nombre suffisant de valeurs à choisir pour répondre aux exigences de sécurité. La plupart des opérations mathématiques sont toujours effectuées sur le champ de base, et les champs plus grands ne sont utilisés que lorsque la sécurité doit être renforcée.
FRI régulier
FRI (Fast Reed-Solomon Interactive) le protocole est une étape importante dans la construction de SNARK ou STARK. Il simplifie le processus de vérification en réduisant le problème de la preuve à un degré d à un problème de preuve à un degré d/2. Ce processus peut être répété plusieurs fois, chaque fois en simplifiant le problème de moitié.
Le fonctionnement de FRI consiste en un processus de simplification répétée. En commençant par prouver que le degré du polynôme est d, à travers une série d'étapes, on finit par prouver que le degré est d/2. Après chaque simplification, le degré du polynôme généré diminue progressivement. Si la sortie d'une étape ne correspond pas aux attentes, alors ce tour de vérification échouera.
Pour réaliser une réduction progressive du domaine, une mapping un-à-deux a été utilisée. Ce type de mapping permet de réduire de moitié la taille de l'ensemble de données tout en préservant les mêmes attributs. Cette opération peut être imaginée comme le processus d'étendre un segment le long de la circonférence d'un cercle sur deux tours.
Pour que la technique de mapping soit efficace, la taille du sous-groupe multiplicatif d'origine doit avoir une grande puissance de 2 comme facteur. Le modulo de BabyBear permet à son sous-groupe multiplicatif maximal de contenir toutes les valeurs non nulles, ce qui est idéal pour cette technique. La taille du sous-groupe multiplicatif de Mersenne31 n'a qu'un seul facteur de puissance de 2, ce qui limite son domaine d'application.
Le domaine Mersenne31 est très adapté aux opérations arithmétiques sur les CPU/GPU 32 bits, étant environ 1,3 fois plus rapide que le domaine BabyBear. Si FRI peut être implémenté dans le domaine Mersenne31, cela améliorera considérablement l'efficacité des calculs.
Circle FRI
L'ingéniosité 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 ayant des propriétés de type bijection. Ce groupe est constitué de points qui satisfont 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 de l'addition : (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1)
La forme double est : 2 * (x,y) = (2x^2 - 1, 2xy)
Circle FRI commence par converger tous les points sur une ligne droite, puis effectue une combinaison linéaire aléatoire pour obtenir un polynôme unidimensionnel P(x). À partir du deuxième tour, le mapping devient : f0(2x^2-1) = (F(x) + F(-x))/2
Cette correspondance réduit la taille de l'ensemble de moitié à chaque fois, en convertissant les coordonnées x des deux points opposés sur le cercle en les coordonnées x des points multipliés. Cela pourrait être fait dans un espace bidimensionnel, mais l'opération unidimensionnelle est plus efficace.
FFTs circulaires
Le groupe Circle prend également en charge FFT, la méthode de construction est similaire à celle de FRI. Les objets traités par Circle FFT sont des espaces de Riemann-Roch, et non des polynômes stricts. Les coefficients produits par Circle FFT sont spécifiques à la base de Circle FFT.
En tant que développeur, vous pouvez presque complètement ignorer ce point. Les STARKs n'ont besoin de stocker les polynômes que comme un ensemble de valeurs d'évaluation. Le seul endroit où la FFT est nécessaire est pour effectuer une extension de faible degré : étant donné N valeurs, générer k*N valeurs sur le même polynôme.
Quotienting
Dans les STARKs de Circle, en raison de l'absence de fonctions linéaires pouvant être appliquées en un seul point, il est nécessaire d'utiliser des techniques différentes pour remplacer l'opération commerciale traditionnelle. Nous devons prouver en évaluant à deux points, en ajoutant un point virtuel.
Si le polynôme P est égal à y1 à x1 et à y2 à x2, nous choisissons la fonction d'interpolation L, qui est égale en ces deux points. Ensuite, prouvons que P-L est nul aux deux points, en prouvant que le quotient Q obtenu en divisant L par L est un polynôme.
Polynômes disparaissant
Dans les STARKs de Circle, le polynôme d'oubli est :
Z1(x,y) = y
Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1
Cela peut être déduit à partir de la fonction de pliage : dans les Circle STARKs, on réutilise x → 2x^2 - 1. Le premier tour nécessite un traitement spécial.
Inverser l'ordre des bits
Circle STARKs utilise un ordre de bits inversé modifié, inversant chaque bit sauf le dernier, et utilise le dernier bit pour déterminer si les autres bits doivent être inversés. Cela reflète la structure de pliage unique des Circle STARKs.
Efficacité
Circle STARKs est très efficace. Les calculs impliquent généralement :
Arithmétique native : utilisée pour la logique métier
Arithmétique native : utilisée pour la cryptographie ( comme le hachage Poseidon )
Recherche de paramètres : réaliser divers calculs à l'aide d'un tableau de valeurs
Les STARKs circulaires utilisent pleinement l'espace de calcul, en gaspillant moins. Ils sont légèrement inférieurs à Binius, mais le concept est plus simple.
Conclusion
Les STARKs de Circle ne sont pas plus complexes pour les développeurs que les STARKs classiques. Comprendre le FRI de Circle et les FFTs peut aider à comprendre d'autres FFTs spéciaux. Actuellement, l'efficacité de la couche de base des STARKs est proche de sa limite, les directions d'optimisation futures pourraient inclure :
Maximiser l'efficacité arithmétique des fonctions de hachage et des signatures.
Construction récursive pour améliorer 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.
19 J'aime
Récompense
19
4
Reposter
Partager
Commentaire
0/400
NftBankruptcyClub
· 08-09 22:10
La taille de la police a diminué, mais l'efficacité a en fait augmenté...666
Voir l'originalRépondre0
GasWhisperer
· 08-09 22:08
hmm... des champs plus petits = des preuves plus rapides, mais pouvons-nous faire confiance à poseidon2 ? Je me sens en conflit à propos de ce compromis efficacité/sécurité pour être honnête.
Voir l'originalRépondre0
alpha_leaker
· 08-09 21:58
Stark est un peu effrayant.
Voir l'originalRépondre0
ChainDetective
· 08-09 21:54
Je viens de comprendre, c'est essentiellement une version simplifiée pour des calculs rapides.
Circle STARKs : Exploration et percées des preuves ZK efficaces à petit champ
Explorer Circle STARKs
Ces dernières années, la tendance de la conception du protocole STARKs est de se tourner vers l'utilisation de champs plus petits. Les premières implémentations de production de STARKs utilisaient des champs de 256 bits, c'est-à-dire des opérations modulo sur de grands nombres. Cependant, cette conception est peu efficace, le traitement de grands nombres gaspillant beaucoup de puissance de calcul. Pour résoudre ce problème, les STARKs ont commencé à utiliser des 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 maintenant prouver 620 000 hachages Poseidon2 par seconde sur un ordinateur portable M3. Cela signifie que tant que nous faisons confiance à Poseidon2 en tant que fonction de hachage, nous pouvons résoudre le problème du développement efficace de ZK-EVM. Alors, comment ces technologies fonctionnent-elles ? Comment les preuves sur de petits champs sont-elles construites ? Cet article explorera ces détails, en se concentrant particulièrement sur les STARKs de Circle, une solution compatible avec le champ Mersenne31.
Problèmes courants lors de l'utilisation de petits champs
Lors de la création d'une preuve basée sur un hachage, une astuce importante consiste à valider indirectement les propriétés des polynômes en évaluant le polynôme à des points aléatoires. Cela peut grandement simplifier le processus de preuve.
Par exemple, supposons que le protocole exige que vous génériez un engagement pour un polynôme A, tel que A^3(x) + x - A(ωx) = x^N. Le protocole peut exiger que vous choisissiez des coordonnées aléatoires r et prouviez que A(r)^3 + r - A(ωr) = r^N. Ensuite, déduisez A(r) = c, vous prouveQ = (A - c)/(X - r) est un polynôme.
Pour prévenir les attaques, nous devons choisir r après que l'attaquant ait fourni A. Dans les protocoles basés sur les courbes elliptiques, c'est simple : nous pouvons choisir un nombre aléatoire de 256 bits comme r. Mais dans les STARKs à petits champs, il n'y a qu'environ 2 milliards de r disponibles, et l'attaquant pourrait les craquer par épuisement.
Cette question a deux solutions :
Des contrôles aléatoires multiples sont simples et efficaces, mais peuvent poser des problèmes d'efficacité. L'extension de domaine est similaire aux nombres complexes, mais est basée sur un domaine fini. Nous introduisons une nouvelle valeur α, déclarant que α^2 = une certaine valeur. Cela crée une nouvelle structure mathématique capable d'effectuer des calculs plus complexes sur un domaine fini.
Grâce à l'extension de domaine, nous disposons d'un nombre suffisant de valeurs à choisir pour répondre aux exigences de sécurité. La plupart des opérations mathématiques sont toujours effectuées sur le champ de base, et les champs plus grands ne sont utilisés que lorsque la sécurité doit être renforcée.
FRI régulier
FRI (Fast Reed-Solomon Interactive) le protocole est une étape importante dans la construction de SNARK ou STARK. Il simplifie le processus de vérification en réduisant le problème de la preuve à un degré d à un problème de preuve à un degré d/2. Ce processus peut être répété plusieurs fois, chaque fois en simplifiant le problème de moitié.
Le fonctionnement de FRI consiste en un processus de simplification répétée. En commençant par prouver que le degré du polynôme est d, à travers une série d'étapes, on finit par prouver que le degré est d/2. Après chaque simplification, le degré du polynôme généré diminue progressivement. Si la sortie d'une étape ne correspond pas aux attentes, alors ce tour de vérification échouera.
Pour réaliser une réduction progressive du domaine, une mapping un-à-deux a été utilisée. Ce type de mapping permet de réduire de moitié la taille de l'ensemble de données tout en préservant les mêmes attributs. Cette opération peut être imaginée comme le processus d'étendre un segment le long de la circonférence d'un cercle sur deux tours.
Pour que la technique de mapping soit efficace, la taille du sous-groupe multiplicatif d'origine doit avoir une grande puissance de 2 comme facteur. Le modulo de BabyBear permet à son sous-groupe multiplicatif maximal de contenir toutes les valeurs non nulles, ce qui est idéal pour cette technique. La taille du sous-groupe multiplicatif de Mersenne31 n'a qu'un seul facteur de puissance de 2, ce qui limite son domaine d'application.
Le domaine Mersenne31 est très adapté aux opérations arithmétiques sur les CPU/GPU 32 bits, étant environ 1,3 fois plus rapide que le domaine BabyBear. Si FRI peut être implémenté dans le domaine Mersenne31, cela améliorera considérablement l'efficacité des calculs.
Circle FRI
L'ingéniosité 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 ayant des propriétés de type bijection. Ce groupe est constitué de points qui satisfont 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 de l'addition : (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1) La forme double est : 2 * (x,y) = (2x^2 - 1, 2xy)
Circle FRI commence par converger tous les points sur une ligne droite, puis effectue une combinaison linéaire aléatoire pour obtenir un polynôme unidimensionnel P(x). À partir du deuxième tour, le mapping devient : f0(2x^2-1) = (F(x) + F(-x))/2
Cette correspondance réduit la taille de l'ensemble de moitié à chaque fois, en convertissant les coordonnées x des deux points opposés sur le cercle en les coordonnées x des points multipliés. Cela pourrait être fait dans un espace bidimensionnel, mais l'opération unidimensionnelle est plus efficace.
FFTs circulaires
Le groupe Circle prend également en charge FFT, la méthode de construction est similaire à celle de FRI. Les objets traités par Circle FFT sont des espaces de Riemann-Roch, et non des polynômes stricts. Les coefficients produits par Circle FFT sont spécifiques à la base de Circle FFT.
En tant que développeur, vous pouvez presque complètement ignorer ce point. Les STARKs n'ont besoin de stocker les polynômes que comme un ensemble de valeurs d'évaluation. Le seul endroit où la FFT est nécessaire est pour effectuer une extension de faible degré : étant donné N valeurs, générer k*N valeurs sur le même polynôme.
Quotienting
Dans les STARKs de Circle, en raison de l'absence de fonctions linéaires pouvant être appliquées en un seul point, il est nécessaire d'utiliser des techniques différentes pour remplacer l'opération commerciale traditionnelle. Nous devons prouver en évaluant à deux points, en ajoutant un point virtuel.
Si le polynôme P est égal à y1 à x1 et à y2 à x2, nous choisissons la fonction d'interpolation L, qui est égale en ces deux points. Ensuite, prouvons que P-L est nul aux deux points, en prouvant que le quotient Q obtenu en divisant L par L est un polynôme.
Polynômes disparaissant
Dans les STARKs de Circle, le polynôme d'oubli est : Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1
Cela peut être déduit à partir de la fonction de pliage : dans les Circle STARKs, on réutilise x → 2x^2 - 1. Le premier tour nécessite un traitement spécial.
Inverser l'ordre des bits
Circle STARKs utilise un ordre de bits inversé modifié, inversant chaque bit sauf le dernier, et utilise le dernier bit pour déterminer si les autres bits doivent être inversés. Cela reflète la structure de pliage unique des Circle STARKs.
Efficacité
Circle STARKs est très efficace. Les calculs impliquent généralement :
Les STARKs circulaires utilisent pleinement l'espace de calcul, en gaspillant moins. Ils sont légèrement inférieurs à Binius, mais le concept est plus simple.
Conclusion
Les STARKs de Circle ne sont pas plus complexes pour les développeurs que les STARKs classiques. Comprendre le FRI de Circle et les FFTs peut aider à comprendre d'autres FFTs spéciaux. Actuellement, l'efficacité de la couche de base des STARKs est proche de sa limite, les directions d'optimisation futures pourraient inclure :