Arbre de Merkle Merkle tree
Un arbre de hachage où chaque nœud interne est le hachage de ses enfants. Connaître la seule racine suffit à vérifier l'intégrité de tout le contenu de l'arbre. Ralph Merkle, 1979.
Il sert de base à Bitcoin (la racine de Merkle des transactions figure dans chaque bloc), à Git (le hachage d'un commit est la racine d'arbres de hachages), à IPFS (adressage par contenu), à Certificate Transparency, à BitTorrent (vérification des morceaux) et à ZFS/Btrfs (intégrité du système de fichiers). Une preuve de Merkle montre O(log n) hachages pour prouver qu'une feuille précise est incluse. Les arbres de Merkle creux et les arbres de Verkle en sont des variantes modernes. Le brevet a expiré en 2002, et l'usage s'est largement répandu depuis.