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

1. Introduction

Une des principales raisons de l'inefficacité des STARKs est que dans les programmes réels, la plupart des valeurs sont assez 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 redondantes supplémentaires qui occupent tout le domaine, même si les valeurs d'origine sont très petites. Réduire la taille du domaine devient une stratégie clé.

La largeur de codage 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 les 32 bits présentent encore un grand gaspillage d'espace. Le domaine binaire permet des opérations directes sur les bits, avec un codage compact, efficace et sans gaspillage, ce qui pourrait être la quatrième génération des STARKs.

Le domaine binaire est largement utilisé en cryptographie, comme AES(F28), GMAC(F2128), QR code(F28), etc. Lorsque l'on utilise des domaines plus petits, l'opération d'extension 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 pour assurer la sécurité et la disponibilité. La plupart des calculs de Prover fonctionnent sous le champ de base, de manière efficace; les contrôles de points aléatoires et les calculs FRI nécessitent d'aller plus en profondeur dans un domaine d'extension plus grand pour assurer la sécurité.

Solutions innovantes de Binius :

1. utilise des polynômes multivariables ( en plusieurs variables ) à la place des polynômes univariables, en représentant la trajectoire de calcul par des valeurs de "hypercube".
2. considérer le hypercube comme un carré, étendre Reed-Solomon basé sur le carré

2. Analyse des principes

Binius = HyperPlonk PIOP + Brakedown PCS + domaine binaire

Cinq technologies clés :

1. arithmétisation basée sur le domaine binaire en tour
2. Adaptation de l'HyperPlonk pour les vérifications de produit et de permutation
3. Nouvelle preuve de décalage multilinéraire
4. version améliorée de la recherche Lasso
5. schéma d'engagement de polynômes à petite échelle

2.1 Domain fini : arithmétisation basée sur les tours de champs binaires

Avantages du domaine binaire en tour :

• Calcul efficace : le champ binaire prend en charge des opérations arithmétiques efficaces
• Arithmetic efficace : la structure du champ binaire prend en charge le processus d'arithmétisation simplifié.
• Profiter pleinement des caractéristiques hiérarchiques grâce à la structure en tour

Une chaîne de 128 bits peut être interprétée de manière flexible :

• Un élément unique dans un domaine binaire de 128 bits
• Deux éléments de domaine de tour de 64 bits
• Quatre éléments de domaine de 32 bits
• 16 éléments de domaine de tour de 8 bits
• 128 éléments de domaine F2

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

Mécanisme de vérification du cœur de Binius:

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

Amélioration de Binius sur HyperPlonk :

• Optimisation de ProductCheck
• Traiter correctement le problème de division par zéro
• Prise en charge de la vérification de permutation intercolonnes

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

Méthode clé:

• Packing : regrouper des éléments plus petits adjacents en éléments plus grands
• Opérateur de décalage : réorganiser les éléments à l'intérieur du bloc

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

Avantages du protocole Lasso:

• Efficacité de preuve élevée : engagement de m+n éléments de domaine
• Pas besoin de s'engager sur un grand tableau : peut traiter des tableaux très grands

Binius introduit la version multiplicative du protocole Lasso :

• Générer un "compteur mémoire" incrémental par multiplication dans le domaine binaire
• Le preneur d'engagement garantit un vecteur de comptage de lecture non nul pour assurer la sécurité.

2.5 PCS: version adaptée Brakedown PCS

Idée principale : packing

Deux solutions :

1. Instancier le code concaténé
2. Utiliser l'encodage au niveau des blocs, prend en charge l'utilisation autonome des codes de Reed-Solomon.

Engagements de polynômes sur de petits domaines et évaluation sur des domaines étendus:

• S'engager sur le petit domaine K
• Évaluer dans un domaine d'expansion plus large L/K

Codage par blocs et code de Reed-Solomon :

• Autoriser le petit domaine ( comme le polynôme F2) à utiliser l'alphabet majuscule ( comme le code Reed-Solomon F216) pour des engagements efficaces.

3. Optimisation de la pensée

Quatre points clés d'optimisation :

3.1 PIOP basé sur GKR : multiplication de champs binaires basée sur GKR

Transformez "vérifier A·B =? C" en "vérifier (gA)B =? gC"

• Il suffit d'un engagement auxiliaire
• Réduire les frais de Sumchecks

3.2 Optimisation de ZeroCheck PIOP : Équilibre des coûts de calcul entre Prover et Verifier

Méthode d'optimisation:

• Réduire le transfert de données des parties prouvantes
• Réduire le nombre de points d'évaluation des parties vérificatrices
• Optimisation par interpolation algébrique

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

Amélioration des points clés :

• Sélection de l'itération t
• L'impact de la taille du domaine
• Optimisation de l'algorithme de Karatsuba
• Amélioration de l'efficacité de la mémoire

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

Quatre innovations:

1. Polynôme aplati
2. Polynomiale de disparition de sous-espace
3. Emballage de la base algébrique
4. Échange de somme de vérification

FRI-Binius peut réduire la taille de la preuve Binius d'un ordre de grandeur.

4. Conclusion

Avantages de Binius:

• Peut être utilisé pour des témoins avec le domaine power-of-two minimal.
• Faible utilisation de la mémoire pour une preuve rapide
• Supprimer essentiellement le goulet d'étranglement de l'engagement Prover

Nouveau goulot d'étranglement : protocole Sumcheck

• Peut être efficacement résolu à l'aide de matériel spécialisé

FRI-Binius:

• Éliminer les coûts d'intégration de la preuve de domaine
• Ne pas entraîner une augmentation des coûts de la couche de preuve de participation.

Progrès actuel:

• 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
• Ingonyama réalise la version FPGA de Binius