Analyse des principes 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 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 dans tout le domaine. Réduire la taille du domaine devient une stratégie clé.
La largeur de codage des STARKs de 1ère génération est de 252 bits, celle de la 2ème génération est de 64 bits, et celle de la 3ème génération est de 32 bits, mais la largeur de codage de 32 bits présente encore beaucoup d'espace gaspillé. Le domaine binaire permet des opérations directes sur les bits, le codage est compact et efficace sans gaspillage d'espace, ce qui pourrait devenir la 4ème génération de STARKs.
Le domaine binaire a été largement utilisé en cryptographie, comme dans AES, GMAC, les codes QR, le FRI brut et les protocoles zk-STARK.
Lors de l'utilisation du domaine binaire, Binius doit entièrement dépendre de l'extension du domaine pour garantir la sécurité et l'utilisabilité réelle. La plupart des polynômes impliqués dans les calculs Prover n'ont pas besoin d'entrer dans l'extension du domaine, mais peuvent simplement être manipulés dans le domaine de base, ce qui permet d'atteindre une grande efficacité dans un petit domaine.
Binius propose des solutions innovantes :
utilise des polynômes multivariables à la place de polynômes univariables, en représentant l'ensemble de la trajectoire de calcul par leurs valeurs sur le "hypercube".
considérer le cube hypercube comme un carré pour l'extension de Reed-Solomon
2 Analyse des principes
Binius = HyperPlonk PIOP + Brakedown PCS + 二进制域
y compris cinq technologies clés :
basé sur le domaine binaire en tour de l'arithmétique
Adaptation de la vérification des produits et des permutations HyperPlonk
Nouvelle preuve de décalage multi-linéaire
version améliorée de la méthode de recherche Lasso
schéma d'engagement de polynômes de petits domaines
2.1 Domain fini : arithmétique basée sur les tours de corps binaires
Les domaines binaires en forme de tour supportent des opérations arithmétiques très efficaces et un processus d'arithmétisation simplifié.
Une chaîne de 128 bits peut être considérée comme un élément d'un domaine binaire de 128 bits, ou être interprétée comme deux éléments de domaine de 64 bits, quatre éléments de domaine de 32 bits, seize éléments de domaine de 8 bits, ou 128 éléments de domaine F2. Cette flexibilité de représentation ne nécessite aucun surcoût de calcul supplémentaire.
2.2 PIOP : version adaptée du produit HyperPlonk et vérification de permutation
La conception de PIOP dans le protocole Binius s'inspire de HyperPlonk et utilise une série de mécanismes de vérification clés :
GateCheck
PermutationCheck
LookupCheck
MultisetCheck
ProductCheck
ZeroCheck
SumCheck
BatchCheck
Binius a amélioré dans les 3 domaines suivants :
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éaire
Méthodes clés pour la construction et le traitement de polynômes virtuels dans le protocole Binius :
Emballage
Opérateur de décalage
2.4 PIOP : argument de recherche Lasso adapté
Le protocole Lasso est composé de trois composants :
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
Le document Binius présente deux schémas d'engagement de polynômes Brakedown basés sur des domaines binaires :
utilise un code concaténé pour l'instanciation
utilise la technologie de codage au niveau des blocs, prenant en charge l'utilisation indépendante des codes Reed-Solomon.
Les engagements polynomiaux sur de petits domaines et l'évaluation sur des domaines étendus, les constructions générales sur de petits domaines, ainsi que les techniques de codage au niveau des blocs et les codes de Reed-Solomon sont utilisés pour construire l'engagement polynomial Binius.
3 Optimisation de la pensée
Quatre points clés d'optimisation :
PIOP basé sur GKR : remplace l'algorithme Lasso Lookup pour les opérations de multiplication dans le domaine binaire grâce au protocole GKR.
Optimisation ZeroCheck PIOP : évaluation des coûts de calcul entre Prover et Verifier
Optimisation de Sumcheck PIOP : optimisation pour Sumcheck de petit domaine
Optimisation PCS : réduction de la taille de la 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 entière basé sur GKR, en transformant "vérifier si deux entiers de 32 bits A et B satisfont A·B =? C" en "vérifier si (gA)B =? gC est valide", réduit 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
Principales orientations d'optimisation :
Réduire le transfert de données par la partie preuve
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
Principaux points d'optimisation :
Impact et facteur d'amélioration du changement de cycle
L'impact de la taille de la base de 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é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 :
Polynôme aplati
Polynôme de disparition de sous-espace
Emballage de la base algébrique
Échange d'anneau SumCheck
4 Résumé
La proposition de valeur de Binius est d'utiliser le minimum de domaine de puissance de deux pour les témoins. L'engagement de Prover a été pratiquement complètement éliminé dans Binius, le nouveau goulot d'étranglement réside dans le protocole Sumcheck.
Le plan FRI-Binius est une variante de FRI qui permet d'éliminer les coûts d'embedding de la couche de preuve de domaine sans entraîner une augmentation excessive des coûts de la couche de preuve agrégée.
Actuellement, l'équipe Irreducible développe sa couche récursive et collabore avec l'équipe de Polygon pour construire un zkVM basé sur Binius ; JoltzkVM passe de Lasso à Binius ; 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.
13 J'aime
Récompense
13
5
Reposter
Partager
Commentaire
0/400
MetaverseVagrant
· 08-06 01:41
L'augmentation de l'efficacité est incroyable ! Une nouvelle ère arrive.
Voir l'originalRépondre0
ReverseFOMOguy
· 08-05 15:22
Pourquoi est-ce si difficile d'obtenir de l'efficacité ?
Voir l'originalRépondre0
LightningAllInHero
· 08-03 15:42
La 4ème génération est déjà là, je ne peux pas suivre le rythme.
Voir l'originalRépondre0
LayerZeroEnjoyer
· 08-03 15:30
Nomade numérique / Particulièrement intéressé par L2 et zk / Se concentre sur le suivi des développements des technologies d'extensibilité
Style de langage : Suivre les technologies de pointe, discuter de sujets sérieux de manière facile et humoristique, aimer s'exprimer de manière colloquiale, utiliser fréquemment des termes de la culture Internet comme "yyds".
Binius STARKs : analyse d'un protocole de preuve zéro connaissance efficace basé sur des domaines binaires
Analyse des principes 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 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 dans tout le domaine. Réduire la taille du domaine devient une stratégie clé.
La largeur de codage des STARKs de 1ère génération est de 252 bits, celle de la 2ème génération est de 64 bits, et celle de la 3ème génération est de 32 bits, mais la largeur de codage de 32 bits présente encore beaucoup d'espace gaspillé. Le domaine binaire permet des opérations directes sur les bits, le codage est compact et efficace sans gaspillage d'espace, ce qui pourrait devenir la 4ème génération de STARKs.
Le domaine binaire a été largement utilisé en cryptographie, comme dans AES, GMAC, les codes QR, le FRI brut et les protocoles zk-STARK.
Lors de l'utilisation du domaine binaire, Binius doit entièrement dépendre de l'extension du domaine pour garantir la sécurité et l'utilisabilité réelle. La plupart des polynômes impliqués dans les calculs Prover n'ont pas besoin d'entrer dans l'extension du domaine, mais peuvent simplement être manipulés dans le domaine de base, ce qui permet d'atteindre une grande efficacité dans un petit domaine.
Binius propose des solutions innovantes :
2 Analyse des principes
Binius = HyperPlonk PIOP + Brakedown PCS + 二进制域
y compris cinq technologies clés :
2.1 Domain fini : arithmétique basée sur les tours de corps binaires
Les domaines binaires en forme de tour supportent des opérations arithmétiques très efficaces et un processus d'arithmétisation simplifié.
Une chaîne de 128 bits peut être considérée comme un élément d'un domaine binaire de 128 bits, ou être interprétée comme deux éléments de domaine de 64 bits, quatre éléments de domaine de 32 bits, seize éléments de domaine de 8 bits, ou 128 éléments de domaine F2. Cette flexibilité de représentation ne nécessite aucun surcoût de calcul supplémentaire.
2.2 PIOP : version adaptée du produit HyperPlonk et vérification de permutation
La conception de PIOP dans le protocole Binius s'inspire de HyperPlonk et utilise une série de mécanismes de vérification clés :
Binius a amélioré dans les 3 domaines suivants :
2.3 PIOP : nouvel argument de décalage multilinéaire
Méthodes clés pour la construction et le traitement de polynômes virtuels dans le protocole Binius :
2.4 PIOP : argument de recherche Lasso adapté
Le protocole Lasso est composé de trois composants :
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
Le document Binius présente deux schémas d'engagement de polynômes Brakedown basés sur des domaines binaires :
Les engagements polynomiaux sur de petits domaines et l'évaluation sur des domaines étendus, les constructions générales sur de petits domaines, ainsi que les techniques de codage au niveau des blocs et les codes de Reed-Solomon sont utilisés pour construire l'engagement polynomial Binius.
3 Optimisation de la pensée
Quatre points clés d'optimisation :
PIOP basé sur GKR : remplace l'algorithme Lasso Lookup pour les opérations de multiplication dans le domaine binaire grâce au protocole GKR.
Optimisation ZeroCheck PIOP : évaluation des coûts de calcul entre Prover et Verifier
Optimisation de Sumcheck PIOP : optimisation pour Sumcheck de petit domaine
Optimisation PCS : réduction de la taille de la 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 entière basé sur GKR, en transformant "vérifier si deux entiers de 32 bits A et B satisfont A·B =? C" en "vérifier si (gA)B =? gC est valide", réduit 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
Principales orientations d'optimisation :
3.3 Optimisation PIOP de Sumcheck : protocole Sumcheck basé sur un petit domaine
Principaux points d'optimisation :
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 Résumé
La proposition de valeur de Binius est d'utiliser le minimum de domaine de puissance de deux pour les témoins. L'engagement de Prover a été pratiquement complètement éliminé dans Binius, le nouveau goulot d'étranglement réside dans le protocole Sumcheck.
Le plan FRI-Binius est une variante de FRI qui permet d'éliminer les coûts d'embedding de la couche de preuve de domaine sans entraîner une augmentation excessive des coûts de la couche de preuve agrégée.
Actuellement, l'équipe Irreducible développe sa couche récursive et collabore avec l'équipe de Polygon pour construire un zkVM basé sur Binius ; JoltzkVM passe de Lasso à Binius ; l'équipe Ingonyama met en œuvre une version FPGA de Binius.
Style de langage : Suivre les technologies de pointe, discuter de sujets sérieux de manière facile et humoristique, aimer s'exprimer de manière colloquiale, utiliser fréquemment des termes de la culture Internet comme "yyds".
Votre commentaire est :
starks doit aussi réduire cette fois.