Titre original : « Exploration du cercle STARKs »
Écrit par : Vitalik Buterin, co-fondateur d'Ethereum
Compilé par : Chris, Techub News
Le prérequis pour comprendre cet article est que vous compreniez déjà les principes de base des SNARK et des STARK. Si cela ne vous est pas familier, je vous suggère de lire les premières parties de cet article pour en comprendre les bases.
Ces dernières années, la tendance dans la conception des protocoles STARK a été d’utiliser des champs plus petits. Les premières implémentations de production de STARK utilisaient des champs de 256 bits, c'est-à-dire une arithmétique modulo sur de grands nombres (par exemple 21888...95617), ce qui rendait ces protocoles compatibles avec les signatures basées sur des courbes elliptiques. Cependant, l'efficacité de cette conception est relativement faible. Dans des circonstances normales, le traitement et le calcul de ces grands nombres n'ont aucune utilité pratique et gaspilleront beaucoup de puissance de calcul, comme le traitement de X (représentant un certain nombre) et le traitement de quatre fois X. , traitement Seul un neuvième du temps de calcul est requis. Pour résoudre ce problème, les STARK ont commencé à se déplacer vers des domaines plus petits : d'abord Goldilocks, puis Mersenne31 et BabyBear.
Ce changement a amélioré les vitesses de preuve, par exemple Starkware étant capable de prouver 620 000 hachages Poséidon2 par seconde sur un ordinateur portable M3. Cela signifie que tant que nous sommes prêts à faire confiance à Poséidon2 comme fonction de hachage, nous pouvons résoudre le problème difficile du développement d'un ZK-EVM efficace. Alors, comment fonctionnent ces technologies ? Comment ces preuves s’appuient-elles sur des champs plus petits ? Comment ces protocoles se comparent-ils à des solutions comme Binius ? Cet article explorera ces détails, en se concentrant spécifiquement sur un schéma appelé Circle STARK (implémenté dans le stwo de Starkware, le plonky3 de Polygon et ma propre version en Python), qui ont la propriété unique d'être compatibles avec les champs Mersenne31.
Problèmes courants lorsque l'on travaille avec des champs mathématiques plus petits
Une astuce très importante lors de la création de preuves basées sur le hachage (ou de toutes sortes) est de pouvoir vérifier indirectement les propriétés d'un polynôme en évaluant le polynôme à des points aléatoires. Cette approche peut grandement simplifier le processus de preuve, car l’évaluation en points aléatoires est généralement beaucoup plus facile que le traitement du polynôme entier.
Par exemple, supposons qu'un système de preuve vous oblige à générer un engagement envers un polynôme A, qui doit satisfaire A^3 (x) + x - A (\omega*x) = x^N (un polynôme très courant dans le ZK -Type de preuve de protocole SNARK). Le protocole pourrait vous demander de choisir une coordonnée aléatoire et de prouver que A (r) + r - A (\omega*r) = r^N. Ensuite, revenez en arrière jusqu'à A (r) = c, et vous prouvez que Q = \frac {A - c}{X - r} est un polynôme.
Si vous connaissez à l’avance les détails ou les composants internes des protocoles, vous pourrez peut-être trouver des moyens de les contourner ou de les pirater. Des actions ou méthodes spécifiques pour y parvenir peuvent être mentionnées ensuite. Par exemple, pour satisfaire l’équation A (\omega * r), vous pouvez définir A (r) sur 0 et laisser A être une ligne droite passant par ces deux points.
Pour empêcher ces attaques, nous devons choisir r après que l'attaquant a fourni A (Fiat-Shamir est une technique utilisée pour améliorer la sécurité du protocole en définissant certains paramètres sur une valeur de hachage pour éviter les attaques. Choisissez Les paramètres doivent provenir d'un nombre suffisamment grand. défini pour garantir qu’un attaquant ne peut pas prédire ou deviner ces paramètres, améliorant ainsi la sécurité du système.
Dans les protocoles basés sur des courbes elliptiques et les STARK de la période 2019, le problème est simple : toutes nos opérations mathématiques sont effectuées sur des nombres de 256 bits, nous pouvons donc choisir r comme étant un nombre aléatoire de 256 bits, de sorte que . Cependant, dans les STARK sur des champs plus petits, nous rencontrons un problème : il n'y a qu'environ 2 milliards de valeurs possibles de r parmi lesquelles choisir, donc un attaquant qui veut forger une preuve n'a besoin que d'essayer 2 milliards de fois, ce qui est un beaucoup de travail, mais pour un attaquant déterminé, cela reste tout à fait possible !
Il y a deux solutions pour ce problème:
Effectuer plusieurs contrôles aléatoires
Non
Le moyen le plus simple et le plus efficace d'effectuer plusieurs contrôles aléatoires est le suivant : au lieu de vérifier à une coordonnée, répétez la vérification à quatre coordonnées aléatoires. C'est théoriquement possible, mais cela pose des problèmes d'efficacité. Si vous avez affaire à un polynôme de degré inférieur à une certaine valeur et que vous opérez sur un domaine d'une certaine taille, un attaquant peut en fait construire un polynôme malveillant qui semble normal à ces emplacements. Par conséquent, savoir s’ils réussiront à enfreindre le protocole est une question probabiliste. Le nombre de séries de contrôles doit donc être augmenté pour améliorer la sécurité globale et garantir que les attaquants peuvent être efficacement défendus contre les attaques.
Cela conduit à une autre solution : les champs étendus sont comme des nombres complexes, mais sont basés sur des champs finis. Nous introduisons une nouvelle valeur, notée α\alphaα, et déclarons qu'elle satisfait une certaine relation, telle que α2=some value\alpha^2 = \text {some value}α2=some value. De cette façon, nous créons une nouvelle structure mathématique capable d’effectuer des opérations plus complexes sur des corps finis. Dans ce domaine étendu, le calcul de la multiplication devient une multiplication utilisant la nouvelle valeur α\alphaα. Nous pouvons désormais opérer sur des paires de valeurs dans un domaine étendu, et non plus uniquement sur des nombres simples. Par exemple, si nous travaillons sur un domaine comme Mersenne ou BabyBear, une telle extension nous permet d'avoir plus de choix de valeurs, améliorant ainsi la sécurité. Pour augmenter encore la taille du champ, nous pouvons appliquer à plusieurs reprises la même technique. Puisque nous avons déjà utilisé α\alphaα, nous devons définir une nouvelle valeur, qui dans Mersenne31 est représentée en choisissant α\alphaα tel que α2=une valeur\alpha^2 = \text {une valeur}α2=une valeur.
Code (vous pouvez l'améliorer avec Karatsuba)
En étendant le domaine, nous disposons désormais de suffisamment de valeurs parmi lesquelles choisir qui répondent à nos besoins de sécurité. Si vous avez affaire à des polynômes de degré inférieur à ddd, cela fournit 104 bits de sécurité par tour. Cela signifie que nous disposons d’une sécurité adéquate. Si un niveau de sécurité plus élevé est requis, tel que 128 bits, nous pouvons ajouter un travail informatique supplémentaire au protocole pour améliorer la sécurité.
Les domaines étendus ne sont réellement utilisés que dans les protocoles FRI (Fast Reed-Solomon Interactive) et d'autres scénarios nécessitant des combinaisons linéaires aléatoires. La plupart des calculs sont toujours effectués sur les champs sous-jacents, qui sont généralement des champs modulo ppp ou qqq. De plus, presque toutes les données hachées sont effectuées sur les champs sous-jacents, donc seuls quatre octets par valeur sont hachés. Cela permet de tirer parti de l'efficacité des petits champs tout en permettant l'utilisation de champs plus grands lorsque des améliorations de sécurité sont nécessaires.
VEN régulier
Lors de la construction d'un SNARK ou d'un STARK, la première étape est généralement l'arithmétisation. Il s’agit de la conversion de tout problème informatique en une équation dans laquelle certaines variables et coefficients sont des polynômes. Plus précisément, cette équation ressemblera généralement à P (X, Y, Z) = 0 P (X, Y, Z) = 0 P (X, Y, Z) = 0, où P est un polynôme et Z est un paramètre donné et le le solveur doit fournir des valeurs X et Y. Une fois que vous avez une telle équation, la solution de cette équation correspond à la solution du problème informatique sous-jacent.
Pour prouver que vous avez une solution, vous devez montrer que les valeurs que vous proposez sont bien des polynômes légitimes (par opposition aux fractions, ou ressemblent à un polynôme à certains endroits et à un polynôme différent à d'autres, etc.), Et ces polynômes ont un certain degré maximum. Pour ce faire, nous utilisons une technique de combinaison linéaire stochastique appliquée par étapes :
Supposons que vous ayez une évaluation d'un polynôme A et que vous vouliez prouver que son degré est inférieur à 2^{20}
Considérons le polynôme B (x^2) = A (x) + A (-x), C (x^2) = \frac {A (x) - A (-x)}{x}
D est une combinaison linéaire aléatoire de B et C, c'est-à-dire D=B+rCD = B + rCD=B+rC, où r est un coefficient aléatoire.
Essentiellement, ce qui se passe, c'est que B isole les coefficients pairs de A et ? isole les coefficients impairs. Étant donné B et C, vous pouvez récupérer le polynôme d'origine 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 1. Parce que la combinaison de termes pairs et impairs n’augmente pas le degré. Puisque D est une combinaison linéaire aléatoire de B et C, le degré de D doit également être le degré de A, ce qui vous permet d'utiliser le degré de D pour vérifier que le degré de A répond aux exigences.
Premièrement, FRI simplifie le processus de vérification en réduisant le problème de la preuve d'un polynôme de degré d au problème de la preuve d'un polynôme de degré d/2. Ce processus peut être répété plusieurs fois, simplifiant le problème de moitié à chaque fois.
FRI fonctionne en répétant ce processus de simplification. Par exemple, si vous commencez par prouver que le degré d’un polynôme est d, vous finirez par prouver, à travers une série d’étapes, que le degré du polynôme est d/2. Après chaque simplification, le degré du polynôme résultant diminue progressivement. Si le résultat d’une étape n’est pas du degré polynomial attendu, alors cette série de vérifications échouera. Si quelqu'un essaie de pousser un polynôme qui n'est pas de degré d grâce à cette technique, alors au deuxième tour de sortie, son degré ne répondra pas aux attentes avec une certaine probabilité, et au troisième tour il sera plus susceptible d'être incohérent, et enfin Le contrôle échouera. Cette conception peut détecter et rejeter efficacement les entrées qui ne répondent pas aux exigences. Un ensemble de données est susceptible de réussir la validation FRI s’il est égal à un polynôme de degré d dans la plupart des emplacements. Cependant, pour construire un tel ensemble de données, l'attaquant doit connaître les polynômes réels, de sorte que même une preuve légèrement erronée montre que le prouveur est capable de générer une « vraie » preuve.
Examinons de plus près ce qui se passe ici et les propriétés nécessaires pour que tout cela fonctionne. A chaque étape, nous réduisons de moitié le degré du polynôme, et réduisons également de moitié l'ensemble de points (l'ensemble de points qui nous intéresse). Le premier est essentiel au bon fonctionnement du protocole FRI (Fast Reed-Solomon Interactive). Ce dernier rend l'algorithme extrêmement rapide : puisque la taille de chaque tour est réduite de moitié par rapport au tour précédent, le coût de calcul total est de O (N) au lieu de O (N*log (N)).
Pour obtenir une réduction progressive du domaine, une cartographie deux à un est utilisée, c'est-à-dire que chaque point est mappé à l'un des deux points. Cette cartographie nous permet de réduire de moitié la taille de l'ensemble de données. Un avantage important de ce mappage deux-à-un est qu’il est reproductible. Autrement dit, lorsque nous appliquons ce mappage, le jeu de résultats résultant conserve toujours les mêmes propriétés. Supposons que nous commençons par un sous-groupe multiplicatif. Ce sous-groupe est un ensemble S où chaque élément x a également son multiple 2x dans l'ensemble. Si vous mettez l'ensemble S au carré (c'est-à-dire mappez chaque élément x de l'ensemble à 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. Alors qu’en théorie nous pourrions réduire l’ensemble de données à une seule valeur, en pratique nous nous arrêtons généralement avant d’atteindre un ensemble plus petit.
Vous pouvez considérer cette opération comme le processus d'étirement d'une ligne (par exemple, un segment de ligne ou un arc) sur la circonférence d'un cercle afin qu'elle fasse deux révolutions autour du cercle. Par exemple, si un point est à x degrés sur la circonférence, il se déplacera de 2x degrés après cette opération. Chaque point du cercle de 0 à 179 degrés correspond à un point de 180 à 359 degrés, et ces deux points coïncideront. Cela signifie que lorsque vous cartographiez un point de x degrés à 2x degrés, il coïncidera avec une position à x+180 degrés. Ce processus peut être répété. Autrement dit, vous pouvez appliquer cette opération de mappage plusieurs fois, en déplaçant à chaque fois les points du cercle vers leurs nouvelles positions.
Pour que la technique de cartographie soit efficace, la taille du sous-groupe multiplicatif d'origine doit avoir de grandes puissances de 2 comme facteurs. BabyBear est un système avec un certain module tel que son sous-groupe multiplicatif maximal contient toutes les valeurs non nulles, de sorte que la taille du sous-groupe soit 2k−1 (où k est le nombre de chiffres dans le module). Les sous-groupes de cette taille sont bien adaptés à la technique ci-dessus car elle permet une réduction efficace du degré du polynôme par l'application répétée de l'opération de cartographie. Dans BabyBear, vous pouvez sélectionner un sous-groupe de taille 2 ^ k (ou simplement utiliser l'ensemble complet), puis appliquer la méthode FRI pour réduire progressivement le degré du polynôme à 15 et vérifier le degré du polynôme à la fin. Cette méthode tire parti des propriétés du module et de 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 valeur telle que la taille du sous-groupe multiplicatif est de 2 ^ 31 - 1. Dans ce cas, la taille du sous-groupe multiplicatif n'a comme facteur qu'une puissance de 2, ce qui permet de le diviser par 2 une seule fois. Le traitement ultérieur n'est plus adapté aux techniques ci-dessus, c'est-à-dire qu'il n'est pas possible d'utiliser la FFT pour une réduction efficace du degré polynomial comme BabyBear.
Les champs Mersenne31 sont bien adaptés aux opérations arithmétiques sur les opérations CPU/GPU 32 bits existantes. En raison de ses propriétés de module (telles que 2^{31} - 1), de nombreuses opérations peuvent être effectuées à l'aide d'opérations binaires efficaces : si le résultat de l'addition de deux nombres dépasse le module, le résultat peut être décalé par l'opération de module pour le réduire. à une plage appropriée. L'opération de déplacement est une opération très efficace. Dans les opérations de multiplication, des instructions spéciales du processeur (souvent appelées instructions de décalage d'ordre élevé) sont utilisées pour traiter le résultat. Ces instructions peuvent calculer efficacement la partie d'ordre élevé de la multiplication, améliorant ainsi l'efficacité de l'opération. Dans le domaine Mersenne31, les opérations arithmétiques sont environ 1,3 fois plus rapides que dans le domaine BabyBear en raison des propriétés décrites ci-dessus. Mersenne31 offre une plus grande efficacité de calcul. Si FRI peut être implémenté dans le domaine Mersenne31, cela améliorera considérablement l'efficacité des calculs et rendra les applications FRI plus efficaces.
Cercle VEN
C'est ce qui est intéressant avec les Circle STARK, étant donné un nombre premier p, vous pouvez trouver une population de taille p qui a des propriétés similaires de deux à un. Cette population est composée de tous les points qui satisfont à certaines conditions, par exemple l'ensemble des points où x^2 mod p est égal à une certaine valeur.
Ces points suivent un modèle additif, qui peut vous sembler familier si vous avez récemment fait quelque chose en rapport avec la trigonométrie ou la multiplication complexe.
(x_1, y_1) + (x_2, y_2) = (x_1x_2 - y_1y_2, x_1y_2 + x_2y_1)
La forme doublée est :
2 * (x, y) = (2x^2 - 1, 2xy)
Concentrons-nous maintenant sur les points impairs de ce cercle :
Tout d’abord, nous faisons converger tous les points vers une ligne droite. La forme équivalente des formules B (x²) et C (x²) que nous utilisons dans FRI ordinaire est :
f_0 (x) = \frac {F (x,y) + F (x,-y)}{2}
Nous pouvons alors effectuer des combinaisons linéaires aléatoires pour obtenir un polynôme unidimensionnel P(x) défini sur un sous-ensemble des droites x :
À partir du deuxième tour, la cartographie change :
f_0 (2x^2-1) = \frac {F (x) + F (-x)}{2}
Ce mappage réduit en fait la taille de l'ensemble ci-dessus de moitié à chaque fois, ce qui se passe ici, c'est que chaque x représente deux points dans un sens : (x, y) et (x, -y). Et (x → 2x^2 - 1) est la règle de doublement de points ci-dessus. Par conséquent, nous convertissons les coordonnées x de deux points opposés sur le cercle en coordonnées x du point multiplié.
Par exemple, si nous prenons la deuxième valeur du cercle en partant de la droite, 2, et appliquons la cartographie 2 → 2 (2^2) - 1 = 7, nous obtenons 7 comme résultat. Si nous revenons au cercle d'origine, (2, 11) est le troisième point en partant de la droite, de sorte qu'en doublant nous obtenons le sixième point en partant de la droite, qui est (7, 13).
Cela aurait pu être fait en deux dimensions, mais opérer en une seule dimension rend le processus plus efficace.
FFT de cercle
Un algorithme étroitement lié au FRI est la FFT, qui convertit n évaluations d'un polynôme de degré inférieur à n en n coefficients de ce polynôme. Le processus de FFT est similaire à FRI, sauf qu'au lieu de générer des combinaisons linéaires aléatoires f_0 et f_1 à chaque étape, FFT exécute de manière récursive une FFT demi-taille sur celles-ci et prend la sortie de FFT (f_0) comme coefficients pairs, traite la sortie de FFT (f_1) comme coefficients impairs.
Les groupes de cercle prennent également en charge les FFT, qui sont construites de la même manière que les FRI. Cependant, une différence clé est que Circle FFT (et Circle FRI) traitent des objets qui ne sont pas strictement des polynômes. Au lieu de cela, ce sont ce qu'on appelle mathématiquement des espaces de Riemann-Roch : dans ce cas, les polynômes sont modulo circulaires ( x^2 + y^2 - 1 = 0 ). Autrement dit, nous traitons tout multiple de x^2 + y^2 - 1 comme zéro. Une autre façon de voir les choses est la suivante : nous permettons uniquement à y d'être élevé à une puissance : dès qu'un terme y^2 apparaît, nous le remplaçons par 1 - x^2 .
Cela signifie également que les coefficients produits par Circle FFT ne sont pas des monômes comme le FRI ordinaire (par exemple, si le FRI régulier produit [6, 2, 8, 3], alors nous savons que cela signifie P (x) = 3x^3 + 8x ^2 + 2x + 6). En revanche, les coefficients de la Circle FFT sont spécifiques à la base Circle FFT : {1, y, x, xy, 2x^2 - 1, 2x^2y - y, 2x^3 - x, 2x^3y - xy, 8x^4 - 8x^2 + 1...}
La bonne nouvelle est qu’en tant que développeur, vous pouvez presque complètement ignorer cela. STARKs ne vous oblige jamais à connaître les coefficients. Au lieu de cela, vous stockez simplement le polynôme sous la forme d'un ensemble de valeurs d'évaluation sur un domaine spécifique. Le seul endroit où vous devez utiliser la FFT est de faire une extension de bas degré (similaire à l'espace de Riemann-Roch) : étant donné les valeurs N, générez des valeurs k*N, le tout sur le même polynôme. Dans ce cas, vous pouvez utiliser une FFT pour générer les coefficients, ajouter (k-1) n zéros à ces coefficients, puis utiliser la FFT inverse pour obtenir un plus grand ensemble de valeurs évaluées.
Les Circle FFT ne sont pas le seul type de FFT spécial. Les FFT à courbe elliptique sont plus puissantes car elles peuvent fonctionner sur n'importe quel champ fini (champ premier, champ binaire, etc.). Cependant, ECFFT est plus complexe et moins efficace, donc puisque nous pouvons utiliser Circle FFT sur p = 2^{31}-1, nous choisissons de l'utiliser.
À partir de là, nous plongerons dans certains des détails les plus obscurs qui rendent la mise en œuvre de Circle STARK différente des STARK classiques.
Quotientage
Dans le protocole STARK, une opération courante consiste à effectuer des opérations de quotient sur des points spécifiques. Ces points peuvent être sélectionnés délibérément ou aléatoirement. Par exemple, si vous souhaitez prouver que P (x) = y, vous pouvez le faire en suivant ces étapes :
Calculer le quotient : Étant donné un polynôme P (x) et une constante y, calculez le quotient Q ={P - y}/{X - x}, où X est le point choisi.
Prouver des polynômes : prouver que Q est un polynôme et non une fraction. De cette façon, il est prouvé que P (x) = y est vrai.
De plus, dans le protocole DEEP-FRI, les points d'évaluation sont sélectionnés de manière aléatoire pour réduire le nombre de branches Merkle, améliorant ainsi la sécurité et l'efficacité du protocole FRI.
Lorsqu'il s'agit du protocole STARK du groupe de cercles, puisqu'il n'existe pas de fonction linéaire pouvant passer par un seul point, différentes techniques doivent être utilisées pour remplacer la méthode traditionnelle d'opération de quotient. Cela nécessite souvent de concevoir de nouveaux algorithmes utilisant les propriétés géométriques uniques des groupes de cercles.
Dans un groupe de cercles, vous pouvez construire une fonction tangente tangente à un certain point (P_x, P_y), mais cette fonction aura une multiplicité 2 passant par le point, c'est-à-dire qu'un polynôme devient le A multiple d'une fonction linéaire qui doit satisfaire à des conditions plus strictes que d’être simplement nul à ce stade. Par conséquent, vous ne pouvez pas simplement prouver les résultats de l’évaluation à un moment donné. Alors, comment pouvons-nous gérer cela ?
Nous avons dû accepter ce défi et le prouver en évaluant sur deux points, ajoutant ainsi un point factice sur lequel nous n'avions pas besoin de nous concentrer.
Fonction de ligne : hache + par + c. Si vous la transformez en équation, en la forçant à être égale à 0, vous la reconnaîtrez peut-être comme une ligne sous ce qu'on appelle la forme standard en mathématiques au secondaire.
Si nous avons un polynôme P qui est égal à y_1 en x_1 et y_2 en x_2, nous pouvons choisir une fonction d'interpolation L qui est égale à y_1 en x_1 et y_2 en x_2. Cela peut être exprimé simplement par L = \frac {y_2 - y_1}{x_2 - x_1} \cdot (x - x_1) + y_1.
Nous prouvons ensuite que P est égal à y_1 en x_1 et y_2 en x_2 en soustrayant L (ce qui rend P - L nul aux deux points) et par L (c'est-à-dire une fonction linéaire entre x_2 - x_1) Divisez par L pour prouver que le quotient Q est un polynôme.
Polynômes en voie de disparition
Dans STARK, l'équation polynomiale que vous essayez de prouver ressemble généralement à C (P (x), P ({next}(x))) = Z (x) ⋅ H (x) , où Z (x) est un A polynôme égal à zéro sur tout le domaine d’évaluation d’origine. Dans STARK normal, cette fonction est x^n - 1. Dans la circulaire STARK, la fonction correspondante est :
Z_1 (x,y) = y
Z_2 (x,y) = x
Z_{n+1}(x,y) = (2 * Z_n (x,y)^2) - 1
Notez que vous pouvez dériver le polynôme de disparition de la fonction de pliage : dans STARK normal, vous réutilisez x → x^2 , tandis que dans STARK circulaire, vous réutilisez x → 2x^2 - 1 . Cependant, pour le premier tour, vous procédez différemment car le premier tour est spécial.
Ordre des bits inversé
Dans les STARK, les polynômes ne sont généralement pas évalués dans l'ordre « naturel » (par exemple P (1), P (ω), P (ω2),…, P (ωn−1)), mais dans ce que j'appelle l'inverse Arrangé en ordre des bits inversé :
P (\oméga^{\frac {3n}{8}})
Si nous définissons n = 16 et nous concentrons uniquement sur les puissances de ω auxquelles nous évaluons, la liste ressemble à ceci :
{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
Ce tri a la propriété clé que les valeurs regroupées au début du processus d'évaluation FRI deviennent adjacentes dans le tri. Par exemple, la première étape des groupes FRI x et -x. Dans le cas de n = 16, ω^8 = -1, ce qui signifie P (ω^i) ) et ( P (-ω^i) = P (ω^{i+8}) \). Comme nous pouvons le voir, ce sont exactement les paires les unes à côté des autres. La deuxième étape des groupes FRI P (ω^i) , P (ω^{i+4}) , P (ω^{i+8}) et P (ω^{i+12}) . C’est exactement ce que nous voyons par groupes de quatre, et ainsi de suite. Cela rend FRI plus efficace en termes d'espace, car cela vous permet de fournir une preuve Merkle pour les valeurs repliées ensemble (ou, si vous pliez k tours à la fois, pour les 2 ^ k valeurs).
Dans les cercles STARK, la structure de pli est légèrement différente : dans la première étape, nous associons (x, y) avec (x, -y) dans la deuxième étape, nous associons x avec -x dans l'étape suivante, associons p ; avec q, et choisissez p et q tels que Q^i (p) = -Q^i (q), où Q^i est un mappage qui répète x → 2x^2-1 i fois. Si nous pensons aux points en fonction de leur position sur le cercle, alors à chaque étape, il semble que le premier point soit associé au dernier point, le deuxième point à l'avant-dernier point, et ainsi de suite.
Pour ajuster l'ordre des bits inversé afin de refléter cette structure de pliage, nous devons inverser chaque bit sauf le dernier. Nous gardons le dernier bit et l'utilisons pour décider s'il faut retourner les autres bits.
Un pli de taille 16 dans l’ordre inverse des bits est le suivant :
{0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}
Si vous regardez le cercle de la section précédente, vous verrez que les points 0, 15, 8 et 7 (dans le sens inverse des aiguilles d'une montre à partir de la droite) sont (x, y), (x, -y), (-x, - y) et (-x, y), ce qui est exactement ce dont nous avons besoin.
efficacité
Dans les Circle STARK (et les STARK 31 bits prime en général), ces protocoles sont très efficaces. Un calcul éprouvé dans Circle STARK implique généralement plusieurs types de calculs :
1. Arithmétique native : utilisée pour la logique métier, comme le comptage.
2. Arithmétique native : utilisée en cryptographie, comme les fonctions de hachage comme Poséidon.
3. Paramètres de recherche : Une méthode de calcul générale et efficace qui met en œuvre divers calculs en lisant les valeurs du tableau.
La principale mesure de l'efficacité est de savoir si vous utilisez pleinement tout l'espace pour effectuer un travail utile dans une trace de calcul, ou si vous laissez beaucoup d'espace libre. Dans les SNARK pour les grands champs, il y a souvent beaucoup d'espace libre : la logique métier et les tables de recherche impliquent souvent des calculs sur de petits nombres (ces nombres ont tendance à être inférieurs à N, où N est le nombre total d'étapes d'un calcul, donc dans pratiquez moins de 2^{25 }), mais vous devez quand même payer le coût d'utilisation d'un champ de taille 2^{256} bits. Ici, la taille du champ est de 2^{31}, donc l'espace perdu n'est pas énorme. Les hachages de faible complexité arithmétique conçus pour les SNARK (tels que Poséidon) exploitent pleinement chaque bit de chaque nombre de la trace dans n'importe quel champ.
Binius est une meilleure solution que Circle STARK car il vous permet de mélanger des champs de différentes tailles, ce qui entraîne un regroupement de bits plus efficace. Binius offre également la possibilité d'effectuer des ajouts 32 bits sans la surcharge des tables de recherche. Cependant, ces avantages ont le prix (à mon avis) de rendre le concept plus complexe, alors que les Circle STARK (et les STARK classiques basés sur BabyBear) sont conceptuellement beaucoup plus simples.
Conclusion : mes réflexions sur les Circle STARK
Les Circle STARK ne sont pas plus compliqués pour les développeurs que les STARK. Au cours du processus de mise en œuvre, les trois problèmes mentionnés ci-dessus constituent fondamentalement des différences par rapport au FRI conventionnel. Bien que les mathématiques derrière les polynômes sur lesquels Circle FRI opère soient très complexes et prennent un certain temps à comprendre et à apprécier, cette complexité est en réalité tellement cachée qu'elle n'est pas directement ressentie par les développeurs.
Comprendre Circle FRI et Circle FFT peut également être une passerelle vers la compréhension d'autres FFT spéciales : notamment les FFT de domaine binaire, telles que celles utilisées par Binius et précédemment LibSTARK, mais aussi certaines constructions plus complexes, telles que les FFT à courbe elliptique, qui utilisent quelques- La cartographie à plusieurs peut être bien combinée avec des opérations de points de courbe elliptique.
En combinaison avec Mersenne31, BabyBear et des technologies de domaine binaire comme Binius, nous avons vraiment l'impression d'approcher les limites d'efficacité de la couche de base STARK. À ce stade, je prédis que la direction d’optimisation de STARK se concentrera sur les points suivants :
Arithmétisation des fonctions de hachage, des signatures, etc. pour maximiser l'efficacité : optimisez les primitives cryptographiques de base telles que les fonctions de hachage et les signatures numériques dans leurs formes les plus efficaces afin qu'elles puissent atteindre des performances optimales lorsqu'elles sont utilisées dans les preuves STARK. Cela signifie des optimisations spéciales pour ces primitives afin de réduire l'effort de calcul et d'augmenter l'efficacité.
Construction récursive pour permettre davantage de parallélisation : la construction récursive fait référence à l'application récursive du processus de preuve STARK à différents niveaux, augmentant ainsi les capacités de traitement parallèle. De cette manière, les ressources informatiques peuvent être utilisées plus efficacement et le processus de preuve peut être accéléré.
Arithmétiser les machines virtuelles pour améliorer l'expérience des développeurs : l'arithmétisation des machines virtuelles permet aux développeurs de créer et d'exécuter des tâches informatiques plus efficacement et plus simplement. Cela inclut l'optimisation de la machine virtuelle pour une utilisation dans les preuves STARK et l'amélioration de l'expérience des développeurs lors de la création et du test de contrats intelligents ou d'autres tâches informatiques.