Analyse des principes des STARKs Binius et réflexion sur leur optimisation
1 Introduction
Une des principales raisons de l'inefficacité des STARKs est que la plupart des valeurs numériques dans les programmes réels sont assez 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 l'occupation de nombreux valeurs redondantes dans tout le domaine, même si la valeur originale elle-même est très petite. Pour résoudre ce problème, réduire la taille du domaine est devenu une stratégie clé.
Comme indiqué dans le tableau 1, la largeur de code des STARKs de première génération est de 252 bits, celle des STARKs de deuxième génération est de 64 bits, et celle des STARKs de troisième génération est de 32 bits, mais la largeur de code de 32 bits présente encore un grand espace gaspillé. En comparaison, le domaine binaire permet d'opérer directement sur les bits, rendant le codage compact et efficace sans aucun espace de gaspillage, c'est-à-dire les STARKs de quatrième génération.
Comparé aux découvertes récentes sur les corps finis comme Goldilocks, BabyBear et Mersenne31, la recherche sur les corps binaires remonte aux années 1980. À l'heure actuelle, les corps binaires sont largement utilisés en cryptographie, des exemples typiques incluent :
Norme de cryptage avancé ( AES ), basé sur le domaine F28;
Code d'authentification de message Galois ( GMAC ), basé sur le champ F2128;
QR code, utilisant le codage Reed-Solomon basé sur F28;
Le protocole FRI d'origine et le protocole zk-STARK, ainsi que la fonction de hachage Grøstl qui est entrée dans la finale SHA-3, qui est basée sur le domaine F28, sont un algorithme de hachage très adapté à la récursivité.
Lorsqu'on utilise un domaine plus petit, 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 des Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais doivent simplement opérer sous le domaine de base, réalisant ainsi une haute efficacité dans le 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 des domaines binaires, il existe 2 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 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 extension du codage.
Binius a proposé une solution innovante qui traite ces deux problèmes, en représentant les mêmes données de deux manières différentes : tout d'abord, en utilisant des polynômes multivariés ( au lieu de polynômes univariés, en représentant l'ensemble de la trajectoire de calcul par ses valeurs sur les hypercubes ) ; ensuite, comme la longueur de chaque dimension de l'hypercube est de 2, il n'est pas possible d'effectuer une extension standard de Reed-Solomon comme pour les STARKs, mais on peut considérer l'hypercube comme un carré (, sur lequel on base l'extension de Reed-Solomon. Cette méthode améliore considérablement l'efficacité du codage et les performances 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 :
Information-Theoretic Polynomial Interactive Oracle Proof, PIOP) : PIOP en tant que système de preuve 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, permettant ainsi à celui-ci de 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, influençant ainsi les performances 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. PCS est un outil cryptographique qui permet à un prouveur de s'engager à un certain polynôme et de vérifier ultérieurement les résultats d'é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 variés.
En fonction des besoins spécifiques, choisissez différents PIOP et PCS, et combinez-les avec un domaine fini approprié ou une courbe elliptique, il est possible de 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 avec un accent sur l'évolutivité et l'élimination de la configuration de confiance dans le protocole ZCash.
• Plonky2 : combine PLONK PIOP et FRI PCS, et est basé sur le domaine 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 corps fini ou à la courbe elliptique utilisés, afin d'assurer la validité, la performance et la sécurité du système. Le choix de ces combinaisons affecte non seulement la taille des preuves SNARK et l'efficacité de la vérification, mais détermine également si le système peut atteindre la transparence sans configuration de confiance préalable, et s'il peut prendre en charge des fonctionnalités d'extension telles que des preuves récursives ou des preuves agrégées.
Binius: HyperPlonk PIOP + Brakedown PCS + domaines binaires. Plus précisément, Binius comprend cinq technologies clés pour réaliser son efficacité et sa sécurité. Tout d'abord, l'arithmétique basée sur les tours de champs binaires (towers of binary fields) constitue la base de ses calculs, 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 une vérification cohérente, sécurisée et efficace des variables et de 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 champs. 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 champs (Small-Field PCS), lui permettant de réaliser un système de preuve efficace sur le champ binaire, et réduisant les frais généralement associés aux grands champs.
( 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 vérifiables rapides, principalement en raison de deux aspects : des calculs efficaces et une arithmétisation efficace. Les corps binaires soutiennent essentiellement des opérations arithmétiques hautement efficaces, ce qui en fait un choix idéal pour les applications cryptographiques sensibles aux performances. De plus, la structure 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, combinées à la capacité d'exploiter pleinement les 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.
Dans ce contexte, "canonical" fait référence à la représentation unique et directe des éléments dans un corps binaire. Par exemple, dans le corps binaire F2 le plus fondamental, 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, toutes les chaînes de 32 bits ne peuvent pas correspondre de manière unique à un élément du corps, tandis que le corps binaire offre cette commodité d'un mappage 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 ) utilisée dans AES, la réduction de Montgomery ( 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" souligne que le corps binaire n'introduit pas de retenue dans les opérations d'addition et de multiplication, et que l'opération d'exponentiation dans le corps binaire est très efficace, car elle suit la règle simplifiée (X + Y )2 = X2 + Y 2.
Comme montré 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 champs binaires. Elle peut être considérée comme un élément unique dans un champ binaire de 128 bits, ou être décomposée en deux éléments de champ de 64 bits, quatre éléments de champ de 32 bits, seize éléments de champ de 8 bits, ou 128 éléments de champ F2. Cette flexibilité de représentation ne nécessite aucun coût de calcul, juste une conversion de type de chaîne de bits (typecast), ce qui est une propriété très intéressante et utile. En outre, les éléments de petits champs peuvent être regroupés en éléments de champs 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. De plus, le document "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité de calcul des opérations de multiplication, d'élévation au carré et d'inversion dans un champ binaire de n bits ( décomposé en un sous-champ 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 clés pour valider la justesse des polynômes et des ensembles multivariés. Ces vérifications clés comprennent :
GateCheck : vérifier si le témoin secret ω et l'entrée publique x satisfont la relation d'opération du circuit C)x,ω(=0, afin d'assurer le bon fonctionnement du circuit.
PermutationCheck : Vérifier si les résultats d'évaluation des deux polynômes multivariés 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 des polynômes.
LookupCheck : Vérifiez si l'évaluation du polynôme se trouve dans la table de recherche donnée, c'est-à-dire f(Bµ) ⊆ T(Bµ(, assurez-vous que certaines valeurs se situent dans la plage spécifiée.
MultisetCheck : Vé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 l'hypercube booléen est égale à une certaine valeur déclarée ∏x∈Hµ f(x) = s, afin de garantir l'exactitude du produit polynomial.
ZeroCheck : vérifier si un polynôme multivarié 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 multivariable est égale à la valeur déclarée ∑x∈Hµ f(x) = s. En transformant le problème d'évaluation d'un polynôme multivarié en un problème d'évaluation d'un polynôme à variable unique, 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, ce qui permet de traiter plusieurs instances de vérification de somme.
BatchCheck : basé sur SumCheck, vérifie la validité des évaluations de plusieurs polynômes multivariables afin d'améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk présentent de nombreuses similitudes dans la conception du protocole, 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.
Traitement du problème de division par zéro : HyperPlonk n'a pas réussi à traiter correctement les cas de division par zéro, ce qui 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 de généraliser à n'importe quelle valeur de produit.
Vérification de permutation inter-colonnes : HyperPlonk ne prend pas en charge 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 polynomiale plus complexes.
Ainsi, Binius a amélioré le mécanisme PIOPSumCheck existant, augmentant la flexibilité et l'efficacité du protocole, en particulier dans le traitement de la vérification de polynômes multivariés plus complexes, offrant un soutien fonctionnel plus fort. Ces améliorations non seulement résolvent les limitations de HyperPlonk, mais jettent également les bases pour les futurs systèmes de preuve basés sur des domaines binaires.
( 2.3 PIOP : nouvel argument de décalage multilinéraire ------ applicable à l'hypercube booléen
Dans le protocole Binius, virtuel
Voir l'original
Cette page peut inclure du contenu de tiers fourni à des fins d'information uniquement. Gate ne garantit ni l'exactitude ni la validité de ces contenus, n’endosse pas les opinions exprimées, et ne fournit aucun conseil financier ou professionnel à travers ces informations. Voir la section Avertissement pour plus de détails.
15 J'aime
Récompense
15
5
Partager
Commentaire
0/400
AirdropHunter007
· 07-21 14:04
Combien de laine peut-on tirer de cela ?
Voir l'originalRépondre0
GateUser-3824aa38
· 07-20 17:31
C'est déjà trop avec 32 chiffres, c'est assez compétitif.
Voir l'originalRépondre0
SchroedingerGas
· 07-20 17:30
Les frais de gas sont vraiment trop abstraits ! Qui comprend ça ?
Voir l'originalRépondre0
WhaleWatcher
· 07-20 17:23
Optimisation de domaine, bull. Notre cercle aurait dû être changé depuis longtemps.
Voir l'originalRépondre0
MechanicalMartel
· 07-20 17:08
stark est trop lourd, non ? Quand pourra-t-il être plus rapide ?
Analyse du protocole Binius : Optimisation et innovation des STARKs dans le domaine binaire
Analyse des principes des STARKs Binius et réflexion sur leur optimisation
1 Introduction
Une des principales raisons de l'inefficacité des STARKs est que la plupart des valeurs numériques dans les programmes réels sont assez 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 l'occupation de nombreux valeurs redondantes dans tout le domaine, même si la valeur originale elle-même est très petite. Pour résoudre ce problème, réduire la taille du domaine est devenu une stratégie clé.
Comme indiqué dans le tableau 1, la largeur de code des STARKs de première génération est de 252 bits, celle des STARKs de deuxième génération est de 64 bits, et celle des STARKs de troisième génération est de 32 bits, mais la largeur de code de 32 bits présente encore un grand espace gaspillé. En comparaison, le domaine binaire permet d'opérer directement sur les bits, rendant le codage compact et efficace sans aucun espace de gaspillage, c'est-à-dire les STARKs de quatrième génération.
Tableau 1: Chemin de dérivation des STARKs
| Algèbre | Largeur de code | Système représentatif | |------|----------|----------| | 1ère génération | 252bit | StarkWare | | 2ème génération | 64 bits | Plonky2 | | 3ème génération | 32 bits | Polygon zkEVM | | 4ème génération | 1bit | Binius |
Comparé aux découvertes récentes sur les corps finis comme Goldilocks, BabyBear et Mersenne31, la recherche sur les corps binaires remonte aux années 1980. À l'heure actuelle, les corps binaires sont largement utilisés en cryptographie, des exemples typiques incluent :
Norme de cryptage avancé ( AES ), basé sur le domaine F28;
Code d'authentification de message Galois ( GMAC ), basé sur le champ F2128;
QR code, utilisant le codage Reed-Solomon basé sur F28;
Le protocole FRI d'origine et le protocole zk-STARK, ainsi que la fonction de hachage Grøstl qui est entrée dans la finale SHA-3, qui est basée sur le domaine F28, sont un algorithme de hachage très adapté à la récursivité.
Lorsqu'on utilise un domaine plus petit, 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 des Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais doivent simplement opérer sous le domaine de base, réalisant ainsi une haute efficacité dans le 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 des domaines binaires, il existe 2 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 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 extension du codage.
Binius a proposé une solution innovante qui traite ces deux problèmes, en représentant les mêmes données de deux manières différentes : tout d'abord, en utilisant des polynômes multivariés ( au lieu de polynômes univariés, en représentant l'ensemble de la trajectoire de calcul par ses valeurs sur les hypercubes ) ; ensuite, comme la longueur de chaque dimension de l'hypercube est de 2, il n'est pas possible d'effectuer une extension standard de Reed-Solomon comme pour les STARKs, mais on peut considérer l'hypercube comme un carré (, sur lequel on base l'extension de Reed-Solomon. Cette méthode améliore considérablement l'efficacité du codage et les performances 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 :
Information-Theoretic Polynomial Interactive Oracle Proof, PIOP) : PIOP en tant que système de preuve 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, permettant ainsi à celui-ci de 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, influençant ainsi les performances 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. PCS est un outil cryptographique qui permet à un prouveur de s'engager à un certain polynôme et de vérifier ultérieurement les résultats d'é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 variés.
En fonction des besoins spécifiques, choisissez différents PIOP et PCS, et combinez-les avec un domaine fini approprié ou une courbe elliptique, il est possible de 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 avec un accent sur l'évolutivité et l'élimination de la configuration de confiance dans le protocole ZCash.
• Plonky2 : combine PLONK PIOP et FRI PCS, et est basé sur le domaine 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 corps fini ou à la courbe elliptique utilisés, afin d'assurer la validité, la performance et la sécurité du système. Le choix de ces combinaisons affecte non seulement la taille des preuves SNARK et l'efficacité de la vérification, mais détermine également si le système peut atteindre la transparence sans configuration de confiance préalable, et s'il peut prendre en charge des fonctionnalités d'extension telles que des preuves récursives ou des preuves agrégées.
Binius: HyperPlonk PIOP + Brakedown PCS + domaines binaires. Plus précisément, Binius comprend cinq technologies clés pour réaliser son efficacité et sa sécurité. Tout d'abord, l'arithmétique basée sur les tours de champs binaires (towers of binary fields) constitue la base de ses calculs, 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 une vérification cohérente, sécurisée et efficace des variables et de 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 champs. 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 champs (Small-Field PCS), lui permettant de réaliser un système de preuve efficace sur le champ binaire, et réduisant les frais généralement associés aux grands champs.
( 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 vérifiables rapides, principalement en raison de deux aspects : des calculs efficaces et une arithmétisation efficace. Les corps binaires soutiennent essentiellement des opérations arithmétiques hautement efficaces, ce qui en fait un choix idéal pour les applications cryptographiques sensibles aux performances. De plus, la structure 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, combinées à la capacité d'exploiter pleinement les 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.
Dans ce contexte, "canonical" fait référence à la représentation unique et directe des éléments dans un corps binaire. Par exemple, dans le corps binaire F2 le plus fondamental, 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, toutes les chaînes de 32 bits ne peuvent pas correspondre de manière unique à un élément du corps, tandis que le corps binaire offre cette commodité d'un mappage 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 ) utilisée dans AES, la réduction de Montgomery ( 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" souligne que le corps binaire n'introduit pas de retenue dans les opérations d'addition et de multiplication, et que l'opération d'exponentiation dans le corps binaire est très efficace, car elle suit la règle simplifiée (X + Y )2 = X2 + Y 2.
Comme montré 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 champs binaires. Elle peut être considérée comme un élément unique dans un champ binaire de 128 bits, ou être décomposée en deux éléments de champ de 64 bits, quatre éléments de champ de 32 bits, seize éléments de champ de 8 bits, ou 128 éléments de champ F2. Cette flexibilité de représentation ne nécessite aucun coût de calcul, juste une conversion de type de chaîne de bits (typecast), ce qui est une propriété très intéressante et utile. En outre, les éléments de petits champs peuvent être regroupés en éléments de champs 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. De plus, le document "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité de calcul des opérations de multiplication, d'élévation au carré et d'inversion dans un champ binaire de n bits ( décomposé en un sous-champ 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 clés pour valider la justesse des polynômes et des ensembles multivariés. Ces vérifications clés comprennent :
GateCheck : vérifier si le témoin secret ω et l'entrée publique x satisfont la relation d'opération du circuit C)x,ω(=0, afin d'assurer le bon fonctionnement du circuit.
PermutationCheck : Vérifier si les résultats d'évaluation des deux polynômes multivariés 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 des polynômes.
LookupCheck : Vérifiez si l'évaluation du polynôme se trouve dans la table de recherche donnée, c'est-à-dire f(Bµ) ⊆ T(Bµ(, assurez-vous que certaines valeurs se situent dans la plage spécifiée.
MultisetCheck : Vé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 l'hypercube booléen est égale à une certaine valeur déclarée ∏x∈Hµ f(x) = s, afin de garantir l'exactitude du produit polynomial.
ZeroCheck : vérifier si un polynôme multivarié 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 multivariable est égale à la valeur déclarée ∑x∈Hµ f(x) = s. En transformant le problème d'évaluation d'un polynôme multivarié en un problème d'évaluation d'un polynôme à variable unique, 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, ce qui permet de traiter plusieurs instances de vérification de somme.
BatchCheck : basé sur SumCheck, vérifie la validité des évaluations de plusieurs polynômes multivariables afin d'améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk présentent de nombreuses similitudes dans la conception du protocole, 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.
Traitement du problème de division par zéro : HyperPlonk n'a pas réussi à traiter correctement les cas de division par zéro, ce qui 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 de généraliser à n'importe quelle valeur de produit.
Vérification de permutation inter-colonnes : HyperPlonk ne prend pas en charge 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 polynomiale plus complexes.
Ainsi, Binius a amélioré le mécanisme PIOPSumCheck existant, augmentant la flexibilité et l'efficacité du protocole, en particulier dans le traitement de la vérification de polynômes multivariés plus complexes, offrant un soutien fonctionnel plus fort. Ces améliorations non seulement résolvent les limitations de HyperPlonk, mais jettent également les bases pour les futurs systèmes de preuve basés sur des domaines binaires.
( 2.3 PIOP : nouvel argument de décalage multilinéraire ------ applicable à l'hypercube booléen
Dans le protocole Binius, virtuel