L'arbre de hachage de Merkle prouve qu'un enregistrement figure dans un fichier géant avec une poignée de hachages

Prouver qu'un enregistrement fait partie d'un grand jeu de données signifiait généralement envoyer le jeu de données. C'est peu pratique pour une sauvegarde, un fichier de transactions ou un cache web.

La thèse de 1979 et l'article de 1989 de Merkle décrivent un arbre dans lequel chaque bloc est haché et les hachages sont appariés jusqu'à ce qu'il ne reste qu'une racine. Vérifier un membre nécessite les log-n hachages situés sur le chemin, et non le fichier.

L'arbre transforme un test d'appartenance en un test d'égalité sur la racine, et une modification n'importe où se manifeste par un chemin modifié. C'est ainsi qu'une structure de données entière peut être attestée sans que chaque octet soit vu.

Engager les feuilles en hachant par paires jusqu'à une racine unique

La taille de la preuve est logarithmique, de sorte que la vérification reste peu coûteuse sur les plus grands jeux de données.

La racine engage l'ensemble du jeu de données, de sorte que toute altération est détectée.

Un vérificateur n'a besoin que de la racine et d'un court chemin, et non de faire confiance au serveur.

Il s'agit d'une chaîne de hachages à sens unique, de sorte qu'aucune information sur les données n'est divulguée.

Pour prouver un fait concernant un ensemble immense, ne pas envoyer l'ensemble. Le réduire à un seul condensé, puis ne fournir que le court chemin qui relie l'affirmation unique à ce condensé.

Les arbres de Merkle sont fondamentaux dans Git, les chaînes de blocs de cryptomonnaies, la transparence des certificats et le stockage distribué. Ils permettent à un client de vérifier une petite pièce d'un grand stockage non authentifié en ne faisant confiance qu'à une seule racine courte.