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. En bitcoin et 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 pas pour obtenir l'ensemble original de transactions. 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 en une seule fois, toutefois. Plutôt, 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é, cette structure ressemble à un arbre. Dans le schéma ci-dessous, "T" désigne une opération, "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 sous forme de " 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écutez une fonction de hachage pour produire le hachage unique du bloc :000000000000000000bfc767ef8bf28c42cbd4bdbafd9aa1b5c3c33c2b089594 dans le cas du bloc #482819. Ce hachage n'est pas réellement inclus dans le bloc concerné, mais 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 350 gigaoctets à fin juin 2021). Par exemple, dire que vous vouliez vérifier cette transaction T ré est inclus dans le bloc du schéma 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 ré , et il renvoie H C , H UN B, et H E F G H . L'arbre Merkle vous permet de vérifier que tout est comptabilisé avec trois hachages :étant donné H UN B , H C , H E F G H, et la racine H ABCDEFGH , H ré (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ées 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.