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

1. Introduction

Un des principaux 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 Reed-Solomon pour étendre les données entraîne de nombreuses valeurs redondantes supplémentaires qui occupent tout le domaine. 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 de la deuxième génération est de 64 bits, et celle de la troisième génération est de 32 bits, mais la largeur de code de 32 bits présente encore un grand gaspillage d'espace. En comparaison, le domaine binaire permet des opérations directes sur les bits, le codage est compact et efficace sans aucun gaspillage, c'est-à-dire les STARKs de quatrième génération.

Comparé aux domaines finis tels que Goldilocks, BabyBear, Mersenne31, étudiés ces dernières années, la recherche sur les domaines binaires remonte aux années 80 et est largement utilisée en cryptographie, comme dans le domaine AES(F28, le domaine GMAC)F2128, le code QR( et le codage Reed-Solomon).

Binius utilise un domaine binaire, nécessitant une dépendance complète à un domaine étendu pour garantir la sécurité et la disponibilité. La plupart des calculs Prover fonctionnent efficacement sous le domaine de base, tandis que les vérifications de points aléatoires et les calculs FRI nécessitent une analyse approfondie du domaine étendu pour assurer la sécurité.

Binius utilise des polynômes multivariables pour représenter les trajectoires de calcul sur un "hypercube", en considérant l'hypercube comme un carré pour étendre Reed-Solomon, tout en garantissant la sécurité tout en améliorant considérablement l'efficacité du codage et les performances de calcul.

2. Analyse des principes

Binius:HyperPlonk PIOP + Brakedown PCS + domaine binaire.

Comprend cinq technologies clés :

1. Fondement de calcul arithmétique basé sur le domaine binaire en tour.

2. Adapter les vérifications de produit et de permutation HyperPlonk pour garantir la cohérence des vérifications de variables et de permutations.

3. Nouvelle preuve de décalage multilinéaire, optimisation de l'efficacité de la vérification des relations multilinéaires sur de petits domaines.

4. Version améliorée de la recherche Lasso, offrant flexibilité et sécurité au mécanisme de recherche.

5. Schéma d'engagement de polynômes sur de petits domaines, réalisant un système de preuve efficace sur un domaine binaire.

( 2.1 Domaine fini : arithmétique basée sur les tours de champs binaires

Le domaine binaire en forme de tour prend en charge des opérations arithmétiques efficaces et simplifie le processus arithmétique, ce qui le rend particulièrement adapté aux systèmes de preuve extensibles comme Binius.

Une chaîne de 128 bits peut être considérée comme un élément unique dans un domaine binaire de 128 bits, ou décomposée en deux éléments de domaine de 64 bits, quatre éléments de domaine de 32 bits, seize éléments de domaine de 8 bits, ou 128 éléments de domaine F2. Cette flexibilité ne nécessite aucun coût de calcul, il s'agit simplement d'une conversion de type de chaîne de bits.

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

( 2.2 PIOP: version modifiée du produit HyperPlonk et vérification de permutation

Binius PIOP s'inspire de HyperPlonk et utilise un mécanisme de vérification central pour valider la correctitude des polynômes et des ensembles multivariables, y compris GateCheck, PermutationCheck, LookupCheck, MultisetCheck, ProductCheck, ZeroCheck, SumCheck, BatchCheck.

Binius a amélioré les 3 aspects suivants :

• Optimisation de ProductCheck : spécialiser la valeur à 1, simplifier le processus de vérification pour réduire la complexité de calcul.

• Gestion des problèmes de division par zéro : traiter correctement les cas où le dénominateur est zéro, permettant une généralisation à n'importe quelle valeur de produit.

• Vérification de permutation intercolonnes : prend en charge la vérification de permutation entre plusieurs colonnes, traitant des cas de permutation polynomiale plus complexes.

) 2.3 PIOP : nouvel argument de décalage multilinéraire

La construction et le traitement des polynômes virtuels dans Binius sont des technologies clés:

• Packing : regrouper les éléments de plus petite taille en positions adjacentes dans le dictionnaire pour optimiser l'opération.

• Opérateurs de décalage: réorganiser les éléments à l'intérieur du bloc, en fonction d'un décalage donné.

![Bitlayer Research : Analyse des principes de Binius STARKs et réflexions sur son optimisation]###https://img-cdn.gateio.im/webp-social/moments-a5d031be4711f29ef910057f4e44a118.webp###

( 2.4 PIOP: version adaptée de l'argument de recherche Lasso

Le protocole Lasso permet à la partie prouvante de s'engager sur un vecteur a ∈ Fm et de prouver que tous les éléments existent dans une table préalablement spécifiée t ∈ Fn.

Binius adapte Lasso aux opérations sur les corps binaires, introduisant une version multiplicative du protocole Lasso, qui exige que le prouveur et le vérificateur collaborent sur l'opération "compte mémoire" du protocole d'incrémentation, générant des incréments par multiplication dans le corps binaire.

) 2.5 PCS: version adaptée Brakedown PCS

La pensée centrale de BiniusPCS est le packing. Deux solutions de promesse polynomiale Brakedown basées sur un domaine binaire sont fournies:

1. Instancier le code concaténé

2. Utiliser la technologie de codage au niveau des blocs, supporte l'utilisation indépendante des codes de Reed-Solomon.

La deuxième solution simplifie le processus de preuve et de vérification, la taille de la preuve est légèrement plus grande, mais les avantages de la simplification et de la mise en œuvre en valent la peine.

![Bitlayer Research : Analyse des principes STARKs de Binius et réflexions sur leur optimisation]###https://img-cdn.gateio.im/webp-social/moments-d74bdd8bc21dcfc05e21f9c0074461c3.webp###

3. Optimisation de la pensée

( 3.1 PIOP basé sur GKR : multiplication de domaine binaire basée sur GKR

Convertir "vérifier si deux entiers 32 bits A et B satisfont A·B =? C" en "vérifier si )gA###B =? gC est vrai", en utilisant le protocole GKR pour réduire considérablement les coûts d'engagement.

Les opérations de multiplication basées sur GKR nécessitent seulement un engagement auxiliaire, rendant l'algorithme plus efficace en réduisant les coûts des Sumchecks, en particulier dans les scénarios où les opérations de Sumchecks sont moins coûteuses que la génération d'engagements.

( 3.2 ZeroCheck PIOP optimisation : compromis sur les coûts de calcul entre Prover et Verifier

Réduire le transfert de données du prouveur : transférer une partie du travail à la partie vérificatrice, réduisant ainsi la quantité de données envoyées par le prouveur.

Réduire le nombre de points d'évaluation des preuves : modifier la méthode d'envoi des polynômes pour réduire le nombre de points d'évaluation.

Optimisation d'interpolation algébrique : construction d'une décomposition ordonnée par division longue de polynômes pour réaliser l'optimisation d'interpolation.

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

( 3.3 Optimisation PIOP de Sumcheck : protocole Sumcheck basé sur un petit domaine

L'impact et le facteur d'amélioration du changement de cycle : Le choix du cycle t affecte la performance, le facteur d'amélioration au meilleur point de changement atteint sa valeur maximale.

Impact de la taille du champ de base sur la performance : un champ de base plus petit ) tel que GF###( montre des avantages d'optimisation plus significatifs.

Optimisation des bénéfices de l'algorithme de Karatsuba : amélioration significative des performances de Sumcheck sur petits domaines, l'algorithme 4 est cinq fois plus efficace que l'algorithme 3.

Amélioration de l'efficacité de la mémoire : l'algorithme 4 nécessite O[2]d·t), l'algorithme 3 nécessite O(2d·t), adapté aux environnements aux ressources limitées.

( 3.4 PCS Optimisation : FRI-Binius réduction de la taille de preuve de Binius

FRI-Binius met en œuvre le mécanisme de repli de domaine binaire FRI, apportant 4 innovations :

• Polynomiale aplatie
• Polynomede disparition de sous-espace
• Emballage de base algébrique
• Échange de somme de cercle

Grâce à FRI-Binius, la taille des preuves Binius peut être réduite d'un ordre de grandeur, approchant les systèmes les plus avancés.

![Bitlayer Research : Analyse des principes de Binius STARKs et réflexion sur son optimisation])https://img-cdn.gateio.im/webp-social/moments-16690fad3bc761b99c40e8e82ab2297c.webp###

4. Conclusion

Binius a essentiellement éliminé le goulot d'étranglement des engagements Prover, le nouveau goulot d'étranglement étant le protocole Sumcheck. Le schéma FRI-Binius est une variante de FRI, capable d'éliminer les coûts d'intégration du niveau de preuve de domaine.

L'équipe Irreducible développe une couche récursive, en collaboration avec Polygon pour construire un zkVM basé sur Binius. JoltzkVM passe de Lasso à Binius pour améliorer les performances récursives. Ingonyama réalise une version FPGA de Binius.