Analyse des principes de Binius STARKs et réflexions sur son optimisation
1 Introduction
Un des principaux problèmes d'efficacité 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, l'utilisation du codage de Reed-Solomon pour étendre les données entraîne l'occupation de nombreux valeurs redondantes supplémentaires sur tout le domaine. Pour résoudre ce problème, réduire la taille du domaine est devenu une stratégie clé.
La largeur de code de la première génération de STARKs 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. Cependant, la largeur de code de 32 bits présente encore un grand nombre d'espaces gaspillés. En comparaison, le domaine binaire permet d'opérer directement sur les bits, avec un codage compact et efficace sans aucun espace gaspillé, c'est-à-dire la quatrième génération de STARKs.
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 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 les calculs Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais doivent simplement opérer sous le domaine de base, réalisant ainsi une haute 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.
Binius a proposé une solution innovante, traitant respectivement ces deux problèmes et représentant les mêmes données de deux manières différentes : d'abord, en utilisant des polynômes multivariés (en particulier des polynômes multilinaires) à la place de polynômes univariés, en représentant l'ensemble de la trajectoire de calcul par leurs valeurs sur des "hypercubes" ; ensuite, étant donné que chaque dimension de l'hypercube a une longueur de 2, il n'est pas possible de procéder à une extension de Reed-Solomon standard comme avec les STARKs, mais on peut considérer l'hypercube comme un carré, et effectuer l'extension de Reed-Solomon basée sur ce carré. 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 : HyperPlonk PIOP + Brakedown PCS + domaine binaire. Plus précisément, Binius comprend cinq technologies clés pour réaliser son efficacité et sa sécurité :
Arithmétique basée sur des tours de champs binaires
Adapté les vérifications de produit et de permutation HyperPlonk
Nouvelle démonstration de décalage multilinéal
Version améliorée de la démonstration de recherche Lasso
Schéma d'engagement de polynômes à petits domaines (Small-Field PCS)
2.1 Domaine fini : arithmétique basée sur les tours de corps binaires
Le domaine binaire en forme de tour est clé pour réaliser des calculs vérifiables rapides, principalement en raison de deux aspects : le calcul efficace et l'arithmétisation efficace. Le domaine binaire prend essentiellement en charge 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 du domaine binaire soutient un processus d'arithmétisation simplifié, c'est-à-dire que les opérations effectuées sur le domaine binaire peuvent être représentées sous une forme algébrique compacte et facile à vérifier.
2.2 PIOP : version adaptée du produit HyperPlonk et PermutationCheck
La conception de PIOP dans le protocole Binius s'inspire de HyperPlonk et utilise une série de mécanismes de vérification essentiels pour valider l'exactitude des polynômes et des ensembles multivariables. Ces vérifications essentielles comprennent :
GateCheck
PermutationCheck
LookupCheck
MultisetCheck
ProductCheck
ZeroCheck
SumCheck
BatchCheck
Binius a apporté des améliorations dans les 3 domaines suivants :
Optimisation de ProductCheck
Traitement des problèmes de division par zéro
Vérification de permutation intercolonnes
2.3 PIOP : nouvel argument de décalage multiligne
Dans le protocole Binius, la construction et le traitement des polynômes virtuels sont l'une des technologies clés, comprenant principalement deux méthodes :
Emballage
Opérateur de décalage
2.4 PIOP : argument de recherche Lasso adapté
Le protocole Lasso est composé des trois composants suivants :
Abstraction des polynômes virtuels de grande table
Recherche de petite table
Vérification de plusieurs ensembles
Le protocole Binius adapte Lasso aux opérations dans le domaine binaire, introduisant une version multiplicative du protocole Lasso.
2.5 PCS : version adaptée Brakedown PCS
La pensée fondamentale derrière la construction de BiniusPCS est le packing. L'engagement polynomial de Binius utilise principalement :
Engagement de petit polynôme et évaluation dans un domaine étendu
Construction universelle de petits domaines
Codage en bloc et codes de Reed-Solomon
3 Optimisation de la pensée
Pour améliorer davantage les performances du protocole Binius, cet article propose quatre points d'optimisation clés :
PIOP basé sur GKR : pour les opérations de multiplication dans le domaine binaire
Optimisation ZeroCheck PIOP : Équilibrer les coûts de calcul entre le Prover et le Verifier.
Optimisation de Sumcheck PIOP : optimisation pour les Sumchecks de petit domaine
Optimisation PCS : réduction de la taille de preuve grâce à l'optimisation FRI-Binius
3.1 PIOP basé sur GKR : multiplication de domaine binaire basée sur GKR
L'algorithme de multiplication d'entiers basé sur GKR, en transformant "vérifier si 2 entiers de 32 bits A et B satisfont A·B =? C" en "vérifier si (gA)B =? gC est vrai", réduit considérablement les frais d'engagement grâce au protocole GKR.
3.2 ZeroCheck PIOP optimisation : compromis entre les coûts de calcul du Prover et du Verifier
Les principales orientations d'optimisation comprennent les suivantes :
Réduire le transfert de données entre les parties prenantes.
Réduire le nombre de points d'évaluation pour le prouveur
Optimisation par interpolation algébrique
3.3 Optimisation de PIOP Sumcheck : protocole Sumcheck basé sur des petits domaines
Les principaux points d'optimisation incluent :
L'impact et le facteur d'amélioration du changement de tour
L'impact de la taille du domaine sur la performance
Les bénéfices de l'optimisation de l'algorithme de Karatsuba
Amélioration de l'efficacité de la mémoire
3.4 PCS Optimisation : FRI-Binius réduit la taille de preuve de Binius
FRI-Binius a mis en œuvre le mécanisme de pliage FRI dans le domaine binaire, apportant 4 innovations :
Polygone aplati
Polynôme de disparition de sous-espace
Emballage de base algébrique
Échange de somme circulaire
4 Conclusion
La proposition de valeur de Binius est de permettre aux témoins d'utiliser le plus petit domaine de puissance de deux, de sorte qu'il suffit de choisir la taille du domaine en fonction des besoins. Binius est une solution de conception collaborative qui utilise "du matériel, des logiciels et le protocole Sumcheck accéléré par FPGA", permettant de prouver rapidement avec une très faible utilisation de mémoire.
Binius a presque complètement éliminé le goulot d'étranglement des engagements de Prover, le nouveau goulot d'étranglement réside dans le protocole Sumcheck. Les problèmes liés à de nombreuses évaluations de polynômes et aux multiplications dans le domaine au sein du protocole Sumcheck peuvent être résolus de manière efficace grâce à du matériel spécialisé. Le schéma FRI-Binius est une variante du FRI, offrant un choix très attrayant - éliminer les coûts d'incorporation du niveau de preuve dans le domaine sans entraîner une explosion des coûts au niveau de la preuve agrégée.
Actuellement, l'équipe d'Irreducible développe sa couche récursive et a annoncé une collaboration avec l'équipe de Polygon pour construire un zkVM basé sur Binius ; JoltzkVM passe de Lasso à Binius pour améliorer ses performances récursives ; l'équipe d'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.
12 J'aime
Récompense
12
6
Partager
Commentaire
0/400
SilentObserver
· 07-16 18:11
Comment l'efficacité a-t-elle augmenté autant ?
Voir l'originalRépondre0
StakeOrRegret
· 07-16 11:52
C'est ce que j'ai toujours dit, combien de ressources faut-il gaspiller pour évoluer vers la véritable quatrième génération.
Voir l'originalRépondre0
Ser_This_Is_A_Casino
· 07-16 06:56
On est déjà à la quatrième génération ici.
Voir l'originalRépondre0
AirdropHunterXiao
· 07-15 16:49
Airdrop est devenu une compétition, je passe mes journées à étudier cela de manière approfondie.
Voir l'originalRépondre0
CodeSmellHunter
· 07-15 16:44
stark嗲气666
Répondre0
RektRecorder
· 07-15 16:41
Je préfère regarder les jetons de l'extérieur que cette pile de mysticisme.
Solution d'optimisation Binius STARKs : arithmétique sur les champs binaires et polynômes multilinaires pour améliorer l'efficacité
Analyse des principes de Binius STARKs et réflexions sur son optimisation
1 Introduction
Un des principaux problèmes d'efficacité 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, l'utilisation du codage de Reed-Solomon pour étendre les données entraîne l'occupation de nombreux valeurs redondantes supplémentaires sur tout le domaine. Pour résoudre ce problème, réduire la taille du domaine est devenu une stratégie clé.
La largeur de code de la première génération de STARKs 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. Cependant, la largeur de code de 32 bits présente encore un grand nombre d'espaces gaspillés. En comparaison, le domaine binaire permet d'opérer directement sur les bits, avec un codage compact et efficace sans aucun espace gaspillé, c'est-à-dire la quatrième génération de STARKs.
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 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 les calculs Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais doivent simplement opérer sous le domaine de base, réalisant ainsi une haute 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.
Binius a proposé une solution innovante, traitant respectivement ces deux problèmes et représentant les mêmes données de deux manières différentes : d'abord, en utilisant des polynômes multivariés (en particulier des polynômes multilinaires) à la place de polynômes univariés, en représentant l'ensemble de la trajectoire de calcul par leurs valeurs sur des "hypercubes" ; ensuite, étant donné que chaque dimension de l'hypercube a une longueur de 2, il n'est pas possible de procéder à une extension de Reed-Solomon standard comme avec les STARKs, mais on peut considérer l'hypercube comme un carré, et effectuer l'extension de Reed-Solomon basée sur ce carré. 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 : HyperPlonk PIOP + Brakedown PCS + domaine binaire. Plus précisément, Binius comprend cinq technologies clés pour réaliser son efficacité et sa sécurité :
2.1 Domaine fini : arithmétique basée sur les tours de corps binaires
Le domaine binaire en forme de tour est clé pour réaliser des calculs vérifiables rapides, principalement en raison de deux aspects : le calcul efficace et l'arithmétisation efficace. Le domaine binaire prend essentiellement en charge 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 du domaine binaire soutient un processus d'arithmétisation simplifié, c'est-à-dire que les opérations effectuées sur le domaine binaire peuvent être représentées sous une forme algébrique compacte et facile à vérifier.
2.2 PIOP : version adaptée du produit HyperPlonk et PermutationCheck
La conception de PIOP dans le protocole Binius s'inspire de HyperPlonk et utilise une série de mécanismes de vérification essentiels pour valider l'exactitude des polynômes et des ensembles multivariables. Ces vérifications essentielles comprennent :
Binius a apporté des améliorations dans les 3 domaines suivants :
2.3 PIOP : nouvel argument de décalage multiligne
Dans le protocole Binius, la construction et le traitement des polynômes virtuels sont l'une des technologies clés, comprenant principalement deux méthodes :
2.4 PIOP : argument de recherche Lasso adapté
Le protocole Lasso est composé des trois composants suivants :
Le protocole Binius adapte Lasso aux opérations dans le domaine binaire, introduisant une version multiplicative du protocole Lasso.
2.5 PCS : version adaptée Brakedown PCS
La pensée fondamentale derrière la construction de BiniusPCS est le packing. L'engagement polynomial de Binius utilise principalement :
3 Optimisation de la pensée
Pour améliorer davantage les performances du protocole Binius, cet article propose quatre points d'optimisation clés :
3.1 PIOP basé sur GKR : multiplication de domaine binaire basée sur GKR
L'algorithme de multiplication d'entiers basé sur GKR, en transformant "vérifier si 2 entiers de 32 bits A et B satisfont A·B =? C" en "vérifier si (gA)B =? gC est vrai", réduit considérablement les frais d'engagement grâce au protocole GKR.
3.2 ZeroCheck PIOP optimisation : compromis entre les coûts de calcul du Prover et du Verifier
Les principales orientations d'optimisation comprennent les suivantes :
3.3 Optimisation de PIOP Sumcheck : protocole Sumcheck basé sur des petits domaines
Les principaux points d'optimisation incluent :
3.4 PCS Optimisation : FRI-Binius réduit la taille de preuve de Binius
FRI-Binius a mis en œuvre le mécanisme de pliage FRI dans le domaine binaire, apportant 4 innovations :
4 Conclusion
La proposition de valeur de Binius est de permettre aux témoins d'utiliser le plus petit domaine de puissance de deux, de sorte qu'il suffit de choisir la taille du domaine en fonction des besoins. Binius est une solution de conception collaborative qui utilise "du matériel, des logiciels et le protocole Sumcheck accéléré par FPGA", permettant de prouver rapidement avec une très faible utilisation de mémoire.
Binius a presque complètement éliminé le goulot d'étranglement des engagements de Prover, le nouveau goulot d'étranglement réside dans le protocole Sumcheck. Les problèmes liés à de nombreuses évaluations de polynômes et aux multiplications dans le domaine au sein du protocole Sumcheck peuvent être résolus de manière efficace grâce à du matériel spécialisé. Le schéma FRI-Binius est une variante du FRI, offrant un choix très attrayant - éliminer les coûts d'incorporation du niveau de preuve dans le domaine sans entraîner une explosion des coûts au niveau de la preuve agrégée.
Actuellement, l'équipe d'Irreducible développe sa couche récursive et a annoncé une collaboration avec l'équipe de Polygon pour construire un zkVM basé sur Binius ; JoltzkVM passe de Lasso à Binius pour améliorer ses performances récursives ; l'équipe d'Ingonyama met en œuvre une version FPGA de Binius.