Analyse des principes STARKs de Binius et réflexions 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, comme les index dans les boucles for, les valeurs booléennes, les compteurs, etc. 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 l'occupation de nombreux valeurs redondantes supplémentaires dans tout le domaine, même si la valeur originale elle-même est très petite. Pour résoudre ce problème, la réduction de la taille du domaine est devenue une stratégie clé.
Comme indiqué dans le tableau 1, la largeur de code des STARKs de première génération est de 252 bits, celle des STARKs de deuxième génération est de 64 bits, et celle des STARKs de troisième génération est de 32 bits, mais la largeur de code de 32 bits présente encore beaucoup d'espace gaspillé. En comparaison, le domaine binaire permet d'opérer directement sur les bits, avec un codage compact et efficace sans espace gaspillé, c'est-à-dire les STARKs de quatrième génération.
Tableau 1 : Chemin de dérivation des STARKs
| Ordre | Largeur | Description |
|------|------|------|
| 1ère génération | 252 bits | Basé sur le domaine des grands nombres premiers |
| 2ème génération | 64 bits | Domaine de Goldilocks |
| 3ème génération | 32 bits | Domaine Babybear |
| 4ème génération | 1bit | domaine binaire |
Comparé aux découvertes récentes sur les corps finis comme Goldilocks, BabyBear et Mersenne31, la recherche sur les corps binaires remonte aux années 1980. Actuellement, les corps binaires sont largement utilisés en cryptographie, des exemples typiques incluent :
Standard de cryptage avancé (AES), basé sur le domaine F28;
Galois Message Authentication Code ( GMAC ), basé sur le domaine F2128;
Code QR, utilisant le codage Reed-Solomon basé sur F28;
Le protocole FRI d'origine et le protocole zk-STARK, ainsi que la fonction de hachage Grøstl, qui a atteint la finale du SHA-3, basée sur le domaine F28, est un algorithme de hachage très adapté à la récursivité.
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 compter entièrement sur 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 grande efficacité dans le 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 le domaine binaire, il existe deux problèmes pratiques : lors du calcul de la représentation de trace dans les STARKs, la taille du domaine utilisée doit être supérieure au degré du polynôme ; lors de l'engagement de l'arbre Merkle dans les STARKs, un encodage de Reed-Solomon doit être effectué, et la taille du domaine utilisée doit être supérieure à la taille après l'extension de l'encodage.
Binius a proposé une solution innovante pour traiter ces deux problèmes séparément et représenter les mêmes données de deux manières différentes : tout d'abord, en utilisant un polynôme multivarié (, spécifiquement un polynôme multilinéraire ), à la place d'un polynôme univarié, pour représenter l'ensemble de la trajectoire de calcul par ses valeurs sur des "hyper cubes" (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 standard de Reed-Solomon comme avec les STARKs, mais on peut considérer l'hypercube comme un carré (square) et effectuer l'extension de Reed-Solomon sur ce carré. Cette méthode augmente considérablement l'efficacité du codage et les performances 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 :
Information-Theoretic Polynomial Interactive Oracle Proof, PIOP( : PIOP, en tant que système de preuve central, transforme la relation de calcul d'entrée en égalité polynomiale vérifiable. Différents protocoles PIOP, à travers l'interaction avec le vérificateur, permettent au prouveur d'envoyer progressivement des polynômes, de sorte que le vérificateur puisse vérifier si le calcul est correct en interrogeant un petit nombre de résultats d'évaluation de polynômes. Les protocoles PIOP existants incluent : PLONK PIOP, Spartan PIOP et HyperPlonk PIOP, qui traitent chacun les expressions polynomiales de manière différente, influençant ainsi la performance et l'efficacité de l'ensemble du système SNARK.
Schéma d'engagement polynomial ) Polynomial Commitment Scheme, PCS ( : Le schéma d'engagement polynomial est utilisé pour prouver si l'égalité polynomiale générée par PIOP est valable. PCS est un outil cryptographique, grâce auquel le prouveur peut s'engager sur un certain polynôme et vérifier plus tard le résultat de l'évaluation de ce polynôme, tout en cachant d'autres informations sur le polynôme. Les schémas d'engagement polynomial courants incluent KZG, Bulletproofs, FRI ) Fast Reed-Solomon IOPP ( et Brakedown, etc. Différents PCS ont des performances, une sécurité et des cas d'utilisation différents.
Selon les besoins spécifiques, choisissez différents PIOP et PCS, et combinez-les avec un domaine fini ou une courbe elliptique appropriée, vous pouvez construire des systèmes de preuve ayant différentes propriétés. Par exemple :
• Halo2: combinant PLONK PIOP et Bulletproofs PCS, basé sur la courbe Pasta. Halo2 a été conçu en mettant l'accent sur l'évolutivité et l'élimination de la configuration de confiance dans le protocole ZCash.
• Plonky2 : utilise PLONK PIOP et FRI PCS combinés, et est basé sur le domaine de Goldilocks. Plonky2 est conçu pour réaliser une récursivité efficace. Lors de la conception de ces systèmes, le PIOP et le PCS choisis doivent correspondre au champ fini ou à la courbe elliptique utilisée, afin d'assurer la validité, la performance et la sécurité du système. Le choix de ces combinaisons influence non seulement la taille des preuves SNARK et l'efficacité de la vérification, mais détermine également si le système peut réaliser la transparence sans configuration de confiance préalable, et s'il peut prendre en charge des fonctionnalités d'extension telles que les preuves récursives ou les preuves agrégées.
Binius : HyperPlonk PIOP + Brakedown PCS + champs binaires. Plus précisément, Binius comprend cinq technologies clés pour réaliser son efficacité et sa sécurité. Tout d'abord, la construction arithmétique basée sur les tours de champs binaires )towers of binary fields( constitue la base de ses calculs, permettant d'effectuer des opérations simplifiées dans le champ binaire. Deuxièmement, Binius a adapté les vérifications de produit et de permutation de HyperPlonk dans son protocole de preuve Oracle interactif )PIOP(, garantissant une vérification de cohérence sécurisée et efficace entre les variables et leurs permutations. Troisièmement, le protocole introduit une nouvelle preuve de décalage multilinéaire, optimisant l'efficacité de la vérification des relations multilinéaires sur de petits champs. Quatrièmement, Binius utilise une version améliorée de la preuve de recherche Lasso, offrant flexibilité et sécurité robuste au mécanisme de recherche. Enfin, le protocole utilise un schéma d'engagement polynomial sur de petits champs )Small-Field PCS(, lui permettant de réaliser un système de preuve efficace dans le champ binaire et de réduire les frais généralement associés aux grands champs.
) 2.1 Domaine limité : arithmétique basée sur les tours de champs binaires
Les corps binaires en tour sont la clé de la réalisation de calculs rapidement vérifiables, principalement en raison de deux aspects : le calcul efficace et l'arithmétisation efficace. Les corps binaires soutiennent essentiellement 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 des corps binaires soutient un processus d'arithmétisation simplifié, c'est-à-dire que les opérations effectuées sur les corps binaires peuvent être représentées sous une forme algébrique compacte et facilement vérifiable. Ces caractéristiques, associées à la capacité de tirer pleinement parti de ses caractéristiques hiérarchiques grâce à la structure en tour, rendent les corps binaires particulièrement adaptés à des systèmes de preuve extensibles tels que Binius.
Le terme "canonique" fait référence à la représentation unique et directe des éléments dans le domaine binaire. Par exemple, dans le domaine binaire le plus basique F2, toute chaîne de k bits peut être directement mappée à un élément de domaine binaire de k bits. Cela diffère des domaines premiers, qui ne peuvent pas offrir une telle représentation canonique dans un nombre de bits donné. Bien qu'un domaine premier de 32 bits puisse être contenu dans 32 bits, il n'est pas vrai que chaque chaîne de 32 bits corresponde de manière unique à un élément de domaine, alors que le domaine binaire offre cette commodité d'un mappage un à un. Dans le domaine premier 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 domaines finis spécifiques comme Mersenne-31 ou Goldilocks-64. Dans le domaine binaire F2k, les méthodes de réduction couramment utilisées incluent des réductions spéciales ### comme celles utilisées dans AES (, la réduction de Montgomery ) comme utilisée dans POLYVAL (, et la réduction récursive ) comme Tower (. Le document "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" indique que le domaine binaire n'a pas besoin d'introduire des retenues dans les opérations d'addition et de multiplication, et que l'opération de carré dans le domaine binaire est très efficace, car elle suit la règle simplifiée )X + Y (2 = X2 + Y 2.
Comme indiqué dans la figure 1, une chaîne de 128 bits : cette chaîne peut être interprétée de plusieurs manières dans le contexte des domaines binaires. Elle peut être considérée comme un élément unique dans un domaine binaire de 128 bits, ou être décomposée en deux éléments de domaine de tour de 64 bits, quatre éléments de domaine de tour de 32 bits, 16 éléments de domaine de tour de 8 bits, ou 128 éléments de domaine F2. Cette flexibilité de représentation n'implique aucun coût de calcul, juste un typecast de chaîne de bits )typecast(, qui est une caractéristique très intéressante et utile. De plus, les petits éléments de domaine peuvent être empaquetés en éléments de domaine plus grands sans coût de calcul supplémentaire. Le protocole Binius tire parti de cette caractéristique pour améliorer l'efficacité des calculs. En outre, le document "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité de calcul des opérations de multiplication, de mise au carré et d'inversion dans un domaine binaire de tour de n bits ) décomposable en un sous-domaine de m bits (.
![Bitlayer Research : Analyse des principes STARKs de Binius et réflexions sur leur optimisation])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 2.2 PIOP: version modifiée du produit HyperPlonk et vérification de permutation ------ applicable aux domaines binaires
La conception de PIOP dans le protocole Binius s'inspire de HyperPlonk et utilise une série de mécanismes de vérification fondamentaux pour valider la correctitude des polynômes et des ensembles multivariés. Ces vérifications fondamentales comprennent :
GateCheck : Vérifiez si le témoin secret ω et l'entrée publique x satisfont la relation d'opération du circuit C###x, ω(=0, afin de garantir le bon fonctionnement du circuit.
PermutationCheck : vérifier si les résultats d'évaluation des deux polynômes multivariables f et g sur le cube de Booléen forment une relation de permutation f)x( = f)π(x(), afin d'assurer la cohérence des permutations entre les variables polynomiales.
LookupCheck : Vérifiez si l'évaluation du polynôme est dans la table de recherche donnée, c'est-à-dire f)Bµ( ⊆ T)Bµ(, assurez-vous que certaines valeurs sont dans la plage spécifiée.
MultisetCheck : vérifie si deux ensembles multivariables sont égaux, c'est-à-dire {)x1,i,x2,(}i∈H={)y1,i,y2,(}i∈H, garantissant la cohérence entre plusieurs ensembles.
ProductCheck: Vérifiez si l'évaluation d'un polynôme rationnel sur le cube hyperbolique booléen est égale à une valeur déclarée ∏x∈Hµ f)x( = s, afin d'assurer la correctitude du produit polynomial.
ZeroCheck : Vérifier si un polynôme multivariable en tout point du cube hyperbolique booléen est nul ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, afin d'assurer la distribution des zéros du polynôme.
SumCheck : Vérifie si la somme d'un polynôme multivariable est égale à la valeur déclarée ∑x∈Hµ f)x( = s. En transformant le problème d'évaluation d'un polynôme multivarié en un problème d'évaluation d'un polynôme univarié, cela réduit la complexité de calcul pour le vérificateur. De plus, SumCheck permet également le traitement par lots en introduisant des nombres aléatoires pour construire des combinaisons linéaires, ce qui permet de traiter plusieurs instances de vérification de somme.
BatchCheck : basé sur SumCheck, vérifie la justesse de l'évaluation de plusieurs polynômes multivariables afin d'améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk aient de nombreuses similitudes dans la conception des protocoles, Binius a apporté des améliorations dans les 3 domaines suivants :
Optimisation de ProductCheck : dans HyperPlonk, ProductCheck exige que le dénominateur U soit non nul partout sur l'hypercube, et que le produit soit égal à une valeur spécifique ; Binius simplifie ce processus de vérification en spécialisant cette valeur à 1, ce qui réduit la complexité de calcul.
Traitement du problème de division par zéro : HyperPlonk n’a pas réussi à traiter correctement les situations de division par zéro, ce qui rend impossible d’affirmer que U est non nul sur l’hypercube ; Binius a correctement traité ce problème, même lorsque le dénominateur est nul, le ProductCheck de Binius peut continuer à fonctionner, permettant ainsi une généralisation à n’importe quelle valeur de produit.
Vérification de permutation inter-colonnes : HyperPlonk n'a pas cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de gérer des cas de permutation polynomiale plus complexes.
Ainsi, Binius a amélioré le mécanisme PIOPSumCheck existant, augmentant la flexibilité et l'efficacité du protocole, en particulier lors du traitement de la vérification de polynômes multivariés plus complexes, offrant un support fonctionnel plus fort. Ces améliorations ont non seulement résolu les limitations dans HyperPlonk, mais ont également jeté les bases pour les systèmes de preuve basés sur des domaines binaires à l'avenir.
) 2.3 PIOP : nouvel argument de décalage multilinéraire ------ applicable à l'hypercube booléen
Dans le protocole Binius, multi-virtuel
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.
6 J'aime
Récompense
6
4
Reposter
Partager
Commentaire
0/400
AllTalkLongTrader
· Il y a 19h
Qui peut comprendre ça ? À part star, je n'ai rien compris.
Voir l'originalRépondre0
MerkleDreamer
· Il y a 19h
La largeur a diminué, enfin la gaspillage a été réduit.
Voir l'originalRépondre0
PanicSeller
· Il y a 20h
Cette optimisation traîne vraiment trop, je suis fatigué.
Binius STARKs nouvelle percée : optimisation du domaine binaire et système de preuve efficace
Analyse des principes STARKs de Binius et réflexions 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, comme les index dans les boucles for, les valeurs booléennes, les compteurs, etc. 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 l'occupation de nombreux valeurs redondantes supplémentaires dans tout le domaine, même si la valeur originale elle-même est très petite. Pour résoudre ce problème, la réduction de la taille du domaine est devenue une stratégie clé.
Comme indiqué dans le tableau 1, la largeur de code des STARKs de première génération est de 252 bits, celle des STARKs de deuxième génération est de 64 bits, et celle des STARKs de troisième génération est de 32 bits, mais la largeur de code de 32 bits présente encore beaucoup d'espace gaspillé. En comparaison, le domaine binaire permet d'opérer directement sur les bits, avec un codage compact et efficace sans espace gaspillé, c'est-à-dire les STARKs de quatrième génération.
Tableau 1 : Chemin de dérivation des STARKs
| Ordre | Largeur | Description | |------|------|------| | 1ère génération | 252 bits | Basé sur le domaine des grands nombres premiers | | 2ème génération | 64 bits | Domaine de Goldilocks | | 3ème génération | 32 bits | Domaine Babybear | | 4ème génération | 1bit | domaine binaire |
Comparé aux découvertes récentes sur les corps finis comme Goldilocks, BabyBear et Mersenne31, la recherche sur les corps binaires remonte aux années 1980. Actuellement, les corps binaires sont largement utilisés en cryptographie, des exemples typiques incluent :
Standard de cryptage avancé (AES), basé sur le domaine F28;
Galois Message Authentication Code ( GMAC ), basé sur le domaine F2128;
Code QR, utilisant le codage Reed-Solomon basé sur F28;
Le protocole FRI d'origine et le protocole zk-STARK, ainsi que la fonction de hachage Grøstl, qui a atteint la finale du SHA-3, basée sur le domaine F28, est un algorithme de hachage très adapté à la récursivité.
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 compter entièrement sur 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 grande efficacité dans le 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 le domaine binaire, il existe deux problèmes pratiques : lors du calcul de la représentation de trace dans les STARKs, la taille du domaine utilisée doit être supérieure au degré du polynôme ; lors de l'engagement de l'arbre Merkle dans les STARKs, un encodage de Reed-Solomon doit être effectué, et la taille du domaine utilisée doit être supérieure à la taille après l'extension de l'encodage.
Binius a proposé une solution innovante pour traiter ces deux problèmes séparément et représenter les mêmes données de deux manières différentes : tout d'abord, en utilisant un polynôme multivarié (, spécifiquement un polynôme multilinéraire ), à la place d'un polynôme univarié, pour représenter l'ensemble de la trajectoire de calcul par ses valeurs sur des "hyper cubes" (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 standard de Reed-Solomon comme avec les STARKs, mais on peut considérer l'hypercube comme un carré (square) et effectuer l'extension de Reed-Solomon sur ce carré. Cette méthode augmente considérablement l'efficacité du codage et les performances 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 :
Information-Theoretic Polynomial Interactive Oracle Proof, PIOP( : PIOP, en tant que système de preuve central, transforme la relation de calcul d'entrée en égalité polynomiale vérifiable. Différents protocoles PIOP, à travers l'interaction avec le vérificateur, permettent au prouveur d'envoyer progressivement des polynômes, de sorte que le vérificateur puisse vérifier si le calcul est correct en interrogeant un petit nombre de résultats d'évaluation de polynômes. Les protocoles PIOP existants incluent : PLONK PIOP, Spartan PIOP et HyperPlonk PIOP, qui traitent chacun les expressions polynomiales de manière différente, influençant ainsi la performance et l'efficacité de l'ensemble du système SNARK.
Schéma d'engagement polynomial ) Polynomial Commitment Scheme, PCS ( : Le schéma d'engagement polynomial est utilisé pour prouver si l'égalité polynomiale générée par PIOP est valable. PCS est un outil cryptographique, grâce auquel le prouveur peut s'engager sur un certain polynôme et vérifier plus tard le résultat de l'évaluation de ce polynôme, tout en cachant d'autres informations sur le polynôme. Les schémas d'engagement polynomial courants incluent KZG, Bulletproofs, FRI ) Fast Reed-Solomon IOPP ( et Brakedown, etc. Différents PCS ont des performances, une sécurité et des cas d'utilisation différents.
Selon les besoins spécifiques, choisissez différents PIOP et PCS, et combinez-les avec un domaine fini ou une courbe elliptique appropriée, vous pouvez construire des systèmes de preuve ayant différentes propriétés. Par exemple :
• Halo2: combinant PLONK PIOP et Bulletproofs PCS, basé sur la courbe Pasta. Halo2 a été conçu en mettant l'accent sur l'évolutivité et l'élimination de la configuration de confiance dans le protocole ZCash.
• Plonky2 : utilise PLONK PIOP et FRI PCS combinés, et est basé sur le domaine de Goldilocks. Plonky2 est conçu pour réaliser une récursivité efficace. Lors de la conception de ces systèmes, le PIOP et le PCS choisis doivent correspondre au champ fini ou à la courbe elliptique utilisée, afin d'assurer la validité, la performance et la sécurité du système. Le choix de ces combinaisons influence non seulement la taille des preuves SNARK et l'efficacité de la vérification, mais détermine également si le système peut réaliser la transparence sans configuration de confiance préalable, et s'il peut prendre en charge des fonctionnalités d'extension telles que les preuves récursives ou les preuves agrégées.
Binius : HyperPlonk PIOP + Brakedown PCS + champs binaires. Plus précisément, Binius comprend cinq technologies clés pour réaliser son efficacité et sa sécurité. Tout d'abord, la construction arithmétique basée sur les tours de champs binaires )towers of binary fields( constitue la base de ses calculs, permettant d'effectuer des opérations simplifiées dans le champ binaire. Deuxièmement, Binius a adapté les vérifications de produit et de permutation de HyperPlonk dans son protocole de preuve Oracle interactif )PIOP(, garantissant une vérification de cohérence sécurisée et efficace entre les variables et leurs permutations. Troisièmement, le protocole introduit une nouvelle preuve de décalage multilinéaire, optimisant l'efficacité de la vérification des relations multilinéaires sur de petits champs. Quatrièmement, Binius utilise une version améliorée de la preuve de recherche Lasso, offrant flexibilité et sécurité robuste au mécanisme de recherche. Enfin, le protocole utilise un schéma d'engagement polynomial sur de petits champs )Small-Field PCS(, lui permettant de réaliser un système de preuve efficace dans le champ binaire et de réduire les frais généralement associés aux grands champs.
) 2.1 Domaine limité : arithmétique basée sur les tours de champs binaires
Les corps binaires en tour sont la clé de la réalisation de calculs rapidement vérifiables, principalement en raison de deux aspects : le calcul efficace et l'arithmétisation efficace. Les corps binaires soutiennent essentiellement 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 des corps binaires soutient un processus d'arithmétisation simplifié, c'est-à-dire que les opérations effectuées sur les corps binaires peuvent être représentées sous une forme algébrique compacte et facilement vérifiable. Ces caractéristiques, associées à la capacité de tirer pleinement parti de ses caractéristiques hiérarchiques grâce à la structure en tour, rendent les corps binaires particulièrement adaptés à des systèmes de preuve extensibles tels que Binius.
Le terme "canonique" fait référence à la représentation unique et directe des éléments dans le domaine binaire. Par exemple, dans le domaine binaire le plus basique F2, toute chaîne de k bits peut être directement mappée à un élément de domaine binaire de k bits. Cela diffère des domaines premiers, qui ne peuvent pas offrir une telle représentation canonique dans un nombre de bits donné. Bien qu'un domaine premier de 32 bits puisse être contenu dans 32 bits, il n'est pas vrai que chaque chaîne de 32 bits corresponde de manière unique à un élément de domaine, alors que le domaine binaire offre cette commodité d'un mappage un à un. Dans le domaine premier 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 domaines finis spécifiques comme Mersenne-31 ou Goldilocks-64. Dans le domaine binaire F2k, les méthodes de réduction couramment utilisées incluent des réductions spéciales ### comme celles utilisées dans AES (, la réduction de Montgomery ) comme utilisée dans POLYVAL (, et la réduction récursive ) comme Tower (. Le document "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" indique que le domaine binaire n'a pas besoin d'introduire des retenues dans les opérations d'addition et de multiplication, et que l'opération de carré dans le domaine binaire est très efficace, car elle suit la règle simplifiée )X + Y (2 = X2 + Y 2.
Comme indiqué dans la figure 1, une chaîne de 128 bits : cette chaîne peut être interprétée de plusieurs manières dans le contexte des domaines binaires. Elle peut être considérée comme un élément unique dans un domaine binaire de 128 bits, ou être décomposée en deux éléments de domaine de tour de 64 bits, quatre éléments de domaine de tour de 32 bits, 16 éléments de domaine de tour de 8 bits, ou 128 éléments de domaine F2. Cette flexibilité de représentation n'implique aucun coût de calcul, juste un typecast de chaîne de bits )typecast(, qui est une caractéristique très intéressante et utile. De plus, les petits éléments de domaine peuvent être empaquetés en éléments de domaine plus grands sans coût de calcul supplémentaire. Le protocole Binius tire parti de cette caractéristique pour améliorer l'efficacité des calculs. En outre, le document "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité de calcul des opérations de multiplication, de mise au carré et d'inversion dans un domaine binaire de tour de n bits ) décomposable en un sous-domaine de m bits (.
![Bitlayer Research : Analyse des principes STARKs de Binius et réflexions sur leur optimisation])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 2.2 PIOP: version modifiée du produit HyperPlonk et vérification de permutation ------ applicable aux domaines binaires
La conception de PIOP dans le protocole Binius s'inspire de HyperPlonk et utilise une série de mécanismes de vérification fondamentaux pour valider la correctitude des polynômes et des ensembles multivariés. Ces vérifications fondamentales comprennent :
GateCheck : Vérifiez si le témoin secret ω et l'entrée publique x satisfont la relation d'opération du circuit C###x, ω(=0, afin de garantir le bon fonctionnement du circuit.
PermutationCheck : vérifier si les résultats d'évaluation des deux polynômes multivariables f et g sur le cube de Booléen forment une relation de permutation f)x( = f)π(x(), afin d'assurer la cohérence des permutations entre les variables polynomiales.
LookupCheck : Vérifiez si l'évaluation du polynôme est dans la table de recherche donnée, c'est-à-dire f)Bµ( ⊆ T)Bµ(, assurez-vous que certaines valeurs sont dans la plage spécifiée.
MultisetCheck : vérifie si deux ensembles multivariables sont égaux, c'est-à-dire {)x1,i,x2,(}i∈H={)y1,i,y2,(}i∈H, garantissant la cohérence entre plusieurs ensembles.
ProductCheck: Vérifiez si l'évaluation d'un polynôme rationnel sur le cube hyperbolique booléen est égale à une valeur déclarée ∏x∈Hµ f)x( = s, afin d'assurer la correctitude du produit polynomial.
ZeroCheck : Vérifier si un polynôme multivariable en tout point du cube hyperbolique booléen est nul ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, afin d'assurer la distribution des zéros du polynôme.
SumCheck : Vérifie si la somme d'un polynôme multivariable est égale à la valeur déclarée ∑x∈Hµ f)x( = s. En transformant le problème d'évaluation d'un polynôme multivarié en un problème d'évaluation d'un polynôme univarié, cela réduit la complexité de calcul pour le vérificateur. De plus, SumCheck permet également le traitement par lots en introduisant des nombres aléatoires pour construire des combinaisons linéaires, ce qui permet de traiter plusieurs instances de vérification de somme.
BatchCheck : basé sur SumCheck, vérifie la justesse de l'évaluation de plusieurs polynômes multivariables afin d'améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk aient de nombreuses similitudes dans la conception des protocoles, Binius a apporté des améliorations dans les 3 domaines suivants :
Optimisation de ProductCheck : dans HyperPlonk, ProductCheck exige que le dénominateur U soit non nul partout sur l'hypercube, et que le produit soit égal à une valeur spécifique ; Binius simplifie ce processus de vérification en spécialisant cette valeur à 1, ce qui réduit la complexité de calcul.
Traitement du problème de division par zéro : HyperPlonk n’a pas réussi à traiter correctement les situations de division par zéro, ce qui rend impossible d’affirmer que U est non nul sur l’hypercube ; Binius a correctement traité ce problème, même lorsque le dénominateur est nul, le ProductCheck de Binius peut continuer à fonctionner, permettant ainsi une généralisation à n’importe quelle valeur de produit.
Vérification de permutation inter-colonnes : HyperPlonk n'a pas cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de gérer des cas de permutation polynomiale plus complexes.
Ainsi, Binius a amélioré le mécanisme PIOPSumCheck existant, augmentant la flexibilité et l'efficacité du protocole, en particulier lors du traitement de la vérification de polynômes multivariés plus complexes, offrant un support fonctionnel plus fort. Ces améliorations ont non seulement résolu les limitations dans HyperPlonk, mais ont également jeté les bases pour les systèmes de preuve basés sur des domaines binaires à l'avenir.
) 2.3 PIOP : nouvel argument de décalage multilinéraire ------ applicable à l'hypercube booléen
Dans le protocole Binius, multi-virtuel