Analyse des principes STARKs de Binius et réflexion sur leurs optimisations
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 relativement petites, comme les index dans les boucles for, les valeurs booléennes, les compteurs, etc. Cependant, pour garantir la sécurité des preuves basées sur les arbres de Merkle, l'utilisation du codage Reed-Solomon pour étendre les données entraîne l'occupation de nombreux valeurs redondantes 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é.
La largeur des codes STARKs de première génération est de 252 bits, celle de la deuxième génération est de 64 bits, et celle de la 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, avec un encodage compact et efficace sans espace gaspillé, c'est-à-dire les STARKs de quatrième génération.
Comparé aux découvertes récentes des corps finis comme Goldilocks, BabyBear et Mersenne31, les recherches sur les corps binaires remontent aux années 1980. Actuellement, les corps binaires sont largement utilisés en cryptographie, des exemples typiques incluent :
Norme de cryptage avancé (AES), basé sur le domaine F28 ;
Galois code d'authentification de message ( GMAC ), basé sur le domaine F2128;
Code QR, utilisant le codage Reed-Solomon basé sur F28 ;
Le protocole FRI original et le protocole zk-STARK, ainsi que la fonction de hachage Grøstl qui a atteint la finale de SHA-3, basée sur le domaine F28, sont un algorithme de hachage très adapté à la récursivité.
Lorsque des domaines plus petits sont utilisés, l'opération d'extension de domaine devient de plus en plus importante pour garantir la sécurité. Le domaine binaire utilisé par Binius doit entièrement dépendre de l'extension de domaine pour assurer sa sécurité et sa praticité. La plupart des polynômes impliqués dans les calculs des Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais doivent simplement fonctionner sous le domaine de base, permettant ainsi d'atteindre une grande efficacité dans de petits domaines. Cependant, les vérifications de points aléatoires et les calculs FRI doivent encore plonger dans un domaine d'extension plus grand pour garantir la sécurité requise.
Lors de la construction d'un système de preuve basé sur un domaine binaire, il existe 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, 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 séparément et réalise la représentation des mêmes données de deux manières différentes : d'abord, en utilisant des polynômes multivariés (plus précisément des polynômes multilinaires) au lieu de polynômes univariés, en représentant l'ensemble de la trajectoire de calcul par ses valeurs dans des "hypercubes" ; ensuite, étant donné que la longueur de chaque dimension de l'hypercube est de 2, il n'est pas possible de faire une extension de Reed-Solomon standard comme avec les STARKs, mais l'hypercube peut être considéré comme un carré, permettant d'effectuer une extension de Reed-Solomon basée sur ce carré. Cette méthode améliore considérablement l'efficacité du codage et la performance de calcul tout en garantissant la sécurité.
2 Analyse des principes
La construction de la plupart des systèmes SNARKs actuels comprend généralement les deux parties suivantes :
Preuve d'Oracle Interactif Polynomiale d'Information Théorique (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP) : Le PIOP, en tant que système de preuve central, transforme les relations de calcul d'entrée en égalités polynomiales vérifiables. Différents protocoles PIOP interagissent avec le vérificateur, permettant au prouveur d'envoyer progressivement des polynômes, de sorte que le vérificateur puisse vérifier si le calcul est correct en interrogeant un nombre limité de résultats d'évaluation de polynômes. Les protocoles PIOP existants incluent : PLONK PIOP, Spartan PIOP et HyperPlonk PIOP, qui traitent chacun les expressions polynomiales de manière différente, 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. Le PCS est un outil cryptographique qui permet à un prouveur de s'engager sur 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 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 variés.
Selon les besoins spécifiques, choisissez différents PIOP et PCS, et combinez-les avec un champ fini ou une courbe elliptique appropriée, pour construire des systèmes de preuve ayant 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 en éliminant la configuration de confiance dans le protocole ZCash.
• Plonky2 : utilisant PLONK PIOP et FRI PCS combinés, basés sur le domaine Goldilocks. Plonky2 a été 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 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 atteindre 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 constitue la base de son calcul, permettant d'effectuer des opérations simplifiées dans le domaine binaire. Deuxièmement, Binius a adapté les vérifications de produit et de permutation de HyperPlonk dans son protocole de preuve Oracle interactif (PIOP), garantissant une vérification de cohérence sécurisée et efficace entre les variables et leurs permutations. Troisièmement, le protocole introduit une nouvelle preuve de décalage multilinéraire, optimisant l'efficacité de la validation 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é forte pour le mécanisme de recherche. Enfin, le protocole utilise un schéma d'engagement de polynômes de petits domaines (Small-Field PCS), lui permettant de réaliser un système de preuves efficace dans le domaine binaire et réduisant les frais généralement associés aux grands domaines.
2.1 Corps finis : arithmétique basée sur les tours de corps binaires
Le domaine binaire en tour est la clé pour réaliser des calculs vérifiables rapides, principalement en raison de deux aspects : le calcul efficace et l'arithmétique efficace. Le domaine binaire prend en charge des opérations arithmétiques hautement efficaces, ce qui en fait un choix idéal pour les applications cryptographiques sensibles aux exigences de performance. De plus, la structure du domaine binaire soutient un processus d'arithmétisation simplifié, c'est-à-dire que les opérations effectuées sur le domaine 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, font du domaine binaire un choix particulièrement adapté pour des systèmes de preuve évolutifs tels que Binius.
Le terme "canonical" désigne la représentation unique et directe d'un élément dans le domaine binaire. Par exemple, dans le domaine binaire de base F2, toute chaîne de k bits peut être directement mappée à un élément du domaine binaire de k bits. Cela diffère des domaines premiers, qui ne peuvent pas fournir cette représentation canonique dans un nombre de bits donné. Bien qu'un domaine premier de 32 bits puisse être contenu dans 32 bits, ce n'est pas le cas pour chaque chaîne de 32 bits qui peut être associée de manière unique à un élément du domaine, alors que le domaine binaire offre cette commodité de mappage un à un. Dans le domaine premier Fp, les méthodes de réduction courantes incluent la réduction de Barrett, la réduction de Montgomery, ainsi que des méthodes de réduction spéciales pour des domaines finis spécifiques comme Mersenne-31 ou Goldilocks-64. Dans le domaine binaire F2k, les méthodes de réduction couramment utilisées comprennent la réduction spéciale (comme celle utilisée dans AES), la réduction de Montgomery (comme celle 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 domaine binaire ne nécessite pas l'introduction de retenue dans les opérations d'addition et de multiplication, et que l'opération de carré dans le domaine binaire est très efficace, car elle suit la règle simplifiée (X + Y )2 = X2 + Y 2.
Comme 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 analysée comme deux éléments de domaine de tour de 64 bits, quatre éléments de domaine de tour de 32 bits, seize éléments de domaine de tour de 8 bits, ou 128 éléments de domaine F2. Cette flexibilité de représentation ne nécessite aucun coût de calcul, juste une conversion de type de la chaîne de bits, ce qui est une propriété très intéressante et utile. De plus, les éléments de petit domaine peuvent être emballé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, d'élévation au carré et d'inversion dans les domaines binaires à tour de n bits (décomposables en sous-domaines de m bits).
2.2 PIOP : version adaptée de HyperPlonk Product et PermutationCheck ------ applicable aux domaines binaires
Le design 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 correctitude des polynômes et des ensembles multivariables. Ces vérifications clés comprennent :
GateCheck : vérifie si le témoin secret ω et l'entrée publique x satisfont la relation de calcul du circuit C(x,ω)=0, afin d'assurer le bon fonctionnement du circuit.
PermutationCheck : Vérifie si les résultats d'évaluation de deux polynômes multivariés f et g sur le cube hyperbolique booléen forment une relation de permutation f(x) = f(π(x)), afin d'assurer la cohérence des permutations entre les variables du polynôme.
LookupCheck : vérifie si l'évaluation du polynôme se trouve dans la table de recherche donnée, c'est-à-dire f(Bµ) ⊆ T(Bµ), en s'assurant 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érifier si l'évaluation d'un polynôme à coefficients rationnels sur le cube hyperbolique booléen est égale à une valeur déclarée ∏x∈Hµ f(x) = s, afin de garantir la validité du produit polynomial.
ZeroCheck : vérifier si un polynôme multivariable à 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 de l'évaluation de polynômes multivariables en un problème d'é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, réalisant ainsi le traitement par lots de plusieurs instances de vérification de sommes.
BatchCheck : basé sur SumCheck, vérifie la validité de l'évaluation de plusieurs polynômes multivariés pour améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk aient 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 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 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 généralisation à n'importe quelle valeur de produit.
Vérification de permutation inter-colonnes : HyperPlonk n'a pas cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de gérer des cas de permutation de polynômes plus complexes.
Ainsi, Binius a amélioré la flexibilité et l'efficacité du protocole grâce à une amélioration du mécanisme PIOPSumCheck existant, offrant un support fonctionnel plus puissant, en particulier lors du traitement de vérifications de polynômes multivariables plus complexes. Ces améliorations ont non seulement résolu les limitations de HyperPlonk, mais ont également jeté 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 au hypercube booléen
Dans le protocole Binius, la construction et le traitement des polynômes virtuels sont l'une des technologies clés, permettant de générer et d'opérer efficacement des polynômes dérivés de poignées d'entrée ou d'autres polynômes virtuels. Voici deux méthodes clés :
Emballage :
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.
13 J'aime
Récompense
13
8
Partager
Commentaire
0/400
StableGeniusDegen
· 07-23 00:04
On ne peut pas suivre si ça va trop loin.
Voir l'originalRépondre0
LiquiditySurfer
· 07-21 04:57
C'est trop gaspillé, ça fait trois générations que c'est comme ça.
Voir l'originalRépondre0
RetailTherapist
· 07-20 05:05
C'est vraiment trop compliqué, non ?
Voir l'originalRépondre0
CryptoSourGrape
· 07-20 00:28
Si j'avais étudié tout cela au lieu de rester inactif... Sigh, plus je regarde, plus je suis amer.
Voir l'originalRépondre0
gas_fee_therapist
· 07-20 00:24
Réduire la largeur de bande de moitié, c'est vraiment pour réduire les coûts et améliorer l'efficacité, n'est-ce pas ?
Voir l'originalRépondre0
ImpermanentLossEnjoyer
· 07-20 00:20
32 bits va encore être critiqué.
Voir l'originalRépondre0
MEVHunter
· 07-20 00:19
heh, un autre protocole inefficace prêt à être exploité... les astuces de champ binaire ne te sauveront pas des requins du mempool
Voir l'originalRépondre0
MEV_Whisperer
· 07-20 00:14
L'optimisation n'est pas terminée, 32 bits gaspillent encore trop d'espace.
Binius Innovation : Analyse approfondie de l'optimisation des domaines binaires STARKs
Analyse des principes STARKs de Binius et réflexion sur leurs optimisations
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 relativement petites, comme les index dans les boucles for, les valeurs booléennes, les compteurs, etc. Cependant, pour garantir la sécurité des preuves basées sur les arbres de Merkle, l'utilisation du codage Reed-Solomon pour étendre les données entraîne l'occupation de nombreux valeurs redondantes 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é.
La largeur des codes STARKs de première génération est de 252 bits, celle de la deuxième génération est de 64 bits, et celle de la 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, avec un encodage compact et efficace sans espace gaspillé, c'est-à-dire les STARKs de quatrième génération.
Comparé aux découvertes récentes des corps finis comme Goldilocks, BabyBear et Mersenne31, les recherches sur les corps binaires remontent aux années 1980. Actuellement, les corps binaires sont largement utilisés en cryptographie, des exemples typiques incluent :
Norme de cryptage avancé (AES), basé sur le domaine F28 ;
Galois code d'authentification de message ( GMAC ), basé sur le domaine F2128;
Code QR, utilisant le codage Reed-Solomon basé sur F28 ;
Le protocole FRI original et le protocole zk-STARK, ainsi que la fonction de hachage Grøstl qui a atteint la finale de SHA-3, basée sur le domaine F28, sont un algorithme de hachage très adapté à la récursivité.
Lorsque des domaines plus petits sont utilisés, l'opération d'extension de domaine devient de plus en plus importante pour garantir la sécurité. Le domaine binaire utilisé par Binius doit entièrement dépendre de l'extension de domaine pour assurer sa sécurité et sa praticité. La plupart des polynômes impliqués dans les calculs des Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais doivent simplement fonctionner sous le domaine de base, permettant ainsi d'atteindre une grande efficacité dans de petits domaines. Cependant, les vérifications de points aléatoires et les calculs FRI doivent encore plonger dans un domaine d'extension plus grand pour garantir la sécurité requise.
Lors de la construction d'un système de preuve basé sur un domaine binaire, il existe 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, 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 séparément et réalise la représentation des mêmes données de deux manières différentes : d'abord, en utilisant des polynômes multivariés (plus précisément des polynômes multilinaires) au lieu de polynômes univariés, en représentant l'ensemble de la trajectoire de calcul par ses valeurs dans des "hypercubes" ; ensuite, étant donné que la longueur de chaque dimension de l'hypercube est de 2, il n'est pas possible de faire une extension de Reed-Solomon standard comme avec les STARKs, mais l'hypercube peut être considéré comme un carré, permettant d'effectuer une extension de Reed-Solomon basée sur ce carré. Cette méthode améliore considérablement l'efficacité du codage et la performance de calcul tout en garantissant la sécurité.
2 Analyse des principes
La construction de la plupart des systèmes SNARKs actuels comprend généralement les deux parties suivantes :
Preuve d'Oracle Interactif Polynomiale d'Information Théorique (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP) : Le PIOP, en tant que système de preuve central, transforme les relations de calcul d'entrée en égalités polynomiales vérifiables. Différents protocoles PIOP interagissent avec le vérificateur, permettant au prouveur d'envoyer progressivement des polynômes, de sorte que le vérificateur puisse vérifier si le calcul est correct en interrogeant un nombre limité de résultats d'évaluation de polynômes. Les protocoles PIOP existants incluent : PLONK PIOP, Spartan PIOP et HyperPlonk PIOP, qui traitent chacun les expressions polynomiales de manière différente, 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. Le PCS est un outil cryptographique qui permet à un prouveur de s'engager sur 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 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 variés.
Selon les besoins spécifiques, choisissez différents PIOP et PCS, et combinez-les avec un champ fini ou une courbe elliptique appropriée, pour construire des systèmes de preuve ayant 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 en éliminant la configuration de confiance dans le protocole ZCash.
• Plonky2 : utilisant PLONK PIOP et FRI PCS combinés, basés sur le domaine Goldilocks. Plonky2 a été 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 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 atteindre 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 constitue la base de son calcul, permettant d'effectuer des opérations simplifiées dans le domaine binaire. Deuxièmement, Binius a adapté les vérifications de produit et de permutation de HyperPlonk dans son protocole de preuve Oracle interactif (PIOP), garantissant une vérification de cohérence sécurisée et efficace entre les variables et leurs permutations. Troisièmement, le protocole introduit une nouvelle preuve de décalage multilinéraire, optimisant l'efficacité de la validation 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é forte pour le mécanisme de recherche. Enfin, le protocole utilise un schéma d'engagement de polynômes de petits domaines (Small-Field PCS), lui permettant de réaliser un système de preuves efficace dans le domaine binaire et réduisant les frais généralement associés aux grands domaines.
2.1 Corps finis : arithmétique basée sur les tours de corps binaires
Le domaine binaire en tour est la clé pour réaliser des calculs vérifiables rapides, principalement en raison de deux aspects : le calcul efficace et l'arithmétique efficace. Le domaine binaire prend en charge des opérations arithmétiques hautement efficaces, ce qui en fait un choix idéal pour les applications cryptographiques sensibles aux exigences de performance. De plus, la structure du domaine binaire soutient un processus d'arithmétisation simplifié, c'est-à-dire que les opérations effectuées sur le domaine 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, font du domaine binaire un choix particulièrement adapté pour des systèmes de preuve évolutifs tels que Binius.
Le terme "canonical" désigne la représentation unique et directe d'un élément dans le domaine binaire. Par exemple, dans le domaine binaire de base F2, toute chaîne de k bits peut être directement mappée à un élément du domaine binaire de k bits. Cela diffère des domaines premiers, qui ne peuvent pas fournir cette représentation canonique dans un nombre de bits donné. Bien qu'un domaine premier de 32 bits puisse être contenu dans 32 bits, ce n'est pas le cas pour chaque chaîne de 32 bits qui peut être associée de manière unique à un élément du domaine, alors que le domaine binaire offre cette commodité de mappage un à un. Dans le domaine premier Fp, les méthodes de réduction courantes incluent la réduction de Barrett, la réduction de Montgomery, ainsi que des méthodes de réduction spéciales pour des domaines finis spécifiques comme Mersenne-31 ou Goldilocks-64. Dans le domaine binaire F2k, les méthodes de réduction couramment utilisées comprennent la réduction spéciale (comme celle utilisée dans AES), la réduction de Montgomery (comme celle 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 domaine binaire ne nécessite pas l'introduction de retenue dans les opérations d'addition et de multiplication, et que l'opération de carré dans le domaine binaire est très efficace, car elle suit la règle simplifiée (X + Y )2 = X2 + Y 2.
Comme 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 analysée comme deux éléments de domaine de tour de 64 bits, quatre éléments de domaine de tour de 32 bits, seize éléments de domaine de tour de 8 bits, ou 128 éléments de domaine F2. Cette flexibilité de représentation ne nécessite aucun coût de calcul, juste une conversion de type de la chaîne de bits, ce qui est une propriété très intéressante et utile. De plus, les éléments de petit domaine peuvent être emballé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, d'élévation au carré et d'inversion dans les domaines binaires à tour de n bits (décomposables en sous-domaines de m bits).
2.2 PIOP : version adaptée de HyperPlonk Product et PermutationCheck ------ applicable aux domaines binaires
Le design 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 correctitude des polynômes et des ensembles multivariables. Ces vérifications clés comprennent :
GateCheck : vérifie si le témoin secret ω et l'entrée publique x satisfont la relation de calcul du circuit C(x,ω)=0, afin d'assurer le bon fonctionnement du circuit.
PermutationCheck : Vérifie si les résultats d'évaluation de deux polynômes multivariés f et g sur le cube hyperbolique booléen forment une relation de permutation f(x) = f(π(x)), afin d'assurer la cohérence des permutations entre les variables du polynôme.
LookupCheck : vérifie si l'évaluation du polynôme se trouve dans la table de recherche donnée, c'est-à-dire f(Bµ) ⊆ T(Bµ), en s'assurant 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érifier si l'évaluation d'un polynôme à coefficients rationnels sur le cube hyperbolique booléen est égale à une valeur déclarée ∏x∈Hµ f(x) = s, afin de garantir la validité du produit polynomial.
ZeroCheck : vérifier si un polynôme multivariable à 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 de l'évaluation de polynômes multivariables en un problème d'é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, réalisant ainsi le traitement par lots de plusieurs instances de vérification de sommes.
BatchCheck : basé sur SumCheck, vérifie la validité de l'évaluation de plusieurs polynômes multivariés pour améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk aient 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 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 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 généralisation à n'importe quelle valeur de produit.
Vérification de permutation inter-colonnes : HyperPlonk n'a pas cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de gérer des cas de permutation de polynômes plus complexes.
Ainsi, Binius a amélioré la flexibilité et l'efficacité du protocole grâce à une amélioration du mécanisme PIOPSumCheck existant, offrant un support fonctionnel plus puissant, en particulier lors du traitement de vérifications de polynômes multivariables plus complexes. Ces améliorations ont non seulement résolu les limitations de HyperPlonk, mais ont également jeté 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 au hypercube booléen
Dans le protocole Binius, la construction et le traitement des polynômes virtuels sont l'une des technologies clés, permettant de générer et d'opérer efficacement des polynômes dérivés de poignées d'entrée ou d'autres polynômes virtuels. Voici deux méthodes clés :