Analyse des principes de Binius STARKs et réflexion sur leur optimisation
1. Introduction
Une des principales raisons de l'inefficacité des STARKs est que la plupart des valeurs dans les programmes réels sont relativement petites, comme les indices dans les boucles for, les valeurs booléennes, les compteurs, etc. Cependant, pour garantir la sécurité des preuves basées sur les arbres de Merkle, l'utilisation du codage de Reed-Solomon pour étendre les données entraîne de nombreuses valeurs redondantes supplémentaires qui occupent 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é.
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 une grande quantité d'espace gaspillé. En comparaison, le domaine binaire permet d'opérer directement sur les bits, offrant 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 80 du siècle dernier. Actuellement, 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 le 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, 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 dépend entièrement de l'extension de domaine pour garantir sa sécurité et sa praticité. La plupart des polynômes impliqués dans les calculs Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais peuvent fonctionner sous le domaine de base, réalisant ainsi une grande efficacité dans un petit domaine. Cependant, les vérifications de points aléatoires et les calculs FRI doivent encore plonger dans une extension de domaine plus grande pour garantir le niveau de sécurité requis.
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 dans les STARKs, un codage de Reed-Solomon doit être effectué, et la taille du domaine utilisée doit être supérieure à la taille après extension du codage.
Binius a proposé une solution innovante qui traite ces deux problèmes de manière distincte et permet de représenter les mêmes données de deux manières différentes : tout d'abord, en utilisant un polynôme multilinéraire ( au lieu d'un polynôme à variable unique, représentant ainsi l'ensemble de la trajectoire de calcul par ses valeurs sur les hypercubes "hyper-cubes" ) ; ensuite, étant donné que la longueur de chaque dimension de l'hypercube est de 2, il n'est pas possible d'effectuer une extension de Reed-Solomon standard comme avec les STARKs, mais on peut considérer l'hypercube comme un carré (, basé sur lequel on réalise une extension de Reed-Solomon. 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 :
Preuve d'oracle interactive polynomiale d'information théorique )Information-Theoretic Polynomial Interactive Oracle Proof, PIOP(: En tant que système de preuve central, PIOP transforme les relations de calcul d'entrée en égalités polynomiales vérifiables. Différents protocoles PIOP permettent au prouveur d'envoyer progressivement des polynômes par interaction avec le vérificateur, permettant à ce dernier de vérifier si le calcul est correct en interrogeant peu de résultats d'évaluation des polynômes. Les protocoles PIOP existants incluent: PLONK PIOP, Spartan PIOP et HyperPlonk PIOP, qui traitent chacun les expressions polynomiales de manière différente, affectant ainsi les performances et l'efficacité de l'ensemble du système SNARK.
Schéma d'engagement polynomial )Polynomial Commitment Scheme, PCS( : Le schéma d'engagement polynomial est utilisé pour prouver si l'égalité polynomiale générée par PIOP est valide. Le PCS est un outil cryptographique grâce auquel le prouveur peut s'engager sur un certain polynôme et valider ultérieurement le résultat d'é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 présentent des performances, une sécurité et des cas d'utilisation variés.
Selon les besoins spécifiques, choisissez différents PIOP et PCS, et combinez-les avec un domaine fini ou une courbe elliptique appropriée, vous pouvez construire des systèmes de preuve avec des attributs différents. Par exemple:
• Halo2 : combinant PLONK PIOP et Bulletproofs PCS, et basé sur la courbe Pasta. Halo2 est conçu en mettant l'accent sur l'évolutivité et sur l'élimination de la configuration de confiance dans le protocole ZCash.
• Plonky2 : adopte 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, les PIOP et 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 des preuves de SNARK et l'efficacité de la vérification, mais détermine également si le système peut réaliser 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 + champs binaires. Plus précisément, Binius comprend cinq technologies clés pour réaliser son efficacité et sa sécurité. Tout d'abord, l'arithmétisation 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 champ binaire. Ensuite, Binius a adapté la vérification de produit et de permutation de HyperPlonk dans son protocole de preuve Oracle interactive )PIOP(, garantissant une vérification de cohérence sûre 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 champs. Quatrièmement, Binius utilise une version améliorée de la preuve de recherche Lasso, offrant flexibilité et sécurité solide au mécanisme de recherche. Enfin, le protocole utilise un schéma d'engagement polynomial sur de petits champs )Small-Field PCS(, lui permettant de réaliser un système de preuve efficace sur le champ binaire et réduisant les coûts généralement associés aux grands champs.
) 2.1 Corps finis : arithmétisation basée sur les tours de champs binaires
Les corps binaires en tour sont essentiels pour la réalisation de calculs rapides et vérifiables, 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 prend en charge 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é d'exploiter pleinement ses caractéristiques hiérarchiques par le biais de la structure de tour, rendent les corps binaires particulièrement adaptés à des systèmes de preuve évolutifs tels que Binius.
Le terme "canonical" désigne la représentation unique et directe d'un élément dans un corps binaire. Par exemple, dans le corps binaire 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 premiers, qui ne peuvent pas offrir cette représentation standard dans un nombre de bits donné. Bien qu'un corps premier de 32 bits puisse être contenu dans 32 bits, il n'est pas vrai que chaque chaîne de 32 bits correspond de manière unique à un élément de corps, alors que le corps binaire offre cette commodité de correspondance 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 comme 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" souligne que le corps binaire ne nécessite pas d'introduire des retenues 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 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 d'un domaine binaire. Elle peut être considérée comme un élément unique dans un domaine binaire de 128 bits, ou être interprété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 ne nécessite aucun coût de calcul, c'est simplement une conversion de type de chaîne de bits )typecast(, ce qui est une propriété très intéressante et utile. De plus, les petits éléments de domaine peuvent être 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. En outre, l'article "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité calculatoire 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 sous-domaines de m bits (.
![Bitlayer Research : Analyse du principe des STARKs de Binius et réflexion 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 domaines binaires
La conception de PIOP dans le protocole Binius s'inspire de HyperPlonk et utilise une série de mécanismes de vérification essentiels pour valider l'exactitude des polynômes et des ensembles multivariés. Ces vérifications essentielles comprennent :
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érifier si les résultats d'évaluation des deux polynômes multivariables f et g sur le cube hyperbolique booléen sont une relation de permutation f###x( = f)π(x)(, afin d'assurer la cohérence des permutations entre les variables des polynômes.
LookupCheck : Vérifier si l'évaluation du polynôme est dans la table de recherche donnée, c'est-à-dire f(Bµ) ⊆ T)Bµ(, s'assurer que certaines valeurs se 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 des polynômes rationnels sur le cube hyperbolique booléen est égale à une valeur déclarée ∏x∈Hµ f)x( = s, afin de garantir la validité du produit polynômial.
ZeroCheck : vérifier si un polynôme multivarié est nul à un point quelconque sur le cube hyperbolique booléen ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, afin de garantir la distribution des zéros du polynôme.
SumCheck : Vérifie si la somme d'un polynôme multivarié est égale à la valeur déclarée ∑x∈Hµ f)x( = s. En transformant le problème d'évaluation de polynôme multivarié en évaluation de polynôme univarié, 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 et traiter plusieurs instances de vérification de sommes.
BatchCheck : basé sur SumCheck, valide la justesse de l'évaluation de plusieurs polynômes multivariables afin d'améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk présentent de nombreuses similitudes dans la conception des protocoles, 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 partout sur l'hypercube, et 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 réussi à traiter adéquatement les cas de division par zéro, ce qui rend impossible d'affirmer que U est non nul sur l'hypercube ; Binius a correctement géré ce problème, même lorsque le dénominateur est zéro, le ProductCheck de Binius peut continuer à traiter, permettant une généralisation à toute 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 traiter des cas de permutations polynomiales plus complexes.
Ainsi, Binius a amélioré la flexibilité et l'efficacité du protocole grâce à des améliorations du mécanisme existant PIOPSumCheck, en offrant un support fonctionnel plus puissant, notamment lors du traitement de validations de polynômes multivariés plus complexes. Ces améliorations non seulement résolvent les limitations dans HyperPlonk, mais établissent également une base pour les futurs systèmes de preuves basés sur des corps binaires.
![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 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 est
Voir l'original
Cette page peut inclure du contenu de tiers fourni à des fins d'information uniquement. Gate ne garantit ni l'exactitude ni la validité de ces contenus, n’endosse pas les opinions exprimées, et ne fournit aucun conseil financier ou professionnel à travers ces informations. Voir la section Avertissement pour plus de détails.
7 J'aime
Récompense
7
4
Reposter
Partager
Commentaire
0/400
zkProofInThePudding
· Il y a 16h
La largeur a encore été compressée, bull.
Voir l'originalRépondre0
GweiWatcher
· 08-11 10:29
On dirait que c'est encore trop de gaspillage.
Voir l'originalRépondre0
MerkleDreamer
· 08-11 10:27
Vraiment gaspiller...
Voir l'originalRépondre0
LayerZeroHero
· 08-11 10:12
Zut, cette optimisation est vraiment trop difficile.
Binius STARKs : applications innovantes et optimisation des performances dans le domaine binaire
Analyse des principes de Binius STARKs et réflexion sur leur optimisation
1. Introduction
Une des principales raisons de l'inefficacité des STARKs est que la plupart des valeurs dans les programmes réels sont relativement petites, comme les indices dans les boucles for, les valeurs booléennes, les compteurs, etc. Cependant, pour garantir la sécurité des preuves basées sur les arbres de Merkle, l'utilisation du codage de Reed-Solomon pour étendre les données entraîne de nombreuses valeurs redondantes supplémentaires qui occupent 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é.
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 une grande quantité d'espace gaspillé. En comparaison, le domaine binaire permet d'opérer directement sur les bits, offrant 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 80 du siècle dernier. Actuellement, 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 le 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, 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 dépend entièrement de l'extension de domaine pour garantir sa sécurité et sa praticité. La plupart des polynômes impliqués dans les calculs Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais peuvent fonctionner sous le domaine de base, réalisant ainsi une grande efficacité dans un petit domaine. Cependant, les vérifications de points aléatoires et les calculs FRI doivent encore plonger dans une extension de domaine plus grande pour garantir le niveau de sécurité requis.
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 dans les STARKs, un codage de Reed-Solomon doit être effectué, et la taille du domaine utilisée doit être supérieure à la taille après extension du codage.
Binius a proposé une solution innovante qui traite ces deux problèmes de manière distincte et permet de représenter les mêmes données de deux manières différentes : tout d'abord, en utilisant un polynôme multilinéraire ( au lieu d'un polynôme à variable unique, représentant ainsi l'ensemble de la trajectoire de calcul par ses valeurs sur les hypercubes "hyper-cubes" ) ; ensuite, étant donné que la longueur de chaque dimension de l'hypercube est de 2, il n'est pas possible d'effectuer une extension de Reed-Solomon standard comme avec les STARKs, mais on peut considérer l'hypercube comme un carré (, basé sur lequel on réalise une extension de Reed-Solomon. 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 :
Preuve d'oracle interactive polynomiale d'information théorique )Information-Theoretic Polynomial Interactive Oracle Proof, PIOP(: En tant que système de preuve central, PIOP transforme les relations de calcul d'entrée en égalités polynomiales vérifiables. Différents protocoles PIOP permettent au prouveur d'envoyer progressivement des polynômes par interaction avec le vérificateur, permettant à ce dernier de vérifier si le calcul est correct en interrogeant peu de résultats d'évaluation des polynômes. Les protocoles PIOP existants incluent: PLONK PIOP, Spartan PIOP et HyperPlonk PIOP, qui traitent chacun les expressions polynomiales de manière différente, affectant ainsi les performances et l'efficacité de l'ensemble du système SNARK.
Schéma d'engagement polynomial )Polynomial Commitment Scheme, PCS( : Le schéma d'engagement polynomial est utilisé pour prouver si l'égalité polynomiale générée par PIOP est valide. Le PCS est un outil cryptographique grâce auquel le prouveur peut s'engager sur un certain polynôme et valider ultérieurement le résultat d'é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 présentent des performances, une sécurité et des cas d'utilisation variés.
Selon les besoins spécifiques, choisissez différents PIOP et PCS, et combinez-les avec un domaine fini ou une courbe elliptique appropriée, vous pouvez construire des systèmes de preuve avec des attributs différents. Par exemple:
• Halo2 : combinant PLONK PIOP et Bulletproofs PCS, et basé sur la courbe Pasta. Halo2 est conçu en mettant l'accent sur l'évolutivité et sur l'élimination de la configuration de confiance dans le protocole ZCash.
• Plonky2 : adopte 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, les PIOP et 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 des preuves de SNARK et l'efficacité de la vérification, mais détermine également si le système peut réaliser 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 + champs binaires. Plus précisément, Binius comprend cinq technologies clés pour réaliser son efficacité et sa sécurité. Tout d'abord, l'arithmétisation 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 champ binaire. Ensuite, Binius a adapté la vérification de produit et de permutation de HyperPlonk dans son protocole de preuve Oracle interactive )PIOP(, garantissant une vérification de cohérence sûre 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 champs. Quatrièmement, Binius utilise une version améliorée de la preuve de recherche Lasso, offrant flexibilité et sécurité solide au mécanisme de recherche. Enfin, le protocole utilise un schéma d'engagement polynomial sur de petits champs )Small-Field PCS(, lui permettant de réaliser un système de preuve efficace sur le champ binaire et réduisant les coûts généralement associés aux grands champs.
) 2.1 Corps finis : arithmétisation basée sur les tours de champs binaires
Les corps binaires en tour sont essentiels pour la réalisation de calculs rapides et vérifiables, 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 prend en charge 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é d'exploiter pleinement ses caractéristiques hiérarchiques par le biais de la structure de tour, rendent les corps binaires particulièrement adaptés à des systèmes de preuve évolutifs tels que Binius.
Le terme "canonical" désigne la représentation unique et directe d'un élément dans un corps binaire. Par exemple, dans le corps binaire 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 premiers, qui ne peuvent pas offrir cette représentation standard dans un nombre de bits donné. Bien qu'un corps premier de 32 bits puisse être contenu dans 32 bits, il n'est pas vrai que chaque chaîne de 32 bits correspond de manière unique à un élément de corps, alors que le corps binaire offre cette commodité de correspondance 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 comme 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" souligne que le corps binaire ne nécessite pas d'introduire des retenues 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 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 d'un domaine binaire. Elle peut être considérée comme un élément unique dans un domaine binaire de 128 bits, ou être interprété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 ne nécessite aucun coût de calcul, c'est simplement une conversion de type de chaîne de bits )typecast(, ce qui est une propriété très intéressante et utile. De plus, les petits éléments de domaine peuvent être 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. En outre, l'article "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité calculatoire 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 sous-domaines de m bits (.
![Bitlayer Research : Analyse du principe des STARKs de Binius et réflexion 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 domaines binaires
La conception de PIOP dans le protocole Binius s'inspire de HyperPlonk et utilise une série de mécanismes de vérification essentiels pour valider l'exactitude des polynômes et des ensembles multivariés. Ces vérifications essentielles comprennent :
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érifier si les résultats d'évaluation des deux polynômes multivariables f et g sur le cube hyperbolique booléen sont une relation de permutation f###x( = f)π(x)(, afin d'assurer la cohérence des permutations entre les variables des polynômes.
LookupCheck : Vérifier si l'évaluation du polynôme est dans la table de recherche donnée, c'est-à-dire f(Bµ) ⊆ T)Bµ(, s'assurer que certaines valeurs se 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 des polynômes rationnels sur le cube hyperbolique booléen est égale à une valeur déclarée ∏x∈Hµ f)x( = s, afin de garantir la validité du produit polynômial.
ZeroCheck : vérifier si un polynôme multivarié est nul à un point quelconque sur le cube hyperbolique booléen ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, afin de garantir la distribution des zéros du polynôme.
SumCheck : Vérifie si la somme d'un polynôme multivarié est égale à la valeur déclarée ∑x∈Hµ f)x( = s. En transformant le problème d'évaluation de polynôme multivarié en évaluation de polynôme univarié, 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 et traiter plusieurs instances de vérification de sommes.
BatchCheck : basé sur SumCheck, valide la justesse de l'évaluation de plusieurs polynômes multivariables afin d'améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk présentent de nombreuses similitudes dans la conception des protocoles, 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 partout sur l'hypercube, et 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 réussi à traiter adéquatement les cas de division par zéro, ce qui rend impossible d'affirmer que U est non nul sur l'hypercube ; Binius a correctement géré ce problème, même lorsque le dénominateur est zéro, le ProductCheck de Binius peut continuer à traiter, permettant une généralisation à toute 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 traiter des cas de permutations polynomiales plus complexes.
Ainsi, Binius a amélioré la flexibilité et l'efficacité du protocole grâce à des améliorations du mécanisme existant PIOPSumCheck, en offrant un support fonctionnel plus puissant, notamment lors du traitement de validations de polynômes multivariés plus complexes. Ces améliorations non seulement résolvent les limitations dans HyperPlonk, mais établissent également une base pour les futurs systèmes de preuves basés sur des corps binaires.
![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 des polynômes dérivés de poignées d'entrée ou d'autres polynômes virtuels. Voici deux méthodes clés :