Arbre de Merkle

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
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 est de pouvoir vérifier l'intégrité d'un ensemble de données sans les avoir nécessairement toutes au moment de la vérification.

Construction de l'arbre

Dans la figure, l'ensemble de données est représenté par les blocks L1 à L4. L'arbre est constitué par un ensemble de valeurs de hash interdépendantes. Les feuilles de l'arbre sont les valeurs de hash de chacun des blocks de données initiales. Dans un arbre de Merkle binaire, ces hashs sont alors concaténés deux à deux pour pouvoir calculer un nouveau hash parent. Ainsi de suite jusqu'au sommet de l'arbre ou on obtient un hash-sommet. Si le nombre de blocks, ou les hashs intermédiaires ne forment pas un arbre binaire, on complète la base avec suffisamment de blocks vides.

Exploitation

Pour garantir l'intégrité d'un block téléchargé par rapport à l'ensemble des données, il suffit de posséder les hashs des frères, les hashs des oncles et le hash-sommet. De plus, seul le hash-sommet doit être récupéré de manière sure pour garantir l'intégrité de l'ensemble des données représenté par l'arbre.

Par exemple, si on veut vérifier l'intégrité du block L2, il suffit d'avoir récupéré le hash0-0 (son frère), le hash1 (son oncle) et le hash-sommet.


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.

La fonction de hachage cryptographique MD6 utilise un arbre de Merkle, ce qui permet 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