Analyse des principes de Binius STARKs et réflexion sur son 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 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 codage 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 codage de 32 bits souffre encore d'un grand gaspillage d'espace. 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 découvertes récentes dans des domaines finis comme Goldilocks, BabyBear, Mersenne31, 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 :
Norme de cryptage avancée (AES), basée sur le domaine F28
Galois Message Authentication Code ( GMAC ), basé sur le corps 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 du SHA-3, qui est basée sur le domaine F28, sont des algorithmes de hachage très adaptés à la récursion.
Lorsque des domaines plus petits sont utilisés, l'opération d'extension de domaine devient de plus en plus importante pour garantir la sécurité. Le domaine binaire utilisé par Binius doit entièrement s'appuyer sur l'extension de domaine pour assurer sa sécurité et sa praticité. La plupart des polynômes impliqués dans les calculs de Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais doivent simplement fonctionner 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 plonger dans un domaine d'extension plus grand pour garantir la sécurité requise.
Lors de la construction d'un système de preuve basé sur un domaine binaire, il existe 2 problèmes pratiques : lors 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 de 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 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é (, en particulier 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 "hypercubes" ( ; ensuite, étant donné que la longueur de chaque dimension de l'hypercube est de 2, il n'est pas possible d'effectuer une extension Reed-Solomon standard comme avec les STARKs, mais l'hypercube peut être considéré comme un carré ), sur la base duquel on peut effectuer une extension Reed-Solomon. Cette méthode garantit la sécurité tout en améliorant considérablement l'efficacité du codage et la performance de calcul.
2 Analyse des principes
La construction de la plupart des systèmes SNARKs actuels comprend généralement les deux parties suivantes :
Information Théorique de Preuve d'Oracle Interactif Polynomiale (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, en tant que système de preuve central, transforme les relations de calcul d'entrée en égalités polynomiales vérifiables. Différents protocoles PIOP, à travers des interactions 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 nombre limité de résultats d'évaluation de polynômes. Les protocoles PIOP existants incluent : PLONK PIOP, Spartan PIOP et HyperPlonk PIOP, chacun ayant une approche différente du traitement des expressions polynomiales, ce qui affecte 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 valide. Le PCS est un outil cryptographique par lequel 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, entre autres. Différents PCS ont des performances, des niveaux de sécurité et des cas d'utilisation différents.
Selon les besoins spécifiques, choisissez différents PIOP et PCS, et combinez-les avec des domaines finis ou des courbes elliptiques appropriés, ce qui permet de construire des systèmes de preuve avec différentes propriétés. Par exemple :
• Halo2: combiné de PLONK PIOP et de Bulletproofs PCS, basé sur la courbe Pasta. Lors de la conception de Halo2, l'accent a été mis sur l'évolutivité et l'élimination du trusted setup dans le protocole ZCash.
• Plonky2 : combine PLONK PIOP avec FRI PCS 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, le PIOP et le PCS choisis doivent correspondre au corps fini ou à la courbe elliptique utilisée, 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 préalable, et s'il peut supporter des fonctionnalités d'extension telles que des preuves récursives ou des preuves agrégées.
Binius : HyperPlonk PIOP + Brakedown PCS + domaine binaire. Plus précisément, Binius comprend cinq technologies clés pour garantir son efficacité et sa sécurité. Tout d'abord, l'arithmétique basée sur les tours de champs binaires (towers of binary fields) constitue la base de ses calculs, permettant des opérations simplifiées dans le domaine 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 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 polynomial sur de petits domaines (Small-Field PCS), permettant un système de preuve efficace dans le domaine binaire et 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 essentiels pour réaliser des calculs rapides et 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 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 permet 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 facile à vérifier. Ces caractéristiques, associées à la capacité d'exploiter pleinement leur hiérarchie grâce à la structure en tour, font que les corps binaires conviennent particulièrement à des systèmes de preuve évolutifs comme Binius.
Le terme "canonical" fait référence à la représentation unique et directe des éléments dans le domaine binaire. Par exemple, dans le domaine binaire de base F2, toute 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, cela ne signifie pas que chaque chaîne de 32 bits corresponde de manière unique à un élément du domaine, tandis que le domaine binaire offre cette commodité de 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 tels que Mersenne-31 ou Goldilocks-64. Dans le domaine binaire F2k, les méthodes de réduction couramment utilisées incluent la réduction spéciale ) comme utilisée dans AES, la réduction de Montgomery ### comme utilisée dans POLYVAL, et la réduction récursive ( comme Tower ). L'article "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" indique que dans le domaine binaire, il n'est pas nécessaire d'introduire des retenues lors des 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 illustré par la figure 1, une chaîne de 128 bits : cette chaîne peut être interprétée de différentes manières dans le contexte des domaines binaires. Elle peut être considérée comme un élément unique dans le domaine binaire de 128 bits, ou être analysée comme deux éléments de domaine de tour de 64 bits, quatre éléments de domaine de tour de 32 bits, seize éléments de domaine de tour de 8 bits, ou 128 éléments de domaine F2. Cette flexibilité de représentation ne nécessite aucun coût de calcul, juste un changement de type de chaîne de bits (typecast), ce qui est une propriété très intéressante et utile. De plus, les éléments de petits domaines peuvent être emballés en éléments de plus grands domaines sans coût de calcul supplémentaire. Le protocole Binius tire parti de cette caractéristique pour améliorer l'efficacité de calcul. 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 les domaines de tour binaire de n bits ( décomposables en sous-domaines de m bits ).
( 2.2 PIOP: version modifié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 la justesse des polynômes et des ensembles multivariés. Ces vérifications essentielles comprennent :
GateCheck : vérifier 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 l'hypercube 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 trouvent 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érifier si l'évaluation d'un polynomial rationnel sur le cube hyperbolique booléen est égale à une valeur déclarée ∏x∈Hµ f(x) = s, afin de garantir la validité du produit polynomial.
ZeroCheck : vérifier si un polynôme multivariable est nul à un point quelconque sur le cube hyperbolique booléen ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, afin d'assurer la distribution des zéros du polynôme.
SumCheck : Vérification 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 multivariable en évaluation d'un polynôme à une variable, 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 pour construire des combinaisons linéaires et réaliser le traitement par lots de plusieurs instances de vérification de somme.
BatchCheck : basé sur SumCheck, vérifie la justesse de l'évaluation de plusieurs polynômes multivariés afin d'améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk présentent 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 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, réduisant ainsi la complexité de calcul.
Gestion 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 empêche d'affirmer que U est non nul sur l'hypercube ; Binius a correctement géré 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 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, en offrant un meilleur support fonctionnel, notamment lors de la vérification de polynômes multivariables plus complexes. Ces améliorations non seulement résolvent les limitations de HyperPlonk, mais jettent é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éraire ------ applicable au cube hyperbolique booléen
Dans le protocole Binius, les multiples virtuels
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
3
Partager
Commentaire
0/400
ETHReserveBank
· Il y a 20h
off-chain coûts ont diminué, qui ne serait pas content ?
Voir l'originalRépondre0
ChainChef
· 07-31 16:01
préparer un nouvel alpha ici... binius ressemble à une sauce parfaitement réduite par rapport à ces recettes gonflées de 252 bits, pour être honnête.
Binius : Optimisation révolutionnaire des STARKs en domaine binaire
Analyse des principes de Binius STARKs et réflexion sur son 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 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 codage 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 codage de 32 bits souffre encore d'un grand gaspillage d'espace. 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 : Chemin de dérivation des STARKs
| Algèbre | Largeur de code | Exemple | |------|----------|------| | 1ère génération | 252 bits | Ethereum STARKs | | 2ème génération | 64 bits | Plonky2 | | 3ème génération | 32 bits | BabyBear | | 4ème génération | 1bit | Binius |
Comparé aux découvertes récentes dans des domaines finis comme Goldilocks, BabyBear, Mersenne31, 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 :
Lorsque des domaines plus petits sont utilisés, l'opération d'extension de domaine devient de plus en plus importante pour garantir la sécurité. Le domaine binaire utilisé par Binius doit entièrement s'appuyer sur l'extension de domaine pour assurer sa sécurité et sa praticité. La plupart des polynômes impliqués dans les calculs de Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais doivent simplement fonctionner 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 plonger dans un domaine d'extension plus grand pour garantir la sécurité requise.
Lors de la construction d'un système de preuve basé sur un domaine binaire, il existe 2 problèmes pratiques : lors 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 de 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 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é (, en particulier 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 "hypercubes" ( ; ensuite, étant donné que la longueur de chaque dimension de l'hypercube est de 2, il n'est pas possible d'effectuer une extension Reed-Solomon standard comme avec les STARKs, mais l'hypercube peut être considéré comme un carré ), sur la base duquel on peut effectuer une extension Reed-Solomon. Cette méthode garantit la sécurité tout en améliorant considérablement l'efficacité du codage et la performance de calcul.
2 Analyse des principes
La construction de la plupart des systèmes SNARKs actuels comprend généralement les deux parties suivantes :
Information Théorique de Preuve d'Oracle Interactif Polynomiale (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, en tant que système de preuve central, transforme les relations de calcul d'entrée en égalités polynomiales vérifiables. Différents protocoles PIOP, à travers des interactions 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 nombre limité de résultats d'évaluation de polynômes. Les protocoles PIOP existants incluent : PLONK PIOP, Spartan PIOP et HyperPlonk PIOP, chacun ayant une approche différente du traitement des expressions polynomiales, ce qui affecte 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 valide. Le PCS est un outil cryptographique par lequel 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, entre autres. Différents PCS ont des performances, des niveaux de sécurité et des cas d'utilisation différents.
Selon les besoins spécifiques, choisissez différents PIOP et PCS, et combinez-les avec des domaines finis ou des courbes elliptiques appropriés, ce qui permet de construire des systèmes de preuve avec différentes propriétés. Par exemple :
• Halo2: combiné de PLONK PIOP et de Bulletproofs PCS, basé sur la courbe Pasta. Lors de la conception de Halo2, l'accent a été mis sur l'évolutivité et l'élimination du trusted setup dans le protocole ZCash.
• Plonky2 : combine PLONK PIOP avec FRI PCS 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, le PIOP et le PCS choisis doivent correspondre au corps fini ou à la courbe elliptique utilisée, 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 préalable, et s'il peut supporter des fonctionnalités d'extension telles que des preuves récursives ou des preuves agrégées.
Binius : HyperPlonk PIOP + Brakedown PCS + domaine binaire. Plus précisément, Binius comprend cinq technologies clés pour garantir son efficacité et sa sécurité. Tout d'abord, l'arithmétique basée sur les tours de champs binaires (towers of binary fields) constitue la base de ses calculs, permettant des opérations simplifiées dans le domaine 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 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 polynomial sur de petits domaines (Small-Field PCS), permettant un système de preuve efficace dans le domaine binaire et 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 essentiels pour réaliser des calculs rapides et 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 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 permet 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 facile à vérifier. Ces caractéristiques, associées à la capacité d'exploiter pleinement leur hiérarchie grâce à la structure en tour, font que les corps binaires conviennent particulièrement à des systèmes de preuve évolutifs comme Binius.
Le terme "canonical" fait référence à la représentation unique et directe des éléments dans le domaine binaire. Par exemple, dans le domaine binaire de base F2, toute 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, cela ne signifie pas que chaque chaîne de 32 bits corresponde de manière unique à un élément du domaine, tandis que le domaine binaire offre cette commodité de 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 tels que Mersenne-31 ou Goldilocks-64. Dans le domaine binaire F2k, les méthodes de réduction couramment utilisées incluent la réduction spéciale ) comme utilisée dans AES, la réduction de Montgomery ### comme utilisée dans POLYVAL, et la réduction récursive ( comme Tower ). L'article "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" indique que dans le domaine binaire, il n'est pas nécessaire d'introduire des retenues lors des 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 illustré par la figure 1, une chaîne de 128 bits : cette chaîne peut être interprétée de différentes manières dans le contexte des domaines binaires. Elle peut être considérée comme un élément unique dans le domaine binaire de 128 bits, ou être analysée comme deux éléments de domaine de tour de 64 bits, quatre éléments de domaine de tour de 32 bits, seize éléments de domaine de tour de 8 bits, ou 128 éléments de domaine F2. Cette flexibilité de représentation ne nécessite aucun coût de calcul, juste un changement de type de chaîne de bits (typecast), ce qui est une propriété très intéressante et utile. De plus, les éléments de petits domaines peuvent être emballés en éléments de plus grands domaines sans coût de calcul supplémentaire. Le protocole Binius tire parti de cette caractéristique pour améliorer l'efficacité de calcul. 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 les domaines de tour binaire de n bits ( décomposables en sous-domaines de m bits ).
( 2.2 PIOP: version modifié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 la justesse des polynômes et des ensembles multivariés. Ces vérifications essentielles comprennent :
GateCheck : vérifier 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 l'hypercube 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 trouvent 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érifier si l'évaluation d'un polynomial rationnel sur le cube hyperbolique booléen est égale à une valeur déclarée ∏x∈Hµ f(x) = s, afin de garantir la validité du produit polynomial.
ZeroCheck : vérifier si un polynôme multivariable est nul à un point quelconque sur le cube hyperbolique booléen ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, afin d'assurer la distribution des zéros du polynôme.
SumCheck : Vérification 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 multivariable en évaluation d'un polynôme à une variable, 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 pour construire des combinaisons linéaires et réaliser le traitement par lots de plusieurs instances de vérification de somme.
BatchCheck : basé sur SumCheck, vérifie la justesse de l'évaluation de plusieurs polynômes multivariés afin d'améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk présentent 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 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, réduisant ainsi la complexité de calcul.
Gestion 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 empêche d'affirmer que U est non nul sur l'hypercube ; Binius a correctement géré 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 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, en offrant un meilleur support fonctionnel, notamment lors de la vérification de polynômes multivariables plus complexes. Ces améliorations non seulement résolvent les limitations de HyperPlonk, mais jettent é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éraire ------ applicable au cube hyperbolique booléen
Dans le protocole Binius, les multiples virtuels