Analyse des principes des STARKs de Binius et réflexion sur leur optimisation
1 Introduction
Les STARKs sont un système de preuve basé sur le hachage, contrairement aux SNARKs qui sont basés sur les courbes elliptiques. Une des principales raisons pour lesquelles les STARKs sont actuellement peu efficaces est que la plupart des valeurs numériques 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 Reed-Solomon pour étendre les données entraîne de nombreuses valeurs redondantes supplémentaires occupant tout le domaine, même si la valeur d'origine 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 le montre 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 présente encore une grande quantité d'espace gaspillé. En comparaison, le domaine binaire permet d'opérer directement sur les bits, ce qui rend 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
| Génération | Largeur | Caractéristiques |
|------|------|------|
| 1ère génération | 252 bits | Domaine, gaspillage d'espace important |
| 2ème génération | 64 bits | Domaine moyen, gaspillage d'espace important |
| 3ème génération | 32 bits | Petit domaine, il reste de l'espace gaspillé |
| 4ème génération | 1bit | Domaine binaire, pas d'espace gaspillé |
Comparé à Goldilocks, BabyBear, Mersenne31 et d'autres découvertes récentes sur les corps finis, 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ée ( AES ), basée sur le domaine F28 ;
Galois Message Authentication Code ( GMAC ), basé sur le champ F2128 ;
QR Code, utilisant le codage Reed-Solomon basé sur F28 ;
Protocole FRI original et zk-STARK, ainsi que la fonction de hachage Grøstl, qui a atteint la finale de SHA-3, est basée sur le domaine F28 et constitue 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 entièrement dépendre de 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 peuvent simplement fonctionner dans le domaine de base, réalisant ainsi une grande efficacité dans un petit domaine. 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 un domaine binaire, il existe deux problèmes pratiques : lors du calcul de la trace dans les STARKs, la taille du domaine utilisé doit être supérieure au degré du polynôme ; lors de l'engagement dans l'arbre Merkle des STARKs, un codage de Reed-Solomon doit être effectué, et la taille du domaine utilisé doit être supérieure à la taille après l'extension du codage.
Binius a proposé une solution innovante qui traite ces deux problèmes de manière distincte et représente les mêmes données de deux façons différentes : tout d'abord, en utilisant des polynômes multivariables (, en particulier des polynômes multilinaires ), pour remplacer les polynômes à variable unique, en représentant 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 de procéder à 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 basée sur ce carré. 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 informationnelle ( 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 permettent au prouveur d'envoyer progressivement des polynômes, grâce à une interaction avec le vérificateur, de sorte que le vérificateur puisse vérifier si le calcul est correct en se basant sur les résultats d'évaluation d'un nombre limité de polynômes. Les protocoles PIOP existants incluent : PLONK PIOP, Spartan PIOP et HyperPlonk PIOP, qui traitent chacun les expressions polynomiales de manière différente, influençant ainsi la performance et l'efficacité du système SNARK dans son ensemble.
Schéma de promesse polynomiale ( Polynomial Commitment Scheme, PCS ) : Le schéma de promesse polynomiale est utilisé pour prouver si l'égalité polynomiale générée par PIOP est valide. PCS est un outil cryptographique qui permet à un prouveur de s'engager sur un certain polynôme et de 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 de promesse polynomiale 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.
En fonction des besoins spécifiques, choisissez différents PIOP et PCS, et combinez-les avec un domaine fini ou une courbe elliptique appropriée, il est possible 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. 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 : combine PLONK PIOP et FRI PCS, 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és, afin d'assurer la correction, la performance et la sécurité du système. Ces choix combinés affectent non seulement la taille des preuves SNARK et l'efficacité de la vérification, mais déterminent également si le système peut réaliser la transparence sans configuration de confiance préalable, et s'il peut prendre en charge des fonctionnalités d'extension telles que les preuves récursives ou les preuves agrégées.
Binius : HyperPlonk PIOP + Brakedown PCS + 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 adapte dans son protocole de preuve Oracle interactif (PIOP) les vérifications de produit et de permutation de HyperPlonk, 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 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), lui permettant de réaliser un système de preuve efficace dans le domaine binaire, tout en réduisant les coûts généralement associés aux grands domaines.
( 2.1 Domaine fini : arithmétisation basée sur les tours de champs binaires
Les corps binaires en tour sont la clé pour réaliser des calculs vérifiables rapides, principalement en raison de deux aspects : le calcul efficace et l'arithmétique efficace. Les corps binaires soutiennent essentiellement des opérations arithmétiques extrêmement efficaces, ce qui en fait un choix idéal pour les applications cryptographiques sensibles aux performances. De plus, la structure des corps binaires soutient un processus d'arithmétisation simplifié, c'est-à-dire que les opérations effectuées sur les corps binaires peuvent être représentées sous une forme algébrique compacte et facile à vérifier. Ces caractéristiques, associées à la capacité d'exploiter pleinement les caractéristiques hiérarchiques de la structure en tour, rendent les corps binaires particulièrement adaptés à des systèmes de preuve évolutifs tels que Binius.
Le terme "canonical" fait référence à la représentation unique et directe des éléments dans un 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 de domaine binaire de k bits. Cela diffère des domaines premiers, qui ne peuvent pas fournir une telle représentation canonique dans un nombre de bits donné. Bien qu'un domaine premier de 32 bits puisse être contenu dans 32 bits, ce n'est pas le cas pour chaque chaîne de 32 bits qui peut être associée de manière unique à un élément de domaine, alors que le domaine binaire offre cette commodité de correspondance un à un. Dans le domaine premier Fp, les méthodes de réduction courantes comprennent 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 courantes comprennent la 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 ). L'article "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" souligne que le domaine binaire n'a pas besoin d'introduire des retenues pour les opérations d'addition et de multiplication, et que l'opération de carré dans un domaine binaire est très efficace, car elle suit la règle simplifiée (X + Y )2 = X2 + Y 2.
Comme indiqué dans la figure 1, une chaîne de 128 bits : cette chaîne peut être interprétée de plusieurs manières dans le contexte des domaines binaires. Elle peut être considérée comme un élément unique dans un domaine binaire de 128 bits, ou être interprétée comme deux éléments de domaine de 64 bits, quatre éléments de domaine de 32 bits, seize éléments de domaine de 8 bits, ou 128 éléments de domaine F2. Cette flexibilité de représentation n'implique 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 petit 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é de calcul des opérations de multiplication, de mise au carré et d'inversion dans un domaine binaire à n bits ( décomposé en un sous-domaine de m bits ).
( 2.2 PIOP: version adaptée de HyperPlonk Product et PermutationCheck------conçu pour le domaine binaire
La conception de PIOP dans le protocole Binius s'inspire de HyperPlonk et adopte une série de mécanismes de vérification essentiels pour valider la correction 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 le cube hyperbolique booléen constituent 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 est dans la table de recherche donnée, c'est-à-dire f(Bµ( ⊆ T)Bµ), assurez-vous que certaines valeurs sont dans la plage spécifiée.
MultisetCheck : vérifie si deux ensembles multivariables sont égaux, c'est-à-dire {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, garantissant la cohérence entre plusieurs ensembles.
ProductCheck : Vérifiez si l'évaluation d'un polynôme rationnel sur le cube hyperbolique booléen est égale à une valeur déclarée ∏x∈Hµ f(x) = s, afin de garantir l'exactitude du produit polynomial.
ZeroCheck : Vérifier si un polynôme multivariable est nul en un point quelconque du cube hyperboolé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 multivarié est égale à la valeur déclarée ∑x∈Hµ f(x) = s. En transformant le problème d'évaluation d'un polynôme multivarié en un problème d'évaluation de polynôme à une seule 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 réaliser le traitement par lots de plusieurs instances de vérification de somme.
BatchCheck : basé sur SumCheck, vérifie l'exactitude 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 apporte des améliorations dans les 3 domaines suivants :
Optimisation de ProductCheck : dans HyperPlonk, ProductCheck exige que le dénominateur U soit non nul partout sur l'hypercube, et que le produit soit égal à une valeur spécifique ; Binius simplifie ce processus de vérification en spécialisant cette valeur à 1, réduisant ainsi la complexité de calcul.
Gestion des problèmes de division par zéro : HyperPlonk n'a pas pu gérer 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 inter-colonnes : HyperPlonk n'a pas cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de gérer des situations 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 validations de polynômes multivariables plus complexes, offrant un soutien fonctionnel plus fort. Ces améliorations ont non seulement résolu les limitations de HyperPlonk, mais ont également ouvert la voie à de nouvelles possibilités.
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.
8 J'aime
Récompense
8
5
Partager
Commentaire
0/400
SelfCustodyIssues
· 07-11 16:18
Cette vitesse de développement a durement baissé pit
Voir l'originalRépondre0
CryptoTarotReader
· 07-11 09:56
Les codeurs recommencent à se battre sur le terrain, est-ce vraiment nécessaire ?
Voir l'originalRépondre0
NFTRegretful
· 07-08 16:51
32 bits ne suffisent pas, c'est compliqué.
Voir l'originalRépondre0
ImpermanentPhilosopher
· 07-08 16:50
Cette amélioration est vraiment trop lente... 32 est déjà trop long.
Voir l'originalRépondre0
BearMarketSurvivor
· 07-08 16:33
32 bits c'est trop grand, celui qui s'enroule perd.
Binius domaine binaire STARKs : analyse des principes et innovations d'optimisation
Analyse des principes des STARKs de Binius et réflexion sur leur optimisation
1 Introduction
Les STARKs sont un système de preuve basé sur le hachage, contrairement aux SNARKs qui sont basés sur les courbes elliptiques. Une des principales raisons pour lesquelles les STARKs sont actuellement peu efficaces est que la plupart des valeurs numériques 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 Reed-Solomon pour étendre les données entraîne de nombreuses valeurs redondantes supplémentaires occupant tout le domaine, même si la valeur d'origine 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 le montre 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 présente encore une grande quantité d'espace gaspillé. En comparaison, le domaine binaire permet d'opérer directement sur les bits, ce qui rend 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
| Génération | Largeur | Caractéristiques | |------|------|------| | 1ère génération | 252 bits | Domaine, gaspillage d'espace important | | 2ème génération | 64 bits | Domaine moyen, gaspillage d'espace important |
| 3ème génération | 32 bits | Petit domaine, il reste de l'espace gaspillé | | 4ème génération | 1bit | Domaine binaire, pas d'espace gaspillé |
Comparé à Goldilocks, BabyBear, Mersenne31 et d'autres découvertes récentes sur les corps finis, 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ée ( AES ), basée sur le domaine F28 ;
Galois Message Authentication Code ( GMAC ), basé sur le champ F2128 ;
QR Code, utilisant le codage Reed-Solomon basé sur F28 ;
Protocole FRI original et zk-STARK, ainsi que la fonction de hachage Grøstl, qui a atteint la finale de SHA-3, est basée sur le domaine F28 et constitue 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 entièrement dépendre de 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 peuvent simplement fonctionner dans le domaine de base, réalisant ainsi une grande efficacité dans un petit domaine. 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 un domaine binaire, il existe deux problèmes pratiques : lors du calcul de la trace dans les STARKs, la taille du domaine utilisé doit être supérieure au degré du polynôme ; lors de l'engagement dans l'arbre Merkle des STARKs, un codage de Reed-Solomon doit être effectué, et la taille du domaine utilisé doit être supérieure à la taille après l'extension du codage.
Binius a proposé une solution innovante qui traite ces deux problèmes de manière distincte et représente les mêmes données de deux façons différentes : tout d'abord, en utilisant des polynômes multivariables (, en particulier des polynômes multilinaires ), pour remplacer les polynômes à variable unique, en représentant 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 de procéder à 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 basée sur ce carré. 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 informationnelle ( 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 permettent au prouveur d'envoyer progressivement des polynômes, grâce à une interaction avec le vérificateur, de sorte que le vérificateur puisse vérifier si le calcul est correct en se basant sur les résultats d'évaluation d'un nombre limité de polynômes. Les protocoles PIOP existants incluent : PLONK PIOP, Spartan PIOP et HyperPlonk PIOP, qui traitent chacun les expressions polynomiales de manière différente, influençant ainsi la performance et l'efficacité du système SNARK dans son ensemble.
Schéma de promesse polynomiale ( Polynomial Commitment Scheme, PCS ) : Le schéma de promesse polynomiale est utilisé pour prouver si l'égalité polynomiale générée par PIOP est valide. PCS est un outil cryptographique qui permet à un prouveur de s'engager sur un certain polynôme et de 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 de promesse polynomiale 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.
En fonction des besoins spécifiques, choisissez différents PIOP et PCS, et combinez-les avec un domaine fini ou une courbe elliptique appropriée, il est possible 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. 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 : combine PLONK PIOP et FRI PCS, 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és, afin d'assurer la correction, la performance et la sécurité du système. Ces choix combinés affectent non seulement la taille des preuves SNARK et l'efficacité de la vérification, mais déterminent également si le système peut réaliser la transparence sans configuration de confiance préalable, et s'il peut prendre en charge des fonctionnalités d'extension telles que les preuves récursives ou les preuves agrégées.
Binius : HyperPlonk PIOP + Brakedown PCS + 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 adapte dans son protocole de preuve Oracle interactif (PIOP) les vérifications de produit et de permutation de HyperPlonk, 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 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), lui permettant de réaliser un système de preuve efficace dans le domaine binaire, tout en réduisant les coûts généralement associés aux grands domaines.
( 2.1 Domaine fini : arithmétisation basée sur les tours de champs binaires
Les corps binaires en tour sont la clé pour réaliser des calculs vérifiables rapides, principalement en raison de deux aspects : le calcul efficace et l'arithmétique efficace. Les corps binaires soutiennent essentiellement des opérations arithmétiques extrêmement efficaces, ce qui en fait un choix idéal pour les applications cryptographiques sensibles aux performances. De plus, la structure des corps binaires soutient un processus d'arithmétisation simplifié, c'est-à-dire que les opérations effectuées sur les corps binaires peuvent être représentées sous une forme algébrique compacte et facile à vérifier. Ces caractéristiques, associées à la capacité d'exploiter pleinement les caractéristiques hiérarchiques de la structure en tour, rendent les corps binaires particulièrement adaptés à des systèmes de preuve évolutifs tels que Binius.
Le terme "canonical" fait référence à la représentation unique et directe des éléments dans un 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 de domaine binaire de k bits. Cela diffère des domaines premiers, qui ne peuvent pas fournir une telle représentation canonique dans un nombre de bits donné. Bien qu'un domaine premier de 32 bits puisse être contenu dans 32 bits, ce n'est pas le cas pour chaque chaîne de 32 bits qui peut être associée de manière unique à un élément de domaine, alors que le domaine binaire offre cette commodité de correspondance un à un. Dans le domaine premier Fp, les méthodes de réduction courantes comprennent 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 courantes comprennent la 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 ). L'article "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" souligne que le domaine binaire n'a pas besoin d'introduire des retenues pour les opérations d'addition et de multiplication, et que l'opération de carré dans un domaine binaire est très efficace, car elle suit la règle simplifiée (X + Y )2 = X2 + Y 2.
Comme indiqué dans la figure 1, une chaîne de 128 bits : cette chaîne peut être interprétée de plusieurs manières dans le contexte des domaines binaires. Elle peut être considérée comme un élément unique dans un domaine binaire de 128 bits, ou être interprétée comme deux éléments de domaine de 64 bits, quatre éléments de domaine de 32 bits, seize éléments de domaine de 8 bits, ou 128 éléments de domaine F2. Cette flexibilité de représentation n'implique 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 petit 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é de calcul des opérations de multiplication, de mise au carré et d'inversion dans un domaine binaire à n bits ( décomposé en un sous-domaine de m bits ).
( 2.2 PIOP: version adaptée de HyperPlonk Product et PermutationCheck------conçu pour le domaine binaire
La conception de PIOP dans le protocole Binius s'inspire de HyperPlonk et adopte une série de mécanismes de vérification essentiels pour valider la correction 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 le cube hyperbolique booléen constituent 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 est dans la table de recherche donnée, c'est-à-dire f(Bµ( ⊆ T)Bµ), assurez-vous que certaines valeurs sont dans la plage spécifiée.
MultisetCheck : vérifie si deux ensembles multivariables sont égaux, c'est-à-dire {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, garantissant la cohérence entre plusieurs ensembles.
ProductCheck : Vérifiez si l'évaluation d'un polynôme rationnel sur le cube hyperbolique booléen est égale à une valeur déclarée ∏x∈Hµ f(x) = s, afin de garantir l'exactitude du produit polynomial.
ZeroCheck : Vérifier si un polynôme multivariable est nul en un point quelconque du cube hyperboolé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 multivarié est égale à la valeur déclarée ∑x∈Hµ f(x) = s. En transformant le problème d'évaluation d'un polynôme multivarié en un problème d'évaluation de polynôme à une seule 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 réaliser le traitement par lots de plusieurs instances de vérification de somme.
BatchCheck : basé sur SumCheck, vérifie l'exactitude 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 apporte des améliorations dans les 3 domaines suivants :
Optimisation de ProductCheck : dans HyperPlonk, ProductCheck exige que le dénominateur U soit non nul partout sur l'hypercube, et que le produit soit égal à une valeur spécifique ; Binius simplifie ce processus de vérification en spécialisant cette valeur à 1, réduisant ainsi la complexité de calcul.
Gestion des problèmes de division par zéro : HyperPlonk n'a pas pu gérer 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 inter-colonnes : HyperPlonk n'a pas cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de gérer des situations 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 validations de polynômes multivariables plus complexes, offrant un soutien fonctionnel plus fort. Ces améliorations ont non seulement résolu les limitations de HyperPlonk, mais ont également ouvert la voie à de nouvelles possibilités.