Analyse du principe de Binius STARKs et de sa pensée d’optimisation

1 Présentation

Contrairement aux SNARK basés sur des courbes elliptiques, les STARK peuvent être considérés comme des SNARK basés sur le hachage. L’une des principales raisons de l’inefficacité actuelle des STARKs est que la plupart des valeurs du programme réel sont petites, telles que les index dans les boucles for, les valeurs true et false, les compteurs, etc. Cependant, pour assurer la sécurité des preuves basées sur l’arbre de Merkle, lorsque les données sont étendues avec l’encodage Reed-Solomon, de nombreuses valeurs redondantes supplémentaires occupent l’ensemble du domaine, même si les valeurs d’origine elles-mêmes sont très petites. Pour résoudre ce problème, la réduction de la taille du domaine devient une stratégie clé.

Comme le montre le Tableau 1, les STARK de première génération sont de 252 bits, les STARK de deuxième génération de 64 bits et les STARK de troisième génération de 32 bits. En revanche, le domaine binaire permet des opérations d’alignement direct des bits et est compact et efficace dans l’encodage sans gaspiller d’espace, c’est-à-dire les STARK de 4e génération.

Tableau 1 : Voies d’évolution des STARK

| Fonctionnalité | STARK de 1ère génération | STARK de 2e génération | STARK de 3e génération | La 4e génération STARKs(Binius) | |------|-------------|-------------|-------------|---------------------| | Largeur du bit de code | 252 bits | 64 bits | 32 bits | 1 bit | | Système représentatif | StarkWare | Plonky2 | Bébé ours | Binius |

Par rapport aux domaines finis découverts ces dernières années, tels que Goldilocks, BabyBear et Mersenne31, l’étude des domaines binaires remonte aux années 80 du siècle dernier. À l’heure actuelle, les domaines binaires ont été largement utilisés en cryptographie, des exemples typiques incluent :

• Norme de cryptage avancée (AES), basée sur les domaines F28 ;

• Code d’authentification du message Galois (GMAC), basé sur le domaine F2128 ;

• Code QR, utilisant l’encodage Reed-Solomon basé sur F28 ;

• Les protocoles originaux FRI et zk-STARK, ainsi que la fonction de hachage Grøstl qui a été finaliste du SHA-3, qui est basée sur le domaine F28 et est un algorithme de hachage bien adapté à la récursivité.

Lors de l’utilisation de domaines plus petits, l’extension des opérations de domaine devient de plus en plus importante pour garantir la sécurité. Le domaine binaire utilisé par Binius, en revanche, doit s’appuyer entièrement sur l’expansion du domaine pour assurer sa sécurité et sa disponibilité réelle. La plupart des polynômes impliqués dans les calculs de Prover n’ont pas besoin d’entrer dans le domaine étendu, mais doivent seulement fonctionner sous le domaine de base, atteignant ainsi une efficacité élevée dans les petits domaines. Cependant, les contrôles ponctuels aléatoires et les calculs FRI doivent toujours être effectués dans une zone d’expansion plus grande pour garantir la sécurité requise.

Lors de la construction d’un système de preuve basé sur des domaines binaires, il y a deux problèmes pratiques : lors du calcul de la représentation de trace dans STARKs, la taille du domaine utilisée doit être supérieure à l’ordre du polynôme ; Lorsque l’arbre de Merkle est promis dans STARKs, il doit être encodé en Reed-Solomon, et la taille du domaine utilisé doit être supérieure à la taille de l’extension d’encodage.

Binius propose une solution innovante qui traite ces deux problèmes séparément et le fait en représentant les mêmes données de deux manières différentes : premièrement, en utilisant des polynômes multivariés (plus précisément, multilinéaires) au lieu de polynômes univariés, et en représentant l’ensemble de la trajectoire de calcul par sa valeur sur les « hypercubes » ; Deuxièmement, puisque la longueur de chaque dimension de l’hypercube est de 2, il n’est pas possible de faire l’extension standard de Reed-Solomon comme STARKs, mais l’hypercube peut être traité comme un carré basé sur l’extension de Reed-Solomon. Cette méthode améliore considérablement l’efficacité de l’encodage et les performances de calcul tout en assurant la sécurité.

2 Analyse des principes

La construction de la plupart des systèmes SNARK actuels se compose généralement des deux parties suivantes :

• La preuve Oracle interactive polynomiale de la théorie de l’information (PIOP) :P IOP comme cœur du système de preuve, transformant les relations de calcul des entrées en équations polynomiales vérifiables. Différents protocoles PIOP permettent au prouveur d’envoyer des polynômes étape par étape en interagissant avec le validateur, ce qui permet à ce dernier de vérifier que le calcul est correct en interrogeant les résultats d’évaluation d’un petit nombre de polynômes. Les protocoles PIOP existants incluent PLONK PIOP, Spartan PIOP et HyperPlonk PIOP, qui gèrent tous les expressions polynomiales différemment, ce qui affecte les performances et l’efficacité de l’ensemble du système SNARK.

• Schéma d’engagement polynomial (PCS) : Le schéma d’engagement polynomial est utilisé pour prouver si l’équation polynomiale générée par PIOP est vraie. PCS est un outil cryptographique grâce auquel un prouveur peut s’engager dans un certain polynôme et vérifier ultérieurement les résultats 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. Les différents PC ont des performances, une sécurité et des scénarios d’application différents.

Selon les exigences spécifiques, différents PIOP et PCS peuvent être sélectionnés, et combinés à des champs finis ou des courbes elliptiques appropriés, des systèmes de preuve avec différentes propriétés peuvent être construits. Par exemple:

• Halo2 : Propulsé par PLONK PIOP combiné à Bulletproofs PCS et basé sur des courbes de pâtes. Halo2 a été conçu dans un souci d’évolutivité, ainsi que de suppression de la configuration de confiance du protocole ZCash.

• Plonky2 : Combine PLONK PIOP avec FRI PCS et est basé sur le domaine Boucle d’or. Plonky2 est pour une récursivité efficace. Lors de la conception de ces systèmes, le PIOP et le PCS sélectionnés doivent correspondre au domaine fini ou à la courbe elliptique utilisée pour garantir l’exactitude, les performances et la sécurité du système. Le choix de ces combinaisons affecte non seulement la taille de la preuve et l’efficacité de la vérification des SNARK, mais détermine également si le système peut atteindre la transparence sans avoir besoin de paramètres de confiance, et s’il peut prendre en charge des fonctions étendues 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 atteindre son efficacité et sa sécurité. Tout d’abord, l’arithmétique basée sur les tours de champs binaires constitue la base de ses calculs, qui permettent de réaliser des opérations simplifiées dans les corps binaires. Deuxièmement, dans son protocole interactif Oracle Proof Protocol (PIOP), Binius a adapté le produit HyperPlonk et la vérification de la permutation pour assurer une vérification de cohérence sûre et efficace entre les variables et leurs permutations. Troisièmement, le protocole introduit un nouvel argument de décalage multilinéaire pour optimiser l’efficacité de la vérification de la relation multilinéaire sur un petit domaine. Quatrièmement, Binius adopte une version améliorée de l’argument de recherche Lasso, qui offre une flexibilité et une sécurité renforcées pour le mécanisme de recherche. Enfin, le protocole utilise un schéma d’engagement polynomial à petit champ (Small-Field PCS), ce qui lui permet de mettre en œuvre un système de preuve efficace sur le domaine binaire et de réduire la surcharge généralement associée aux grands domaines.

2.1 Champs finis : arithmétique basée sur des tours de champs binaires

Le domaine binaire de la tour est la clé du calcul vérifiable rapide, qui est principalement attribué à deux aspects : le calcul efficace et l’arithmétisation efficace. Les domaines binaires prennent en charge des opérations arithmétiques très efficaces, ce qui les rend idéaux pour les applications de cryptographie sensibles aux exigences de performance. De plus, la structure du domaine binaire prend en charge un processus arithmétique 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 possibilité de tirer pleinement parti de sa nature hiérarchique grâce à des structures en tour, rendent le domaine binaire particulièrement adapté aux systèmes de preuve évolutifs tels que Binius

où « canonique » fait référence à une représentation unique et directe d’un élément dans le domaine binaire. Par exemple, dans le domaine binaire le plus basique F2, n’importe quelle chaîne de bits k peut être mappée directement à un élément de domaine binaire de bits k. Cela contraste avec le champ des nombres premiers, qui ne peut pas fournir une telle représentation canonique dans la position donnée. Bien qu’un champ de nombres premiers de 32 bits puisse être contenu dans un système de 32 bits, toutes les chaînes de 32 bits ne correspondent pas de manière unique à un élément de domaine, et les champs binaires ont la commodité de ce mappage un-à-un. Dans le domaine premier Fp, les méthodes de réduction courantes comprennent la réduction de Barrett, la réduction de Montgomery et des méthodes de réduction spéciales pour des corps finis spécifiques tels que Mersenne-31 ou Boucle d’Or-64. Dans le domaine binaire F2k, les méthodes de réduction couramment utilisées comprennent la réduction spéciale (par exemple, utilisée dans AES), la réduction de Montgomery (par exemple, utilisée dans POLYVAL) et la réduction récursive (par exemple, Tower). L’article « Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations » souligne que le domaine binaire n’a pas besoin d’introduire le carry à la fois dans l’addition et la multiplication, et que le fonctionnement au carré du domaine binaire est très efficace car il suit (X + Y )2 = x2 + y 2.

! Bitlayer Research : Binius STARKs Principle Analysis and Optimization Thinking

Comme le montre la figure 1, une chaîne de 128 bits : cette chaîne peut être interprétée de différentes manières dans le contexte du domaine binaire. Il peut être considéré comme un élément unique dans un domaine binaire de 128 bits, ou il peut être résolu en deux éléments de tour de 64 bits, quatre éléments de tour de 32 bits, 16 éléments de tour de 8 bits ou 128 éléments de domaine F2. La flexibilité de cette représentation ne nécessite aucune surcharge de calcul, juste un typage de chaînes au niveau du bit, ce qui est une propriété très intéressante et utile. Dans le même temps, les petits éléments de domaine peuvent être regroupés dans des éléments de domaine plus grands sans surcharge de calcul supplémentaire. Le protocole Binius tire parti de cette fonctionnalité pour améliorer l’efficacité de calcul. De plus, l’article « On Efficient Inversion in Tower Fields of Characteristic Two » explore la complexité computationnelle des opérations de multiplication, d’équerrage et d’inversion dans un domaine binaire de tour à n bits qui peut être décomposé en sous-domaines de bits m.

2.2 PIOP : Produit HyperPlonk adapté et PermutationCheck ------ pour les domaines binaires

La conception PIOP dans le protocole Binius emprunte à HyperPlonk et utilise une série de mécanismes de vérification de base pour vérifier l’exactitude des polynômes et des ensembles multivariés. Ces tests de base comprennent :

1. GateCheck : Vérifiez si le témoin confidentiel ω et l’entrée publique x satisfont à la relation de fonctionnement du circuit C(x, ω)=0 pour garantir le bon fonctionnement du circuit.

2. PermutationCheck : Vérifiez que les résultats d’évaluation des deux polynômes multivariés f et g sur l’hypercube booléen sont des relations de permutation f(x) = f(π(x)) pour assurer la cohérence de l’arrangement entre les variables polynomiales.

3. LookupCheck : Vérifiez que le polynôme s’évalue dans une table de recherche donnée, c’est-à-dire f(Bμ) ⊆ T(Bμ), en vous assurant que certaines valeurs sont dans la plage spécifiée.

4. MultisetCheck : Vérifiez si les deux ensembles multivariés sont égaux, c’est-à-dire {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H pour assurer la cohérence entre plusieurs ensembles.

5. ProductCheck : Vérifie si l’évaluation d’un polynôme rationnel sur un hypercube booléen est égale à une valeur déclarée ∏x∈Hμ f(x) = s pour garantir l’exactitude du produit polynomial.

6. ZeroCheck : Vérifiez qu’un polynôme multivarié est nul en tout point de l’hypercube booléen ∏x∈Hμ f(x) = 0,∀x ∈ Bμ pour garantir la distribution nulle du polynôme.

7. SumCheck : Vérifie si la valeur de somme du polynôme multivarié est la valeur déclarée ∑x∈Hμ f(x) = s. En transformant le problème d’évaluation des polynômes multivariés en évaluation polynomiale univariée, la complexité de calcul du vérificateur est réduite. De plus, SumCheck permet également le traitement par lots, en introduisant des nombres aléatoires, en construisant des combinaisons linéaires pour réaliser le traitement par lots de plusieurs instances de contrôle de somme.

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

Bien qu’il existe de nombreuses similitudes entre Binius et HyperPlonk en termes de conception de protocole, Binius a apporté des améliorations dans les trois aspects suivants :

• Optimisation 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 zéro : HyperPlonk ne parvient pas à gérer correctement le cas de division zéro, ce qui entraîne l’incapacité d’affirmer le problème non nul de U sur l’hypercube ; Binius gère cela correctement, et le ProductCheck de Binius continue de traiter même lorsque le dénominateur est zéro, ce qui permet des généralisations à des valeurs de produit arbitraires.

• PermutationCheck : Cette fonctionnalité n’est pas disponible dans HyperPlonk ; Binius prend en charge PermutationCheck entre plusieurs colonnes, ce qui lui permet de gérer des permutations polynomiales plus complexes.

Par conséquent, grâce à l’amélioration du mécanisme PIOPSumCheck existant, Binius améliore la flexibilité et l’efficacité du protocole, en particulier lorsqu’il s’agit de vérifications polynomiales multivariées plus complexes, et fournit un support fonctionnel plus fort. Ces améliorations permettent non seulement de remédier aux limitations d’HyperPlonk, mais aussi de fournir une base binaire pour l’avenir