Un arbre Merkle est une structure de données utilisée dans les applications informatiques. Dans le bitcoin et d'autres crypto-monnaies, les arbres Merkle servent à coder les données de la blockchain de manière plus efficace et sécurisée.
Ils sont également appelés «arbres de hachage binaires».
Briser l'arbre Merkle
Dans la blockchain de bitcoin, un bloc de transactions est exécuté via un algorithme pour générer un hachage, qui est une chaîne de chiffres et de lettres qui peut être utilisée pour vérifier qu'un ensemble de données donné est le même que l'ensemble de transactions d'origine, mais ne pas obtenir l'ensemble de transactions d'origine. Cependant, le logiciel de Bitcoin ne gère pas l'intégralité du bloc de données de transaction - ce qui représente en moyenne 10 minutes de transactions - via la fonction de hachage. Au lieu de cela, chaque transaction est hachée, puis chaque paire de transactions est concaténée et hachée ensemble, et ainsi de suite jusqu'à ce qu'il y ait un hachage pour le bloc entier. (S'il y a un nombre impair de transactions, une transaction est doublée et son hachage est concaténé avec lui-même.)
Visualisée, cette structure ressemble à un arbre. Dans le diagramme ci-dessous, "T" désigne une transaction, "H" un hachage. Notez que l'image est très simplifiée; un bloc moyen contient plus de 500 transactions, pas huit.
Les hachages sur la rangée du bas sont appelés «feuilles», les hachages intermédiaires comme «branches» et le hachage en haut comme «racine». La racine Merkle d'un bloc donné est stockée dans l'en-tête: par exemple, la racine Merkle du bloc # 482819 est e045b18e7a3d708d686717b4f44db2099aabcad9bebf968de5f7271b458f71c8. La racine est combinée avec d'autres informations (la version du logiciel, le hachage du bloc précédent, l'horodatage, la cible de difficulté et le nonce), puis s'exécute via une fonction de hachage pour produire le hachage unique du bloc: 0000000000000000000000bfc767ef8bf28c42cbd4bdbafd9aa1b5c3c33c2b089594 dans le cas du bloc # 19. Ce hachage n'est pas réellement inclus dans le bloc concerné, mais dans le suivant; elle est distincte de la racine de Merkle.
L'arbre Merkle est utile car il permet aux utilisateurs de vérifier une transaction spécifique sans télécharger l'intégralité de la blockchain (plus de 130 gigaoctets fin août 2017). Par exemple, supposons que vous vouliez vérifier que la transaction T D est incluse dans le bloc du diagramme ci-dessus. Si vous avez le hachage racine (H ABCDEFGH), le processus est comme un jeu de sudoku: vous interrogez le réseau sur H D et il renvoie H C, H AB et H EFGH. L'arbre de Merkle vous permet de vérifier que tout est pris en compte avec trois hachages: étant donné H AB, H C, H EFGH et la racine H ABCDEFGH, H D (le seul hachage manquant) doit être présent dans les données.
Les arbres Merkle portent le nom de Ralph Merkle, qui les a proposés dans un article de 1987 intitulé "Une signature numérique basée sur une fonction de cryptage conventionnelle". Merkle a également inventé le hachage cryptographique.
