Hash Tree
Un arbre de hachage (arbre de Merkle) organise les hachés de blocs de données en un arbre binaire : les feuilles sont les hachés des blocs, les nœuds internes hachent la concaténation des hachés enfants, et la racine est le condensé global.
Objectif
Vérifier efficacement l'intégrité de grandes masses de données — seuls O(log n) hachés frères suffisent pour vérifier une feuille, sans recalculer tout l'arbre.
Mécanisme
Feuille h_i=H(data_i), nœud interne h=H(h_left || h_right), la racine h_root est le condensé global. Vérifier la feuille i requiert les hachés frères de chaque niveau le long du chemin feuille-racine (le chemin d'authentification).
Cas d’usage
- Arbres de commits Git
- Vérification de transactions blockchain
- Intégrité de fichiers P2P (BitTorrent)