Explorer les 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 de production des STARKs utilisaient des champs de 256 bits, c'est-à-dire qu'elles effectuaient des opérations modulo sur de grands nombres, ce qui rendait ces protocoles compatibles avec les signatures basées sur des courbes elliptiques. Cependant, cette conception est relativement inefficace, car en général, le traitement de ces grands nombres n'a pas d'utilité pratique et gaspille 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 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 nous sommes prêts à faire confiance à Poseidon2 en tant que fonction de hachage, nous pouvons résoudre le problème du développement d'un ZK-EVM efficace. Comment ces technologies fonctionnent-elles ? Comment ces preuves sont-elles établies sur des champs plus petits ? Comment ces protocoles se comparent-ils aux solutions telles que Binius ? Cet article explorera ces détails, en mettant particulièrement l'accent sur une solution appelée Circle STARKs, qui possède des propriétés uniques compatibles avec le champ Mersenne31.

Problèmes courants lors de l'utilisation de champs mathématiques plus petits

Lors de la création d'une preuve basée sur un hachage ( ou de tout type de preuve ), une technique très importante est de prouver en vérifiant les résultats de l'évaluation d'un polynôme à des points aléatoires, ce qui permet de valider indirectement les propriétés du polynôme. Cette méthode peut considérablement simplifier le processus de preuve, car l'évaluation à des points aléatoires est généralement beaucoup plus facile que de traiter l'ensemble du polynôme.

Par exemple, supposons qu'un système de preuve exige que vous génériez un engagement à un polynôme, A, qui doit satisfaire A^3(x) + x - A(ωx) = x^N(. C'est un type de preuve très courant dans le protocole ZK-SNARK ). Le protocole peut vous demander de choisir un coordonnée aléatoire r et de prouver A(r) + r - A(ωr) = r^N. Ensuite, en rétrogradant A(r) = c, vous prouvez que Q = (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. Les paramètres sélectionnés doivent provenir d'un ensemble suffisamment grand pour garantir que l'attaquant ne puisse pas prédire ou deviner ces paramètres, augmentant ainsi la sécurité du système.

Dans les protocoles basés sur les courbes elliptiques et les STARKs de l'année 2019, ce problème est très simple : toutes nos opérations mathématiques se font sur des nombres de 256 bits, donc nous pouvons choisir r comme un nombre aléatoire de 256 bits, et c'est tout. Cependant, dans les STARKs sur des champs plus petits, nous sommes confrontés à un problème : il n'y a environ que 2 milliards de valeurs possibles pour r, donc un attaquant cherchant à falsifier une preuve n'a besoin d'essayer que 2 milliards de fois. Bien que cela demande beaucoup de travail, c'est tout à fait réalisable pour un attaquant déterminé !

Cette question a deux solutions :

• Effectuer plusieurs contrôles aléatoires
• Champ d'extension

La méthode d'exécution de plusieurs contrôles aléatoires est la plus simple et efficace : plutôt que de vérifier à un seul endroit, il vaut mieux répéter la vérification à quatre endroits aléatoires. Cela est théoriquement faisable, mais il existe un problème d'efficacité. Si vous traitez un polynôme de degré inférieur à une certaine valeur et que vous opérez sur un domaine de taille donnée, un attaquant peut en réalité construire un polynôme malveillant qui semble normal à ces emplacements. Ainsi, la question de savoir s'ils peuvent réussir à compromettre le protocole est un problème de probabilité, ce qui nécessite d'augmenter le nombre de vérifications pour renforcer la sécurité globale et s'assurer qu'il est possible de défendre efficacement contre les attaques des attaquants.

Cela soulève une autre solution : l'extension de corps, qui est similaire aux corps multiples, mais basée sur des corps finis. Nous introduisons une nouvelle valeur, notée α, et déclarons qu'elle satisfait une certaine relation, comme α^2=some value. De cette manière, nous créons une nouvelle structure mathématique capable d'effectuer des opérations plus complexes sur des corps finis. Dans ce corps étendu, le calcul de la multiplication devient une multiplication utilisant la nouvelle valeur α. Nous pouvons désormais opérer sur des paires de valeurs dans le corps étendu, et pas seulement sur des nombres uniques. Par exemple, si nous travaillons sur des corps comme Mersenne ou BabyBear, une telle extension nous permet d'avoir plus de choix de valeurs, augmentant ainsi la sécurité. Pour augmenter encore la taille du corps, nous pouvons appliquer la même technique de manière répétée. Étant donné que nous avons déjà utilisé α, nous devons définir une nouvelle valeur, ce qui se traduit dans Mersenne31 par le choix de α tel que α^2=some value.

Grâce à l'extension de domaine, nous avons maintenant suffisamment de valeurs à choisir pour satisfaire nos exigences de sécurité. Si nous traitons des polynômes de degré inférieur à d, chaque tour peut offrir une sécurité de 104 bits. Cela signifie que nous avons une protection suffisante. Si un niveau de sécurité plus élevé est nécessaire, par exemple 128 bits, nous pouvons ajouter un certain travail de calcul supplémentaire dans le protocole pour renforcer la sécurité.

Le domaine d'extension est utilisé en pratique uniquement dans les scénarios nécessitant des combinaisons linéaires aléatoires, tels que le protocole FRI(Fast Reed-Solomon Interactive) et d'autres. La plupart des opérations mathématiques sont toujours effectuées sur le champ de base, qui est généralement un champ modulo p ou q. De plus, presque toutes les données de hachage sont effectuées sur le champ de base, de sorte que chaque valeur n'a besoin que d'un hachage de quatre octets. Cela permet de tirer parti de l'efficacité des petits champs, tout en permettant d'utiliser des champs plus grands lorsque des améliorations de sécurité sont nécessaires.

FRI régulier

Lors de la construction d'un SNARK ou d'un STARK, la première étape consiste généralement en l'arithmétisation. Cela consiste à transformer un problème de calcul arbitraire en une équation, où certaines variables et coefficients sont des polynômes. Plus précisément, cette équation ressemble généralement à P(X,Y,Z)=0, où P est un polynôme, X, Y et Z sont des paramètres donnés, et le solveur doit fournir les valeurs de X et Y. Une fois que nous avons une telle équation, la solution de cette équation correspond à la solution du problème de calcul sous-jacent.

Pour prouver que vous avez une solution, vous devez démontrer que la valeur que vous proposez est en effet un polynôme raisonnable ( et non une fraction, ou qu'à certains endroits, elle ressemble à un polynôme, mais à d'autres endroits, c'est un polynôme différent, etc. ), et que ces polynômes ont un certain degré maximum. Pour cela, nous avons utilisé une technique de combinaison linéaire aléatoire appliquée progressivement :

• Supposons que vous ayez une valeur d'évaluation d'un polynôme A, vous souhaitez prouver que son degré est inférieur à 2^20.
• Considérer le polynôme B(x^2) = A(x) + A(-x),C(x^2) = (A(x) - A(-x))/x
• D est une combinaison linéaire aléatoire de B et C, c'est-à-dire D=B+rC, où r est un coefficient aléatoire.

En essence, ce qui se passe est que B isole les coefficients pairs de A, et C isole les coefficients impairs. Étant donné B et C, vous pouvez reconstruire le polynôme original A : A(x) = B(x^2) + xC(x^2). Si le degré de A est effectivement inférieur à 2^20, alors les degrés de B et C seront respectivement le degré de A et le degré de A moins un. Parce que la combinaison des termes de degré pair et impair n'augmentera pas le degré. Puisque D est une combinaison linéaire aléatoire de B et C, le degré de D devrait également être le degré de A, ce qui vous permet de vérifier si le degré de A respecte les exigences par le degré de D.

Tout d'abord, FRI simplifie le processus de vérification en réduisant le problème de prouver que le degré d'un polynôme est d à celui de prouver que le degré d'un polynôme est d/2. Ce processus peut être répété plusieurs fois, chaque fois en réduisant le problème de moitié.

Le fonctionnement de FRI consiste à répéter ce processus de simplification. Par exemple, si vous commencez avec un polynôme de degré d, à travers une série d'étapes, vous finirez par prouver que le polynôme a un degré de d/2. Après chaque simplification, le degré du polynôme généré diminue progressivement. Si la sortie à un certain stade n'est pas le degré de polynôme attendu, alors cette vérification échouera. Si quelqu'un essaie de pousser un polynôme qui n'a pas un degré d par cette technique, alors lors de la sortie de la deuxième ronde, son degré aura une certaine probabilité de ne pas correspondre à l'attente, et dans la troisième ronde, il sera encore plus probable que cela ne corresponde pas, et la vérification finale échouera. Ce design permet de détecter et de rejeter efficacement les entrées qui ne répondent pas aux exigences. Si l'ensemble de données est égal à un polynôme de degré d dans la plupart des positions, cet ensemble de données a la possibilité de passer la vérification FRI. Cependant, pour construire un tel ensemble de données, l'attaquant doit connaître le polynôme réel, donc même une légère imperfection dans la preuve indique que le prouveur est capable de générer une "preuve réelle".

Examinons plus en détail ce qui se passe ici et les propriétés nécessaires pour que tout fonctionne correctement. À chaque étape, nous réduisons le degré du polynôme de moitié, tout en réduisant également de moitié l'ensemble des points ( que nous considérons. Le premier est essentiel pour que le protocole FRI) Fast Reed-Solomon Interactive( fonctionne correctement. Le second permet à l'algorithme de s'exécuter très rapidement : comme la taille de chaque étape est réduite de moitié par rapport à la précédente, le coût de calcul total est O)N(, et non O)N*log(N().

Pour réaliser une réduction progressive du domaine, une mapping un-à-deux a été utilisée, c'est-à-dire que chaque point est mappé à l'un des deux points. Ce mapping nous permet de réduire la taille de l'ensemble de données de moitié. Un des avantages importants de ce mapping un-à-deux est qu'il est répétable. Cela signifie que lorsque nous appliquons ce mapping, l'ensemble de résultats obtenu conserve les mêmes propriétés. Supposons que nous commençons à partir d'un sous-groupe multiplicatif ). Ce sous-groupe est un ensemble S, où chaque élément x a son multiple 2x également dans l'ensemble. Si nous effectuons une opération de mise au carré sur l'ensemble S (, c'est-à-dire que chaque élément x de l'ensemble est mappé à x^2), le nouvel ensemble S^2 conservera également les mêmes propriétés. Cette opération nous permet de continuer à réduire la taille de l'ensemble de données, jusqu'à ce qu'il ne reste finalement qu'une seule valeur. Bien que théoriquement nous puissions réduire l'ensemble de données à une seule valeur, dans la pratique, nous arrêtons généralement avant d'atteindre un ensemble plus petit.

Vous pouvez imaginer cette opération comme un processus d'étirement d'une ligne sur le cercle, par exemple, un segment ou un arc ( le long du cercle, le faisant tourner deux fois autour du cercle. Par exemple, si un point est situé à x degrés sur le cercle, alors après cette opération, il se déplacera à 2x degrés. Chaque point sur le cercle de 0 à 179 degrés a un point correspondant de 180 à 359 degrés, ces deux points se superposent. Cela signifie que lorsque vous mappez un point de x degrés à 2x degrés, il coïncide avec un point situé à x + 180 degrés. Ce processus peut être répété. Autrement dit, vous pouvez appliquer plusieurs fois cette opération de mapping, déplaçant ainsi les points sur le cercle vers leurs nouvelles positions.

![Vitalik nouvelle œuvre : exploration des STARKs Circle])https://img-cdn.gateio.im/webp-social/moments-4e2ceec842bcdcc68f5efb0e9ec2d6ab.webp(

Pour rendre la technique de mapping efficace, la taille du sous-groupe multiplicatif d'origine doit avoir une grande puissance de 2 comme facteur. BabyBear est un système avec un module spécifique, dont le module est une certaine valeur, de sorte que son plus grand sous-groupe multiplicatif contient toutes les valeurs non nulles, donc la taille du sous-groupe est 2k−1) où k est le nombre de bits du module (. Cette taille de sous-groupe est très adaptée à la technique mentionnée, car elle permet de réduire efficacement le degré du polynôme par l'application répétée de l'opération de mapping. Dans BabyBear, vous pouvez choisir un sous-groupe de taille 2^k ) ou utiliser directement l'ensemble entier (, puis appliquer la méthode FRI pour réduire progressivement le degré du polynôme à 15 et vérifier finalement le degré du polynôme. Cette méthode exploite les propriétés du module et la taille du sous-groupe multiplicatif, rendant le processus de calcul très efficace. Mersenne31 est un autre système, dont le module est une certaine valeur, de sorte que la taille du sous-groupe multiplicatif est 2^31 - 1. Dans ce cas, la taille du sous-groupe multiplicatif n'a qu'une puissance de 2 comme facteur, ce qui fait qu'il ne peut être divisé par 2 qu'une seule fois. Les traitements suivants ne sont plus applicables à la technique mentionnée, c'est-à-dire qu'il n'est pas possible d'utiliser FFT pour réduire efficacement le degré du polynôme comme dans BabyBear.

Le domaine Mersenne31 est très adapté pour effectuer des opérations arithmétiques sur des CPU/GPU de 32 bits existants. En raison des propriétés de son modulo ), par exemple 2^31 - 1(, de nombreuses opérations peuvent être effectuées à l'aide d'opérations binaires efficaces : si la somme de deux nombres dépasse le modulo, il est possible de réduire le résultat en appliquant un opérateur binaire avec le modulo.