1. Introduction

Différents des SNARKs basés sur les courbes elliptiques, les STARKs peuvent être considérés comme des SNARKs basés sur le hachage. L'un des principaux défis contribuant à l'inefficacité actuelle des STARKs est que la plupart des valeurs dans les programmes réels sont relativement petites, tels que les indices dans les boucles for, les valeurs booléennes et les compteurs. Cependant, pour garantir la sécurité des preuves basées sur les arbres de Merkle, le codage Reed-Solomon est utilisé pour étendre les données, ce qui entraîne de nombreuses valeurs redondantes occupant tout le champ, même lorsque les valeurs d'origine elles-mêmes sont petites. Pour remédier à cette inefficacité, la réduction de la taille du champ est devenue une stratégie clé.

Comme indiqué dans le tableau 1, la première génération de STARKs avait une largeur de codage de 252 bits, la deuxième génération de 64 bits et la troisième génération de 32 bits. Malgré la réduction de la largeur de codage dans la troisième génération, il reste un espace significatif gaspillé. En revanche, les champs binaires permettent une manipulation directe des bits, permettant un codage compact et efficace avec un minimum de gaspillage. Cette efficacité est réalisée dans la quatrième génération de STARKs.

Tableau 1: Chemin de dérivation STARKs

En comparaison avec des champs finis tels que Goldilocks, BabyBear, et Mersenne31, qui ont récemment attiré l'attention, la recherche sur les champs binaires remonte aux années 1980. Aujourd'hui, les champs binaires sont largement utilisés en cryptographie, avec des exemples notables incluant:

• Advanced Encryption Standard (AES), basé sur le
• 𝐹28
• champ;
• Code d'authentification de message de Galois (GMAC), basé sur le
• 𝐹2128
• champ;
• Les codes QR, qui utilisent le codage Reed-Solomon basé sur le
• 𝐹28
• champ;
• Les protocoles FRI et zk-STARK originaux, ainsi que la fonction de hachage Grøstl, finaliste de la compétition SHA-3, qui est basée sur le
• F28 (en anglais seulement)
• champ et convient parfaitement aux algorithmes de hachage récursifs.

Lorsque des champs plus petits sont utilisés, les opérations d'extension de champ deviennent de plus en plus importantes pour garantir la sécurité. Le champ binaire utilisé par Binius repose entièrement sur l'extension de champ pour garantir à la fois la sécurité et l'utilisabilité pratique. La plupart des calculs polynomiaux impliqués dans les opérations de vérification n'ont pas besoin d'entrer dans le champ étendu, car ils ont seulement besoin de fonctionner dans le champ de base, ce qui permet d'atteindre une grande efficacité dans le petit champ. Cependant, les vérifications de points aléatoires et les calculs FRI doivent encore être effectués dans un champ étendu plus large pour garantir le niveau de sécurité nécessaire.

Il existe deux défis pratiques lors de la construction d'un système de preuve basé sur des champs binaires : Premièrement, la taille du champ utilisée pour la représentation de la trace dans les STARKs doit être plus grande que le degré du polynôme. Deuxièmement, la taille du champ utilisée pour l'engagement de l'arbre de Merkle dans les STARKs doit être supérieure à la taille après l'extension d'encodage Reed-Solomon.

Binius est une solution innovante pour résoudre ces deux problèmes en représentant les mêmes données de deux manières différentes : premièrement, en utilisant des polynômes multivariés (plus précisément multilinéaires) au lieu de polynômes univariés, représentant l'ensemble de la trace de calcul à travers leurs évaluations sur des « hypercubes ». Deuxièmement, puisque chaque dimension de l'hypercube a une longueur de 2, il n'est pas possible d'effectuer des extensions standard de Reed-Solomon comme dans les STARKs, mais l'hypercube peut être traité comme un carré, et une extension de Reed-Solomon peut être effectuée sur la base de ce carré. Cette méthode garantit non seulement la sécurité, mais améliore également considérablement l'efficacité de codage et les performances de calcul.

2. Principes de Binius

La construction de la plupart des systèmes SNARK modernes se compose généralement des deux composants suivants :

• Preuve Oracle Interactive Polynomiale d'Information-Théorique (PIOP) : En tant que cœur du système de preuve, le PIOP transforme les relations computationnelles de l'entrée en équations polynomiales vérifiables. Différents protocoles PIOP permettent au prouveur d'envoyer des polynômes de manière progressive par des interactions avec le vérificateur. Cela permet au vérificateur de confirmer la correction d'un calcul en interrogeant uniquement un petit nombre d'évaluations polynomiales. Divers protocoles PIOP, tels que PLONK PIOP, Spartan PIOP et HyperPlonk PIOP, gèrent différemment les expressions polynomiales, ce qui influence les performances et l'efficacité du système SNARK dans son ensemble.
• Le schéma d'engagement de polynômes (PCS): Le PCS est un outil cryptographique utilisé pour prouver que les équations polynomiales générées par le PIOP sont valides. Il permet au prouveur de s'engager dans un polynôme et de vérifier ses évaluations sans révéler d'informations supplémentaires sur le polynôme. Les schémas PCS courants comprennent KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP) et Brakedown, chacun offrant des caractéristiques de performances distinctes, des garanties de sécurité et des scénarios applicables.

En sélectionnant différents PIOP et schémas PCS, et en les combinant avec des champs finis ou des courbes elliptiques appropriés, il est possible de construire des systèmes de preuve avec des propriétés distinctes. Par exemple:

• Halo2 : Combine PLONK PIOP avec Bulletproofs PCS et fonctionne sur la courbe Pasta. Halo2 est conçu en gardant à l'esprit la scalabilité et élimine la configuration de confiance précédemment utilisée dans le protocole ZCash.
• Plonky2 : Combine PLONK PIOP avec FRI PCS et est basé sur le champ Goldilocks. Plonky2 est optimisé pour une récursivité efficace.

Lors de la conception de ces systèmes, la compatibilité entre le PIOP, le PCS et le corps fini ou la courbe elliptique choisis est essentielle pour garantir la correction, les performances et la sécurité. Ces combinaisons influencent la taille de la preuve SNARK, l'efficacité de la vérification et déterminent si le système peut atteindre la transparence sans configuration de confiance, ainsi que prendre en charge des fonctionnalités avancées telles que les preuves récursives ou l'agrégation de preuves.

Binius combine HyperPlonk PIOP avec Brakedown PCS et opère dans un champ binaire. Plus précisément, Binius intègre cinq technologies clés pour atteindre à la fois l'efficacité et la sécurité:

1. Arithmétique basée sur des tours de champs binaires : cela forme la base de calcul de Binius, permettant des opérations simplifiées dans le champ binaire.
2. Vérification des produits et des permutations HyperPlonk : Binius adapte les vérifications de produits et de permutations de HyperPlonk dans son PIOP pour assurer une cohérence sécurisée et efficace entre les variables et leurs permutations.
3. Nouvel argument de décalage multilinéaire: cette optimisation améliore la vérification des relations multilinéaires dans de petits champs, améliorant ainsi l'efficacité globale.
4. Argument de recherche Lasso amélioré : le protocole intègre un mécanisme de recherche plus flexible et sécurisé avec cet argument avancé.
5. Schéma d'engagement de polynômes à petit champ (PCS) : Binius utilise un PCS adapté aux petits champs, réduisant les frais généraux généralement associés aux plus grands champs et permettant un système de preuve efficace dans le champ binaire.

Ces innovations permettent à Binius d'offrir un système SNARK compact et performant, optimisé pour les champs binaires tout en maintenant une sécurité et une évolutivité robustes.

2.1 Champs finis : Arithmétique basée sur les tours de champs binaires

Les tours de champs binaires jouent un rôle critique dans la réalisation de calculs rapides et vérifiables en raison de deux facteurs principaux : le calcul efficace et l'arithmétisation efficace. Les champs binaires prennent en charge de manière inhérente des opérations arithmétiques hautement efficaces, ce qui les rend idéaux pour les applications cryptographiques sensibles à la performance. De plus, leur structure permet un processus d'arithmétisation simplifié, où les opérations effectuées dans les champs binaires peuvent être représentées sous des formes algébriques compactes et facilement vérifiables. Ces caractéristiques, combinées à la structure hiérarchique des tours de champs binaires, les rendent 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 un champ binaire. Par exemple, dans le champ binaire le plus basique $\mathbb{F}2

,anyk−bitstringcanbedirectly mappedtoak−bitbinaryfieldelement.Ceci diffère des champs primitifs,qui n’offrent pas une telle représentation canonique dans un nombre donné de bits.Bien qu’un champ à 32 bits puisse s’adapter à l’intérieur de 32 bits,notez que chaquechaîne de 32 bits peut correspondre de manière unique à un élément de champ,tandis que les champs binaires fournissent ceci/unmappage.Inprimefields

\mathbb{F}_p$ , 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écialisées pour certains corps finis comme Mersenne-31 ou Goldilocks-64 . Dans les corps binaires $\mathbb{F}{2^k}$ , les méthodes de réduction courantes comprennent la réduction spéciale (comme utilisée dans AES), la réduction de Montgomery (comme utilisée dans POLYVAL), et la réduction récursive (comme utilisée dans les champs de Tower). Le document Exploration de l'espace de conception du champ premier par rapport aux implémentations matérielles du champ binaire ECCnote que les champs binaires ne nécessitent pas de propagation de retenue lors de l'addition ou de la multiplication, et l'élevation au carré dans les champs binaires est très efficace grâce à la règle de simplification

(𝑋+𝑌)2=𝑋2+𝑌2

.

Figure 1. Les tours du champ binaire

Comme illustré dans la Figure 1, une chaîne de 128 bits peut être interprétée de plusieurs façons dans le contexte d'un champ binaire. Elle peut être considérée comme un élément unique dans le champ binaire de 128 bits, ou elle peut être analysée comme deux éléments de champ de tour de 64 bits, quatre éléments de champ de tour de 32 bits, seize éléments de champ de tour de 8 bits, ou 128 éléments de gate.

𝐹2

. Cette flexibilité de représentation n'entraîne aucune surcharge computationnelle, car il s'agit simplement d'une conversion de type de la chaîne de bits. C'est une propriété très intéressante et utile, car des éléments de champ plus petits peuvent être emballés dans des éléments de champ plus grands sans coût computationnel supplémentaire. Le protocole Binius exploite cette propriété pour améliorer l'efficacité computationnelle. De plus, le document Sur l'inversion efficace dans les champs de tour de caractéristique deuxexplorer la complexité computationnelle de la multiplication, du carré et de l'inversion dans

n

champs binaires de tour de -bit (décomposables en

𝑚

-bit subfields).

2,2 PIOP: Produit HyperPlonk Adapté et Vérification de Permutation - Adapté pour les Champs Binaires

La conception PIOP dans le protocole Binius s'inspire de HyperPlonk et intègre une série de vérifications de base pour vérifier la justesse des polynômes et des ensembles multivariés. Ces vérifications sont essentielles pour garantir l'intégrité des calculs au sein du système de preuve, en particulier lorsqu'ils sont effectués sur des champs binaires. Les principales vérifications comprennent :

1. gateCheck: Garantit que le témoin privé
2. 𝜔
3. et entrée publique
4. 𝑥
5. satisfaire la relation d'opération de circuit
6. 𝐶(𝑥,𝜔)=0
7. , vérifiant l'exécution correcte du circuit.
8. PermutationCheck: Vérifie que les résultats d'évaluation de deux polynômes multivariés
9. 𝑓
10. et
11. 𝑔
12. sur la forme de l'hypercube booléen forment une relation de permutation
13. 𝑓(𝑥)=𝑓(𝜋(𝑥))
14. , en veillant à une cohérence entre les variables polynomiales.
15. LookupCheck: Vérifie si l'évaluation d'un polynôme est dans une table de recherche donnée, c'est-à-dire,
16. 𝑓(𝐵𝜇)⊆𝑇(𝐵𝜇)
17. , en veillant à ce que certaines valeurs se situent dans une plage spécifiée.
18. MultisetCheck: Confirme si deux ensembles multivariés sont égaux, c'est-à-dire, ${(x{1,i},x{2,i})}{i \in H} = {(y{1,i},y{2,i})}{i \in H}$, en veillant à la cohérence entre différents ensembles.
19. ProductCheck: Veille à ce que l'évaluation d'un polynôme rationnel sur l'hypercube booléen soit égale à une valeur déclarée, c'est-à-dire,
20. ∏𝑥∈𝐻𝜇𝑓(𝑥)=𝑠
21. , confirmant la justesse du produit polynomial.
22. ZeroCheck: Vérifie si un polynôme multivarié s'évalue à zéro à n'importe quel point sur l'hypercube booléen, c.-à-d.,
23. ∏𝑥∈𝐻𝜇𝑓(𝑥)=0
24. pour tous
25. 𝑥∈𝐵𝜇
26. , en veillant à une répartition correcte des zéros dans le polynôme.
27. SumCheck: Confirme si la somme des évaluations d'un polynôme multivarié est égale à la valeur déclarée, c'est-à-dire,
28. ∑x∈Hμf(x)=s
29. . En réduisant l'évaluation des polynômes multivariés à l'évaluation des polynômes univariés, elle réduit la complexité computationnelle du vérificateur. SumCheck permet également le regroupement, qui construit des combinaisons linéaires à l'aide de nombres aléatoires pour traiter en lots plusieurs instances.
30. BatchCheck: Une extension de SumCheck, elle vérifie la justesse de multiples évaluations de polynômes multivariés, augmentant l'efficacité du protocole.

Alors que Binius et HyperPlonk partagent plusieurs similitudes dans leurs conceptions de protocole, Binius introduit les améliorations clés suivantes:

1. Optimisation de ProductCheck : Dans HyperPlonk, ProductCheck exige le dénominateur
2. 𝑈
3. pour être non nul sur l'ensemble de l'hypercube et que le produit corresponde à une valeur spécifique. Binius simplifie cette vérification en fixant la valeur du produit à 1, ce qui réduit la complexité globale du calcul.
4. Gestion des problèmes de division par zéro : HyperPlonk ne traite pas efficacement les problèmes de division par zéro, ce qui rend difficile de garantir que
5. 𝑈
6. reste non nul sur l'hypercube. Binius résout cela en traitant correctement les scénarios de division par zéro, permettant à ProductCheck de fonctionner même lorsque le dénominateur est zéro, permettant des extensions à des valeurs de produit arbitraires.
7. Vérification de permutation inter-colonne : HyperPlonk ne prend pas en charge les vérifications de permutation inter-colonne. Binius résout cette limitation en introduisant la prise en charge de la vérification de permutation inter-colonne, permettant au protocole de gérer des permutations polynomiales plus complexes à travers plusieurs colonnes.

Ainsi, Binius améliore la flexibilité et l'efficacité du protocole en améliorant le mécanisme de vérification PIOP SumCheck existant, notamment en fournissant une fonctionnalité plus solide pour la vérification de polynômes multivariés plus complexes. Ces améliorations ne font pas seulement face aux limites de HyperPlonk, mais posent également les bases de systèmes futurs basés sur des champs binaires.

2.3 PIOP: Un nouvel argument de décalage multilinéaire - Applicable à l'hypercube booléen

Dans le protocole Binius, la manipulation et la construction de polynômes virtuels jouent un rôle crucial dans la gestion efficace des polynômes. Deux techniques principales sont utilisées pour ces opérations:

• Emballage: La méthode d'emballage optimise la manipulation des éléments plus petits en les regroupant dans un domaine plus grand. Plus précisément, les éléments adjacents dans l'ordre lexicographique sont regroupés dans des blocs plus grands, généralement de taille
• 2𝜅
• . En exploitant l'extension multilinéaire (MLE), les éléments emballés sont transformés en un nouveau polynôme virtuel, qui peut ensuite être évalué et traité efficacement. Cette méthode améliore les performances des opérations sur l'hypercube booléen en restructurant la fonction
• 𝑡
• dans une forme computationnellement efficace.
• Opérateur de décalage : L'opérateur de décalage réarrange les éléments au sein d'un bloc en les décalant de manière cyclique en fonction d'un décalage donné
• 𝑜
• . Ce changement s'applique aux blocs de taille
• 2b
• , en veillant à ce que tous les éléments d'un bloc soient décalés uniformément en fonction du décalage prédéfini. Cet opérateur est particulièrement utile lorsqu'il s'agit de polynômes virtuels dans des espaces de grande dimension, car sa complexité augmente linéairement avec la taille du bloc, ce qui en fait une technique idéale pour les ensembles de données volumineux ou les calculs complexes d'hypercube booléen.

2.4 PIOP : Un Argument de Recherche de Lasso Adapté - Applicable aux Champs Binaires

Le protocole Lasso dans Binius offre une méthode très efficace pour prouver que les éléments d'un vecteur

𝑎∈𝐹𝑚

sont contenus dans une table prédéfinie

𝑡∈𝐹𝑛

. Cet argument de recherche introduit le concept de « Lookup Singularity » et convient parfaitement aux schémas d'engagement polynomial multilinéaire. L'efficacité de Lasso est mise en évidence dans deux aspects majeurs :

• Efficacité de la preuve : lors de la conduite
• 𝑚
• recherches dans une table de taille
• n
• , le prouveur n'a besoin de s'engager que pour
• 𝑚+𝑛
• petits éléments de terrain, avec la taille du terrain tirée de l'ensemble
• 0,...,𝑚
• . Dans les schémas cryptographiques qui reposent sur l'exponentiation, le coût du prouveur est
• O(m+n)
• opérations de groupe (par exemple, additions de points de courbe elliptique). Cette efficacité s'ajoute au coût de vérification de la correspondance entre un polynôme multilinéaire évalué sur un hypercube booléen et un élément de tableau.
• Aucun engagement envers les grandes tables : Si la table
• 𝑡
• est structuré, Lasso ne nécessite pas d'engagement direct envers la table, ce qui permet de traiter des tables très volumineuses (par exemple,
• 2128
• ou plus). Le temps d'exécution du prouveur dépend uniquement des entrées spécifiques consultées dans la table. Pour tout paramètre entier
• 𝑐>1
• , le coût principal concerne la taille de la preuve, qui augmente à mesure que
• 3⋅𝑐⋅𝑚+𝑐⋅𝑛1/𝑐
• éléments de terrain engagés. Ces éléments sont également petits, tirés de l'ensemble
• 0,…,max𝑚,𝑛1/𝑐,𝑞−1
• , où
• 𝑞
• est la plus grande valeur du vecteur
• a
• .

Le protocole Lasso se compose de trois composants principaux:

1. Abstraction polynomiale virtuelle de grandes tables : Le protocole Lasso combine des polynômes virtuels pour permettre des recherches et des opérations efficaces sur de grandes tables, garantissant une évolutivité sans dégradation des performances.
2. Petite recherche de table : Au cœur de Lasso se trouve la petite recherche de table, qui vérifie si un polynôme virtuel évalué sur un hypercube booléen est un sous-ensemble des évaluations d'un autre polynôme virtuel. Ce processus est semblable à une détection de mémoire hors ligne et se résume à une tâche de détection de multiconjoints.
3. Vérification multiconjoints : Le protocole intègre également un mécanisme virtuel pour effectuer des vérifications multiconjoints, garantissant que deux ensembles d'éléments correspondent ou remplissent des conditions prédéfinies.

Le protocole Binius adapte Lasso aux opérations sur les champs binaires, en supposant que le champ actuel est un champ premier de grande caractéristique (beaucoup plus grand que la longueur de la colonne recherchée). Binius introduit une version multiplicative du protocole Lasso, obligeant le prouveur et le vérificateur à incrémenter l'opération de “compteur de mémoire” du protocole non pas simplement en ajoutant 1 mais en incrémentant à l'aide d'un générateur multiplicatif dans le champ binaire. Cependant, cette adaptation multiplicative introduit une complexité supplémentaire : contrairement à une incrémentation additive, le générateur multiplicatif n'incrémente pas dans tous les cas, ayant plutôt une seule orbite à 0, ce qui peut présenter un vecteur d'attaque. Pour atténuer cette attaque potentielle, le prouveur doit s'engager à un vecteur de compteur de lecture qui est non nul partout pour assurer la sécurité du protocole.

2,5 PCS : PCS de panne adapté – Applicable aux petits champs

L'idée centrale derrière la construction du Binius PCS (Polynomial Commitment Scheme) est l'emballage. Le document Binius présente deux schémas PCS Brakedown basés sur des champs binaires : l'un instancié en utilisant des codes concaténés, et l'autre en utilisant un codage au niveau du bloc, qui prend en charge l'utilisation autonome des codes Reed-Solomon. Le deuxième schéma PCS Brakedown simplifie le processus de preuve et de vérification, bien qu'il produise une taille de preuve légèrement plus grande que le premier ; cependant, ce compromis en vaut la peine en raison des avantages de simplification et d'implémentation qu'il offre.

L'engagement polynomial de Binius utilise principalement l'engagement polynomial de petit champ avec des évaluations dans un champ étendu, une construction universelle de petit champ et un codage au niveau des blocs avec des techniques de code Reed-Solomon.

Engagement de polynômes à petit champ avec évaluation de champ étendu Dans le protocole Binius, les engagements de polynômes sont effectués sur un petit champ

𝐾

, avec des évaluations ayant lieu dans un champ étendu

L/K

. Cette technique permet de s’assurer qu’un polynôme multilinéaire

t(X0,...,Xl−1)

appartient au domaine

𝐾[𝑋0,…,𝑋ℓ−1]

, tandis que les points d'évaluation sont dans le champ plus large

𝐿

. Cette structure d'engagement permet des requêtes efficaces dans le domaine étendu, équilibrant la sécurité et l'efficacité computationnelle.

Construction universelle de petit champ Cette construction définit les paramètres clés tels que le champ

𝐾

, sa dimension

ℓ

, et le code de bloc linéaire associé

𝐶

, tout en veillant à ce que le champ étendu

𝐿

est suffisamment grand pour des évaluations sécurisées. En exploitant les propriétés du champ étendu, Binius parvient à des engagements robustes grâce à des codes linéaires en bloc, maintenant un équilibre entre l'efficacité computationnelle et la sécurité.

Encodage au niveau du bloc avec des codes de Reed-Solomon pour les polynômes définis sur de petits champs comme $\mathbb{F}2

Ce schéma permet d’engager efficacement des polynômes de petit champ en les codant ligne par ligne dans des champs plus grands (tels que :

\mathbb{F}{2^{16}}$ ), utilisant l'efficacité et les propriétés de séparation de distance maximale des codes Reed-Solomon. Après l'encodage, ces lignes sont engagées à l'aide d'un arbre de Merkle, ce qui simplifie la complexité opérationnelle des engagements polynomiaux en petit champ. Cette approche permet une manipulation efficace des polynômes dans de petits champs sans la charge computationnelle généralement associée à des champs plus importants.

3. Optimisations Binius

Pour améliorer encore les performances, Binius intègre quatre optimisations majeures :

1. PIOP basé sur GKR : Le protocole GKR (Goldreich-Kalai-Rothblum) est utilisé pour remplacer l'algorithme de recherche en lasso dans la multiplication de champs binaires, ce qui réduit considérablement les frais généraux dans le processus d'engagement.
2. Optimisation ZeroCheck PIOP : Cette optimisation traite de l'équilibre entre les coûts computationnels du prouveur et du vérificateur, rendant l'opération ZeroCheck plus efficace en distribuant la charge de travail de manière plus efficace.
3. Optimisation de PIOP Sumcheck : En optimisant le processus de Sumcheck en petit champ, Binius réduit la charge de calcul globale lorsqu'il opère sur de petits champs.
4. Optimisation PCS : En utilisant l'optimisation FRI-Binius (preuves interactives de proximité Fast Reed-Solomon Oracle de Binius), Binius réduit la taille de la preuve et améliore les performances du protocole, améliorant ainsi l'efficacité globale à la fois dans la génération de preuves et la vérification.

3.1 PIOP basé sur GKR : multiplication de champs binaires utilisant GKR

Dans le protocole Binius original, la multiplication de champs binaires est gérée par un schéma basé sur la recherche, qui lie la multiplication à des opérations d’addition linéaires basées sur le nombre de membres d’un mot. Bien que cette méthode optimise la multiplication binaire dans une certaine mesure, elle introduit toujours des engagements auxiliaires linéairement liés au nombre de membres. En adoptant une approche basée sur GKR, le protocole Binius peut réduire considérablement le nombre d’engagements requis, ce qui permet d’accroître l’efficacité des opérations de multiplication de champs binaires.

L'idée principale du protocole GKR (Goldwasser-Kalai-Rothblum) est d'obtenir un accord entre le Prover (P) et le Vérificateur (V) sur un circuit arithmétique en couches sur un champ fini.

𝐹

Chaque nœud dans ce circuit a deux entrées pour calculer la fonction requise. Pour réduire la complexité de calcul du Vérificateur, le protocole utilise le protocole SumCheck, qui réduit progressivement les revendications sur les valeurs de porte de sortie du circuit aux valeurs de porte de couche inférieure, simplifiant finalement les revendications en déclarations sur les entrées. De cette façon, le Vérificateur n'a besoin que de vérifier la justesse des entrées du circuit.

La Algorithme de multiplication d'entiers basé sur GKRdans Binius transforme la vérification de deux entiers de 32 bits

𝐴

et

𝐵

satisfaire

𝐴⋅𝐵=?𝐶

en vérifiant si

(gA)B= ?gC

contient dans

Réf. F264∗

Cette transformation, combinée au protocole GKR, réduit considérablement les frais associés aux engagements polynomiaux. Comparé au précédent schéma basé sur la recherche Binius, l'approche de multiplication basée sur GKR ne nécessite qu'un seul engagement auxiliaire et réduit le coût des SumChecks, rendant l'algorithme plus efficace, en particulier dans les cas où les SumChecks sont plus économiques que des engagements supplémentaires. Cette méthode devient une solution prometteuse pour minimiser les coûts d'engagement polynomiaux dans les champs binaires à mesure que les optimisations de Binius progressent.

3.2 Optimisation ZeroCheck PIOP : Équilibrage des coûts de calcul entre le prouveur et le vérificateur

Le papier Quelques améliorations pour le PIOP pour ZeroCheckpropose des stratégies pour équilibrer les coûts de calcul entre le Prover (P) et le Verifier (V), en mettant l'accent sur la réduction de la transmission de données et de la complexité de calcul. Ci-dessous sont les principales techniques d'optimisation :

• Réduction de la transmission de données du Prover

En transférant une partie de la charge de calcul au Vérificateur, la transmission des données du Proverbe peut être réduite au minimum. Par exemple, dans le tour

𝑖

, le Prover envoie

vi+1(X)

pour

𝑋=0,…,𝑑+1

, et le vérificateur vérifie si

𝑣𝑖=𝑣𝑖+1(0)+𝑣𝑖+1(1)

tient.

Optimisation : Le Prover peut éviter d'envoyer

vi+1(1)

, comme le Vérificateur peut le calculer comme

𝑣𝑖+1(1)=𝑣𝑖−𝑣𝑖+1(0)

.

Dans le tour initial, le Prover envoie

𝑣1(0)=𝑣1(1)=0

, ce qui élimine certains calculs d’évaluation, ce qui réduit à la fois les coûts de calcul et de transmission

𝑑2𝑛−1𝐶𝐹+(𝑑+1)2𝑛−1𝐶𝐺

.

• Réduction du nombre de points d'évaluation pour le prouveur

Pendant la ronde

Je

, le Prover doit envoyer

𝑣𝑖+1(𝑋)

, calculé comme

𝑣𝑖+1(𝑋)=∑𝑥∈𝐻𝑛−𝑖−1𝛿^𝑛(𝛼,(𝑟,𝑋,𝑥))𝐶(𝑟,𝑋,𝑥)

.

Optimisation : Au lieu de cela, le Prover peut envoyer

𝑣𝑖+1′(𝑋)=∑𝑥∈𝐻𝑛−𝑖−1𝛿^𝑛(𝛼𝑖+1,…,𝛼𝑛−1,𝑥)𝐶(𝑟,𝑋,𝑥),

où $v_i(X) = v_i'(X) \cdot \hat{\delta}{i+1}((\alpha_0, \dots, \alpha_i), (r, X))

.𝐴𝑠𝑡ℎ𝑒𝑉𝑒𝑟𝑖𝑓𝑖𝑒𝑟ℎ𝑎𝑠𝑎𝑐𝑐𝑒𝑠𝑠𝑡𝑜

\alpha

𝑎𝑛𝑑

r

,𝑡ℑ𝑡ℎ𝑒𝑑𝑒𝑔𝑟𝑒𝑒𝑜𝑓

v_i'(X)

islowertainmentof

v_i(X)

,en réduisant les points d’évaluation requis.Le contrôle inter−rond peut alors être simplifié

(1 - \alphai)v{i+1}’(0) + \alpha_i v{i+1}’(1) = v_i’(X),

𝑡ℎ𝑒𝑟𝑒𝑏𝑦𝑙𝑜𝑤𝑒𝑟𝑖𝑛𝑔𝑑𝑎𝑡𝑎𝑡𝑟𝑎𝑛𝑠𝑚𝑖𝑠𝑠𝑖𝑜𝑛𝑛𝑒𝑒𝑑𝑠𝑎𝑛𝑑𝑒𝑛ℎ𝑎𝑛𝑐𝑖𝑛𝑔𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑐𝑦.𝑊𝑖𝑡ℎ𝑡ℎ𝑒𝑠𝑒𝑖𝑚𝑝𝑟𝑜𝑣𝑒𝑚𝑒𝑛𝑡𝑠,𝑡ℎ𝑒𝑜𝑣𝑒𝑟𝑎𝑙𝑙𝑐𝑜𝑠𝑡𝑖𝑠𝑎𝑝𝑝𝑟𝑜𝑥𝑖𝑚𝑎𝑡𝑒𝑙𝑙𝑦

2^{n-1}(d - 1)C_F + 2^{n-1}dC_G.

Pour

d = 3$ , ces optimisations permettent une réduction des coûts d'un facteur de 5/3.

• Optimisation de l'interpolation algébrique

Pour un Prover honnête, le polynôme

𝐶(𝑥0,…,𝑥𝑛−1)

est nul sur

𝐻𝑛

et peut être exprimé comme

𝐶(𝑥0,…,𝑥𝑛−1)=∑𝑖=0𝑛−1𝑥𝑖(𝑥𝑖−1)𝑄𝑖(𝑥0,…,𝑥𝑛−1)

. Où

𝑄𝑖

est calculé par division polynomiale ordonnée, en commençant par

𝑅𝑛=𝐶

. Division séquentielle par

𝑥𝑖(𝑥𝑖−1)

calcule

𝑄𝑖

et

𝑅𝑖

, avec

𝑅0

représentant l'extension multilinéaire de

𝐶

sur

𝐻𝑛

, supposé être zéro.

Analyse des degrés de

QI

. Pour

𝑗>𝑖

,

𝑄𝑗

reste au même niveau dans

𝑥𝑖

comme

𝐶

. Pour

𝑗=𝑖

, le degré est réduit de 2, et pour

𝑗<𝑖

, le degré est au plus 1. Étant donné un vecteur

𝑟=(𝑟0,…,𝑟𝑖)

,

𝑄𝑗(𝑟,𝑋)

est multilinéaire pour tous

𝑗≤𝑖

. De plus,

𝑄𝑖(𝑟,𝑋)=∑𝑗=0𝑖𝑟𝑗(𝑟𝑗−1)𝑄𝑗(𝑟,𝑋)

est le polynôme multilinéaire unique correspondant

C(r,X)

sur

𝐻𝑛−𝑖

. Pour toute

𝑋

et

𝑥∈𝐻𝑛−𝑖−1

, cela peut être représenté comme

𝐶(𝑟,𝑋,𝑥)−𝑄𝑖(𝑟,𝑋,𝑥)=𝑋(𝑋−1)𝑄𝑖+1(𝑟,𝑋,𝑥).

Ainsi, lors de chaque tour du protocole, un nouveau

𝑄

est introduit, et son évaluation peut être dérivée de

𝐶

et le précédent

𝑄

, permettant une optimisation d'interpolation.

3.3 Optimisation de PIOP Sumcheck: protocole de vérification de somme de petit champ

Dans le protocole STARKs mis en œuvre par Binius, le principal goulot d'étranglement pour le prouveur est souvent le protocole de vérification de la somme plutôt que le schéma d'engagement polynômial (PCS), en raison du faible coût de l'engagement.

Figure 2. Relation entre le tour de basculement et l'amélioration du facteur

En 2024, Ingonyama a proposé améliorations pour les protocoles Sumcheck basés sur les petits champs, en se concentrant sur les algorithmes 3 et 4. Ces améliorations ont été mises en œuvre et rendues publiques ici. L'algorithme 4 intègre l'algorithme de Karatsuba dans l'algorithme 3, réduisant ainsi le nombre de multiplications de champ d'extension en échange de plus de multiplications de champ de base. Cette approche est plus efficace lorsque les multiplications de champ d'extension sont plus coûteuses que celles de champ de base.

1. L'impact des tours de basculement et des facteurs d'amélioration L'optimisation du protocole de vérification de somme de petit champ dépend de la sélection du tour de basculement optimal

𝑡

, qui marque le moment où le protocole revient de la version optimisée à l'algorithme naïf. Les expériences indiquent que le facteur d'amélioration atteint son maximum au point de basculement optimal, puis suit une tendance parabolique. Lorsque ce point est dépassé, l'efficacité diminue car le rapport entre les multiplications du champ de base et du champ d'extension est plus élevé dans les champs plus petits, ce qui nécessite un retour opportun à l'algorithme naïf.

Pour certaines applications, comme le Cubic Sumcheck (

𝑑=3

), le protocole Sumcheck à petit champ offre une amélioration d'un ordre de grandeur par rapport à l'approche naïve. Par exemple, dans le champ de base

𝐺𝐹[2]2. Impact de la taille du champ de base sur les performances Des champs de base plus petits (par exemple,

, L'algorithme 4 surpasse l'algorithme naïf de près de 30 fois.

GF[2]

) améliorer considérablement l'efficacité de l'algorithme optimisé en raison de la plus grande disparité entre les coûts des multiplications dans le champ d'extension et le champ de base. Cela conduit à un facteur d'amélioration plus important pour l'algorithme optimisé.

1. Les gains d'optimisation de l'algorithme de Karatsuba L'algorithme de Karatsuba joue un rôle crucial dans l'amélioration des performances du protocole de vérification de somme de petit champ. Pour un champ de base de

𝐺𝐹[2]

, L'algorithme 4 atteint des facteurs d'amélioration maximale de 6 pour l'algorithme 3 et de 30 pour l'algorithme 4, ce qui indique que l'algorithme 4 est cinq fois plus efficace que l'algorithme 3. L'algorithme de Karatsuba améliore l'efficacité d'exécution et optimise le point de basculement pour les deux algorithmes, avec des points optimaux à

t=5

pour l'algorithme 3 et

𝑡=8

pour l'algorithme 4.

1. Améliorations de l'efficacité de la mémoire Le protocole de vérification de somme à petit champ améliore également l'efficacité de la mémoire. L'algorithme 4 nécessite

𝑂(𝑑⋅𝑡)

la mémoire, tandis que l'algorithme 3 a besoin de

𝑂(2𝑑⋅𝑡)

mémoire. Pour

𝑡=8

, l’algorithme 4 n’utilise que 0,26 Mo de mémoire, contre 67 Mo pour l’algorithme 3. Cela rend l’algorithme 4 particulièrement adapté aux environnements à mémoire limitée, tels que la preuve côté client avec des ressources limitées.

3.4 PCS Optimisation: FRI-Binius Réduction de la taille de preuve Binius

L’un des principaux défis du protocole de Binius est sa taille de preuve relativement grande, qui s’adapte à la racine carrée de la taille du témoin à

𝑂(𝑁)

. Cette mise à l'échelle de la racine carrée limite sa compétitivité par rapport aux systèmes offrant des preuves plus succinctes. En revanche, des tailles de preuves polylogarithmiques, comme celles obtenues par des systèmes avancés tels que Plonky3 grâce à des techniques telles que FRI, sont essentielles pour garantir des vérificateurs vraiment « succincts ». L'optimisation FRI-Binius vise à réduire la taille de la preuve de Binius et à améliorer ses performances globales par rapport à des systèmes plus efficaces.

Le papierPreuves polylogarithmiques pour des multilinéaires sur des tours binaires, appelé FRI-Binius, introduit un nouveau mécanisme de pliage FRI (preuve de proximité interactive Reed-Solomon rapide) basé sur le champ binaire avec quatre innovations clés:

• Polynômes aplatis: Transforme le polynôme multilinéaire initial en une base de polynômes de hauteur à faible code (LCH) pour une computation optimisée.
• Polynômes de disparition des sous-espaces : utilise ces polynômes conjointement avec une transformée NTT (Nombre Théorique des Nombres) additive pour permettre une décomposition similaire à FFT, optimisant les opérations sur le champ des coefficients.
• Emballage sur base algébrique : facilite l'emballage efficace des données, minimisant le surdébit du protocole lié à l'incorporation.
• Ring-Switching SumCheck: Une nouvelle optimisation SumCheck utilisant des techniques de commutation d'anneau pour améliorer encore les performances.

Processus central du schéma d'engagement polynomial multilinéaire (PCS) FRI-Binius

Le protocole FRI-Binius optimise les schémas d'engagement polynomiaux multilinéaires (PCS) sur le champ binaire en transformant le polynôme multilinéaire initial, défini sur le champ binaire

𝐹2

, en un polynôme multilinéaire sur un champ plus grand

𝐾

.

1. Phase d'engagement La phase d'engagement transforme un
2. ℓ
3. -polynôme multilinéaire variable (sur $\mathbb{F}2
4. )𝑖𝑛𝑡𝑜𝑎𝑐𝑜𝑚𝑚𝑖𝑡𝑚𝑒𝑛𝑡𝑓𝑜𝑟𝑎𝑝𝑎𝑐𝑘𝑒𝑑
5. \ell'
6. −𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒𝑚𝑢𝑙𝑡𝑖𝑙𝑖𝑛𝑒𝑎𝑟𝑝𝑜𝑙𝑦𝑛𝑜𝑚𝑖𝑎𝑙(𝑜𝑣𝑒𝑟
7. \mathbb{F}{2^{128}}$ ). Ce processus réduit le nombre de coefficients d'un facteur de 128, ce qui permet une génération de preuves plus efficace.
8. Phase d'évaluation Dans cette phase, le prouveur et le vérificateur exécutent
9. ℓ′
10. des rounds d'un protocole de vérification de somme de commutation d'anneaux croisés combiné avec des preuves d'oracle interactives de proximité (IOPP) FRI. Les détails clés comprennent:
    • Preuves d'ouverture FRI: Elles constituent la majorité de la taille de la preuve et sont traitées de manière similaire aux preuves FRI standard sur de grands champs.
    • Coût de vérification de la somme du prouveur : Comparable au coût d'exécution de SumCheck dans un grand champ.
    • Coût FRI du vérificateur : Correspond aux coûts FRI standard observés dans les implémentations de grands champs.
    • Opérations du vérificateur: Le vérificateur reçoit 128 éléments de
    • 𝐹2128
    • et effectue 128 multiplications supplémentaires, permettant une vérification efficace.

Avantages de FRI-Binius

En appliquant cette méthode, Binius est capable de réduire la taille de sa preuve d'un ordre de grandeur, la rapprochant des performances des systèmes cryptographiques de pointe, tout en restant compatible avec les champs binaires. La méthode de pliage FRI, optimisée pour les champs binaires, combinée à des emballages algébriques et des optimisations SumCheck, aide Binius à générer des preuves plus petites sans compromettre l'efficacité de la vérification.

Cette transformation marque une étape importante vers l'amélioration de la taille de la preuve dans Binius, en veillant à ce qu'elle devienne plus compétitive avec d'autres systèmes de pointe, en particulier ceux axés sur des tailles de preuve polylogarithmiques.

Tableau 2 : Comparaison de la taille de preuve entre Binius et FRI-Binius

Table 3: Comparaison entre Plonky3 FRI et FRI-Binius

4. Conclusion

Toute la proposition de valeur de Binius réside dans sa capacité à utiliser la plus petite taille de champ de puissance de deux pour les témoins, en sélectionnant la taille de champ selon les besoins. Binius est un schéma de co-conception pour « le matériel, les logiciels et les protocoles Sumcheck accélérés par FPGA », permettant des preuves rapides avec une très faible utilisation de la mémoire.

Les systèmes de preuve tels que Halo2 et Plonky3 impliquent quatre étapes clés intensives en calcul : la génération des données de témoin, l'engagement envers les données de témoin, l'exécution d'un argument de disparition et la génération de la preuve d'ouverture.

Par exemple, avec la fonction de hachage Keccak dans Plonky3 et la fonction de hachage Grøstl dans Binius, la distribution computationnelle pour ces quatre étapes clés est illustrée à la Figure 3.

Figure 3. Coût de validation plus petit

Cette comparaison montre que Binius a essentiellement éliminé le goulot d'étranglement de l'engagement du prouveur. Le nouveau goulot d'étranglement est le protocole Sumcheck, où des problèmes tels que de nombreuses évaluations de polynômes et des multiplications de champs peuvent être efficacement résolus avec du matériel spécialisé.

Le schéma FRI-Binius, une variante de FRI, offre une option très attrayante en supprimant les frais d'intégration de la couche de preuve sur le terrain sans entraîner une augmentation significative des coûts dans la couche de preuve agrégée.

Actuellement, l'équipe Irreducible développe sa couche récursive et aa annoncé un partenariat avec l'équipe Polygon pour construire un zkVM basé sur Binius; le Jolt zkVM passe de Lasso à Binius pour améliorer ses performances récursives; et l' L'équipe Ingonyama met en œuvre une version FPGA de Binius.

Références

1. 2024.04 Binius Succinct Arguments over Towers of Binary Fields
2. 2024.07 Preuves polylogarithmiques de Fri-Binius pour les multilinéaires sur les tours binaires
3. 2024.08 Multiplication d’entiers dans Binius : approche basée sur GKR
4. 2024.06 zkStudyClub - FRI-Binius: Preuves polylogarithmiques pour les multilinéaires sur les tours binaires
5. 2024.04 ZK11: Binius: un SNARK optimisé pour le matériel - Jim Posen
6. 2023.12 Épisode 303 : Plongée dans Binius avec Ulvetanna
7. 2024.09 Conception de zkVMs haute performance
8. 2024.07 Sumcheck et Open-Binius
9. 2024.04 Binius: preuves hautement efficaces sur les champs binaires
10. 2023.12 SNARKs sur les champs binaires: Binius - Partie 1
11. 2024.06 SNARKs sur les champs binaires : Binius - Partie 2
12. @espressosys/hyperplonk-a-zk-proof-system-for-zkevms-d45fd077bfba">2022.10 HyperPlonk, un système de preuve zk pour ZKEVMs

Disclaimer :

1. Cet article est repris de [ bitlayer]. Tous les droits d'auteur appartiennent à l'auteur original [lynndell]. S’il y a des objections à cette réimpression, veuillez contacter le Porte d’apprentissageéquipe, et ils s'en occuperont rapidement.
2. Clause de non-responsabilité: Les vues et opinions exprimées dans cet article ne sont que celles de l'auteur et ne constituent en aucun cas des conseils en investissement.
3. Les traductions de l'article dans d'autres langues sont effectuées par l'équipe de Gate Learn. Sauf mention contraire, la copie, la distribution ou le plagiat des articles traduits est interdit.