Vitalik : Binius, des preuves efficaces sur les champs binaires
TechFlow SélectionTechFlow Sélection
Vitalik : Binius, des preuves efficaces sur les champs binaires
Binius est un système de preuve basé sur des champs binaires, conçu pour améliorer l'efficacité des preuves cryptographiques, en particulier les preuves associées aux SNARK et aux STARK.
Dédié à des analyses Web3 approfondiesRédaction : Vitalik Buterin
Traduction : Kate, Mars Finance
Cet article s'adresse principalement aux lecteurs ayant une certaine familiarité avec la cryptographie de l'époque 2019, en particulier les SNARK et les STARK. Si ce n'est pas votre cas, je vous recommande de lire d'abord ces articles. Remerciements particuliers à Justin Drake, Jim Posen, Benjamin Diamond et Radi Cojbasic pour leurs retours et commentaires.
Au cours des deux dernières années, les STARK sont devenus une technologie clé et irremplaçable permettant de produire efficacement des preuves cryptographiques facilement vérifiables pour des énoncés très complexes (par exemple, prouver qu'un bloc Ethereum est valide). L'une des raisons principales réside dans la taille du champ : les SNARK basés sur les courbes elliptiques exigent un travail sur des entiers de 256 bits pour garantir une sécurité suffisante, tandis que les STARK autorisent des tailles de champ plus petites, donc plus efficaces : tout d'abord le champ Goldilocks (entiers de 64 bits), puis Mersenne31 et BabyBear (tous deux de 31 bits). Grâce à ces gains d'efficacité, Plonky2 utilisant Goldilocks est des centaines de fois plus rapide que ses prédécesseurs dans la génération de preuves pour divers calculs.
Une question naturelle se pose alors : pouvons-nous pousser cette tendance jusqu'à sa conclusion logique, en construisant un système de preuve encore plus rapide en opérant directement sur des zéros et uns ? C'est précisément ce que tente de faire Binius, en utilisant de nombreuses astuces mathématiques qui le rendent radicalement différent des SNARK et STARK d'il y a trois ans. Cet article explique pourquoi les petits champs rendent la génération de preuves plus efficace, pourquoi les champs binaires possèdent des propriétés particulièrement puissantes, ainsi que les techniques utilisées par Binius pour rendre si efficace la preuve sur des champs binaires.
Binius. À la fin de cet article, vous devriez être capable de comprendre chaque partie de ce schéma.
Rappel : les corps finis (finite fields)
L'une des tâches clés des systèmes de preuve cryptographiques consiste à manipuler de grandes quantités de données tout en gardant les nombres petits. Si vous pouvez compresser un énoncé portant sur un programme complexe en une équation mathématique contenant quelques nombres, mais que ces nombres sont aussi grands que le programme initial, alors vous n'avez rien gagné.
Pour effectuer des calculs arithmétiques complexes tout en maintenant de petits nombres, les cryptographes utilisent habituellement l'arithmétique modulaire. Nous choisissons un nombre premier appelé « module » p. L'opérateur % signifie « prendre le reste » : 15%7=1, 53%10=3, etc. (notez que le résultat est toujours non négatif, donc par exemple -1%10=9).
Vous avez peut-être déjà rencontré l'arithmétique modulaire dans le contexte des heures (par exemple, 9 heures plus 4 heures donne quelle heure ?), mais ici nous n'effectuons pas seulement des additions et soustractions modulo un nombre ; nous pouvons aussi multiplier, diviser et élever à des puissances.
Nous redéfinissons :
Toutes ces règles sont cohérentes entre elles. Par exemple, si p=7, alors :
5+3=1 (car 8%7=1)
1-3=5 (car -2%7=5)
2*5=3
3/5=2
Le terme plus général pour cette structure est un corps fini. Un corps fini est une structure mathématique obéissant aux lois arithmétiques habituelles, mais où le nombre de valeurs possibles est limité, de sorte que chaque valeur peut être représentée par une taille fixe.
L'arithmétique modulaire (ou corps premiers) est le type le plus courant de corps fini, mais il existe un autre type : les extensions de corps. Vous avez peut-être déjà vu une extension de corps : les nombres complexes. Nous « imaginons » un nouvel élément, que nous notons i, et faisons des opérations mathématiques avec lui : (3i+2)*(2i+4)=6i*i+12i+4i+8=16i+2. De même, nous pouvons considérer des extensions de corps premiers. Lorsque nous commençons à travailler avec des corps plus petits, les extensions de corps premiers deviennent cruciales pour préserver la sécurité, et les corps binaires (utilisés par Binius) dépendent entièrement des extensions pour être utiles en pratique.
Rappel : l'arithmétisation
Les SNARK et STARK prouvent l'exécution d'un programme informatique via l'arithmétique : vous transformez un énoncé concernant le programme que vous souhaitez prouver en une équation mathématique impliquant des polynômes. Une solution valide de cette équation correspond à une exécution valide du programme.
Prenons un exemple simple : supposons que j'aie calculé le 100e nombre de Fibonacci et que je veuille vous prouver lequel il est. Je crée un polynôme F codant la suite de Fibonacci : ainsi F(0)=F(1)=1, F(2)=2, F(3)=3, F(4)=5, etc., jusqu'à 100 étapes. La condition que je dois prouver est F(x+2)=F(x)+F(x+1) pour x={0,1…98}. Je peux vous convaincre en vous fournissant le quotient :
où Z(x) = (x-0) * (x-1) * …(x-98). Si je peux fournir F et H satisfaisant cette équation, alors F doit satisfaire F(x+2)-F(x+1)-F(x) sur cet intervalle. Si je vérifie en outre que F(0)=F(1)=1, alors F(100) doit effectivement être le 100e nombre de Fibonacci.
Si vous voulez prouver quelque chose de plus complexe, vous remplacez la relation « simple » F(x+2) = F(x) + F(x+1) par une équation plus compliquée, disant essentiellement que « F(x+1) est le résultat d'une machine virtuelle initialisée à l'état F(x) après un pas de calcul ». Vous pouvez aussi remplacer le nombre 100 par un nombre plus grand, par exemple 100 000 000, pour couvrir davantage d'étapes.
Tous les SNARK et STARK reposent sur cette idée : utiliser des équations simples sur des polynômes (parfois des vecteurs ou matrices) pour représenter de nombreuses relations entre valeurs individuelles. Tous les algorithmes ne vérifient pas comme ci-dessus des égalités entre étapes de calcul adjacentes : par exemple, PLONK et R1CS ne le font pas. Mais beaucoup des méthodes les plus efficaces le font, car répéter plusieurs fois la même vérification (ou un petit nombre de vérifications) permet de minimiser les coûts.
Plonky2 : des SNARK et STARK de 256 bits aux 64 bits... uniquement des STARK
Il y a cinq ans, un bon résumé des différents types de preuves sans connaissance était le suivant. Il existait deux types de preuves : les SNARK (basés sur des courbes elliptiques) et les STARK (basés sur des hachages). Techniquement, les STARK sont une forme de SNARK, mais en pratique on utilise souvent « SNARK » pour désigner les variantes basées sur des courbes elliptiques, et « STARK » pour les constructions basées sur des hachages. Les SNARK sont petits, donc rapides à vérifier et faciles à inclure sur une blockchain. Les STARK sont volumineux, mais ils n'ont pas besoin de configuration fiable et sont résistants au quantique.
Les STARK fonctionnent en traitant les données comme des polynômes, en calculant ces polynômes, et en utilisant la racine de Merkle des données étendues comme « engagement polynomial »
Un point historique important est que les SNARK basés sur des courbes elliptiques ont été largement adoptés en premier : ce n'est qu'autour de 2018 que les STARK sont devenus assez efficaces grâce à FRI, alors que Zcash fonctionnait déjà depuis plus d'un an. Les SNARK basés sur des courbes elliptiques ont une limitation majeure : si vous utilisez un tel SNARK, les calculs arithmétiques dans vos équations doivent être effectués modulo le nombre de points sur la courbe elliptique. Ce nombre est très grand, typiquement proche de 2^256 : par exemple, pour la courbe bn128, il vaut 21888242871839275222246405745257275088548364400416034343698204186575808495617. Pourtant, les calculs réels utilisent des petits nombres : si vous pensez à un programme « réel » dans votre langage favori, la plupart des éléments utilisés sont des compteurs, des indices dans des boucles for, des positions dans le programme, des bits uniques représentant True ou False, et autres objets presque toujours constitués de quelques chiffres seulement.
Même si vos données « brutes » consistent en de « petits » nombres, le processus de preuve nécessite des calculs de quotients, d'extensions, de combinaisons linéaires aléatoires et d'autres transformations de données, conduisant à autant, voire davantage, d'objets dont la taille moyenne atteint celle maximale du champ. Cela crée une inefficacité critique : pour prouver un calcul sur n petites valeurs, vous devez effectuer davantage de calculs sur n valeurs beaucoup plus grandes. Initialement, les STARK ont hérité de l'habitude des SNARK d'utiliser des champs de 256 bits, subissant ainsi la même inefficacité.
Quelques évaluations de polynômes étendues selon Reed-Solomon. Bien que les valeurs initiales soient petites, les valeurs supplémentaires s'étendent toutes à la taille complète du champ (ici, 2^31 - 1)
En 2022, Plonky2 a été publié. Son innovation principale fut d'effectuer l'arithmétique modulo un petit nombre premier : 2^64 - 2^32 + 1 = 18446744067414584321. Désormais, chaque addition ou multiplication peut être réalisée en quelques instructions CPU, et le hachage de toutes les données est quatre fois plus rapide qu'auparavant. Mais cela pose un problème : cette approche ne fonctionne que pour les STARK. Si vous essayez de l'utiliser avec un SNARK, une courbe elliptique aussi petite deviendrait vulnérable.
Pour assurer la sécurité, Plonky2 doit aussi introduire des champs étendus. Une technique clé pour vérifier les équations arithmétiques est l'« échantillonnage aléatoire de points » : si vous voulez vérifier que H(x) * Z(x) = F(x+2)-F(x+1)-F(x), vous choisissez aléatoirement une coordonnée r, fournissez des preuves d'engagement pour H(r), Z(r), F(r), F(r+1) et F(r+2), puis vérifiez si H(r) * Z(r) = F(r+2)-F(r+1)-F(r). Si un attaquant peut deviner la coordonnée à l'avance, il pourrait tromper le système de preuve — c'est pourquoi le choix doit être aléatoire. Cependant, cela signifie que la coordonnée doit être tirée d'un ensemble suffisamment grand pour empêcher l'attaquant de deviner par hasard. Avec un module proche de 2^256, c'est évidemment le cas. Mais avec un module de 2^64 - 2^32 + 1, ce n'est pas encore suffisant, et avec 2^31 - 1, c'est certainement insuffisant. Essayer de falsifier une preuve deux milliards de fois jusqu'à réussir par chance est tout à fait dans les capacités d'un attaquant.
Pour contrer cela, nous échantillonnons r depuis un champ étendu. Par exemple, vous pouvez définir y tel que y³=5, et former des combinaisons de 1, y, y². Cela augmente le nombre total de coordonnées à environ 2^93. La majorité des polynômes calculés par le prouveur n'entrent pas dans ce champ étendu ; ils restent modulo 2^31 - 1, conservant ainsi tous les gains d'efficacité des petits champs. Seules les vérifications sur des points aléatoires et les calculs FRI exploitent pleinement ce champ plus large pour obtenir la sécurité requise.
Des petits nombres premiers aux nombres binaires
Les ordinateurs effectuent l'arithmétique en représentant les grands nombres comme des séquences de 0 et 1, et en construisant des « circuits » sur ces bits pour calculer des opérations comme l'addition et la multiplication. Les ordinateurs sont particulièrement optimisés pour les entiers de 16, 32 et 64 bits. Par exemple, 2^64 - 2^32 + 1 et 2^31 - 1 ont été choisis non seulement parce qu'ils respectent ces seuils, mais aussi parce qu'ils s'y adaptent bien : la multiplication modulo 2^64 - 2^32 + 1 peut être effectuée en utilisant des multiplications régulières de 32 bits, avec des décalages et duplications du résultat à quelques endroits ; cet article explique bien certaines astuces.
Cependant, une meilleure méthode serait de calculer directement en binaire. Et si l'addition pouvait être simplement un XOR, sans avoir à gérer la retenue lorsqu'on ajoute 1+1 sur un bit vers le suivant ? Et si la multiplication pouvait aussi être parallélisée de manière similaire ? Ces avantages proviennent de la capacité à représenter les valeurs vrai/faux par un seul bit.
Profiter directement de ces avantages en calculant en binaire est exactement ce que Binius cherche à faire. L'équipe Binius a montré lors d'un zkSummit des gains d'efficacité impressionnants :
Malgré une « taille » globalement comparable, les opérations sur un champ binaire de 32 bits nécessitent cinq fois moins de ressources de calcul que celles sur un champ de Mersenne de 31 bits.
Des polynômes univariés aux hypercubes
Supposons que nous soyons convaincus par ce raisonnement et que nous voulions tout faire avec des bits (0 et 1). Comment représenter un milliard de bits par un polynôme ?
Ici, nous rencontrons deux problèmes pratiques :
1. Pour un polynôme représentant de nombreuses valeurs, celles-ci doivent être accessibles lors de l'évaluation du polynôme : dans l'exemple de Fibonacci ci-dessus, F(0), F(1)... F(100), et dans un calcul plus grand, les exposants peuvent atteindre plusieurs millions. Notre champ doit contenir des nombres allant jusqu'à cette taille.
2. Tout ce que nous engageons dans un arbre de Merkle (comme tous les STARK) doit être encodé via Reed-Solomon : par exemple, étendre n valeurs à 8n, en utilisant de la redondance pour empêcher un prouveur malveillant de tricher en falsifiant une seule valeur durant le calcul. Cela nécessite aussi un champ suffisamment grand : pour étendre un million de valeurs à 8 millions, vous avez besoin de 8 millions de points distincts pour évaluer le polynôme.
Une idée clé de Binius est de résoudre ces deux problèmes séparément, en représentant les mêmes données de deux façons différentes. D'abord, le polynôme lui-même. Les SNARK basés sur des courbes elliptiques, les STARK de l'ère 2019, Plonky2, etc., manipulent généralement des polynômes à une variable : F(x). En revanche, Binius s'inspire du protocole Spartan et utilise des polynômes multivariés : F(x₁,x₂,…,xₖ). En pratique, nous représentons toute la trajectoire de calcul sous forme d'un « hypercube », où chaque xi vaut 0 ou 1. Par exemple, si nous voulons représenter une suite de Fibonacci, et que nous utilisons encore un champ assez grand pour les contenir, nous pouvons imaginer ses 16 premiers termes ainsi :
Autrement dit, F(0,0,0,0) devrait valoir 1, F(1,0,0,0) aussi 1, F(0,1,0,0) vaut 2, et ainsi de suite jusqu'à F(1,1,1,1)=987. Étant donné un tel hypercube de calcul, il existe un polynôme multilinéaire (de degré 1 en chaque variable) qui produit ces valeurs. Ainsi, nous pouvons voir cet ensemble de valeurs comme une représentation du polynôme ; nous n'avons pas besoin d'en calculer les coefficients.
Bien sûr, cet exemple n'est qu'illustratif : en pratique, tout l'intérêt de l'hypercube est de nous permettre de manipuler des bits individuels. La méthode « native Binius » pour calculer les nombres de Fibonacci consisterait à utiliser un cube en haute dimension, stockant chaque nombre, disons, sur 16 bits. Cela demande de l'ingéniosité pour implémenter l'addition d'entiers au niveau des bits, mais ce n'est pas trop difficile pour Binius.
Passons maintenant aux codes correcteurs d'erreurs. Le fonctionnement des STARK est le suivant : vous prenez n valeurs, Reed-Solomon les étend à davantage de valeurs (généralement 8n, entre 2n et 32n), puis sélectionnez aléatoirement quelques branches de Merkle dans l'extension, et effectuez un certain contrôle dessus. L'hypercube a une longueur de 2 dans chaque dimension. L'étendre directement n'est donc pas pratique : il n'y a pas assez d'espace pour échantillonner des branches de Merkle à partir de 16 valeurs. Alors que faire ? Nous supposons que l'hypercube est un carré !
Binius simplifié – un exemple
Voir ici l'implémentation Python de ce protocole.
Examinons un exemple, utilisant par commodité des entiers ordinaires comme notre champ (dans une implémentation réelle, on utiliserait des éléments de champ binaire). D'abord, nous codons l'hypercube que nous voulons engager en un carré :
Ensuite, nous étendons ce carré via Reed-Solomon. Autrement dit, nous traitons chaque ligne comme un polynôme de degré 3 évalué en x={0,1,2,3}, et nous l'évaluons aux mêmes polynômes en x={4,5,6,7} :
Notez que les nombres grossissent rapidement ! C'est pourquoi, en pratique, nous utilisons toujours des corps finis plutôt que des entiers ordinaires : si nous utilisions des entiers modulo 11, par exemple, l'extension de la première ligne serait simplement [3,10,0,6].
Si vous souhaitez tester l'extension et vérifier vous-même ces valeurs, vous pouvez utiliser mon code simple d'extension Reed-Solomon.
Ensuite, nous considérons cette extension comme des colonnes et créons un arbre de Merkle sur les colonnes. La racine de cet arbre est notre engagement.
Maintenant, supposons que le prouveur veuille prouver à un moment donné le calcul de ce polynôme en un point r={r₀,r₁,r₂,r₃}. Binius comporte une subtilité qui le rend plus faible que d'autres schémas d'engagement polynomial : le prouveur ne doit pas connaître ni pouvoir deviner s avant de s'engager sur la racine de Merkle (autrement dit, r doit être une valeur pseudo-aléatoire dépendant de la racine de Merkle). Cela rend le schéma inutile pour les « recherches dans une base de données » (par exemple : « Bon, tu m'as donné la racine de Merkle, maintenant prouve-moi P(0,0,1,0) ! »). Mais les protocoles de preuve sans connaissance que nous utilisons en pratique n'ont généralement pas besoin de telles recherches ; ils ont juste besoin de vérifier le polynôme en un point d'évaluation aléatoire. Cette restriction convient donc à nos besoins.
Supposons que nous choisissions r={1,2,3,4} (la valeur du polynôme en ce point est alors -137 ; vous pouvez confirmer avec ce code). Maintenant, nous entrons dans le processus de preuve. Nous divisons r en deux parties : la première {1,2} représente la combinaison linéaire des colonnes dans la ligne, la seconde {3,4} représente la combinaison linéaire des lignes. Nous calculons un « produit tensoriel » pour la partie colonne :
Et pour la partie ligne :
Cela signifie : la liste de tous les produits possibles d'un élément de chaque ensemble. Dans le cas des lignes, nous obtenons :
[(1-r₂)*(1-r₃), (1-r₃), (1-r₂)*r₃, r₂*r₃]
Avec r={1,2,3,4} (donc r₂=3 et r₃=4) :
[(1-3)*(1-4), 3*(1-4),(1-3)*4,3*4] = [6, -9, -8, -12]
Maintenant, nous calculons une nouvelle « ligne » t en prenant une combinaison linéaire des lignes existantes. Autrement dit, nous prenons :
Vous pouvez voir cela comme une évaluation partielle. Si vous multipliez le produit tensoriel complet par le vecteur complet des valeurs, vous obtenez P(1,2,3,4) = -137. Ici, nous multiplions seulement par un produit tensoriel partiel utilisant la moitié des coordonnées d'évaluation, réduisant ainsi la grille N×N à une ligne de √N valeurs. Si vous donnez cette ligne à quelqu'un d'autre, il peut terminer le calcul avec le produit tensoriel de l'autre moitié des coordonnées.
Le prouveur fournit au vérificateur cette nouvelle ligne t ainsi que quelques preuves de Merkle pour des colonnes échantillonnées aléatoirement. Dans notre exemple illustratif, nous ferons en sorte que le prouveur fournisse seulement la dernière colonne ; en réalité, il devrait en fournir des dizaines pour assurer une sécurité suffisante.
Maintenant, nous utilisons la linéarité du code Reed-Solomon. La propriété clé est : la combinaison linéaire d'extensions Reed-Solomon donne le même résultat que l'extension Reed-Solomon de la combinaison linéaire. Cette « indépendance d'ordre » survient généralement lorsque les deux opérations sont linéaires.
Le vérificateur fait exactement cela. Il calcule t, puis calcule la même combinaison linéaire des colonnes que le prouveur (mais seulement pour les colonnes fournies), et vérifie que les deux procédés donnent le même résultat.
Dans cet exemple, étendre t et calculer la même combinaison linéaire ([6,-9,-8,12]) donne la même réponse : -10746. Cela prouve que la racine de Merkle a été construite de façon « honnête » (ou du moins « suffisamment proche »), et qu'elle correspond à t : au moins la grande majorité des colonnes sont compatibles entre elles.
Mais le vérificateur doit aussi vérifier une autre chose : la valeur du polynôme en {r₀…r₃}. Jusqu'ici, toutes les étapes du vérificateur n'ont pas dépendu de la valeur que le prouveur affirme. Voici comment nous vérifions cela. Nous prenons le produit tensoriel de la « partie colonne » que nous avons marquée comme point de calcul :
Dans notre exemple, où r={1,2,3,4} donc la moitié des colonnes est {1,2}, cela donne :
Maintenant, nous prenons cette combinaison linéaire de t :
Cela donne le même résultat que l'évaluation directe du polynôme.
Ce qui précède est très proche d'une description complète du protocole « simple » Binius. Il présente déjà certains avantages intéressants : par exemple, puisque les données sont divisées en lignes et colonnes, vous avez besoin d'un champ de taille réduite de moitié. Mais cela n'exploite pas pleinement tous les bénéfices du calcul binaire. Pour cela, nous avons besoin du protocole Binius complet. Mais d'abord, explorons plus profondément les corps binaires.
Corps binaires
Le plus petit corps possible est l'arithmétique modulo 2, si petit que nous pouvons en écrire les tables d'addition et de multiplication :
Nous pouvons obtenir des corps binaires plus grands par extension : partant de F₂ (entiers modulo 2), nous définissons x tel que x²=x+1, obtenant les tables suivantes :
Il s'avère que nous pouvons étendre indéfiniment les corps binaires en répétant cette construction. Contrairement aux réels où vous pouvez ajouter un nouvel élément (i), mais pas continuer indéfiniment (les quaternions existent, mais sont mathématiquement étranges, par exemple ab ≠ ba), avec les corps finis, vous pouvez continuer à ajouter des extensions. Spécifiquement, nous définissons les éléments ainsi :
etc. Cela est souvent appelé structure en tour, car chaque extension successive ajoute un nouveau niveau à la tour. Ce n'est pas la seule façon de construire des corps binaires de taille arbitraire, mais elle présente des avantages uniques que Binius exploite.
Nous pouvons représenter ces nombres comme des listes de bits. Par exemple, 1100101010001111. Le premier bit représente le multiple de 1, le deuxième celui de x₀, puis les suivants représentent les multiples successifs de x₁, x₁*x₀, x₂, x₂*x₀, etc. Ce codage est bon car il peut être décomposé :
Cette notation est relativement inhabituelle, mais j'aime représenter les éléments de corps binaires comme des entiers, avec la convention que les bits de poids faible sont à droite. Ainsi, 1=1, x₀=01=2, 1+x₀=11=3, 1+x₀+x₂=11001000=19, etc. Dans cette expression, c'est 61779.
L'addition dans un corps binaire est simplement un XOR (et la soustraction aussi, d'ailleurs) ; notez que cela implique x+x=0 pour tout x. Pour multiplier deux éléments x*y, il existe un algorithme récursif très simple : divisez chaque nombre en deux moitiés :
Puis décomposez la multiplication :
La dernière partie est la seule un peu délicate, car vous devez appliquer les règles de simplification. Il existe des méthodes plus efficaces pour la multiplication, analogues à l'algorithme de Karatsuba ou à la transformation de Fourier rapide, mais je laisse cela en exercice aux lecteurs intéressés.
La division dans un corps binaire se fait par multiplication combinée à l'inversion. La méthode « simple mais lente » d'inversion utilise le petit théorème de Fermat généralisé. Il existe un algorithme d'inversion plus complexe mais plus efficace, que vous pouvez trouver ici. Vous pouvez utiliser ce code pour expérimenter l'addition, la multiplication et la division dans les corps binaires.
À gauche : table d'addition des éléments à quatre bits dans un corps binaire (soit composés uniquement de 1, x₀, x₁, x₀x₁). À droite : table de multiplication des mêmes éléments.
La beauté de ce type de corps binaire réside dans le fait qu'il combine certains des meilleurs aspects des « entiers normaux » et de l'arithmétique modulaire. Comme les entiers normaux, les éléments de corps binaires sont extensibles à volonté. Mais comme l'arithmétique modulaire, si vous opérez sur des valeurs de taille bornée, tous vos résultats restent dans cette même borne. Par exemple, en prenant les puissances successives de 42, on obtient :
Après 255 étapes, on retrouve 42²⁵⁵=1, comme avec les entiers normaux et l'arithmétique modulaire, ils obéissent aux lois mathématiques habituelles : a*b=b*a, a*(b+c)=a*b+a*c, et même quelques nouvelles lois étranges.
Enfin, les corps binaires gèrent commodément les bits : si vous faites des opérations mathématiques avec des nombres tenus dans 2ᵏ bits, toutes vos sorties tiendront aussi dans 2ᵏ bits. Cela évite les complications. Dans EIP-4844 d'Ethereum, les « blocs » d'un blob doivent être des nombres modulo 52435875175126190479447740508185965837690552500527637822603658699938581184513, donc coder des données binaires nécessite de sacrifier de l'espace et d'ajouter des vérifications applicatives pour s'assurer que chaque élément stocke une valeur inférieure à 2²⁴⁸. Cela signifie aussi que les opérations sur corps binaires sont extrêmement rapides sur ordinateur — que ce soit sur CPU, ou sur FPGA et ASIC théoriquement optimaux.
Tout cela signifie que nous pouvons faire des codages Reed-Solomon comme ci-dessus, d'une manière qui évite complètement l'« explosion » des entiers, comme nous l'avons vu dans notre exemple, et d'une manière très « native » aux calculs que les ordinateurs maîtrisent. La propriété de « décomposition » des corps binaires — la manière dont nous avons écrit 1100101010001111 = 11001010 + 10001111*x₃, puis pouvons continuer à diviser selon nos besoins — est également cruciale pour offrir une grande flexibilité.
Binius complet
Voir ici l'implémentation Python de ce protocole.
Nous pouvons maintenant passer à « Binius complet », qui adapte « Binius simplifié » pour (i) fonctionner sur des corps binaires, (ii) nous permettre d'engager des bits individuels. Ce protocole est difficile à comprendre car il alterne constamment entre différentes façons de voir une matrice de bits ; certes, j'ai mis plus de temps à le comprendre qu'à comprendre habituellement un protocole cryptographique. Mais une fois que vous maîtrisez les corps binaires, la bonne nouvelle est qu'il n'y a plus de « maths difficiles » derrière Binius. Pas de couplages de courbes elliptiques avec leurs abysses croissants de géométrie algébrique ; ici, il n'y a que des corps binaires.
Regardons à nouveau le schéma complet :
Jusqu'ici, vous devriez reconnaître la plupart des composants. L'idée de « platifier » l'hypercube en une grille, celle de calculer les combinaisons de lignes et de colonnes comme produits tensoriels des points d'évaluation, et celle de vérifier l'équivalence entre « étendre Reed-Solomon puis combiner les lignes » et « combiner les lignes puis étendre Reed-Solomon », sont toutes présentes dans Binius simplifié.
Qu'y a-t-il de nouveau dans « Binius complet » ? Trois choses fondamentalement :
• Les valeurs individuelles dans l'hypercube et le carré doivent être des bits (0 ou 1).
• Le processus d'extension consiste à regrouper les bits en colonnes et à les traiter temporairement comme des éléments de champ plus grands, étendant ainsi les bits en davantage de bits.
• Après l'étape de combinaison des lignes, il y a une étape de « décomposition en bits » par élément, ramenant l'extension aux bits.
Nous allons discuter de ces deux cas successivement. D'abord, le nouveau processus d'extension. Les codes Reed-Solomon ont une limite fondamentale : si vous étendez n à k*n, vous devez travailler dans un champ contenant k*n valeurs différentes pouvant servir de coordonnées. Avec F₂ (alias bits), cela est impossible. Nous regroupons donc des éléments adjacents de F₂ en « paquets » formant des valeurs plus grandes. Dans cet exemple, nous empaquetons deux bits à la fois en éléments {0,1,2,3}, ce qui suffit car notre extension n'a que quatre points. Dans une « vraie » preuve, nous empaquetterions probablement 16 bits à la fois. Ensuite, nous appliquons le code Reed-Solomon à ces valeurs empaquetées, puis les désassemblons à nouveau en bits.
Bienvenue dans la communauté officielle TechFlow
Groupe Telegram :https://t.me/TechFlowDaily
Compte Twitter officiel :https://x.com/TechFlowPost
Compte Twitter anglais :https://x.com/BlockFlow_News
@VitalikButerin
