Merkle trees

How hash trees let systems compare and verify large datasets cheaply: structure and root hashes, finding differences between replicas, proofs of inclusion, uses in databases' anti-entropy, file sync, Git, certificate transparency, blockchains and audit logs, and design choices for building them.

Reading is half of it. See this used in a real interview: walk through Design a Distributed Key-Value Store →

How do two servers with a billion keys each find the handful that differ, without sending a billion keys over the network? How can a client be sure a file chunk or a log entry has not been tampered with, without downloading everything? Merkle trees answer both with hashes arranged in a tree. They appear in key-value store designs (anti-entropy), file sync, version control, transparency logs and blockchains, and naming them at the right moment is a strong signal.

The structure

1. Split the data into blocks (key ranges, file chunks, log entries) and hash each one. These hashes are the leaves.
2. Hash pairs (or groups) of child hashes together to form parent nodes.
3. Repeat until one hash remains: the root.

The root summarises everything below it. Change one byte anywhere and the leaf hash changes, which changes every hash on the path to the root.

Finding differences

Two replicas each build a Merkle tree over the same key ranges:

• Compare roots. Equal roots mean the data is (with overwhelming probability) identical: done, with one hash exchanged.
• If they differ, compare the children and descend only into subtrees whose hashes differ.
• At the leaves, exchange only the differing ranges.

The work is proportional to the number of differences times the tree depth, not to the dataset size. Cassandra and Dynamo-style databases use this for anti-entropy repair between replicas. See quorums and leaderless replication and Design a Key-Value Store.

Proofs of inclusion

To prove a block is part of a dataset with a known root, provide the block plus the sibling hashes along its path to the root (a Merkle proof, about log₂ N hashes). The verifier recomputes up to the root and compares. A client can verify one chunk of a huge file, or one entry in a giant log, with a few hundred bytes of proof.

Where they are used

• File sync and backup: compare directory trees or chunk lists to sync only what changed. See delta sync and Design Dropbox.
• Git: commits, trees and blobs are named by hashes of their content; a commit hash covers the whole project state.
• Content-addressed storage and IPFS: large files are Merkle DAGs of chunks; identical chunks are stored once. See hashing and encoding.
• Certificate transparency: append-only public logs of TLS certificates, with proofs that a certificate is included and that the log only grew. The same idea makes audit logs tamper-evident.
• Blockchains: block headers include a Merkle root of transactions, so light clients verify a transaction with a short proof.
• Distributed databases and object stores: verifying replicas and detecting silent corruption during scrubbing. See distributed file systems.

Design choices

• What the leaves cover: fixed key ranges (stable boundaries, easy to compare between replicas) versus content-defined chunks (stable under insertions in files).
• Fan-out: binary trees give the smallest proofs; wider trees are shallower with fewer levels to compare.
• Updating: when data changes, recompute hashes along the path to the root (log N work). Databases often rebuild trees periodically or maintain them incrementally per range.
• Hash function: a cryptographic hash such as SHA-256 or BLAKE3 when tampering matters; faster hashes are acceptable for pure replica comparison in a trusted environment.
• Consistency of snapshots: compare trees built over the same logical snapshot, or concurrent writes cause spurious differences (which are harmless but waste repair work).

Append-only logs

For logs that only grow, Merkle trees support two proofs: inclusion (this entry is in the log) and consistency (today's log extends yesterday's without rewriting history). Publishing the root periodically lets anyone detect if an operator edits past entries.

In the interview

For Design a Key-Value Store: "Each node maintains a Merkle tree per token range; background anti-entropy compares trees between replicas and streams only the differing ranges, which keeps repair cheap even with billions of keys." For Design Dropbox: "Files are chunked and hashed; the client compares chunk hashes (or a tree of them) with the server and uploads only new chunks." For a web crawler, content hashes per page detect changes without full comparisons.

Checklist

• Leaves are hashes of blocks; parents hash their children; the root summarises all.
• Compare roots, then descend only into differing subtrees.
• Inclusion proofs of about log N hashes.
• Uses: anti-entropy, sync, Git, transparency logs, blockchains, scrubbing.
• Choose leaf boundaries, fan-out, hash function and update strategy deliberately.