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

Un arbre de Merkle se présente comme un modèle de structure de données qui contient un résumé d’informations d’un volume de données. Il se base sur une fonction de hachage, dont la caractéristique est de prendre une donnée de taille arbitraire (aléatoire) en entrée pour lui donner une empreinte de taille fixe à partir de laquelle il est impossible de retrouver la donnée initiale. C’est une fonction à sens unique.

Dans ce type de structure, les données que l’on appelle « feuilles » sont disposées dans un certain ordre et toutes hachées. Leurs empreintes sont combinées 2 à 2 qui seront hachées à leur tour et cela jusqu’à ce qu’il n’y ait plus qu’une seule empreinte appelée « racine » (root) qui sera ajoutée comme référence dans le « header » du bloc. Grâce à cette organisation au sein d’un bloc, les mineurs pourront remonter très rapidement vers la dernière transaction concernée lors de la vérification des nouvelles transactions. Ils pourront également vérifier s’il existe une transaction dont le montant est supérieur à celui qui doit être dépensé dans la nouvelle transaction.

L’arbre de Merkle offre la possibilité d’identifier les transactions appartenant à un même membre et cela très rapidement. Dans le cas où l’ensemble de ces transactions ou une seule suffit à couvrir les dépenses effectuées par ce membre, cela signifie que sa transaction sera autorisée.

L’utilisation d’un arbre de Merkle dans la blockchain permet d’avoir une structure qui ne nécessite pas de télécharger toute la base de données, mais seulement une partie. En effet, il est possible d’accéder à n’importe quelle transaction sans devoir tout télécharger. On peut prendre la branche qui permet de remonter à la transaction qui nous intéresse.

Cette structure s’avère ainsi très utile pour démontrer qu’une chaîne de transaction reste inchangée. En utilisant la chaîne de hachage cryptographique, on peut remonter jusqu’à la transaction recherchée ce qui permet de s’assurer que toute la branche – depuis la racine jusqu’à la transaction – n’a pas été altérée. Dans la mesure où la vérification peut se faire sur une seule branche sans devoir télécharger toute la base de données dans son intégralité, cela rend la structure très légère à utiliser en matière de capacité de calcul et de mémoire. Ainsi, elle est parfaitement adaptée aux participants de la blockchain dits « légers » qui ne téléchargent pas la base de données complète (la blockchain dans son intégralité), mais peuvent toute de même vérifier des transactions sur la chaîne de blocs.

L’organisation des données en arbre de hachage est essentielle dans le fonctionnement d’un réseau qui repose sur une blockchain, que ce soit en matière d’accès efficace aux données qu’à leur sécurité.

Un arbre de Merkle est un arbre de hachage pouvant être utilisé dans la vérification de tout type de données stockées, manipulées et transférées dans et entre des ordinateurs. Il est principalement utilisé dans la cryptographie basée sur le hachage en s’assurant que les blocs de données reçus dans un réseau P2P, envoyés d’autres pairs, sont reçus intacts et non altérés. Il permet également de vérifier que les autres pairs n’envoient pas de faux blocs.

On retrouve fréquemment l’arbre de Merkle dans les systèmes de fichiers comme IPFS pour contrer la dégradation des données, les protocoles tels que Dat et Apache Wave, les systèmes de contrôle de révision distribués comme Mercurial et Git ou encore les systèmes de sauvegarde comme Tahoe-LAFS, mais aussi dans le cadre de la transparence des certificats. Cela fait un certain moment que des suggestions ont été faites pour l’utilisation des arbres de hachage dans des systèmes informatiques de confiance.

On peut également retrouver différents types de blocs, tels que le bloc ommer et le bloc orphelin.