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

1 Introduction

Une des principales raisons de l'inefficacité des STARKs est que la plupart des valeurs dans les programmes réels sont relativement petites. 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 de nombreuses valeurs de redondance supplémentaires occupant l'ensemble du domaine, même si la valeur d'origine elle-même est très petite. Pour résoudre ce problème, réduire la taille du domaine est devenue une stratégie clé.

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 beaucoup d'espace gaspillé. En comparaison, le domaine binaire permet d'opérer directement sur les bits, offrant un codage compact et efficace sans aucun espace gaspillé, c'est-à-dire les STARKs de quatrième génération.

Comparé aux nouveaux domaines finis récemment découverts tels que Goldilocks, BabyBear et Mersenne31, la recherche sur les domaines binaires remonte aux années 1980. Actuellement, les domaines binaires sont largement utilisés en cryptographie, des exemples typiques incluent :

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

• Galois code d'authentification de message ( 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, finaliste du SHA-3, qui est basée sur le domaine F28, est un algorithme de hachage très adapté aux récursions.

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 dépend entièrement de l'extension de domaine pour assurer sa sécurité et sa réelle utilisabilité. La plupart des polynômes impliqués dans les calculs Prover n'ont pas besoin d'entrer dans l'extension de domaine et peuvent être traités dans le domaine de base, permettant ainsi une grande efficacité dans le petit domaine. Cependant, les vérifications de points aléatoires et les calculs FRI doivent encore plonger 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, il existe 2 problèmes pratiques : 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 de 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, traitant respectivement ces deux problèmes et réalisant la représentation des mêmes données de deux manières différentes : d'abord, en utilisant des polynômes multivariés (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 chaque dimension de l'hypercube a une longueur 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 effectuer l'extension de Reed-Solomon basée sur ce carré. Cette méthode garantit la sécurité tout en améliorant considérablement l'efficacité du codage et les performances de calcul.

2 Analyse des principes

La plupart des systèmes SNARKs actuels sont généralement construits en deux parties :

• Preuves d'oracles interactifs polynomiaux basés sur la théorie de l'information (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP) : Le PIOP, en tant que cœur du système de preuve, transforme les relations de calcul d'entrée en équations polynomiales vérifiables. Différents protocoles PIOP, en interagissant avec le vérificateur, permettent au prouveur d'envoyer progressivement des polynômes, permettant ainsi au vérificateur de vérifier si le calcul est correct en interrogeant un nombre réduit d'évaluations de polynômes. Les protocoles PIOP existants incluent : PLONK PIOP, Spartan PIOP et HyperPlonk PIOP, chacun ayant sa propre manière de traiter les expressions polynomiales, ce qui influence la performance et l'efficacité du système SNARK dans son ensemble.

• 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. Le PCS est un outil cryptographique qui permet à un prouveur de s'engager sur un certain polynôme et de vérifier plus tard le résultat de l'évaluation de ce polynôme, tout en masquant d'autres informations sur le polynôme. Les schémas d'engagement polynomial courants incluent KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP) et Brakedown, entre autres. Différents PCS ont des performances, une sécurité et des cas d'utilisation variés.

En fonction des besoins spécifiques, choisissez différents PIOP et PCS, et combinez-les avec un domaine fini ou une courbe elliptique appropriée, afin de 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 supprimant le trusted setup du 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 des preuves SNARK et l'efficacité de la vérification, mais détermine également si le système peut réaliser 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 les tours de domaines binaires constitue la base de son calcul, permettant d'effectuer des opérations simplifiées dans le domaine binaire. Deuxièmement, Binius a adapté la vérification de produit et de permutation de HyperPlonk dans son protocole de preuve Oracle interactif (PIOP), garantissant un contrôle de cohérence sécurisé 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 sur petits domaines (Small-Field PCS), lui permettant de réaliser un système de preuve efficace sur le domaine binaire et réduisant les frais généralement associés aux grands domaines.

2.1 Domain fini : arithmetic basé sur les tours de champs binaires

Le domaine binaire en forme de tour est la clé pour réaliser des calculs vérifiables rapides, principalement en raison de deux aspects : le calcul efficace et l'arithmétisation efficace. Le domaine binaire supporte essentiellement des opérations arithmétiques très efficaces, ce qui en fait un choix idéal pour les applications cryptographiques sensibles aux performances. De plus, la structure du domaine binaire permet un processus d'arithmétisation simplifié, c'est-à-dire que les opérations effectuées sur le domaine binaire peuvent être représentées sous une forme algébrique compacte et facilement vérifiable. Ces caractéristiques, combinées à la capacité d'exploiter pleinement ses propriétés hiérarchiques grâce à la structure en tour, rendent le domaine binaire 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 des éléments dans le corps binaire. Par exemple, dans le corps binaire F2 le plus fondamental, toute 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, ce n'est pas le cas pour chaque chaîne de 32 bits qui peut correspondre de manière unique à un élément du corps, tandis que le corps binaire offre cette commodité de mappage un à un. Dans le corps premier Fp, les méthodes de réduction courantes incluent la réduction Barrett, la réduction 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 les réductions spéciales (comme celles utilisées dans AES), la réduction Montgomery (comme celle 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" souligne que le corps binaire n'a pas besoin d'introduire de retenue pour les 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 de (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 des domaines binaires. Elle peut être considérée comme un élément unique dans un domaine binaire de 128 bits, ou être analysée comme 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, il s'agit simplement d'une conversion de type de chaîne de bits, ce qui est une propriété très intéressante et utile. En même temps, 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. De plus, l'article "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité de calcul pour effectuer des multiplications, des carrés et des opérations d'inversion dans un domaine binaire de tour de n bits (décomposable en sous-domaines de m bits).

2.2 PIOP : version adaptée de HyperPlonk Product et PermutationCheck ------ applicable au corps 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 l'exactitude des polynômes et des ensembles multivariés. Ces vérifications clés comprennent :

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

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

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

4. MultisetCheck : vérifie si deux ensembles multivariés 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 booléen est égale à une valeur déclarée ∏x∈Hµ f(x) = s, afin d'assurer la validité du produit polynomial.

6. ZeroCheck : Vérifier si un polynôme multivarié aux multiples variables est nul en un point quelconque sur l'hypercube booléen ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, pour garantir la distribution des zéros du polynôme.

7. SumCheck : Vérifie si la somme d'un polynôme multivarié 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 un problème d'évaluation de polynôme à une variable, cela réduit la complexité de calcul pour le vérificateur. De plus, SumCheck permet le traitement par lots, en introduisant un nombre aléatoire pour construire une combinaison linéaire et réaliser le traitement par lots de plusieurs instances de vérification de somme.

8. BatchCheck : basé sur SumCheck, vérifie la justesse de l'évaluation 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 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.

• Gestion des problèmes de division par zéro : HyperPlonk n'a pas réussi à gérer 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 traité ce problème, même lorsque le dénominateur est nul, le ProductCheck de Binius peut continuer à fonctionner, permettant une généralisation à n'importe quelle valeur de produit.

• Vérification de permutation intercolonnes : HyperPlonk n'a pas cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de traiter des cas de permutation polynomiale 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 validations 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 au cube hyperbolique booléen

Dans le protocole Binius, la construction et le traitement des polynômes virtuels sont l'une des technologies clés, permettant 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 :

• Packing：Cette méthode consiste à frapper les plus petits éléments des positions adjacentes dans l'ordre lexicographique.