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 assez petites, mais pour garantir la sécurité des preuves basées sur les arbres de Merkle, de nombreuses valeurs redondantes supplémentaires occupent tout le domaine lors de l'extension des données avec le codage Reed-Solomon. 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 d'opérer directement sur les bits, le codage est compact et efficace sans aucun gaspillage d'espace, c'est-à-dire les STARKs de quatrième génération.

Le domaine binaire est largement utilisé 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

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 totalement dépendre de l'extension de domaine pour assurer sa sécurité et sa réelle utilisabilité.

Binius a proposé une solution innovante :

• Utiliser des polynômes multivariés (en particulier des polynômes multilinaires) à la place de polynômes à une seule variable, en représentant toute la trajectoire de calcul par leurs valeurs sur le "cube hyper".
• Considérez l'hypercube comme un carré et effectuez une extension de Reed-Solomon basée sur ce carré.

2 Analyse des principes

Binius = HyperPlonk PIOP + Brakedown PCS + domaine binaire

Binius comprend cinq technologies clés :

1. Arithmétique basée sur le domaine binaire en tour
2. Vérification des produits et des permutations de la version adaptée de HyperPlonk
3. Nouvelle preuve de décalage multi-linéaire
4. Version améliorée de la recherche Lasso
5. Schéma d'engagement de polynômes à petite portée

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

Avantages du domaine binaire en tour :

• Calcul efficace : le champ binaire prend en charge des opérations arithmétiques hautement efficaces.
• Arithmétique efficace : la structure de champ binaire prend en charge des processus arithmétiques simplifiés
• Représentation flexible : une même chaîne peut être interprétée de plusieurs façons dans le contexte d'un domaine binaire.
• Pas de réduction nécessaire : le champ binaire n'a pas besoin d'introduire des retenues dans les opérations d'addition et de multiplication.
• Calcul efficace des carrés: (X + Y)2 = X2 + Y2

2.2 PIOP: version adaptée du produit HyperPlonk et Vérification de permutation

Mécanisme de vérification central

1. GateCheck
2. PermutationCheck
3. LookupCheck
4. MultisetCheck
5. ProductCheck
6. ZeroCheck
7. SumCheck
8. BatchCheck

Comparé à l'amélioration de HyperPlonk :

• Optimisation de ProductCheck
• Gestion du problème de division par zéro
• Vérification de permutation croisée

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

Méthode clé:

• Emballage : Optimiser l'opération en regroupant les éléments plus petits adjacents dans l'ordre lexicographique en éléments plus grands.
• Opérateurs de décalage : réorganiser les éléments à l'intérieur d'un bloc, en effectuant un décalage circulaire basé sur l'offset donné.

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

Les avantages du protocole Lasso:

• Preuve efficace : pour m recherches dans une table de taille n, il suffit de s'engager m+n éléments de domaine.
• Pas besoin de s'engager sur de grandes tables : si la table t est structurée, il n'est pas nécessaire de s'y engager, on peut traiter des tables très volumineuses.

Composition du protocole Lasso:

• Abstraction de polynômes virtuels de grande table
• Recherche de petite table
• Vérification de plusieurs ensembles

Adaptation de Binius pour Lasso :

• Introduction de la version multiplicative du protocole Lasso
• Exiger que le preneur de preuve s'engage à un vecteur de comptage de lecture qui est partout non nul.

2.5 PCS: version adaptée Brakedown PCS

Idée principale : packing

Deux solutions :

1. Utiliser le code concaténé
2. Utiliser la technologie d'encodage au niveau des blocs, prend en charge l'utilisation distincte des codes Reed-Solomon.

Principales technologies :

• Engagement de petits polynômes et évaluation dans un domaine étendu
• Construction universelle de petit domaine
• Codage de blocs et codes de Reed-Solomon

3 Optimisation de la pensée

Quatre points d'optimisation clés :

1. PIOP basé sur GKR : multiplication binaire
2. Optimisation de ZeroCheck PIOP : Équilibre des coûts de calcul entre Prover et Verifier
3. Optimisation du PIOP Sumcheck : protocole Sumcheck basé sur de petits domaines
4. Optimisation PCS : FRI-Binius réduit la taille de preuve de Binius

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

Idée principale:

Vérifiez si "A·B =? C" pour deux entiers 32 bits A et B. Convertir en "Vérification en cours (gA)B =? gC est-il valable"

Avantages:

• Il suffit d'un engagement auxiliaire
• Réduire le coût des Sumchecks

3.2 ZeroCheck PIOP optimisation

Direction d'optimisation:

• Réduire le transfert de données par le prouvant
• Réduire le nombre de points d'évaluation de la partie prouvante
• Optimisation par interpolation algébrique

3.3 Sumcheck PIOP optimisation

Améliorations clés :

• Choix de changement de tour
• L'impact de la taille du domaine sur la performance
• Les gains d'optimisation de l'algorithme de Karatsuba
• Amélioration de l'efficacité de la mémoire

Effets concrets :

• Dans le cas d'un corps de Galois GF[2], les performances de l'algorithme 4 sont près de 30 fois supérieures à celles de l'algorithme naïf.
• L'algorithme 4 nécessite seulement 0,26 Mo de mémoire, tandis que l'algorithme 3 nécessite 67 Mo.

3.4 PCS Optimisation:FRI-Binius

Quatre points d'innovation:

1. Polynomiale aplatie
2. Polynomiale de disparition du sous-espace
3. Emballage de la base algébrique
4. Échange de sommes de vérification

Efficacité: Réduire la taille de la preuve Binius d'un ordre de grandeur.

4 Conclusion

Les avantages de Binius:

• Peut utiliser le domaine power-of-two minimum pour les témoins
• Faible utilisation de la mémoire, preuve rapide
• A complètement éliminé le goulet d'étranglement des engagements de commit de Prover.

FRI-Binius方案: Éliminer les frais d'intégration du niveau de preuve de domaine sans provoquer une explosion des coûts du niveau de preuve agrégé.

Derniers développements:

• L'équipe Irreducible développe sa couche récursive et collabore avec l'équipe Polygon pour construire un zkVM basé sur Binius.
• JoltzkVM passe de Lasso à Binius pour améliorer ses performances récursives.
• L'équipe Ingonyama est en train de réaliser la version FPGA de Binius