Voir la table des matières Ne plus voir la table des matières
- Qu’est-ce qu’un arbre de Verkle ?
- Pourquoi Ethereum a-t-il besoin de preuves plus courtes ?
- Quelles ruptures l’EIP introduit-il dans la structure de l’arbre ?
- Que vient faire la courbe Bandersnatch dans l’affaire ?
- Comment les valeurs sont-elles rangées dans les feuilles ?
- Insérer une valeur quand deux tiges se ressemblent
- Ce que les arbres de Verkle engagent pour la suite d’Ethereum
Un arbre de Verkle est une structure de données cryptographique qui remplit la même fonction qu’un arbre de Merkle : ranger une grande quantité d’informations de façon à pouvoir prouver la présence de n’importe quel élément à qui ne détient que la racine de l’arbre. La différence tient dans un seul chiffre. Là où une preuve de Merkle pèse environ un kilooctet, la preuve équivalente dans un arbre de Verkle tient sous 150 octets.
Cette réduction n’est pas une coquetterie d’ingénieur. Elle conditionne l’arrivée des clients sans état, ces logiciels capables de valider les blocs d’Ethereum sans conserver l’intégralité des comptes et des données de stockage. La Fondation Ethereum a publié le 2 décembre 2021, sous la signature de Guillaume Ballet et Dankrad Feist, un billet décrivant l’agencement concret retenu dans le projet d’EIP consacré à ces arbres.
Le sujet a la réputation d’être hermétique, et il l’est en partie. Les briques restent pourtant abordables une fois posées dans l’ordre, et l’enjeu vaut l’effort pour quiconque suit la trajectoire du réseau au-delà du prochain trimestre. Qu’est-ce qui change réellement quand on remplace un hachage par un engagement vectoriel ?
Qu’est-ce qu’un arbre de Verkle ?
Un arbre de Verkle est un schéma d’engagement qui fonctionne comme un arbre de Merkle, mais dont les témoins sont beaucoup plus petits. Le principe consiste à remplacer les hachages par un engagement vectoriel, ce qui rend enfin rentables les facteurs de ramification larges. Le projet d’Ethereum retient une largeur de 256 enfants par nœud.
Ce que change l’engagement vectoriel
Un engagement vectoriel est une fonction de hachage particulière. Elle transforme une liste de valeurs en une empreinte unique, mais elle autorise en plus une opération qu’un hachage ordinaire ne permet pas : produire une preuve courte que la valeur occupant la i-ième position de la liste engagée est bien celle qu’on annonce.
Le schéma retenu s’appuie sur les engagements de Pedersen, construits sur des courbes elliptiques. Cette primitive remplace, dans la preuve, le rôle que jouaient les nœuds frères d’un arbre de Merkle classique. Le vérificateur obtient la même certitude sans recevoir la même quantité de données, et c’est tout le gain de place.
Pourquoi un arbre de Merkle atteint sa limite
Dans un arbre de Merkle, prouver une valeur oblige à fournir tous les nœuds frères rencontrés sur le chemin de la feuille vers la racine. Le vérificateur a besoin de l’ensemble complet des enfants d’un nœud pour recalculer sa valeur, et il doit répéter l’opération à chaque étage. Élargir l’arbre aggrave le problème au lieu de le résoudre.
C’est la raison pour laquelle un arbre de Patricia est le plus efficace avec une largeur de 2, et pourquoi la structure de données historique d’Ethereum, hexadécimale, est en réalité assez peu optimale. Dans un arbre de Verkle, le coût des nœuds frères disparaît, si bien que la largeur devient un levier et non un handicap.
D’où vient l’idée d’arbre de Verkle
L’idée n’est pas née chez Ethereum. Les arbres de Verkle ont été introduits par John Kuszmaul dans un article publié en 2018, et ils sont restés longtemps moins connus que d’autres constructions cryptographiques de la même période. Leur reprise dans un projet d’EIP les fait sortir de l’ombre quatre ans après leur formalisation.
Le nom dit la filiation, puisqu’il combine l’engagement vectoriel et l’arbre de Merkle. La contrepartie de la brièveté des preuves est d’ailleurs assumée par ses promoteurs, qui reconnaissent une dépendance accrue à une cryptographie plus compliquée, tout en la jugeant plus abordable que celle des schémas de SNARK modernes. Le compromis se joue entre taille de preuve et complexité du code, pas entre sécurité et performance.
Pourquoi Ethereum a-t-il besoin de preuves plus courtes ?
Parce que la taille du témoin décide de qui peut valider le réseau. Sur un arbre contenant un milliard d’éléments, une preuve de Merkle binaire réclame environ un kilooctet, contre moins de 150 octets pour un arbre de Verkle. Cette division par sept ouvre la voie aux clients sans état, comme l’écrivait Vitalik Buterin dès juin 2021.
Le témoin, ce fichier qui pèse trop lourd
Un témoin est le paquet de données qui accompagne un bloc pour permettre à un nœud de vérifier les changements d’état sans détenir l’état complet. Sa taille est la variable qui commande tout le reste : un témoin de plusieurs mégaoctets par bloc rend l’exercice impraticable sur une connexion domestique.
Ethereum accumule aujourd’hui des centaines de gigaoctets d’état, et cette masse croît sans discontinuer. Le réseau se trouve devant le même arbitrage que celui décrit dans le compromis entre décentralisation et débit, sauf qu’il porte ici sur le stockage plutôt que sur le calcul. Réduire le témoin déplace la contrainte sans sacrifier la vérifiabilité.
Les clients sans état, une promesse restée théorique
Un client sans état vérifie les blocs sans conserver l’état, en s’appuyant uniquement sur le témoin livré avec chaque bloc. L’idée circule dans la recherche Ethereum depuis plusieurs années et butait sur un obstacle unique et têtu : le témoin coûtait plus cher à transmettre que l’état à stocker.
Passer sous la barre des 150 octets par élément prouvé renverse ce calcul. Un nœud qui n’exige plus des centaines de gigaoctets de disque devient installable sur du matériel ordinaire, ce qui élargit mécaniquement le nombre de vérificateurs indépendants. La décentralisation se mesure au nombre de machines capables de dire non, et cette population dépend du ticket d’entrée matériel.
Ce que pèse concrètement une preuve de Verkle
Les tailles calculées par Vitalik Buterin en juin 2021, pour une largeur de 256 et des engagements KZG de 48 octets, donnent une idée précise du terrain de jeu. Le tableau croise la taille de l’arbre et le nombre de couples clé-valeur prouvés simultanément :
| Taille de l’arbre | 1 valeur | 10 valeurs | 1 000 valeurs | 10 000 valeurs |
|---|---|---|---|---|
| 256 nœuds | 176 octets | 176 octets | 176 octets | 176 octets |
| 65 536 nœuds | 224 octets | 608 octets | 12 176 octets | 12 464 octets |
| 16,7 millions | 272 octets | 1 040 octets | 59 792 octets | 457 616 octets |
| 4,3 milliards | 320 octets | 1 472 octets | 107 744 octets | 937 472 octets |
La colonne la plus instructive est la première. Prouver une valeur unique dans un arbre de 4,3 milliards de nœuds coûte 320 octets, soit le poids d’un SMS un peu long. Sur un arbre réaliste, non parfaitement équilibré, il faut ajouter une profondeur d’environ 0,6, ce qui représente une trentaine d’octets par élément.
Un choix technique fait encore varier la facture. Avec des engagements de type bulletproof plutôt que KZG, chaque élément descend à 32 octets et les tailles annoncées reculent d’un tiers, au prix d’une vérification plus coûteuse. Les mêmes primitives sous-tendent les transactions confidentielles bâties sur ces preuves.
Quelles ruptures l’EIP introduit-il dans la structure de l’arbre ?
Trois changements structurants, énoncés dès l’ouverture du billet de la Fondation Ethereum du 2 décembre 2021. Ils touchent la taille des clés, la séparation historique entre comptes et stockage, et la nature même des empreintes. Aucun des trois ne se limite à une optimisation : chacun modifie le contrat passé avec les développeurs de clients.
Voici ce que le projet d’EIP met sur la table, dans l’ordre où ses auteurs le présentent :
- le passage de clés de 20 octets à des clés de 32 octets, à ne pas confondre avec le passage à des adresses de 32 octets, qui est un chantier distinct ;
- la fusion de l’arbre des comptes et de l’arbre de stockage, jusqu’ici tenus séparément ;
- l’introduction du verkle trie lui-même, qui substitue des engagements vectoriels aux hachages.
La fusion des deux arbres est celle qui bouleverse le plus les implémentations existantes. Elle supprime la frontière entre l’identité d’un compte et les données de son contrat, ce qui rapproche physiquement des informations souvent lues ensemble.
Une clé en deux morceaux, tige et suffixe
L’un des objectifs de conception consiste à rendre peu coûteux l’accès aux positions voisines, par exemple deux emplacements de stockage aux adresses presque identiques ou deux fragments de code contigus. Le mécanisme repose sur un découpage : une tige de 31 octets et un suffixe d’un octet, pour un total de 32.
Le schéma de clés est pensé pour que des emplacements proches partagent la même tige et ne diffèrent que par le suffixe. Lire dix cases de stockage consécutives ne coûte alors presque pas plus cher qu’en lire une, puisqu’elles vivent sous le même engagement.
Nœuds d’extension et nœuds internes
L’arbre se compose de deux types de nœuds seulement. Les nœuds d’extension représentent 256 valeurs qui partagent la même tige et se distinguent par leur suffixe. Les nœuds internes possèdent jusqu’à 256 enfants, qui sont soit d’autres nœuds internes, soit des nœuds d’extension.
L’engagement d’un nœud interne se calcule simplement : le nœud est vu comme un vecteur de 256 valeurs, chacune étant la représentation en élément de champ de l’engagement racine du sous-arbre correspondant. Un sous-arbre vide vaut zéro, ce qui évite d’avoir à distinguer les branches inoccupées.
Que vient faire la courbe Bandersnatch dans l’affaire ?
Elle fournit le terrain mathématique des engagements. Bandersnatch a été retenue pour deux raisons explicites : ses performances, et sa compatibilité avec des SNARK efficaces dans BLS12_381. Son ordre de courbe est un nombre premier de 253 bits, contrainte dont découle une bonne partie de l’agencement décrit par l’EIP.
Un champ scalaire de 253 bits, et ses conséquences
L’ordre de la courbe vaut exactement 13 108 968 793 781 547 619 861 935 127 046 491 459 309 155 893 440 570 251 786 403 306 729 687 672 801. Ce nombre premier de 253 bits impose une limite sèche : on ne peut s’engager sûrement que sur 252 bits, faute de quoi le champ déborde.
De cette limite découle la largeur de 256 retenue pour l’arbre. Chaque engagement porte jusqu’à 256 valeurs de 252 bits chacune, ce que les auteurs notent sous la forme d’un engagement sur une liste de longueur 256. Le plafond de 252 bits explique aussi le découpage des valeurs décrit plus loin.
Le pari des SNARK
La compatibilité avec BLS12_381 n’a rien d’anecdotique. Elle laisse ouverte la possibilité de raisonner un jour sur l’arbre de Verkle à l’intérieur d’un SNARK, ce qui servirait aux cumuls et permettrait de compresser tous les témoins dans une seule preuve sans changer à nouveau de schéma d’engagement.
Cette option compte pour les réseaux de seconde couche, dont l’économie dépend directement du coût de publication des preuves sur la couche de base. Un arbre conçu dès l’origine pour être digéré par un SNARK vaut mieux qu’un arbre qu’il faudra remplacer quand la technologie mûrira.
Cela permet de réduire la taille des preuves d’un facteur 6 à 8 par rapport à des arbres de Merkle idéaux, et d’un facteur supérieur à 20 ou 30 par rapport aux arbres de Patricia hexadécimaux qu’Ethereum utilise aujourd’hui.
Vitalik Buterin, billet « Verkle trees » publié sur son site personnel le 18 juin 2021
Comment les valeurs sont-elles rangées dans les feuilles ?
Par un découpage en deux moitiés. Une valeur fait 256 bits, un élément de champ n’en accepte que 252 : quatre bits seraient perdus à chaque case. Les auteurs ont donc partitionné le groupe de 256 valeurs en deux groupes de 128, chaque valeur de 32 octets étant coupée en deux tranches de 16.
Deux engagements pour 256 valeurs
Un seul engagement ne suffirait pas à couvrir 256 valeurs de 32 octets. Le nœud d’extension s’appuie donc sur deux engagements supplémentaires : C₁ couvre les suffixes 0 à 127, C₂ les suffixes 128 à 255. L’ensemble formé par l’extension et ces deux engagements porte le nom d’arbre d’extension et de suffixe.
L’engagement du nœud d’extension lui-même porte sur un vecteur de quatre éléments seulement, les positions restantes valant zéro. On y trouve un marqueur d’extension, qui n’est rien d’autre que le nombre 1, les deux engagements de sous-arbre, et la tige de la clé menant à ce nœud. La tige couvre toute la clé jusqu’à ce point, contrairement aux nœuds d’extension d’un arbre de Merkle-Patricia.
Ce détail sert directement les preuves sans état. Quand une nouvelle clé vient scinder une extension en deux, l’ancien voisin n’a pas besoin d’être mis à jour, ce qui produit une preuve plus petite et évite une cascade de réécritures.
Le marqueur de feuille et l’expiration d’état
Un marqueur de feuille est ajouté à la moitié basse de chaque valeur, positionné au 129e bit. Sa fonction est de distinguer une feuille jamais consultée d’une feuille écrasée par des zéros, distinction qui n’a rien de théorique : aucune valeur n’est jamais supprimée d’un arbre de Verkle.
Cette permanence est réclamée par les futurs schémas d’expiration d’état, qui visent à décharger les nœuds des données dormantes sans les rendre irrécupérables. Elle s’inscrit dans la même famille de réponses que le découpage du réseau en fragments, avec une cible différente : le poids de l’état plutôt que le débit de transactions.
Insérer une valeur quand deux tiges se ressemblent
L’insertion devient intéressante au moment où deux tiges partagent leurs premiers octets. Le billet de la Fondation Ethereum illustre le cas avec un arbre ne contenant qu’une valeur, placée à l’emplacement composé uniquement de zéros, dans lequel on insère une seconde valeur dont la tige ne diffère qu’à partir du troisième octet.
Le mécanisme ajoute alors deux nœuds internes, un par octet identique restant, jusqu’à atteindre l’octet qui distingue les deux tiges. Un nouvel arbre d’extension et de suffixe est inséré à cet endroit, doté d’une tige complète de 31 octets. Le nœud initial reste intact, et l’engagement de son sous-arbre conserve exactement la valeur qu’il avait avant l’opération.
Le coût de mise à jour reste modeste, et c’est le second gain silencieux de la structure. Modifier une valeur demande de remonter du nœud feuille vers la racine en ajustant chaque engagement intermédiaire, opération que la propriété homomorphe des engagements polynomiaux ramène à quatre multiplications sur courbe elliptique environ. Aucun engagement n’a besoin d’être recalculé depuis zéro, ce qui rend l’écriture aussi économique que la lecture.
Cette propriété explique pourquoi les arbres de Verkle produisent des arbres moins profonds tout en réduisant la quantité de données stockées. La puissance réelle vient toutefois d’ailleurs, de la capacité à produire des témoins plus courts, que les auteurs annonçaient traiter dans un billet suivant.
Ce que les arbres de Verkle engagent pour la suite d’Ethereum
Le chantier n’est pas isolé. Il occupe une ligne précise dans les chantiers annoncés après la fusion, aux côtés de l’expiration d’état et de la compression des données, et il conditionne plusieurs d’entre eux. Une preuve courte est le préalable à un réseau que l’on peut vérifier depuis un téléphone, objectif que la trajectoire dessinée par ses développeurs assume ouvertement.
Un point mérite d’être gardé en tête par qui regarde loin. Les engagements de Pedersen reposent sur des homomorphismes linéaires que l’informatique quantique rendrait un jour vulnérables, ce que Vitalik Buterin écrivait lui-même en juin 2021 en évoquant un basculement futur vers des preuves de Merkle enveloppées dans des STARK. Les arbres de Verkle sont une étape, pas un terminus.
Reste la question qui décidera du calendrier réel. Un changement de cette ampleur touche chaque implémentation de client, chaque outil d’indexation, chaque service qui lit l’état d’Ethereum, et la coordination pèsera plus lourd que la cryptographie. Le rythme auquel les équipes de développement absorberont cette migration dira mieux que n’importe quelle annonce ce que le réseau est capable d’encaisser.
