Analyse des principes des STARKs de Binius et réflexion sur leur optimisation
1. Introduction
Une des principales raisons de l'inefficacité des STARKs est que la plupart des valeurs numériques dans les programmes réels sont assez petites. 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 l'occupation de nombreux valeurs redondantes supplémentaires sur l'ensemble du 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 première génération est de 252 bits, celle des STARKs de deuxième génération est de 64 bits, et celle des STARKs de troisième génération est de 32 bits, mais la largeur de code de 32 bits présente encore beaucoup d'espace gaspillé. En comparaison, le domaine binaire permet d'opérer directement sur les bits, avec un codage compact et efficace sans aucun espace gaspillé, c'est-à-dire les STARKs de quatrième génération.
Comparé aux découvertes récentes sur les corps finis, comme Goldilocks, BabyBear et Mersenne31, la recherche sur les corps binaires remonte aux années 1980. Actuellement, les corps binaires sont largement utilisés en cryptographie, les exemples typiques incluent :
Standard de cryptage avancé ( AES ), basé sur le domaine F28
Code d'authentification de message Galois ( GMAC ), basé sur le domaine F2128
QR code, 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 est entrée en finale de SHA-3, basée sur le domaine F28, est 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 véritable utilisabilité. La plupart des polynômes impliqués dans les calculs Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais doivent simplement opérer sous le domaine de base, permettant ainsi d'atteindre une grande efficacité dans un petit domaine. Cependant, les vérifications de points aléatoires et les calculs FRI doivent encore plonger dans une plus grande extension de domaine 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 trace dans les STARKs, la taille du domaine utilisée doit être supérieure au degré du polynôme ; lors de l'engagement dans l'arbre de Merkle des STARKs, un encodage de Reed-Solomon doit être effectué, et la taille du domaine utilisée doit être supérieure à la taille après extension de l'encodage.
Binius a proposé une solution innovante qui traite ces deux problèmes séparément et représente 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 ) pour remplacer les polynômes à variable unique, en représentant l'ensemble de la trajectoire de calcul par ses valeurs sur les "hypercubes" ( ; ensuite, étant donné que la longueur de chaque dimension de l'hypercube est de 2, il n'est pas possible d'effectuer une extension standard de Reed-Solomon comme avec les STARKs, mais l'hypercube peut être considéré comme un ) carré (, et l'extension de Reed-Solomon peut être faite sur cette forme carré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 deux parties :
Preuve d'oracle interactif polynomial d'information théorique )Information-Theoretic Polynomial Interactive Oracle Proof, PIOP( : PIOP, en tant que système de preuve central, transforme la relation de calcul d'entrée en équations polynomiales vérifiables. Différents protocoles PIOP, à travers une 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 nombre limité de résultats d'évaluation de polynômes. Les protocoles PIOP existants comprennent : PLONK PIOP, Spartan PIOP et HyperPlonk PIOP, qui traitent chacun les expressions polynomiales de manière différente, affectant ainsi les performances et l'efficacité de l'ensemble du système SNARK.
Schéma d'engagement polynomial )Polynomial Commitment Scheme, PCS( : Un 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 au prouveur de s'engager sur un 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, des niveaux de sécurité et des cas d'utilisation différents.
En fonction des besoins spécifiques, choisissez différents PIOP et PCS, et combinez-les avec des domaines finis ou des courbes elliptiques appropriés, ce qui permet de construire des systèmes de preuve avec différentes propriétés. Par exemple :
Halo2 : combiné de PLONK PIOP et de Bulletproofs PCS, basé sur la courbe Pasta. Halo2 a été conçu en mettant l'accent sur la scalabilité et sur la suppression de la configuration de confiance dans le protocole ZCash.
Plonky2 : utilise PLONK PIOP et FRI PCS combinés, et est basé sur le domaine Goldilocks. Plonky2 est conçu pour réaliser une récursivité 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 influence non seulement la taille de la preuve SNARK et l'efficacité de la vérification, mais détermine également si le système peut réaliser la transparence sans configuration de confiance préalable, et s'il peut prendre en charge des fonctionnalités d'extension telles que les preuves récursives ou les preuves agrégées.
Binius : HyperPlonk PIOP + Brakedown PCS + domaines binaires. Concrètement, Binius comprend cinq technologies clés pour réaliser son efficacité et sa sécurité. Tout d'abord, l'arithmétique basée sur les tours de domaines binaires )towers of binary fields( constitue la base de ses calculs, permettant d'effectuer des opérations simplifiées dans le domaine binaire. Deuxièmement, Binius a adapté la vérification des produits et des permutations 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 permutations. Troisièmement, le protocole introduit une nouvelle preuve de décalage multinomial, optimisant l'efficacité de la vérification des relations multinomiales sur de petits domaines. Quatrièmement, Binius adopte une version améliorée de la preuve de recherche Lasso, offrant flexibilité et sécurité robuste au mécanisme de recherche. Enfin, le protocole utilise un schéma d'engagement polynomial sur petits domaines )Small-Field PCS(, lui permettant de réaliser un système de preuve efficace dans le domaine binaire, tout en réduisant les frais généralement associés aux grands domaines.
) 2.1 Domaine fini : arithmétique basée sur les tours de champs binaires
Le domaine binaire en tour est la clé pour réaliser des calculs rapides et vérifiables, principalement en raison de deux aspects : le calcul efficace et l'arithmétisation efficace. Les domaines binaires supportent essentiellement des opérations arithmétiques très efficaces, ce qui en fait un choix idéal pour les applications cryptographiques sensibles aux performances. De plus, la structure des domaines binaires permet 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, ajoutées à la capacité d'exploiter pleinement ses propriétés hiérarchiques grâce à la structure en 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 corps binaire. Par exemple, dans le corps binaire de base F2, toute chaîne de k bits peut être directement mappée à un élément de corps binaire de k bits. Cela diffère des corps de nombres premiers, qui ne peuvent pas fournir cette représentation canonique dans un nombre de bits donné. Bien qu'un corps de nombres premiers de 32 bits puisse être contenu dans 32 bits, il n'est pas vrai que chaque chaîne de 32 bits corresponde de manière unique à un élément du corps, tandis que le corps binaire offre cette commodité de mappage un à un. Dans le corps 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 corps finis spécifiques tels que Mersenne-31 ou Goldilocks-64. Dans le corps 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 ) comme Tower (. L'article "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" indique que dans le corps binaire, aucune retenue n'est nécessaire dans les opérations d'addition et de multiplication, et que l'opération de carré dans le corps 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 décomposée en deux éléments de domaine de 64 bits, quatre éléments de domaine de 32 bits, 16 éléments de domaine de 8 bits, ou 128 éléments de domaine F2. Cette flexibilité de représentation ne nécessite aucun coût de calcul, il s'agit simplement d'un changement 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. De plus, le document "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité de calcul des opérations de multiplication, de carré et d'inversion dans un domaine binaire en tour de n bits ) décomposable en un sous-domaine de m bits (.
![Bitlayer Research : Analyse des principes des STARKs de Binius et réflexion sur leur optimisation])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 2.2 PIOP: version adaptée de HyperPlonk Product et PermutationCheck------applicable au domaine binaire
La conception de PIOP dans le protocole Binius s'inspire de HyperPlonk et utilise une série de mécanismes de vérification essentiels pour valider l'exactitude des polynômes et des ensembles multivariés. Ces vérifications essentielles comprennent :
GateCheck : vérifiez si le témoin secret ω et l'entrée publique x satisfont la relation de calcul du circuit C###x, ω(=0, afin de garantir le bon fonctionnement du circuit.
PermutationCheck : Vérifiez si les résultats d'évaluation des 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 polynomiales.
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 se trouvent dans la plage spécifiée.
MultisetCheck : vérifie si deux ensembles multivariables sont égaux, c'est-à-dire {)x1,i,x2,(}i∈H={)y1,i,y2,(}i∈H, garantissant la cohérence entre plusieurs ensembles.
ProductCheck : Vérifier si l'évaluation d'un polynôme rationnel sur le cube hyperbolique booléen est égale à une valeur déclarée ∏x∈Hµ f)x( = s, afin de garantir l'exactitude du produit polynomial.
ZeroCheck : vérifier si un polynôme multivariable est nul à un point quelconque sur l'hypercube booléen ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, afin de s'assurer de la distribution des zéros du polynôme.
SumCheck : vérifie si la somme d'un polynôme multivariable est égale à la valeur déclarée ∑x∈Hµ f)x( = s. En transformant le problème d'évaluation d'un polynôme multivarié en évaluation d'un polynôme à variable unique, cela réduit la complexité de calcul pour le vérificateur. De plus, SumCheck permet également le traitement par lots en introduisant des nombres aléatoires pour construire des combinaisons linéaires, ce qui permet de traiter plusieurs instances de vérification de somme.
BatchCheck: basé sur SumCheck, vérifie l'exactitude des évaluations 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 du protocole, Binius apporte des améliorations dans les 3 domaines suivants :
Optimisation de ProductCheck : dans HyperPlonk, ProductCheck exige que le dénominateur U soit non nul sur l'hypercube, et que le produit doive être é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 adéquatement les cas de division par zéro, ce qui empêche d'affirmer que U est non nul sur l'hypercube ; Binius a correctement résolu 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 d'arrangements polynomiaux plus complexes.
Ainsi, Binius a amélioré la flexibilité et l'efficacité du protocole grâce à des modifications apportées au mécanisme PIOPSumCheck existant, offrant un support fonctionnel renforcé, notamment lors du traitement de validations de polynômes multivariables plus complexes. Ces améliorations non seulement résolvent les limitations du HyperPlonk, mais posent é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 à l'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 de manipuler efficacement les polynômes dérivés de poignées d'entrée ou d'autres polynômes virtuels. Voici deux méthodes clés :
Packing: Cette méthode consiste à regrouper les éléments les plus petits situés à des positions adjacentes dans l'ordre lexicographique en éléments plus grands.
Voir l'original
Cette page peut inclure du contenu de tiers fourni à des fins d'information uniquement. Gate ne garantit ni l'exactitude ni la validité de ces contenus, n’endosse pas les opinions exprimées, et ne fournit aucun conseil financier ou professionnel à travers ces informations. Voir la section Avertissement pour plus de détails.
15 J'aime
Récompense
15
4
Reposter
Partager
Commentaire
0/400
SurvivorshipBias
· Il y a 5h
stks de 252 à 32 bits gagne !
Voir l'originalRépondre0
liquiditea_sipper
· Il y a 20h
La largeur de codage est à nouveau enroulée.
Voir l'originalRépondre0
GateUser-9ad11037
· Il y a 20h
Cette idée d'optimisation est tout simplement géniale.
Voir l'originalRépondre0
ProveMyZK
· Il y a 20h
Avec une efficacité si faible, vous osez encore appeler cela une optimisation ?
Analyse des principes d'optimisation du domaine binaire de Binius STARKs : amélioration de l'efficacité d'encodage et des performances de calcul
Analyse des principes des STARKs de Binius et réflexion sur leur optimisation
1. Introduction
Une des principales raisons de l'inefficacité des STARKs est que la plupart des valeurs numériques dans les programmes réels sont assez petites. 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 l'occupation de nombreux valeurs redondantes supplémentaires sur l'ensemble du 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 première génération est de 252 bits, celle des STARKs de deuxième génération est de 64 bits, et celle des STARKs de troisième génération est de 32 bits, mais la largeur de code de 32 bits présente encore beaucoup d'espace gaspillé. En comparaison, le domaine binaire permet d'opérer directement sur les bits, avec un codage compact et efficace sans aucun espace gaspillé, c'est-à-dire les STARKs de quatrième génération.
Comparé aux découvertes récentes sur les corps finis, comme Goldilocks, BabyBear et Mersenne31, la recherche sur les corps binaires remonte aux années 1980. Actuellement, les corps binaires sont largement utilisés en cryptographie, les exemples typiques incluent :
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 véritable utilisabilité. La plupart des polynômes impliqués dans les calculs Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais doivent simplement opérer sous le domaine de base, permettant ainsi d'atteindre une grande efficacité dans un petit domaine. Cependant, les vérifications de points aléatoires et les calculs FRI doivent encore plonger dans une plus grande extension de domaine 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 trace dans les STARKs, la taille du domaine utilisée doit être supérieure au degré du polynôme ; lors de l'engagement dans l'arbre de Merkle des STARKs, un encodage de Reed-Solomon doit être effectué, et la taille du domaine utilisée doit être supérieure à la taille après extension de l'encodage.
Binius a proposé une solution innovante qui traite ces deux problèmes séparément et représente 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 ) pour remplacer les polynômes à variable unique, en représentant l'ensemble de la trajectoire de calcul par ses valeurs sur les "hypercubes" ( ; ensuite, étant donné que la longueur de chaque dimension de l'hypercube est de 2, il n'est pas possible d'effectuer une extension standard de Reed-Solomon comme avec les STARKs, mais l'hypercube peut être considéré comme un ) carré (, et l'extension de Reed-Solomon peut être faite sur cette forme carré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 deux parties :
Preuve d'oracle interactif polynomial d'information théorique )Information-Theoretic Polynomial Interactive Oracle Proof, PIOP( : PIOP, en tant que système de preuve central, transforme la relation de calcul d'entrée en équations polynomiales vérifiables. Différents protocoles PIOP, à travers une 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 nombre limité de résultats d'évaluation de polynômes. Les protocoles PIOP existants comprennent : PLONK PIOP, Spartan PIOP et HyperPlonk PIOP, qui traitent chacun les expressions polynomiales de manière différente, affectant ainsi les performances et l'efficacité de l'ensemble du système SNARK.
Schéma d'engagement polynomial )Polynomial Commitment Scheme, PCS( : Un 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 au prouveur de s'engager sur un 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, des niveaux de sécurité et des cas d'utilisation différents.
En fonction des besoins spécifiques, choisissez différents PIOP et PCS, et combinez-les avec des domaines finis ou des courbes elliptiques appropriés, ce qui permet de construire des systèmes de preuve avec différentes propriétés. Par exemple :
Halo2 : combiné de PLONK PIOP et de Bulletproofs PCS, basé sur la courbe Pasta. Halo2 a été conçu en mettant l'accent sur la scalabilité et sur la suppression de la configuration de confiance dans le protocole ZCash.
Plonky2 : utilise PLONK PIOP et FRI PCS combinés, et est basé sur le domaine Goldilocks. Plonky2 est conçu pour réaliser une récursivité 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 influence non seulement la taille de la preuve SNARK et l'efficacité de la vérification, mais détermine également si le système peut réaliser la transparence sans configuration de confiance préalable, et s'il peut prendre en charge des fonctionnalités d'extension telles que les preuves récursives ou les preuves agrégées.
Binius : HyperPlonk PIOP + Brakedown PCS + domaines binaires. Concrètement, Binius comprend cinq technologies clés pour réaliser son efficacité et sa sécurité. Tout d'abord, l'arithmétique basée sur les tours de domaines binaires )towers of binary fields( constitue la base de ses calculs, permettant d'effectuer des opérations simplifiées dans le domaine binaire. Deuxièmement, Binius a adapté la vérification des produits et des permutations 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 permutations. Troisièmement, le protocole introduit une nouvelle preuve de décalage multinomial, optimisant l'efficacité de la vérification des relations multinomiales sur de petits domaines. Quatrièmement, Binius adopte une version améliorée de la preuve de recherche Lasso, offrant flexibilité et sécurité robuste au mécanisme de recherche. Enfin, le protocole utilise un schéma d'engagement polynomial sur petits domaines )Small-Field PCS(, lui permettant de réaliser un système de preuve efficace dans le domaine binaire, tout en réduisant les frais généralement associés aux grands domaines.
) 2.1 Domaine fini : arithmétique basée sur les tours de champs binaires
Le domaine binaire en tour est la clé pour réaliser des calculs rapides et vérifiables, principalement en raison de deux aspects : le calcul efficace et l'arithmétisation efficace. Les domaines binaires supportent essentiellement des opérations arithmétiques très efficaces, ce qui en fait un choix idéal pour les applications cryptographiques sensibles aux performances. De plus, la structure des domaines binaires permet 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, ajoutées à la capacité d'exploiter pleinement ses propriétés hiérarchiques grâce à la structure en 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 corps binaire. Par exemple, dans le corps binaire de base F2, toute chaîne de k bits peut être directement mappée à un élément de corps binaire de k bits. Cela diffère des corps de nombres premiers, qui ne peuvent pas fournir cette représentation canonique dans un nombre de bits donné. Bien qu'un corps de nombres premiers de 32 bits puisse être contenu dans 32 bits, il n'est pas vrai que chaque chaîne de 32 bits corresponde de manière unique à un élément du corps, tandis que le corps binaire offre cette commodité de mappage un à un. Dans le corps 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 corps finis spécifiques tels que Mersenne-31 ou Goldilocks-64. Dans le corps 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 ) comme Tower (. L'article "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" indique que dans le corps binaire, aucune retenue n'est nécessaire dans les opérations d'addition et de multiplication, et que l'opération de carré dans le corps 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 décomposée en deux éléments de domaine de 64 bits, quatre éléments de domaine de 32 bits, 16 éléments de domaine de 8 bits, ou 128 éléments de domaine F2. Cette flexibilité de représentation ne nécessite aucun coût de calcul, il s'agit simplement d'un changement 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. De plus, le document "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité de calcul des opérations de multiplication, de carré et d'inversion dans un domaine binaire en tour de n bits ) décomposable en un sous-domaine de m bits (.
![Bitlayer Research : Analyse des principes des STARKs de Binius et réflexion sur leur optimisation])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 2.2 PIOP: version adaptée de HyperPlonk Product et PermutationCheck------applicable au domaine binaire
La conception de PIOP dans le protocole Binius s'inspire de HyperPlonk et utilise une série de mécanismes de vérification essentiels pour valider l'exactitude des polynômes et des ensembles multivariés. Ces vérifications essentielles comprennent :
GateCheck : vérifiez si le témoin secret ω et l'entrée publique x satisfont la relation de calcul du circuit C###x, ω(=0, afin de garantir le bon fonctionnement du circuit.
PermutationCheck : Vérifiez si les résultats d'évaluation des 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 polynomiales.
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 se trouvent dans la plage spécifiée.
MultisetCheck : vérifie si deux ensembles multivariables sont égaux, c'est-à-dire {)x1,i,x2,(}i∈H={)y1,i,y2,(}i∈H, garantissant la cohérence entre plusieurs ensembles.
ProductCheck : Vérifier si l'évaluation d'un polynôme rationnel sur le cube hyperbolique booléen est égale à une valeur déclarée ∏x∈Hµ f)x( = s, afin de garantir l'exactitude du produit polynomial.
ZeroCheck : vérifier si un polynôme multivariable est nul à un point quelconque sur l'hypercube booléen ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, afin de s'assurer de la distribution des zéros du polynôme.
SumCheck : vérifie si la somme d'un polynôme multivariable est égale à la valeur déclarée ∑x∈Hµ f)x( = s. En transformant le problème d'évaluation d'un polynôme multivarié en évaluation d'un polynôme à variable unique, cela réduit la complexité de calcul pour le vérificateur. De plus, SumCheck permet également le traitement par lots en introduisant des nombres aléatoires pour construire des combinaisons linéaires, ce qui permet de traiter plusieurs instances de vérification de somme.
BatchCheck: basé sur SumCheck, vérifie l'exactitude des évaluations 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 du protocole, Binius apporte des améliorations dans les 3 domaines suivants :
Optimisation de ProductCheck : dans HyperPlonk, ProductCheck exige que le dénominateur U soit non nul sur l'hypercube, et que le produit doive être é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 adéquatement les cas de division par zéro, ce qui empêche d'affirmer que U est non nul sur l'hypercube ; Binius a correctement résolu 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 d'arrangements polynomiaux plus complexes.
Ainsi, Binius a amélioré la flexibilité et l'efficacité du protocole grâce à des modifications apportées au mécanisme PIOPSumCheck existant, offrant un support fonctionnel renforcé, notamment lors du traitement de validations de polynômes multivariables plus complexes. Ces améliorations non seulement résolvent les limitations du HyperPlonk, mais posent é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 à l'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 de manipuler efficacement les polynômes dérivés de poignées d'entrée ou d'autres polynômes virtuels. Voici deux méthodes clés :