Un arbre de Merkle, également appelé arbre de hachage, est une structure de données hiérarchique où chaque feuille contient le hachage cryptographique d'un bloc de données, et chaque nœud parent contient le hachage cryptographique de la concaténation des hachages de ses nœuds enfants. Cette structure arborescente binaire permet de vérifier l'intégrité et la cohérence de grands ensembles de données avec une efficacité remarquable : au lieu de contrôler chaque donnée individuellement, le vérificateur n'a besoin d'examiner qu'un petit nombre de hachages le long d'une branche, d'une feuille à la racine. Le hachage unique situé au sommet de l'arbre, appelé racine de Merkle, constitue une empreinte numérique unique pour l'ensemble des données qu'elle contient. Si un seul bit de données est altéré dans l'arbre, la modification se propage à travers tous les hachages parents jusqu'à ce que la racine de Merkle elle-même soit modifiée, signalant instantanément une falsification des données.
Dans la technologie blockchain, les arbres de Merkle sont fondamentaux pour le stockage et la validation des transactions par les blocs. Chaque en-tête de bloc dans Bitcoin, Ethereum et la quasi-totalité des autres protocoles blockchain contient une racine de Merkle qui récapitule toutes les transactions incluses dans ce bloc. Cette conception permet aux clients légers – souvent appelés nœuds SPV (Simplified Payment Verification) – de confirmer la présence d'une transaction spécifique dans un bloc sans télécharger l'intégralité de son contenu. Le client n'a besoin que de l'en-tête du bloc (qui contient la racine de Merkle) et d'une courte séquence de hachages de transactions sœurs, appelée preuve de Merkle ou chemin de Merkle. Pour un bloc contenant 4 096 transactions, cette preuve ne requiert que 12 hachages au lieu des 4 096 hachages de transactions – une réduction logarithmique qui rend les portefeuilles mobiles et les appareils aux ressources limitées compatibles avec le réseau.
Au-delà de la simple inclusion de transactions, les arbres de Merkle sous-tendent certaines des constructions les plus avancées de l'écosystème des cryptomonnaies. Ethereum utilise une version modifiée, appelée Merkle Patricia Trie, pour stocker l'intégralité de son état global : le solde de chaque compte, chaque emplacement de stockage de contrat intelligent et chaque portion de code. Les rollups à divulgation nulle de connaissance utilisent les arbres de Merkle pour intégrer des lots de transactions hors chaîne dans une seule racine sur la chaîne. Les contrats de distribution d'airdrops utilisent les arbres de Merkle pour permettre à des milliers d'adresses de réclamer des jetons avec un minimum de données sur la chaîne. L'élégance de cette structure réside dans sa simplicité : une application récursive du hachage qui convertit un ensemble de données arbitrairement volumineux en un seul engagement de taille fixe, vérifiable en temps logarithmique.
Origine & Histoire
1979 : Ralph Merkle décrit pour la première fois les arbres de hachage dans sa thèse de doctorat à Stanford et dépose ensuite un brevet pour ce concept (brevet américain n° 4 309 569, déposé le 5 septembre 1979 et accordé le 5 janvier 1982). Merkle développe cette structure dans le cadre de ses travaux pionniers sur la cryptographie à clé publique et les signatures numériques, cherchant une méthode efficace pour authentifier les grandes structures de données.
1987–1988 : Merkle a combiné sa structure d’arbre de hachage avec des schémas de signature à usage unique, s’appuyant sur la construction antérieure de signature à usage unique de Lamport-Diffie, dans un article présenté à CRYPTO '87 et publié dans les actes de la conférence en 1988. Cette combinaison, désormais généralement connue sous le nom de schéma de signature Merkle, a démontré qu’un seul arbre de hachage pouvait authentifier de nombreuses paires de clés à usage unique sous une seule clé publique, gérant efficacement un grand nombre de clés cryptographiques.
Fin des années 1990 : Avec l’émergence des systèmes de partage de fichiers poste à poste, les structures d’arbres de hachage ont été utilisées pour permettre aux nœuds de vérifier indépendamment l’intégrité des segments de fichiers téléchargés, détectant ainsi les données corrompues ou malveillantes sans avoir à retélécharger les fichiers entiers. Ce modèle a ensuite été formalisé dans des spécifications telles que le format THEX (Tree Hash Exchange).
2008 : Satoshi Nakamoto a intégré les arbres de Merkle à la conception du protocole Bitcoin. La section 7 du livre blanc de Bitcoin, « Récupération d’espace disque », décrit comment les arbres de Merkle permettent d’éliminer les données de transactions anciennes tout en conservant un hachage racine compact. La section 8, « Vérification simplifiée des paiements », explique séparément comment cette même structure permet aux clients légers de confirmer qu’une transaction est incluse dans un bloc en utilisant uniquement l’en-tête du bloc et une preuve Merkle.
2009 : Le réseau Bitcoin a été lancé avec des racines Merkle intégrées dans l’en-tête de chaque bloc. Le bloc de genèse (bloc 0) contenait une seule transaction dont la racine Merkle était égale au hachage de cette transaction, établissant ainsi le modèle pour tous les blocs suivants.
2015 : Ethereum a été lancé avec trois variantes distinctes d’arbres de Merkle dans l’en-tête de chaque bloc : un arbre de transactions, un arbre de reçus et un arbre d’état, tous implémentés sous forme d’arbres Patricia de Merkle. Cette conception a étendu les fonctionnalités des arbres de Merkle, passant d’une simple vérification des transactions à une authentification complète de l’état du système.
2017-2019 : Les arbres de Merkle sont devenus essentiels à la conception des solutions de mise à l’échelle de couche 2. Les chaînes Plasma utilisaient les engagements Merkle pour ancrer l’état des chaînes enfants au réseau principal Ethereum, tandis que les premières architectures de rollup utilisaient les racines Merkle pour regrouper des centaines de transactions en une seule preuve sur la chaîne.
2020-2024 : Les systèmes de preuve à divulgation nulle de connaissance, tels que zkSync et StarkNet, ont adopté des variantes spécialisées d’arbres de Merkle – notamment des arbres de Merkle clairsemés basés sur le hachage Poséidon – optimisées pour un calcul efficace au sein des circuits ZK. Les contrats de distribution de jetons par airdrop basés sur Merkle sont devenus le modèle standard pour la distribution de jetons sur Ethereum.
« Un arbre de hachage permet de vérifier indépendamment n'importe quelle branche de l'arbre, sans que les nœuds aient besoin de stocker l'ensemble des données. »
En termes simples
Imaginez un tableau de tournoi sportif. Chaque match du premier tour désigne un vainqueur. Ces vainqueurs s'affrontent ensuite au deuxième tour, et ainsi de suite, jusqu'à ce qu'il ne reste qu'un seul champion. Un arbre de Merkle fonctionne de la même manière, sauf qu'au lieu d'équipes sportives, on part de blocs de données, et au lieu de jouer des matchs, on combine des paires de données à l'aide d'un hachage cryptographique jusqu'à obtenir un hachage unique, appelé « racine de Merkle », qui représente le champion.
Imaginez un arbre généalogique inversé. À la base, des centaines de membres de la famille (des blocs de données). Chaque paire de frères et sœurs est associée à leurs parents. Ces parents forment les grands-parents, et ainsi de suite, jusqu'à un ancêtre unique tout en haut. Si un membre de la famille change, toutes les générations précédentes changent également, et ainsi de suite jusqu'à l'ancêtre tout en haut.
Imaginez le système de catalogue d'une bibliothèque. Au lieu de vérifier chaque livre sur chaque rayon pour s'assurer qu'il n'en manque aucun, le bibliothécaire conserve un résumé de chaque rayon, regroupe ces résumés par allée, puis par étage, et enfin un résumé principal pour toute la bibliothèque. Pour vérifier la présence d'un livre, il suffit de consulter les résumés qui jalonnent son parcours, de l'étagère au résumé principal ; inutile de vérifier chaque livre individuellement.
Imaginez la mise sous scellés des preuves dans un procès. Chaque élément de preuve reçoit sa propre enveloppe inviolable. Les enveloppes sont placées deux à deux dans des enveloppes plus grandes, elles-mêmes insérées dans des enveloppes encore plus grandes, jusqu'à ce que tout soit contenu dans une enveloppe principale scellée. Si quelqu'un altère un élément de preuve, toutes les enveloppes situées au-dessus présentent des signes d'altération, et le scellé de l'enveloppe principale se brise.
Important : Les arbres de Merkle attestent de l’inclusion et de l’intégrité des données, mais ne les chiffrent pas et n’assurent pas leur confidentialité. Toute personne ayant accès à l’arbre peut consulter les données ; l’arbre garantit uniquement que les données n’ont pas été altérées. De plus, la sécurité d’un arbre de Merkle repose entièrement sur la robustesse de la fonction de hachage sous-jacente ; si cette fonction est compromise, les garanties d’intégrité de l’arbre s’effondrent.
Caractéristiques techniques clés
Structure d'arbre de hachage binaire
Les nœuds feuilles contiennent le hachage des blocs de données individuels (par exemple, les transactions).
Les nœuds internes contiennent le hachage de la concaténation de leurs deux hachages enfants : H(parent) = Hash(H(left) || H(right))
L'arbre est toujours équilibré ; si le nombre de feuilles est impair, la dernière feuille est dupliquée pour former une paire.
La profondeur de l'arbre est log2(n) où n est le nombre de nœuds feuilles
Le hachage racine (racine de Merkle) est une empreinte digitale de taille fixe de l'ensemble des données, quelle que soit la taille de cet ensemble.
Comment fonctionne la vérification par preuve de Merkle
Un vérificateur souhaite confirmer qu'une transaction spécifique Tx_k est inclus dans un bloc
Le vérificateur obtient l'en-tête du bloc, qui contient la racine Merkle
Le prouveur fournit le hachage de Tx_k ainsi que sa preuve Merkle – la séquence de hachages frères le long du chemin de la feuille à la racine
Le vérificateur hache Tx_k, puis le combine avec le hachage du premier élément frère en utilisant la même fonction de hachage
Le résultat est combiné avec le hachage du frère suivant, et ainsi de suite, en remontant l'arbre niveau par niveau.
Si le hachage final calculé correspond à la racine Merkle dans l'en-tête du bloc, la transaction est vérifiée comme incluse.
Pour un arbre avec n feuilles, seulement log2(n) Des hachages sont nécessaires – par exemple, 20 hachages pour vérifier 1 transaction parmi 1 048 576
Merkle Patricia Trie (Ethereum)
Ethereum étend l'arbre de Merkle de base en un trie Patricia (arbre radix) qui associe des clés à des valeurs.
L'arbre d'état associe les adresses des comptes aux états des comptes (solde, nonce, racine de stockage, hachage du code).
L'arbre de stockage associe des emplacements de stockage de 256 bits à leurs valeurs pour chaque contrat intelligent.
La compression des chemins réduit la surcharge de stockage en regroupant les chaînes à enfant unique en nœuds d'extension.
Trois types de nœuds : nœuds de branche (16 enfants + valeur), nœuds d’extension (préfixe partagé + nœud suivant), nœuds feuilles (chemin restant + valeur)
Arbres de Merkle clairsemés pour les preuves à divulgation nulle de connaissance
Les arbres de Merkle clairsemés (SMT) sont des arbres de Merkle dont la plupart des feuilles sont vides (valeur de hachage par défaut).
Utilisé dans les ZK-rollups pour représenter les états de compte avec des preuves d'appartenance et de non-appartenance efficaces.
Des fonctions de hachage optimisées comme Poseidon et Pedersen sont utilisées pour les calculs compatibles avec les circuits ZK.
Un SMT de profondeur 256 peut représenter toutes les clés possibles de 256 bits tout en restant calculable
La preuve de non-inclusion est aussi simple que de prouver que la feuille à une position donnée contient la valeur par défaut
Avantages désavantages
Avantages
Désavantages
Vérification logarithmique : taille de la preuve et échelle de temps de vérification O(log n), permettant une vérification efficace même pour des millions de transactions
Surcharge de stockage : Le stockage de tous les hachages intermédiaires nécessite environ 2n - 1 nœuds pour n nœuds feuilles, doublant approximativement les besoins en stockage de données brutes
Détection de falsification : Toute modification apportée à un nœud feuille se propage vers le haut, modifiant la racine Merkle et révélant immédiatement toute corruption ou manipulation de données.
Coût de recalcul : La mise à jour d’une seule feuille nécessite le recalcul de tous les hachages le long du chemin vers la racine. O(log n) opérations de hachage par mise à jour
Prise en charge client légère : les nœuds SPV peuvent vérifier l’inclusion des transactions avec uniquement les en-têtes de blocs et les preuves Merkle, ce qui permet l’utilisation de portefeuilles mobiles et embarqués.
Dépendance à la fonction de hachage : L’ensemble du modèle de sécurité repose sur la résistance aux collisions de la fonction de hachage choisie ; une fonction de hachage défaillante compromet l’arbre.
Efficacité de la bande passante : les preuves de Merkle ne transmettent que log2(n) Des hachages au lieu de l'ensemble des données, ce qui réduit considérablement la bande passante réseau nécessaire à la vérification.
Exigence d'équilibrage : les arbres de Merkle binaires standard nécessitent un nombre pair de feuilles ; les ensembles de données comportant un nombre impair de feuilles nécessitent une duplication, ce qui peut introduire des bogues d'implémentation subtils.
Composabilité : les arbres de Merkle peuvent être imbriqués – une racine de Merkle peut être une feuille d’un arbre de niveau supérieur – permettant des schémas d’engagement de données multicouches utilisés dans les agrégations et le partitionnement.
Complexité des tries : Les tries Merkle Patricia (comme dans Ethereum) sont nettement plus complexes à implémenter que les arbres Merkle binaires de base, avec de multiples types de nœuds et un encodage des chemins.
Construction parallèle : les hachages des feuilles peuvent être calculés indépendamment et en parallèle, ce qui rend la construction d’arbres de Merkle hautement parallélisable sur les matériels modernes.
Surcharge d'état : Dans les blockchains à état, l'arbre de Merkle s'agrandit à chaque nouveau compte et emplacement de stockage, contribuant à une surcharge d'état à long terme et à l'allongement des temps de synchronisation.
Standardisée et éprouvée en conditions réelles : des décennies de recherche universitaire et de déploiement en production (Bitcoin depuis 2009) garantissent une grande fiabilité de sa structure.
Évolution de la taille des preuves : Bien que logarithmique, la taille des preuves augmente avec la taille de l’ensemble de données ; pour les très grands arbres (milliards de feuilles), la taille des preuves peut devenir non triviale.
Gestion du risque
Risque de vulnérabilité des fonctions de hachage
Les arbres de Merkle héritent des propriétés de sécurité de leur fonction de hachage sous-jacente (généralement SHA-256 pour Bitcoin, Keccak-256 pour Ethereum).
Si les attaques par collision deviennent réalisables contre la fonction de hachage, un attaquant pourrait construire deux ensembles de données différents avec la même racine de Merkle.
Mesures d'atténuation : surveiller les recherches cryptographiques afin de détecter les avancées concernant SHA-256 et Keccak-256 ; les communautés blockchain peuvent procéder à un hard fork pour mettre à jour les fonctions de hachage si nécessaire.
L'informatique quantique représente une menace à long terme pour la sécurité des fonctions de hachage, bien que les estimations actuelles suggèrent que SHA-256 reste sûr pendant des décennies.
Risque de bug d'implémentation
Des erreurs subtiles dans les implémentations d'arbres de Merkle – telles qu'une gestion incorrecte des feuilles impaires, des erreurs de décalage d'une unité dans les chemins de preuve ou des incohérences d'endianness – peuvent créer des vulnérabilités exploitables.
La scission de Bitcoin Cash en 2018 a mis en évidence des cas limites dans la validation des arbres de Merkle lors de la vérification des blocs.
Mesures d'atténuation : utiliser des bibliothèques open source bien auditées (par exemple, MerkleProof.sol d'OpenZeppelin pour Solidity) ; effectuer une vérification formelle des implémentations critiques.
Effectuer des tests avec des entrées adverses, notamment des arbres vides, des arbres à une seule feuille et des arbres de profondeur maximale.
Risque d'attaque par ambiguïté de type
Dans un arbre de Merkle naïf, un attaquant pourrait potentiellement créer un nœud interne frauduleux qui entre en collision avec un nœud feuille légitime.
Ce type d'attaque est plus précisément connu sous le nom d'attaque par ambiguïté de type ou d'attaque inter-nœuds, et peut être atténué en ajoutant un séparateur de domaine (0x00 pour les feuilles, 0x01 pour les nœuds internes) avant le hachage.
L'implémentation de l'arbre de Merkle de Bitcoin utilise un hachage double SHA-256, ce qui offre une résistance supplémentaire.
Mesure d'atténuation : Toujours différencier le hachage des feuilles et celui des nœuds internes ; suivre les normes établies telles que la RFC 6962 (Transparence des certificats).
Risque de croissance et de performance de l'État
Dans Ethereum, l'arbre d'état s'agrandit à chaque nouveau compte et emplacement de stockage de contrat, augmentant ainsi le coût de la génération et de la vérification des preuves au fil du temps.
Les temps de synchronisation complète des nœuds sont fortement influencés par la taille du trie d'état (des centaines de gigaoctets).
Mesures d'atténuation : Les propositions d'expiration d'état (EIP-4444, arbres de Verkle) visent à élaguer l'état historique ; la recherche sur les clients sans état se concentre sur la fourniture de preuves d'état avec chaque bloc
Pertinence culturelle
Les arbres de Merkle occupent une place unique dans la culture crypto, étant l'une des rares structures de données à avoir acquis une notoriété en dehors des cercles d'informaticiens. L'expression « preuve de Merkle » est couramment employée sur les serveurs Discord, les fils Twitter et les forums de gouvernance, souvent par des participants qui ne maîtrisent pas forcément les mathématiques sous-jacentes, mais qui en reconnaissent l'importance.
« Les arbres de Merkle sont les héros méconnus de la blockchain. Chaque fois que vous vérifiez une transaction, remerciez Ralph Merkle. »
Le concept a acquis une importance considérable dans la culture crypto lors de la faillite de FTX en 2022, lorsque l'expression « preuve de réserves » est entrée dans le débat public. Des plateformes d'échange comme Binance et Kraken ont mis en place des systèmes de preuve de réserves basés sur l'arbre de Merkle, permettant aux utilisateurs de vérifier indépendamment que leurs fonds figuraient bien dans les avoirs déclarés de la plateforme. L'expression « preuve de réserves par arbre de Merkle » est devenue un gage de confiance après la faillite de FTX, illustrant comment une invention informatique de 1979 est devenue une référence culturelle en matière de transparence financière.
Dans les communautés NFT et airdrop, l'expression « airdrop Merkle » est devenue courante. Des projets comme Uniswap, ENS et Optimism utilisaient des contrats de distribution basés sur l'arbre Merkle, permettant aux adresses éligibles de réclamer des tokens en fournissant une preuve Merkle de leur présence dans la liste de distribution. Ce modèle, popularisé par la bibliothèque OpenZeppelin, a été repris par des centaines de projets et constitue désormais la norme de facto pour la distribution de tokens sur la blockchain.
La communauté des développeurs débat régulièrement des mérites des arbres de Merkle par rapport à des alternatives plus récentes comme les arbres de Verkle (proposés dans la feuille de route d'Ethereum concernant l'absence d'état), ce qui témoigne de l'importance de cette structure dans les discussions sur l'architecture de la blockchain.
Exemples du monde réel
Vérification du portefeuille Bitcoin SPV
Scénario : Un utilisateur disposant d’un portefeuille Bitcoin mobile sur un smartphone à capacité de stockage limitée souhaite vérifier la légitimité d’un paiement de 0.5 BTC reçu sans télécharger l’intégralité de la blockchain de plus de 500 Go.
Mise en œuvre : Le portefeuille SPV télécharge uniquement les en-têtes de blocs (80 octets chacun, soit environ 60 Mo pour l’historique complet de la blockchain). Lorsqu’un utilisateur reçoit un paiement, le portefeuille demande une preuve Merkle à un nœud complet : un ensemble de 10 à 12 hachages de blocs frères qui retracent le chemin de la transaction jusqu’à la racine Merkle dans l’en-tête du bloc.
Résultat : Le portefeuille vérifie l’inclusion de la transaction dans le bloc en recalculant les hachages jusqu’à la racine Merkle, confirmant ainsi la légitimité du paiement. Cette opération prend quelques millisecondes et utilise quelques kilo-octets de données, rendant Bitcoin utilisable sur des appareils mobiles aux ressources limitées. C’est précisément le cas d’utilisation décrit par Satoshi dans la section 8 du livre blanc de Bitcoin.
Distribution gratuite de jetons UNI sur Uniswap (2020)
Scénario : Uniswap devait distribuer 150 millions de jetons UNI à environ 250 000 utilisateurs historiques. Stocker les adresses de ces 250 000 utilisateurs sur la blockchain engendrerait des frais de gaz se chiffrant en millions de dollars.
Mise en œuvre : Les ingénieurs d’Uniswap ont construit un arbre de Merkle dont les nœuds terminaux étaient les adresses éligibles et le montant correspondant. Seule la racine de l’arbre (32 octets) était stockée sur la blockchain dans le contrat de distribution. Chaque utilisateur pouvait réclamer ses jetons en soumettant une preuve de Merkle (environ 18 hachages pour 250 000 adresses) attestant de son inclusion dans l’arbre.
Résultat : Le contrat de distribution gratuite a nécessité un stockage minimal sur la blockchain tout en permettant à tout utilisateur éligible de réclamer des jetons sans autorisation. Le coût en gaz par réclamation était d'environ 80 000 à 100 000 unités, contre des millions de dollars pour le préchargement de toutes les adresses sur la blockchain. Ce modèle est depuis devenu la norme du secteur pour la distribution de jetons.
Preuve de réserves de Binance (après FTX, 2022)
Scénario : Après la faillite de FTX, Binance a dû faire face à une pression urgente pour prouver que les fonds de ses clients étaient intégralement couverts. La plateforme détenait des actifs pour un très grand nombre de comptes utilisateurs, rendant la divulgation au niveau de chaque compte impossible et portant atteinte à la vie privée.
Mise en œuvre : Binance a implémenté un système de preuve de réserves basé sur l’arbre de Merkle, où le solde de chaque compte utilisateur était haché et représenté par un nœud terminal. Les utilisateurs pouvaient vérifier l’inclusion de leur compte en se connectant et en demandant leur preuve Merkle personnelle, qu’ils pouvaient ensuite comparer indépendamment à la racine Merkle publiée. Des auditeurs tiers vérifiaient que le total des réserves correspondait à l’engagement de la racine Merkle.
Résultat : Les utilisateurs ont pu vérifier l’inclusion de leur compte dans l’arbre de réserves, rétablissant ainsi une certaine confiance dans les plateformes d’échange centralisées. Bien que cette approche ne soit pas parfaite (elle ne prouve pas l’absence de passif), elle a permis d’établir la transparence basée sur l’arbre de Merkle comme une norme largement adoptée pour la responsabilité des plateformes d’échange.
Vérification d'état Ethereum pour les protocoles DeFi
Scénario : Un protocole de prêt DeFi sur Ethereum doit vérifier le solde actuel des garanties d'un compte utilisateur sur un rollup de couche 2 avant de traiter une liquidation.
Mise en œuvre : Le rollup publie sa racine d'état (une racine Merkle de tous les soldes des comptes) sur le réseau principal Ethereum. Le contrat de liquidation sur Ethereum accepte une preuve Merkle démontrant le solde de garantie de l'utilisateur au sein de l'arbre d'état du rollup. Cette preuve contient environ 20 à 30 hachages pour un arbre Merkle clairsemé représentant un très grand nombre de comptes possibles.
Résultat : La liquidation inter-couches s’effectue sans tiers de confiance ; aucun oracle ni relais de sécurité n’est requis. La preuve Merkle lie cryptographiquement l’état du rollup au contrat du réseau principal, permettant ainsi la composabilité entre les couches 1 et 2 sans compromettre la sécurité. Ce modèle général est utilisé dans de nombreuses architectures de rollup et de prêts inter-chaînes.
Tableau de comparaison
Fonctionnalité
Arbre de Merkle (binaire)
Merkle Patricia Trie (Ethereum)
Arbre Verkle (Proposé)
Structure
Arbre binaire des hachages
trie Radix avec engagements de hachage
Arbre avec engagements vectoriels
Taille de l'épreuve
O(log n) hachages (~32 octets chacun)
O(log n) mais plus grand en raison du facteur de ramification 16
O(log n) mais plus petites que les épreuves Merkle
Utilisation principale
Inclusion des transactions (Bitcoin)
Stockage complet de l'état mondial (Ethereum)
Vérification du client sans état (futur Ethereum)
Cartographie des clés
Positionnel (basé sur l'index)
Clé-valeur (adresse-état)
Clé-valeur (adresse-état)
Coût de mise à jour
O(log n) ressasser
O(log n) mais avec les frais supplémentaires liés à la restructuration du trie
O(log n) avec des engagements moins chers
Vérification de la preuve
Recalcul simple du hachage
Plus complexe (plusieurs types de nœuds)
Nécessite des opérations sur les courbes elliptiques
État gonflé
Minimal (les listes de transactions sont limitées)
Grave (l'état se développe de manière illimitée)
Atténué par des tailles d'épreuve plus petites
Résistance quantique
Basé sur le hachage (relativement sûr face à l'informatique quantique)
Basé sur le hachage (relativement sûr face à l'informatique quantique)
Repose sur des courbes elliptiques (vulnérables aux attaques quantiques)
Maturité
Déployé depuis 2009 (Bitcoin)
Déployé depuis 2015 (Ethereum)
Phase de recherche/déploiement (EIP-6800)
Termes connexes
Fonction de hachage – Une fonction mathématique qui convertit les données d'entrée en une sortie de taille fixe, servant d'élément de base à chaque nœud d'un arbre de Merkle.
Vérification simplifiée des paiements (SPV) – Une méthode de vérification des transactions Bitcoin utilisant uniquement les en-têtes de blocs et les preuves Merkle, permettant des clients légers qui reposent entièrement sur l'efficacité de l'arbre Merkle.
Racine Merkle – Le hachage unique situé au sommet d'un arbre Merkle qui sert d'engagement cryptographique pour toutes les données stockées dans l'arbre, inclus dans l'en-tête de chaque bloc de la blockchain.
En-tête de bloc – La section métadonnées d'un bloc blockchain qui contient la racine Merkle, le hachage du bloc précédent, l'horodatage et d'autres champs spécifiques au protocole.
Patricia Trie – Un trie (arbre de préfixes) optimisé en espace utilisé par Ethereum en combinaison avec le hachage Merkle pour créer le Merkle Patricia Trie pour le stockage d'état.
Arbre de Merkle – Un successeur proposé aux arbres de Merkle dans Ethereum qui utilise des engagements vectoriels au lieu d'engagements basés sur le hachage, réduisant ainsi la taille des preuves.
Preuve de connaissance zéro – Une méthode cryptographique qui permet à une partie de prouver sa connaissance d'un fait sans révéler le fait lui-même, utilisant souvent des arbres de Merkle pour les engagements d'état dans les ZK-rollups.
Preuve de réserves – Une pratique d'audit selon laquelle les plateformes d'échange de cryptomonnaies utilisent les arbres de Merkle pour prouver que les dépôts des clients sont entièrement garantis par des actifs sur la blockchain.
Airdrop – Un événement de distribution de jetons qui utilise généralement des contrats intelligents basés sur l'arbre Merkle pour permettre aux bénéficiaires éligibles de réclamer des jetons en soumettant des preuves Merkle.
State Trie – L'arbre de Merkle Patricia d'Ethereum qui associe chaque adresse de compte à son état actuel, constituant ainsi la base de l'architecture de stockage de données d'Ethereum.
Arbre binaire – Une structure de données fondamentale en informatique où chaque nœud a au maximum deux enfants, servant de base structurelle aux arbres de Merkle standard.
Reçu de transaction – Une structure de données générée après l'exécution d'une transaction Ethereum, stockée dans un arbre de Merkle distinct au sein de chaque bloc pour une vérification efficace du reçu.
QFP
Q : Qu'est-ce qu'un arbre de Merkle et pourquoi est-il important pour la blockchain ? Un arbre de Merkle est une structure de données qui organise les données sous forme d'arbre binaire de hachages cryptographiques, produisant un hachage racine unique représentant l'ensemble des données. Il est essentiel pour la blockchain car il permet une vérification efficace des transactions : un client léger peut confirmer qu'une transaction est incluse dans un bloc en vérifiant uniquement une petite preuve de Merkle (de taille logarithmique) au lieu de télécharger chaque transaction.
Q : Comment fonctionne une preuve de Merkle ? Une preuve de Merkle repose sur les hachages des nœuds frères le long du chemin menant d'une feuille spécifique à la racine de Merkle. Pour la vérifier, on hache les données cibles, on les combine avec le premier hachage frère, on hache le résultat, on le combine avec le hachage du nœud frère suivant, et ainsi de suite jusqu'à atteindre la racine. Si la racine calculée correspond à la racine de Merkle connue, les données sont validées comme étant incluses dans l'arbre. Pour un arbre comportant un million de feuilles, cela ne nécessite qu'une vingtaine de hachages.
Q : Quelle est la différence entre un arbre de Merkle et un arbre de Patricia de Merkle ? Un arbre de Merkle standard est un arbre de hachage binaire simple utilisé pour les listes ordonnées de données (comme les transactions d'un bloc Bitcoin). Un arbre de Patricia de Merkle, utilisé par Ethereum, est une structure plus complexe qui combine un trie radix (arbre de préfixes) avec le hachage Merkle pour créer un magasin clé-valeur à intégrité prouvée.
Q : Que sont les arbres de Verkle et remplaceront-ils les arbres de Merkle ? Les arbres de Verkle sont une proposition d'amélioration pour Ethereum (EIP-6800) qui remplace les engagements basés sur le hachage par des engagements polynomiaux (vectoriels), produisant ainsi des preuves plus courtes, essentielles pour la feuille de route des clients sans état d'Ethereum. Cependant, les arbres de Verkle reposent sur la cryptographie à courbes elliptiques, potentiellement vulnérable aux ordinateurs quantiques, tandis que les arbres de Merkle, basés sur le hachage, sont considérés comme plus résistants à l'informatique quantique.
Q : Comment les arbres de Merkle sont-ils utilisés dans les distributions de NFT et de tokens par airdrop ? Les projets construisent un arbre de Merkle dont les feuilles sont les adresses de portefeuilles éligibles (et les montants qu'elles peuvent réclamer). Seule la racine de l'arbre est stockée sur la blockchain, ce qui permet d'économiser les frais de gaz. Chaque utilisateur éligible peut réclamer des tokens en soumettant sa preuve Merkle : un petit ensemble de hachages attestant que son adresse figure bien dans l'arbre. Ce modèle, popularisé par la bibliothèque MerkleProof d'OpenZeppelin, a été utilisé par Uniswap, ENS, Optimism et des centaines d'autres projets.
Q : Les arbres de Merkle peuvent-ils être utilisés pour préserver la confidentialité ? Les arbres de Merkle standard ne garantissent pas la confidentialité : toutes les données sont visibles. Cependant, des variantes spécialisées sont utilisées dans les systèmes préservant la confidentialité. Les preuves de Merkle à divulgation nulle de connaissance permettent de prouver l’inclusion sans révéler les données des feuilles, autorisant ainsi des transactions privées et la vérification d’état confidentielle.
Q : Que se passe-t-il si deux ensembles de données différents produisent la même racine Merkle ? Cela constituerait une collision de hachage : deux entrées différentes produisent la même sortie de la fonction de hachage. Avec SHA-256 (utilisé dans Bitcoin), la détection d’une telle collision nécessiterait environ 2^128 opérations, ce qui est informatiquement irréalisable avec les technologies actuelles et prévisibles.
Références
Merkle, RC « Une signature numérique basée sur une fonction de chiffrement conventionnelle »
