Table des matières
Qu'est-ce qu'un arbre Merkle ?
Comment fonctionne un arbre Merkle ?
Pourquoi la racine de Merkel est-elle utilisée dans Bitcoin ?
Exploitation minière
vérifier
Résumer
Qu'est-ce qu'un arbre Merkle ?
Au début des années 1980, Ralph Merkle, un informaticien bien connu dans le domaine de la cryptographie à clé publique, a proposé le concept d'arbre de Merkle.
La structure arborescente Merkle peut vérifier efficacement l'intégrité de l'ensemble de données et est plus efficace dans les réseaux peer-to-peer qui exigent que les participants partagent et vérifient les informations de manière indépendante.
Les fonctions de hachage sont au cœur de l'arborescence Merkle. Par conséquent, nous vous recommandons de comprendre ce qu’est le hachage avant de poursuivre cet article.
Comment fonctionnent les arbres de Merkle ?
Supposons que vous souhaitiez télécharger un fichier volumineux. Lors des téléchargements de logiciels open source, il est souvent nécessaire de vérifier si le hachage du fichier téléchargé correspond à celui rendu public par le développeur. S'ils correspondent, les deux fichiers sont identiques.
Si les hachages ne correspondent pas, vous avez des problèmes. Soit vous avez téléchargé un fichier malveillant déguisé en logiciel, soit vous l'avez téléchargé de manière incorrecte, et le résultat final est que le fichier est inutilisable. Si le téléchargement n'est pas correct, vous vous sentirez certainement ennuyé, après tout, vous avez passé beaucoup de temps à attendre que le fichier soit téléchargé. Maintenant, nous devons tout recommencer et espérer que le même problème ne se reproduira plus.
Avez-vous déjà réfléchi à la possibilité d’un moyen plus simple de résoudre ce problème ? C’est là qu’interviennent les arbres Merkle. Les arbres Merkle peuvent diviser les fichiers en plusieurs blocs de données. Par exemple, un fichier de 50 Go peut être divisé en 100 morceaux, chacun d’une taille de 0,5 Go. Ensuite, vous pourrez les télécharger un par un. Voici comment fonctionnent les fichiers torrent.
La source du fichier à ce stade est une valeur de hachage, appelée racine Merkle. Cette valeur de hachage unique représente tous les blocs de données qui composent le fichier. De plus, les racines Merkle peuvent rendre la vérification des données beaucoup plus facile.
Pour faciliter la compréhension, donnons un exemple. Ci-dessous, un fichier de 8 Go est divisé en huit parties, et chaque partie est nommée de A à H. Chaque fragment est ensuite placé dans une fonction de hachage, ce qui génère huit valeurs de hachage différentes.
Les valeurs de hachage des huit fragments sont calculées via la fonction de hachage.
J’espère que les exemples ci-dessus sont suffisamment clairs. Nous avons maintenant les valeurs de hachage de tous les fragments. Si l'une d'entre elles est erronée, pouvons-nous trouver le problème en la comparant avec le fichier source ? Peut-être, mais cela reste extrêmement inefficace. Si un fichier contient des milliers de fragments, devons-nous effectuer des opérations de hachage sur tous les fragments, puis comparer soigneusement les résultats ?
inutile. Nous devons simplement combiner une paire de valeurs de hachage, puis effectuer une opération de hachage de fusion. Autrement dit, nous hachons hA + hB, hC + hD, hE + hF et hG + hH. Cela donne quatre valeurs de hachage. Nous passons ensuite au prochain tour de hachage de fusion jusqu’à ce que nous obtenions deux valeurs de hachage. Ces deux valeurs de hachage sont ensuite combinées pour produire la valeur de hachage principale, également connue sous le nom de racine de Merkle (également appelée valeur de hachage racine).
La structure ressemble à un arbre à l’envers. La rangée inférieure de feuilles se combine pour former des nœuds et enfin des racines.
Nous avons maintenant la racine Merkle représentant le fichier téléchargé. Comparez la valeur de hachage racine à la valeur du fichier source, et si elles correspondent, tout le monde est content ! Une fois que les valeurs de hachage sont différentes, cela prouve que les données ont été falsifiées. En d’autres termes, un ou plusieurs fragments génèrent des valeurs de hachage différentes. Par conséquent, même la plus petite modification des données changera complètement la racine de Merkle.
Heureusement, il est également facile de vérifier les mauvais fragments. Supposons que l’erreur soit hE. Tout d’abord, nous demandons aux autres deux valeurs de hachage (hABCD et hEFGH) pour générer la racine de Merkle. Nos valeurs hABCD doivent correspondre à celles des autres, prouvant que le sous-arbre ne comporte aucune erreur. Si le hEFGH ne correspond pas, nous pouvons corriger l'erreur à partir d'ici. Demandez ensuite à d'autres leurs valeurs de hachage hEF et hGH et comparez-les avec les vôtres. Si hGH est bon, alors hEF est le coupable. Enfin, nous comparons les valeurs de hachage de hE et hF. Une fois que nous avons trouvé que la source de l'erreur est hE, nous pouvons retélécharger le bloc de données.
Pour résumer, la fonction de l’arbre de Merkle est de diviser les données en plusieurs parties, puis de hacher les données à plusieurs reprises pour former une racine de Merkle, qui peut vérifier efficacement où les données erronées sont apparues. Dans la section suivante, nous examinerons d’autres applications intéressantes.
Vous souhaitez démarrer votre voyage dans la crypto-monnaie ? Allez sur Binance et achetez du Bitcoin maintenant !
Pourquoi Merkle Root est-il utilisé dans Bitcoin ?
Il existe de nombreux cas d’utilisation pour les arbres de Merkle, mais cet article se concentre sur le rôle important qu’ils jouent dans la blockchain. Bitcoin et de nombreuses crypto-monnaies sont indissociables des arbres de Merkle. L'arbre de Merkle est un composant de chaque bloc et est généralement situé dans l'en-tête du bloc. Grâce à la valeur de hachage de transaction (TXID) de chaque transaction dans le bloc, nous pouvons obtenir les feuilles.
Dans ce contexte, la racine de Merkle sert à plusieurs fins. Examinons l’application de Merkle Root 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 l'en-tête du bloc, qui a une taille fixe et contient des métadonnées de bloc. La deuxième partie est le corps du bloc, qui peut être de taille variable mais est généralement beaucoup plus grand que l'en-tête du bloc et contient une liste de transactions.
Les mineurs doivent hacher les données à plusieurs reprises jusqu'à ce qu'ils produisent un résultat qui répond à des conditions spécifiques afin d'exploiter un bloc valide. Pour obtenir le bon résultat, il leur faut des milliards de tentatives. À chaque tentative, les mineurs modifient le nombre aléatoire dans l'en-tête du bloc, également appelé valeur Nonce, pour générer des résultats différents. Cependant, le reste du bloc reste le même, chacune des milliers de transactions devant encore être hachées.
La racine de Merkle simplifie grandement ce processus. Lorsque l'exploitation minière démarre, toutes les transactions sont mises en file d'attente, empaquetées et construites dans un arbre Merkle, et la valeur de hachage racine 32 bits générée est placée dans l'en-tête du bloc. Ensuite, il n’est pas nécessaire de hacher le bloc entier, uniquement l’en-tête du bloc.
Cette approche est efficace car elle empêche la falsification des données et permet à toutes les transactions d’un bloc d’être efficacement agrégées sous une forme compacte. La liste des transactions d'un en-tête de bloc valide ne peut pas être modifiée, sinon la racine Merkle changera. Une fois le bloc envoyé à d’autres nœuds, le hachage racine est calculé à partir de la liste des transactions. Si elle ne correspond pas à la valeur dans l'en-tête du bloc, le bloc peut être rejeté.
vérifier
Il existe une autre propriété intéressante de la racine Merkle que nous pouvons utiliser, qui concerne son utilisation avec des clients légers (nœuds qui ne conservent pas une copie complète de la blockchain). Si vous exécutez un nœud sur une machine aux ressources limitées, vous ne souhaitez certainement pas télécharger et hacher toutes les transactions d’un bloc. Au lieu de cela, vous demandez simplement une preuve Merkle, qui est une preuve fournie par un nœud complet qui prouve qu'une transaction a été incluse dans un bloc spécifique. Cette preuve, mieux connue sous le nom de « Vérification de paiement simplifiée » ou SPV, a été détaillée par Satoshi Nakamoto dans le livre blanc Bitcoin.
Pour vérifier hD, vérifiez simplement la valeur de hachage en rouge.
Supposons que nous souhaitons obtenir des informations sur la transaction avec TXID hD. Si hC est connu, hCD peut être calculé. Ensuite, à partir de hAB, hABCD peut être calculé. Enfin, en se référant à hEFGH, nous pouvons vérifier si la racine de Merkle calculée est cohérente avec la valeur de hachage racine dans l'en-tête du bloc. S'ils correspondent, cela prouve que la transaction a été incluse dans le bloc, car il est presque impossible de générer la même valeur de hachage en utilisant des données différentes.
Dans l’exemple ci-dessus, nous n’avons effectué que trois opérations de hachage. Sans la preuve de Merkel, il en aurait fallu sept. Les blocs d’aujourd’hui contiennent des milliers de transactions, et les preuves Merkle nous font gagner beaucoup de temps et de puissance de calcul.
Résumer
Les arbres de Merkle se sont avérés utiles dans les applications informatiques et, comme nous l’avons vu, ils sont également précieux dans les blockchains. L'arbre de Merkle rend la vérification des informations dans les systèmes distribués plus pratique et évite la congestion des données redondantes dans le réseau.
Sans les arbres et les racines de Merkle, Bitcoin et d’autres blocs de crypto-monnaie ne seraient pas aussi compacts qu’ils le sont aujourd’hui. Alors que les clients légers manquent d'avantages en termes de confidentialité et de sécurité, les preuves Merkle permettent aux utilisateurs de vérifier que les transactions sont incluses dans des blocs avec des frais minimes.