Analyse des principes des STARKs de Binius et réflexion sur leur optimisation
1 Introduction
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 des arbres de Merkle, l'utilisation du codage Reed-Solomon pour étendre les données entraîne de nombreuses valeurs redondantes qui occupent tout le domaine. Pour résoudre ce problème, réduire la taille du domaine est devenu une stratégie clé.
La largeur d'encodage 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 d'encodage de 32 bits entraîne encore un grand gaspillage d'espace. En revanche, le domaine binaire permet d'opérer directement sur les bits, l'encodage est compact et efficace sans espace gaspillé, c'est-à-dire les STARKs de quatrième génération.
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 s'appuyer sur l'extension de domaine pour assurer sa sécurité et sa praticité. Dans la plupart des calculs de Prover, les polynômes impliqués n'ont pas besoin d'entrer dans l'extension de domaine, mais doivent simplement opérer sous le domaine de base, ce qui permet d'atteindre une grande 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.
Lors de la construction d'un système de preuve basé sur un domaine binaire, deux problèmes pratiques se posent : dans les STARKs, la taille du domaine utilisée lors du calcul de la représentation de la trace doit être supérieure au degré du polynôme ; dans les STARKs, lors de l'engagement de l'arbre de Merkle, un codage de Reed-Solomon doit être effectué, et la taille du domaine doit être supérieure à la taille après extension du codage.
Binius a proposé une solution innovante qui traite ces deux problèmes séparément et représente les mêmes données de deux manières différentes : tout 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 ses valeurs sur des "hypercubes" ; ensuite, étant donné que la longueur de chaque dimension de l'hypercube est de 2, il n'est pas possible de faire une extension de Reed-Solomon standard comme avec les STARKs, mais l'hypercube peut être considéré comme un carré, sur la base duquel une extension de Reed-Solomon peut être réalisée. Cette méthode améliore considérablement l'efficacité du codage et la performance de calcul tout en garantissant la sécurité.
2 Analyse des principes
La construction de la plupart des systèmes SNARKs actuels comprend généralement les deux parties suivantes :
Preuve d'oracle interactive polynomiale basée sur la théorie de l'information (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP)
Binius : HyperPlonk PIOP + Brakedown PCS + domaine binaire. Plus précisément, Binius comprend cinq technologies clés pour assurer son efficacité et sa sécurité :
Arithmétisation basée sur le domaine binaire en tour
Vérification des produits et des permutations de la version adaptée HyperPlonk
Nouvelle preuve de décalage multilinéaire
Version améliorée de la recherche Lasso
Schéma d'engagement de polynômes sur de petits domaines
2.1 Domain fini : arithmétique basée sur les tours de champs binaires
Le domaine binaire en forme de tour est la clé pour réaliser des calculs rapidement vérifiables, principalement en raison de deux aspects : le calcul efficace et l'arithmétique 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 exigences de performance. De plus, la structure du domaine binaire prend en charge 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.
Dans le corps des nombres premiers Fp, les méthodes de réduction courantes incluent la réduction de Barrett, la réduction de Montgomery, ainsi que des méthodes de réduction spéciales pour des corps finis spécifiques comme Mersenne-31 ou Goldilocks-64. Dans le corps binaire F2k, les méthodes de réduction couramment utilisées incluent la réduction spéciale (comme celle utilisée dans AES), la réduction de Montgomery (comme celle utilisée dans POLYVAL) et la réduction récursive (comme Tower).
Le champ binaire n'exige pas l'introduction de retenues dans les opérations d'addition et de multiplication, et l'opération de carré dans le champ binaire est très efficace, car elle suit la règle simplifiée (X + Y )2 = X2 + Y 2.
2.2 PIOP : version adaptée de HyperPlonk Product 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 la correctitude des polynômes et des ensembles multivariés. Ces vérifications essentielles comprennent :
GateCheck
PermutationCheck
LookupCheck
MultisetCheck
ProductCheck
ZeroCheck
SumCheck
BatchCheck
Binius a apporté les améliorations suivantes par rapport à HyperPlonk :
Optimisation de ProductCheck
Gestion du problème de la division par zéro
Vérification de permutation inter-colonnes
2.3 PIOP : nouvel argument de décalage multilinéal
Dans le protocole Binius, la construction et le traitement des polynômes virtuels sont l'une des technologies clés, capables de générer et d'opérer efficacement sur des polynômes dérivés de poignées d'entrée ou d'autres polynômes virtuels. Voici deux méthodes clés :
Emballage
Opérateur de décalage
2.4 PIOP : argument de recherche Lasso adapté
Le protocole Lasso permet à la partie prouvante de s'engager sur un vecteur a ∈ Fm et de prouver que tous ses éléments se trouvent dans une table spécifiée à l'avance t ∈ Fn. Le protocole Lasso se compose 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 sur les domaines binaires, introduisant une version multiplicative du protocole Lasso.
2.5 PCS : version adaptée Brakedown PCS
La pensée centrale de la construction de BiniusPCS est le packing. Le document de Binius propose deux schémas de promesse de polynômes Brakedown basés sur le domaine binaire :
Utiliser le code concaténé pour l'instanciation
Utiliser la technologie de codage au niveau des blocs, supportant l'utilisation autonome des codes de Reed-Solomon.
Les engagements polynomiaux de Binius utilisent principalement les technologies suivantes :
Engagement de petits polynômes et évaluation dans un domaine étendu
Construction générique de petit domaine
Codage de blocs et code de Reed-Solomon
3 Optimisation de la pensée
Pour améliorer davantage la performance 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 : Équilibrage des coûts de calcul entre le Prover et le Verifier
Optimisation de Sumcheck PIOP : optimisation pour le Sumcheck de petit domaine
Optimisation PCS : optimisation par FRI-Binius
3.1 PIOP basé sur GKR : multiplication binaire dans le domaine basé sur GKR
L'algorithme de multiplication d'entiers basé sur GKR transforme "vérifier si deux entiers de 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 des engagements grâce au protocole GKR.
3.2 ZeroCheck PIOP optimisation : compromis entre les coûts de calcul du Prover et du Verifier
Le document "Some Improvements for the PIOP for ZeroCheck" propose diverses solutions d'optimisation pour ajuster la répartition de la charge de travail entre le prouveur (P) et le vérificateur (V), afin de trouver un compromis sur les coûts. Les principales optimisations comprennent :
Réduire le transfert de données de la partie prouvante
Réduire le nombre de points d'évaluation du prouveur
Optimisation par interpolation algébrique
3.3 Optimisation PIOP de Sumcheck : protocole Sumcheck basé sur un petit domaine
Ingonyama a proposé en 2024 une amélioration du protocole Sumcheck basé sur des petits domaines et a rendu le code source disponible. Les principales optimisations incluent :
L'impact et le facteur d'amélioration du changement de tour
L'impact de la taille du domaine sur les performances
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éduit la taille de preuve de Binius
L'article "Polylogarithmic Proofs for Multilinears over Binary Towers", abrégé en FRI-Binius, met en œuvre le mécanisme de pliage FRI sur le domaine binaire, apportant 4 innovations dans les domaines suivants :
Polynomials aplatis
Polynomiale de disparition de sous-espace
Emballage de la base algébrique
Échange de somme de vérification
Grâce à FRI-Binius, la taille de la preuve Binius peut être réduite d'un ordre de grandeur.
4 Conclusion
Binius est un schéma de conception coopératif qui utilise le "protocole de Sumcheck accéléré par matériel, logiciel et FPGA", permettant des preuves rapides avec une très faible utilisation de mémoire. Dans Binius, le goulot d'étranglement de l'engagement du Prover a été pratiquement entièrement éliminé, et le nouveau goulot d'étranglement réside dans le protocole de Sumcheck. Les nombreux problèmes d'évaluations polynomiales et de multiplications dans le domaine du protocole de Sumcheck peuvent être efficacement résolus à l'aide de matériel dédié.
Le plan FRI-Binius, en tant que variante FRI, offre un choix très attrayant - en éliminant les frais d'intégration du niveau de preuve de domaine, sans entraîner une explosion des coûts du niveau de preuve agrégée. Actuellement, l'équipe Irreducible développe son niveau récursif et a annoncé une collaboration 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 met en œuvre une version FPGA de Binius.
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.
26 J'aime
Récompense
26
8
Reposter
Partager
Commentaire
0/400
AirdropF5Bro
· Il y a 8h
Oh là là, cette vague de Starknet est impressionnante.
Voir l'originalRépondre0
¯\_(ツ)_/¯
· 08-12 16:41
Cette optimisation est vraiment incroyable, passant de 252 au binaire.
Voir l'originalRépondre0
SerumSquirter
· 08-10 20:16
L'efficacité augmente de plus en plus et le domaine devient de plus en plus petit.
Voir l'originalRépondre0
GateUser-afe07a92
· 08-10 09:35
C'est ennuyant, le prochain.
Voir l'originalRépondre0
ForkTongue
· 08-10 09:20
C'est vraiment bien écrit, mais je n'ai pas compris le professionnel...
Voir l'originalRépondre0
NullWhisperer
· 08-10 09:16
hmm... l'optimisation des champs binaires semble théoriquement élégante mais parlons de ces cas limites dans les opérations sur les champs d'extension...
Voir l'originalRépondre0
HalfBuddhaMoney
· 08-10 09:15
Depuis combien de temps n'ai-je pas traduit le domaine à largeur nulle ? Cette fois, je vais bien expliquer.
Voir l'originalRépondre0
NonFungibleDegen
· 08-10 09:08
ser cette chose frappante est basée af... binaires = le nombre augmente, enfin un vrai alpha pas ce cope de merkle tree
Analyse du principe des STARKs de Binius : optimisation des domaines binaires et engagement polynomial efficace
Analyse des principes des STARKs de Binius et réflexion sur leur optimisation
1 Introduction
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 des arbres de Merkle, l'utilisation du codage Reed-Solomon pour étendre les données entraîne de nombreuses valeurs redondantes qui occupent tout le domaine. Pour résoudre ce problème, réduire la taille du domaine est devenu une stratégie clé.
La largeur d'encodage 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 d'encodage de 32 bits entraîne encore un grand gaspillage d'espace. En revanche, le domaine binaire permet d'opérer directement sur les bits, l'encodage est compact et efficace sans espace gaspillé, c'est-à-dire les STARKs de quatrième génération.
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 s'appuyer sur l'extension de domaine pour assurer sa sécurité et sa praticité. Dans la plupart des calculs de Prover, les polynômes impliqués n'ont pas besoin d'entrer dans l'extension de domaine, mais doivent simplement opérer sous le domaine de base, ce qui permet d'atteindre une grande 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.
Lors de la construction d'un système de preuve basé sur un domaine binaire, deux problèmes pratiques se posent : dans les STARKs, la taille du domaine utilisée lors du calcul de la représentation de la trace doit être supérieure au degré du polynôme ; dans les STARKs, lors de l'engagement de l'arbre de Merkle, un codage de Reed-Solomon doit être effectué, et la taille du domaine doit être supérieure à la taille après extension du codage.
Binius a proposé une solution innovante qui traite ces deux problèmes séparément et représente les mêmes données de deux manières différentes : tout 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 ses valeurs sur des "hypercubes" ; ensuite, étant donné que la longueur de chaque dimension de l'hypercube est de 2, il n'est pas possible de faire une extension de Reed-Solomon standard comme avec les STARKs, mais l'hypercube peut être considéré comme un carré, sur la base duquel une extension de Reed-Solomon peut être réalisée. Cette méthode améliore considérablement l'efficacité du codage et la performance de calcul tout en garantissant la sécurité.
2 Analyse des principes
La construction de la plupart des systèmes SNARKs actuels comprend généralement les deux parties suivantes :
Binius : HyperPlonk PIOP + Brakedown PCS + domaine binaire. Plus précisément, Binius comprend cinq technologies clés pour assurer son efficacité et sa sécurité :
2.1 Domain fini : arithmétique basée sur les tours de champs binaires
Le domaine binaire en forme de tour est la clé pour réaliser des calculs rapidement vérifiables, principalement en raison de deux aspects : le calcul efficace et l'arithmétique 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 exigences de performance. De plus, la structure du domaine binaire prend en charge 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.
Dans le corps des nombres premiers Fp, les méthodes de réduction courantes incluent la réduction de Barrett, la réduction de Montgomery, ainsi que des méthodes de réduction spéciales pour des corps finis spécifiques comme Mersenne-31 ou Goldilocks-64. Dans le corps binaire F2k, les méthodes de réduction couramment utilisées incluent la réduction spéciale (comme celle utilisée dans AES), la réduction de Montgomery (comme celle utilisée dans POLYVAL) et la réduction récursive (comme Tower).
Le champ binaire n'exige pas l'introduction de retenues dans les opérations d'addition et de multiplication, et l'opération de carré dans le champ binaire est très efficace, car elle suit la règle simplifiée (X + Y )2 = X2 + Y 2.
2.2 PIOP : version adaptée de HyperPlonk Product 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 la correctitude des polynômes et des ensembles multivariés. Ces vérifications essentielles comprennent :
Binius a apporté les améliorations suivantes par rapport à HyperPlonk :
2.3 PIOP : nouvel argument de décalage multilinéal
Dans le protocole Binius, la construction et le traitement des polynômes virtuels sont l'une des technologies clés, capables de générer et d'opérer efficacement sur des polynômes dérivés de poignées d'entrée ou d'autres polynômes virtuels. Voici deux méthodes clés :
2.4 PIOP : argument de recherche Lasso adapté
Le protocole Lasso permet à la partie prouvante de s'engager sur un vecteur a ∈ Fm et de prouver que tous ses éléments se trouvent dans une table spécifiée à l'avance t ∈ Fn. Le protocole Lasso se compose des trois composants suivants :
Le protocole Binius adapte Lasso aux opérations sur les domaines binaires, introduisant une version multiplicative du protocole Lasso.
2.5 PCS : version adaptée Brakedown PCS
La pensée centrale de la construction de BiniusPCS est le packing. Le document de Binius propose deux schémas de promesse de polynômes Brakedown basés sur le domaine binaire :
Les engagements polynomiaux de Binius utilisent principalement les technologies suivantes :
3 Optimisation de la pensée
Pour améliorer davantage la performance du protocole Binius, cet article propose quatre points d'optimisation clés :
3.1 PIOP basé sur GKR : multiplication binaire dans le domaine basé sur GKR
L'algorithme de multiplication d'entiers basé sur GKR transforme "vérifier si deux entiers de 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 des engagements grâce au protocole GKR.
3.2 ZeroCheck PIOP optimisation : compromis entre les coûts de calcul du Prover et du Verifier
Le document "Some Improvements for the PIOP for ZeroCheck" propose diverses solutions d'optimisation pour ajuster la répartition de la charge de travail entre le prouveur (P) et le vérificateur (V), afin de trouver un compromis sur les coûts. Les principales optimisations comprennent :
3.3 Optimisation PIOP de Sumcheck : protocole Sumcheck basé sur un petit domaine
Ingonyama a proposé en 2024 une amélioration du protocole Sumcheck basé sur des petits domaines et a rendu le code source disponible. Les principales optimisations incluent :
3.4 PCS Optimisation : FRI-Binius réduit la taille de preuve de Binius
L'article "Polylogarithmic Proofs for Multilinears over Binary Towers", abrégé en FRI-Binius, met en œuvre le mécanisme de pliage FRI sur le domaine binaire, apportant 4 innovations dans les domaines suivants :
Grâce à FRI-Binius, la taille de la preuve Binius peut être réduite d'un ordre de grandeur.
4 Conclusion
Binius est un schéma de conception coopératif qui utilise le "protocole de Sumcheck accéléré par matériel, logiciel et FPGA", permettant des preuves rapides avec une très faible utilisation de mémoire. Dans Binius, le goulot d'étranglement de l'engagement du Prover a été pratiquement entièrement éliminé, et le nouveau goulot d'étranglement réside dans le protocole de Sumcheck. Les nombreux problèmes d'évaluations polynomiales et de multiplications dans le domaine du protocole de Sumcheck peuvent être efficacement résolus à l'aide de matériel dédié.
Le plan FRI-Binius, en tant que variante FRI, offre un choix très attrayant - en éliminant les frais d'intégration du niveau de preuve de domaine, sans entraîner une explosion des coûts du niveau de preuve agrégée. Actuellement, l'équipe Irreducible développe son niveau récursif et a annoncé une collaboration 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 met en œuvre une version FPGA de Binius.