Arbre de Merkle définition

Vous avez certainement entendu parler de blockchain et de hash ? Lorsqu’on s’intéresse à cette technologie et au Bitcoin, il arrive d’entendre parler d’Arbre de Merkle. Ils sont un des concepts qui donnent toute son importance à la blockchain. 

SOMMAIRE

Qu’est-ce qu’un arbre de Merkle ?

L’arbre de Merkle, également appelé arbre de hachage binaire, est un composant indispensable de la technologie blockchain, assurant la vérification sécurisée et efficace des données.

Il a été inventé par Ralph Merkle en 1979, qui avait auparavant co-inventé le « Merkle–Hellman knapsack cryptosystem« .

Les arbres de Merkle, également connus sous le nom d’arbres de hachage binaires, sont une sorte de structure de données répandue en informatique.

Dans le bitcoin et d’autres cryptomonnaies, ils sont utilisés pour chiffrer les données de la blockchain de manière plus efficace et sécurisée.

Il s’agit d’une structure de données mathématique composée de hachages binaires de différents blocs de données qui résument toutes les transactions d’un bloc.

Il permet également une vérification rapide et sécurisée du contenu dans les grands ensembles de données et vérifie la cohérence et le contenu des données.

Pour résumer, un arbre de Merkle est une structure de données qui peut aider à prouver l’intégrité d’un ensemble de données tout en réduisant considérablement les besoins en mémoire nécessaires pour le faire.

Cette utilité est obtenue grâce à des fonctions de hachage à sens unique qui fusionnent des couches de données en une racine de Merkle unique capable de valider toutes les données contenues dans l’arbre de Merkle associé.

L’architecture de données de l’arbre de Merkle est un élément clé des blockchains publiques et est utilisée dans les réseaux peer-to-peer (P2P) tels que les applications de partage de fichiers, le bitcoin et d’autres blockchains décentralisées.

Principe du Merkle Tree

Les fonctions de hachages et les hash

Une fonction de hachage fait correspondre n’importe quel type de données arbitraires de n’importe quelle longueur à une sortie de taille fixe. Il est couramment utilisé en cryptographie puisqu’il s’agit d’une fonction cryptographique.

En d’autres termes, un hachage est le résultat d’une fonction de hachage (fonction mathématique) qui génère une chaîne de caractères uniques de taille fixe appelés octets. Cette fonctionnalité permet d’identifier des données de manière simple et sécurisée.

Ils sont efficaces et reconnus pour une propriété : ils sont irréversibles. C’est une fonction à sens unique qui n’est censée fonctionner que dans une seule direction.

Essentiellement, ils sont utilisés pour encoder les données afin de les rendre plus accessibles et sécurisées, peu importe le nombre de données saisies. Dans la blockchain, ces fonctions de hachages sont utilisées pour garantir l’authenticité des données.

Une fonction de hachage fait correspondre tout type de données arbitraires de n’importe quelle longueur à une sortie de taille fixe.

Elles sont efficaces et sont connues pour une propriété : elles sont irréversibles. C’est une fonction à sens unique qui n’est censée fonctionner que dans un seul sens.

Certaines des familles de hachage disponibles sont Message Direct (MD), Secure Hash Function (SHF) et RIPE Message Direct (RIPEMD).

Prenons un exemple. Si l’on veut utiliser l’algorithme de hachage SHA256 et qu’on transmet 101Blockchains en entrée, on obtiendra le résultat suivant :

fbffd63a60374a31aa9811cbc80b577e23925a5874e86a17f712bab874f33ac9.

Il est important de connaître les hashs car ils sont un composant principal de l’arbre de Merkle.

Les nœuds racine et nœuds feuilles

Pour bien assimiler le fonctionnement d’un arbre de Merkle, il faut bien intégrer le concept de nœuds parents et enfants.

À part la racine (Merkle Root), tous les noeuds sont reliés à des noeuds parents, par un hash qui se situe au-dessus de celui-ci dans la hiérarchie.

Autrement dit, un nœud contenant les valeurs des deux nœuds qui lui sont inférieures est le « parent » de ces deux nœuds.  

Par ailleurs, il faut savoir que si chaque nœud a un maximum de deux « nœuds enfants », alors il sera désigné d’arbre de hachage binaire :

Dans une chaîne de blocs, l’arbre de Merkle permettra de fournir une empreinte pour chaque transaction effectuée sur celle-ci provenant d’un bloc. 

C’est avec ce processus que l’on peut voir si une transaction est effectivement comprise dans un bloc de la chaîne ou non.

Sur la chaîne de blocks Bitcoin, les arbres de Merkle sont utilisés pour organiser les transactions à l’intérieur des blocs :

Bien d’autres protocoles cryptographiques utilisent les arbres de Merkle pour structurer leur propres transactions dans les blocs des chaînes.

Ethereum utilise trois arbres de Merkle pour organiser différents types de données.

D’une part, les transactions et les reçus (receipts), qui sont des données qui montrent l’effet des transactions. Ensuite, il y a les données relatives à l’état du système (soldes des comptes, code des contrats, données de la chaîne de blocs).

AUTRE TYPE D’UTILISATION DE L’ARBRE DE MERKLE : LES « MAST »

Les Merklized Abstract Syntax Trees (MAST) sont des « arbres syntaxiques abstraits merkélisés » permettant de gérer la structuration des smarts contracts, ce qui permet d’ajouter des avantages en matière de scalabilité et de confidentialité du réseau. 

Ainsi en agençant les différentes conditions d’un contrat intelligent, il est possible de n’exécuter qu’une partie de ces conditions sans en révéler les autres pour les utilisateurs qui interagissent avec ce contrat.

Le hachage de la racine est le hachage le plus élevé dans la structure de données hachées. Ce qui est intéressant, c’est sa relation avec Bitcoin, où cette racine fait partie de l’en-tête du bloc. Elle détermine quelles transactions sont présentes.

Un arbre de Merkle utilise un type spécial de terminologie descriptive pour décrire la relation entre les noeuds et les niveaux de nœuds, tel qu’utilisé pendant le processus de vérification de paiement simplifié (SPV).

L’arbre de Merkle dans Bitcoin

L’arbre de Merkle est essentiel au fonctionnement de Bitcoin. C’est un des grands principes utilisé de manière générale en cryptographie.

Il aurait été possible de s’en passer dans le cas qui consiste à « hacher » les IDs des transactions par lots.

Cependant, si l’on souhaite le faire pour valider une transaction particulière, il faut connaître tous les id de transactions du bloc associé et cette situation présente un problème.

Cela nécessite une très grande quantité de mémoire pour stocker et envoyer sur le réseau. L’arbre de Merkle permet d’utiliser la racine de Merkle afin de vérifier l’id de transaction sans connaître tous les id de transaction du bloc.

C’est là toute la force et la subtilité du principe. Il en découle 2 caractéristiques intéressantes : réduction de la mémoire (place sur le disque) et réduction du temps de traitement.

Les arbres de Merkle sont donc une technologie qui permettent le bon fonctionnement des blockchains et rendent cet écosystème vraiment intéressant.