Analyse des principes de Binius STARKs et réflexions sur leur optimisation
1 Introduction
Contrairement aux SNARKs basés sur des courbes elliptiques, les STARKs peuvent être considérés comme des SNARKs basés sur des fonctions de hachage. Actuellement, l'une des principales raisons de l'inefficacité des STARKs est que dans la plupart des programmes réels, la plupart des valeurs numériques sont relativement petites, comme les indices de boucle, les valeurs booléennes, les compteurs, etc. Cependant, pour garantir la sécurité des preuves basées sur des arbres de Merkle, l'utilisation du codage de Reed-Solomon pour étendre les données entraîne que de nombreuses valeurs redondantes occupent tout le domaine, même si les valeurs d'origine sont très petites. Pour résoudre ce problème, réduire la taille du domaine devient une stratégie clé.
La largeur de codage des STARKs de première génération est de 252 bits, celle de la deuxième génération est de 64 bits, et celle de la troisième génération est de 32 bits, mais le codage de 32 bits présente encore beaucoup d'espace gaspillé. En comparaison, le domaine binaire permet d'opérer directement sur les bits, le codage est compact et efficace sans gaspillage, et peut être considéré comme la quatrième génération de STARKs.
Comparé aux corps finis découverts ces dernières années tels que Goldilocks, BabyBear et Mersenne31, la recherche sur les corps binaires remonte aux années 1980. Actuellement, les corps binaires sont largement utilisés en cryptographie, comme le domaine AES(F28, le domaine GMAC)F2128, et le code Reed-Solomon des QR codes(F28, etc. Les protocoles FRI originaux et zk-STARK, ainsi que la fonction de hachage Grøstl, finaliste du concours SHA-3, sont également basés sur le domaine F28.
L'opération d'extension de domaine devient de plus en plus importante pour garantir la sécurité lors de l'utilisation de domaines plus petits. Le domaine binaire utilisé par Binius repose entièrement sur l'extension de domaine pour garantir la sécurité et la disponibilité. La plupart des polynômes impliqués dans les calculs de Prover n'ont besoin d'opérer que 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 être effectués dans un domaine d'extension plus grand afin de garantir la sécurité requise.
Lors de la construction d'un système de preuve basé sur le domaine binaire, il existe deux problèmes pratiques :
Lors de la représentation du trace dans 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, le codage de Reed-Solomon doit être effectué, et la taille du domaine utilisée doit être supérieure à la taille après l'extension du codage.
Binius propose des solutions innovantes pour traiter ces deux problèmes :
Utiliser un polynôme multivariable ) multilinéraire ( à la place d'un polynôme à variable unique, en représentant toute la trajectoire de calcul par ses valeurs sur le "hypercube".
Étant donné que chaque dimension du cuboctaèdre a une longueur de 2, il n'est pas possible de procéder à une extension Reed-Solomon standard comme avec les STARKs, mais on peut considérer le cuboctaèdre comme un carré et effectuer une extension Reed-Solomon basée sur ce carré.
Cette méthode améliore considérablement l'efficacité du codage et les performances de calcul tout en garantissant la sécurité.
![Bitlayer Research : Analyse des principes STARKs de Binius et réflexion sur leur optimisation])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
2 Analyse des principes
La plupart des systèmes SNARKs actuels comprennent généralement deux parties :
Preuve de l'oracle interactif polynomial en théorie de l'information ) PIOP (:
En tant que noyau du système de preuve, transforme les relations de calcul d'entrée en équations polynomiales vérifiables. Grâce à une interaction avec le vérificateur, le prouveur envoie progressivement des polynômes, permettant au vérificateur de valider la précision du calcul 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, entre autres.
Schéma d'engagement polynomial )PCS(:
Utilisé pour prouver si l'égalité polynomiale générée par PIOP est valide. PCS est un outil cryptographique, le prouveur peut s'engager sur un certain polynôme et vérifier plus tard son résultat d'évaluation, tout en cachant d'autres informations sur le polynôme. Les PCS courants incluent KZG, Bulletproofs, FRI et Brakedown.
Selon les besoins, choisissez différents PIOP et PCS, et combinez-les avec un domaine fini ou une courbe elliptique appropriée, ce qui permet de construire des systèmes de preuve avec différentes propriétés. Par exemple :
Halo2: PLONK PIOP + Bulletproofs PCS + Pasta courbe
Arithmétisation basée sur le domaine binaire en forme de tour : constituant la base du calcul, réalisant des opérations simplifiées dans le domaine binaire.
Adaptation de la vérification des produits et des permutations HyperPlonk : assurer une vérification d'incohérence efficace entre les variables et les permutations.
Nouvelle preuve de décalage multilinéaire : optimisation de l'efficacité de la validation des relations multilinéaires sur de petits domaines
Amélioration de la recherche Lasso: fournir flexibilité et sécurité au mécanisme de recherche
Schéma d'engagement par polynôme sur de petits domaines : mise en œuvre d'un système de preuve efficace sur des domaines binaires, réduisant les coûts associés aux grands domaines.
![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.1 Domain fini : arithmétique basée sur les tours de champs binaires
Les corps binaires en tour sont essentiels pour réaliser des calculs rapides et vérifiables, principalement en raison de leur calcul efficace et de leur arithmétisation 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 à la performance. La structure des corps binaires supporte un processus d'arithmétisation simplifié, et les opérations effectuées sur les corps binaires peuvent être représentées sous une forme algébrique compacte et facilement vérifiable. Ces caractéristiques, associées à la capacité d'exploiter pleinement 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 comme Binius.
Le terme "canonical" fait référence à la représentation unique et directe des éléments dans le domaine binaire. Par exemple, dans le domaine binaire de base F2, toute 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 fixe de bits. Bien qu'un domaine premier de 32 bits puisse être contenu dans 32 bits, chaque chaîne de 32 bits ne peut pas correspondre de manière unique à un élément du domaine, tandis que le domaine binaire possède cette commodité de correspondance un à un.
Dans le domaine des nombres premiers Fp, les méthodes de réduction courantes comprennent 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, les méthodes de réduction courantes incluent des réductions spéciales ( telles que celles utilisées par AES ), la réduction de Montgomery ### telle que celle utilisée par POLYVAL ( et la réduction récursive ) telle que Tower (.
Le document "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" souligne que le champ binaire n'exige pas l'introduction de retenues dans les opérations d'addition et de multiplication, et que l'opération de mise au carré dans le champ binaire est très efficace, car elle suit la règle simplifiée )X + Y(2 = X2 + Y2.
Une chaîne de 128 bits peut être interprétée de plusieurs manières dans le contexte des domaines binaires. Elle peut être considérée comme un élément unique dans un domaine binaire de 128 bits, ou être 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 ne nécessite aucun coût de calcul, mais uniquement une conversion de type de chaîne de bits, ce qui est une propriété très intéressante et utile. En même temps, 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.
Le document "On Efficient Inversion in Tower Fields of Characteristic Two" discute de la complexité des calculs pour effectuer des multiplications, des carrés et des inversions dans un domaine binaire en tour de n bits, décomposé en un sous-domaine de m bits ).
( 2.2 PIOP: version adaptée du produit HyperPlonk et de la 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 la correctitude des polynômes et des ensembles multivariés :
GateCheck : vérifier si le témoin secret ω et l'entrée publique x satisfont la relation de calcul du circuit C)x,ω(=0, assurant le bon fonctionnement du circuit.
PermutationCheck : Vérifiez si les résultats d'évaluation des deux polynômes multivariables f et g sur le cube hypercubique booléen forment une relation de permutation f)x### = f(π)x(), en s'assurant de la cohérence des permutations entre les variables du polynôme.
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 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, garantir l'exactitude du produit du polynôme.
ZeroCheck : vérifier si un polynôme multivarié sur l'hypercube de Boole à un point quelconque est nul ∏x∈Hμ f(x) = 0, ∀x ∈ Bμ, assurer la distribution des zéros du polynôme.
SumCheck : vérifie si la somme d'un polynôme multivariable est égale à la valeur déclarée ∑x∈Hμ f(x) = s. En transformant le problème d'évaluation d'un polynôme multivarié en évaluation d'un polynôme à une seule variable, 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 afin de réaliser le traitement par lots de plusieurs instances de vérification de sommes.
BatchCheck : Basé sur SumCheck, vérifie la validité des évaluations de plusieurs polynômes multivariés pour améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk aient de nombreuses similarités dans la conception du protocole, Binius a apporté des améliorations dans les 3 domaines suivants :
Optimisation de ProductCheck : dans HyperPlonk, ProductCheck exige que le dénominateur U soit non nul partout sur l'hypercube, et que le produit soit égal à une valeur spécifique ; Binius simplifie ce processus de vérification en spécialisant cette valeur à 1, réduisant ainsi la complexité de calcul.
Gestion des problèmes de division par zéro : HyperPlonk n'a pas réussi à gérer correctement les cas de division par zéro, rendant impossible d'affirmer que U est non nul sur l'hypercube ; Binius a correctement traité ce problème, même lorsque le dénominateur est zéro, le ProductCheck de Binius peut continuer à traiter, 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, permettant à 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 apportées au mécanisme existant de vérification de somme PIOP, notamment en offrant un meilleur soutien fonctionnel lors du traitement de la validation de polynômes multivariés plus complexes. Ces améliorations non seulement résolvent les limitations de HyperPlonk, mais posent également les bases pour de futurs systèmes de preuve basés sur des corps binaires.
( 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 techniques clés, permettant de générer et d'opérer efficacement des polynômes dérivés d'un gestionnaire d'entrée ou d'autres polynômes virtuels. Voici deux méthodes clés :
Packing: Cette méthode optimise l'opération en regroupant les éléments plus petits situés à des positions adjacentes dans l'ordre lexicographique pour former des éléments plus grands. L'opérateur Pack cible des blocs de taille 2κ et les combine en un seul élément dans un domaine de haute dimension. Grâce à l'extension multilinéaire )Multilinear Extension, MLE(, ce polynôme virtuel peut être évalué et traité efficacement, transformant la fonction t en un autre polynôme, ce qui améliore les performances de calcul.
Opérateurs de décalage : Les opérateurs de décalage réarrangent les éléments à l'intérieur des blocs, en effectuant un décalage circulaire basé sur un décalage donné o. Cette méthode s'applique à des blocs de taille 2b, chaque bloc exécutant un décalage selon le décalage. Les opérateurs de décalage sont définis par le soutien de la fonction, garantissant la cohérence et l'efficacité lors du traitement des polynômes virtuels. L'évaluation de la complexité de cette construction augmente linéairement avec la taille du bloc, ce qui la rend particulièrement adaptée pour traiter de grands ensembles de données ou des scénarios à haute dimension dans l'hypercube booléen.
![Bitlayer Research : Analyse des principes des STARKs de Binius et réflexion sur leur optimisation])https://img-cdn.gateio.im/webp-social/moments-7f96976952fd0f8da0e93ff1042a966d.webp###
( 2.4 PIOP : argument de recherche Lasso modifié ------ applicable au domaine binaire
Le protocole Lasso permet à la partie preuve de s'engager sur un vecteur a ∈ Fm et de prouver que tous ses éléments existent dans une table préalablement spécifiée t ∈ Fn. Lasso déverrouille le concept de "lookup singularities")lookup singularities( et peut être appliqué à des schémas d'engagement de polynômes multilinéraires. Son efficacité se manifeste dans les deux aspects suivants :
Efficacité de la preuve : Pour m recherches dans une table de taille n, le prouveur n'a besoin de s'engager que sur m+n éléments de domaine. Ces éléments de domaine sont très petits, tous situés dans l'ensemble {0,...,m}. Dans un schéma d'engagement basé sur des puissances multiples, le coût de calcul du prouveur est de O)m + n### opérations de groupe( comme
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.
10 J'aime
Récompense
10
4
Reposter
Partager
Commentaire
0/400
DeadTrades_Walking
· Il y a 9h
La compression de domaine a commencé à être amusante.
Voir l'originalRépondre0
zkProofInThePudding
· Il y a 9h
Je n'ai pas beaucoup de compétences, je ne fais que gaspiller un peu d'espace.
Voir l'originalRépondre0
PanicSeller
· Il y a 9h
Après avoir regardé, j'ai de nouveau mal à la tête.
Voir l'originalRépondre0
BankruptWorker
· Il y a 9h
Je sens que j'ai encore compris quelque chose de triste.
Binius : Optimisation et innovation des STARKs basés sur le domaine binaire
Analyse des principes de Binius STARKs et réflexions sur leur optimisation
1 Introduction
Contrairement aux SNARKs basés sur des courbes elliptiques, les STARKs peuvent être considérés comme des SNARKs basés sur des fonctions de hachage. Actuellement, l'une des principales raisons de l'inefficacité des STARKs est que dans la plupart des programmes réels, la plupart des valeurs numériques sont relativement petites, comme les indices de boucle, les valeurs booléennes, les compteurs, etc. Cependant, pour garantir la sécurité des preuves basées sur des arbres de Merkle, l'utilisation du codage de Reed-Solomon pour étendre les données entraîne que de nombreuses valeurs redondantes occupent tout le domaine, même si les valeurs d'origine sont très petites. Pour résoudre ce problème, réduire la taille du domaine devient une stratégie clé.
La largeur de codage des STARKs de première génération est de 252 bits, celle de la deuxième génération est de 64 bits, et celle de la troisième génération est de 32 bits, mais le codage de 32 bits présente encore beaucoup d'espace gaspillé. En comparaison, le domaine binaire permet d'opérer directement sur les bits, le codage est compact et efficace sans gaspillage, et peut être considéré comme la quatrième génération de STARKs.
Comparé aux corps finis découverts ces dernières années tels que Goldilocks, BabyBear et Mersenne31, la recherche sur les corps binaires remonte aux années 1980. Actuellement, les corps binaires sont largement utilisés en cryptographie, comme le domaine AES(F28, le domaine GMAC)F2128, et le code Reed-Solomon des QR codes(F28, etc. Les protocoles FRI originaux et zk-STARK, ainsi que la fonction de hachage Grøstl, finaliste du concours SHA-3, sont également basés sur le domaine F28.
L'opération d'extension de domaine devient de plus en plus importante pour garantir la sécurité lors de l'utilisation de domaines plus petits. Le domaine binaire utilisé par Binius repose entièrement sur l'extension de domaine pour garantir la sécurité et la disponibilité. La plupart des polynômes impliqués dans les calculs de Prover n'ont besoin d'opérer que 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 être effectués dans un domaine d'extension plus grand afin de garantir la sécurité requise.
Lors de la construction d'un système de preuve basé sur le domaine binaire, il existe deux problèmes pratiques :
Binius propose des solutions innovantes pour traiter ces deux problèmes :
Cette méthode améliore considérablement l'efficacité du codage et les performances de calcul tout en garantissant la sécurité.
![Bitlayer Research : Analyse des principes STARKs de Binius et réflexion sur leur optimisation])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
2 Analyse des principes
La plupart des systèmes SNARKs actuels comprennent généralement deux parties :
Preuve de l'oracle interactif polynomial en théorie de l'information ) PIOP (: En tant que noyau du système de preuve, transforme les relations de calcul d'entrée en équations polynomiales vérifiables. Grâce à une interaction avec le vérificateur, le prouveur envoie progressivement des polynômes, permettant au vérificateur de valider la précision du calcul 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, entre autres.
Schéma d'engagement polynomial )PCS(: Utilisé pour prouver si l'égalité polynomiale générée par PIOP est valide. PCS est un outil cryptographique, le prouveur peut s'engager sur un certain polynôme et vérifier plus tard son résultat d'évaluation, tout en cachant d'autres informations sur le polynôme. Les PCS courants incluent KZG, Bulletproofs, FRI et Brakedown.
Selon les besoins, choisissez différents PIOP et PCS, et combinez-les avec un domaine fini ou une courbe elliptique appropriée, ce qui permet de construire des systèmes de preuve avec différentes propriétés. Par exemple :
Binius comprend cinq technologies clés :
Arithmétisation basée sur le domaine binaire en forme de tour : constituant la base du calcul, réalisant des opérations simplifiées dans le domaine binaire.
Adaptation de la vérification des produits et des permutations HyperPlonk : assurer une vérification d'incohérence efficace entre les variables et les permutations.
Nouvelle preuve de décalage multilinéaire : optimisation de l'efficacité de la validation des relations multilinéaires sur de petits domaines
Amélioration de la recherche Lasso: fournir flexibilité et sécurité au mécanisme de recherche
Schéma d'engagement par polynôme sur de petits domaines : mise en œuvre d'un système de preuve efficace sur des domaines binaires, réduisant les coûts associés aux grands domaines.
![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.1 Domain fini : arithmétique basée sur les tours de champs binaires
Les corps binaires en tour sont essentiels pour réaliser des calculs rapides et vérifiables, principalement en raison de leur calcul efficace et de leur arithmétisation 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 à la performance. La structure des corps binaires supporte un processus d'arithmétisation simplifié, et les opérations effectuées sur les corps binaires peuvent être représentées sous une forme algébrique compacte et facilement vérifiable. Ces caractéristiques, associées à la capacité d'exploiter pleinement 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 comme Binius.
Le terme "canonical" fait référence à la représentation unique et directe des éléments dans le domaine binaire. Par exemple, dans le domaine binaire de base F2, toute 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 fixe de bits. Bien qu'un domaine premier de 32 bits puisse être contenu dans 32 bits, chaque chaîne de 32 bits ne peut pas correspondre de manière unique à un élément du domaine, tandis que le domaine binaire possède cette commodité de correspondance un à un.
Dans le domaine des nombres premiers Fp, les méthodes de réduction courantes comprennent 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, les méthodes de réduction courantes incluent des réductions spéciales ( telles que celles utilisées par AES ), la réduction de Montgomery ### telle que celle utilisée par POLYVAL ( et la réduction récursive ) telle que Tower (.
Le document "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" souligne que le champ binaire n'exige pas l'introduction de retenues dans les opérations d'addition et de multiplication, et que l'opération de mise au carré dans le champ binaire est très efficace, car elle suit la règle simplifiée )X + Y(2 = X2 + Y2.
Une chaîne de 128 bits peut être interprétée de plusieurs manières dans le contexte des domaines binaires. Elle peut être considérée comme un élément unique dans un domaine binaire de 128 bits, ou être 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 ne nécessite aucun coût de calcul, mais uniquement une conversion de type de chaîne de bits, ce qui est une propriété très intéressante et utile. En même temps, 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.
Le document "On Efficient Inversion in Tower Fields of Characteristic Two" discute de la complexité des calculs pour effectuer des multiplications, des carrés et des inversions dans un domaine binaire en tour de n bits, décomposé en un sous-domaine de m bits ).
( 2.2 PIOP: version adaptée du produit HyperPlonk et de la 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 la correctitude des polynômes et des ensembles multivariés :
GateCheck : vérifier si le témoin secret ω et l'entrée publique x satisfont la relation de calcul du circuit C)x,ω(=0, assurant le bon fonctionnement du circuit.
PermutationCheck : Vérifiez si les résultats d'évaluation des deux polynômes multivariables f et g sur le cube hypercubique booléen forment une relation de permutation f)x### = f(π)x(), en s'assurant de la cohérence des permutations entre les variables du polynôme.
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 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, garantir l'exactitude du produit du polynôme.
ZeroCheck : vérifier si un polynôme multivarié sur l'hypercube de Boole à un point quelconque est nul ∏x∈Hμ f(x) = 0, ∀x ∈ Bμ, assurer la distribution des zéros du polynôme.
SumCheck : vérifie si la somme d'un polynôme multivariable est égale à la valeur déclarée ∑x∈Hμ f(x) = s. En transformant le problème d'évaluation d'un polynôme multivarié en évaluation d'un polynôme à une seule variable, 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 afin de réaliser le traitement par lots de plusieurs instances de vérification de sommes.
BatchCheck : Basé sur SumCheck, vérifie la validité des évaluations de plusieurs polynômes multivariés pour améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk aient de nombreuses similarités dans la conception du protocole, Binius a apporté des améliorations dans les 3 domaines suivants :
Optimisation de ProductCheck : dans HyperPlonk, ProductCheck exige que le dénominateur U soit non nul partout sur l'hypercube, et que le produit soit égal à une valeur spécifique ; Binius simplifie ce processus de vérification en spécialisant cette valeur à 1, réduisant ainsi la complexité de calcul.
Gestion des problèmes de division par zéro : HyperPlonk n'a pas réussi à gérer correctement les cas de division par zéro, rendant impossible d'affirmer que U est non nul sur l'hypercube ; Binius a correctement traité ce problème, même lorsque le dénominateur est zéro, le ProductCheck de Binius peut continuer à traiter, 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, permettant à 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 apportées au mécanisme existant de vérification de somme PIOP, notamment en offrant un meilleur soutien fonctionnel lors du traitement de la validation de polynômes multivariés plus complexes. Ces améliorations non seulement résolvent les limitations de HyperPlonk, mais posent également les bases pour de futurs systèmes de preuve basés sur des corps binaires.
( 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 techniques clés, permettant de générer et d'opérer efficacement des polynômes dérivés d'un gestionnaire d'entrée ou d'autres polynômes virtuels. Voici deux méthodes clés :
Packing: Cette méthode optimise l'opération en regroupant les éléments plus petits situés à des positions adjacentes dans l'ordre lexicographique pour former des éléments plus grands. L'opérateur Pack cible des blocs de taille 2κ et les combine en un seul élément dans un domaine de haute dimension. Grâce à l'extension multilinéaire )Multilinear Extension, MLE(, ce polynôme virtuel peut être évalué et traité efficacement, transformant la fonction t en un autre polynôme, ce qui améliore les performances de calcul.
Opérateurs de décalage : Les opérateurs de décalage réarrangent les éléments à l'intérieur des blocs, en effectuant un décalage circulaire basé sur un décalage donné o. Cette méthode s'applique à des blocs de taille 2b, chaque bloc exécutant un décalage selon le décalage. Les opérateurs de décalage sont définis par le soutien de la fonction, garantissant la cohérence et l'efficacité lors du traitement des polynômes virtuels. L'évaluation de la complexité de cette construction augmente linéairement avec la taille du bloc, ce qui la rend particulièrement adaptée pour traiter de grands ensembles de données ou des scénarios à haute dimension dans l'hypercube booléen.
![Bitlayer Research : Analyse des principes des STARKs de Binius et réflexion sur leur optimisation])https://img-cdn.gateio.im/webp-social/moments-7f96976952fd0f8da0e93ff1042a966d.webp###
( 2.4 PIOP : argument de recherche Lasso modifié ------ applicable au domaine binaire
Le protocole Lasso permet à la partie preuve de s'engager sur un vecteur a ∈ Fm et de prouver que tous ses éléments existent dans une table préalablement spécifiée t ∈ Fn. Lasso déverrouille le concept de "lookup singularities")lookup singularities( et peut être appliqué à des schémas d'engagement de polynômes multilinéraires. Son efficacité se manifeste dans les deux aspects suivants :