Analyse des principes des STARKs de Binius et réflexion 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 relativement petites, comme les indices dans une boucle for, les valeurs booléennes, les compteurs, etc. Cependant, pour assurer 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 de nombreuses valeurs de redondance supplémentaires qui occupent tout le domaine, même si la valeur originale elle-même est très petite. Pour résoudre ce problème, la réduction de la taille du domaine est devenue une stratégie clé.

La largeur de codage des STARKs de 1ère génération est de 252 bits, celle des STARKs de 2ème génération est de 64 bits, et celle des STARKs de 3ème génération est de 32 bits, mais la largeur de codage de 32 bits présente encore beaucoup d'espace gaspillé. En comparaison, le domaine binaire permet d'opérer directement sur les bits, rendant le codage compact et efficace sans espace gaspillé, c'est-à-dire les STARKs de 4ème génération.

Comparé aux recherches récentes sur les corps finis comme Goldilocks, BabyBear et Mersenne31, l'étude des corps binaires remonte aux années 80. Actuellement, les corps binaires sont largement utilisés en cryptographie, des exemples typiques incluent :

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

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

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

• Protocole FRI original et zk-STARK, ainsi que la fonction de hachage Grøstl qui a atteint la finale du SHA-3, 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 complètement dépendre de l'extension de domaine pour garantir sa sécurité et sa praticité. La plupart des polynômes impliqués dans les calculs des Prover n'ont pas besoin de passer dans l'extension de domaine, mais peuvent simplement fonctionner sous le domaine de base, ce qui permet d'atteindre une grande efficacité dans un petit domaine. Cependant, les vérifications de points aléatoires et les calculs FRI doivent encore approfondir dans un domaine d'extension plus grand pour garantir la sécurité requise.

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

Binius a proposé une solution innovante qui traite ces deux problèmes séparément et représente les mêmes données de deux manières différentes : d'abord, en utilisant des polynômes multivariables (, spécifiquement des polynômes multilinaires ), pour remplacer les polynômes à variable unique, représentant l'ensemble de la trajectoire de calcul par ses valeurs sur des ( hypercubes dans un "hypercube" ; ensuite, étant donné que la longueur de chaque dimension de l'hypercube est de 2, il n'est pas possible de faire une extension Reed-Solomon standard comme avec les STARKs, mais l'hypercube peut être considéré comme un ) carré (, sur la base duquel une extension Reed-Solomon peut être réalisée. Cette méthode améliore considérablement l'efficacité du codage et les performances de calcul 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, grâce à 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 traitent chacun les expressions polynomiales de manière différente, influençant ainsi 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 l'égalité polynomiale générée par PIOP est valide. PCS est un outil cryptographique, par lequel le prouveur peut s'engager sur un certain polynôme et, plus tard, vérifier 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 des performances, une sécurité et des cas d'utilisation différents.

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

• Halo2 : combinant PLONK PIOP et Bulletproofs PCS, basé sur la courbe Pasta. Halo2 a été conçu en mettant l'accent sur l'évolutivité et en éliminant la configuration de confiance dans le protocole ZCash.

• Plonky2 : utilise PLONK PIOP et FRI PCS combinés, et est basé sur le domaine de Goldilocks. Plonky2 est conçu pour réaliser une récursivité efficace. Lors de la conception de ces systèmes, le PIOP et le PCS choisis doivent correspondre au champ fini ou à la courbe elliptique utilisés, afin d'assurer la correction, la performance et la sécurité du système. Le choix de ces combinaisons affecte non seulement la taille de la preuve SNARK et l'efficacité de la vérification, mais détermine également si le système peut atteindre la transparence sans configuration de confiance préalable, et s'il peut prendre en charge des fonctionnalités d'extension telles que les preuves récursives ou les preuves 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 des tours de domaines binaires )towers of binary fields( constitue la base de ses calculs, permettant d'effectuer des opérations simplifiées dans le domaine binaire. Ensuite, Binius a adapté la vérification de produit et de permutation de HyperPlonk dans son protocole de preuve oracle interactive )PIOP(, garantissant une vérification cohérente 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 polynômial sur de petits domaines )Small-Field PCS(, lui permettant d'implémenter un système de preuve efficace sur le domaine binaire, tout en réduisant les coûts généralement associés aux grands domaines.

) 2.1 Domain fini : arithmétisation basée sur les tours de champs binaires

Les corps binaires en tour sont essentiels pour réaliser des calculs vérifiables rapides, principalement en raison de deux aspects : le calcul efficace et l'arithmétique efficace. Les corps binaires soutiennent intrinsèquement 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 permet un processus d'arithmétisation simplifié, c'est-à-dire que les opérations effectuées sur le corps binaire peuvent être représentées sous une forme algébrique compacte et facile à vérifier. Ces caractéristiques, combinées à la capacité d'exploiter pleinement ses caractéristiques hiérarchiques via une structure en tour, rendent les corps binaires particulièrement adaptés à des systèmes de preuve évolutifs tels que Binius.

Dans ce contexte, "canonical" fait référence à la représentation unique et directe des éléments dans un corps binaire. Par exemple, dans le corps binaire de base F2, n'importe quelle chaîne de k bits peut être directement mappée à un élément de corps binaire de k bits. Cela diffère des corps premiers, qui ne peuvent pas fournir cette représentation canonique dans un nombre de bits donné. Bien qu'un corps premier de 32 bits puisse être contenu dans 32 bits, chaque chaîne de 32 bits ne peut pas nécessairement correspondre de manière unique à un élément de corps, alors que le corps binaire offre cette commodité de correspondance un à un. Dans le corps 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 corps finis spécifiques comme Mersenne-31 ou Goldilocks-64. Dans le corps binaire F2k, les méthodes de réduction couramment utilisées incluent la réduction spéciale ### utilisée dans AES, la réduction de Montgomery ( utilisée dans POLYVAL et la réduction récursive ) comme Tower (. L'article "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" indique que le corps binaire n'a pas besoin d'introduire des retenues lors des opérations d'addition et de multiplication, et que l'opération de carré dans le corps binaire est très efficace, car elle suit la règle simplifiée )X + Y (2 = X2 + Y 2.

Comme montré 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 du domaine binaire. Elle peut être considérée comme un élément unique dans le domaine binaire de 128 bits, ou être analysée en deux éléments de domaine de tour de 64 bits, quatre éléments de domaine de tour de 32 bits, seize é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, juste une conversion de type de chaîne de bits )typecast(, ce qui est une propriété très intéressante et utile. De plus, les éléments de petit domaine peuvent être empaquetés en éléments de domaine plus grands sans coût de calcul supplémentaire. Le protocole Binius tire parti de cette caractéristique pour améliorer l'efficacité du calcul. En outre, le document "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 (.

![Bitlayer Research : Analyse des principes STARKs de Binius et réflexion sur leur optimisation])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(

) 2.2 PIOP: Version modifiée du produit HyperPlonk et PermutationCheck------Applicable aux domaines binaires

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

1. GateCheck : vérifier si le témoin confidentiel ω et l'entrée publique x satisfont la relation de calcul du circuit C(x,ω)=0, afin de garantir le bon fonctionnement du circuit.

2. PermutationCheck : vérifier si les résultats d'évaluation de deux polynômes multivariés f et g sur le cube hyperbooléen forment une relation de permutation f###x( = f)π(x)(, afin d'assurer la cohérence des permutations entre les variables polynomiales.

3. LookupCheck : Vérifiez si l'évaluation du polynôme se trouve 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érifiez si l'évaluation d'un polynôme rationnel sur le cube hyperbolique de Boole est égale à une valeur déclarée ∏x∈Hµ f)x( = s, afin d'assurer l'exactitude du produit polynômial.

6. ZeroCheck : Vérifiez si un polynôme multivarié à plusieurs variables est nul en un point quelconque sur l'hypercube booléen ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, afin d'assurer la distribution des zéros du polynôme.

7. SumCheck : Vérification 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 d'un polynôme multivarié en évaluation d'un polynôme univarié, cela réduit la complexité computationnelle pour le vérificateur. De plus, SumCheck permet également le traitement par lots, en introduisant des nombres aléatoires pour construire des combinaisons linéaires afin de réaliser le traitement par lots de plusieurs instances de vérification de somme.

8. BatchCheck : basé sur SumCheck, vérifie l'exactitude des évaluations de plusieurs polynômes multivariables afin d'améliorer l'efficacité du protocole.

Bien que Binius et HyperPlonk aient de nombreuses similarités dans la conception des protocoles, Binius a apporté des améliorations dans les 3 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.

• Traitement du problème de division par zéro : HyperPlonk n'a pas réussi à traiter adéquatement les cas de division par zéro, ce qui empêche d'affirmer que U est non nul sur l'hypercube ; Binius a correctement traité 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 intercolonnes : HyperPlonk ne dispose pas de cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de gérer des cas de permutation de polynômes plus complexes.

Ainsi, Binius a amélioré la flexibilité et l'efficacité du protocole grâce à l'amélioration du mécanisme PIOPSumCheck existant, offrant un support fonctionnel renforcé, en particulier lors du traitement de vérifications de polynômes multivariés plus complexes. 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 corps binaires.

) 2.3 PIOP : nouvel argument de décalage multilinéraire ------ applicable au cuboctaèdre booléen

Dans le protocole Binius, la construction et le traitement des polynômes virtuels sont l'une des techniques clés, capables de générer et d'opérer efficacement des polynômes dérivés de poignées d'entrée ou d'autres polynômes virtuels. Voici deux méthodes clés :

• Emballage : Cette méthode optimise l'opération en regroupant les éléments les plus petits aux positions adjacentes dans l'ordre lexicographique en éléments plus grands. L'opérateur Pack cible des blocs de taille 2κ et les combine en un plus grand.