Analyse des principes STARKs de Binius et réflexions sur l'optimisation
1. Introduction
L'une des principales raisons de l'inefficacité des STARKs est que la plupart des valeurs dans les programmes réels sont relativement 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 de redondance supplémentaires qui occupent tout le domaine. Réduire la taille du domaine est devenu 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 la largeur de codage de 32 bits présente encore un grand espace de gaspillage. En revanche, le domaine binaire permet une manipulation directe des bits, le codage est compact et efficace sans aucun espace de gaspillage, c'est-à-dire les STARKs de quatrième génération.
Binius utilise un domaine binaire, nécessitant une dépendance complète à un domaine étendu pour garantir sa sécurité et sa praticabilité. La plupart des polynômes impliqués dans les calculs Prover n'ont pas besoin d'entrer dans un domaine étendu, mais peuvent être manipulés dans le domaine de base, permettant ainsi une grande efficacité dans le petit domaine. Cependant, les vérifications de points aléatoires et les calculs FRI doivent encore plonger dans un domaine étendu plus grand pour assurer la sécurité requise.
Binius a proposé une solution innovante : tout d'abord, en utilisant un polynôme multivarié (en particulier un polynôme multilinéraire) au lieu d'un polynôme à variable unique, pour représenter l'ensemble de la trajectoire de calcul par ses valeurs sur l'"hypercube" ; ensuite, en considérant l'hypercube comme un carré, en se basant sur ce carré pour effectuer une extension de Reed-Solomon. Cette méthode améliore considérablement l'efficacité du codage et les performances de calcul tout en garantissant la sécurité.
2. Analyse des principes
Binius comprend cinq technologies clés :
Arithmetic basé sur le domaine binaire en forme de tour
Vérification des produits et des permutations de la version adaptée de HyperPlonk
Nouvelle preuve de décalage multilinéraire
Version améliorée de la recherche Lasso
Schéma d'engagement de polynômes de petite dimension
2.1 Domain fini : arithmétisation basée sur les tours de corps binaires
Le domaine binaire en forme de tour prend en charge des opérations arithmétiques très efficaces et soutient un processus arithmétique simplifié. Les éléments du domaine binaire ont une représentation unique et directe, ce qui permet de les convertir et de les empaqueter de manière flexible entre différents domaines de taille.
2.2 PIOP: version adaptée du produit HyperPlonk et PermutationCheck
Binius a adopté une série de mécanismes de contrôle essentiels, y compris GateCheck, PermutationCheck, LookupCheck, MultisetCheck, ProductCheck, ZeroCheck, SumCheck et BatchCheck.
Comparé à HyperPlonk, Binius a amélioré les aspects suivants :
Optimisation de ProductCheck
Traitement du problème de division par zéro
Vérification de permutation croisée
2.3 PIOP : nouvel argument de décalage multilinéraire
Binius utilise deux méthodes clés, Packing et l'opérateur de décalage, pour traiter les polynômes virtuels.
2.4 PIOP: version adaptée de l'argument de recherche Lasso
Le protocole Lasso est composé de trois composants :
Abstraction de polynômes virtuels à grande échelle
Recherche de petite table
Vérification de plusieurs ensembles
Binius a introduit une version multiplicative du protocole Lasso, exigeant que la partie prouvante et la partie vérificatrice incrémentent conjointement l'opération de "compte mémoire" du protocole, non pas par une simple incrémentation de 1, mais plutôt en incrémentant à l'aide d'un générateur multiplicatif dans un corps binaire.
2.5 PCS: version adaptée Brakedown PCS
L'engagement polynomial de Binius utilise principalement :
Engagements de petits polynômes et évaluations de champs étendus
Construction universelle de petit domaine
Codage de bloc et technologie des codes de Reed-Solomon
3. Optimisation de la réflexion
3.1 PIOP basé sur GKR : multiplication de domaine binaire basée sur GKR
L'algorithme de multiplication d'entiers basé sur GKR, transforme "vérifier si 2 entiers 32 bits A et B satisfont A·B =? C" en "vérifier si (gA)B =? gC est vrai", réduisant considérablement le coût d'engagement grâce au protocole GKR.
3.2 ZeroCheck PIOP optimisation : compromis entre les coûts de calcul de Prover et Verifier
Réduire le transfert de données par la partie de preuve
Réduire le nombre de points d'évaluation des parties vérificatrices
Optimisation par interpolation algébrique
3.3 Optimisation PIOP Sumcheck : protocole Sumcheck basé sur un petit domaine
Impact et facteur d'amélioration du changement de cycle
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
3.4 PCS Optimisation : FRI-Binius réduction de la taille de preuve Binius
FRI-Binius a réalisé un mécanisme de pliage FRI dans le domaine binaire, apportant quatre innovations :
Polynomiale aplatie
Polynomiale de disparition de sous-espace
Emballage de base algébrique
Échange de somme de circuits
4. Conclusion
Binius a quasiment complètement éliminé le goulet d'étranglement des engagements commit de Prover, le nouveau goulet d'étranglement réside dans le protocole Sumcheck. Le schéma FRI-Binius est une variante de FRI, qui peut éliminer le coût d'incorporation du niveau de preuve de domaine. Actuellement, l'équipe Irreducible développe son niveau récursif et collabore avec l'équipe Polygon pour construire un zkVM basé sur Binius ; JoltzkVM passe de Lasso à Binius ; l'équipe Ingonyama met en œuvre une version FPGA de Binius.
Voir l'original
Cette page peut inclure du contenu de tiers fourni à des fins d'information uniquement. Gate ne garantit ni l'exactitude ni la validité de ces contenus, n’endosse pas les opinions exprimées, et ne fournit aucun conseil financier ou professionnel à travers ces informations. Voir la section Avertissement pour plus de détails.
14 J'aime
Récompense
14
5
Partager
Commentaire
0/400
WalletDivorcer
· 07-27 05:08
Si tu ne parles que de sécurité, tu as déjà perdu...soupir
Voir l'originalRépondre0
Anon4461
· 07-24 16:08
Qui cette titre de thèse trompe-t-il v几
Voir l'originalRépondre0
ProofOfNothing
· 07-24 16:06
La largeur de bande de 252 à 32 n'est pas encore assez basse.
Voir l'originalRépondre0
RugPullAlertBot
· 07-24 16:00
J'ai entendu dire que les preuves à divulgation nulle de connaissance coûtent encore de l'argent.
Voir l'originalRépondre0
StakeOrRegret
· 07-24 15:55
J'ai lu le document trois fois, je n'ai rien compris.
Binius STARKs : innovation de preuve zéro connaissance à haute efficacité basée sur le domaine binaire
Analyse des principes STARKs de Binius et réflexions sur l'optimisation
1. Introduction
L'une des principales raisons de l'inefficacité des STARKs est que la plupart des valeurs dans les programmes réels sont relativement 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 de redondance supplémentaires qui occupent tout le domaine. Réduire la taille du domaine est devenu 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 la largeur de codage de 32 bits présente encore un grand espace de gaspillage. En revanche, le domaine binaire permet une manipulation directe des bits, le codage est compact et efficace sans aucun espace de gaspillage, c'est-à-dire les STARKs de quatrième génération.
Binius utilise un domaine binaire, nécessitant une dépendance complète à un domaine étendu pour garantir sa sécurité et sa praticabilité. La plupart des polynômes impliqués dans les calculs Prover n'ont pas besoin d'entrer dans un domaine étendu, mais peuvent être manipulés dans le domaine de base, permettant ainsi une grande efficacité dans le petit domaine. Cependant, les vérifications de points aléatoires et les calculs FRI doivent encore plonger dans un domaine étendu plus grand pour assurer la sécurité requise.
Binius a proposé une solution innovante : tout d'abord, en utilisant un polynôme multivarié (en particulier un polynôme multilinéraire) au lieu d'un polynôme à variable unique, pour représenter l'ensemble de la trajectoire de calcul par ses valeurs sur l'"hypercube" ; ensuite, en considérant l'hypercube comme un carré, en se basant sur ce carré pour effectuer une extension de Reed-Solomon. Cette méthode améliore considérablement l'efficacité du codage et les performances de calcul tout en garantissant la sécurité.
2. Analyse des principes
Binius comprend cinq technologies clés :
2.1 Domain fini : arithmétisation basée sur les tours de corps binaires
Le domaine binaire en forme de tour prend en charge des opérations arithmétiques très efficaces et soutient un processus arithmétique simplifié. Les éléments du domaine binaire ont une représentation unique et directe, ce qui permet de les convertir et de les empaqueter de manière flexible entre différents domaines de taille.
2.2 PIOP: version adaptée du produit HyperPlonk et PermutationCheck
Binius a adopté une série de mécanismes de contrôle essentiels, y compris GateCheck, PermutationCheck, LookupCheck, MultisetCheck, ProductCheck, ZeroCheck, SumCheck et BatchCheck.
Comparé à HyperPlonk, Binius a amélioré les aspects suivants :
2.3 PIOP : nouvel argument de décalage multilinéraire
Binius utilise deux méthodes clés, Packing et l'opérateur de décalage, pour traiter les polynômes virtuels.
2.4 PIOP: version adaptée de l'argument de recherche Lasso
Le protocole Lasso est composé de trois composants :
Binius a introduit une version multiplicative du protocole Lasso, exigeant que la partie prouvante et la partie vérificatrice incrémentent conjointement l'opération de "compte mémoire" du protocole, non pas par une simple incrémentation de 1, mais plutôt en incrémentant à l'aide d'un générateur multiplicatif dans un corps binaire.
2.5 PCS: version adaptée Brakedown PCS
L'engagement polynomial de Binius utilise principalement :
3. Optimisation de la réflexion
3.1 PIOP basé sur GKR : multiplication de domaine binaire basée sur GKR
L'algorithme de multiplication d'entiers basé sur GKR, transforme "vérifier si 2 entiers 32 bits A et B satisfont A·B =? C" en "vérifier si (gA)B =? gC est vrai", réduisant considérablement le coût d'engagement grâce au protocole GKR.
3.2 ZeroCheck PIOP optimisation : compromis entre les coûts de calcul de Prover et Verifier
3.3 Optimisation PIOP Sumcheck : protocole Sumcheck basé sur un petit domaine
3.4 PCS Optimisation : FRI-Binius réduction de la taille de preuve Binius
FRI-Binius a réalisé un mécanisme de pliage FRI dans le domaine binaire, apportant quatre innovations :
4. Conclusion
Binius a quasiment complètement éliminé le goulet d'étranglement des engagements commit de Prover, le nouveau goulet d'étranglement réside dans le protocole Sumcheck. Le schéma FRI-Binius est une variante de FRI, qui peut éliminer le coût d'incorporation du niveau de preuve de domaine. Actuellement, l'équipe Irreducible développe son niveau récursif et collabore avec l'équipe Polygon pour construire un zkVM basé sur Binius ; JoltzkVM passe de Lasso à Binius ; l'équipe Ingonyama met en œuvre une version FPGA de Binius.