Analyse des principes des STARKs de Binius et réflexions 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 relativement petites, comme les indices dans les boucles for, les valeurs booléennes, les compteurs, etc. Cependant, pour garantir la sécurité des preuves basées sur les arbres de Merkle, l'utilisation du codage de Reed-Solomon pour étendre les données entraîne de nombreuses valeurs de redondance supplémentaires qui occupent 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 de code des STARKs de 1ère génération est de 252 bits, celle des STARKs de 2ème génération est de 64 bits, et celle des STARKs de 3ème génération est de 32 bits, mais la largeur de code de 32 bits présente encore une grande quantité d'espace gaspillé. En comparaison, le domaine binaire permet de manipuler directement les bits, avec un codage compact et efficace sans aucun espace gaspillé, c'est-à-dire les STARKs de 4ème génération.
Comparé aux découvertes récentes dans les domaines finis comme Goldilocks, BabyBear, Mersenne31, la recherche sur les domaines binaires remonte aux années 80. Actuellement, les domaines binaires sont largement utilisés en cryptographie, des exemples typiques incluent :
Standard de chiffrement avancé ( AES ), basé sur le domaine F28 ;
Code d'authentification de message Galois ( GMAC ), basé sur le domaine F2128;
Code QR, utilisant un codage Reed-Solomon basé sur F28;
Protocole FRI original et zk-STARK, ainsi que la fonction de hachage Grøstl, qui a atteint la finale de SHA-3, basée sur le domaine F28, est un algorithme de hachage particulièrement adapté à la récursivité.
Lorsque des domaines plus petits sont utilisés, l'opération d'extension de domaine devient de plus en plus importante pour garantir la sécurité. Le domaine binaire utilisé par Binius doit entièrement dépendre de l'extension de domaine pour assurer sa sécurité et sa praticité. La plupart des polynômes impliqués dans les calculs de Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais peuvent simplement opérer sous le domaine de base, réalisant ainsi une haute efficacité dans un petit domaine. Cependant, les vérifications de points aléatoires et les calculs FRI doivent encore plonger dans un plus grand domaine d'extension pour garantir la sécurité requise.
Lors de la construction d'un système de preuve basé sur le domaine binaire, 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 l'extension du codage.
Binius a proposé une solution innovante, traitant ces deux problèmes séparément, et réalisant cela en représentant les mêmes données de deux manières différentes : tout d'abord, en utilisant des polynômes multivariés ( spécifiquement des polynômes multilinaires ) au lieu de polynômes univariés, pour représenter toute la trajectoire de calcul par ses valeurs sur des "hypercubes" ( ; ensuite, étant donné que la longueur de chaque dimension de l'hypercube est de 2, il n'est pas possible de réaliser une extension Reed-Solomon standard comme avec les STARKs, mais on peut considérer l'hypercube comme un ) carré ( et effectuer une extension Reed-Solomon basée sur ce carré. Cette méthode, tout en garantissant la sécurité, améliore considérablement l'efficacité du codage et les performances de calcul.
2 Analyse des principes
La construction de la plupart des systèmes SNARKs actuellement implique généralement deux parties :
Preuve d'oracle interactive polynomiale d'information théorique )Information-Theoretic Polynomial Interactive Oracle Proof, PIOP( : PIOP, en tant que système de preuve central, transforme les relations de calcul d'entrée en égalités polynomiales vérifiables. Différents protocoles PIOP permettent au prouveur d'envoyer progressivement des polynômes grâce à une interaction avec le vérificateur, de sorte que le vérificateur peut vérifier si le calcul est correct en interrogeant un petit nombre de résultats d'évaluation des polynômes. Les protocoles PIOP existants incluent : PLONK PIOP, Spartan PIOP et HyperPlonk PIOP, qui traitent chacun les expressions polynomiales de manière différente, influençant ainsi la performance et l'efficacité du système SNARK dans son ensemble.
Polynomial Commitment Scheme ) Polynomial Commitment Scheme, PCS ( : Le schéma d'engagement polynômial est utilisé pour prouver si une équation 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 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 polynômial courants incluent KZG, Bulletproofs, FRI ) Fast Reed-Solomon IOPP ( et Brakedown, etc. Différents PCS ont des performances, des niveaux de 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, afin 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 est conçu en mettant l'accent sur l'évolutivité et l'élimination du trusted setup dans le protocole ZCash.
• Plonky2 : utilise une combinaison de PLONK PIOP et de FRI PCS, basée sur le domaine de Goldilocks. Plonky2 est conçu pour réaliser une récursivité efficace. Lors de la conception de ces systèmes, les PIOP et PCS choisis doivent correspondre au domaine fini ou à la courbe elliptique utilisée, afin de garantir la validité, la performance et la sécurité du système. Le choix de ces combinaisons influence 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 + champs 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 les champs binaires. Deuxièmement, Binius adapte la vérification de produit et de permutation de HyperPlonk dans son protocole de preuve Oracle interactif )PIOP(, garantissant une vérification cohérente et sécurisée 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 champs. Quatrièmement, Binius utilise une version améliorée de la preuve de recherche Lasso, offrant flexibilité et sécurité robuste pour le mécanisme de recherche. Enfin, le protocole utilise un schéma d'engagement polynomial sur de petits champs )Small-Field PCS(, permettant de réaliser un système de preuve efficace sur les champs binaires et réduisant les frais généralement associés aux grands champs.
) 2.1 Domain fini : arithmétique basée sur les tours de champs binaires
Les corps binaires en tour sont la clé pour réaliser des calculs vérifiables rapides, principalement en raison de deux aspects : le calcul efficace et l'arithmétique efficace. Les corps binaires soutiennent essentiellement des opérations arithmétiques hautement efficaces, ce qui en fait un choix idéal pour les applications cryptographiques sensibles aux performances. De plus, la structure des corps binaires supporte un processus d'arithmétisation simplifié, c'est-à-dire que les opérations effectuées sur le corps binaire peuvent être exprimées sous une forme algébrique compacte et facile à vérifier. Ces caractéristiques, associées à la capacité d'exploiter pleinement les propriétés 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" désigne la représentation unique et directe des éléments 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 de nombres premiers, qui ne peuvent pas fournir cette représentation canonique dans un nombre de bits donné. Bien qu'un domaine de nombres premiers de 32 bits puisse être contenu dans 32 bits, cela ne signifie pas que chaque chaîne de 32 bits corresponde de manière unique à un élément du domaine, alors que le domaine binaire offre cette commodité de correspondance bijective. Dans le domaine de nombres premiers 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 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 ) utilisée dans Tower (. L'article "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" souligne que le domaine binaire n'a pas besoin d'introduire des retenues 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 d'un domaine binaire. Elle peut être considérée comme un élément unique dans un domaine binaire de 128 bits, ou être analysée en deux éléments de domaine de tour de 64 bits, quatre éléments de domaine de tour de 32 bits, 16 éléments de domaine de tour de 8 bits, ou 128 éléments de domaine F2. Cette flexibilité de représentation ne nécessite aucun coût de calcul, c'est simplement un type de conversion de chaîne de bits )typecast(, qui est une propriété très intéressante et utile. Par ailleurs, les éléments de petit domaine peuvent être empaqueté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é computationnelle. De plus, le document "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité computationnelle des opérations de multiplication, de mise au carré et d'inversion dans un domaine binaire de tour de n bits ) décomposable en un sous-domaine de m bits (.
![Bitlayer Research : Analyse du principe des STARKs de Binius et réflexions sur leur optimisation])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 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 essentiels pour valider l'exactitude des polynômes et des ensembles multivariables. Ces vérifications essentielles comprennent :
GateCheck : Vérifiez si le témoin secret ω et l'entrée publique x satisfont la relation de calcul du circuit C(x,ω)=0, afin de garantir le bon fonctionnement du circuit.
PermutationCheck : Vérifie si les résultats d'évaluation de deux polynômes multivariables 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 du polynôme.
LookupCheck : vérifier si l'évaluation du polynôme est dans la table de recherche donnée, c'est-à-dire f(Bµ) ⊆ T)Bµ(, s'assurer 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 le cube hyperbolique booléen est égale à une valeur déclarée ∏x∈Hµ f)x( = s, afin d'assurer la validité du produit polynomial.
ZeroCheck: Vérifier si un polynôme multivarié à plusieurs variables est nul à 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érifier si la somme d'un polynôme multivarié est égale à la valeur déclarée ∑x∈Hµ f)x( = s. En transformant le problème d'évaluation d'un polynôme multivarié en évaluation d'un polynôme à une seule variable, on 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 et réaliser le traitement par lots de plusieurs instances de vérification de somme.
BatchCheck : basé sur SumCheck, vérifie la validité de l'évaluation de plusieurs polynômes multivariés afin d'améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk présentent de nombreuses similitudes dans la conception du protocole, 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.
Gestion 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 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 inter-colonnes : HyperPlonk n'a pas cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de gérer des situations de permutation polynomiale plus complexes.
Ainsi, Binius a amélioré le mécanisme PIOPSumCheck existant, augmentant la flexibilité et l'efficacité du protocole, en particulier lors du traitement de 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 systèmes de preuve basés sur des domaines binaires à l'avenir.
![Bitlayer Research : Analyse des principes des STARKs de Binius et réflexion sur leur optimisation])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(
) 2.3 PIOP: nouvel argument de décalage multilinéraire------applicable au cube hyperbolique booléen
Dans le protocole Binius, la construction et le traitement des polynômes virtuels sont l'une des technologies clés, permettant de générer et de manipuler 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: cette méthode passe par
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
5
Partager
Commentaire
0/400
TokenomicsTinfoilHat
· 07-09 06:31
Je ne comprends vraiment pas pourquoi c'est devenu de plus en plus basique malgré toutes les optimisations.
Voir l'originalRépondre0
FancyResearchLab
· 07-06 17:35
Encore ces optimisations fantaisistes.
Voir l'originalRépondre0
PaperHandsCriminal
· 07-06 17:32
Encore un plan d'optimisation, je ne comprends même pas les problèmes de base...
Voir l'originalRépondre0
ConfusedWhale
· 07-06 17:24
Optimiser optimiser, il faut toujours optimiser.
Voir l'originalRépondre0
NFTBlackHole
· 07-06 17:12
Zut, réduire le domaine permet d'économiser autant d'espace.
Binius : Analyse de l'optimisation STARKs basée sur le domaine binaire
Analyse des principes des STARKs de Binius et réflexions 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 relativement petites, comme les indices dans les boucles for, les valeurs booléennes, les compteurs, etc. Cependant, pour garantir la sécurité des preuves basées sur les arbres de Merkle, l'utilisation du codage de Reed-Solomon pour étendre les données entraîne de nombreuses valeurs de redondance supplémentaires qui occupent 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 de code des STARKs de 1ère génération est de 252 bits, celle des STARKs de 2ème génération est de 64 bits, et celle des STARKs de 3ème génération est de 32 bits, mais la largeur de code de 32 bits présente encore une grande quantité d'espace gaspillé. En comparaison, le domaine binaire permet de manipuler directement les bits, avec un codage compact et efficace sans aucun espace gaspillé, c'est-à-dire les STARKs de 4ème génération.
Comparé aux découvertes récentes dans les domaines finis comme Goldilocks, BabyBear, Mersenne31, la recherche sur les domaines binaires remonte aux années 80. Actuellement, les domaines binaires sont largement utilisés en cryptographie, des exemples typiques incluent :
Standard de chiffrement avancé ( AES ), basé sur le domaine F28 ;
Code d'authentification de message Galois ( GMAC ), basé sur le domaine F2128;
Code QR, utilisant un codage Reed-Solomon basé sur F28;
Protocole FRI original et zk-STARK, ainsi que la fonction de hachage Grøstl, qui a atteint la finale de SHA-3, basée sur le domaine F28, est un algorithme de hachage particulièrement adapté à la récursivité.
Lorsque des domaines plus petits sont utilisés, l'opération d'extension de domaine devient de plus en plus importante pour garantir la sécurité. Le domaine binaire utilisé par Binius doit entièrement dépendre de l'extension de domaine pour assurer sa sécurité et sa praticité. La plupart des polynômes impliqués dans les calculs de Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais peuvent simplement opérer sous le domaine de base, réalisant ainsi une haute efficacité dans un petit domaine. Cependant, les vérifications de points aléatoires et les calculs FRI doivent encore plonger dans un plus grand domaine d'extension pour garantir la sécurité requise.
Lors de la construction d'un système de preuve basé sur le domaine binaire, 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 l'extension du codage.
Binius a proposé une solution innovante, traitant ces deux problèmes séparément, et réalisant cela en représentant les mêmes données de deux manières différentes : tout d'abord, en utilisant des polynômes multivariés ( spécifiquement des polynômes multilinaires ) au lieu de polynômes univariés, pour représenter toute la trajectoire de calcul par ses valeurs sur des "hypercubes" ( ; ensuite, étant donné que la longueur de chaque dimension de l'hypercube est de 2, il n'est pas possible de réaliser une extension Reed-Solomon standard comme avec les STARKs, mais on peut considérer l'hypercube comme un ) carré ( et effectuer une extension Reed-Solomon basée sur ce carré. Cette méthode, tout en garantissant la sécurité, améliore considérablement l'efficacité du codage et les performances de calcul.
2 Analyse des principes
La construction de la plupart des systèmes SNARKs actuellement implique généralement deux parties :
Preuve d'oracle interactive polynomiale d'information théorique )Information-Theoretic Polynomial Interactive Oracle Proof, PIOP( : PIOP, en tant que système de preuve central, transforme les relations de calcul d'entrée en égalités polynomiales vérifiables. Différents protocoles PIOP permettent au prouveur d'envoyer progressivement des polynômes grâce à une interaction avec le vérificateur, de sorte que le vérificateur peut vérifier si le calcul est correct en interrogeant un petit nombre de résultats d'évaluation des polynômes. Les protocoles PIOP existants incluent : PLONK PIOP, Spartan PIOP et HyperPlonk PIOP, qui traitent chacun les expressions polynomiales de manière différente, influençant ainsi la performance et l'efficacité du système SNARK dans son ensemble.
Polynomial Commitment Scheme ) Polynomial Commitment Scheme, PCS ( : Le schéma d'engagement polynômial est utilisé pour prouver si une équation 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 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 polynômial courants incluent KZG, Bulletproofs, FRI ) Fast Reed-Solomon IOPP ( et Brakedown, etc. Différents PCS ont des performances, des niveaux de 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, afin 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 est conçu en mettant l'accent sur l'évolutivité et l'élimination du trusted setup dans le protocole ZCash.
• Plonky2 : utilise une combinaison de PLONK PIOP et de FRI PCS, basée sur le domaine de Goldilocks. Plonky2 est conçu pour réaliser une récursivité efficace. Lors de la conception de ces systèmes, les PIOP et PCS choisis doivent correspondre au domaine fini ou à la courbe elliptique utilisée, afin de garantir la validité, la performance et la sécurité du système. Le choix de ces combinaisons influence 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 + champs 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 les champs binaires. Deuxièmement, Binius adapte la vérification de produit et de permutation de HyperPlonk dans son protocole de preuve Oracle interactif )PIOP(, garantissant une vérification cohérente et sécurisée 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 champs. Quatrièmement, Binius utilise une version améliorée de la preuve de recherche Lasso, offrant flexibilité et sécurité robuste pour le mécanisme de recherche. Enfin, le protocole utilise un schéma d'engagement polynomial sur de petits champs )Small-Field PCS(, permettant de réaliser un système de preuve efficace sur les champs binaires et réduisant les frais généralement associés aux grands champs.
) 2.1 Domain fini : arithmétique basée sur les tours de champs binaires
Les corps binaires en tour sont la clé pour réaliser des calculs vérifiables rapides, principalement en raison de deux aspects : le calcul efficace et l'arithmétique efficace. Les corps binaires soutiennent essentiellement des opérations arithmétiques hautement efficaces, ce qui en fait un choix idéal pour les applications cryptographiques sensibles aux performances. De plus, la structure des corps binaires supporte un processus d'arithmétisation simplifié, c'est-à-dire que les opérations effectuées sur le corps binaire peuvent être exprimées sous une forme algébrique compacte et facile à vérifier. Ces caractéristiques, associées à la capacité d'exploiter pleinement les propriétés 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" désigne la représentation unique et directe des éléments 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 de nombres premiers, qui ne peuvent pas fournir cette représentation canonique dans un nombre de bits donné. Bien qu'un domaine de nombres premiers de 32 bits puisse être contenu dans 32 bits, cela ne signifie pas que chaque chaîne de 32 bits corresponde de manière unique à un élément du domaine, alors que le domaine binaire offre cette commodité de correspondance bijective. Dans le domaine de nombres premiers 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 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 ) utilisée dans Tower (. L'article "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" souligne que le domaine binaire n'a pas besoin d'introduire des retenues 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 d'un domaine binaire. Elle peut être considérée comme un élément unique dans un domaine binaire de 128 bits, ou être analysée en deux éléments de domaine de tour de 64 bits, quatre éléments de domaine de tour de 32 bits, 16 éléments de domaine de tour de 8 bits, ou 128 éléments de domaine F2. Cette flexibilité de représentation ne nécessite aucun coût de calcul, c'est simplement un type de conversion de chaîne de bits )typecast(, qui est une propriété très intéressante et utile. Par ailleurs, les éléments de petit domaine peuvent être empaqueté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é computationnelle. De plus, le document "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité computationnelle des opérations de multiplication, de mise au carré et d'inversion dans un domaine binaire de tour de n bits ) décomposable en un sous-domaine de m bits (.
![Bitlayer Research : Analyse du principe des STARKs de Binius et réflexions sur leur optimisation])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 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 essentiels pour valider l'exactitude des polynômes et des ensembles multivariables. Ces vérifications essentielles comprennent :
GateCheck : Vérifiez si le témoin secret ω et l'entrée publique x satisfont la relation de calcul du circuit C(x,ω)=0, afin de garantir le bon fonctionnement du circuit.
PermutationCheck : Vérifie si les résultats d'évaluation de deux polynômes multivariables 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 du polynôme.
LookupCheck : vérifier si l'évaluation du polynôme est dans la table de recherche donnée, c'est-à-dire f(Bµ) ⊆ T)Bµ(, s'assurer 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 le cube hyperbolique booléen est égale à une valeur déclarée ∏x∈Hµ f)x( = s, afin d'assurer la validité du produit polynomial.
ZeroCheck: Vérifier si un polynôme multivarié à plusieurs variables est nul à 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érifier si la somme d'un polynôme multivarié est égale à la valeur déclarée ∑x∈Hµ f)x( = s. En transformant le problème d'évaluation d'un polynôme multivarié en évaluation d'un polynôme à une seule variable, on 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 et réaliser le traitement par lots de plusieurs instances de vérification de somme.
BatchCheck : basé sur SumCheck, vérifie la validité de l'évaluation de plusieurs polynômes multivariés afin d'améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk présentent de nombreuses similitudes dans la conception du protocole, 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.
Gestion 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 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 inter-colonnes : HyperPlonk n'a pas cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de gérer des situations de permutation polynomiale plus complexes.
Ainsi, Binius a amélioré le mécanisme PIOPSumCheck existant, augmentant la flexibilité et l'efficacité du protocole, en particulier lors du traitement de 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 systèmes de preuve basés sur des domaines binaires à l'avenir.
![Bitlayer Research : Analyse des principes des STARKs de Binius et réflexion sur leur optimisation])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(
) 2.3 PIOP: nouvel argument de décalage multilinéraire------applicable au cube hyperbolique booléen
Dans le protocole Binius, la construction et le traitement des polynômes virtuels sont l'une des technologies clés, permettant de générer et de manipuler 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 :