Analyse des principes des STARKs Binius et réflexions sur leur optimisation
1 Introduction
Différent des SNARKs basés sur les courbes elliptiques, les STARKs peuvent être considérés comme des SNARKs basés sur le hachage. Une des principales raisons de l'inefficacité actuelle des STARKs est que la plupart des valeurs numériques dans les programmes réels sont relativement petites, comme les index dans les boucles for, les valeurs de vérité, les compteurs, etc. Cependant, pour garantir la sécurité des preuves basées sur l'arbre de Merkle, de nombreuses valeurs de redondance supplémentaires occupent tout le domaine lors de l'expansion des données à l'aide du codage de Reed-Solomon, même si la valeur d'origine 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 de la première génération de STARKs est de 252 bits, celle de la deuxième génération de STARKs est de 64 bits, et celle de la troisième génération de STARKs est de 32 bits, mais la largeur de code de 32 bits présente encore un grand nombre d'espaces gaspillés. En comparaison, le champ binaire permet d'opérer directement sur les bits, ce qui rend le codage compact et efficace sans aucun espace gaspillé, c'est-à-dire la quatrième génération de STARKs.
Comparé aux découvertes récentes de champs finis tels que Goldilocks, BabyBear et Mersenne31, la recherche sur le champ binaire remonte aux années 1980. Actuellement, le champ binaire est largement utilisé en cryptographie, des exemples typiques incluent :
Norme de chiffrement avancée ( AES ), basée sur le domaine F28;
Galois Code d'Authentification de Message ( 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, finaliste du SHA-3, qui est basée sur le domaine F28, une algorithme de hachage très adapté à 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 doit entièrement dépendre de l'extension de domaine pour assurer sa sécurité et sa praticité. La plupart des polynômes impliqués dans les calculs de Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais doivent simplement opérer sous le domaine de base, réalisant ainsi une haute efficacité dans un petit domaine. Cependant, les vérifications de points aléatoires et les calculs FRI doivent encore plonger dans un domaine d'extension plus grand pour garantir la sécurité requise.
Lors de la construction d'un système de preuve basé sur un domaine binaire, il existe 2 problèmes pratiques : lors du calcul de la représentation de trace dans les STARKs, la taille du domaine utilisée doit être supérieure au degré du polynôme ; lors de l'engagement de l'arbre Merkle dans les STARKs, il est nécessaire de faire un codage de Reed-Solomon, et la taille du domaine utilisée doit être supérieure à la taille après l'extension du codage.
Binius a proposé une solution innovante pour traiter ces deux problèmes, en représentant les mêmes données de deux manières différentes : tout d'abord, en utilisant un polynôme multivarié (, en particulier un polynôme multilinéraire ), au lieu d'un polynôme univarié, pour représenter l'ensemble de la trajectoire de calcul par ses valeurs sur des "hypercubes" ( ; ensuite, comme chaque dimension de l'hypercube a une longueur de 2, il n'est pas possible de réaliser une extension standard de Reed-Solomon comme avec les STARKs, mais l'hypercube peut être considéré comme un carré ), sur la base duquel une extension de Reed-Solomon peut être effectué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 théorique preuve d'oracle interactive polynomiale ( Information-Theoretic Polynomial Interactive Oracle Proof, PIOP ) : PIOP, en tant que système de preuve central, transforme les relations de calcul d'entrée en équations polynomiales vérifiables. Différents protocoles PIOP permettent au prouveur d'envoyer progressivement des polynômes grâce à une interaction avec le vérificateur, de sorte que le vérificateur 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, impactant ainsi les performances et l'efficacité de l'ensemble du système SNARK.
Schéma de compromis polynomial (Polynomial Commitment Scheme, PCS) : Le schéma de compromis polynomial est utilisé pour prouver si l'égalité polynomial générée par PIOP est valable. PCS est un outil cryptographique par lequel le prouveur peut s'engager sur un certain polynôme et vérifier plus tard le résultat de l'évaluation de ce polynôme, tout en cachant d'autres informations sur le polynôme. Les schémas de compromis 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 : combinant PLONK PIOP et Bulletproofs PCS, basé sur la courbe Pasta. Lors de la conception de Halo2, l'accent a été mis sur l'évolutivité et l'élimination de la configuration de confiance dans le protocole ZCash.
• Plonky2 : Utilise PLONK PIOP et FRI PCS combinés, et est 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 domaine fini ou à la courbe elliptique utilisés, 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'expansion telles que les preuves récursives ou les preuves agrégées.
Binius: HyperPlonk PIOP + Brakedown PCS + domaines binaires. Plus précisément, Binius comprend cinq technologies clés pour réaliser son efficacité et sa sécurité. Tout d'abord, l'arithmétique basée sur les tours de domaines binaires (towers of binary fields) constitue la base de ses calculs, permettant d'effectuer des opérations simplifiées dans les domaines binaires. Deuxièmement, Binius adapte les vérifications de produits et de permutations de HyperPlonk dans son protocole de preuve Oracle interactif (PIOP), garantissant une vérification de la cohérence sécurisée et efficace entre les variables et leurs permutations. Troisièmement, le protocole introduit une nouvelle preuve de décalage multilinéraire, optimisant l'efficacité de la 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é renforcée pour le mécanisme de recherche. Enfin, le protocole utilise un schéma d'engagement polynomial sur de petits domaines (Small-Field PCS), lui permettant d'implémenter un système de preuve efficace dans le domaine binaire et réduisant les frais généralement associés aux grands domaines.
( 2.1 Corps finis : arithmétisation basée sur les tours de corps binaires
Les corps binaires en tour sont la clé pour réaliser des calculs vérifiables rapides, principalement en raison de deux aspects : le calcul efficace et l'arithmétisation efficace. Les corps binaires soutiennent essentiellement des opérations arithmétiques hautement efficaces, ce qui en fait un choix idéal pour les applications cryptographiques sensibles aux performances. De plus, la structure des corps binaires supporte un processus d'arithmétisation simplifié, c'est-à-dire que les opérations effectuées sur le corps binaire peuvent être représentées sous une forme algébrique compacte et facile à vérifier. Ces caractéristiques, combinées à la capacité de tirer pleinement parti de ses 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 champ binaire. Par exemple, dans le champ binaire de base F2, toute 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 offrir cette représentation canonique dans un nombre de bits donné. Bien qu'un champ premier de 32 bits puisse être contenu dans 32 bits, cela ne signifie pas que chaque chaîne de 32 bits correspond de manière unique à un élément de champ, tandis que le champ binaire possède cette commodité d'une correspondance un à un. Dans le champ premier Fp, les méthodes de réduction courantes incluent la réduction Barrett, la réduction Montgomery, ainsi que des méthodes de réduction spécifiques pour des champs finis particuliers 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 ) utilisée dans AES ###, la réduction 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" souligne 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 illustré dans la figure 1, une chaîne de 128 bits : cette chaîne peut être interprétée de plusieurs manières dans le contexte des domaines binaires. Elle peut être considérée comme un élément unique dans un domaine binaire de 128 bits, ou être analysée comme deux éléments de domaine de tour de 64 bits, quatre éléments de domaine de tour de 32 bits, seize éléments de domaine de tour de 8 bits, ou 128 éléments de domaine F2. Cette flexibilité de représentation n'implique aucun coût de calcul, il s'agit simplement d'un typecast de la chaîne de bits (typecast), ce qui est une propriété très intéressante et utile. Parallèlement, les éléments de petits domaines peuvent être empaquetés en éléments de domaine plus grands sans coût de calcul supplémentaire. Le protocole Binius tire parti de cette caractéristique pour améliorer l'efficacité 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 mise au carré et d'inversion dans un domaine binaire de tour de n bits pouvant être décomposé en un sous-domaine de m bits (.
![Bitlayer Research : Analyse des principes STARKs de Binius et réflexions sur son optimisation])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 2.2 PIOP: version modifiée du produit HyperPlonk et Vérification de permutation ------ applicable aux corps binaires
La conception de PIOP dans le protocole Binius s'inspire de HyperPlonk et utilise une série de mécanismes de vérification essentiels pour valider la correctitude des polynômes et des ensembles multivariés. Ces vérifications essentielles incluent :
GateCheck : vérifier si le témoin confidentiel ω 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 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 du polynôme.
LookupCheck : vérifie si l'évaluation du polynôme se trouve dans la table de recherche donnée, c'est-à-dire f(Bµ) ⊆ T)Bµ(, garantissant que certaines valeurs se situent dans la plage spécifiée.
MultisetCheck: Vérifie si deux ensembles multivariables sont égaux, c'est-à-dire {)x1,i,x2,(}i∈H={)y1,i,y2,(}i∈H, garantissant la cohérence entre plusieurs ensembles.
ProductCheck : Vérifiez si l'évaluation d'un polynôme rationnel sur le cube hyperbolique booléen est égale à une valeur déclarée ∏x∈Hµ f)x( = s, afin d'assurer la validité du produit polynômial.
ZeroCheck : vérifier si un polynôme multivariable est nul à n'importe quel point 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é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 à une variable, cela réduit la complexité de calcul pour le vérificateur. De plus, SumCheck permet le traitement par lots en introduisant des nombres aléatoires pour construire des combinaisons linéaires, permettant ainsi le traitement par lots de plusieurs instances de vérification de somme.
BatchCheck : Basé sur SumCheck, vérifie l'exactitude de l'évaluation de plusieurs polynômes multivariables afin d'améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk aient de nombreuses similitudes dans la conception du protocole, Binius a amélioré les 3 aspects suivants :
Optimisation de ProductCheck : Dans HyperPlonk, ProductCheck exige que le dénominateur U soit non nul partout sur l'hypercube, et que le produit doit ê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.
Gestion du problème de division par zéro : HyperPlonk n'a pas su traiter correctement les cas de division par zéro, ce qui empêche d'affirmer que U est non nul sur l'hypercube ; Binius a correctement traité ce problème, même lorsque le dénominateur est nul, le ProductCheck de Binius peut continuer à fonctionner, permettant une généralisation à n'importe quelle valeur de produit.
Vérification de permutation intercolonnes : HyperPlonk ne prend pas en charge cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de gérer des cas de réarrangement 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 la validation de polynômes multivariés plus complexes, offrant un soutien fonctionnel plus fort. Ces améliorations résolvent non seulement les limitations de HyperPlonk, mais posent également les bases pour de futurs systèmes de preuve basés sur des domaines binaires.
) 2.3 PIOP : nouvel argument de décalage multilinéaire ------ applicable au cube hyperbolique booléen
Dans le protocole Binius, la construction et le traitement des polynômes virtuels sont l'une des technologies clés, permettant de générer et d'opérer efficacement des polynômes dérivés de poignées d'entrée ou d'autres polynômes virtuels. Voici deux méthodes clés :
Packing: Cette méthode consiste à prendre le plus petit des emplacements adjacents dans l'ordre du dictionnaire.
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.
17 J'aime
Récompense
17
8
Partager
Commentaire
0/400
MetaverseHermit
· 07-25 11:05
Ah, c'est vrai que cette compression de données est un peu trop sévère, non ?
Voir l'originalRépondre0
HallucinationGrower
· 07-23 22:02
Qui comprend, plus on modifie, plus c'est lent.
Voir l'originalRépondre0
WalletAnxietyPatient
· 07-23 04:46
Frères, j'ai étudié pendant trois jours et je ne comprends toujours pas le hash.
Voir l'originalRépondre0
ContractFreelancer
· 07-23 04:46
C'est un peu complexe. Apprenons d'abord à dessiner des cercles avant d'en parler.
Voir l'originalRépondre0
LiquidityWitch
· 07-23 04:39
ah, en train de brasser un peu de magie noire avec ces starks... enfin, quelqu'un lit les anciens rouleaux tbh
Voir l'originalRépondre0
LiquidationWatcher
· 07-23 04:37
cela ressemble à la fusion eth de 2022... avancez avec prudence les amis
Voir l'originalRépondre0
FlippedSignal
· 07-23 04:33
L'encodage de la largeur de bit diminue progressivement bull ah
Voir l'originalRépondre0
NestedFox
· 07-23 04:22
Le problème de l'inefficacité n'a toujours pas été résolu.
Binius STARKs : un nouveau système de preuve efficace basé sur des domaines binaires
Analyse des principes des STARKs Binius et réflexions sur leur optimisation
1 Introduction
Différent des SNARKs basés sur les courbes elliptiques, les STARKs peuvent être considérés comme des SNARKs basés sur le hachage. Une des principales raisons de l'inefficacité actuelle des STARKs est que la plupart des valeurs numériques dans les programmes réels sont relativement petites, comme les index dans les boucles for, les valeurs de vérité, les compteurs, etc. Cependant, pour garantir la sécurité des preuves basées sur l'arbre de Merkle, de nombreuses valeurs de redondance supplémentaires occupent tout le domaine lors de l'expansion des données à l'aide du codage de Reed-Solomon, même si la valeur d'origine 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 de la première génération de STARKs est de 252 bits, celle de la deuxième génération de STARKs est de 64 bits, et celle de la troisième génération de STARKs est de 32 bits, mais la largeur de code de 32 bits présente encore un grand nombre d'espaces gaspillés. En comparaison, le champ binaire permet d'opérer directement sur les bits, ce qui rend le codage compact et efficace sans aucun espace gaspillé, c'est-à-dire la quatrième génération de STARKs.
Comparé aux découvertes récentes de champs finis tels que Goldilocks, BabyBear et Mersenne31, la recherche sur le champ binaire remonte aux années 1980. Actuellement, le champ binaire est largement utilisé en cryptographie, des exemples typiques incluent :
Norme de chiffrement avancée ( AES ), basée sur le domaine F28;
Galois Code d'Authentification de Message ( 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, finaliste du SHA-3, qui est basée sur le domaine F28, une algorithme de hachage très adapté à 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 doit entièrement dépendre de l'extension de domaine pour assurer sa sécurité et sa praticité. La plupart des polynômes impliqués dans les calculs de Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais doivent simplement opérer sous le domaine de base, réalisant ainsi une haute efficacité dans un petit domaine. Cependant, les vérifications de points aléatoires et les calculs FRI doivent encore plonger dans un domaine d'extension plus grand pour garantir la sécurité requise.
Lors de la construction d'un système de preuve basé sur un domaine binaire, il existe 2 problèmes pratiques : lors du calcul de la représentation de trace dans les STARKs, la taille du domaine utilisée doit être supérieure au degré du polynôme ; lors de l'engagement de l'arbre Merkle dans les STARKs, il est nécessaire de faire un codage de Reed-Solomon, et la taille du domaine utilisée doit être supérieure à la taille après l'extension du codage.
Binius a proposé une solution innovante pour traiter ces deux problèmes, en représentant les mêmes données de deux manières différentes : tout d'abord, en utilisant un polynôme multivarié (, en particulier un polynôme multilinéraire ), au lieu d'un polynôme univarié, pour représenter l'ensemble de la trajectoire de calcul par ses valeurs sur des "hypercubes" ( ; ensuite, comme chaque dimension de l'hypercube a une longueur de 2, il n'est pas possible de réaliser une extension standard de Reed-Solomon comme avec les STARKs, mais l'hypercube peut être considéré comme un carré ), sur la base duquel une extension de Reed-Solomon peut être effectué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 théorique preuve d'oracle interactive polynomiale ( Information-Theoretic Polynomial Interactive Oracle Proof, PIOP ) : PIOP, en tant que système de preuve central, transforme les relations de calcul d'entrée en équations polynomiales vérifiables. Différents protocoles PIOP permettent au prouveur d'envoyer progressivement des polynômes grâce à une interaction avec le vérificateur, de sorte que le vérificateur 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, impactant ainsi les performances et l'efficacité de l'ensemble du système SNARK.
Schéma de compromis polynomial (Polynomial Commitment Scheme, PCS) : Le schéma de compromis polynomial est utilisé pour prouver si l'égalité polynomial générée par PIOP est valable. PCS est un outil cryptographique par lequel le prouveur peut s'engager sur un certain polynôme et vérifier plus tard le résultat de l'évaluation de ce polynôme, tout en cachant d'autres informations sur le polynôme. Les schémas de compromis 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 : combinant PLONK PIOP et Bulletproofs PCS, basé sur la courbe Pasta. Lors de la conception de Halo2, l'accent a été mis sur l'évolutivité et l'élimination de la configuration de confiance dans le protocole ZCash.
• Plonky2 : Utilise PLONK PIOP et FRI PCS combinés, et est 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 domaine fini ou à la courbe elliptique utilisés, 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'expansion telles que les preuves récursives ou les preuves agrégées.
Binius: HyperPlonk PIOP + Brakedown PCS + domaines binaires. Plus précisément, Binius comprend cinq technologies clés pour réaliser son efficacité et sa sécurité. Tout d'abord, l'arithmétique basée sur les tours de domaines binaires (towers of binary fields) constitue la base de ses calculs, permettant d'effectuer des opérations simplifiées dans les domaines binaires. Deuxièmement, Binius adapte les vérifications de produits et de permutations de HyperPlonk dans son protocole de preuve Oracle interactif (PIOP), garantissant une vérification de la cohérence sécurisée et efficace entre les variables et leurs permutations. Troisièmement, le protocole introduit une nouvelle preuve de décalage multilinéraire, optimisant l'efficacité de la 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é renforcée pour le mécanisme de recherche. Enfin, le protocole utilise un schéma d'engagement polynomial sur de petits domaines (Small-Field PCS), lui permettant d'implémenter un système de preuve efficace dans le domaine binaire et réduisant les frais généralement associés aux grands domaines.
( 2.1 Corps finis : arithmétisation basée sur les tours de corps binaires
Les corps binaires en tour sont la clé pour réaliser des calculs vérifiables rapides, principalement en raison de deux aspects : le calcul efficace et l'arithmétisation efficace. Les corps binaires soutiennent essentiellement des opérations arithmétiques hautement efficaces, ce qui en fait un choix idéal pour les applications cryptographiques sensibles aux performances. De plus, la structure des corps binaires supporte un processus d'arithmétisation simplifié, c'est-à-dire que les opérations effectuées sur le corps binaire peuvent être représentées sous une forme algébrique compacte et facile à vérifier. Ces caractéristiques, combinées à la capacité de tirer pleinement parti de ses 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 champ binaire. Par exemple, dans le champ binaire de base F2, toute 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 offrir cette représentation canonique dans un nombre de bits donné. Bien qu'un champ premier de 32 bits puisse être contenu dans 32 bits, cela ne signifie pas que chaque chaîne de 32 bits correspond de manière unique à un élément de champ, tandis que le champ binaire possède cette commodité d'une correspondance un à un. Dans le champ premier Fp, les méthodes de réduction courantes incluent la réduction Barrett, la réduction Montgomery, ainsi que des méthodes de réduction spécifiques pour des champs finis particuliers 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 ) utilisée dans AES ###, la réduction 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" souligne 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 illustré dans la figure 1, une chaîne de 128 bits : cette chaîne peut être interprétée de plusieurs manières dans le contexte des domaines binaires. Elle peut être considérée comme un élément unique dans un domaine binaire de 128 bits, ou être analysée comme deux éléments de domaine de tour de 64 bits, quatre éléments de domaine de tour de 32 bits, seize éléments de domaine de tour de 8 bits, ou 128 éléments de domaine F2. Cette flexibilité de représentation n'implique aucun coût de calcul, il s'agit simplement d'un typecast de la chaîne de bits (typecast), ce qui est une propriété très intéressante et utile. Parallèlement, les éléments de petits domaines peuvent être empaquetés en éléments de domaine plus grands sans coût de calcul supplémentaire. Le protocole Binius tire parti de cette caractéristique pour améliorer l'efficacité 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 mise au carré et d'inversion dans un domaine binaire de tour de n bits pouvant être décomposé en un sous-domaine de m bits (.
![Bitlayer Research : Analyse des principes STARKs de Binius et réflexions sur son optimisation])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 2.2 PIOP: version modifiée du produit HyperPlonk et Vérification de permutation ------ applicable aux corps binaires
La conception de PIOP dans le protocole Binius s'inspire de HyperPlonk et utilise une série de mécanismes de vérification essentiels pour valider la correctitude des polynômes et des ensembles multivariés. Ces vérifications essentielles incluent :
GateCheck : vérifier si le témoin confidentiel ω 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 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 du polynôme.
LookupCheck : vérifie si l'évaluation du polynôme se trouve dans la table de recherche donnée, c'est-à-dire f(Bµ) ⊆ T)Bµ(, garantissant que certaines valeurs se situent dans la plage spécifiée.
MultisetCheck: Vérifie si deux ensembles multivariables sont égaux, c'est-à-dire {)x1,i,x2,(}i∈H={)y1,i,y2,(}i∈H, garantissant la cohérence entre plusieurs ensembles.
ProductCheck : Vérifiez si l'évaluation d'un polynôme rationnel sur le cube hyperbolique booléen est égale à une valeur déclarée ∏x∈Hµ f)x( = s, afin d'assurer la validité du produit polynômial.
ZeroCheck : vérifier si un polynôme multivariable est nul à n'importe quel point 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é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 à une variable, cela réduit la complexité de calcul pour le vérificateur. De plus, SumCheck permet le traitement par lots en introduisant des nombres aléatoires pour construire des combinaisons linéaires, permettant ainsi le traitement par lots de plusieurs instances de vérification de somme.
BatchCheck : Basé sur SumCheck, vérifie l'exactitude de l'évaluation de plusieurs polynômes multivariables afin d'améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk aient de nombreuses similitudes dans la conception du protocole, Binius a amélioré les 3 aspects suivants :
Optimisation de ProductCheck : Dans HyperPlonk, ProductCheck exige que le dénominateur U soit non nul partout sur l'hypercube, et que le produit doit ê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.
Gestion du problème de division par zéro : HyperPlonk n'a pas su traiter correctement les cas de division par zéro, ce qui empêche d'affirmer que U est non nul sur l'hypercube ; Binius a correctement traité ce problème, même lorsque le dénominateur est nul, le ProductCheck de Binius peut continuer à fonctionner, permettant une généralisation à n'importe quelle valeur de produit.
Vérification de permutation intercolonnes : HyperPlonk ne prend pas en charge cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de gérer des cas de réarrangement 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 la validation de polynômes multivariés plus complexes, offrant un soutien fonctionnel plus fort. Ces améliorations résolvent non seulement les limitations de HyperPlonk, mais posent également les bases pour de futurs systèmes de preuve basés sur des domaines binaires.
) 2.3 PIOP : nouvel argument de décalage multilinéaire ------ applicable au cube hyperbolique booléen
Dans le protocole Binius, la construction et le traitement des polynômes virtuels sont l'une des technologies clés, permettant de générer et d'opérer efficacement des polynômes dérivés de poignées d'entrée ou d'autres polynômes virtuels. Voici deux méthodes clés :