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

Bref résumé

✔️ Un arbre de Merkle Tree les données, crée des valeurs de hachage de ces données et les fusionne en une structure arborescente, ce qui permet une vérification et un transfert efficaces.

✔️ Inventé par Ralph Merkle, l'arbre de Merkle est un diagramme arborescent utilisé pour l'intégrité des données.

✔️ Les arbres de Merkle sont largement utilisés dans les technologies de blockchain telles que Bitcoin et Ethereum, où ils permettent de valider les transactions et de réduire la charge de données.

Qu'est-ce qu'un arbre de Merkle Tree ?

Le concept de l'arbre de Merkle a été inventé par le mathématicien américain Ralph Merkle et breveté en 1979. L'ex-chancelier allemand n'y est donc pour rien. Il a été décrit dans le papier "Une signature numérique certifiée".

Dans le nom Merkle Tree, la dernière partie est synonyme d'arbre. Ce n'est pas sans raison, car il s'agit ici d'un diagramme d'arbre, ou modèle de ramification, où de plus en plus de branches mènent à une branche principale. Il s'agit d'un modèle de ramification similaire à celui d'un arbre généalogique.

Un autre nom pour l'arbre de Merkle est l'arbre de hash. Un hash est un dérivé algorithmique d'une entrée, c'est-à-dire que tu peux tirer un hash (dérivé) de, disons, un mot (entrée) au moyen d'un certain système d'algorithmes.

Un système très connu est le SHA (Secure Hash Algorithm) 256. Il s'agit de tirer un hash de 256 bits à partir d'une entrée donnée. Le résultat (sortie) devient alors une chaîne de 64 chiffres et lettres.

Un dérivé typique du hash SHA 256 :

"Anycoindirect" a comme résultat lorsque tu exécutes SHA 256 dessus :

98948d20dc70322d424ea5bbf37970e20b6aafa90c498116779ea964042c2c64

" anycoindirect " a pour sortie :

a730a577d61512581afdd9c74e68abb2c43b0f7db3c70a92583464277b7abc81

Tu peux constater qu'une seule majuscule change déjà tout. À partir de hashs comme celui-ci, un arbre est créé. Comme à Noël, n'est-ce pas ?

Comment fonctionne un Merkle Tree ?

Supposons que tu veuilles envoyer un message ou un fichier à quelqu'un d'autre, mais que tu ne veuilles pas que d'autres personnes puissent le voir. Il peut s'agir d'informations secrètes, comme un mot de passe, mais aussi du partage d'un fichier contenant des informations importantes. Dans ce cas, tu peux utiliser SHA 256 pour crypter le message.

Un message est divisé en morceaux et transformé en un hash. Chaque hash apparaît dans l'arbre, la racine se trouvant au sommet de l'arbre. Il s'agit du message ou du fichier complet. Un grand avantage ici est que le message peut être divisé en petits morceaux, ce qui signifie que d'énormes fichiers ne doivent pas être livrés entièrement par un seul ordinateur et que cela peut être fait beaucoup plus rapidement.

L'arbre est donc construit de bas en haut, un peu comme tu le fais avec Bittorrent. Chacun possède alors un petit morceau du fichier (réseaux peer to peer) et, du côté de l'utilisateur final, tous les petits morceaux sont recollés, après quoi l'arbre est à nouveau complet. Ensuite, l'utilisateur final peut calculer avec son Merkle Tree si tous les morceaux sont originaux (les hashs qui peuvent être calculés doivent alors correspondre à son tableau).

La racine a un résultat spécifique, donc si tu la connais, tu sais aussi si le message ou le fichier sont originaux. Dès que ce n'est pas le cas, une nouvelle tentative sera faite pour recevoir l'original. Une fois que l'arbre racine et le résultat correspondent dans ton cas, tu as reçu les bonnes informations.

Ci-dessus, nous avons expliqué comment créer un seul hash. Dans l'arborescence, certaines de ces sorties sont fusionnées et mises dans un nouveau hash en utilisant la même méthode. Ainsi, au fur et à mesure que tu arrives au sommet de l'arbre, de plus en plus d'informations apparaîtront dans un hash supérieur. Jusqu'à ce que tu arrives au sommet et que tu fusionnes tous les hashs de l'arbre en 1 seul hash, après quoi tu es prêt à envoyer les informations.

Le destinataire du message se voit communiquer l'arbre racine et commence à télécharger les branches, les hashs. Ces branches peuvent provenir de plusieurs sources. Après cela, il commence à reconstruire tous les hashs de l'arbre. Chaque partie de l'arbre doit être correcte, dès qu'elle ne l'est pas, l'arbre racine n'est pas correct, mais grâce à la reconstruction, il peut déterminer quelle partie n'est pas correcte. Il essaie alors généralement de télécharger à nouveau l'ensemble de l'arbre.

Comme ces arbres de Merkle Tree travaillent avec des données binaires, ils sont également appelés arbres binaires.

À quoi servent les arbres de Merkle Tree en cryptographie ?

Maintenant que tu sais que pour vérifier l'exactitude d'un hash, il suffit vraiment de connaître l'arbre racine, tu peux imaginer qu'il pourrait y avoir des systèmes qui en font usage.

Le Bitcoin est une blockchain importante qui utilise ce système. Sur cette blockchain, beaucoup d'informations doivent être traitées dans un bloc. Moins il y a d'informations à vérifier et à mettre dans un tel bloc, mieux c'est.

Comme un Merkle Tree peut agréger pas mal de données en un seul nombre, c'est très utile pour construire un bloc.

Disons que tu as traité 200 transactions en tant que mineur au cours des 10 dernières minutes (un nouveau bloc est ajouté au réseau Bitcoin toutes les 10 minutes environ). L'arbre Merkle Tree se met alors au travail pour réduire toutes ces transactions en un seul arbre racine.

Les validateurs du réseau Bitcoin doivent suivre l'état de la blockchain, valider les transactions et ajouter de nouvelles pièces de monnaie. S'ils ne doivent vérifier qu'une seule séquence pour s'assurer qu'elle est correcte, non seulement ils sont beaucoup plus rapides, mais un bloc est également beaucoup plus petit. Si 51 % de ces mineurs sont d'accord pour dire que l'arbre racine est correct, le bloc peut être ajouté.

Ce hash de l'arbre racine est placé au début du bloc suivant, de sorte que tous les mineurs connaissent la valeur du hash du bloc précédent. Ainsi, lorsqu'ils créent un nouveau bloc, ils définissent l'état entier du réseau avec une seule chaîne de chiffrement. Ensuite, de nouvelles transactions sont ajoutées, passant par le même processus et ainsi de suite. Si l'arbre racine n'est pas correct, par exemple parce qu'il y a des enregistrements scélérats parmi eux, les mineurs ne peuvent pas non plus se mettre d'accord et ils commencent à chercher un Merkle Tree avec l'arbre racine correct. Ethereum utilise également un arbre de Merkle, mais bien sûr, ils ont encore inventé quelque chose de spécial : l'arbre Merkle Patricia.

Si les réseaux n'utilisaient pas d'arbres de Merkle, toutes les données devraient être transmises et tu peux imaginer ce que cela signifierait pour la vitesse, sans parler de la sécurité.