Arbre Merkle
Qu’est-ce qu’un arbre Merkle?
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 à 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 qui peut être utilisée pour vérifier qu’un ensemble donné de données est le même que l’ensemble original de transactions, mais de ne pas obtenir le jeu de transactions d’origine. Cependant, le logiciel de Bitcoin n’exécute pas tout le bloc de données de transaction – représentant en moyenne 10 minutes de transactions – via la fonction de hachage en même temps. 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 tout le 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 sur la ligne 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 exécutée via une fonction de hachage pour produire le hachage unique du bloc: 000000000000000000bfc767ef8bf28c42cbd4bdbafd9aa1b5c3c33c2b08952894 dans le cas du bloc. Ce hachage n’est pas réellement inclus dans le bloc concerné, mais dans le suivant; il est distinct de la racine Merkle.
L’arbre Merkle est utile car il permet aux utilisateurs de vérifier une transaction spécifique sans télécharger l’ensemble 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 Merkle vous permet de vérifier que tout est pris en compte avec trois hachages: étant donné que 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.