Merkle Tree

Un arbre de Merkle place les hachés des données aux feuilles et les hachés des enfants aux nœuds internes, permettant une vérification d'intégrité efficace de grandes masses de données ; utilisé dans Git et les blockchains.

Objectif

Rendre efficace la vérification d'intégrité de données à grande échelle et localisable sur des blocs de données précis.

Mécanisme

Les feuilles portent les hachés des blocs H(d_i). Les nœuds internes hachent la concaténation de leurs enfants, H(left||right). Le haché racine représente l'ensemble. Vérifier un bloc ne requiert que les O(log n) hachés frères le long du chemin racine-feuille (une preuve de Merkle). Tout changement d'un bloc modifie le haché racine.

Cas d’usage

Vérification de l'arbre d'objets Git
Vérification des transactions blockchain
Adressage de contenu IPFS
Cohérence du stockage distribué

Exemples

entrée

4 data blocks → a 2-level Merkle tree

Output

The root hash represents all of them

O(log n) verification

Erreurs courantes

Weak hashes enable collision forgery: Use a secure hash such as SHA-256

Termes associés

Un filtre de Bloom approxime l'appartenance à un ensemble avec k fonctions de hachage et un tableau de bits, offrant une efficacité spatiale au prix d'un taux de faux positifs.

Consistent Hashing

Le hachage cohérent remappe seulement 1/n des clés lors de l'ajout ou du retrait de nœuds, minimisant la redistribution ; il est utilisé dans le cache distribué et le sharding.

SHA-256 est le membre de la famille SHA-2 à sortie de 256 bits, très utilisé dans TLS, les blockchains et les applications cryptographiques, sans attaque pratique connue.

Outils associés

Calculatrice de hash

Compute MD5, SHA-1, SHA-256, or SHA-512 hashes with hex or Base64 output. Gratuit, privé et 100% côté client.

References