Articles récents
  • Vivatech 2024 : Le rendez-vous incontournable de l’innovation et de la blockchain

    VivaTech 2024, l’un des plus grands salons de la technologie et de l’innovation en Europe, bat actuellement son plein à...

  • Le Digital Services Act (DSA) : les enjeux de son application dans ce contexte électoral

    Le règlement relatif à un marché unique des Services Numériques, plus communément appelé DSA pour Digital Services Act,...

  • Bitcoin : vers la fin de l’État-nation

    La monnaie représente un enjeu central pour les grands États de notre société contemporaine puisqu’elle permet de...

  • La Blockchain Business School et PyratzLabs lancent un programme de financement boursier

    L’industrie du Web3 est en pleine expansion et la demande de talents qualifiés dans le domaine de la blockchain ne...

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

Cette fonction permet de vérifier l’intégrité des données d’un ensemble. Si les deux hashes sont les mêmes, votre fichier n’est pas corrompu !
Intermédiaire

Ralph Merkle, informaticien, est le petit-neveu de Fred Merkle, AKA “bonehead”, joueur de première base en 1907 pour les New York Giants (baseball et non football américain). Merkle est surtout connu pour son invention de la public-key cryptography (ou cryptographie clé publique). Titulaire d’un Bachelor et d’un Master de University of California, Berkeley et d’un doctorat de Stanford, Ralph a une liste d’inventions qui donneraient le vertige à tout informaticien moyen :

  • Les puzzles de Merkle
  • Le cryptosystème de Merkle-Hellman
  • La construction de Merkle Damgård

Toutefois, cet article portera sur ce qu’est l’arbre de Merkle et comment il fonctionne.  

 

Qu’est-ce que l’arbre de Merkle ?

Le concept d’arbre de Merkle a pour objectif de vérifier l’intégrité des données d’un ensemble donné. Dans le cas des réseaux peer-to-peer (de pair à pair), où les utilisateurs et les participants doivent partager et valider des informations de manière indépendante, l’arbre de Merkle intervient lorsqu’il s’agit de traiter ce que l’on appelle les fonctions hash. Si vous n’êtes pas encore à l’aise avec le concept de hash, je vous invite à lire cet article d’abord.

 

Lire plus : Qu’est-ce que le hachage ?

 

Arbre de Merkle : comment vérifier que le fichier que je télécharge n’est pas corrompu ?

Supposons que vous souhaitez télécharger un fichier volumineux à l’aide d’un logiciel open-source, vous allez vérifier que le hash du fichier que vous avez téléchargé correspond à celui qui a été effectué par les développeurs. Si les deux hashes sont les mêmes, alors vous savez que le fichier qu’ils possèdent est exactement le même que le vôtre. Pour rappel, un hash est unique ! Par contre, si le hash ne correspond pas à celui du ou des développeurs (si les deux hashes sont différents), un problème majeur se pose : soit un fichier a été téléchargé de manière malveillante, soit il n’a pas été téléchargé correctement et ne fonctionnera tout simplement pas. Le temps que vous attendez pour le téléchargement de votre fichier dépend du bon fonctionnement de ces fonctions de hachage, car si ce n’est pas le cas, vous devrez recommencer le téléchargement en espérant que le fichier n’est pas corrompu d’une quelconque manière. Il doit sûrement y avoir un moyen plus simple de le faire, non ? 

 

Comment se construit un Arbre de Merkle ?

C’est précisément là que l’arbre de Merkle entre en jeu. Par exemple, un fichier de 75 Go peut être divisé en cent morceaux, de sorte que chaque morceau fasse 0,75 Go. Le processus pour récupérer votre fichier serait alors de télécharger morceau par morceau puis de le rassembler : c’est typiquement ce qui se passe lorsque les fichiers sont des fichiers pirates ou torrent. Dans ce cas, un Arbre de Merkle vous fournira un hash connu sous le nom de racine de Merkle (ou Merkle root), un hash unique qui est une représentation de chaque morceau de données qui compose votre fichier initial. 

 

Comment faciliter la vérification des données avec le Merkle root ?

Vous suivez toujours ? Bien. Une fois que nous avons tous les hashes, il est possible de savoir si l’un est corrompu en le comparant avec les autres sources. Cependant, si votre fichier contient des centaines de fragments, il est peu probable que le hash de tous ces fragments pose un problème, n’est-ce pas ? Peut-être pas. Au lieu de cela, prenez chaque paire de hashes, combinez-les, pour ensuite les hacher ensemble. Si nous avons des fragments, disons h1+h2, h3 +h4, h5+h6, et h7+h8, nous nous retrouvons avec quatre nouveaux hashes (le nouveau hash h12 étant la combinaison des hashes h1+h2). Ensuite, un autre tour de hachage a lieu jusqu’à ce que nous nous retrouvions avec deux. Enfin, nous effectuons notre dernier hash, appelé master hash, racine de Merkle (ou Merkle root).

Prenons 8 documents appelés 1 à 8. Puis, hachons-les un par un, et appelons leur hachage h1 à h8.

 

À quoi ressemble un arbre de Merkle ?

Une fois la racine de Merkle atteinte, la structure ressemble à un arbre inversé. D’où l’arbre de Merkle.

La moitié inférieure est constituée des feuilles, qui sont combinées pour produire des nœuds, et la dernière partie (la plus haute) est alors la racine (AKA Merkle root), et cette racine représente le fichier que nous avons téléchargé. Nous pouvons tracer et comparer la racine à sa source, si elle correspond, c’est bon ! Mais là encore, si les hashes sont différents, nous pouvons alors en déduire que les données ont été modifiées. En clair, un ou plusieurs fragments peuvent produire un hash différent, donc une modification, même minime des données donnera un résultat totalement différent, ou une Merkle Root.

 

Comment déterminer si un fragment de l’arbre de Merkle est défectueux ?

Heureusement, il existe un moyen pour vous de déterminer si un fragment est défectueux ou non. Prenons l’exemple de h5. Regardons l’un des deux hashes de la paire qui a produit la racine de Merkle (h1234 et h5678). La valeur de h5678 devrait correspondre car il n’y a pas d’erreur dans ce sous-arbre. Vous pouvez comparer respectivement h56 et h78 pour vérification. Si l’un des hashes est incorrect, vous pouvez alors retélécharger ce chunk. 

En résumé, un arbre de Merkle est développé en décomposant les données en différents morceaux, qui sont ensuite hachés à plusieurs reprises pour former ce qui est la racine de Merkle. Vous pouvez déterminer efficacement si quelque chose s’est gravement détraqué dans les données fournies.

 

Que penser du Merkle root ?

Sans les arbres et les racines Merkle (Merkle root), le Bitcoin et les autres crypto-monnaies seraient loin d’être aussi fluides qu’elles le sont aujourd’hui. La genèse systématique de Merkle permet aux utilisateurs de rechercher des preuves de leurs transactions, de les comparer et de les décomposer avec une certaine facilité et un minimum de remaniement.

Prev
Cette semaine dans la Silicon Valley #08

Cette semaine dans la Silicon Valley #08

L’actualité de la semaine en bref : Telegram se lance dans la crypto, SBF se défend maladroitement, la BCE attaque...

Next
Les DAO : le futur des fonds d’investissement ?

Les DAO : le futur des fonds d’investissement ?

Les fonds de Venture Capital aiment se présenter comme disruptifs. Mais ils oublient qu'ils peuvent eux-mêmes être...

Versia Hodges

Vous Pourriez aussi aimer !
Article recommandé
L’actualité de la semaine en bref : Telegram se lance…
fr_FRFrench