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 dans les programmes réels sont relativement petites, comme les index dans les boucles for, les valeurs booléennes, les compteurs, etc. Cependant, pour assurer 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 dans 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 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é à Goldilocks, BabyBear, Mersenne31 et d'autres découvertes récentes sur les corps finis, la recherche sur les corps binaires remonte aux années 1980. Aujourd'hui, les corps binaires sont largement utilisés en cryptographie, des exemples typiques incluent:
Standard de chiffrement avancé ( AES ), basé sur le domaine F28;
Galois Message Authentication Code ( GMAC ), basé sur le domaine F2128;
QR code, utilisant un codage Reed-Solomon basé sur F28;
Protocole FRI d'origine et zk-STARK, ainsi que la fonction de hachage Grøstl qui a atteint la finale de SHA-3, cette fonction basée sur le domaine F28 est un algorithme de hachage très adapté aux récursions.
Lorsque des domaines plus petits sont utilisés, l'opération d'extension de domaine devient de plus en plus importante pour assurer la sécurité. Le domaine binaire utilisé par Binius doit entièrement s'appuyer sur l'extension de domaine pour garantir sa sécurité et sa praticité. La plupart des polynômes impliqués dans les calculs des Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais peuvent simplement fonctionner dans le domaine de base, ce qui permet d'atteindre une grande efficacité dans le petit domaine. Cependant, les vérifications de points aléatoires et le calcul FRI doivent encore plonger dans un domaine d'extension plus grand pour garantir la sécurité requise.
Lors de la construction d'un système de preuves 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 codage de Reed-Solomon doit être effectué, et la taille du domaine utilisée doit être supérieure à la taille après extension du codage.
Binius a proposé une solution innovante qui traite ces deux problèmes de manière distincte et représente les mêmes données de deux manières différentes : d'abord, en utilisant un polynôme multivarié (, spécifiquement un polynôme multilinéraire ), au lieu d'un polynôme à variable unique, pour représenter l'ensemble de la trajectoire de calcul par ses valeurs dans les "hyper-cubes" ( ; ensuite, comme la longueur de chaque dimension de l'hyper-cube est de 2, il n'est pas possible de faire une extension Reed-Solomon standard comme avec les STARKs, mais on peut considérer l'hyper-cube comme un carré ), et effectuer l'extension Reed-Solomon sur cette base carrée. Cette méthode améliore considérablement l'efficacité du codage et la performance de calcul tout en garantissant la sécurité.
2 Analyse des principes
La construction de la plupart des systèmes SNARKs actuels comprend généralement les deux parties suivantes :
Information-Theoretic Polynomial Interactive Oracle Proof, PIOP(: Le PIOP, en tant que système de preuve central, transforme les relations de calcul en égalités polynomiales vérifiables. Différents protocoles PIOP permettent au prouveur d'envoyer progressivement des polynômes par interaction avec le vérificateur, permettant à ce dernier de 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, chacun ayant une approche différente du traitement des expressions polynomiales, ce qui affecte 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 qui permet au prouveur de s'engager sur un certain polynôme et de vérifier ultérieurement le résultat de l'évaluation de ce polynôme, tout en cachant d'autres informations sur le polynôme. Les schémas d'engagement polynomial courants incluent KZG, Bulletproofs, FRI)Fast Reed-Solomon IOPP( et Brakedown, entre autres. Différents PCS ont des performances, une sécurité et des cas d'utilisation 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, pour 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 est conçu en mettant l'accent sur l'évolutivité et en supprimant la configuration de confiance du protocole ZCash.
• Plonky2 : utilisant la combinaison de PLONK PIOP et de FRI PCS, et basé sur le domaine de Goldilocks. Plonky2 est conçu pour réaliser des récursions efficaces. Lors de la conception de ces systèmes, le PIOP et le PCS choisis doivent correspondre au corps fini ou à la courbe elliptique utilisés, afin d'assurer la correctitude, 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 nécessiter de 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 + domaine binaire. 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 le domaine binaire. Deuxièmement, Binius a adapté HyperPlonk pour le produit et la vérification de permutation dans son protocole de preuve Oracle interactif )PIOP(, garantissant une vérification de cohérence sécurisée et efficace entre les variables et leurs permutations. Troisièmement, le protocole introduit une nouvelle preuve de décalage multilinéaire, optimisant l'efficacité de la vérification des relations multilinéaires sur de petits domaines. Quatrièmement, Binius utilise une version améliorée de la preuve de recherche Lasso, offrant flexibilité et sécurité robuste au mécanisme de recherche. Enfin, le protocole utilise un schéma d'engagement polynômial de petit domaine )Small-Field PCS(, lui permettant de mettre en œuvre 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 Corps finis : arithmétique basée sur les tours de corps binaires
Les corps binaires en tour sont essentiels pour réaliser des calculs vérifiables rapides, principalement en raison de deux aspects : le calcul efficace et l'arithmétisation efficace. Les corps binaires prennent intrinsèquement 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 des corps binaires soutient un processus d'arithmétisation simplifié, c'est-à-dire que les opérations effectuées sur les corps binaires peuvent être représentées sous une forme algébrique compacte et facile à vérifier. Ces caractéristiques, combinées à la capacité de tirer pleinement parti de leurs 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 tels que Binius.
Le terme "canonical" fait référence à la représentation unique et directe d'un élément dans un corps binaire. Par exemple, dans le corps binaire le plus simple F2, toute chaîne de k bits peut être directement mappée à un élément du corps binaire de k bits. Cela diffère des corps premiers, qui ne peuvent pas fournir cette représentation canonique dans un nombre de bits donné. Bien qu'un corps premier de 32 bits puisse être contenu dans 32 bits, ce n'est pas le cas de chaque chaîne de 32 bits qui peut correspondre de manière unique à un élément du corps, tandis que le corps binaire possède cette commodité d'un mappage un à un. Dans le corps premier Fp, les méthodes de réduction courantes incluent la réduction de Barrett, la réduction de Montgomery, ainsi que des méthodes de réduction spéciales pour des corps finis spécifiques tels que Mersenne-31 ou Goldilocks-64. Dans le corps binaire F2k, les méthodes de réduction courantes incluent des réductions spéciales ( comme celles utilisées dans AES ), la réduction de Montgomery ### comme celles utilisées dans POLYVAL ( et la réduction récursive ) comme celle de Tower (. Le document "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" indique que le corps binaire ne nécessite pas l'introduction de retenues dans les opérations d'addition et de multiplication, et que l'opération de carré est très efficace, car elle suit la règle simplifiée )X + Y (2 = X2 + Y 2.
Comme indiqué dans la figure 1, une chaîne de 128 bits : cette chaîne peut être interprétée de plusieurs manières dans le contexte des domaines binaires. Elle peut être considérée comme un élément unique dans un domaine binaire de 128 bits, ou être analysée comme deux éléments de domaine de tour de 64 bits, quatre éléments de domaine de tour de 32 bits, 16 éléments de domaine de tour 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 un changement de type de chaîne de bits )typecast(, ce qui est une propriété très intéressante et utile. En même temps, 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, l'article "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 tour de n bits ) décomposé en sous-domaines 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(
Figure 1 : Domaine binaire en tour
) 2.2 PIOP: version adapté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 adopte une série de mécanismes de vérification essentiels pour valider la correctitude des polynômes et des ensembles multivariables. Ces vérifications essentielles incluent :
GateCheck : vérifier 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 multivariés f et g sur le cube hyperbooléen sont une relation de permutation f###x( = f)π(x)(, afin de garantir la cohérence des permutations entre les variables polynômiales.
LookupCheck : Vérifiez si l'évaluation du polynôme se trouve dans la table de recherche donnée, c'est-à-dire f(Bµ) ⊆ T)Bµ(, assurez-vous que certaines valeurs se trouvent dans la plage spécifiée.
MultisetCheck : vérifier 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 de garantir l'exactitude du produit polynomial.
ZeroCheck : Vérifiez si un polynôme multivariable à plusieurs variables est nul en 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érification 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 univarié, 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 et en construisant des combinaisons linéaires pour 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 multivariés afin d'améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk présentent de nombreuses similitudes dans la conception des protocoles, Binius a apporté des améliorations dans les 3 domaines suivants :
Optimisation de ProductCheck : dans HyperPlonk, ProductCheck exige que le dénominateur U soit non nul partout sur l'hypercube, et que le produit soit égal à une valeur spécifique ; Binius simplifie ce processus de vérification en spécialisant cette valeur à 1, réduisant ainsi la complexité computationnelle.
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 zéro, le ProductCheck de Binius peut continuer à fonctionner, permettant une généralisation à n'importe quelle valeur de produit.
Vérification de permutation intercolonnes : HyperPlonk n'a pas cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de traiter des cas de permutation polynomiale plus complexes.
Ainsi, Binius a amélioré la flexibilité et l'efficacité du protocole grâce à des modifications du mécanisme PIOPSumCheck existant, en particulier lors du traitement de la validation de polynômes multivariables plus complexes, offrant un soutien fonctionnel plus solide. 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 corps binaires à l'avenir.
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.
14 J'aime
Récompense
14
5
Reposter
Partager
Commentaire
0/400
LightningPacketLoss
· Il y a 7h
Cette optimisation est vraiment insuffisante, 32 bits, c'est trop peu.
Voir l'originalRépondre0
PanicSeller
· Il y a 7h
C'est à la fois une optimisation et une compression, mais on perd toujours beaucoup.
Voir l'originalRépondre0
MoonBoi42
· Il y a 7h
Cette chose a été optimisée pendant une demi-journée, et ça ne vaut même pas Polaris.
Voir l'originalRépondre0
DecentralizeMe
· Il y a 7h
Optimiser le truc flashy
Voir l'originalRépondre0
ApeWithAPlan
· Il y a 8h
La réduction de la largeur de code de 252 à 32 est encore trop lente, non ?
Binius STARKs : innovations et optimisations dans le domaine binaire
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 dans les programmes réels sont relativement petites, comme les index dans les boucles for, les valeurs booléennes, les compteurs, etc. Cependant, pour assurer 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 dans 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 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.
Tableau 1 : Chemin de dérivation des STARKs
| Génération | Largeur de code | Système représenté | |------|----------|----------| | 1ère génération | 252 bits | StarkWare STARKs | | 2ème génération | 64 bits | Plonky2 | | 3ème génération | 32 bits | BabyBear | | 4ème génération | 1 bit | Binius |
Comparé à Goldilocks, BabyBear, Mersenne31 et d'autres découvertes récentes sur les corps finis, la recherche sur les corps binaires remonte aux années 1980. Aujourd'hui, les corps binaires sont largement utilisés en cryptographie, des exemples typiques incluent:
Standard de chiffrement avancé ( AES ), basé sur le domaine F28;
Galois Message Authentication Code ( GMAC ), basé sur le domaine F2128;
QR code, utilisant un codage Reed-Solomon basé sur F28;
Protocole FRI d'origine et zk-STARK, ainsi que la fonction de hachage Grøstl qui a atteint la finale de SHA-3, cette fonction basée sur le domaine F28 est un algorithme de hachage très adapté aux récursions.
Lorsque des domaines plus petits sont utilisés, l'opération d'extension de domaine devient de plus en plus importante pour assurer la sécurité. Le domaine binaire utilisé par Binius doit entièrement s'appuyer sur l'extension de domaine pour garantir sa sécurité et sa praticité. La plupart des polynômes impliqués dans les calculs des Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais peuvent simplement fonctionner dans le domaine de base, ce qui permet d'atteindre une grande efficacité dans le petit domaine. Cependant, les vérifications de points aléatoires et le calcul FRI doivent encore plonger dans un domaine d'extension plus grand pour garantir la sécurité requise.
Lors de la construction d'un système de preuves 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 codage de Reed-Solomon doit être effectué, et la taille du domaine utilisée doit être supérieure à la taille après extension du codage.
Binius a proposé une solution innovante qui traite ces deux problèmes de manière distincte et représente les mêmes données de deux manières différentes : d'abord, en utilisant un polynôme multivarié (, spécifiquement un polynôme multilinéraire ), au lieu d'un polynôme à variable unique, pour représenter l'ensemble de la trajectoire de calcul par ses valeurs dans les "hyper-cubes" ( ; ensuite, comme la longueur de chaque dimension de l'hyper-cube est de 2, il n'est pas possible de faire une extension Reed-Solomon standard comme avec les STARKs, mais on peut considérer l'hyper-cube comme un carré ), et effectuer l'extension Reed-Solomon sur cette base carrée. Cette méthode améliore considérablement l'efficacité du codage et la performance de calcul tout en garantissant la sécurité.
2 Analyse des principes
La construction de la plupart des systèmes SNARKs actuels comprend généralement les deux parties suivantes :
Information-Theoretic Polynomial Interactive Oracle Proof, PIOP(: Le PIOP, en tant que système de preuve central, transforme les relations de calcul en égalités polynomiales vérifiables. Différents protocoles PIOP permettent au prouveur d'envoyer progressivement des polynômes par interaction avec le vérificateur, permettant à ce dernier de 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, chacun ayant une approche différente du traitement des expressions polynomiales, ce qui affecte 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 qui permet au prouveur de s'engager sur un certain polynôme et de vérifier ultérieurement le résultat de l'évaluation de ce polynôme, tout en cachant d'autres informations sur le polynôme. Les schémas d'engagement polynomial courants incluent KZG, Bulletproofs, FRI)Fast Reed-Solomon IOPP( et Brakedown, entre autres. Différents PCS ont des performances, une sécurité et des cas d'utilisation 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, pour 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 est conçu en mettant l'accent sur l'évolutivité et en supprimant la configuration de confiance du protocole ZCash.
• Plonky2 : utilisant la combinaison de PLONK PIOP et de FRI PCS, et basé sur le domaine de Goldilocks. Plonky2 est conçu pour réaliser des récursions efficaces. Lors de la conception de ces systèmes, le PIOP et le PCS choisis doivent correspondre au corps fini ou à la courbe elliptique utilisés, afin d'assurer la correctitude, 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 nécessiter de 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 + domaine binaire. 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 le domaine binaire. Deuxièmement, Binius a adapté HyperPlonk pour le produit et la vérification de permutation dans son protocole de preuve Oracle interactif )PIOP(, garantissant une vérification de cohérence sécurisée et efficace entre les variables et leurs permutations. Troisièmement, le protocole introduit une nouvelle preuve de décalage multilinéaire, optimisant l'efficacité de la vérification des relations multilinéaires sur de petits domaines. Quatrièmement, Binius utilise une version améliorée de la preuve de recherche Lasso, offrant flexibilité et sécurité robuste au mécanisme de recherche. Enfin, le protocole utilise un schéma d'engagement polynômial de petit domaine )Small-Field PCS(, lui permettant de mettre en œuvre 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 Corps finis : arithmétique basée sur les tours de corps binaires
Les corps binaires en tour sont essentiels pour réaliser des calculs vérifiables rapides, principalement en raison de deux aspects : le calcul efficace et l'arithmétisation efficace. Les corps binaires prennent intrinsèquement 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 des corps binaires soutient un processus d'arithmétisation simplifié, c'est-à-dire que les opérations effectuées sur les corps binaires peuvent être représentées sous une forme algébrique compacte et facile à vérifier. Ces caractéristiques, combinées à la capacité de tirer pleinement parti de leurs 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 tels que Binius.
Le terme "canonical" fait référence à la représentation unique et directe d'un élément dans un corps binaire. Par exemple, dans le corps binaire le plus simple F2, toute chaîne de k bits peut être directement mappée à un élément du corps binaire de k bits. Cela diffère des corps premiers, qui ne peuvent pas fournir cette représentation canonique dans un nombre de bits donné. Bien qu'un corps premier de 32 bits puisse être contenu dans 32 bits, ce n'est pas le cas de chaque chaîne de 32 bits qui peut correspondre de manière unique à un élément du corps, tandis que le corps binaire possède cette commodité d'un mappage un à un. Dans le corps premier Fp, les méthodes de réduction courantes incluent la réduction de Barrett, la réduction de Montgomery, ainsi que des méthodes de réduction spéciales pour des corps finis spécifiques tels que Mersenne-31 ou Goldilocks-64. Dans le corps binaire F2k, les méthodes de réduction courantes incluent des réductions spéciales ( comme celles utilisées dans AES ), la réduction de Montgomery ### comme celles utilisées dans POLYVAL ( et la réduction récursive ) comme celle de Tower (. Le document "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" indique que le corps binaire ne nécessite pas l'introduction de retenues dans les opérations d'addition et de multiplication, et que l'opération de carré est très efficace, car elle suit la règle simplifiée )X + Y (2 = X2 + Y 2.
Comme indiqué dans la figure 1, une chaîne de 128 bits : cette chaîne peut être interprétée de plusieurs manières dans le contexte des domaines binaires. Elle peut être considérée comme un élément unique dans un domaine binaire de 128 bits, ou être analysée comme deux éléments de domaine de tour de 64 bits, quatre éléments de domaine de tour de 32 bits, 16 éléments de domaine de tour 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 un changement de type de chaîne de bits )typecast(, ce qui est une propriété très intéressante et utile. En même temps, 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, l'article "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 tour de n bits ) décomposé en sous-domaines 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(
Figure 1 : Domaine binaire en tour
) 2.2 PIOP: version adapté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 adopte une série de mécanismes de vérification essentiels pour valider la correctitude des polynômes et des ensembles multivariables. Ces vérifications essentielles incluent :
GateCheck : vérifier 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 multivariés f et g sur le cube hyperbooléen sont une relation de permutation f###x( = f)π(x)(, afin de garantir la cohérence des permutations entre les variables polynômiales.
LookupCheck : Vérifiez si l'évaluation du polynôme se trouve dans la table de recherche donnée, c'est-à-dire f(Bµ) ⊆ T)Bµ(, assurez-vous que certaines valeurs se trouvent dans la plage spécifiée.
MultisetCheck : vérifier 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 de garantir l'exactitude du produit polynomial.
ZeroCheck : Vérifiez si un polynôme multivariable à plusieurs variables est nul en 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érification 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 univarié, 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 et en construisant des combinaisons linéaires pour 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 multivariés afin d'améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk présentent de nombreuses similitudes dans la conception des protocoles, Binius a apporté des améliorations dans les 3 domaines suivants :
Optimisation de ProductCheck : dans HyperPlonk, ProductCheck exige que le dénominateur U soit non nul partout sur l'hypercube, et que le produit soit égal à une valeur spécifique ; Binius simplifie ce processus de vérification en spécialisant cette valeur à 1, réduisant ainsi la complexité computationnelle.
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 zéro, le ProductCheck de Binius peut continuer à fonctionner, permettant une généralisation à n'importe quelle valeur de produit.
Vérification de permutation intercolonnes : HyperPlonk n'a pas cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de traiter des cas de permutation polynomiale plus complexes.
Ainsi, Binius a amélioré la flexibilité et l'efficacité du protocole grâce à des modifications du mécanisme PIOPSumCheck existant, en particulier lors du traitement de la validation de polynômes multivariables plus complexes, offrant un soutien fonctionnel plus solide. 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 corps binaires à l'avenir.
) 2.3 PIOP : nouvel argument de décalage multilinéraire ------ applicable