Merkle tree

A Merkle tree (hash tree) is a binary tree in which each leaf is the hash of a data block and each internal node is the hash of its two children. The single root hash therefore commits to the entire data set: changing any block changes the root. Ralph Merkle introduced the construction in 1979 (A Certified Digital Signature).

#Compact proofs

Membership of one leaf is proven with an authentication path of sibling hashes from leaf to root, about log2(n) hashes for n leaves. A verifier holding only the 32-byte root can check the proof, so the root works as a constant-size commitment to arbitrarily many items.

#Role in signatures and blockchains

Hash-based signatures use Merkle trees to bundle many one-time signature keys under a single root public key; XMSS (RFC 8391) and SLH-DSA are built this way and rely only on cryptographic hash function security. Blockchains use the same idea: each Bitcoin block header commits to all transactions in the block through a Merkle root, which enables lightweight payment verification (Bitcoin whitepaper); see is Bitcoin quantum safe? for the quantum-security context.