Arbre de Merkle

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Un arbre de Merkle binaire.

En informatique et en cryptographie, un arbre de Merkle ou arbre de hachage est une structure de données contenant un résumé d'information d'un volume de données, généralement grand (comme un fichier).

Les arbres de hachage ont été inventés par Ralph Merkle en 1979[1].

Fonctionnement[modifier | modifier le code]

Le principe d'un arbre de hachage consiste à décomposer les données d'entrée en un ensemble de blocs de tailles identiques. Ces blocs sont les feuilles de l'arbre. Ils sont généralement complétés avec des valeurs neutres, comme des zéros, de façon à obtenir des blocs de la taille souhaitée.

Les nœuds de niveau supérieur sont ensuite obtenus en compressant les nœuds du niveau courant à l'aide d'une fonction de hachage/compression jusqu'à n'obtenir qu'un nœud : la racine.

Utilisations[modifier | modifier le code]

Actuellement, les arbres de hachage sont très utilisés dans les réseaux pair à pair, car ils permettent de vérifier l'intégrité d'une partie d'un fichier. En effet, il suffit alors de connaître le bon nœud se situant à la hauteur nécessaire dans l'arbre, sans nécessairement devoir posséder tout le fichier.

Ils sont également très utilisés dans les fonctions de hachage cryptographique, comme MD6, car ils sont intrinsèquement parallélisable, et permettent donc à ces algorithmes de tirer parti du parallélisme présent dans les ordinateurs modernes.

Les arbres de Merkle sont aussi utilisés dans le système de fichiers ZFS[2], dans le protocole Google Wave ou dans le système de monnaie virtuelle bitcoin.

Références[modifier | modifier le code]

  1. R. C. Merkle, A digital signature based on a conventional encryption function, Crypto '87
  2. Jeff Bonwick's Blog ZFS End-to-End Data Integrity