Search tools and guides ⌘K
VI · Graphs & sets

Merkle tree

Hash of hashes; tamper-evident.

1979 · Ralph Merkle · Stanford
The story

Merkle's 1979 thesis introduced a tree of hashes — leaves are data, every internal node is the hash of its children. Verifying any leaf belongs to the tree requires only the path of sibling hashes up to the root. Cryptographically tamper-evident; sub-linear proofs.

How it works

Hash each data block (leaves). Each internal node's value is the hash of its children's values. The root hash summarises the entire tree. Inclusion proof: log₂(n) hashes (the siblings on the path).

Where it lives

Bitcoin and Ethereum (transaction trees). Git (commit/tree objects). IPFS. ZFS, Btrfs (block checksums). Certificate Transparency logs. Database replication checksums.

The key insight

A Merkle root commits to gigabytes of data in 32 bytes. Bitcoin uses this so that "light" SPV wallets can verify a transaction's inclusion in a block by downloading only ~32 hashes — the full block can be tens of megabytes.

More in Graphs & sets
Adjacency list Each node, its neighbours. Disjoint Set / Union-Find Track connected components, in a forest. LSM-tree Append-only, merged in the background. DAG · directed acyclic graph Order without cycles.
Across the cabinet
VII Quad-tree / Octree Recursive 4-way / 8-way subdivision. VII BVH · bounding volume hierarchy A tree of boxes for ray tracing. VII Z-order / Hilbert curve Linearise space, preserve locality. I Array A row of equal-sized boxes. I Dynamic array (vector) An array that grows itself. I Linked list A chain you can splice. I Stack Last in, first out. I Queue First in, first out.
← All data structures