Merkle Tree
A Merkle tree has data hashes at its leaves and hashes of children at internal nodes, enabling efficient integrity verification of large data; it is used in Git and blockchains.
Purpose
To make integrity verification of large-scale data efficient and localizable to specific data blocks.
Mechanism
Leaves hold the hashes of data blocks H(d_i). Internal nodes hash the concatenation of their children, H(left||right). The root hash represents the whole. Verifying one block requires only the O(log n) sibling hashes along the path from root to leaf (a Merkle proof). Any change to a data block changes the root hash.
Use cases
- Git object tree verification
- Blockchain transaction verification
- IPFS content addressing
- Distributed storage consistency
Examples
- Input
4 data blocks → a 2-level Merkle treeOutputThe root hash represents all of themO(log n) verification
Common errors
- Weak hashes enable collision forgery
- Use a secure hash such as SHA-256
Related terms
Bloom Filter
A Bloom filter approximates set membership with k hash functions and a bit array, offering space efficiency at the cost of a false-positive rate. GLOSSARY
Consistent Hashing
Consistent hashing remaps only 1/n of the keys when nodes are added or removed, minimizing redistribution; it is used in distributed caching and sharding. GLOSSARY
SHA-256
SHA-256 is the 256-bit-output member of the SHA-2 family, widely used in TLS, blockchains, and cryptographic applications, with no known practical attacks. GLOSSARY