Analyse des principes des STARKs de Binius et réflexion sur leur optimisation
1 Introduction
Une des principales raisons de l'inefficacité des STARKs est que la plupart des valeurs numériques dans les programmes réels sont 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 l'ensemble du domaine, même si la valeur originale elle-même est très petite. Pour résoudre ce problème, la réduction de la taille du domaine est devenue une stratégie clé.
Comme indiqué dans le tableau 1, la largeur de code des STARKs de première génération est de 252 bits, celle des STARKs de deuxième génération est de 64 bits, et celle des STARKs de troisième génération est de 32 bits, mais la largeur de code de 32 bits présente encore un vaste espace gaspillé. En comparaison, le domaine binaire permet d'opérer directement sur les bits, le codage étant compact et efficace sans aucun espace gaspillé, c'est-à-dire les STARKs de quatrième génération.
Comparé aux domaines finis découverts récemment, comme Goldilocks, BabyBear et Mersenne31, la recherche sur les domaines binaires remonte aux années 1980. Actuellement, les domaines 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 le codage Reed-Solomon basé sur F28;
Protocole FRI original et zk-STARK, ainsi que la fonction de hachage Grøstl qui a atteint la finale du SHA-3, cette fonction basée sur le domaine F28 est un algorithme de hachage très adapté à la récursivité.
Lorsqu'un domaine plus petit est utilisé, 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 garantir 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 peuvent simplement fonctionner dans le domaine de base, ce qui permet d'atteindre une grande efficacité dans un petit domaine. Cependant, les vérifications de points aléatoires et les calculs FRI doivent encore plonger dans une extension de domaine plus grande pour garantir la sécurité requise.
Lors de la construction d'un système de preuves 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é doit être supérieure au degré du polynôme ; lors de l'engagement de l'arbre de Merkle dans les STARKs, un codage de Reed-Solomon doit être effectué, et la taille du domaine utilisé doit être supérieure à la taille après extension du codage.
Binius a proposé une solution innovante qui traite ces deux problèmes séparément et réalise la représentation des mêmes données de deux manières différentes : d'abord, en utilisant des polynômes multivariés ( au lieu de polynômes à une seule variable, en représentant l'ensemble de la trajectoire de calcul par leurs 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 standard de Reed-Solomon comme avec les STARKs, mais l'hypercube peut être considéré comme un carré (, sur lequel l'extension de Reed-Solomon peut être basée. Cette méthode améliore considérablement l'efficacité de 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 informationnelle )Information-Theoretic Polynomial Interactive Oracle Proof, PIOP( : PIOP, en tant que cœur du système de preuve, transforme la relation 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 seulement quelques 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 la performance et l'efficacité de l'ensemble du système SNARK.
Schéma d'engagement polynomial )Polynomial Commitment Scheme, PCS( : Le schéma d'engagement polynomial est utilisé pour prouver si une équation polynomiale générée par PIOP est valide. Le PCS est un outil cryptographique qui permet à un prouveur de s'engager sur un certain polynôme et de vérifier ultérieurement le résultat de l'évaluation de ce polynôme, tout en cachant d'autres informations sur le polynôme. Les schémas d'engagement polynomial courants incluent KZG, Bulletproofs, FRI)Fast Reed-Solomon IOPP( et Brakedown, entre autres. Différents PCS ont des performances, une sécurité et des scénarios d'application différents.
En fonction des besoins spécifiques, choisissez différents PIOP et PCS, et associez-les à un domaine fini ou à une courbe elliptique appropriée, ce qui permet de construire des systèmes de preuve ayant différentes propriétés. Par exemple:
Halo2 : combinant PLONK PIOP et Bulletproofs PCS, et 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 : Utilise PLONK PIOP et FRI PCS combinés, et est basé sur le domaine de Goldilocks. Plonky2 est conçu pour réaliser une récursion efficace. Lors de la conception de ces systèmes, le PIOP et le PCS choisis doivent correspondre au corps fini ou à la courbe elliptique utilisée, afin de garantir la correctivité, la performance et la sécurité du système. Le choix de ces combinaisons influence non seulement la taille des preuves SNARK et l'efficacité de validation, mais détermine également si le système peut réaliser la transparence sans configuration de confiance, et s'il peut prendre en charge des fonctionnalités extensibles 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étisation basée sur les tours de domaines binaires )towers of binary fields( constitue la base de ses calculs, permettant d'effectuer des opérations simplifiées dans le domaine binaire. Deuxièmement, Binius a adapté l'HyperPlonk produit et vérification de permutation dans son protocole de preuve Oracle interactif )PIOP(, garantissant une vérification cohérente sécurisée et efficace entre les variables et leurs permutations. Troisièmement, le protocole introduit une nouvelle preuve de décalage 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é robuste au mécanisme de recherche. Enfin, le protocole utilise un schéma de promesse polynomiale sur de petits domaines )Small-Field PCS(, permettant de réaliser un système de preuve efficace sur le domaine binaire, tout en réduisant les frais généralement associés aux grands domaines.
) 2.1 Domaine fini : arithmétique basée sur les tours de champs binaires
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 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 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 leurs caractéristiques 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" désigne la représentation unique et directe des éléments dans le domaine binaire. Par exemple, dans le domaine binaire le plus basique F2, toute chaîne de k bits peut être directement mappée à un élément de domaine binaire de k bits. Cela diffère du domaine premier, qui ne peut pas fournir cette représentation canonique sur un nombre de bits donné. Bien qu'un domaine premier de 32 bits puisse être contenu dans 32 bits, chaque chaîne de 32 bits ne peut pas nécessairement correspondre de manière unique à un élément de domaine, alors que le domaine binaire offre cette commodité de mappage un à un. Dans le domaine premier Fp, des 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 tels que Mersenne-31 ou Goldilocks-64. Dans le domaine binaire F2k, des 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 ) utilisée dans 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 mise au 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 d'un domaine binaire. Elle peut être considérée comme un élément unique dans un domaine binaire de 128 bits, ou être décomposée en deux éléments de domaine de 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'entraîne aucun coût de calcul, c'est simplement un type de conversion 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 emballés en éléments de domaine plus grands sans coût de calcul supplémentaire. Le protocole Binius a tiré 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 des opérations de multiplication, de mise au carré et d'inversion dans un domaine binaire de tour de n bits ) décomposé en sous-domaines de m bits (.
![Bitlayer Research : Analyse des principes des STARKs de Binius et réflexion sur leur optimisation])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 2.2 PIOP: Version adaptée du produit HyperPlonk et Vérification de permutation ------ Applicable au domaine binaire
La conception de PIOP dans le protocole Binius s'inspire de HyperPlonk et utilise une série de mécanismes de vérification essentiels pour valider l'exactitude des polynômes et des ensembles multivariés. Ces vérifications essentielles comprennent :
GateCheck : vé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 hyperbooléen forment une relation de permutation f###x( = f)π(x)(, afin d'assurer la cohérence des permutations entre les variables polynomiales.
LookupCheck : Vérifiez si l'évaluation du polynôme est dans la table de recherche donnée, c'est-à-dire f(Bµ) ⊆ T)Bµ(, assurez-vous 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érifier si l'évaluation du polynôme rationnel sur l'hypercube booléen est égale à une valeur déclarée ∏x∈Hµ f)x( = s, afin d'assurer l'exactitude du produit polynomial.
ZeroCheck : vérifier si un polynôme multivarié en un point quelconque du cube hyperbolique booléen est nul ∏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 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 et réaliser 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 multivariés afin d'améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk aient de nombreuses similitudes dans la conception du protocole, Binius apporte des améliorations dans les 3 domaines suivants :
Optimisation de ProductCheck : dans HyperPlonk, ProductCheck exige que le dénominateur U soit non nul partout sur l'hypercube, et que le produit soit égal à une valeur spécifique ; Binius simplifie ce processus de vérification en spécialisant cette valeur à 1, réduisant ainsi la complexité de calcul.
Traitement des problèmes de division par zéro : HyperPlonk n'a pas réussi à traiter adéquatement les cas de division par zéro, ce qui a conduit à l'incapacité d'affirmer que U est non nul sur l'hypercube ; Binius a correctement géré ce problème, même dans le cas où le dénominateur est zéro, le ProductCheck de Binius peut continuer à traiter, permettant de généraliser à n'importe quelle valeur de produit.
Vérification de permutation inter-colonnes : HyperPlonk n'a pas cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de gérer des cas de permutations polynomiales plus complexes.
Ainsi, Binius a amélioré la flexibilité et l'efficacité du protocole grâce à l'amélioration du mécanisme PIOPSumCheck existant.
![Bitlayer Research : Analyse des principes STARKs de Binius et réflexion sur leur optimisation])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(
![Bitlayer Research : Analyse des principes des STARKs de Binius et réflexions sur leur optimisation])https://img-cdn.gateio.im/webp-social/moments-a5d031be4711f29ef910057f4e44a118.webp(
Binius: STARKs optimisés sur le domaine binaire
Analyse des principes des STARKs de Binius et réflexion sur leur optimisation
1 Introduction
Une des principales raisons de l'inefficacité des STARKs est que la plupart des valeurs numériques 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 l'ensemble du domaine, même si la valeur originale elle-même est très petite. Pour résoudre ce problème, la réduction de la taille du domaine est devenue une stratégie clé.
Comme indiqué dans le tableau 1, la largeur de code des STARKs de première génération est de 252 bits, celle des STARKs de deuxième génération est de 64 bits, et celle des STARKs de troisième génération est de 32 bits, mais la largeur de code de 32 bits présente encore un vaste espace gaspillé. En comparaison, le domaine binaire permet d'opérer directement sur les bits, le codage étant compact et efficace sans aucun espace gaspillé, c'est-à-dire les STARKs de quatrième génération.
Tableau 1 : Chemin d'extension des STARKs
| Algèbre | Largeur de code | Mise en œuvre représentative | |------|----------|------------| | Première génération | 252bit | StarkWare | | 2ème génération | 64 bits | Plonky2 | | 3ème génération | 32 bits | BabyBear |
| 4ème génération | 1bit | Binius |
Comparé aux domaines finis découverts récemment, comme Goldilocks, BabyBear et Mersenne31, la recherche sur les domaines binaires remonte aux années 1980. Actuellement, les domaines binaires sont largement utilisés en cryptographie, des exemples typiques incluent :
Lorsqu'un domaine plus petit est utilisé, 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 garantir 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 peuvent simplement fonctionner dans le domaine de base, ce qui permet d'atteindre une grande efficacité dans un petit domaine. Cependant, les vérifications de points aléatoires et les calculs FRI doivent encore plonger dans une extension de domaine plus grande pour garantir la sécurité requise.
Lors de la construction d'un système de preuves 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é doit être supérieure au degré du polynôme ; lors de l'engagement de l'arbre de Merkle dans les STARKs, un codage de Reed-Solomon doit être effectué, et la taille du domaine utilisé doit être supérieure à la taille après extension du codage.
Binius a proposé une solution innovante qui traite ces deux problèmes séparément et réalise la représentation des mêmes données de deux manières différentes : d'abord, en utilisant des polynômes multivariés ( au lieu de polynômes à une seule variable, en représentant l'ensemble de la trajectoire de calcul par leurs 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 standard de Reed-Solomon comme avec les STARKs, mais l'hypercube peut être considéré comme un carré (, sur lequel l'extension de Reed-Solomon peut être basée. Cette méthode améliore considérablement l'efficacité de 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 informationnelle )Information-Theoretic Polynomial Interactive Oracle Proof, PIOP( : PIOP, en tant que cœur du système de preuve, transforme la relation 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 seulement quelques 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 la performance et l'efficacité de l'ensemble du système SNARK.
Schéma d'engagement polynomial )Polynomial Commitment Scheme, PCS( : Le schéma d'engagement polynomial est utilisé pour prouver si une équation polynomiale générée par PIOP est valide. Le PCS est un outil cryptographique qui permet à un prouveur de s'engager sur un certain polynôme et de vérifier ultérieurement le résultat de l'évaluation de ce polynôme, tout en cachant d'autres informations sur le polynôme. Les schémas d'engagement polynomial courants incluent KZG, Bulletproofs, FRI)Fast Reed-Solomon IOPP( et Brakedown, entre autres. Différents PCS ont des performances, une sécurité et des scénarios d'application différents.
En fonction des besoins spécifiques, choisissez différents PIOP et PCS, et associez-les à un domaine fini ou à une courbe elliptique appropriée, ce qui permet de construire des systèmes de preuve ayant différentes propriétés. Par exemple:
Halo2 : combinant PLONK PIOP et Bulletproofs PCS, et 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 : Utilise PLONK PIOP et FRI PCS combinés, et est basé sur le domaine de Goldilocks. Plonky2 est conçu pour réaliser une récursion efficace. Lors de la conception de ces systèmes, le PIOP et le PCS choisis doivent correspondre au corps fini ou à la courbe elliptique utilisée, afin de garantir la correctivité, la performance et la sécurité du système. Le choix de ces combinaisons influence non seulement la taille des preuves SNARK et l'efficacité de validation, mais détermine également si le système peut réaliser la transparence sans configuration de confiance, et s'il peut prendre en charge des fonctionnalités extensibles 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étisation basée sur les tours de domaines binaires )towers of binary fields( constitue la base de ses calculs, permettant d'effectuer des opérations simplifiées dans le domaine binaire. Deuxièmement, Binius a adapté l'HyperPlonk produit et vérification de permutation dans son protocole de preuve Oracle interactif )PIOP(, garantissant une vérification cohérente sécurisée et efficace entre les variables et leurs permutations. Troisièmement, le protocole introduit une nouvelle preuve de décalage 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é robuste au mécanisme de recherche. Enfin, le protocole utilise un schéma de promesse polynomiale sur de petits domaines )Small-Field PCS(, permettant de réaliser un système de preuve efficace sur le domaine binaire, tout en réduisant les frais généralement associés aux grands domaines.
) 2.1 Domaine fini : arithmétique basée sur les tours de champs binaires
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 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 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 leurs caractéristiques 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" désigne la représentation unique et directe des éléments dans le domaine binaire. Par exemple, dans le domaine binaire le plus basique F2, toute chaîne de k bits peut être directement mappée à un élément de domaine binaire de k bits. Cela diffère du domaine premier, qui ne peut pas fournir cette représentation canonique sur un nombre de bits donné. Bien qu'un domaine premier de 32 bits puisse être contenu dans 32 bits, chaque chaîne de 32 bits ne peut pas nécessairement correspondre de manière unique à un élément de domaine, alors que le domaine binaire offre cette commodité de mappage un à un. Dans le domaine premier Fp, des 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 tels que Mersenne-31 ou Goldilocks-64. Dans le domaine binaire F2k, des 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 ) utilisée dans 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 mise au 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 d'un domaine binaire. Elle peut être considérée comme un élément unique dans un domaine binaire de 128 bits, ou être décomposée en deux éléments de domaine de 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'entraîne aucun coût de calcul, c'est simplement un type de conversion 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 emballés en éléments de domaine plus grands sans coût de calcul supplémentaire. Le protocole Binius a tiré 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 des opérations de multiplication, de mise au carré et d'inversion dans un domaine binaire de tour de n bits ) décomposé en sous-domaines de m bits (.
![Bitlayer Research : Analyse des principes des STARKs de Binius et réflexion sur leur optimisation])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 2.2 PIOP: Version adaptée du produit HyperPlonk et Vérification de permutation ------ Applicable au domaine binaire
La conception de PIOP dans le protocole Binius s'inspire de HyperPlonk et utilise une série de mécanismes de vérification essentiels pour valider l'exactitude des polynômes et des ensembles multivariés. Ces vérifications essentielles comprennent :
GateCheck : vé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 hyperbooléen forment une relation de permutation f###x( = f)π(x)(, afin d'assurer la cohérence des permutations entre les variables polynomiales.
LookupCheck : Vérifiez si l'évaluation du polynôme est dans la table de recherche donnée, c'est-à-dire f(Bµ) ⊆ T)Bµ(, assurez-vous 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érifier si l'évaluation du polynôme rationnel sur l'hypercube booléen est égale à une valeur déclarée ∏x∈Hµ f)x( = s, afin d'assurer l'exactitude du produit polynomial.
ZeroCheck : vérifier si un polynôme multivarié en un point quelconque du cube hyperbolique booléen est nul ∏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 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 et réaliser 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 multivariés afin d'améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk aient de nombreuses similitudes dans la conception du protocole, Binius apporte des améliorations dans les 3 domaines suivants :
Optimisation de ProductCheck : dans HyperPlonk, ProductCheck exige que le dénominateur U soit non nul partout sur l'hypercube, et que le produit soit égal à une valeur spécifique ; Binius simplifie ce processus de vérification en spécialisant cette valeur à 1, réduisant ainsi la complexité de calcul.
Traitement des problèmes de division par zéro : HyperPlonk n'a pas réussi à traiter adéquatement les cas de division par zéro, ce qui a conduit à l'incapacité d'affirmer que U est non nul sur l'hypercube ; Binius a correctement géré ce problème, même dans le cas où le dénominateur est zéro, le ProductCheck de Binius peut continuer à traiter, permettant de généraliser à n'importe quelle valeur de produit.
Vérification de permutation inter-colonnes : HyperPlonk n'a pas cette fonctionnalité ; Binius prend en charge la vérification de permutation entre plusieurs colonnes, ce qui permet à Binius de gérer des cas de permutations polynomiales plus complexes.
Ainsi, Binius a amélioré la flexibilité et l'efficacité du protocole grâce à l'amélioration du mécanisme PIOPSumCheck existant.
![Bitlayer Research : Analyse des principes STARKs de Binius et réflexion sur leur optimisation])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(
![Bitlayer Research : Analyse des principes des STARKs de Binius et réflexions sur leur optimisation])https://img-cdn.gateio.im/webp-social/moments-a5d031be4711f29ef910057f4e44a118.webp(
![Bitl