Analyse des principes de Binius STARKs et réflexion sur leur optimisation
1 Introduction
Une des principales raisons de l'inefficacité 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, l'utilisation du codage de Reed-Solomon pour étendre les données entraîne de nombreuses valeurs redondantes supplémentaires occupant tout le domaine, même si la valeur originale elle-même est très petite. Pour résoudre ce problème, la réduction de la taille du domaine est devenue une stratégie clé.
Comme indiqué dans le tableau 1, la largeur de codage des STARKs de première génération est de 252 bits, celle des STARKs de deuxième génération est de 64 bits, et celle des STARKs de troisième génération est de 32 bits, mais la largeur de codage de 32 bits présente encore un grand espace gaspillé. En comparaison, le domaine binaire permet une manipulation directe des bits, avec un codage compact et efficace sans aucun espace gaspillé, c'est-à-dire les STARKs de quatrième génération.
Tableau 1 : Chemin de dérivation des STARKs
Comparé aux recherches récentes sur les corps finis comme Goldilocks, BabyBear et Mersenne31, l'étude des corps binaires remonte aux années 1980. Actuellement, les corps binaires sont largement utilisés en cryptographie, des exemples typiques incluent :
Norme de cryptage avancée ( AES ), basé sur le domaine F28;
Galois Message Authentication Code ( GMAC ), basé sur le champ F2128;
Code QR, utilisant un codage Reed-Solomon basé sur F28;
Le protocole FRI original et le zk-STARK, ainsi que la fonction de hachage Grøstl qui est entrée en finale de SHA-3, basée sur le domaine F28, est un algorithme de hachage très adapté pour la récursion.
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 dépend entièrement de l'extension de domaine pour garantir sa sécurité et son utilité pratique. 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 être opérés sous le domaine de base, réalisant ainsi une grande efficacité dans de petits domaines. Cependant, l'inspection de points aléatoires et le calcul FRI doivent toujours entrer dans un domaine d'extension plus grand pour garantir la sécurité requise.
Lors de la construction d'un système de preuve basé sur des corps binaires, il existe deux problèmes pratiques : lors du calcul de la représentation de trace dans les STARKs, la taille du corps utilisé 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 corps utilisé 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 une représentation des mêmes données de deux manières différentes : d'abord, en utilisant un polynôme multivarié ( qui est spécifiquement un polynôme multilinéraire ) au lieu d'un polynôme univarié, en représentant toute la trajectoire de calcul par ses valeurs sur des "hyper-cubes" ( ; ensuite, étant donné que la longueur de chaque dimension de l'hyper-cube est de 2, il n'est pas possible d'effectuer une extension de Reed-Solomon standard comme avec les STARKs, mais l'hyper-cube peut être considéré comme un carré ), sur la base duquel une extension de Reed-Solomon peut être réalisée. Cette méthode améliore considérablement l'efficacité du codage et les performances de calcul tout en garantissant la sécurité.
2 Analyse des principes
La construction de la plupart des systèmes SNARKs actuels comprend généralement les deux parties suivantes :
Information-Theoretic Polynomial Interactive Oracle Proof, PIOP(: PIOP en tant que cœur du système de preuve, transforme les relations de calcul d'entrée en égalités polynomiales vérifiables. Différents protocoles PIOP, à travers l'interaction avec le vérificateur, permettent 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 petit nombre 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, affectant 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 l'égalité polynomiale générée par PIOP est valide. Le PCS est un outil cryptographique, grâce auquel le prouveur peut s'engager sur un certain polynôme et valider 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 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, vous pouvez construire des systèmes de preuve avec différentes propriétés. Par exemple :
• Halo2 : combiné avec 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 : Combinaison de PLONK PIOP et FRI PCS, basé sur le domaine de Goldilocks. Plonky2 est conçu pour réaliser une récursion efficace. 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 correction, la performance et la sécurité du système. Le choix de ces combinaisons affecte non seulement la taille de la preuve SNARK et l'efficacité de la vérification, mais détermine également si le système peut réaliser la transparence sans configuration de confiance, 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, le calcul basé sur les tours de champs binaires )towers of binary fields( constitue la base de ses calculs, permettant d'effectuer des opérations simplifiées dans le domaine binaire. Deuxièmement, Binius a adapté les vérifications de produits et de substitutions de HyperPlonk dans son protocole de preuve Oracle interactif )PIOP(, garantissant une vérification cohérente, sécurisée et efficace entre les variables et leurs substitutions. 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 pour le mécanisme de recherche. Enfin, le protocole utilise le schéma d'engagement polynomial sur de petits domaines )Small-Field PCS(, lui permettant de réaliser un système de preuve efficace dans le domaine binaire et réduisant les coûts généralement associés aux grands domaines.
![Bitlayer Research : Analyse des principes des STARKs de Binius et réflexions sur leur optimisation])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(
) 2.1 Domaine fini : arithmétique basée sur les tours des corps binaires
Le domaine binaire en tour est la clé pour réaliser des calculs rapides et vérifiables, principalement en raison de deux aspects : un calcul efficace et une arithmétique efficace. Les domaines binaires prennent en charge 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 du domaine binaire soutient un processus d'arithmétisation simplifié, c'est-à-dire que les opérations exécutées sur le domaine binaire peuvent être représentées sous une forme algébrique compacte et facile à vérifier. Ces caractéristiques, associées à la capacité d'exploiter pleinement ses caractéristiques hiérarchiques grâce à la structure de tour, rendent le domaine binaire particulièrement adapté à des systèmes de preuve évolutifs comme Binius.
Le terme "canonical" fait référence à la représentation unique et directe des éléments dans un champ binaire. Par exemple, dans le champ binaire F2 le plus basique, n'importe quelle chaîne de k bits peut être directement mappée à un élément de champ binaire de k bits. Cela diffère des champs premiers, qui ne peuvent pas fournir cette représentation canonique dans un nombre de bits donné. Bien qu'un champ premier de 32 bits puisse être contenu dans 32 bits, chaque chaîne de 32 bits ne peut pas nécessairement correspondre de manière unique à un élément de champ, tandis que le champ binaire offre cette commodité de mappage un à un. Dans le champ 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 champs finis spécifiques comme Mersenne-31 ou Goldilocks-64. Dans le champ binaire F2k, les méthodes de réduction couramment utilisées incluent la réduction spéciale ( comme utilisée dans AES ), la réduction de Montgomery ### comme utilisée dans POLYVAL (, et la réduction récursive ) comme Tower (. L'article "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" indique que le champ 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 champ binaire est très efficace, car elle suit la règle simplifiée )X + Y (2 = X2 + Y 2.
Comme montré dans la figure 1, une chaîne de 128 bits : cette chaîne peut être interprétée de plusieurs manières dans le contexte des 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 64 bits, quatre éléments de domaine de 32 bits, seize éléments de domaine de 8 bits, ou 128 éléments de domaine F2. Cette flexibilité de représentation n'implique aucun coût de calcul, c'est simplement une conversion de type de chaîne de bits )typecast(, ce qui est une propriété très intéressante et utile. De plus, les petits éléments de domaine peuvent être regroupés en éléments de domaine plus grands sans coût de calcul supplémentaire. Le protocole Binius tire parti de cette caractéristique pour améliorer l'efficacité des calculs. En outre, le document "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité de calcul des opérations de multiplication, de mise au carré et d'inversion dans un domaine binaire de n bits ) décomposable en un sous-domaine de m bits (.
Figure 1 : Domaine binaire en tour
![Bitlayer Research : Analyse des principes des STARKs de Binius et réflexion sur leur optimisation])https://img-cdn.gateio.im/webp-social/moments-a5d031be4711f29ef910057f4e44a118.webp(
) 2.2 PIOP: Version adaptée du produit HyperPlonk et PermutationCheck ------ 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 la correctivité des polynômes et des ensembles multivariés. Ces vérifications essentielles comprennent :
GateCheck : Vérifiez si le témoin de confidentialité ω 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érifier si les résultats d'évaluation des deux polynômes multivariables f et g sur le cube hyperboolé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 est dans la table de recherche donnée, c'est-à-dire f(Bµ) ⊆ T)Bµ(, s'assurant que certaines valeurs sont 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 la correction du produit polynômial.
ZeroCheck : Vérifier si un polynôme multivariable à plusieurs variables est nul à un point quelconque sur le cube hyperbolique booléen ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, afin de garantir 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 des polynômes multivariés en un problème d'évaluation de polynômes univariés, cela réduit la complexité de calcul pour le vérificateur. De plus, SumCheck permet également le traitement par lots, en introduisant des nombres aléatoires pour construire des combinaisons linéaires afin de réaliser le traitement par lots de plusieurs instances de vérification de somme.
BatchCheck : Basé sur SumCheck, vérifie la validité des évaluations de plusieurs polynômes multivariables 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 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 l'extension à n'importe quelle valeur de produit.
Vérification de permutation inter-colonnes : HyperPlonk ne dispose pas de cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de gérer des situations de permutation polynomial 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 de polynômes multivariables plus complexes, offrant un meilleur support fonctionnel. Ces améliorations non seulement résolvent les limitations de HyperPlonk, mais jettent également les bases pour les futurs systèmes de preuves basés sur des corps binaires.
) 2.3 PIOP: nouvel argument de décalage multilinéraire ------ applicable à
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.
7 J'aime
Récompense
7
5
Reposter
Partager
Commentaire
0/400
BlockchainBard
· Il y a 20h
Les STARKs prennent de plus en plus d'espace !
Voir l'originalRépondre0
StakeHouseDirector
· Il y a 20h
Optimiser, optimiser, l'espace occupé est toujours trop grand !
Voir l'originalRépondre0
MetaverseLandlord
· Il y a 20h
Je sais juste empiler des paramètres techniques, ça me donne le vertige.
Voir l'originalRépondre0
WhaleWatcher
· Il y a 20h
Chaque jour, on crie pour améliorer l'efficacité, mais cette efficacité n'a toujours pas augmenté ?
Voir l'originalRépondre0
AirdropBuffet
· Il y a 20h
Frère, l'optimisation est si forte, mais c'est dommage que ça ne puisse toujours pas rivaliser.
Analyse des principes des STARKs de Binius : application innovante et optimisation de l'efficacité dans le domaine binaire
Analyse des principes de Binius STARKs et réflexion sur leur optimisation
1 Introduction
Une des principales raisons de l'inefficacité 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, l'utilisation du codage de Reed-Solomon pour étendre les données entraîne de nombreuses valeurs redondantes supplémentaires occupant tout le domaine, même si la valeur originale elle-même est très petite. Pour résoudre ce problème, la réduction de la taille du domaine est devenue une stratégie clé.
Comme indiqué dans le tableau 1, la largeur de codage des STARKs de première génération est de 252 bits, celle des STARKs de deuxième génération est de 64 bits, et celle des STARKs de troisième génération est de 32 bits, mais la largeur de codage de 32 bits présente encore un grand espace gaspillé. En comparaison, le domaine binaire permet une manipulation directe des bits, avec un codage compact et efficace sans aucun espace gaspillé, c'est-à-dire les STARKs de quatrième génération.
Tableau 1 : Chemin de dérivation des STARKs
Comparé aux recherches récentes sur les corps finis comme Goldilocks, BabyBear et Mersenne31, l'étude des corps binaires remonte aux années 1980. Actuellement, les corps binaires sont largement utilisés en cryptographie, des exemples typiques incluent :
Norme de cryptage avancée ( AES ), basé sur le domaine F28;
Galois Message Authentication Code ( GMAC ), basé sur le champ F2128;
Code QR, utilisant un codage Reed-Solomon basé sur F28;
Le protocole FRI original et le zk-STARK, ainsi que la fonction de hachage Grøstl qui est entrée en finale de SHA-3, basée sur le domaine F28, est un algorithme de hachage très adapté pour la récursion.
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 dépend entièrement de l'extension de domaine pour garantir sa sécurité et son utilité pratique. 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 être opérés sous le domaine de base, réalisant ainsi une grande efficacité dans de petits domaines. Cependant, l'inspection de points aléatoires et le calcul FRI doivent toujours entrer dans un domaine d'extension plus grand pour garantir la sécurité requise.
Lors de la construction d'un système de preuve basé sur des corps binaires, il existe deux problèmes pratiques : lors du calcul de la représentation de trace dans les STARKs, la taille du corps utilisé 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 corps utilisé 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 une représentation des mêmes données de deux manières différentes : d'abord, en utilisant un polynôme multivarié ( qui est spécifiquement un polynôme multilinéraire ) au lieu d'un polynôme univarié, en représentant toute la trajectoire de calcul par ses valeurs sur des "hyper-cubes" ( ; ensuite, étant donné que la longueur de chaque dimension de l'hyper-cube est de 2, il n'est pas possible d'effectuer une extension de Reed-Solomon standard comme avec les STARKs, mais l'hyper-cube peut être considéré comme un carré ), sur la base duquel une extension de Reed-Solomon peut être réalisée. Cette méthode améliore considérablement l'efficacité du codage et les performances de calcul tout en garantissant la sécurité.
2 Analyse des principes
La construction de la plupart des systèmes SNARKs actuels comprend généralement les deux parties suivantes :
Information-Theoretic Polynomial Interactive Oracle Proof, PIOP(: PIOP en tant que cœur du système de preuve, transforme les relations de calcul d'entrée en égalités polynomiales vérifiables. Différents protocoles PIOP, à travers l'interaction avec le vérificateur, permettent 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 petit nombre 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, affectant 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 l'égalité polynomiale générée par PIOP est valide. Le PCS est un outil cryptographique, grâce auquel le prouveur peut s'engager sur un certain polynôme et valider 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 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, vous pouvez construire des systèmes de preuve avec différentes propriétés. Par exemple :
• Halo2 : combiné avec 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 : Combinaison de PLONK PIOP et FRI PCS, basé sur le domaine de Goldilocks. Plonky2 est conçu pour réaliser une récursion efficace. 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 correction, la performance et la sécurité du système. Le choix de ces combinaisons affecte non seulement la taille de la preuve SNARK et l'efficacité de la vérification, mais détermine également si le système peut réaliser la transparence sans configuration de confiance, 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, le calcul basé sur les tours de champs binaires )towers of binary fields( constitue la base de ses calculs, permettant d'effectuer des opérations simplifiées dans le domaine binaire. Deuxièmement, Binius a adapté les vérifications de produits et de substitutions de HyperPlonk dans son protocole de preuve Oracle interactif )PIOP(, garantissant une vérification cohérente, sécurisée et efficace entre les variables et leurs substitutions. 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 pour le mécanisme de recherche. Enfin, le protocole utilise le schéma d'engagement polynomial sur de petits domaines )Small-Field PCS(, lui permettant de réaliser un système de preuve efficace dans le domaine binaire et réduisant les coûts généralement associés aux grands domaines.
![Bitlayer Research : Analyse des principes des STARKs de Binius et réflexions sur leur optimisation])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(
) 2.1 Domaine fini : arithmétique basée sur les tours des corps binaires
Le domaine binaire en tour est la clé pour réaliser des calculs rapides et vérifiables, principalement en raison de deux aspects : un calcul efficace et une arithmétique efficace. Les domaines binaires prennent en charge 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 du domaine binaire soutient un processus d'arithmétisation simplifié, c'est-à-dire que les opérations exécutées sur le domaine binaire peuvent être représentées sous une forme algébrique compacte et facile à vérifier. Ces caractéristiques, associées à la capacité d'exploiter pleinement ses caractéristiques hiérarchiques grâce à la structure de tour, rendent le domaine binaire particulièrement adapté à des systèmes de preuve évolutifs comme Binius.
Le terme "canonical" fait référence à la représentation unique et directe des éléments dans un champ binaire. Par exemple, dans le champ binaire F2 le plus basique, n'importe quelle chaîne de k bits peut être directement mappée à un élément de champ binaire de k bits. Cela diffère des champs premiers, qui ne peuvent pas fournir cette représentation canonique dans un nombre de bits donné. Bien qu'un champ premier de 32 bits puisse être contenu dans 32 bits, chaque chaîne de 32 bits ne peut pas nécessairement correspondre de manière unique à un élément de champ, tandis que le champ binaire offre cette commodité de mappage un à un. Dans le champ 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 champs finis spécifiques comme Mersenne-31 ou Goldilocks-64. Dans le champ binaire F2k, les méthodes de réduction couramment utilisées incluent la réduction spéciale ( comme utilisée dans AES ), la réduction de Montgomery ### comme utilisée dans POLYVAL (, et la réduction récursive ) comme Tower (. L'article "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" indique que le champ 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 champ binaire est très efficace, car elle suit la règle simplifiée )X + Y (2 = X2 + Y 2.
Comme montré dans la figure 1, une chaîne de 128 bits : cette chaîne peut être interprétée de plusieurs manières dans le contexte des 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 64 bits, quatre éléments de domaine de 32 bits, seize éléments de domaine de 8 bits, ou 128 éléments de domaine F2. Cette flexibilité de représentation n'implique aucun coût de calcul, c'est simplement une conversion de type de chaîne de bits )typecast(, ce qui est une propriété très intéressante et utile. De plus, les petits éléments de domaine peuvent être regroupés en éléments de domaine plus grands sans coût de calcul supplémentaire. Le protocole Binius tire parti de cette caractéristique pour améliorer l'efficacité des calculs. En outre, le document "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité de calcul des opérations de multiplication, de mise au carré et d'inversion dans un domaine binaire de n bits ) décomposable en un sous-domaine de m bits (.
Figure 1 : Domaine binaire en tour
![Bitlayer Research : Analyse des principes des STARKs de Binius et réflexion sur leur optimisation])https://img-cdn.gateio.im/webp-social/moments-a5d031be4711f29ef910057f4e44a118.webp(
) 2.2 PIOP: Version adaptée du produit HyperPlonk et PermutationCheck ------ 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 la correctivité des polynômes et des ensembles multivariés. Ces vérifications essentielles comprennent :
GateCheck : Vérifiez si le témoin de confidentialité ω 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érifier si les résultats d'évaluation des deux polynômes multivariables f et g sur le cube hyperboolé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 est dans la table de recherche donnée, c'est-à-dire f(Bµ) ⊆ T)Bµ(, s'assurant que certaines valeurs sont 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 la correction du produit polynômial.
ZeroCheck : Vérifier si un polynôme multivariable à plusieurs variables est nul à un point quelconque sur le cube hyperbolique booléen ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, afin de garantir 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 des polynômes multivariés en un problème d'évaluation de polynômes univariés, cela réduit la complexité de calcul pour le vérificateur. De plus, SumCheck permet également le traitement par lots, en introduisant des nombres aléatoires pour construire des combinaisons linéaires afin de réaliser le traitement par lots de plusieurs instances de vérification de somme.
BatchCheck : Basé sur SumCheck, vérifie la validité des évaluations de plusieurs polynômes multivariables 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 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 l'extension à n'importe quelle valeur de produit.
Vérification de permutation inter-colonnes : HyperPlonk ne dispose pas de cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de gérer des situations de permutation polynomial 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 de polynômes multivariables plus complexes, offrant un meilleur support fonctionnel. Ces améliorations non seulement résolvent les limitations de HyperPlonk, mais jettent également les bases pour les futurs systèmes de preuves basés sur des corps binaires.
) 2.3 PIOP: nouvel argument de décalage multilinéraire ------ applicable à