Analyse des principes des STARKs de Binius et réflexions sur leur optimisation

1 Introduction

Un des principaux problèmes d'efficacité des STARKs est que la plupart des valeurs dans les programmes réels sont assez petites, comme les index dans les boucles for, les valeurs booléennes, les compteurs, etc. Cependant, pour garantir la sécurité des preuves basées sur les arbres de Merkle, l'utilisation du codage de Reed-Solomon pour étendre les données entraîne l'occupation de nombreux valeurs redondantes dans tout le domaine, même si les valeurs originales elles-mêmes sont très petites. Pour résoudre ce problème, réduire la taille du domaine est devenu une stratégie clé.

Comme le montre le tableau 1, la largeur de codage des STARKs de première génération est de 252 bits, celle des STARKs de deuxième génération est de 64 bits, et celle des STARKs de troisième génération est de 32 bits, mais la largeur de codage de 32 bits présente encore un vaste espace gaspillé. En revanche, le domaine binaire permet d'opérer directement sur les bits, rendant le codage compact et efficace sans espace gaspillé, soit les STARKs de quatrième génération.

Tableau 1 : chemin de dérivation des STARKs

| Algèbre | Largeur de mot | Domaine | |------|------|------| | 1ère génération | 252 bits | Domaine des nombres premiers | | 2ème génération | 64 bits | Goldilocks | | 3ème génération | 32bits | Domaine des nombres premiers | | 4ème génération | 1bit | domaine binaire |

Comparé aux découvertes récentes sur les corps finis comme Goldilocks, BabyBear et Mersenne31, la recherche sur les corps binaires remonte aux années 1980. Actuellement, les corps binaires sont largement utilisés en cryptographie, des exemples typiques incluent :

• Norme de cryptage avancée ( AES ), basée sur le domaine F28;

• Galois Message Authentication Code ( GMAC ), basé sur le domaine F2128;

• Code QR, utilisant le codage Reed-Solomon basé sur F28;

• Protocole FRI d'origine et zk-STARK, ainsi que la fonction de hachage Grøstl qui a atteint la finale SHA-3, cette fonction basée sur le domaine F28 est un algorithme de hachage très adapté à la récursivité.

Lorsque des domaines plus petits sont utilisés, l'opération d'extension de domaine devient de plus en plus importante pour garantir la sécurité. Le domaine binaire utilisé par Binius doit entièrement dépendre de l'extension de domaine pour garantir sa sécurité et sa réelle utilisabilité. La plupart des polynômes impliqués dans les calculs de Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais doivent opérer uniquement sous le domaine de base, ce qui permet d'atteindre une grande efficacité dans de petits domaines. Cependant, les vérifications de points aléatoires et les calculs FRI doivent encore plonger dans une extension de domaine plus grande pour garantir la sécurité requise.

Lors de la construction d'un système de preuve basé sur des domaines binaires, deux problèmes pratiques existent : lors du calcul de la représentation de trace dans les STARKs, la taille du domaine utilisé doit être supérieure au degré du polynôme ; lors de l'engagement de l'arbre Merkle dans les STARKs, un codage de Reed-Solomon doit être effectué, et la taille du domaine utilisé doit être supérieure à la taille après extension du codage.

Binius a proposé une solution innovante, traitant respectivement ces deux problèmes, et en représentant les mêmes données de deux manières différentes : d'abord, en utilisant des polynômes multivariés ( qui sont spécifiquement des polynômes multilinaires ) au lieu de polynômes univariés, en représentant l'ensemble de la trajectoire de calcul par ses valeurs sur les "hypercubes" ( ; ensuite, étant donné que la longueur de chaque dimension de l'hypercube est de 2, il n'est pas possible de faire une extension standard de Reed-Solomon comme avec les STARKs, mais on peut considérer l'hypercube comme un ) carré (, et faire l'extension de Reed-Solomon basée sur ce carré. Cette méthode améliore considérablement l'efficacité du codage et la performance des calculs tout en garantissant la sécurité.

2 Analyse des principes

La construction de la plupart des systèmes SNARKs actuels comprend généralement les deux parties suivantes :

• Preuve d'oracle interactive polynomiale d'information théorique )Information-Theoretic Polynomial Interactive Oracle Proof, PIOP(: Le PIOP, en tant que système de preuve central, transforme les relations de calcul d'entrée en équations polynomiales vérifiables. Différents protocoles PIOP, à travers l'interaction avec le vérificateur, permettent au prouveur d'envoyer progressivement des polynômes, de sorte que le vérificateur puisse vérifier si le calcul est correct en interrogeant un petit nombre de résultats d'évaluation de polynômes. Les protocoles PIOP existants incluent : PLONK PIOP, Spartan PIOP et HyperPlonk PIOP, qui ont chacun une manière différente de traiter les expressions polynomiales, ce qui affecte la performance et l'efficacité de l'ensemble du système SNARK.

• Schéma d'engagement polynomial ) Polynomial Commitment Scheme, PCS ( : Le schéma d'engagement polynomial est utilisé pour prouver si une équation polynomiale générée par PIOP est valide. Le PCS est un outil cryptographique, grâce auquel le prouveur peut s'engager sur un certain polynôme et vérifier ultérieurement le résultat de l'évaluation de ce polynôme, tout en cachant d'autres informations sur le polynôme. Les schémas d'engagement polynomial courants incluent KZG, Bulletproofs, FRI ) Fast Reed-Solomon IOPP ( et Brakedown, etc. Différents PCS ont différentes performances, sécurité et scénarios d'application.

Selon les besoins spécifiques, choisissez différents PIOP et PCS, et combinez-les avec un domaine fini ou une courbe elliptique appropriés, vous pouvez construire des systèmes de preuve ayant différentes propriétés. Par exemple :

• Halo2 : combinant PLONK PIOP et Bulletproofs PCS, et basé sur la courbe Pasta. Lors de la conception de Halo2, l'accent a été mis sur l'évolutivité et l'élimination de la configuration de confiance dans le protocole ZCash.

• Plonky2 : utilise la combinaison de PLONK PIOP et FRI PCS, et est basé sur le domaine de Goldilocks. Plonky2 est conçu pour réaliser des récursions efficaces. Lors de la conception de ces systèmes, le PIOP et le PCS choisis doivent correspondre au domaine fini ou à la courbe elliptique utilisée, afin d'assurer la correctitude, la performance et la sécurité du système. Ces choix de combinaison influencent non seulement la taille de la preuve SNARK et l'efficacité de la vérification, mais déterminent également si le système peut atteindre la transparence sans nécessiter de configuration de confiance, et s'il peut supporter des fonctionnalités d'extension telles que les preuves récursives ou agrégées.

Binius : HyperPlonk PIOP + Brakedown PCS + domaine binaire. Plus précisément, Binius comprend cinq technologies clés pour réaliser son efficacité et sa sécurité. Tout d'abord, l'arithmétique basée sur les tours de domaine binaire )towers of binary fields( constitue la base de son calcul, permettant d'effectuer des opérations simplifiées dans le domaine binaire. Deuxièmement, Binius a adapté le produit HyperPlonk et la vérification de permutation dans son protocole de preuve Oracle interactif )PIOP(, garantissant une vérification de cohérence sécurisée et efficace entre les variables et leurs permutations. Troisièmement, le protocole introduit une nouvelle preuve de décalage multilinéraire, optimisant l'efficacité de la vérification des relations multilinéaires sur de petits domaines. Quatrièmement, Binius utilise une version améliorée de la preuve de recherche Lasso, offrant flexibilité et sécurité robuste au mécanisme de recherche. Enfin, le protocole utilise un schéma d'engagement polynomial de petit domaine )Small-Field PCS(, lui permettant de réaliser un système de preuve efficace dans le domaine binaire et réduisant les frais généralement associés aux grands domaines.

) 2.1 Domain fini : arithmétisation basée sur les tours des corps binaires

Les corps binaires en tour sont la clé pour réaliser des calculs rapides et vérifiables, principalement en raison de deux aspects : le calcul efficace et l'arithmétique efficace. Les corps binaires soutiennent essentiellement des opérations arithmétiques hautement efficaces, ce qui en fait un choix idéal pour les applications cryptographiques sensibles aux performances. De plus, la structure des corps binaires supporte un processus d'arithmétique simplifié, c'est-à-dire que les opérations effectuées sur les corps binaires peuvent être représentées sous une forme algébrique compacte et facile à vérifier. Ces caractéristiques, associées à la capacité de tirer pleinement parti de ses caractéristiques hiérarchiques grâce à la structure en tour, font des corps binaires un choix particulièrement adapté à des systèmes de preuve évolutifs tels que Binius.

Le terme "canonical" fait référence à la représentation unique et directe d'un élément dans un domaine binaire. Par exemple, dans le domaine binaire le plus simple F2, n'importe quelle chaîne de k bits peut être directement mappée à un élément de domaine binaire de k bits. Cela diffère des domaines premiers, qui ne peuvent pas fournir une telle représentation canonique dans un nombre de bits donné. Bien qu'un domaine premier de 32 bits puisse être contenu dans 32 bits, ce n'est pas le cas pour chaque chaîne de 32 bits qui peut correspondre de manière unique à un élément de domaine, tandis que le domaine binaire a cette commodité de correspondance un à un. Dans le domaine premier Fp, les méthodes de réduction courantes incluent la réduction de Barrett, la réduction de Montgomery, ainsi que des méthodes de réduction spéciales pour des domaines finis spécifiques comme Mersenne-31 ou Goldilocks-64. Dans le domaine binaire F2k, les méthodes de réduction courantes incluent la réduction spéciale ### comme utilisée dans AES (, la réduction de Montgomery ) comme utilisée dans POLYVAL ( et la réduction récursive ) comme Tower (. Le document "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" indique que le domaine binaire n'a pas besoin d'introduire des retenues dans les opérations d'addition et de multiplication, et que l'opération de carré dans le domaine binaire est très efficace, car elle suit la règle simplifiée )X + Y (2 = X2 + Y 2.

Comme indiqué dans la figure 1, une chaîne de 128 bits : cette chaîne peut être interprétée de plusieurs manières dans le contexte des domaines binaires. Elle peut être considérée comme un élément unique dans un domaine binaire de 128 bits, ou être décomposée en deux éléments de domaine de tour de 64 bits, quatre éléments de domaine de tour de 32 bits, 16 éléments de domaine de tour de 8 bits, ou 128 éléments de domaine F2. Cette flexibilité de représentation ne nécessite aucun coût de calcul, c'est simplement un type de conversion de chaîne de bits )typecast(, ce qui est une propriété très intéressante et utile. De plus, les éléments de petits domaines peuvent être empaquetés en éléments de domaines plus grands sans coût de calcul supplémentaire. Le protocole Binius tire parti de cette caractéristique pour améliorer l'efficacité des calculs. En outre, l'article "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité de calcul des opérations de multiplication, de mise au carré et d'inversion dans un domaine binaire de tour de n bits ) décomposé en un sous-domaine de m bits (.

![Tour binaire])https://img-cdn.gateio.im/webp-social/moments-a5d031be4711f29ef910057f4e44a118.webp(

Figure 1 : Domaine binaire en tour

) 2.2 PIOP: version adaptée du produit HyperPlonk et Vérification de Permutation------applicable au domaine binaire

La conception de PIOP dans le protocole Binius s'inspire de HyperPlonk et utilise une série de mécanismes de vérification clés pour valider la justesse des polynômes et des ensembles multivariés. Ces vérifications clés comprennent :

1. GateCheck : valider si le témoin secret ω et l'entrée publique x satisfont à la relation de calcul du circuit C###x, ω(=0, afin de s'assurer que le circuit fonctionne correctement.

2. PermutationCheck : Vérifie si les résultats d'évaluation de deux polynômes multivariés f et g sur le cube hypercubique booléen sont une relation de permutation f)x( = f)π(x(), afin d'assurer la cohérence des permutations entre les variables du polynôme.

3. LookupCheck : vérifiez si l'évaluation du polynôme est dans la table de recherche donnée, c'est-à-dire f)Bµ( ⊆ T)Bµ(, assurez-vous que certaines valeurs sont dans la plage spécifiée.

4. MultisetCheck : vérifie si deux ensembles multivariables sont égaux, c'est-à-dire {)x1,i,x2,(}i∈H={)y1,i,y2,(}i∈H, garantissant la cohérence entre plusieurs ensembles.

5. ProductCheck : vérifier si l'évaluation d'un polynôme rationnel sur l'hypercube booléen est égale à une valeur déclarée ∏x∈Hµ f)x( = s, afin de garantir l'exactitude du produit polynomial.

6. ZeroCheck : vérifier si un polynôme multivarié est nul en un point quelconque sur le cube hyperbolique booléen ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, afin de garantir la distribution des zéros du polynôme.

7. SumCheck : Vérifie si la somme d'un polynôme multivariable est égale à la valeur déclarée ∑x∈Hµ f)x( = s. En transformant le problème d'évaluation du polynôme multivariable en évaluation d'un polynôme à variable unique, cela réduit la complexité de calcul pour le vérificateur. De plus, SumCheck permet le traitement par lots, en introduisant des nombres aléatoires pour construire des combinaisons linéaires et réaliser le traitement de plusieurs instances de vérification de somme.

8. BatchCheck : basé sur SumCheck, vérifie la justesse des évaluations de plusieurs polynômes multivariés pour améliorer l'efficacité du protocole.

Bien que Binius et HyperPlonk présentent de nombreuses similitudes dans la conception du protocole, Binius apporte des améliorations dans les trois domaines suivants :

• Optimisation de ProductCheck : dans HyperPlonk, ProductCheck exige que le dénominateur U soit non nul partout sur l'hypercube, et que le produit soit égal à une valeur spécifique ; Binius simplifie ce processus de vérification en spécialisant cette valeur à 1, réduisant ainsi la complexité de calcul.

• Gestion du problème de division par zéro : HyperPlonk n'a pas réussi à traiter correctement les cas de division par zéro, ce qui rend impossible d'affirmer que U est non nul sur l'hypercube ; Binius a correctement géré ce problème, même lorsque le dénominateur est nul, le ProductCheck de Binius peut continuer à traiter, permettant une généralisation à n'importe quelle valeur de produit.

• Vérification de permutation entre colonnes : HyperPlonk n'a pas cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de gérer des cas de permutations polynomiales plus complexes.

Ainsi, Binius a amélioré le mécanisme PIOPSumCheck existant, augmentant la flexibilité et l'efficacité du protocole, en particulier lors du traitement de la validation de polynômes multivariés plus complexes, offrant un soutien fonctionnel plus fort. Ces améliorations non seulement résolvent les limitations de HyperPlonk, mais jettent également les bases pour de futurs systèmes de preuve basés sur des domaines binaires.

) 2.3 PIOP : nouvel argument de décalage multilinéraire ------ applicable à l'hypercube booléen

Dans le protocole Binius, la construction et le traitement des polynômes virtuels sont clés.