Arbre de Merkle
Qu’est-ce qu’un arbre de Merkle ?
Un arbre de 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 à encoder 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 de 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 pouvant ê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 de ne pas obtenir l’ensemble original de transactions. Cependant, le logiciel de Bitcoin n’exécute pas l’intégralité du bloc de données de transaction, représentant 10 minutes de transactions en moyenne, via la fonction de hachage à la fois. 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 l’ensemble du bloc. (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 schéma 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 de la rangée du bas sont appelés « feuilles », les hachages intermédiaires en tant que « branches » et le hachage en haut en tant que « 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 exécutée via une fonction de hachage pour produire le hachage unique du bloc : 0000000000000000000bfc767ef8bf28c42cbd4bdbafd9aa1b5c3c33c2b08959428 . 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 Tré est inclus dans le bloc du schéma ci-dessus. Si vous avez le hachage racine (HABCDEFGH), le processus ressemble à un jeu de sudoku : vous interrogez le réseau sur Hré, et il renvoie HC, HUN B, et HE F G H. L’arbre de Merkle vous permet de vérifier que tout est comptabilisé avec trois hachages : étant donné HUN B, HC, HE F G H, et la racine HABCDEFGH, Hré (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.