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.