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 index dans les boucles for, les valeurs booléennes, les compteurs, etc. Cependant, pour garantir la sécurité des preuves basées sur des arbres de Merkle, l'utilisation du codage de Reed-Solomon pour étendre les données entraîne de nombreuses valeurs redondantes supplémentaires qui occupent 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 beaucoup d'espace gaspillé. En comparaison, le domaine binaire permet d'opérer directement sur les bits, avec un codage compact et efficace sans aucun espace gaspillé, c'est-à-dire les STARKs de quatrième génération.
Comparé à des découvertes récentes dans des 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 :
Norme de cryptage avancé ( AES ), basé sur le domaine F28;
Code d'authentification de message Galois ( GMAC ), basé sur le domaine F2128;
QR code, utilisant le codage Reed-Solomon basé sur F28;
Le protocole FRI original et le protocole zk-STARK, ainsi que la fonction de hachage Grøstl qui a atteint la finale de SHA-3, basée sur le domaine F28, sont des algorithmes de hachage très adaptés à 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 entièrement s'appuyer sur l'extension de domaine pour assurer sa sécurité et sa réelle utilisabilité. La plupart des polynômes impliqués dans les calculs des Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais doivent simplement fonctionner sous le domaine de base, ce qui permet d'atteindre une grande efficacité dans les petits domaines. 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 2 problèmes pratiques : lors du calcul de la représentation du 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 de 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 extension de l'encodage.
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 : d'abord, en utilisant un polynôme multivarié ( qui est spécifiquement un polynôme multilinéraire ) à la place d'un polynôme à variable unique, en représentant l'ensemble de la trajectoire de calcul par ses valeurs sur des "hypercubes" ( ; ensuite, étant donné que chaque dimension de l'hypercube a une longueur de 2, il n'est pas possible de procéder à une extension standard de Reed-Solomon 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 effectuée. Cette méthode, tout en garantissant la sécurité, améliore considérablement l'efficacité du codage et les performances de calcul.
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): Le PIOP, en tant que cœur du système de preuve, transforme les relations de calcul en équations polynomiales vérifiables. Différents protocoles PIOP permettent au prouveur d'envoyer progressivement des polynômes par l'interaction avec le vérificateur, permettant ainsi au vérificateur de valider 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, affectant ainsi la performance et l'efficacité du système SNARK dans son ensemble.
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 valide. Le PCS est un outil cryptographique grâce auquel le prouveur peut s'engager sur un certain polynôme et vérifier ultérieurement 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, entre autres. Différents PCS ont des performances, des niveaux de sécurité et des scénarios d'application différents.
En fonction des besoins spécifiques, choisissez différents PIOP et PCS, et combinez-les avec un champ 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, et 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 : utilisant PLONK PIOP et FRI PCS combinés, et basé sur le domaine de Goldilocks. Plonky2 est conçu pour permettre une récursivité efficace. Lors de la conception de ces systèmes, les PIOP et PCS choisis doivent correspondre au champ fini ou à la courbe elliptique utilisés, afin d'assurer la correction, 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, 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 + domaine binaire. Plus précisément, Binius comprend cinq technologies clés pour réaliser son efficacité et sa sécurité. Tout d'abord, l'arithmétique 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 de HyperPlonk dans son protocole de preuve Oracle interactif (PIOP), garantissant une vérification de la 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 sécurité robuste au mécanisme de recherche. Enfin, le protocole utilise un schéma d'engagement polynomiale sur de petits domaines (Small-Field PCS), lui permettant de réaliser un système de preuve efficace sur le domaine binaire, tout en réduisant les frais généralement associés aux grands domaines.
( 2.1 Domain fini : arithmétisation basée sur les tours de champs binaires
Les corps binaires en tour sont la clé de la réalisation de calculs vérifiables rapides, principalement en raison de deux aspects : le calcul efficace et l'arithmétique efficace. Les corps binaires supportent essentiellement des opérations arithmétiques très efficaces, ce qui en fait un choix idéal pour les applications cryptographiques sensibles aux performances. De plus, la structure des corps binaires supporte un processus d'arithmétisation simplifié, c'est-à-dire que les opérations effectuées sur le corps binaire peuvent être représentées sous une forme algébrique compacte et facile à vérifier. Ces caractéristiques, combinées à la capacité d'exploiter pleinement la hiérarchie par le biais de la structure en tour, rendent les corps binaires particulièrement adaptés à des systèmes de preuves évolutifs tels que Binius.
Le terme "canonical" fait référence à la représentation unique et directe d'un élément dans un corps binaire. Par exemple, dans le corps binaire le plus simple F2, toute chaîne de k bits peut être directement mappée à un élément du corps binaire de k bits. Cela diffère des corps premiers, qui ne peuvent pas fournir cette représentation canonique dans un nombre de bits donné. Bien qu'un corps premier de 32 bits puisse être contenu dans 32 bits, ce n'est pas le cas pour chaque chaîne de 32 bits qui peut correspondre de manière unique à un élément du corps, tandis que le corps binaire bénéficie de cette facilité de correspondance un à un. Dans le corps 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 corps finis particuliers comme Mersenne-31 ou Goldilocks-64. Dans le corps 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 celle utilisée dans POLYVAL ) et la réduction récursive ( comme dans Tower ). L'article "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" souligne que le corps binaire ne nécessite pas l'introduction de retenues dans les opérations d'addition et de multiplication, et que l'opération de carrée dans le corps 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 du domaine binaire. Elle peut être considérée comme un élément unique dans un domaine binaire de 128 bits, ou être analysée en tant que deux éléments de domaine en tour de 64 bits, quatre éléments de domaine en tour de 32 bits, seize éléments de domaine en tour de 8 bits, ou 128 éléments de domaine F2. La flexibilité de cette représentation ne nécessite aucun coût de calcul, il s'agit simplement d'un type de conversion 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é des calculs. En outre, l'article "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité computationnelle des opérations de multiplication, de mise au carré et d'inversion dans un domaine binaire de tour de n bits ( décomposé en sous-domaines de m bits ).
Figure 1 : Domaine binaire en tour
( 2.2 PIOP: version adaptée du produit HyperPlonk et vérification de permutation ------ applicable aux corps binaires
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 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 hyperbolique booléen sont une relation de permutation f(x) = f(π)x((, afin d'assurer la cohérence des permutations entre les variables du polynôme.
LookupCheck : Vérifiez si l'évaluation du polynôme se trouve dans la table de recherche donnée, c'est-à-dire f)Bµ) ⊆ T(Bµ), assurez-vous que certaines valeurs se situent dans la plage spécifiée.
MultisetCheck : vérifier 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 de garantir l'exactitude du produit polynomial.
ZeroCheck : vérifier si un polynôme multivariable est nul à un point quelconque sur l'hypercube booléen ∏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 une évaluation de polynôme univarié, cela réduit la complexité de calcul pour le vérificateur. De plus, SumCheck permet le traitement par lots en introduisant des nombres aléatoires et en construisant des combinaisons linéaires pour traiter plusieurs instances de vérification de sommes.
BatchCheck : basé sur SumCheck, vérifie la validité des évaluations 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 améliore les trois aspects suivants :
Optimisation de ProductCheck : dans HyperPlonk, ProductCheck exige que le dénominateur U soit non nul partout dans le cube 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é de calcul.
Gestion du problème de division par zéro : HyperPlonk ne parvient pas à gérer correctement les cas de division par zéro, ce qui empêche 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 intercolonnes : HyperPlonk n'a pas cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de traiter 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 des polynômes multivariés plus complexes, offrant un soutien fonctionnel plus fort. Ces améliorations non seulement résolvent les limitations de HyperPlonk, mais posent également les bases pour de futurs systèmes de preuve basés sur des domaines binaires.
( 2.3 PIOP : nouvel argument de décalage multilinéaire ------ applicable au cube hyperbolique booléen
Dans le protocole Binius, la construction et le traitement des polynômes virtuels sont importants.
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.
11 J'aime
Récompense
11
6
Partager
Commentaire
0/400
MissedTheBoat
· Il y a 18h
La compacité est la clé ! Parachutage !
Voir l'originalRépondre0
GasBandit
· 08-05 20:35
Comment avez-vous pensé à optimiser les starks ?
Voir l'originalRépondre0
CryptoComedian
· 08-05 20:35
Écrire des articles a une largeur de pression, j'ai écrit trois générations sans atteindre les normes.
Voir l'originalRépondre0
BlockchainThinkTank
· 08-05 20:23
Nous pensons que l'optimisation ZKP est encore à un stade précoce et qu'il faut aborder ces solutions d'amélioration de l'efficacité avec prudence.
Voir l'originalRépondre0
MentalWealthHarvester
· 08-05 20:17
Encore la période dorée de mes STARKs, je peux encore extraire.
Voir l'originalRépondre0
LayoffMiner
· 08-05 20:08
À quoi tu penses, le gas ne peut pas baisser et tu fais tout un plat de ça.
Nouvelles idées d'optimisation des STARKs : Binius stimule le développement du 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 index dans les boucles for, les valeurs booléennes, les compteurs, etc. Cependant, pour garantir la sécurité des preuves basées sur des arbres de Merkle, l'utilisation du codage de Reed-Solomon pour étendre les données entraîne de nombreuses valeurs redondantes supplémentaires qui occupent 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 beaucoup d'espace gaspillé. En comparaison, le domaine binaire permet d'opérer directement sur les bits, avec un codage compact et efficace sans aucun espace gaspillé, c'est-à-dire les STARKs de quatrième génération.
| Temps | STARKs | Largeur de code | |------|--------|----------| | 2018 | 1ère génération | 252 bits | | 2021 | 2ème génération | 64bit | | 2022 | 3ème génération | 32bit | | 2023 | 4e génération | 1bit |
Tableau 1 : Chemin de dérivation des STARKs
Comparé à des découvertes récentes dans des 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 :
Norme de cryptage avancé ( AES ), basé sur le domaine F28;
Code d'authentification de message Galois ( GMAC ), basé sur le domaine F2128;
QR code, utilisant le codage Reed-Solomon basé sur F28;
Le protocole FRI original et le protocole zk-STARK, ainsi que la fonction de hachage Grøstl qui a atteint la finale de SHA-3, basée sur le domaine F28, sont des algorithmes de hachage très adaptés à 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 entièrement s'appuyer sur l'extension de domaine pour assurer sa sécurité et sa réelle utilisabilité. La plupart des polynômes impliqués dans les calculs des Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais doivent simplement fonctionner sous le domaine de base, ce qui permet d'atteindre une grande efficacité dans les petits domaines. 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 2 problèmes pratiques : lors du calcul de la représentation du 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 de 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 extension de l'encodage.
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 : d'abord, en utilisant un polynôme multivarié ( qui est spécifiquement un polynôme multilinéraire ) à la place d'un polynôme à variable unique, en représentant l'ensemble de la trajectoire de calcul par ses valeurs sur des "hypercubes" ( ; ensuite, étant donné que chaque dimension de l'hypercube a une longueur de 2, il n'est pas possible de procéder à une extension standard de Reed-Solomon 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 effectuée. Cette méthode, tout en garantissant la sécurité, améliore considérablement l'efficacité du codage et les performances de calcul.
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): Le PIOP, en tant que cœur du système de preuve, transforme les relations de calcul en équations polynomiales vérifiables. Différents protocoles PIOP permettent au prouveur d'envoyer progressivement des polynômes par l'interaction avec le vérificateur, permettant ainsi au vérificateur de valider 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, affectant ainsi la performance et l'efficacité du système SNARK dans son ensemble.
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 valide. Le PCS est un outil cryptographique grâce auquel le prouveur peut s'engager sur un certain polynôme et vérifier ultérieurement 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, entre autres. Différents PCS ont des performances, des niveaux de sécurité et des scénarios d'application différents.
En fonction des besoins spécifiques, choisissez différents PIOP et PCS, et combinez-les avec un champ 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, et 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 : utilisant PLONK PIOP et FRI PCS combinés, et basé sur le domaine de Goldilocks. Plonky2 est conçu pour permettre une récursivité efficace. Lors de la conception de ces systèmes, les PIOP et PCS choisis doivent correspondre au champ fini ou à la courbe elliptique utilisés, afin d'assurer la correction, 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, 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 + domaine binaire. Plus précisément, Binius comprend cinq technologies clés pour réaliser son efficacité et sa sécurité. Tout d'abord, l'arithmétique 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 de HyperPlonk dans son protocole de preuve Oracle interactif (PIOP), garantissant une vérification de la 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 sécurité robuste au mécanisme de recherche. Enfin, le protocole utilise un schéma d'engagement polynomiale sur de petits domaines (Small-Field PCS), lui permettant de réaliser un système de preuve efficace sur le domaine binaire, tout en réduisant les frais généralement associés aux grands domaines.
( 2.1 Domain fini : arithmétisation basée sur les tours de champs binaires
Les corps binaires en tour sont la clé de la réalisation de calculs vérifiables rapides, principalement en raison de deux aspects : le calcul efficace et l'arithmétique efficace. Les corps binaires supportent essentiellement des opérations arithmétiques très efficaces, ce qui en fait un choix idéal pour les applications cryptographiques sensibles aux performances. De plus, la structure des corps binaires supporte un processus d'arithmétisation simplifié, c'est-à-dire que les opérations effectuées sur le corps binaire peuvent être représentées sous une forme algébrique compacte et facile à vérifier. Ces caractéristiques, combinées à la capacité d'exploiter pleinement la hiérarchie par le biais de la structure en tour, rendent les corps binaires particulièrement adaptés à des systèmes de preuves évolutifs tels que Binius.
Le terme "canonical" fait référence à la représentation unique et directe d'un élément dans un corps binaire. Par exemple, dans le corps binaire le plus simple F2, toute chaîne de k bits peut être directement mappée à un élément du corps binaire de k bits. Cela diffère des corps premiers, qui ne peuvent pas fournir cette représentation canonique dans un nombre de bits donné. Bien qu'un corps premier de 32 bits puisse être contenu dans 32 bits, ce n'est pas le cas pour chaque chaîne de 32 bits qui peut correspondre de manière unique à un élément du corps, tandis que le corps binaire bénéficie de cette facilité de correspondance un à un. Dans le corps 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 corps finis particuliers comme Mersenne-31 ou Goldilocks-64. Dans le corps 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 celle utilisée dans POLYVAL ) et la réduction récursive ( comme dans Tower ). L'article "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" souligne que le corps binaire ne nécessite pas l'introduction de retenues dans les opérations d'addition et de multiplication, et que l'opération de carrée dans le corps 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 du domaine binaire. Elle peut être considérée comme un élément unique dans un domaine binaire de 128 bits, ou être analysée en tant que deux éléments de domaine en tour de 64 bits, quatre éléments de domaine en tour de 32 bits, seize éléments de domaine en tour de 8 bits, ou 128 éléments de domaine F2. La flexibilité de cette représentation ne nécessite aucun coût de calcul, il s'agit simplement d'un type de conversion 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é des calculs. En outre, l'article "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité computationnelle des opérations de multiplication, de mise au carré et d'inversion dans un domaine binaire de tour de n bits ( décomposé en sous-domaines de m bits ).
Figure 1 : Domaine binaire en tour
( 2.2 PIOP: version adaptée du produit HyperPlonk et vérification de permutation ------ applicable aux corps binaires
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 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 hyperbolique booléen sont une relation de permutation f(x) = f(π)x((, afin d'assurer la cohérence des permutations entre les variables du polynôme.
LookupCheck : Vérifiez si l'évaluation du polynôme se trouve dans la table de recherche donnée, c'est-à-dire f)Bµ) ⊆ T(Bµ), assurez-vous que certaines valeurs se situent dans la plage spécifiée.
MultisetCheck : vérifier 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 de garantir l'exactitude du produit polynomial.
ZeroCheck : vérifier si un polynôme multivariable est nul à un point quelconque sur l'hypercube booléen ∏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 une évaluation de polynôme univarié, cela réduit la complexité de calcul pour le vérificateur. De plus, SumCheck permet le traitement par lots en introduisant des nombres aléatoires et en construisant des combinaisons linéaires pour traiter plusieurs instances de vérification de sommes.
BatchCheck : basé sur SumCheck, vérifie la validité des évaluations 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 améliore les trois aspects suivants :
Optimisation de ProductCheck : dans HyperPlonk, ProductCheck exige que le dénominateur U soit non nul partout dans le cube 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é de calcul.
Gestion du problème de division par zéro : HyperPlonk ne parvient pas à gérer correctement les cas de division par zéro, ce qui empêche 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 intercolonnes : HyperPlonk n'a pas cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de traiter 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 des polynômes multivariés plus complexes, offrant un soutien fonctionnel plus fort. Ces améliorations non seulement résolvent les limitations de HyperPlonk, mais posent également les bases pour de futurs systèmes de preuve basés sur des domaines binaires.
( 2.3 PIOP : nouvel argument de décalage multilinéaire ------ applicable au cube hyperbolique booléen
Dans le protocole Binius, la construction et le traitement des polynômes virtuels sont importants.