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

1 Introduction

Une des principales raisons pour lesquelles les STARKs sont inefficaces est que : la plupart des valeurs dans les programmes réels sont assez petites, mais 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 redondantes 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, réduire la taille du domaine est devenu une stratégie clé.

La largeur de code 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 code de 32 bits présente encore beaucoup d'espace gaspillé. En revanche, le domaine binaire permet d'opérer directement sur les bits, avec 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 découverts ces dernières années, 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 :

• Standard de chiffrement avancé ( AES ), basé 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 de SHA-3, basée sur le domaine F28, est un algorithme de hachage très adapté à la récursivité.

Lorsqu'un petit domaine est utilisé, 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 assurer sa sécurité et sa praticité. La plupart des polynômes impliqués dans le calcul des Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais doivent seulement 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 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 un domaine binaire, deux problèmes pratiques se posent : lors du calcul de la représentation de 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 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 (en particulier des polynômes multilinéaires) au lieu de polynômes univariables, pour représenter l'ensemble de la trajectoire de calcul par ses valeurs sur des "hypercubes" ; ensuite, étant donné que chaque dimension de l'hypercube a une longueur de 2, il n'est pas possible de faire une extension de Reed-Solomon standard comme avec les STARKs, mais l'hypercube peut être considéré comme un carré, et l'extension de Reed-Solomon peut être faite sur ce carré. Cette méthode augmente considérablement l'efficacité du codage et la performance computationnelle 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 cœur du système de preuve, transforme les relations de calcul en égalités polynomiales vérifiables. Différents protocoles PIOP permettent au prouveur d'envoyer progressivement des polynômes grâce à l'interaction avec le vérificateur, de sorte que le vérificateur puisse vérifier si le calcul est correct en interrogeant un petit nombre de résultats d'évaluation des 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, ce qui affecte les performances 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. Le PCS est un outil cryptographique qui permet au 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 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, entre autres. Différents PCS présentent différentes performances, niveaux de sécurité et cas d'utilisation.

Selon les besoins spécifiques, choisissez différents PIOP et PCS, et associez-les à un champ fini ou une courbe elliptique appropriée, ce qui permet 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 est conçu avec un accent sur l'évolutivité et pour éliminer le trusted setup du protocole ZCash.

• Plonky2 : utilise PLONK PIOP combiné avec FRI PCS et est basé sur le domaine de Goldilocks. Plonky2 est conçu pour réaliser une récursion efficace. Lors de la conception de ces systèmes, le PIOP et le PCS sélectionnés doivent correspondre au corps fini ou à la courbe elliptique utilisés, afin d'assurer la correctitude, la performance et la sécurité du système. Le choix de ces combinaisons influence non seulement la taille des preuves 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. Concrètement, Binius comprend cinq technologies clés pour réaliser son efficacité et sa sécurité. Premièrement, l'arithmétique basée sur les tours de domaines binaires constitue la base de ses calculs, permettant des opérations simplifiées dans le domaine binaire. Deuxièmement, Binius a adapté la vérification des produits et des permutations dans son protocole de preuve Oracle interactif (PIOP) HyperPlonk, garantissant une vérification cohérente et sécurisée 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 dans le domaine binaire et réduisant les frais généralement associés aux grands domaines.

2.1 Corps finis : arithmétisation basée sur les tours de champs binaires

Les corps binaires en tour sont la clé de la réalisation de calculs rapides et vérifiables, principalement en raison de deux aspects : le calcul efficace et l'arithmétisation 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 prend en charge un processus d'arithmétisation simplifié, c'est-à-dire que les opérations effectuées sur des corps binaires 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 leurs caractéristiques hiérarchiques grâce à la structure en tour, rendent les corps binaires particulièrement adaptés à des systèmes de preuve extensibles tels que Binius.

Le terme "canonical" fait référence à la représentation unique et directe des éléments dans le domaine binaire. Par exemple, dans le domaine binaire de base F2, toute chaîne de k bits peut être directement mappée à un élément du domaine binaire de k bits. Cela diffère des domaines premiers, qui ne peuvent pas fournir cette représentation canonique dans un nombre de bits donné. Bien qu'un domaine premier de 32 bits puisse être contenu dans 32 bits, cela ne signifie pas que chaque chaîne de 32 bits correspond de manière unique à un élément du domaine, alors que le domaine binaire présente 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 couramment utilisées 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). 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 de retenue 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 illustré 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 tour de 64 bits, quatre éléments de domaine tour de 32 bits, seize éléments de domaine 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 la 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ûts de calcul supplémentaires. Le protocole Binius tire parti de cette caractéristique pour améliorer l'efficacité du calcul. De plus, 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 tour de n bits (décomposable en sous-domaines de m bits).

2.2 PIOP : version adaptée du produit HyperPlonk et vérification de permutation ------ applicable aux corps binaires

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

1. GateCheck : Vérifiez si le témoin de confidentialité ω et l'entrée publique x satisfont la relation d'opération du circuit C(x,ω)=0, afin de garantir le bon fonctionnement du circuit.

2. PermutationCheck : Vérifie si les résultats d'évaluation des deux polynômes multivariables f et g sur l'hypercube booléen sont une relation de permutation f(x) = f(π(x)), afin d'assurer 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µ), garantissant que certaines valeurs se situent 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 à coefficients rationnels sur le cube hyperbolique booléen est égale à une valeur déclarée ∏x∈Hµ f(x) = s, afin d'assurer l'exactitude du produit polynomial.

6. ZeroCheck : Vérifier si un polynôme multivariable à plusieurs variables est nul à un point quelconque du cube hyperbolique booléen ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, afin d'assurer 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 de polynômes multivariables en évaluation de polynômes à une variable, 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 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 de l'évaluation de plusieurs polynômes multivariés afin d'améliorer l'efficacité du protocole.

Bien que Binius et HyperPlonk aient de nombreuses similitudes dans la conception de leurs 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 le cube 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 zéro, le ProductCheck de Binius peut continuer à traiter, permettant ainsi une généralisation à n'importe quelle valeur de produit.

• Vérification de permutation inter-colonnes : 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é la flexibilité et l'efficacité du protocole grâce à des modifications apportées au mécanisme existant de PIOPSumCheck, offrant un support fonctionnel renforcé, en particulier pour le traitement de la validation de polynômes multivariables 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 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 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 :

• Emballage : Cette méthode consiste à réduire les éléments plus petits à des positions adjacentes dans l'ordre lexicographique.