Analyse des principes de Binius STARKs et réflexion sur leur optimisation
1 Introduction
Un des principaux raisons de l'inefficacité des STARKs est que la plupart des valeurs numériques dans les programmes réels sont assez petites, mais 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 de redondance supplémentaires qui occupent tout le domaine, même si la valeur originale elle-même est très petite. Pour résoudre ce problème, 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 des STARKs de deuxième génération est de 64 bits, et celle des STARKs de troisième génération est de 32 bits, mais la largeur de codage de 32 bits présente encore un grand espace gaspillé. En comparaison, le domaine binaire permet d'opérer directement sur les bits, avec un codage compact et efficace sans aucun espace gaspillé, c'est-à-dire les STARKs de quatrième génération.
Comparé aux découvertes récentes sur les corps finis comme Goldilocks, BabyBear et Mersenne31, la recherche sur les corps binaires remonte aux années 1980. Actuellement, les corps binaires sont largement utilisés en cryptographie, des exemples typiques incluent :
Standard de chiffrement avancé ( AES ), basé sur le domaine F28 ;
Galois Message Authentication Code ( GMAC ), basé sur le champ F2128;
QR Code, utilisant un codage Reed-Solomon basé sur F28 ;
Le protocole FRI d'origine et le protocole zk-STARK, ainsi que la fonction de hachage Grøstl, qui a atteint la finale du SHA-3, basée sur le domaine F28, sont des algorithmes de hachage très adaptés à la récursivité.
Lorsqu'on utilise des domaines plus petits, l'opération d'extension de domaine devient de plus en plus importante pour garantir la sécurité. Et le domaine binaire utilisé par Binius doit entièrement dépendre de l'extension de domaine pour assurer sa sécurité et sa réelle utilisabilité. 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 opérer sous le domaine de base, permettant ainsi d'obtenir une grande efficacité dans un petit domaine. 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é requise.
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 trace dans les STARKs, la taille du domaine utilisé doit être supérieure au degré du polynôme ; lors de l'engagement dans l'arbre de Merkle dans les STARKs, il est nécessaire de faire un encodage de Reed-Solomon, et la taille du domaine utilisé doit être supérieure à la taille après l'extension de l'encodage.
Binius a proposé une solution innovante qui traite ces deux problèmes séparément et réalise une représentation des mêmes données de deux manières différentes : tout d'abord, en utilisant des polynômes multivariés (en particulier des polynômes multilinéaires) à la place de polynômes à une seule variable, en représentant l'ensemble de la trajectoire de calcul par ses valeurs sur des "hypercubes" ; ensuite, étant donné que la longueur de chaque dimension de l'hypercube est de 2, il n'est pas possible d'effectuer une extension de Reed-Solomon standard comme avec les STARKs, mais on peut considérer l'hypercube comme un carré, basé sur lequel effectuer une extension de Reed-Solomon. Cette méthode améliore considérablement l'efficacité de codage et les performances 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 à information théorique (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP) : Le PIOP, en tant que système de preuve central, transforme les relations de calcul en égalités polynomiales vérifiables. Différents protocoles PIOP, par l'interaction avec le vérificateur, permettent au prouveur d'envoyer progressivement des polynômes, de sorte que le vérificateur puisse vérifier si le calcul est correct en interrogeant un petit nombre de résultats d'évaluation de polynômes. Les protocoles PIOP existants comprennent : PLONK PIOP, Spartan PIOP et HyperPlonk PIOP, qui traitent chacun les expressions polynomiales de manière différente, influençant ainsi les performances et l'efficacité de l'ensemble du système SNARK.
Schéma d'engagement polynômial (Polynomial Commitment Scheme, PCS) : Le schéma d'engagement polynômial est utilisé pour prouver si l'égalité polynomiale générée par PIOP est valide. Le PCS est un outil cryptographique par lequel le prouveur peut s'engager sur un certain polynôme et 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 polynômial 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'application variés.
Selon les besoins spécifiques, choisissez différents PIOP et PCS, et combinez-les avec un domaine fini ou une courbe elliptique appropriée, pour construire des systèmes de preuve ayant différentes propriétés. Par exemple :
• Halo2 : combinant PLONK PIOP et Bulletproofs PCS, basé sur la courbe Pasta. Lors de la conception de Halo2, l'accent a été mis sur l'évolutivité et l'élimination de la configuration de confiance dans le protocole ZCash.
• Plonky2 : utilise la combinaison de PLONK PIOP et FRI PCS, et est basé sur le domaine de Goldilocks. Plonky2 est conçu pour réaliser une récursivité efficace. 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 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 domaines binaires constitue la base de son calcul, permettant d'effectuer des opérations simplifiées dans le domaine binaire. Deuxièmement, Binius a adapté le produit HyperPlonk et la vérification de permutation dans son protocole de preuve Oracle interactive (PIOP), garantissant une vérification de cohérence 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 pour le mécanisme de recherche. Enfin, le protocole utilise un schéma d'engagement polynomial à petit domaine (Small-Field PCS), lui permettant de réaliser un système de preuve efficace dans le domaine binaire et 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 corps binaires
Les corps binaires en tour sont essentiels pour réaliser des calculs vérifiables rapides, principalement en raison de deux aspects : le calcul efficace et l'arithmétisation efficace. Les corps binaires prennent en charge 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 permet 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, associées à la capacité de tirer pleinement parti de leur hiérarchie grâce à la structure en tour, rendent les corps binaires particulièrement adaptés à des systèmes de preuve évolutifs comme 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 simple 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 de bits donné. Bien qu'un domaine premier de 32 bits puisse être contenu dans 32 bits, chaque chaîne de 32 bits ne correspond pas nécessairement de manière unique à un élément de domaine, alors que le domaine binaire présente cette facilité 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 couramment utilisées incluent la réduction spéciale (comme celle utilisée dans AES), la réduction de Montgomery (comme celle 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 dans le domaine binaire, aucune retenue n'est nécessaire lors des 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 + Y2.
Comme indiqué dans la figure 1, une chaîne de 128 bits : cette chaîne peut être interprétée de différentes 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 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 supplémentaire, mais consiste simplement en 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 petits éléments de domaine peuvent être emballé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. De plus, l'article "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité de calcul des opérations de multiplication, d'élévation au carré et d'inversion dans un domaine binaire de tour de n bits (décomposable en sous-domaines de m bits).
2.2 PIOP : version adaptée du produit HyperPlonk et de la vérification de permutation ------ applicable aux champs binaires
La conception de PIOP dans le protocole Binius s'inspire de HyperPlonk et utilise une série de mécanismes de vérification essentiels pour valider l'exactitude des polynômes et des ensembles multivariés. Ces vérifications essentielles comprennent :
GateCheck : Vérifiez 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érifie si les résultats d'évaluation des deux polynômes multivariés f et g sur le cube de Boolean sont 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 se trouve dans la table de recherche donnée, c'est-à-dire f(Bµ) ⊆ T(Bµ), garantissant 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érifie si l'évaluation d'un polynôme rationnel sur l'hypercube 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érifie si un polynôme multivariable est nul en tout point sur l'hypercube booléen ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, afin d'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 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, construisant des combinaisons linéaires pour réaliser le traitement par lots de plusieurs instances de vérification de somme.
BatchCheck : basé sur SumCheck, vérifie la validité des évaluations de plusieurs polynômes multivariés 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 doit être égal à une valeur spécifique ; Binius simplifie ce processus de vérification en spécialisant cette valeur à 1, réduisant ainsi la complexité de calcul.
Gestion 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 rend impossible d'affirmer que U est non nul sur l'hypercube ; Binius a correctement résolu ce problème, même lorsque le dénominateur est zéro, le ProductCheck de Binius peut continuer à fonctionner, ce qui permet 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 traiter des cas de permutation polynomiale plus complexes.
Ainsi, Binius a amélioré le mécanisme PIOPSumCheck existant, augmentant la flexibilité et l'efficacité du protocole, en particulier lors du traitement de la validation de polynômes multivariables plus complexes, offrant ainsi un meilleur soutien fonctionnel. Ces améliorations non seulement résolvent les limitations de HyperPlonk, mais jettent également les bases pour de futurs systèmes de preuve basés sur des domaines 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 technologies clés, permettant de générer et d'opérer efficacement des polynômes dérivés de gestionnaires 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 adjacents dans l'ordre lexicographique en éléments plus grands. L'opérateur Pack cible les blocs de taille 2κ et les combine en un seul élément dans un domaine de haute dimension. Par extension multilineaire.
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.
Innovation Binius : solution d'optimisation STARKs basée sur le domaine binaire
Analyse des principes de Binius STARKs et réflexion sur leur optimisation
1 Introduction
Un des principaux raisons de l'inefficacité des STARKs est que la plupart des valeurs numériques dans les programmes réels sont assez petites, mais 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 de redondance supplémentaires qui occupent tout le domaine, même si la valeur originale elle-même est très petite. Pour résoudre ce problème, 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 des STARKs de deuxième génération est de 64 bits, et celle des STARKs de troisième génération est de 32 bits, mais la largeur de codage de 32 bits présente encore un grand espace gaspillé. En comparaison, le domaine binaire permet d'opérer directement sur les bits, avec un codage compact et efficace sans aucun espace gaspillé, c'est-à-dire les STARKs de quatrième génération.
Comparé aux découvertes récentes sur les corps finis comme Goldilocks, BabyBear et Mersenne31, la recherche sur les corps binaires remonte aux années 1980. Actuellement, les corps binaires sont largement utilisés en cryptographie, des exemples typiques incluent :
Standard de chiffrement avancé ( AES ), basé sur le domaine F28 ;
Galois Message Authentication Code ( GMAC ), basé sur le champ F2128;
QR Code, utilisant un codage Reed-Solomon basé sur F28 ;
Le protocole FRI d'origine et le protocole zk-STARK, ainsi que la fonction de hachage Grøstl, qui a atteint la finale du SHA-3, basée sur le domaine F28, sont des algorithmes de hachage très adaptés à la récursivité.
Lorsqu'on utilise des domaines plus petits, l'opération d'extension de domaine devient de plus en plus importante pour garantir la sécurité. Et le domaine binaire utilisé par Binius doit entièrement dépendre de l'extension de domaine pour assurer sa sécurité et sa réelle utilisabilité. 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 opérer sous le domaine de base, permettant ainsi d'obtenir une grande efficacité dans un petit domaine. 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é requise.
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 trace dans les STARKs, la taille du domaine utilisé doit être supérieure au degré du polynôme ; lors de l'engagement dans l'arbre de Merkle dans les STARKs, il est nécessaire de faire un encodage de Reed-Solomon, et la taille du domaine utilisé doit être supérieure à la taille après l'extension de l'encodage.
Binius a proposé une solution innovante qui traite ces deux problèmes séparément et réalise une représentation des mêmes données de deux manières différentes : tout d'abord, en utilisant des polynômes multivariés (en particulier des polynômes multilinéaires) à la place de polynômes à une seule variable, en représentant l'ensemble de la trajectoire de calcul par ses valeurs sur des "hypercubes" ; ensuite, étant donné que la longueur de chaque dimension de l'hypercube est de 2, il n'est pas possible d'effectuer une extension de Reed-Solomon standard comme avec les STARKs, mais on peut considérer l'hypercube comme un carré, basé sur lequel effectuer une extension de Reed-Solomon. Cette méthode améliore considérablement l'efficacité de codage et les performances 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 à information théorique (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP) : Le PIOP, en tant que système de preuve central, transforme les relations de calcul en égalités polynomiales vérifiables. Différents protocoles PIOP, par l'interaction avec le vérificateur, permettent au prouveur d'envoyer progressivement des polynômes, de sorte que le vérificateur puisse vérifier si le calcul est correct en interrogeant un petit nombre de résultats d'évaluation de polynômes. Les protocoles PIOP existants comprennent : PLONK PIOP, Spartan PIOP et HyperPlonk PIOP, qui traitent chacun les expressions polynomiales de manière différente, influençant ainsi les performances et l'efficacité de l'ensemble du système SNARK.
Schéma d'engagement polynômial (Polynomial Commitment Scheme, PCS) : Le schéma d'engagement polynômial est utilisé pour prouver si l'égalité polynomiale générée par PIOP est valide. Le PCS est un outil cryptographique par lequel le prouveur peut s'engager sur un certain polynôme et 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 polynômial 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'application variés.
Selon les besoins spécifiques, choisissez différents PIOP et PCS, et combinez-les avec un domaine fini ou une courbe elliptique appropriée, pour construire des systèmes de preuve ayant différentes propriétés. Par exemple :
• Halo2 : combinant PLONK PIOP et Bulletproofs PCS, basé sur la courbe Pasta. Lors de la conception de Halo2, l'accent a été mis sur l'évolutivité et l'élimination de la configuration de confiance dans le protocole ZCash.
• Plonky2 : utilise la combinaison de PLONK PIOP et FRI PCS, et est basé sur le domaine de Goldilocks. Plonky2 est conçu pour réaliser une récursivité efficace. 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 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 domaines binaires constitue la base de son calcul, permettant d'effectuer des opérations simplifiées dans le domaine binaire. Deuxièmement, Binius a adapté le produit HyperPlonk et la vérification de permutation dans son protocole de preuve Oracle interactive (PIOP), garantissant une vérification de cohérence 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 pour le mécanisme de recherche. Enfin, le protocole utilise un schéma d'engagement polynomial à petit domaine (Small-Field PCS), lui permettant de réaliser un système de preuve efficace dans le domaine binaire et 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 corps binaires
Les corps binaires en tour sont essentiels pour réaliser des calculs vérifiables rapides, principalement en raison de deux aspects : le calcul efficace et l'arithmétisation efficace. Les corps binaires prennent en charge 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 permet 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, associées à la capacité de tirer pleinement parti de leur hiérarchie grâce à la structure en tour, rendent les corps binaires particulièrement adaptés à des systèmes de preuve évolutifs comme 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 simple 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 de bits donné. Bien qu'un domaine premier de 32 bits puisse être contenu dans 32 bits, chaque chaîne de 32 bits ne correspond pas nécessairement de manière unique à un élément de domaine, alors que le domaine binaire présente cette facilité 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 couramment utilisées incluent la réduction spéciale (comme celle utilisée dans AES), la réduction de Montgomery (comme celle 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 dans le domaine binaire, aucune retenue n'est nécessaire lors des 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 + Y2.
Comme indiqué dans la figure 1, une chaîne de 128 bits : cette chaîne peut être interprétée de différentes 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 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 supplémentaire, mais consiste simplement en 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 petits éléments de domaine peuvent être emballé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. De plus, l'article "On Efficient Inversion in Tower Fields of Characteristic Two" explore la complexité de calcul des opérations de multiplication, d'élévation au carré et d'inversion dans un domaine binaire de tour de n bits (décomposable en sous-domaines de m bits).
2.2 PIOP : version adaptée du produit HyperPlonk et de la vérification de permutation ------ applicable aux champs binaires
La conception de PIOP dans le protocole Binius s'inspire de HyperPlonk et utilise une série de mécanismes de vérification essentiels pour valider l'exactitude des polynômes et des ensembles multivariés. Ces vérifications essentielles comprennent :
GateCheck : Vérifiez 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érifie si les résultats d'évaluation des deux polynômes multivariés f et g sur le cube de Boolean sont 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 se trouve dans la table de recherche donnée, c'est-à-dire f(Bµ) ⊆ T(Bµ), garantissant 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érifie si l'évaluation d'un polynôme rationnel sur l'hypercube 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érifie si un polynôme multivariable est nul en tout point sur l'hypercube booléen ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, afin d'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 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, construisant des combinaisons linéaires pour réaliser le traitement par lots de plusieurs instances de vérification de somme.
BatchCheck : basé sur SumCheck, vérifie la validité des évaluations de plusieurs polynômes multivariés 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 doit être égal à une valeur spécifique ; Binius simplifie ce processus de vérification en spécialisant cette valeur à 1, réduisant ainsi la complexité de calcul.
Gestion 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 rend impossible d'affirmer que U est non nul sur l'hypercube ; Binius a correctement résolu ce problème, même lorsque le dénominateur est zéro, le ProductCheck de Binius peut continuer à fonctionner, ce qui permet 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 traiter des cas de permutation polynomiale plus complexes.
Ainsi, Binius a amélioré le mécanisme PIOPSumCheck existant, augmentant la flexibilité et l'efficacité du protocole, en particulier lors du traitement de la validation de polynômes multivariables plus complexes, offrant ainsi un meilleur soutien fonctionnel. Ces améliorations non seulement résolvent les limitations de HyperPlonk, mais jettent également les bases pour de futurs systèmes de preuve basés sur des domaines 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 technologies clés, permettant de générer et d'opérer efficacement des polynômes dérivés de gestionnaires d'entrée ou d'autres polynômes virtuels. Voici deux méthodes clés :