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, comme les indices 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 dans tout le domaine, même si la valeur originale elle-même est très petite. Pour résoudre ce problème, réduire la taille du domaine est devenu 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 un grand espace gaspillé. En comparaison, le domaine binaire permet d'opérer directement sur les bits, rendant le codage compact et efficace sans aucun espace gaspillé, c'est-à-dire les STARKs de quatrième génération.
Comparé aux nouvelles découvertes de domaines finis comme Goldilocks, BabyBear, Mersenne31 au cours des dernières années, la recherche sur les domaines binaires remonte aux années 1980. Actuellement, les domaines 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 un codage Reed-Solomon basé sur F28;
Protocole FRI d'origine et zk-STARK, ainsi que la fonction de hachage Grøstl, qui a atteint la finale de SHA-3, cette fonction est basée sur le domaine F28, et 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 totalement dépendre de l'extension de domaine pour assurer sa sécurité et sa réelle utilisabilité. La plupart des polynômes impliqués dans les calculs de Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais peuvent simplement opérer sous le domaine de base, permettant ainsi d'atteindre une grande efficacité dans de petits domaines. Cependant, les vérifications de points aléatoires et les calculs FRI doivent encore s'approfondir 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 des domaines binaires, il existe deux problèmes pratiques : lors du calcul de la représentation de la 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 codage de Reed-Solomon doit être effectué, et la taille du domaine utilisée doit être supérieure à la taille après l'extension du codage.
Binius a proposé une solution innovante pour traiter ces deux problèmes, en représentant les mêmes données de deux manières différentes : d'abord, en utilisant un polynôme multivarié ( qui est un polynôme multilinéraire ) pour remplacer le polynôme univarié, représentant l'ensemble de la trajectoire de calcul par ses valeurs sur les "hypercubes" ( ; ensuite, comme chaque dimension de l'hypercube a une longueur de 2, il n'est pas possible de faire une extension standard de Reed-Solomon comme avec les STARKs, mais on peut considérer l'hypercube comme un ) carré (, et effectuer l'extension de Reed-Solomon sur cette base. 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 d'information théorique )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és polynomiales vérifiables. Différents protocoles PIOP permettent au prouveur d'envoyer progressivement des polynômes par l'interaction avec le vérificateur, de sorte que le vérificateur puisse vérifier si le calcul est correct en interrogeant un nombre limité 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, ce qui influence 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. Le PCS est un outil cryptographique, grâce auquel le prouveur peut s'engager sur un certain polynôme et vérifier plus tard les résultats 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, entre autres. 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, pour construire des systèmes de preuve avec différentes propriétés. Par exemple:
• Halo2 : combinaison de PLONK PIOP et de Bulletproofs PCS, basé sur la courbe Pasta. Halo2 est conçu avec un accent sur l'évolutivité et l'élimination du trusted setup dans le protocole ZCash.
• Plonky2 : adopte PLONK PIOP et FRI PCS combinés, et est basé sur le domaine de Goldilocks. Plonky2 est conçu pour réaliser des récursions efficaces. Lors de la conception de ces systèmes, les PIOP et 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 affecte non seulement la taille de la preuve SNARK et l'efficacité de la vérification, mais détermine également si le système peut atteindre 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 + domaines binaires. Plus précisément, Binius comprend cinq technologies clés pour réaliser son efficacité et sa sécurité. Tout d'abord, l'arithmétisation basée sur les tours de domaines binaires )towers of binary fields( constitue la base de ses calculs, permettant d'effectuer des opérations simplifiées dans le domaine binaire. Deuxièmement, Binius a adapté les vérifications de produits et de permutations d'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éraire, optimisant l'efficacité de la vérification des relations multilinéaires sur de petits domaines. Quatrièmement, Binius utilise une version améliorée de la preuve de recherche Lasso, offrant flexibilité et robustesse en matière de sécurité pour le mécanisme de recherche. Enfin, le protocole utilise un schéma d'engagement polynomial sur de petits domaines )Small-Field PCS(, permettant un système de preuve efficace dans le domaine binaire, tout en réduisant les frais généralement associés aux grands domaines.
) 2.1 Domaine fini : arithmétisation basée sur les tours de champs binaires
Le domaine binaire en tour est la clé pour réaliser un calcul vérifiable rapide, principalement en raison de deux aspects : le calcul efficace et l'arithmétique efficace. Le domaine binaire supporte 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 du domaine binaire supporte 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. Ces caractéristiques, associées à la capacité d'exploiter pleinement ses caractéristiques hiérarchiques grâce à la structure en tour, font du domaine binaire un choix particulièrement adapté pour des systèmes de preuve extensibles tels que Binius.
Parmi eux, "canonical" fait référence à la représentation unique et directe des éléments dans le domaine binaire. Par exemple, dans le domaine binaire F2 le plus fondamental, une chaîne de k bits peut être directement mappée à un élément du domaine binaire de k bits. Cela diffère des domaines premiers, qui ne peuvent pas fournir cette représentation canonique dans un nombre de bits donné. Bien qu'un domaine premier de 32 bits puisse être contenu dans 32 bits, chaque chaîne de 32 bits ne peut pas toujours correspondre de manière unique à un élément du domaine, tandis que le domaine binaire offre cette commodité de correspondance 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 courantes incluent une réduction spéciale ### utilisée dans AES (, la réduction de Montgomery ) utilisée dans POLYVAL ( et la réduction récursive ) utilisée dans Tower (. Le document "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" souligne que le domaine binaire n'introduit pas de transport dans les opérations d'addition et de multiplication, et que l'opération de carré du 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 d'un domaine binaire. 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 du domaine F2. Cette flexibilité de représentation ne nécessite aucun coût de calcul, juste un typecast de chaîne de bits )typecast(, ce qui est une propriété très intéressante et utile. De plus, les petits éléments de domaine peuvent être regroupé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é computationnelle. De plus, le document "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité des calculs pour la multiplication, l'élévation au carré et l'inversion dans le domaine de tour binaire de n bits ) décomposable en sous-domaines de m bits (.
![Bitlayer Research : Analyse des principes des STARKs de Binius et réflexions sur leur optimisation])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 2.2 PIOP: version adaptée du produit HyperPlonk et Vérification de Permutation------s'applique au domaine binaire
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 multivariés. Ces vérifications essentielles comprennent :
GateCheck : Vérifiez si le témoin secret ω et l'entrée publique x satisfont la relation de calcul 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 hyperbolique booléen sont une relation de permutation f)x( = f)π(x(), afin d'assurer la cohérence des permutations entre les variables polynomiales.
LookupCheck : Vérifier si l'évaluation du polynôme est dans la table de recherche donnée, c'est-à-dire f)Bµ( ⊆ T)Bµ(, s'assurer que certaines valeurs se trouvent dans la plage spécifiée.
MultisetCheck : Vérifiez si deux ensembles de variables multiples 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 du polynôme rationnel sur le cube hyperbolique de Boole est égale à une valeur déclarée ∏x∈Hµ f)x( = s, pour garantir la précision du produit polynomial.
ZeroCheck : vérifier si un polynôme multivariable est nul en un point quelconque du cube hyperbolique booléen ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, afin de garantir la distribution des zéros du polynôme.
SumCheck : Vérifie si la somme des valeurs 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 évaluation d'un polynôme à une variable, 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 afin de traiter plusieurs instances de vérification de sommes.
BatchCheck : Basé sur SumCheck, vérifie la validité des évaluations de plusieurs polynômes multivariables pour améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk présentent de nombreuses similitudes dans la conception de leur protocole, 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 doit être égal à une valeur spécifique ; Binius simplifie ce processus de vérification en spécialisant cette valeur à 1, réduisant ainsi la complexité des calculs.
Traitement du problème de division par zéro : HyperPlonk n'a pas réussi à traiter correctement les cas 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 zéro, le ProductCheck de Binius peut continuer à traiter, permettant une généralisation à n'importe quelle valeur de produit.
Vérification de permutation entre colonnes : HyperPlonk ne dispose pas de cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de gérer des cas d'arrangements polynomiaux plus complexes.
Ainsi, Binius a amélioré la flexibilité et l'efficacité du protocole grâce à des modifications du mécanisme PIOPSumCheck existant, offrant un support fonctionnel plus robuste, notamment lors du traitement de la validation de polynômes multivariables plus complexes. Ces améliorations non seulement résolvent les limitations d'HyperPlonk, mais jettent également les bases pour des systèmes de preuve basés sur des domaines binaires à l'avenir.
) 2.3 PIOP : nouvel argument de décalage multilinéraire ------ applicable au cube hyperbolique booléen
Dans le protocole Binius, 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.
23 J'aime
Récompense
23
5
Partager
Commentaire
0/400
zkProofInThePudding
· 07-18 00:38
Optimiser STARKs est vraiment attentionné, chaque génération devient plus économique.
Voir l'originalRépondre0
MissedTheBoat
· 07-17 06:26
Encore un article incompréhensible sur les zk-SNARKs
Voir l'originalRépondre0
LucidSleepwalker
· 07-17 06:23
Optimiser, optimiser, c'est toujours optimiser. 32 bits, c'est du gâchis. Ces devs ne sont pas à la hauteur.
Voir l'originalRépondre0
GateUser-00be86fc
· 07-17 06:23
Je ne comprends pas, mais je suis très choqué!
Voir l'originalRépondre0
BearMarketLightning
· 07-17 06:14
Cette efficacité rivalise avec celle d'une vieille voiture de 32 ans sur l'autoroute !
Binius STARKs : Système de preuve à connaissance nulle efficace basé sur un domaine binaire
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, comme les indices 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 dans tout le domaine, même si la valeur originale elle-même est très petite. Pour résoudre ce problème, réduire la taille du domaine est devenu 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 un grand espace gaspillé. En comparaison, le domaine binaire permet d'opérer directement sur les bits, rendant le codage compact et efficace sans aucun espace gaspillé, c'est-à-dire les STARKs de quatrième génération.
Tableau 1 : Voies d’évolution des STARK
| Algèbre | Largeur de codage | Système représentatif | |------|----------|----------| | 1ère génération | 252bit | StarkWare | | 2ème génération | 64bits | Plonky2 | | 3ème génération | 32 bits | BabyBear | | 4ème génération | Domaine binaire | Binius |
Comparé aux nouvelles découvertes de domaines finis comme Goldilocks, BabyBear, Mersenne31 au cours des dernières années, la recherche sur les domaines binaires remonte aux années 1980. Actuellement, les domaines 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 un codage Reed-Solomon basé sur F28;
Protocole FRI d'origine et zk-STARK, ainsi que la fonction de hachage Grøstl, qui a atteint la finale de SHA-3, cette fonction est basée sur le domaine F28, et 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 totalement dépendre de l'extension de domaine pour assurer sa sécurité et sa réelle utilisabilité. La plupart des polynômes impliqués dans les calculs de Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais peuvent simplement opérer sous le domaine de base, permettant ainsi d'atteindre une grande efficacité dans de petits domaines. Cependant, les vérifications de points aléatoires et les calculs FRI doivent encore s'approfondir 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 des domaines binaires, il existe deux problèmes pratiques : lors du calcul de la représentation de la 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 codage de Reed-Solomon doit être effectué, et la taille du domaine utilisée doit être supérieure à la taille après l'extension du codage.
Binius a proposé une solution innovante pour traiter ces deux problèmes, en représentant les mêmes données de deux manières différentes : d'abord, en utilisant un polynôme multivarié ( qui est un polynôme multilinéraire ) pour remplacer le polynôme univarié, représentant l'ensemble de la trajectoire de calcul par ses valeurs sur les "hypercubes" ( ; ensuite, comme chaque dimension de l'hypercube a une longueur de 2, il n'est pas possible de faire une extension standard de Reed-Solomon comme avec les STARKs, mais on peut considérer l'hypercube comme un ) carré (, et effectuer l'extension de Reed-Solomon sur cette base. 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 d'information théorique )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és polynomiales vérifiables. Différents protocoles PIOP permettent au prouveur d'envoyer progressivement des polynômes par l'interaction avec le vérificateur, de sorte que le vérificateur puisse vérifier si le calcul est correct en interrogeant un nombre limité 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, ce qui influence 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. Le PCS est un outil cryptographique, grâce auquel le prouveur peut s'engager sur un certain polynôme et vérifier plus tard les résultats 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, entre autres. 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, pour construire des systèmes de preuve avec différentes propriétés. Par exemple:
• Halo2 : combinaison de PLONK PIOP et de Bulletproofs PCS, basé sur la courbe Pasta. Halo2 est conçu avec un accent sur l'évolutivité et l'élimination du trusted setup dans le protocole ZCash.
• Plonky2 : adopte PLONK PIOP et FRI PCS combinés, et est basé sur le domaine de Goldilocks. Plonky2 est conçu pour réaliser des récursions efficaces. Lors de la conception de ces systèmes, les PIOP et 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 affecte non seulement la taille de la preuve SNARK et l'efficacité de la vérification, mais détermine également si le système peut atteindre 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 + domaines binaires. Plus précisément, Binius comprend cinq technologies clés pour réaliser son efficacité et sa sécurité. Tout d'abord, l'arithmétisation basée sur les tours de domaines binaires )towers of binary fields( constitue la base de ses calculs, permettant d'effectuer des opérations simplifiées dans le domaine binaire. Deuxièmement, Binius a adapté les vérifications de produits et de permutations d'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éraire, optimisant l'efficacité de la vérification des relations multilinéaires sur de petits domaines. Quatrièmement, Binius utilise une version améliorée de la preuve de recherche Lasso, offrant flexibilité et robustesse en matière de sécurité pour le mécanisme de recherche. Enfin, le protocole utilise un schéma d'engagement polynomial sur de petits domaines )Small-Field PCS(, permettant un système de preuve efficace dans le domaine binaire, tout en réduisant les frais généralement associés aux grands domaines.
) 2.1 Domaine fini : arithmétisation basée sur les tours de champs binaires
Le domaine binaire en tour est la clé pour réaliser un calcul vérifiable rapide, principalement en raison de deux aspects : le calcul efficace et l'arithmétique efficace. Le domaine binaire supporte 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 du domaine binaire supporte 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. Ces caractéristiques, associées à la capacité d'exploiter pleinement ses caractéristiques hiérarchiques grâce à la structure en tour, font du domaine binaire un choix particulièrement adapté pour des systèmes de preuve extensibles tels que Binius.
Parmi eux, "canonical" fait référence à la représentation unique et directe des éléments dans le domaine binaire. Par exemple, dans le domaine binaire F2 le plus fondamental, une chaîne de k bits peut être directement mappée à un élément du domaine binaire de k bits. Cela diffère des domaines premiers, qui ne peuvent pas fournir cette représentation canonique dans un nombre de bits donné. Bien qu'un domaine premier de 32 bits puisse être contenu dans 32 bits, chaque chaîne de 32 bits ne peut pas toujours correspondre de manière unique à un élément du domaine, tandis que le domaine binaire offre cette commodité de correspondance 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 courantes incluent une réduction spéciale ### utilisée dans AES (, la réduction de Montgomery ) utilisée dans POLYVAL ( et la réduction récursive ) utilisée dans Tower (. Le document "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" souligne que le domaine binaire n'introduit pas de transport dans les opérations d'addition et de multiplication, et que l'opération de carré du 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 d'un domaine binaire. 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 du domaine F2. Cette flexibilité de représentation ne nécessite aucun coût de calcul, juste un typecast de chaîne de bits )typecast(, ce qui est une propriété très intéressante et utile. De plus, les petits éléments de domaine peuvent être regroupé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é computationnelle. De plus, le document "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité des calculs pour la multiplication, l'élévation au carré et l'inversion dans le domaine de tour binaire de n bits ) décomposable en sous-domaines de m bits (.
![Bitlayer Research : Analyse des principes des STARKs de Binius et réflexions sur leur optimisation])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 2.2 PIOP: version adaptée du produit HyperPlonk et Vérification de Permutation------s'applique au domaine binaire
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 multivariés. Ces vérifications essentielles comprennent :
GateCheck : Vérifiez si le témoin secret ω et l'entrée publique x satisfont la relation de calcul 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 hyperbolique booléen sont une relation de permutation f)x( = f)π(x(), afin d'assurer la cohérence des permutations entre les variables polynomiales.
LookupCheck : Vérifier si l'évaluation du polynôme est dans la table de recherche donnée, c'est-à-dire f)Bµ( ⊆ T)Bµ(, s'assurer que certaines valeurs se trouvent dans la plage spécifiée.
MultisetCheck : Vérifiez si deux ensembles de variables multiples 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 du polynôme rationnel sur le cube hyperbolique de Boole est égale à une valeur déclarée ∏x∈Hµ f)x( = s, pour garantir la précision du produit polynomial.
ZeroCheck : vérifier si un polynôme multivariable est nul en un point quelconque du cube hyperbolique booléen ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, afin de garantir la distribution des zéros du polynôme.
SumCheck : Vérifie si la somme des valeurs 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 évaluation d'un polynôme à une variable, 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 afin de traiter plusieurs instances de vérification de sommes.
BatchCheck : Basé sur SumCheck, vérifie la validité des évaluations de plusieurs polynômes multivariables pour améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk présentent de nombreuses similitudes dans la conception de leur protocole, 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 doit être égal à une valeur spécifique ; Binius simplifie ce processus de vérification en spécialisant cette valeur à 1, réduisant ainsi la complexité des calculs.
Traitement du problème de division par zéro : HyperPlonk n'a pas réussi à traiter correctement les cas 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 zéro, le ProductCheck de Binius peut continuer à traiter, permettant une généralisation à n'importe quelle valeur de produit.
Vérification de permutation entre colonnes : HyperPlonk ne dispose pas de cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de gérer des cas d'arrangements polynomiaux plus complexes.
Ainsi, Binius a amélioré la flexibilité et l'efficacité du protocole grâce à des modifications du mécanisme PIOPSumCheck existant, offrant un support fonctionnel plus robuste, notamment lors du traitement de la validation de polynômes multivariables plus complexes. Ces améliorations non seulement résolvent les limitations d'HyperPlonk, mais jettent également les bases pour des systèmes de preuve basés sur des domaines binaires à l'avenir.
) 2.3 PIOP : nouvel argument de décalage multilinéraire ------ applicable au cube hyperbolique booléen
Dans le protocole Binius, virtuel