Analyse des principes des STARKs de Binius et réflexion sur leur optimisation
1 Introduction
Contrairement aux SNARKs basés sur les courbes elliptiques, les STARKs peuvent être considérés comme des SNARKs basés sur le hachage. Actuellement, l'une des principales raisons pour lesquelles les STARKs sont peu efficaces 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 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 nombreux valeurs redondantes supplémentaires occupant tout le domaine, même si la valeur originale elle-même est très petite. Pour résoudre ce problème, réduire la taille du domaine est devenu une stratégie clé.
La largeur de codage des STARKs de première génération est de 252 bits, celle de deuxième génération est de 64 bits, et celle de troisième génération est de 32 bits. Cependant, la largeur de codage de 32 bits présente encore un grand gaspillage d'espace. En revanche, le domaine binaire permet d'opérer directement sur les bits, le codage est compact et efficace sans aucun gaspillage d'espace, pouvant être considéré comme la quatrième génération de STARKs.
Comparé aux découvertes de recherche récentes telles que Goldilocks, BabyBear, Mersenne31 et d'autres corps finis, la recherche sur les corps binaires remonte aux années 1980. Actuellement, les corps binaires sont largement utilisés en cryptographie, des exemples typiques incluent :
Norme de cryptage avancée ( AES ), basé sur le domaine F28
Galois Message Authentication Code ( GMAC ), basé sur le domaine F2128
Code QR, utilisant un codage Reed-Solomon basé sur F28
Le protocole FRI original et le protocole zk-STARK, ainsi que la fonction de hachage Grøstl, finaliste du SHA-3, qui est basée sur le domaine F28, sont des algorithmes de hachage très adaptés à la récursivité.
Lorsque des domaines plus petits sont utilisés, l'opération d'extension de domaine devient de plus en plus importante pour garantir la sécurité. Le domaine binaire utilisé par Binius doit entièrement s'appuyer sur l'extension de domaine pour assurer sa sécurité et sa praticité. La plupart des polynômes impliqués dans le calcul des Prover n'ont pas besoin d'entrer dans l'extension de domaine et peuvent simplement opérer sous le domaine de base, permettant ainsi d'atteindre une grande efficacité dans les petits domaines. 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é nécessaire.
Lors de la construction d'un système de preuve basé sur un domaine binaire, deux problèmes pratiques existent : 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 de Merkle dans les STARKs, un encodage de Reed-Solomon doit être effectué, et la taille du domaine utilisée doit être supérieure à la taille après extension de l'encodage.
Binius a proposé une solution innovante pour traiter ces deux problèmes de manière distincte et représenter les mêmes données de deux manières différentes : tout d'abord, en utilisant des polynômes multivariés (, spécifiquement des polynômes multilinaires ), pour remplacer les polynômes univariés, en représentant l'ensemble de la trajectoire de calcul par leurs valeurs sur des "hypercubes" ( ; ensuite, étant donné que chaque dimension de l'hypercube a une longueur de 2, il n'est pas possible d'effectuer une extension standard de Reed-Solomon comme avec les STARKs, mais on peut considérer l'hypercube comme un carré ), et effectuer l'extension de Reed-Solomon basée sur ce carré. Cette méthode améliore considérablement l'efficacité du codage et la performance de calcul tout en assurant 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 Oracle Interactive Polynomiale Information-Théorique (Information-Théorique Polynomial Interactive Oracle Proof, PIOP) : PIOP, en tant que système de preuve central, transforme la relation de calcul d'entrée en égalités polynomiales vérifiables. Différents protocoles PIOP, grâce à leur interaction avec le vérificateur, permettent au prouveur d'envoyer progressivement des polynômes, permettant ainsi au vérificateur de valider si le calcul est correct en interrogeant un nombre limité de résultats d'évaluation de polynômes. Les protocoles PIOP existants incluent : PLONK PIOP, Spartan PIOP et HyperPlonk PIOP, qui traitent chacun les expressions polynomiales de manière différente, affectant ainsi la performance et l'efficacité de l'ensemble du système SNARK.
Schéma d'engagement polynomial (Polynomial Commitment Scheme, PCS) : Un schéma d'engagement polynomial est utilisé pour prouver si les égalités polynomiales générées par PIOP sont valides. Le PCS est un outil cryptographique qui permet à un prouveur de s'engager sur un certain polynôme et de vérifier plus tard les résultats d'évaluation de ce polynôme tout en cachant d'autres informations sur le polynôme. Les schémas d'engagement polynomial les plus courants incluent KZG, Bulletproofs, FRI(Fast Reed-Solomon IOPP) et Brakedown, etc. Différents PCS ont des performances, des niveaux de 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. Halo2 a été conçu en mettant l'accent sur l'évolutivité et en éliminant la configuration de confiance dans le protocole ZCash.
• Plonky2 : adopte PLONK PIOP et FRI PCS combinés, basés 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 champ fini ou à la courbe elliptique utilisés, afin de garantir la correction, la performance et la sécurité du système. Le choix de ces combinaisons influence non seulement la taille de la preuve SNARK et l'efficacité de la vérification, mais détermine également si le système peut réaliser la transparence sans configuration de confiance préalable, et s'il peut prendre en charge des fonctionnalités d'extension telles que les preuves récursives ou les preuves agrégées.
Binius : HyperPlonk PIOP + Brakedown PCS + 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 son calcul, permettant d'effectuer des opérations simplifiées dans le champ binaire. Deuxièmement, Binius a adapté la vérification de produit et de permutation de HyperPlonk dans son protocole de preuve d'oracle interactif (PIOP), garantissant une vérification cohérente sécurisée et efficace entre les variables et leurs permutations. Troisièmement, le protocole introduit une nouvelle preuve de décalage 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é robustes au mécanisme de recherche. Enfin, le protocole utilise un schéma d'engagement polynomial sur de petits domaines (Small-Field PCS), lui permettant de réaliser un système de preuve efficace sur le champ binaire, tout en réduisant les coûts généralement associés aux grands domaines.
( 2.1 Domain fini : arithmétique basée sur les tours de champs 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étique efficace. Les corps binaires soutiennent essentiellement des opérations arithmétiques très efficaces, ce qui les rend idéaux 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 des 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 ses caractéristiques hiérarchiques grâce à la structure en tour, rendent les corps binaires particulièrement adaptés aux systèmes de preuve évolutifs tels que Binius.
Le terme "canonical" fait référence à la représentation unique et directe des éléments dans un domaine binaire. Par exemple, dans le domaine binaire le plus simple F2, n'importe quelle chaîne de k bits peut être directement mappée à un élément du domaine binaire de k bits. Cela diffère des domaines premiers, qui ne peuvent pas fournir cette représentation canonique dans un nombre de bits donné. Bien qu'un domaine 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 du domaine, tandis que le domaine binaire offre cette commodité de correspondance un à un. Dans le domaine 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 domaines finis spécifiques comme Mersenne-31 ou Goldilocks-64. Dans le domaine binaire F2k, les méthodes de réduction courantes incluent la réduction spéciale ) utilisée dans AES ###, la réduction de Montgomery ( utilisée dans POLYVAL ) et la réduction récursive ( comme Tower ). L'article "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" indique que le domaine 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 domaine binaire est très efficace car elle suit la règle simplifiée (X + Y )2 = X2 + Y 2.
Comme indiqué dans la Figure 1, une chaîne de 128 bits : cette chaîne peut être interprétée de plusieurs manières dans le contexte du domaine binaire. 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 ne nécessite aucun coût de calcul, il s'agit simplement d'un changement de type de chaîne de bits (typecast), ce qui est une propriété très intéressante et utile. De plus, les éléments de petit 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, le document "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité de calcul pour effectuer des opérations de multiplication, de carré et d'inversion dans un domaine binaire de tour de n bits décomposable en un sous-domaine de m bits (.
![Bitlayer Research : Analyse des principes de Binius STARKs 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 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 fondamentaux pour valider l'exactitude des polynômes et des ensembles multivariés. Ces vérifications fondamentales 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 constituent une relation de permutation f###x( = f)π(x)(, afin d'assurer la cohérence des permutations entre les variables du polynôme.
LookupCheck : Vérifie si l'évaluation du polynôme est dans la table de recherche donnée, c'est-à-dire f(Bµ) ⊆ T)Bµ(, s'assurant que certaines valeurs se trouvent dans la plage spécifiée.
MultisetCheck : Vérifie si deux ensembles multivariables sont égaux, c'est-à-dire {)x1,i,x2,(}i∈H={)y1,i,y2,(}i∈H, garantissant la cohérence entre plusieurs ensembles.
ProductCheck : vérifier si l'évaluation d'un polynôme rationnel sur le cube hyperbolique booléen est égale à une valeur déclarée ∏x∈Hµ f)x( = s, afin de garantir l'exactitude du produit polynômial.
ZeroCheck : vérifier si un polynôme multivariable est nul à un point quelconque sur l'hypercube booléen ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, afin de 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 de polynôme multivariable en un problème d'évaluation de polynôme à variable unique, cela réduit la complexité de calcul pour le vérificateur. De plus, SumCheck permet le traitement par lot en introduisant des nombres aléatoires, construisant des combinaisons linéaires pour réaliser le traitement par lot de plusieurs instances de vérification de somme.
BatchCheck : basé sur SumCheck, vérifie 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 le cube hypercube, et que le produit soit égal à une valeur spécifique ; Binius simplifie ce processus de vérification en spécialisant cette valeur à 1, réduisant ainsi la complexité de calcul.
Traitement du problème de division par zéro : HyperPlonk n'a pas réussi à gérer 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 inter-colonnes : HyperPlonk n'a pas cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de gérer des situations de permutation polynomiale plus complexes.
Ainsi, Binius a amélioré la flexibilité et l'efficacité du protocole en modifiant le mécanisme PIOPSumCheck existant, offrant un meilleur support fonctionnel, notamment pour la vérification de polynômes multivariables plus complexes. Ces améliorations ne se contentent pas de résoudre les limitations de HyperPlonk, mais jettent également les bases pour de futurs systèmes de preuves basés sur des corps binaires.
![Bitlayer Research : Analyse des principes de Binius STARKs et réflexion sur leurs optimisations])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(
) 2.3 PIOP: nouvel argument de décalage multilinéraire------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 de manipuler efficacement des multiples dérivés de poignées d'entrée ou d'autres polynômes virtuels.
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.
Analyse des principes STARKs de Binius : innovation en domaine binaire et optimisation des performances
Analyse des principes des STARKs de Binius et réflexion sur leur optimisation
1 Introduction
Contrairement aux SNARKs basés sur les courbes elliptiques, les STARKs peuvent être considérés comme des SNARKs basés sur le hachage. Actuellement, l'une des principales raisons pour lesquelles les STARKs sont peu efficaces 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 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 nombreux valeurs redondantes supplémentaires occupant tout le domaine, même si la valeur originale elle-même est très petite. Pour résoudre ce problème, réduire la taille du domaine est devenu une stratégie clé.
La largeur de codage des STARKs de première génération est de 252 bits, celle de deuxième génération est de 64 bits, et celle de troisième génération est de 32 bits. Cependant, la largeur de codage de 32 bits présente encore un grand gaspillage d'espace. En revanche, le domaine binaire permet d'opérer directement sur les bits, le codage est compact et efficace sans aucun gaspillage d'espace, pouvant être considéré comme la quatrième génération de STARKs.
Comparé aux découvertes de recherche récentes telles que Goldilocks, BabyBear, Mersenne31 et d'autres corps finis, la recherche sur les corps binaires remonte aux années 1980. Actuellement, les corps binaires sont largement utilisés en cryptographie, des exemples typiques incluent :
Lorsque des domaines plus petits sont utilisés, l'opération d'extension de domaine devient de plus en plus importante pour garantir la sécurité. Le domaine binaire utilisé par Binius doit entièrement s'appuyer sur l'extension de domaine pour assurer sa sécurité et sa praticité. La plupart des polynômes impliqués dans le calcul des Prover n'ont pas besoin d'entrer dans l'extension de domaine et peuvent simplement opérer sous le domaine de base, permettant ainsi d'atteindre une grande efficacité dans les petits domaines. 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é nécessaire.
Lors de la construction d'un système de preuve basé sur un domaine binaire, deux problèmes pratiques existent : 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 de Merkle dans les STARKs, un encodage de Reed-Solomon doit être effectué, et la taille du domaine utilisée doit être supérieure à la taille après extension de l'encodage.
Binius a proposé une solution innovante pour traiter ces deux problèmes de manière distincte et représenter les mêmes données de deux manières différentes : tout d'abord, en utilisant des polynômes multivariés (, spécifiquement des polynômes multilinaires ), pour remplacer les polynômes univariés, en représentant l'ensemble de la trajectoire de calcul par leurs valeurs sur des "hypercubes" ( ; ensuite, étant donné que chaque dimension de l'hypercube a une longueur de 2, il n'est pas possible d'effectuer une extension standard de Reed-Solomon comme avec les STARKs, mais on peut considérer l'hypercube comme un carré ), et effectuer l'extension de Reed-Solomon basée sur ce carré. Cette méthode améliore considérablement l'efficacité du codage et la performance de calcul tout en assurant 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 Oracle Interactive Polynomiale Information-Théorique (Information-Théorique Polynomial Interactive Oracle Proof, PIOP) : PIOP, en tant que système de preuve central, transforme la relation de calcul d'entrée en égalités polynomiales vérifiables. Différents protocoles PIOP, grâce à leur interaction avec le vérificateur, permettent au prouveur d'envoyer progressivement des polynômes, permettant ainsi au vérificateur de valider si le calcul est correct en interrogeant un nombre limité de résultats d'évaluation de polynômes. Les protocoles PIOP existants incluent : PLONK PIOP, Spartan PIOP et HyperPlonk PIOP, qui traitent chacun les expressions polynomiales de manière différente, affectant ainsi la performance et l'efficacité de l'ensemble du système SNARK.
Schéma d'engagement polynomial (Polynomial Commitment Scheme, PCS) : Un schéma d'engagement polynomial est utilisé pour prouver si les égalités polynomiales générées par PIOP sont valides. Le PCS est un outil cryptographique qui permet à un prouveur de s'engager sur un certain polynôme et de vérifier plus tard les résultats d'évaluation de ce polynôme tout en cachant d'autres informations sur le polynôme. Les schémas d'engagement polynomial les plus courants incluent KZG, Bulletproofs, FRI(Fast Reed-Solomon IOPP) et Brakedown, etc. Différents PCS ont des performances, des niveaux de 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. Halo2 a été conçu en mettant l'accent sur l'évolutivité et en éliminant la configuration de confiance dans le protocole ZCash.
• Plonky2 : adopte PLONK PIOP et FRI PCS combinés, basés 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 champ fini ou à la courbe elliptique utilisés, afin de garantir la correction, la performance et la sécurité du système. Le choix de ces combinaisons influence non seulement la taille de la preuve SNARK et l'efficacité de la vérification, mais détermine également si le système peut réaliser la transparence sans configuration de confiance préalable, et s'il peut prendre en charge des fonctionnalités d'extension telles que les preuves récursives ou les preuves agrégées.
Binius : HyperPlonk PIOP + Brakedown PCS + 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 son calcul, permettant d'effectuer des opérations simplifiées dans le champ binaire. Deuxièmement, Binius a adapté la vérification de produit et de permutation de HyperPlonk dans son protocole de preuve d'oracle interactif (PIOP), garantissant une vérification cohérente sécurisée et efficace entre les variables et leurs permutations. Troisièmement, le protocole introduit une nouvelle preuve de décalage 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é robustes au mécanisme de recherche. Enfin, le protocole utilise un schéma d'engagement polynomial sur de petits domaines (Small-Field PCS), lui permettant de réaliser un système de preuve efficace sur le champ binaire, tout en réduisant les coûts généralement associés aux grands domaines.
( 2.1 Domain fini : arithmétique basée sur les tours de champs 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étique efficace. Les corps binaires soutiennent essentiellement des opérations arithmétiques très efficaces, ce qui les rend idéaux 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 des 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 ses caractéristiques hiérarchiques grâce à la structure en tour, rendent les corps binaires particulièrement adaptés aux systèmes de preuve évolutifs tels que Binius.
Le terme "canonical" fait référence à la représentation unique et directe des éléments dans un domaine binaire. Par exemple, dans le domaine binaire le plus simple F2, n'importe quelle chaîne de k bits peut être directement mappée à un élément du domaine binaire de k bits. Cela diffère des domaines premiers, qui ne peuvent pas fournir cette représentation canonique dans un nombre de bits donné. Bien qu'un domaine 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 du domaine, tandis que le domaine binaire offre cette commodité de correspondance un à un. Dans le domaine 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 domaines finis spécifiques comme Mersenne-31 ou Goldilocks-64. Dans le domaine binaire F2k, les méthodes de réduction courantes incluent la réduction spéciale ) utilisée dans AES ###, la réduction de Montgomery ( utilisée dans POLYVAL ) et la réduction récursive ( comme Tower ). L'article "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" indique que le domaine 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 domaine binaire est très efficace car elle suit la règle simplifiée (X + Y )2 = X2 + Y 2.
Comme indiqué dans la Figure 1, une chaîne de 128 bits : cette chaîne peut être interprétée de plusieurs manières dans le contexte du domaine binaire. 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 ne nécessite aucun coût de calcul, il s'agit simplement d'un changement de type de chaîne de bits (typecast), ce qui est une propriété très intéressante et utile. De plus, les éléments de petit 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, le document "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité de calcul pour effectuer des opérations de multiplication, de carré et d'inversion dans un domaine binaire de tour de n bits décomposable en un sous-domaine de m bits (.
![Bitlayer Research : Analyse des principes de Binius STARKs 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 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 fondamentaux pour valider l'exactitude des polynômes et des ensembles multivariés. Ces vérifications fondamentales 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 constituent une relation de permutation f###x( = f)π(x)(, afin d'assurer la cohérence des permutations entre les variables du polynôme.
LookupCheck : Vérifie si l'évaluation du polynôme est dans la table de recherche donnée, c'est-à-dire f(Bµ) ⊆ T)Bµ(, s'assurant que certaines valeurs se trouvent dans la plage spécifiée.
MultisetCheck : Vérifie si deux ensembles multivariables sont égaux, c'est-à-dire {)x1,i,x2,(}i∈H={)y1,i,y2,(}i∈H, garantissant la cohérence entre plusieurs ensembles.
ProductCheck : vérifier si l'évaluation d'un polynôme rationnel sur le cube hyperbolique booléen est égale à une valeur déclarée ∏x∈Hµ f)x( = s, afin de garantir l'exactitude du produit polynômial.
ZeroCheck : vérifier si un polynôme multivariable est nul à un point quelconque sur l'hypercube booléen ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, afin de 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 de polynôme multivariable en un problème d'évaluation de polynôme à variable unique, cela réduit la complexité de calcul pour le vérificateur. De plus, SumCheck permet le traitement par lot en introduisant des nombres aléatoires, construisant des combinaisons linéaires pour réaliser le traitement par lot de plusieurs instances de vérification de somme.
BatchCheck : basé sur SumCheck, vérifie 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 le cube hypercube, et que le produit soit égal à une valeur spécifique ; Binius simplifie ce processus de vérification en spécialisant cette valeur à 1, réduisant ainsi la complexité de calcul.
Traitement du problème de division par zéro : HyperPlonk n'a pas réussi à gérer 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 inter-colonnes : HyperPlonk n'a pas cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de gérer des situations de permutation polynomiale plus complexes.
Ainsi, Binius a amélioré la flexibilité et l'efficacité du protocole en modifiant le mécanisme PIOPSumCheck existant, offrant un meilleur support fonctionnel, notamment pour la vérification de polynômes multivariables plus complexes. Ces améliorations ne se contentent pas de résoudre les limitations de HyperPlonk, mais jettent également les bases pour de futurs systèmes de preuves basés sur des corps binaires.
![Bitlayer Research : Analyse des principes de Binius STARKs et réflexion sur leurs optimisations])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(
) 2.3 PIOP: nouvel argument de décalage multilinéraire------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 de manipuler efficacement des multiples dérivés de poignées d'entrée ou d'autres polynômes virtuels.