Analyse des principes de Binius STARKs 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. Une des principales raisons de l'inefficacité actuelle des STARKs est que la plupart des valeurs numériques dans les programmes réels sont relativement petites, comme les index dans les boucles for, les valeurs 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 qui occupent tout le domaine, même si la valeur originale elle-même est très petite. Pour résoudre ce problème, la réduction de la taille du domaine est devenue une stratégie clé.
La largeur de code de la première génération de STARKs est de 252 bits, celle de la deuxième génération de STARKs est de 64 bits, et celle de la troisième génération de STARKs est de 32 bits, mais la largeur de code de 32 bits présente encore beaucoup d'espace gaspillé. En comparaison, le domaine binaire permet d'opérer directement sur les bits, rendant le codage compact et efficace sans aucun espace gaspillé, c'est-à-dire la quatrième génération de STARKs.
Comparé aux découvertes récentes sur les corps finis tels que Goldilocks, BabyBear et Mersenne31, la recherche sur les corps binaires remonte aux années 80 du siècle dernier. Actuellement, les corps binaires sont largement utilisés en cryptographie, des exemples typiques incluent :
Norme de cryptage avancé ( AES ), basée sur le domaine F28;
Galois code d'authentification de message ( GMAC ), basé sur le champ F2128;
Code QR, utilisant le codage Reed-Solomon basé sur F28;
Les protocoles FRI et zk-STARK d'origine, ainsi que la fonction de hachage Grøstl qui a atteint la finale de SHA-3, cette fonction basée sur le domaine F28, est un algorithme de hachage particulièrement adapté à la récursivité.
Lorsque des domaines plus petits sont utilisés, l'opération d'extension de domaine devient de plus en plus importante pour garantir la sécurité. Le domaine binaire utilisé par Binius doit entièrement dépendre de l'extension de domaine pour garantir sa sécurité et sa faisabilité pratique. La plupart des polynômes impliqués dans les calculs de Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais doivent simplement fonctionner dans le domaine de base, réalisant ainsi une grande efficacité dans un petit domaine. Cependant, les vérifications de points aléatoires et les calculs FRI doivent encore entrer dans un domaine d'extension plus grand pour garantir la sécurité requise.
Lors de la construction d'un système de preuve basé sur un domaine binaire, il existe 2 problèmes pratiques : lors du calcul de la 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 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 a proposé une solution innovante qui traite les deux problèmes respectivement et représente 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 à variable unique, en représentant l'ensemble de la trajectoire de calcul par ses valeurs sur les "hyper-cubes" ( ; deuxièmement, étant donné que la longueur de chaque dimension de l'hyper-cube est de 2, il n'est pas possible d'effectuer une extension de Reed-Solomon standard comme avec les STARKs, mais l'hyper-cube peut être considéré comme un carré ), sur lequel on peut effectuer une extension de Reed-Solomon. Cette méthode améliore considérablement l'efficacité du codage et la performance de calcul tout en garantissant la sécurité.
2. Analyse des principes
La plupart des systèmes SNARKs actuels sont généralement construits en deux parties :
Preuve d'oracle interactive polynomiale d'information théorique (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP) : PIOP, en tant que système de preuve central, transforme les relations de calcul en égalités polynomiales vérifiables. Différents protocoles PIOP permettent au prouveur d'envoyer progressivement des polynômes grâce à l'interaction avec le vérificateur, de sorte que le vérificateur puisse vérifier la validité du calcul en consultant les résultats d'évaluation d'un petit nombre de polynômes. Les protocoles PIOP existants incluent : PLONK PIOP, Spartan PIOP et HyperPlonk PIOP, chacun ayant une méthode différente de traitement des expressions polynomiales, ce qui impacte 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 l'égalité polynomial générée par PIOP est valide. PCS est un outil cryptographique, à travers lequel le prouveur peut s'engager sur un certain polynôme et vérifier plus tard le résultat de l'évaluation de ce polynôme, tout en cachant d'autres informations sur le polynôme. Les schémas d'engagement polynomial courants incluent KZG, Bulletproofs, FRI ( Fast Reed-Solomon IOPP ) et Brakedown, etc. Différents PCS ont différentes performances, sécurité et cas d'utilisation.
Selon les besoins spécifiques, choisissez différents PIOP et PCS, et combinez-les avec un domaine fini ou une courbe elliptique appropriée, il est possible de construire des systèmes de preuve avec 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 la scalabilité et en éliminant le trusted setup du protocole ZCash.
• Plonky2 : utilise PLONK PIOP et FRI PCS combinés, et est basé sur le domaine de Goldilocks. Plonky2 est conçu pour réaliser des récursions efficaces. Lors de la conception de ces systèmes, le PIOP et le PCS choisis doivent correspondre au domaine fini ou à la courbe elliptique utilisés, afin d'assurer la correction, la performance et la sécurité du système. Le choix de ces combinaisons affecte non seulement la taille des preuves SNARK et l'efficacité de la vérification, mais détermine également si le système peut réaliser une transparence sans configuration de confiance préalable, et s'il peut soutenir des fonctionnalités d'extension telles que des preuves récursives ou des preuves agrégées.
Binius : HyperPlonk PIOP + Brakedown PCS + domaines binaires. Plus précisément, Binius comprend cinq technologies clés pour réaliser son efficacité et sa sécurité. Tout d'abord, l'arithmétique basée sur les tours de domaines binaires (towers of binary fields) constitue la base de son calcul, permettant d'effectuer des opérations simplifiées dans les domaines binaires. Deuxièmement, Binius a adapté les vérifications de produit et de permutation de HyperPlonk 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éaire, optimisant l'efficacité de la vérification des relations multilinéaires dans 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 d'engagement polynomial de petit domaine (Small-Field PCS), lui permettant de réaliser un système de preuve efficace dans les domaines binaires, tout en réduisant les frais généralement associés aux grands domaines.
( 2.1 Domaines finis : arithmétique basée sur les tours de champs binaires
Les corps binaires en tour sont la clé pour réaliser des calculs rapidement vérifiables, principalement en raison de deux aspects : le calcul efficace et l'arithmétique efficace. Les corps binaires soutiennent essentiellement des opérations arithmétiques hautement efficaces, ce qui en fait un choix idéal pour les applications cryptographiques sensibles aux performances. De plus, la structure des corps binaires supporte un processus d'arithmétique simplifié, c'est-à-dire que les opérations effectuées sur le corps binaire peuvent être exprimées sous une forme algébrique compacte et facile à vérifier. Ces caractéristiques, combinées à la capacité d'exploiter pleinement ses caractéristiques hiérarchiques grâce à la structure en tour, rendent les corps binaires particulièrement adaptés à des systèmes de preuve évolutifs comme Binius.
Dans ce contexte, "canonical" fait référence à la représentation unique et directe des éléments dans un corps binaire. Par exemple, dans le corps binaire le plus fondamental F2, toute chaîne de k bits peut être directement mappée à un élément du corps binaire de k bits. Cela diffère des corps premiers, qui ne peuvent pas fournir cette représentation canonique dans un nombre de bits donné. Bien qu'un corps premier de 32 bits puisse être contenu dans 32 bits, ce n'est pas le cas pour chaque chaîne de 32 bits qui peut être mappée de manière unique à un élément du corps, tandis que le corps binaire offre la commodité de ce mappage un à un. Dans le corps premier 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 corps finis spécifiques comme Mersenne-31 ou Goldilocks-64. Dans le corps binaire F2k, les méthodes de réduction couramment utilisées incluent la réduction spéciale ) utilisée dans AES, la réduction de Montgomery ### utilisée dans POLYVAL et la réduction récursive ( utilisée dans Tower ). L'article "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" souligne que le corps binaire ne nécessite pas d'introduire des retenues dans les opérations d'addition et de multiplication, et que l'opération de carré dans le corps binaire est très efficace, car elle suit la règle simplifiée (X + Y )2 = X2 + Y2.
Comme illustré dans la figure 1, une chaîne de 128 bits : cette chaîne peut être interprétée de plusieurs manières dans le contexte des domaines binaires. Elle peut être considérée comme un élément unique dans un domaine binaire de 128 bits, ou être analysée comme deux éléments de domaine tour de 64 bits, quatre éléments de domaine tour de 32 bits, 16 éléments de domaine tour de 8 bits, ou 128 éléments de domaine F2. Cette flexibilité de représentation n'implique aucun coût de calcul, il s'agit simplement d'un 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 petits domaines peuvent être empaquetés en éléments de domaines plus grands sans coût de calcul supplémentaire. Le protocole Binius tire parti de cette caractéristique pour améliorer l'efficacité des calculs. De plus, le document "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité de calcul des opérations de multiplication, de mise au carré et d'inversion dans un domaine binaire de n bits ( décomposé en sous-domaines de m bits ).
( 2.2 PIOP: version adaptée de HyperPlonk Product et PermutationCheck------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 de base pour valider la correctitude des polynômes et des ensembles multivariés. Ces vérifications de base comprennent :
GateCheck : vérifier si le témoin secret ω et l'entrée publique x satisfont la relation d'opération du circuit C)x,ω(=0, afin de garantir le bon fonctionnement du circuit.
PermutationCheck : Vérifie si les résultats d'évaluation de deux polynômes multivariables f et g sur l'hypercube booléen sont 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 se trouve 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érifiez si l'évaluation du polynôme rationnel sur le cube hyperbolique 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 multivariable à plusieurs variables est nul en tout point du cube de Boolean ∏x∈Hμ f(x) = 0, ∀x ∈ Bμ, afin de garantir la distribution des zéros du polynôme.
SumCheck : Vérification 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 des polynômes multivariés en un problème d'évaluation de polynômes univariés, on 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 afin de traiter plusieurs instances de vérification de somme.
BatchCheck : basé sur SumCheck, vérifie la justesse de l'évaluation de plusieurs polynômes multivariables pour améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk aient de nombreuses similitudes dans la conception des protocoles, Binius apporte des améliorations dans les 3 domaines suivants :
Optimisation de ProductCheck : dans HyperPlonk, ProductCheck exige que le dénominateur U soit non nul partout sur l'hypercube, et 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 à traiter correctement les cas de division par zéro, ce qui entraîne l'incapacité d'affirmer que U est non nul sur l'hypercube ; Binius a correctement géré ce problème, même lorsque le dénominateur est zéro, 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, ce qui permet à Binius de gérer des cas de permutations polynomiales plus complexes.
Ainsi, Binius par le biais de
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.
Binius STARKs : système de preuve à connaissance nulle efficace dans le domaine binaire
Analyse des principes de Binius STARKs 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. Une des principales raisons de l'inefficacité actuelle des STARKs est que la plupart des valeurs numériques dans les programmes réels sont relativement petites, comme les index dans les boucles for, les valeurs 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 qui occupent tout le domaine, même si la valeur originale elle-même est très petite. Pour résoudre ce problème, la réduction de la taille du domaine est devenue une stratégie clé.
La largeur de code de la première génération de STARKs est de 252 bits, celle de la deuxième génération de STARKs est de 64 bits, et celle de la troisième génération de STARKs est de 32 bits, mais la largeur de code de 32 bits présente encore beaucoup d'espace gaspillé. En comparaison, le domaine binaire permet d'opérer directement sur les bits, rendant le codage compact et efficace sans aucun espace gaspillé, c'est-à-dire la quatrième génération de STARKs.
Comparé aux découvertes récentes sur les corps finis tels que Goldilocks, BabyBear et Mersenne31, la recherche sur les corps binaires remonte aux années 80 du siècle dernier. Actuellement, les corps binaires sont largement utilisés en cryptographie, des exemples typiques incluent :
Norme de cryptage avancé ( AES ), basée sur le domaine F28;
Galois code d'authentification de message ( GMAC ), basé sur le champ F2128;
Code QR, utilisant le codage Reed-Solomon basé sur F28;
Les protocoles FRI et zk-STARK d'origine, ainsi que la fonction de hachage Grøstl qui a atteint la finale de SHA-3, cette fonction basée sur le domaine F28, est un algorithme de hachage particulièrement adapté à la récursivité.
Lorsque des domaines plus petits sont utilisés, l'opération d'extension de domaine devient de plus en plus importante pour garantir la sécurité. Le domaine binaire utilisé par Binius doit entièrement dépendre de l'extension de domaine pour garantir sa sécurité et sa faisabilité pratique. La plupart des polynômes impliqués dans les calculs de Prover n'ont pas besoin d'entrer dans l'extension de domaine, mais doivent simplement fonctionner dans le domaine de base, réalisant ainsi une grande efficacité dans un petit domaine. Cependant, les vérifications de points aléatoires et les calculs FRI doivent encore entrer dans un domaine d'extension plus grand pour garantir la sécurité requise.
Lors de la construction d'un système de preuve basé sur un domaine binaire, il existe 2 problèmes pratiques : lors du calcul de la 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 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 a proposé une solution innovante qui traite les deux problèmes respectivement et représente 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 à variable unique, en représentant l'ensemble de la trajectoire de calcul par ses valeurs sur les "hyper-cubes" ( ; deuxièmement, étant donné que la longueur de chaque dimension de l'hyper-cube est de 2, il n'est pas possible d'effectuer une extension de Reed-Solomon standard comme avec les STARKs, mais l'hyper-cube peut être considéré comme un carré ), sur lequel on peut effectuer une extension de Reed-Solomon. Cette méthode améliore considérablement l'efficacité du codage et la performance de calcul tout en garantissant la sécurité.
2. Analyse des principes
La plupart des systèmes SNARKs actuels sont généralement construits en deux parties :
Preuve d'oracle interactive polynomiale d'information théorique (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP) : PIOP, en tant que système de preuve central, transforme les relations de calcul en égalités polynomiales vérifiables. Différents protocoles PIOP permettent au prouveur d'envoyer progressivement des polynômes grâce à l'interaction avec le vérificateur, de sorte que le vérificateur puisse vérifier la validité du calcul en consultant les résultats d'évaluation d'un petit nombre de polynômes. Les protocoles PIOP existants incluent : PLONK PIOP, Spartan PIOP et HyperPlonk PIOP, chacun ayant une méthode différente de traitement des expressions polynomiales, ce qui impacte 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 l'égalité polynomial générée par PIOP est valide. PCS est un outil cryptographique, à travers lequel le prouveur peut s'engager sur un certain polynôme et vérifier plus tard le résultat de l'évaluation de ce polynôme, tout en cachant d'autres informations sur le polynôme. Les schémas d'engagement polynomial courants incluent KZG, Bulletproofs, FRI ( Fast Reed-Solomon IOPP ) et Brakedown, etc. Différents PCS ont différentes performances, sécurité et cas d'utilisation.
Selon les besoins spécifiques, choisissez différents PIOP et PCS, et combinez-les avec un domaine fini ou une courbe elliptique appropriée, il est possible de construire des systèmes de preuve avec 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 la scalabilité et en éliminant le trusted setup du protocole ZCash.
• Plonky2 : utilise PLONK PIOP et FRI PCS combinés, et est basé sur le domaine de Goldilocks. Plonky2 est conçu pour réaliser des récursions efficaces. Lors de la conception de ces systèmes, le PIOP et le PCS choisis doivent correspondre au domaine fini ou à la courbe elliptique utilisés, afin d'assurer la correction, la performance et la sécurité du système. Le choix de ces combinaisons affecte non seulement la taille des preuves SNARK et l'efficacité de la vérification, mais détermine également si le système peut réaliser une transparence sans configuration de confiance préalable, et s'il peut soutenir des fonctionnalités d'extension telles que des preuves récursives ou des preuves agrégées.
Binius : HyperPlonk PIOP + Brakedown PCS + domaines binaires. Plus précisément, Binius comprend cinq technologies clés pour réaliser son efficacité et sa sécurité. Tout d'abord, l'arithmétique basée sur les tours de domaines binaires (towers of binary fields) constitue la base de son calcul, permettant d'effectuer des opérations simplifiées dans les domaines binaires. Deuxièmement, Binius a adapté les vérifications de produit et de permutation de HyperPlonk 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éaire, optimisant l'efficacité de la vérification des relations multilinéaires dans 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 d'engagement polynomial de petit domaine (Small-Field PCS), lui permettant de réaliser un système de preuve efficace dans les domaines binaires, tout en réduisant les frais généralement associés aux grands domaines.
( 2.1 Domaines finis : arithmétique basée sur les tours de champs binaires
Les corps binaires en tour sont la clé pour réaliser des calculs rapidement vérifiables, principalement en raison de deux aspects : le calcul efficace et l'arithmétique efficace. Les corps binaires soutiennent essentiellement des opérations arithmétiques hautement efficaces, ce qui en fait un choix idéal pour les applications cryptographiques sensibles aux performances. De plus, la structure des corps binaires supporte un processus d'arithmétique simplifié, c'est-à-dire que les opérations effectuées sur le corps binaire peuvent être exprimées sous une forme algébrique compacte et facile à vérifier. Ces caractéristiques, combinées à la capacité d'exploiter pleinement ses caractéristiques hiérarchiques grâce à la structure en tour, rendent les corps binaires particulièrement adaptés à des systèmes de preuve évolutifs comme Binius.
Dans ce contexte, "canonical" fait référence à la représentation unique et directe des éléments dans un corps binaire. Par exemple, dans le corps binaire le plus fondamental F2, toute chaîne de k bits peut être directement mappée à un élément du corps binaire de k bits. Cela diffère des corps premiers, qui ne peuvent pas fournir cette représentation canonique dans un nombre de bits donné. Bien qu'un corps premier de 32 bits puisse être contenu dans 32 bits, ce n'est pas le cas pour chaque chaîne de 32 bits qui peut être mappée de manière unique à un élément du corps, tandis que le corps binaire offre la commodité de ce mappage un à un. Dans le corps premier 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 corps finis spécifiques comme Mersenne-31 ou Goldilocks-64. Dans le corps binaire F2k, les méthodes de réduction couramment utilisées incluent la réduction spéciale ) utilisée dans AES, la réduction de Montgomery ### utilisée dans POLYVAL et la réduction récursive ( utilisée dans Tower ). L'article "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" souligne que le corps binaire ne nécessite pas d'introduire des retenues dans les opérations d'addition et de multiplication, et que l'opération de carré dans le corps binaire est très efficace, car elle suit la règle simplifiée (X + Y )2 = X2 + Y2.
Comme illustré dans la figure 1, une chaîne de 128 bits : cette chaîne peut être interprétée de plusieurs manières dans le contexte des domaines binaires. Elle peut être considérée comme un élément unique dans un domaine binaire de 128 bits, ou être analysée comme deux éléments de domaine tour de 64 bits, quatre éléments de domaine tour de 32 bits, 16 éléments de domaine tour de 8 bits, ou 128 éléments de domaine F2. Cette flexibilité de représentation n'implique aucun coût de calcul, il s'agit simplement d'un 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 petits domaines peuvent être empaquetés en éléments de domaines plus grands sans coût de calcul supplémentaire. Le protocole Binius tire parti de cette caractéristique pour améliorer l'efficacité des calculs. De plus, le document "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité de calcul des opérations de multiplication, de mise au carré et d'inversion dans un domaine binaire de n bits ( décomposé en sous-domaines de m bits ).
( 2.2 PIOP: version adaptée de HyperPlonk Product et PermutationCheck------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 de base pour valider la correctitude des polynômes et des ensembles multivariés. Ces vérifications de base comprennent :
GateCheck : vérifier si le témoin secret ω et l'entrée publique x satisfont la relation d'opération du circuit C)x,ω(=0, afin de garantir le bon fonctionnement du circuit.
PermutationCheck : Vérifie si les résultats d'évaluation de deux polynômes multivariables f et g sur l'hypercube booléen sont 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 se trouve 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érifiez si l'évaluation du polynôme rationnel sur le cube hyperbolique 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 multivariable à plusieurs variables est nul en tout point du cube de Boolean ∏x∈Hμ f(x) = 0, ∀x ∈ Bμ, afin de garantir la distribution des zéros du polynôme.
SumCheck : Vérification 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 des polynômes multivariés en un problème d'évaluation de polynômes univariés, on 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 afin de traiter plusieurs instances de vérification de somme.
BatchCheck : basé sur SumCheck, vérifie la justesse de l'évaluation de plusieurs polynômes multivariables pour améliorer l'efficacité du protocole.
Bien que Binius et HyperPlonk aient de nombreuses similitudes dans la conception des protocoles, Binius apporte des améliorations dans les 3 domaines suivants :
Optimisation de ProductCheck : dans HyperPlonk, ProductCheck exige que le dénominateur U soit non nul partout sur l'hypercube, et 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 à traiter correctement les cas de division par zéro, ce qui entraîne l'incapacité d'affirmer que U est non nul sur l'hypercube ; Binius a correctement géré ce problème, même lorsque le dénominateur est zéro, 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, ce qui permet à Binius de gérer des cas de permutations polynomiales plus complexes.
Ainsi, Binius par le biais de