Analyse des principes de Binius STARKs et réflexion sur l'optimisation
1. Introduction
Un des principaux problèmes d'efficacité des STARKs 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 de Reed-Solomon pour étendre les données entraîne l'occupation de nombreux valeurs de redondance supplémentaires dans tout le domaine, même si la valeur originale elle-même est très petite. Pour résoudre ce problème, réduire la taille du domaine est devenu 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 présente encore un grand espace gaspillé. En revanche, le domaine binaire permet d'opérer directement sur les bits, le codage étant compact et efficace sans aucun espace gaspillé, c'est-à-dire les STARKs de quatrième génération.
Comparé aux récentes découvertes dans les domaines finis comme Goldilocks, BabyBear et 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 cryptographie avancée ( AES ), basé sur le domaine F2^8
Code d'authentification de message Galois ( GMAC ), basé sur le domaine F2^128
QR code, utilisant le codage Reed-Solomon basé sur F2^8
Protocole FRI original et zk-STARK, ainsi que la fonction de hachage Grøstl qui a atteint la finale du SHA-3, cette fonction est basée sur le domaine F2^8 et est un algorithme de hachage très adapté à la récursivité.
Lorsque des domaines plus petits sont utilisés, l'opération d'extension de domaine devient de plus en plus importante pour garantir la sécurité. Le domaine binaire utilisé par Binius doit entièrement dépendre de l'extension de domaine pour assurer sa sécurité et sa réelle utilité. La plupart des polynômes impliqués dans le calcul des Prover n'ont pas besoin d'entrer dans une extension de domaine, mais doivent simplement opérer sous le domaine de base, permettant ainsi d'atteindre une grande efficacité dans un petit domaine. Cependant, les vérifications de points aléatoires et les calculs FRI doivent encore plonger dans un domaine d'extension plus grand pour garantir la sécurité requise.
Lors de la construction d'un système de preuve basé sur le domaine binaire, il existe deux problèmes pratiques : lors du calcul de la représentation de trace dans les STARKs, la taille du domaine utilisée doit être supérieure au degré du polynôme ; lors de l'engagement de l'arbre de Merkle dans les STARKs, il est nécessaire de faire un codage de Reed-Solomon, 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é ( spécifiquement un polynôme multilinéraire ) à la place d'un polynôme univarié, en représentant l'ensemble de la trajectoire de calcul par ses valeurs sur des "hyper-cubes" (; ensuite, étant donné que chaque dimension de l'hyper-cube a une longueur de 2, il n'est pas possible de procéder à une extension standard de Reed-Solomon comme avec les STARKs, mais on peut considérer l'hyper-cube comme un carré ), sur lequel on effectue l'extension de Reed-Solomon. Cette méthode améliore considérablement l'efficacité du codage et la performance de calcul tout en garantissant la sécurité.
2. Analyse du principe
La construction de la plupart des systèmes SNARKs actuels comprend généralement les deux parties suivantes :
Preuve Oracle Interactive Polynomiale Théorique de l'Information (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, en tant que système de preuve central, convertit les relations de calcul d'entrée en équations polynomiales vérifiables. Différents protocoles PIOP, à travers l'interaction avec le vérificateur, permettent au prouveur d'envoyer progressivement des polynômes, 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, chacun ayant une approche différente pour traiter les expressions polynomiales, ce qui influence la performance et l'efficacité de l'ensemble du système SNARK.
Schéma de preuve polynomiale ( Polynomial Commitment Scheme, PCS ) : Le schéma de preuve polynomiale est utilisé pour prouver si l'égalité polynomiale générée par PIOP est valide. Le PCS est un outil cryptographique qui permet au prouveur de s'engager à un certain polynôme et de 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 de preuve polynomiale courants comprennent KZG, Bulletproofs, FRI ( Fast Reed-Solomon IOPP ) et Brakedown, entre autres. Différents PCS ont des performances, une sécurité et des cas d'utilisation différents.
Selon les besoins spécifiques, choisissez différents PIOP et PCS, et combinez-les avec un domaine fini approprié ou une courbe elliptique, pour 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 : adopte PLONK PIOP et FRI PCS combinés, et est basé sur le domaine de Goldilocks. Plonky2 est conçu pour réaliser des récursions efficaces. Lors de la conception de ces systèmes, le PIOP et le PCS choisis doivent correspondre au corps fini ou à la courbe elliptique utilisée, afin d'assurer la correctitude, la performance et la sécurité du système. Le choix de ces combinaisons affecte non seulement la taille de la preuve SNARK et l'efficacité de la vérification, mais détermine également si le système peut réaliser la transparence sans configuration de confiance préalable, et s'il peut prendre en charge des fonctionnalités étendues telles que la preuve récursive ou la preuve agrégée.
Binius : HyperPlonk PIOP + Brakedown PCS + domaines binaires. Plus précisément, Binius comprend cinq technologies clés pour réaliser son efficacité et sa sécurité. Tout d'abord, l'arithmétique basée sur les tours de champs binaires (towers of binary fields) constitue la base de son calcul, permettant d'effectuer des opérations simplifiées dans le champ binaire. Deuxièmement, Binius a adapté la vérification de produit et de permutation de HyperPlonk dans son protocole de preuve Oracle interactif (PIOP), garantissant un contrôle de cohérence sécurisé 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é solide au mécanisme de recherche. Enfin, le protocole utilise un schéma d'engagement polynomial pour de petits domaines (Small-Field PCS), lui permettant de réaliser un système de preuve efficace sur le champ binaire, tout en réduisant les frais généralement associés aux grands domaines.
( 2.1 Domaine fini : arithmétique basée sur les tours de corps binaires
Les corps binaires en tour sont la clé pour réaliser un calcul vérifiable rapide, 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é de tirer pleinement parti de ses caractéristiques hiérarchiques grâce à la structure en tour, rendent les corps binaires particulièrement adaptés à des systèmes de preuve évolutifs tels que Binius.
Le terme "canonical" fait référence à la représentation unique et directe des éléments dans un corps binaire. Par exemple, dans le corps binaire de base 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 une telle représentation canonique dans un nombre de bits donné. Bien qu'un corps premier de 32 bits puisse être contenu dans 32 bits, chaque chaîne de 32 bits ne correspond pas nécessairement de manière unique à un élément du corps, tandis que le corps binaire offre cette commodité 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 spécifiques comme Mersenne-31 ou Goldilocks-64. Dans le corps binaire F2k, les méthodes de réduction courantes 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 le corps binaire n'a pas besoin d'introduire des retenues dans les opérations d'addition et de multiplication, et que l'opération de carré dans le corps binaire est très efficace, car elle suit la règle simplifiée (X + Y )^2 = X^2 + Y^2.
Comme indiqué dans la figure 1, une chaîne de 128 bits : cette chaîne peut être interprétée de plusieurs manières dans le contexte des domaines binaires. Elle peut être considérée comme un élément unique dans un domaine binaire de 128 bits, ou être décomposée en deux éléments de domaine de tour de 64 bits, quatre éléments de domaine de tour de 32 bits, 16 éléments de domaine de tour de 8 bits, ou 128 éléments de domaine F2. Cette flexibilité de représentation ne nécessite aucun coût de calcul, juste un typecast de chaîne de bits (typecast), ce qui est une propriété très intéressante et utile. De plus, les é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, le document "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité de calcul des opérations de multiplication, de mise au carré et d'inversion dans un domaine binaire de tour de n bits ( décomposable en sous-domaines de m bits ).
( 2.2 PIOP: version adaptée du produit HyperPlonk et Vérification de permutation------applicable aux domaines binaires
La conception de PIOP dans le protocole Binius s'inspire de HyperPlonk et utilise une série de mécanismes de vérification 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 forment une relation de permutation f(x) = f(π)x((, afin d'assurer la cohérence des permutations entre les variables polynomiales.
LookupCheck : Vérifie si l'évaluation du polynôme est dans la table de recherche donnée, c'est-à-dire f)Bµ) ⊆ T(Bµ), en s'assurant que certaines valeurs sont dans la plage spécifiée.
MultisetCheck : Vérifiez 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 du polynôme rationnel sur l'hypercube booléen est égale à une valeur déclarée ∏x∈Hµ f(x) = s, afin d'assurer la validité du produit polynômial.
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 de garantir 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 de l'évaluation d'un polynôme multivarié en évaluation d'un polynôme à une variable, la complexité de calcul pour le vérificateur est réduite. 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 la validité 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 partout sur le cube hypercubique, 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 adéquatement les cas de division par zéro, ce qui rend impossible 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 extension à n'importe quelle valeur de produit.
Vérification de permutation inter-colonnes : HyperPlonk ne dispose pas de cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de gérer des cas de permutation de polynômes plus complexes.
Ainsi, Binius a amélioré le mécanisme PIOPSumCheck existant, augmentant la flexibilité et l'efficacité du protocole, en particulier lors du traitement de la vérification de polynômes multivariables plus complexes, offrant un meilleur support fonctionnel. Ces améliorations ont non seulement résolu les limitations de HyperPlonk, mais ont également jeté 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 l'une des technologies clés, capables de générer efficacement.
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
AllInDaddy
· 07-27 20:46
Ah, je ne comprends pas cette optimisation Stark.
Voir l'originalRépondre0
GateUser-e51e87c7
· 07-26 04:42
La technologie donne mal à la tête Quand est-ce que les images seront ajoutées
Voir l'originalRépondre0
VirtualRichDream
· 07-25 03:17
L'efficacité est la clé.
Voir l'originalRépondre0
SatoshiChallenger
· 07-25 03:17
Les données viennent encore escroquer des financements, le 32 bits est encore gaspillé, n'est-ce pas ?
Voir l'originalRépondre0
airdrop_whisperer
· 07-25 03:13
32 bits, c'est encore du gaspillage d'espace ? Ce n'est pas assez petit...
Comment Binius optimise l'efficacité des STARKs en utilisant le domaine binaire : analyse des 4 technologies clés.
Analyse des principes de Binius STARKs et réflexion sur l'optimisation
1. Introduction
Un des principaux problèmes d'efficacité des STARKs 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 de Reed-Solomon pour étendre les données entraîne l'occupation de nombreux valeurs de redondance supplémentaires dans tout le domaine, même si la valeur originale elle-même est très petite. Pour résoudre ce problème, réduire la taille du domaine est devenu 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 présente encore un grand espace gaspillé. En revanche, le domaine binaire permet d'opérer directement sur les bits, le codage étant compact et efficace sans aucun espace gaspillé, c'est-à-dire les STARKs de quatrième génération.
| Algèbre | Largeur de codage | Mise en œuvre typique | |------|----------|----------| | 1ère génération | 252bit | StarkWare | | 2ème génération | 64bit | Plonky2 | | 3ème génération | 32 bits | Plonky3 | | 4ème génération | 1bit | Binius |
Comparé aux récentes découvertes dans les domaines finis comme Goldilocks, BabyBear et 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 dépendre de l'extension de domaine pour assurer sa sécurité et sa réelle utilité. La plupart des polynômes impliqués dans le calcul des Prover n'ont pas besoin d'entrer dans une extension de domaine, mais doivent simplement opérer sous le domaine de base, permettant ainsi d'atteindre une grande efficacité dans un petit domaine. Cependant, les vérifications de points aléatoires et les calculs FRI doivent encore plonger dans un domaine d'extension plus grand pour garantir la sécurité requise.
Lors de la construction d'un système de preuve basé sur le domaine binaire, il existe deux problèmes pratiques : lors du calcul de la représentation de trace dans les STARKs, la taille du domaine utilisée doit être supérieure au degré du polynôme ; lors de l'engagement de l'arbre de Merkle dans les STARKs, il est nécessaire de faire un codage de Reed-Solomon, 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é ( spécifiquement un polynôme multilinéraire ) à la place d'un polynôme univarié, en représentant l'ensemble de la trajectoire de calcul par ses valeurs sur des "hyper-cubes" (; ensuite, étant donné que chaque dimension de l'hyper-cube a une longueur de 2, il n'est pas possible de procéder à une extension standard de Reed-Solomon comme avec les STARKs, mais on peut considérer l'hyper-cube comme un carré ), sur lequel on effectue l'extension de Reed-Solomon. Cette méthode améliore considérablement l'efficacité du codage et la performance de calcul tout en garantissant la sécurité.
2. Analyse du principe
La construction de la plupart des systèmes SNARKs actuels comprend généralement les deux parties suivantes :
Preuve Oracle Interactive Polynomiale Théorique de l'Information (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP, en tant que système de preuve central, convertit les relations de calcul d'entrée en équations polynomiales vérifiables. Différents protocoles PIOP, à travers l'interaction avec le vérificateur, permettent au prouveur d'envoyer progressivement des polynômes, 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, chacun ayant une approche différente pour traiter les expressions polynomiales, ce qui influence la performance et l'efficacité de l'ensemble du système SNARK.
Schéma de preuve polynomiale ( Polynomial Commitment Scheme, PCS ) : Le schéma de preuve polynomiale est utilisé pour prouver si l'égalité polynomiale générée par PIOP est valide. Le PCS est un outil cryptographique qui permet au prouveur de s'engager à un certain polynôme et de 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 de preuve polynomiale courants comprennent KZG, Bulletproofs, FRI ( Fast Reed-Solomon IOPP ) et Brakedown, entre autres. Différents PCS ont des performances, une sécurité et des cas d'utilisation différents.
Selon les besoins spécifiques, choisissez différents PIOP et PCS, et combinez-les avec un domaine fini approprié ou une courbe elliptique, pour 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 : adopte PLONK PIOP et FRI PCS combinés, et est basé sur le domaine de Goldilocks. Plonky2 est conçu pour réaliser des récursions efficaces. Lors de la conception de ces systèmes, le PIOP et le PCS choisis doivent correspondre au corps fini ou à la courbe elliptique utilisée, afin d'assurer la correctitude, la performance et la sécurité du système. Le choix de ces combinaisons affecte non seulement la taille de la preuve SNARK et l'efficacité de la vérification, mais détermine également si le système peut réaliser la transparence sans configuration de confiance préalable, et s'il peut prendre en charge des fonctionnalités étendues telles que la preuve récursive ou la preuve agrégée.
Binius : HyperPlonk PIOP + Brakedown PCS + domaines binaires. Plus précisément, Binius comprend cinq technologies clés pour réaliser son efficacité et sa sécurité. Tout d'abord, l'arithmétique basée sur les tours de champs binaires (towers of binary fields) constitue la base de son calcul, permettant d'effectuer des opérations simplifiées dans le champ binaire. Deuxièmement, Binius a adapté la vérification de produit et de permutation de HyperPlonk dans son protocole de preuve Oracle interactif (PIOP), garantissant un contrôle de cohérence sécurisé 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é solide au mécanisme de recherche. Enfin, le protocole utilise un schéma d'engagement polynomial pour de petits domaines (Small-Field PCS), lui permettant de réaliser un système de preuve efficace sur le champ binaire, tout en réduisant les frais généralement associés aux grands domaines.
( 2.1 Domaine fini : arithmétique basée sur les tours de corps binaires
Les corps binaires en tour sont la clé pour réaliser un calcul vérifiable rapide, 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é de tirer pleinement parti de ses caractéristiques hiérarchiques grâce à la structure en tour, rendent les corps binaires particulièrement adaptés à des systèmes de preuve évolutifs tels que Binius.
Le terme "canonical" fait référence à la représentation unique et directe des éléments dans un corps binaire. Par exemple, dans le corps binaire de base 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 une telle représentation canonique dans un nombre de bits donné. Bien qu'un corps premier de 32 bits puisse être contenu dans 32 bits, chaque chaîne de 32 bits ne correspond pas nécessairement de manière unique à un élément du corps, tandis que le corps binaire offre cette commodité 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 spécifiques comme Mersenne-31 ou Goldilocks-64. Dans le corps binaire F2k, les méthodes de réduction courantes 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 le corps binaire n'a pas besoin d'introduire des retenues dans les opérations d'addition et de multiplication, et que l'opération de carré dans le corps binaire est très efficace, car elle suit la règle simplifiée (X + Y )^2 = X^2 + Y^2.
Comme indiqué dans la figure 1, une chaîne de 128 bits : cette chaîne peut être interprétée de plusieurs manières dans le contexte des domaines binaires. Elle peut être considérée comme un élément unique dans un domaine binaire de 128 bits, ou être décomposée en deux éléments de domaine de tour de 64 bits, quatre éléments de domaine de tour de 32 bits, 16 éléments de domaine de tour de 8 bits, ou 128 éléments de domaine F2. Cette flexibilité de représentation ne nécessite aucun coût de calcul, juste un typecast de chaîne de bits (typecast), ce qui est une propriété très intéressante et utile. De plus, les é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, le document "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité de calcul des opérations de multiplication, de mise au carré et d'inversion dans un domaine binaire de tour de n bits ( décomposable en sous-domaines de m bits ).
( 2.2 PIOP: version adaptée du produit HyperPlonk et Vérification de permutation------applicable aux domaines binaires
La conception de PIOP dans le protocole Binius s'inspire de HyperPlonk et utilise une série de mécanismes de vérification 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 forment une relation de permutation f(x) = f(π)x((, afin d'assurer la cohérence des permutations entre les variables polynomiales.
LookupCheck : Vérifie si l'évaluation du polynôme est dans la table de recherche donnée, c'est-à-dire f)Bµ) ⊆ T(Bµ), en s'assurant que certaines valeurs sont dans la plage spécifiée.
MultisetCheck : Vérifiez 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 du polynôme rationnel sur l'hypercube booléen est égale à une valeur déclarée ∏x∈Hµ f(x) = s, afin d'assurer la validité du produit polynômial.
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 de garantir 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 de l'évaluation d'un polynôme multivarié en évaluation d'un polynôme à une variable, la complexité de calcul pour le vérificateur est réduite. 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 la validité 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 partout sur le cube hypercubique, 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 adéquatement les cas de division par zéro, ce qui rend impossible 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 extension à n'importe quelle valeur de produit.
Vérification de permutation inter-colonnes : HyperPlonk ne dispose pas de cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de gérer des cas de permutation de polynômes plus complexes.
Ainsi, Binius a amélioré le mécanisme PIOPSumCheck existant, augmentant la flexibilité et l'efficacité du protocole, en particulier lors du traitement de la vérification de polynômes multivariables plus complexes, offrant un meilleur support fonctionnel. Ces améliorations ont non seulement résolu les limitations de HyperPlonk, mais ont également jeté 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 l'une des technologies clés, capables de générer efficacement.