Analyse des principes de Binius STARKs et réflexion sur son optimisation
1 Introduction
Contrairement aux SNARKs basés sur les courbes elliptiques, les STARKs peuvent être considérés comme des SNARKs basés sur le hachage. Une des principales raisons de l'inefficacité actuelle des STARKs est que la plupart des valeurs 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, de nombreuses valeurs redondantes supplémentaires occupent tout le domaine lors de l'extension des données avec le codage de Reed-Solomon, 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 nombre d'espaces gaspillés. En revanche, le domaine binaire permet d'opérer directement sur les bits, offrant un codage compact et efficace sans aucun espace gaspillé, c'est-à-dire les STARKs de quatrième génération.
Tableau 1 : Chemin dérivé des STARKs
| Génération | Largeur de code | Système représentatif |
|------|----------|----------|
| 1ère génération | 252 bits | STARK |
| Deuxième génération | 64bits | Plonky2 |
| 3ème génération | 32 bits | Mina |
| 4ème génération | 1bit | Binius |
Comparé aux découvertes récentes de domaines finis comme Goldilocks, BabyBear, Mersenne31, la recherche sur les domaines binaires remonte aux années 1980. Actuellement, les domaines binaires sont largement utilisés en cryptographie, des exemples typiques incluent :
Norme de cryptage avancée ( AES ), basée sur le domaine F28
Galois Message Authentication Code ( GMAC ), basé sur le champ F2128
Code QR, utilisant le codage Reed-Solomon basé sur F28
Les protocoles FRI et zk-STARK d'origine, ainsi que la fonction de hachage Grøstl, qui a atteint la finale SHA-3, basée sur le domaine F28, est un algorithme de hachage très adapté à la récursivité.
Lorsqu'un domaine plus petit est utilisé, 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 garantir sa sécurité et sa véritable utilisabilité. La plupart des polynômes impliqués dans les calculs Prover n'ont pas besoin d'entrer dans l'extension de domaine et peuvent simplement opérer dans le domaine de base, réalisant ainsi une grande efficacité dans de petits domaines. Cependant, les vérifications de points aléatoires et les calculs FRI doivent toujours plonger dans un domaine d'extension plus grand pour garantir la sécurité requise.
Lors de la construction d'un système de preuve basé sur un domaine binaire, deux problèmes pratiques existent : 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 Merkle tree dans les STARKs, un codage de Reed-Solomon doit être effectué, et la taille du domaine utilisée doit être supérieure à la taille après l'extension du codage.
Binius a proposé une solution innovante pour traiter ces deux problèmes, en représentant les mêmes données de deux manières différentes : d'abord, en utilisant des polynômes multivariés ( spécifiquement des polynômes multilinaires ) pour remplacer les polynômes univariés, 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 d'effectuer une extension standard de Reed-Solomon comme avec les STARKs, mais il est possible de considérer l'hypercube comme un carré ), et d'effectuer l'extension de Reed-Solomon basée sur ce carré. Cette méthode améliore considérablement l'efficacité de l'encodage 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 :
Preuve oracle interactive polynomiale informationnelle (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP) : PIOP, en tant que système de preuve central, transforme la relation de calcul d'entrée en égalités polynomiales vérifiables. Différents protocoles PIOP permettent au prouveur d'envoyer progressivement des polynômes par interaction avec le vérificateur, ce qui permet à ce dernier de valider 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, qui traitent chacun les expressions polynomiales de manière différente, influençant ainsi la performance et l'efficacité de l'ensemble du système SNARK.
Schéma d'engagement polynomial (Polynomial Commitment Scheme, PCS) : Le schéma d'engagement polynomial est utilisé pour prouver si une égalité polynomial générée par PIOP est valide. Le PCS est un outil cryptographique par lequel le preneur d'engagement peut s'engager sur un certain polynôme et valider plus tard le résultat de l'évaluation de ce polynôme, tout en cachant d'autres informations sur le polynôme. Les schémas d'engagement polynomial courants incluent KZG, Bulletproofs, FRI(Fast Reed-Solomon IOPP) et Brakedown, entre autres. Différents PCS ont des performances, 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 ou une courbe elliptique appropriée, ce qui permet de construire des systèmes de preuve avec différentes propriétés. Par exemple :
• Halo2 : combinant PLONK PIOP et 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, 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, le PIOP et le PCS choisis doivent correspondre au domaine fini ou à la courbe elliptique utilisée, afin d'assurer la validité, la performance et la sécurité du système. Le choix de ces combinaisons influence 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 d'extension telles que les preuves récursives ou les 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 domaines binaires (towers of binary fields) constitue la base de ses calculs, permettant des opérations simplifiées dans le domaine binaire. Deuxièmement, Binius a adapté 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ûre 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 polynômial sur petits domaines (Small-Field PCS), permettant un système de preuve efficace dans le domaine binaire et réduisant les frais généralement associés aux grands domaines.
( 2.1 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étisation efficace. Les corps binaires soutiennent essentiellement des opérations arithmétiques très efficaces, ce qui en fait un choix idéal pour les applications cryptographiques sensibles aux performances. De plus, la structure des corps binaires soutient un processus d'arithmétisation simplifié, c'est-à-dire que les opérations effectuées sur les corps binaires peuvent être exprimées sous forme algébrique compacte et facile à vérifier. Ces caractéristiques, combinées à la capacité d'exploiter pleinement leurs caractéristiques hiérarchiques grâce à la structure en tour, rendent les corps binaires particulièrement adaptés à des systèmes de preuve évolutifs comme Binius.
Le terme "canonique" 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 de 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 de corps, alors que le corps binaire dispose de 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 ) 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'exige pas l'introduction de retenues dans les opérations d'addition et de multiplication, et que l'opération de carrée dans le corps binaire est très efficace car elle suit la règle simplifiée (X + Y )2 = X2 + Y 2.
Comme le montre 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, mais est simplement une conversion de type de la chaîne de bits (typecast), ce qui est une propriété très intéressante et utile. De plus, les éléments de petit champ peuvent être regroupés en éléments de champ plus grands sans coût de calcul supplémentaire. Le protocole Binius tire parti de cette caractéristique pour améliorer l'efficacité du calcul. En outre, le document "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité de calcul des opérations de multiplication, de mise au carré et d'inversion dans des champs binaires de tour de n bits ( décomposables en sous-champs de m bits ).
( 2.2 PIOP: version adaptée de HyperPlonk Product et PermutationCheck------ applicable au domaine binaire
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 correctitude des polynômes et des ensembles multivariés. Ces vérifications essentielles comprennent :
GateCheck : Vérifiez si le témoin secret ω et l'entrée publique x satisfont la relation d'opération du circuit C)x,ω(=0, afin de garantir le bon fonctionnement du circuit.
PermutationCheck : Vérifie si les résultats d'évaluation des deux polynômes multivariables f et g sur le cube hyperbolique booléen sont une relation de permutation f)x### = f(π)x(), afin d'assurer la cohérence des permutations entre les variables 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 trouvent dans la plage spécifiée.
MultisetCheck : Vérifie si deux ensembles multivariables sont égaux, c'est-à-dire {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, garantissant la cohérence entre plusieurs ensembles.
ProductCheck : vérifier si l'évaluation d'un polynôme rationnel sur le cube hyperbolique booléen est égale à une valeur déclarée ∏x∈Hµ f(x) = s, afin d'assurer l'exactitude du produit polynômial.
ZeroCheck : Vérifier si un polynôme à plusieurs variables est nul en un point quelconque sur l'hypercube booléen ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, afin d'assurer la distribution des zéros du polynôme.
SumCheck : Vérifie si la somme d'un polynôme multivariable est égale à la valeur déclarée ∑x∈Hµ f(x) = s. En transformant le problème d'évaluation de polynômes multivariables en évaluation de polynômes à une seule variable, cela réduit la complexité de calcul pour le vérificateur. De plus, SumCheck permet le traitement par lots en introduisant des nombres aléatoires pour construire des combinaisons linéaires, permettant ainsi 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 pour améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk présentent de nombreuses similitudes dans la conception des protocoles, Binius a amélioré les 3 aspects 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 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 nul, le ProductCheck de Binius peut continuer à traiter, permettant une généralisation à n'importe quelle valeur de produit.
Vérification de permutation intercolonnes : 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 d'arrangements polynomiaux 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 vérifications plus complexes de polynômes multivariables, offrant un support fonctionnel renforcé. Ces améliorations non seulement résolvent les limitations de HyperPlonk, mais établissent également les bases pour les systèmes de preuve futurs basés sur des domaines binaires.
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.
10 J'aime
Récompense
10
5
Partager
Commentaire
0/400
ZkSnarker
· 07-29 13:22
techniquement, les starks ne sont que des collations mais avec des hashes lmao
Voir l'originalRépondre0
PebbleHander
· 07-26 15:33
Bengbu a été occupé, il y a même des gens qui parlent de ce genre de hardcore.
Voir l'originalRépondre0
SmartContractPhobia
· 07-26 15:26
C'est encore un travail technique qui dérange les débutants.
Voir l'originalRépondre0
LootboxPhobia
· 07-26 15:23
Pas mal, on est passé de trois chiffres à deux chiffres.
Voir l'originalRépondre0
notSatoshi1971
· 07-26 15:18
Et ils pensent pouvoir dépasser snark avec ça ? Cette optimisation est vraiment trop conservatrice.
Binius STARKs : optimisation des domaines binaires et analyse des principes
Analyse des principes de Binius STARKs et réflexion sur son optimisation
1 Introduction
Contrairement aux SNARKs basés sur les courbes elliptiques, les STARKs peuvent être considérés comme des SNARKs basés sur le hachage. Une des principales raisons de l'inefficacité actuelle des STARKs est que la plupart des valeurs 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, de nombreuses valeurs redondantes supplémentaires occupent tout le domaine lors de l'extension des données avec le codage de Reed-Solomon, 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 nombre d'espaces gaspillés. En revanche, le domaine binaire permet d'opérer directement sur les bits, offrant un codage compact et efficace sans aucun espace gaspillé, c'est-à-dire les STARKs de quatrième génération.
Tableau 1 : Chemin dérivé des STARKs
| Génération | Largeur de code | Système représentatif | |------|----------|----------| | 1ère génération | 252 bits | STARK | | Deuxième génération | 64bits | Plonky2 | | 3ème génération | 32 bits | Mina | | 4ème génération | 1bit | Binius |
Comparé aux découvertes récentes de domaines finis comme Goldilocks, BabyBear, Mersenne31, la recherche sur les domaines binaires remonte aux années 1980. Actuellement, les domaines binaires sont largement utilisés en cryptographie, des exemples typiques incluent :
Lorsqu'un domaine plus petit est utilisé, 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 garantir sa sécurité et sa véritable utilisabilité. La plupart des polynômes impliqués dans les calculs Prover n'ont pas besoin d'entrer dans l'extension de domaine et peuvent simplement opérer dans le domaine de base, réalisant ainsi une grande efficacité dans de petits domaines. Cependant, les vérifications de points aléatoires et les calculs FRI doivent toujours plonger dans un domaine d'extension plus grand pour garantir la sécurité requise.
Lors de la construction d'un système de preuve basé sur un domaine binaire, deux problèmes pratiques existent : 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 Merkle tree dans les STARKs, un codage de Reed-Solomon doit être effectué, et la taille du domaine utilisée doit être supérieure à la taille après l'extension du codage.
Binius a proposé une solution innovante pour traiter ces deux problèmes, en représentant les mêmes données de deux manières différentes : d'abord, en utilisant des polynômes multivariés ( spécifiquement des polynômes multilinaires ) pour remplacer les polynômes univariés, 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 d'effectuer une extension standard de Reed-Solomon comme avec les STARKs, mais il est possible de considérer l'hypercube comme un carré ), et d'effectuer l'extension de Reed-Solomon basée sur ce carré. Cette méthode améliore considérablement l'efficacité de l'encodage 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 :
Preuve oracle interactive polynomiale informationnelle (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP) : PIOP, en tant que système de preuve central, transforme la relation de calcul d'entrée en égalités polynomiales vérifiables. Différents protocoles PIOP permettent au prouveur d'envoyer progressivement des polynômes par interaction avec le vérificateur, ce qui permet à ce dernier de valider 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, qui traitent chacun les expressions polynomiales de manière différente, influençant ainsi la performance et l'efficacité de l'ensemble du système SNARK.
Schéma d'engagement polynomial (Polynomial Commitment Scheme, PCS) : Le schéma d'engagement polynomial est utilisé pour prouver si une égalité polynomial générée par PIOP est valide. Le PCS est un outil cryptographique par lequel le preneur d'engagement peut s'engager sur un certain polynôme et valider plus tard le résultat de l'évaluation de ce polynôme, tout en cachant d'autres informations sur le polynôme. Les schémas d'engagement polynomial courants incluent KZG, Bulletproofs, FRI(Fast Reed-Solomon IOPP) et Brakedown, entre autres. Différents PCS ont des performances, 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 ou une courbe elliptique appropriée, ce qui permet de construire des systèmes de preuve avec différentes propriétés. Par exemple :
• Halo2 : combinant PLONK PIOP et 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, 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, le PIOP et le PCS choisis doivent correspondre au domaine fini ou à la courbe elliptique utilisée, afin d'assurer la validité, la performance et la sécurité du système. Le choix de ces combinaisons influence 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 d'extension telles que les preuves récursives ou les 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 domaines binaires (towers of binary fields) constitue la base de ses calculs, permettant des opérations simplifiées dans le domaine binaire. Deuxièmement, Binius a adapté 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ûre 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 polynômial sur petits domaines (Small-Field PCS), permettant un système de preuve efficace dans le domaine binaire et réduisant les frais généralement associés aux grands domaines.
( 2.1 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étisation efficace. Les corps binaires soutiennent essentiellement des opérations arithmétiques très efficaces, ce qui en fait un choix idéal pour les applications cryptographiques sensibles aux performances. De plus, la structure des corps binaires soutient un processus d'arithmétisation simplifié, c'est-à-dire que les opérations effectuées sur les corps binaires peuvent être exprimées sous forme algébrique compacte et facile à vérifier. Ces caractéristiques, combinées à la capacité d'exploiter pleinement leurs caractéristiques hiérarchiques grâce à la structure en tour, rendent les corps binaires particulièrement adaptés à des systèmes de preuve évolutifs comme Binius.
Le terme "canonique" 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 de 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 de corps, alors que le corps binaire dispose de 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 ) 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'exige pas l'introduction de retenues dans les opérations d'addition et de multiplication, et que l'opération de carrée dans le corps binaire est très efficace car elle suit la règle simplifiée (X + Y )2 = X2 + Y 2.
Comme le montre 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, mais est simplement une conversion de type de la chaîne de bits (typecast), ce qui est une propriété très intéressante et utile. De plus, les éléments de petit champ peuvent être regroupés en éléments de champ plus grands sans coût de calcul supplémentaire. Le protocole Binius tire parti de cette caractéristique pour améliorer l'efficacité du calcul. En outre, le document "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité de calcul des opérations de multiplication, de mise au carré et d'inversion dans des champs binaires de tour de n bits ( décomposables en sous-champs de m bits ).
( 2.2 PIOP: version adaptée de HyperPlonk Product et PermutationCheck------ applicable au domaine binaire
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 correctitude des polynômes et des ensembles multivariés. Ces vérifications essentielles comprennent :
GateCheck : Vérifiez si le témoin secret ω et l'entrée publique x satisfont la relation d'opération du circuit C)x,ω(=0, afin de garantir le bon fonctionnement du circuit.
PermutationCheck : Vérifie si les résultats d'évaluation des deux polynômes multivariables f et g sur le cube hyperbolique booléen sont une relation de permutation f)x### = f(π)x(), afin d'assurer la cohérence des permutations entre les variables 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 trouvent dans la plage spécifiée.
MultisetCheck : Vérifie si deux ensembles multivariables sont égaux, c'est-à-dire {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, garantissant la cohérence entre plusieurs ensembles.
ProductCheck : vérifier si l'évaluation d'un polynôme rationnel sur le cube hyperbolique booléen est égale à une valeur déclarée ∏x∈Hµ f(x) = s, afin d'assurer l'exactitude du produit polynômial.
ZeroCheck : Vérifier si un polynôme à plusieurs variables est nul en un point quelconque sur l'hypercube booléen ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, afin d'assurer la distribution des zéros du polynôme.
SumCheck : Vérifie si la somme d'un polynôme multivariable est égale à la valeur déclarée ∑x∈Hµ f(x) = s. En transformant le problème d'évaluation de polynômes multivariables en évaluation de polynômes à une seule variable, cela réduit la complexité de calcul pour le vérificateur. De plus, SumCheck permet le traitement par lots en introduisant des nombres aléatoires pour construire des combinaisons linéaires, permettant ainsi 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 pour améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk présentent de nombreuses similitudes dans la conception des protocoles, Binius a amélioré les 3 aspects 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 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 nul, le ProductCheck de Binius peut continuer à traiter, permettant une généralisation à n'importe quelle valeur de produit.
Vérification de permutation intercolonnes : 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 d'arrangements polynomiaux 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 vérifications plus complexes de polynômes multivariables, offrant un support fonctionnel renforcé. Ces améliorations non seulement résolvent les limitations de HyperPlonk, mais établissent également les bases pour les systèmes de preuve futurs basés sur des domaines binaires.