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 production des STARKs utilisaient des champs de 256 bits, c'est-à-dire des opérations modulo sur de grands nombres, ce qui rendait ces protocoles compatibles avec les signatures basées sur des courbes elliptiques. Cependant, l'efficacité de cette conception est relativement faible, car dans la plupart des cas, le traitement de ces grands nombres n'a pas d'utilité pratique, et cela gaspille également une grande 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 amélioré la vitesse de preuve, par exemple Starkware peut prouver 620 000 hachages 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, il est possible de résoudre le problème de développement d'un ZK-EVM efficace. Alors, comment ces technologies fonctionnent-elles ? Comment ces preuves sont-elles établies sur des champs plus petits ? Comment ces protocoles se comparent-ils à des solutions comme Binius ? Cet article explorera ces détails, en se concentrant particulièrement 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, une technique très importante est de prouver par l'évaluation d'un polynôme en des points aléatoires, ce qui permet de vérifier indirectement les propriétés du polynôme. Cette méthode peut considérablement simplifier le processus de preuve, car l'évaluation en points aléatoires est généralement beaucoup plus facile que de traiter l'ensemble du polynôme.

Pour prévenir les attaques, nous devons choisir r après que l'attaquant a fourni A. Fiat-Shamir est une technique utilisée pour renforcer la sécurité des protocoles en évitant les attaques en définissant certains paramètres comme une valeur de hachage. Les paramètres choisis doivent provenir d'un ensemble suffisamment grand pour garantir que l'attaquant ne peut 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 2019, ce problème est assez 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 cela suffira. Cependant, dans les STARKs sur des champs plus petits, nous rencontrons un problème : il n'y a qu'environ 2 milliards de valeurs possibles pour r, donc un attaquant souhaitant falsifier une preuve n'a qu'à essayer 2 milliards de fois, bien que cela représente une charge de travail considérable, c'est tout à fait réalisable pour un attaquant déterminé !

Cette question a deux solutions :

• Effectuer plusieurs contrôles aléatoires
• Champ étendu

La méthode d'exécution de plusieurs contrôles aléatoires est la plus simple et efficace : au lieu de vérifier à un seul point de coordonnée, il vaut mieux vérifier à quatre coordonnées 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 d'une certaine taille, un attaquant peut en réalité construire des polynômes malveillants qui semblent normaux à ces positions. Par conséquent, leur capacité à 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 de pouvoir défendre efficacement contre les attaques de l'attaquant.

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

Grâce à l'extension de domaine, nous avons maintenant suffisamment de valeurs à choisir pour répondre à nos besoins en matière de sécurité. Si nous traitons des polynômes de degré inférieur à d, chaque ronde peut offrir une sécurité de 104 bits. Cela signifie que nous avons suffisamment de garanties de sécurité. Si nous devons atteindre un niveau de sécurité plus élevé, comme 128 bits, nous pouvons ajouter un travail de calcul supplémentaire dans le protocole pour renforcer la sécurité.

Les domaines d'extension ne sont réellement utilisés que dans le protocole FRI et d'autres scénarios nécessitant des combinaisons linéaires aléatoires. La plupart des opérations mathématiques sont toujours effectuées sur des champs de base, qui sont généralement des champs modulo p ou q. En même temps, presque toutes les données de hachage sont effectuées sur des champs de base, donc chaque valeur nécessite uniquement 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 de SNARK ou STARK, la première étape consiste généralement en l'arithmétisation. Il s'agit de 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 cette équation est établie, la solution de cette équation correspond à la solution du problème de calcul sous-jacent.

Pour prouver que vous avez une solution, vous devez prouver que la valeur que vous proposez est en effet un polynôme raisonnable (et non une fraction, ou un endroit où cela ressemble à un polynôme, mais ailleurs c'est un polynôme différent, etc.), et que ces polynômes ont un certain degré maximum. Pour ce faire, nous avons utilisé une technique de combinaison linéaire aléatoire appliquée de manière progressive :

• 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érez 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 récupérer 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 1. Parce que la combinaison des termes de degré pair et des termes de degré impair ne va pas augmenter le degré. Puisque D est une combinaison linéaire aléatoire de B et C, le degré de D devrait également être celui de A, ce qui vous permet de vérifier si le degré de A est conforme aux exigences en fonction du 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 simplifiant le problème de moitié.

Le fonctionnement de FRI consiste à répéter ce processus de simplification. Par exemple, si vous partez d'un polynôme dont le degré est d, à travers une série d'étapes, vous prouverez finalement que le degré du polynôme est d/2. Après chaque simplification, le degré du polynôme généré diminue progressivement. Si la sortie à une certaine étape n'est pas le degré de polynôme attendu, alors cette ronde de vérification échouera. Si quelqu'un essaie de pousser un polynôme qui n'a pas un degré d par cette technique, alors à la seconde sortie, son degré aura une certaine probabilité de ne pas correspondre aux attentes, et il est encore plus probable qu'il y ait des incohérences lors de la troisième ronde, entraînant finalement un échec de la vérification. Ce design permet de détecter et de rejeter efficacement les entrées non conformes. Si l'ensemble de données est égal à un polynôme d'un degré d dans la plupart des positions, cet ensemble de données peut potentiellement être vérifié par FRI. Cependant, pour construire un tel ensemble de données, l'attaquant doit connaître le polynôme réel, donc même une preuve légèrement défectueuse indique que le prouveur est capable de générer une "preuve réelle".

Comprenons plus en détail ce qui se passe ici et les propriétés nécessaires pour que tout cela fonctionne correctement. À chaque étape, nous réduisons le degré du polynôme de moitié, tout en réduisant également de moitié l'ensemble de points (l'ensemble de points qui nous intéresse). Le premier est la clé pour que le protocole FRI fonctionne correctement. Le second permet à l'algorithme de fonctionner très rapidement : puisque la taille de chaque round est réduite de moitié par rapport au round précédent, le coût de calcul total est O(N), et non O(N*log(N)).

Pour réduire progressivement le domaine, une mappage un-à-deux a été utilisé, c'est-à-dire que chaque point est mappé à l'un des deux points. Ce mappage nous permet de réduire la taille de l'ensemble de données de moitié. Un avantage important de ce mappage un-à-deux est qu'il est répétable. Autrement dit, lorsque nous appliquons ce mappage, l'ensemble de résultats obtenu conserve encore les mêmes propriétés. Supposons que nous partions d'un sous-groupe multiplicatif. Ce sous-groupe est un ensemble S dans lequel chaque élément x a également son multiple 2x dans l'ensemble. Si nous effectuons une opération de 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 nous puissions théoriquement 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 (par exemple, un segment ou un arc) le long de la circonférence d'un cercle, la faisant tourner deux fois autour du cercle. Par exemple, si un point se trouve à la position x degrés sur la circonférence, après cette opération, il se déplacera à la position 2x degrés. Chaque point sur la circonférence allant de 0 à 179 degrés a un point correspondant entre 180 et 359 degrés, et ces deux points coïncident. 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 cette opération de mapping plusieurs fois, chaque fois déplaçant les points sur la circonférence vers leurs nouvelles positions.

Pour que la technique de mappage soit 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 sous-groupe multiplicatif maximal contient toutes les valeurs non nulles, donc la taille du sous-groupe est de 2k−1 (où k est le nombre de bits du module). Cette taille de sous-groupe est particulièrement adaptée à la technique mentionnée ci-dessus, car elle permet de réduire efficacement le degré du polynôme par l'application répétée de l'opération de mappage. 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 enfin vérifier 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 de 2^31 - 1. Dans ce cas, la taille du sous-groupe multiplicatif n'a qu'une seule puissance de 2 comme facteur, ce qui signifie qu'il ne peut être divisé par 2 qu'une seule fois. Les traitements ultérieurs ne sont plus applicables à la technique mentionnée ci-dessus, 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 32 bits existants. En raison des caractéristiques de son module (par exemple, 2^31 - 1), de nombreuses opérations peuvent être effectuées à l'aide d'opérations de bits efficaces : si la somme de deux nombres dépasse le module, le résultat peut être réduit à une plage appropriée en effectuant des opérations de décalage avec le module. Les opérations de décalage sont des calculs très efficaces. Pour les multiplications, des instructions CPU spécifiques (généralement appelées instructions de décalage de bits élevés) peuvent être utilisées pour traiter le résultat. Ces instructions peuvent calculer efficacement la partie haute de la multiplication, augmentant ainsi l'efficacité du calcul. Dans le domaine Mersenne31, en raison des caractéristiques ci-dessus, les opérations arithmétiques sont environ 1,3 fois plus rapides que dans le domaine BabyBear. Mersenne31 offre une meilleure efficacité de calcul. Si le FRI peut être implémenté dans le domaine Mersenne31, cela améliorera considérablement l'efficacité de calcul, rendant le FRI.