Contenu
Qu'est-ce qu'un arbre Merkle ?
Comment fonctionnent les arbres Merkle ?
Pourquoi les racines Merkle sont-elles utilisées dans Bitcoin ?
Exploitation minière
Vérification
Réflexions finales
Qu'est-ce qu'un arbre Merkle ?
L'idée d'un arbre Merkle est née au début des années 1980 par Ralph Merkle, un informaticien surtout connu pour ses travaux dans le domaine de la cryptographie à clé publique.
Un arbre Merkle est une structure utilisée pour vérifier efficacement l'intégrité des données dans un ensemble de données donné et est particulièrement important dans le contexte des réseaux peer-to-peer où les participants doivent partager et vérifier les informations de manière indépendante.
Les fonctions de hachage sont une partie essentielle des arborescences Merkle, nous vous recommandons donc de lire l'article intitulé Qu'est-ce que le hachage ? Avant de poursuivre la lecture de cet article.
Comment fonctionnent les arbres Merkle ?
Disons que vous souhaitez télécharger un fichier volumineux. Dans le cas d'un logiciel Open Source, vous souhaiterez généralement vérifier que la valeur de hachage du fichier que vous avez téléchargé correspond à la valeur rendue publique par les développeurs. Si tel est le cas, vous savez que le fichier que vous avez sur votre ordinateur correspond au leur.
Si les valeurs de hachage ne correspondent pas, alors vous avez un problème. Soit vous avez téléchargé un fichier malveillant se faisant passer pour le programme, soit le téléchargement a échoué et cela ne fonctionne donc pas. Si le téléchargement échoue, vous ne serez probablement pas satisfait si vous devez attendre un moment pour que le fichier soit téléchargé. Il faudra alors recommencer le processus et espérer que tout se passe bien cette fois-ci.
Dans ce cas, vous pensez peut-être s’il existait un moyen plus simple de procéder. Heureusement, c'est là qu'intervient l'arbre Merkle. Grâce à cet arbre, le fichier est divisé en parties. Si la taille du fichier est de 50 Go, vous pourrez peut-être le diviser en 100 morceaux, chacun de 0,5 Go, et le télécharger morceau par morceau. C'est essentiellement ce que vous faites lorsque vous utilisez des fichiers torrent.
Dans ce cas, la source du fichier vous fournira une valeur de hachage connue sous le nom de racine Merkle. Cette valeur unique est une représentation de chaque élément de données qui constitue votre fichier, mais la racine Merkle facilite grandement la vérification des données.
Pour faire simple, nous allons regarder cet exemple où nous utilisons un fichier de 8 Go divisé en 8 parties, et nous étiqueterons ces différentes parties avec les lettres A à H. Chaque partie passera ensuite par une fonction de hachage, résultant en 8 valeurs de hachage différentes.
Nous allons faire passer chacune des huit parties via une fonction de hachage pour obtenir leurs valeurs de hachage.
Eh bien, nous avons maintenant quelque chose qui a un peu plus de sens. Nous avons les valeurs de hachage de toutes les parties, donc si l'une d'elles est fausse, vous le saurez en la comparant à la valeur de hachage source, n'est-ce pas ? Peut-être, mais cela est également extrêmement inefficace. Si le fichier comporte des milliers de parties, allez-vous vraiment toutes les partitionner et ensuite comparer les résultats avec autant de soin ?
Non, à la place, nous prendrons chaque paire de valeurs de hachage, les additionnerons, puis les hacherons ensemble. Nous hachons donc hA + hB, hC + hD, hE + hF et hG + hH pour obtenir 4 valeurs de hachage, puis nous effectuons un autre cycle de hachage pour ces valeurs, pour finalement atteindre 2 valeurs de hachage. Enfin, nous hachons les deux valeurs restantes pour obtenir la valeur de hachage principale : la racine Merkle (ou valeur de hachage racine).
La structure ressemble à un arbre inversé, où dans la dernière rangée se trouvent les feuilles qui se réunissent pour produire les nœuds et éventuellement la racine.
Nous avons maintenant la racine Merkle qui représente le fichier que nous avons téléchargé. Cette valeur de hachage racine peut être comparée à celle fournie par la source, et si elles correspondent, tant mieux ! Mais si les valeurs de hachage sont différentes, cela nous garantit que les données ont été modifiées, c'est-à-dire qu'une ou plusieurs parties ont produit une valeur de hachage différente, donc toute simple modification des données nous donnera une racine Merkle complètement différente. .
Heureusement, il existe un moyen simple pour nous tous de vérifier quelle pièce est erronée. Dans ce cas, disons que cette partie est hE. Tout d'abord, demandez à un pair les deux valeurs de hachage qui ont produit la racine Merkle (hABCD et hEFGH). Votre valeur hABCD doit correspondre à la sienne car il n'y a aucune erreur dans ce sous-arbre. Mais cela ne s'applique pas à la valeur hEFGH, vous devez donc vérifier cette valeur. Vous demandez ensuite les valeurs hEF et hGH et les comparez à vos propres valeurs. Vous constaterez que la valeur hGH est correcte, puis vous réaliserez que la valeur hEF est la raison du problème. Enfin, vous comparerez les valeurs de hachage de hE et hF, et vous savez maintenant que hE est incorrect, vous pouvez donc retélécharger ce fragment.
En bref, un arbre Merkle est créé en divisant les données en plusieurs parties, qui sont ensuite hachées de manière itérative pour former une racine Merkle. Vous pouvez alors vérifier efficacement si une erreur s’est produite avec une donnée. Comme nous le verrons dans la section suivante, il existe également d’autres applications intéressantes.
Voulez-vous commencer à trader des devises numériques ? Achetez du Bitcoin (BTC) sur Binance maintenant !
Pourquoi les racines Merkle sont-elles utilisées dans Bitcoin ?
Il existe quelques cas d'utilisation des arbres Merkle, mais nous nous concentrerons ici sur leur importance dans les blockchains. Les arbres Merkle sont d'une grande importance pour le Bitcoin et les autres crypto-monnaies. Il représente un composant majeur de chaque bloc, car il se situe dans les partitions de stockage des blocs. Pour accéder aux feuilles de l'arborescence, nous utilisons le hachage de transaction ( ID de transaction) de chaque transaction du bloc.
Dans ce cas, la racine Merkle sert à plusieurs fins, et nous passerons ci-dessous en revue ses applications dans l’extraction de crypto-monnaie et la vérification des transactions.
Exploitation minière
Un bloc Bitcoin se compose de deux parties. La première partie est la partition de stockage du bloc, qui est une partie de taille fixe contenant les métadonnées du bloc. La deuxième partie est une liste de transactions de taille variable, mais sa taille est généralement beaucoup plus grande que la partition de stockage par blocs.
Les mineurs doivent hacher les données à plusieurs reprises pour produire un résultat qui correspond aux conditions spécifiques pour extraire un bloc valide. Ils peuvent faire des milliards de tentatives avant de trouver le bon bloc. À chaque tentative, ils modifient un nombre aléatoire dans la section de stockage du bloc (le code privé) pour produire un résultat différent. Cependant, une grande partie de la masse reste la même. Le nombre de transactions peut atteindre des milliers de transactions et vous devrez les hacher à chaque fois.
La racine Merkle rend le processus beaucoup plus facile, car lorsque vous démarrez le minage, vous mettez dans une rangée toutes les transactions que vous souhaitez inclure et créez un arbre Merkle. Vous placez ensuite la valeur de hachage racine résultante (32 octets) dans la partition de stockage par blocs. Ensuite, lors du minage, tout ce que vous avez à faire est de hacher la partition de stockage de blocs au lieu du bloc entier.
Cette méthode fonctionne car elle ne peut pas être falsifiée, résumant efficacement toutes les transactions de bloc dans un format compact. Et vous ne pouvez pas trouver une partition de stockage en bloc valide, puis modifier la liste des transactions plus tard, car cela modifierait la racine Merkle. Lorsque le bloc est envoyé à d'autres nœuds, il calcule la racine à partir de la liste des transactions, et si elle ne correspond pas à ce qui est mentionné dans la section de stockage des blocs, le bloc est rejeté.
Vérification
Il existe une autre propriété intéressante des racines de Merkle dont nous pouvons profiter. Cette fonctionnalité est importante pour les logiciels de nœuds simples (nœuds qui ne portent pas la copie complète de la chaîne blockchain). Si vous exécutez un nœud sur une machine aux ressources limitées, vous ne souhaitez pas télécharger et hacher toutes les transactions du bloc. Au lieu de cela, vous pouvez demander une preuve Merkle – une preuve fournie par l'ensemble du nœud qui prouve qu'une transaction a été effectuée. existe dans un bloc spécifique. Ceci est souvent appelé vérification simplifiée des paiements (SPV) et a été expliqué en détail par Satoshi Nakamoto dans le rapport technique Bitcoin.
Pour vérifier HD, nous n'avons besoin que des valeurs de hachage affichées en rouge.
Regardons par exemple un scénario dans lequel nous souhaitons connaître des informations sur une transaction avec l'ID de transaction hD. Si nous disposons de la valeur hC, nous pouvons trouver hCD. Ensuite, nous avons besoin de hAB pour calculer hABCD. Enfin, dans le cas de hEFGH, nous pouvons vérifier que la racine Merkle résultante correspond à celle de la partition de stockage en bloc. Si cela correspond, cela prouve que la transaction existait dans le bloc – car il serait presque impossible de générer la même valeur de hachage avec des données différentes.
Dans l'exemple précédent, nous n'avions qu'à effectuer le hachage trois fois, et sans la preuve de Merkle, nous aurions dû l'effectuer 7 fois. Étant donné que les blocs contiennent aujourd'hui des milliers de transactions, l'utilisation de la preuve de Merkle permet d'économiser beaucoup de temps et de ressources informatiques.
Réflexions finales
Les arbres Merkle se sont révélés extrêmement utiles dans une gamme d'applications informatiques et, comme nous l'avons vu, ils revêtent une importance capitale pour les blockchains. Dans les systèmes distribués, les arborescences Merkle facilitent la vérification des informations sans inonder le réseau d'un torrent de données inutiles.
Sans les arbres Merkle (et les racines Merkle), les blocs de Bitcoin et d'autres crypto-monnaies ne seraient pas aussi petits qu'ils le sont aujourd'hui. Alors que les simples logiciels de contrat manquent de confidentialité et de sécurité, Merkle's Proof permet aux utilisateurs de vérifier si leurs transactions ont rejoint un bloc à des coûts minimes.