Contenu
Qu'est-ce qu'un arbre Merkle ?
Comment les arbres Merkle sont-ils construits ?
Pourquoi les racines Merkle sont-elles utilisées dans Bitcoin ?
Exploitation minière
Vérification
CV
Qu'est-ce qu'un arbre Merkle ?
Le concept d'arbre de Merkle a été proposé au début des années 1980 par Ralph Merkle, un informaticien connu pour ses travaux sur la cryptographie à clé publique.
Un arbre de Merkle est une structure permettant de vérifier les données d’un ensemble. Il est largement utilisé dans le domaine des réseaux peer-to-peer, où les participants doivent échanger des informations et les vérifier de manière indépendante.
La structure de l'arbre de Merkle est basée sur des fonctions de hachage, nous vous recommandons donc de lire d'abord l'article Qu'est-ce que le hachage ? et revenons ensuite à ce sujet.
Comment sont structurés les arbres de Merkle ?
Disons que vous téléchargez un fichier volumineux. Lorsque vous utilisez un programme open source, vous devez vérifier si le hachage du fichier téléchargé correspond au hachage publié par les développeurs. Si cela correspond, alors le fichier sur votre ordinateur est complètement identique à leur fichier.
Si les hachages sont différents, soit vous avez téléchargé un fichier malveillant déguisé en programme, soit il a été téléchargé de manière incorrecte et ne fonctionnera pas. Les problèmes de chargement peuvent également être gênants, surtout s'ils prennent beaucoup de temps. Dans ce cas, vous devrez retélécharger le fichier et espérer que tout se passe bien cette fois.
Vous vous demandez probablement : « Est-ce vraiment si compliqué ? » Heureusement, c'est là que les arbres de Merkle s'avèrent utiles, nous permettant de diviser le fichier en morceaux. Par exemple, un fichier de 50 Go peut être divisé en 100 fragments de 0,5 Go. Dans ce cas, il sera téléchargé en plusieurs parties, de la même manière que les fichiers sont téléchargés via torrent.
L’objectif principal du processus est d’obtenir un hachage unique appelé racine Merkle qui représente chaque élément de données du fichier. En utilisant la racine de Merkle, nous pouvons grandement simplifier la validation des données.
À titre d’exemple, prenons un fichier de 8 Go, divisé en 8 parties. Chaque fragment reçoit un nom de A à H, puis est passé via une fonction de hachage pour produire 8 hachages différents.
Chacun des huit fragments est passé via une fonction de hachage pour générer son hachage.
Voilà, nous avons réglé ce problème. Nous avons obtenu le hachage de tous les fragments, ce qui signifie que nous pouvons le comparer avec l'original et découvrir lequel est défectueux, n'est-ce pas ? C'est possible, mais ce serait extrêmement inefficace. Notre fichier ne contient que huit fragments, mais s'il y en avait des milliers, les hacheriez-vous tous et compareriez-vous les résultats ?
Peu probable. Au lieu de cela, vous devez prendre chaque paire de hachages, les concaténer et les hacher ensemble. Nous hachons donc hA + hB, hC + hD, hE + hF et hG + hH et obtenons quatre hachages. Ensuite, nous effectuons un autre cycle de hachage afin qu'il y ait deux hachages. Enfin, nous hachons la paire restante et obtenons le hachage principal - la racine Merkle (ou hachage racine).
La structure ressemble à un arbre inversé. Dans la rangée du bas se trouvent les « feuilles » qui vont dans les nœuds, qui vont dans la racine.
Nous avons donc une racine Merkle représentant le fichier téléchargé. Nous pouvons maintenant comparer le hachage racine avec le hachage du créateur d'origine. S'ils correspondent, alors tout va bien ! Si les hachages sont différents, cela signifie que les données ont été modifiées, c'est-à-dire qu'un ou plusieurs fragments ont créé un hachage différent. Ainsi, toute modification des données produira une racine de Merkle complètement différente.
Heureusement, nous pouvons facilement trouver le fragment incorrect. Disons que c'est lui. Pour commencer, demandez les deux derniers hachages qui ont créé la racine Merkle (hABCD et hEFGH). Votre valeur hABCD sera la même que l'originale car il n'y a aucune erreur dans ce segment, mais hEFGH sera différent, c'est donc celui que vous devez vérifier. Ensuite, nous demandons hEF et hGH et les comparons avec les nôtres. Étant donné que l'hGH correspond, nous avons besoin de hEF. Enfin, nous comparons les hachages hE et hF. Nous avons donc découvert que le mauvais fragment est hE, ce qui signifie que nous devons le retélécharger.
Pour résumer, un arbre Merkle est créé en divisant les données en plusieurs parties, qui sont ensuite hachées plusieurs fois pour former la racine Merkle. Ce système permet de vérifier facilement si tout est correct avec chaque donnée. Dans la section suivante, nous examinerons d’autres utilisations possibles.
Vous vous demandez comment démarrer avec les crypto-monnaies ? Achetez du Bitcoin sur Binance !
Pourquoi les racines Merkle sont-elles utilisées dans Bitcoin ?
Les arbres de Merkle ont de nombreux cas d’utilisation, mais nous nous intéressons actuellement à leur application dans la blockchain. Les arbres Merkle sont essentiels pour travailler avec Bitcoin et de nombreuses autres crypto-monnaies, font partie intégrante de chaque bloc et se trouvent dans les en-têtes de bloc. Pour obtenir les feuilles de l'arbre, nous utilisons le hachage de chaque transaction (TXID) incluse dans le bloc.
Dans ce cas, la racine de Merkle sert à plusieurs fins. Ensuite, nous examinerons leur application dans l’extraction de crypto-monnaie et la vérification des transactions.
Exploitation minière
Un bloc de bitcoins se compose de deux parties. La première partie est l'en-tête du bloc, un segment de taille fixe contenant des métadonnées pour le bloc. La deuxième partie est une liste de transactions, dont la taille est généralement beaucoup plus grande que l'en-tête, mais peut varier.
Les mineurs doivent hacher les données plusieurs fois pour obtenir un résultat qui répond à certaines conditions et extraire un bloc valide. Il peut falloir des milliards de tentatives pour le trouver, car les mineurs doivent modifier le nombre aléatoire dans l'en-tête du bloc (nonce) pour obtenir un nouveau résultat, mais la majeure partie du bloc restera la même. Il pourrait y avoir des milliers de transactions dans un bloc, et elles devraient toutes être hachées à chaque fois.
La racine de Merkle rend ce processus beaucoup plus facile. Pendant l'exploitation minière, toutes les transactions requises sont organisées dans un arbre Merkle. Le hachage racine (32 octets) est placé dans l'en-tête du bloc, après quoi seul l'en-tête du bloc est haché, et non le bloc entier.
Cette méthode est protégée contre tout accès non autorisé et permet la sommation efficace de toutes les transactions d'un bloc dans un format compact. Cependant, il est impossible de trouver un en-tête de bloc valide, puis de modifier la liste des transactions, car cela modifierait la racine Merkle. Lorsqu'un bloc est envoyé à d'autres nœuds, ils calculent la racine à partir de la liste des transactions. Si elle ne correspond pas à la racine dans l'en-tête, le bloc est rejeté.
Vérification
Examinons une autre propriété utile des racines de Merkle, qui concerne les nœuds légers (qui ne contiennent pas une copie complète de la blockchain). Si vous exécutez un nœud sur un périphérique aux ressources limitées, vous n’aurez peut-être pas besoin de télécharger et de hacher toutes les transactions d’un bloc. Au lieu de cela, vous pouvez simplement demander à un nœud complet une preuve Merkle, c'est-à-dire une preuve que votre transaction se trouve dans un bloc particulier. Cette méthode a été décrite en détail par Satoshi Nakamoto dans le livre blanc Bitcoin et est souvent appelée vérification simplifiée des paiements (SPV).
Seuls les hachages rouges sont nécessaires pour vérifier hD.
Supposons que nous ayons besoin d’informations sur une transaction dont le TXID est hD. Étant donné hC, nous pouvons calculer hCD. Nous avons alors besoin de hAB pour calculer hABCD. Enfin, hEFGH peut être utilisé pour vérifier si la racine Merkle résultante correspond à la racine dans l'en-tête du bloc. Si tel est le cas, cela prouve que la transaction a été incluse dans le bloc, car il est presque impossible de créer le même hachage avec des données différentes.
Dans l'exemple ci-dessus, nous n'avons haché que trois fois, alors que sans preuve Merkle, nous aurions dû hacher sept fois. Étant donné que les blocs peuvent contenir des milliers de transactions, l’utilisation des preuves Merkle permet d’économiser beaucoup de temps et de ressources informatiques.
CV
Les arbres de Merkle ont prouvé leur efficacité dans la technologie informatique. Ils sont incroyablement utiles dans les blockchains et permettent une vérification facile des informations dans les systèmes distribués sans encombrer le réseau avec des données inutiles.
Sans les arbres de Merkle (et les racines de Merkle), les blocs de Bitcoin et d’autres crypto-monnaies seraient très volumineux. Bien qu'il puisse y avoir des problèmes de confidentialité et de sécurité avec les nœuds légers, les preuves Merkle permettent de savoir à un coût minimal si des transactions ont été incluses dans un bloc.