Symptom

A client has a 4 GB file that it downloaded from an untrusted mirror. You publish a SHA-256 hash so it can verify the file. It downloads, hashes, compares, and the hashes differ.

Now what? One byte is wrong somewhere in four billion, and the only remedy your scheme offers is to download the whole file again from a different mirror and hope. The hash told you that something is wrong and nothing about where.

Turn it around and the problem gets worse. A client wants to check one 1 KB record out of a billion. To verify it against your published hash it must download all billion records. The verification cost is proportional to the size of the whole set, no matter how small the thing being verified is, and that is the property that makes a flat hash useless for anything incremental.

Statement

Split the data into $n$ leaves. Hash each leaf. Hash each adjacent pair of hashes to form the level above. Repeat until one hash remains: the root, or Merkle root.

Membership proof. To prove leaf $i$ is in the tree, supply the sibling hash at each level from the leaf to the root — the authentication path. The verifier recomputes upward and compares against the root. The proof is $\lceil \log_2 n \rceil$ hashes and verification is $\lceil \log_2 n \rceil$ hash evaluations.

Security. Forging a proof for a leaf not in the tree requires finding a hash collision. With a $b$-bit hash, the birthday bound (T074) puts that at $2^{b/2}$ work.

The numbers are what make it feel unreasonable. Over a billion leaves the tree is 30 levels deep, so a proof is 30 SHA-256 hashes: 960 bytes, and 30 hash computations to verify. A million leaves gives 20 hashes, 640 bytes. The verifier never sees the other billion records and never needs to.

Argument

Why collision resistance is exactly the right assumption, and where the digest width comes from. Suppose an adversary produces a valid authentication path for a leaf $L’$ that is not in the tree, against an honest root $R$. Verification recomputes a chain of hashes from $L’$ up to $R$.

Compare that chain against the honest tree’s chain to the same root. They end at the same value $R$ and begin at different values, so somewhere along the way two different inputs produce the same output. That is a collision, extracted directly from the forgery. So forging is at least as hard as finding a collision in the hash.

This is why T074 sets the parameters rather than intuition. Collisions arrive at $\sqrt{N}$, not $N$: a 128-bit hash offers $2^{64}$ collision work, which is reachable, and 160-bit SHA-1 offers $2^{80}$, which was reachable enough that SHA-1 collisions were demonstrated in 2017 for about $2^{63}$ actual work. SHA-256 is used everywhere in this space because $2^{128}$ is the target and that requires 256 bits of output. The width is a consequence, not a convention.

The second-preimage subtlety that real designs get wrong. A naive tree has an attack. If internal nodes and leaves are hashed the same way, an adversary can present an internal node as if it were a leaf and produce a shorter valid path, because the verifier cannot tell what level a hash came from. Related tricks exploit trees whose leaf count is not a power of two, where duplicated final nodes make two different leaf sets produce the same root.

Bitcoin has exactly this bug (CVE-2012-2459), arising from its odd-node duplication rule, and it was patched by rejecting blocks with duplicate transactions rather than by fixing the tree. The general fix is domain separation: prefix leaf hashes with 0x00 and internal hashes with 0x01, which Certificate Transparency does by specification in RFC 6962. This is a good example of a construction being sound in the abstract and unsound as deployed.

Where the structure actually runs, which is nearly everywhere.

Git is a Merkle DAG. A blob’s name is its content hash, a tree object names blobs and subtrees by hash, a commit names its tree and its parents by hash. A commit hash therefore authenticates the entire history reachable from it, which is why rewriting any past commit changes every hash after it, and why git fsck can detect corruption anywhere in the object store. The property everyone uses daily — that a commit SHA identifies an exact tree state — is a Merkle root property.

Certificate Transparency logs every issued TLS certificate into an append-only Merkle tree. It uses two proof types, and the second one is the interesting one: consistency proofs show that the tree at size $m$ is a prefix of the tree at size $n$, in $O(\log n)$ hashes, so a monitor can verify the log never removed or altered an entry without downloading it. Membership proves inclusion; consistency proves append-only. Chrome requires CT for all publicly-trusted certificates, so this runs on essentially every HTTPS connection.

Blockchains put the transaction Merkle root in the block header. A light client holding only headers can verify that a transaction is in a block with a $\log n$ proof, which is what makes Simplified Payment Verification possible without storing hundreds of gigabytes.

Distributed databases use them for anti-entropy. Cassandra and DynamoDB compare Merkle trees over key ranges between replicas; matching roots mean the ranges are identical and no data moves, and mismatched roots let the comparison descend only into differing subtrees. The repair cost becomes proportional to the amount of divergence rather than to the amount of data, which is the solution to the symptom this post opened with.

IPFS, ZFS, and Btrfs are the same idea for content addressing and integrity: ZFS hashes every block and stores the hash in the parent block pointer up to a signed uberblock, which is how it detects silent disk corruption that RAID happily propagates.

Why the tree and not a list of hashes. Publishing one hash per record also allows verifying a single record. But then the authenticator is $n$ hashes — 32 GB for a billion records — and it must be republished on every change. The tree compresses the authenticator to one hash while keeping per-item proofs small, and an update touches only the $\log n$ nodes on one path. That combination is the entire contribution.

Forbids

Proving non-membership. A plain Merkle tree proves an item is present. It cannot prove absence. Sorted Merkle trees or sparse Merkle trees are required, where you prove membership of the two adjacent items that bracket the gap, and this is why Ethereum uses a Patricia trie rather than a plain tree.

Forging a proof without a collision. The reduction is tight, and it is the whole security argument.

Hiding the data from the proof. An authentication path reveals sibling hashes, and sibling hashes may be brute-forceable if leaves have low entropy. Leaves must be salted if privacy matters, and this has bitten real designs where leaves were short identifiers.

Verifying with a compromised root. The root must arrive over an authenticated channel. The tree moves trust; it does not create it.

Does not forbid

It does not require a balanced or power-of-two tree, and this is the misreading that leads people to pad. Unbalanced trees are fine and are what real systems build. Certificate Transparency’s trees are of arbitrary size and use a well-defined split rule, and Git’s trees mirror the directory structure with whatever shape the repository has.

It does not require rebuilding on update. Changing one leaf changes only the $\log n$ hashes on its path. This is what makes ZFS’s per-block checksums affordable on every write.

It does not require the leaves be ordered or a sequence. The tree authenticates a set with a fixed arrangement. Ordering is only needed for non-membership proofs.

It does not require a huge dataset to be worth it. Git uses it for repositories of a few files, because the benefit is content addressing and integrity, not just proof size.

It does not make the data available. A valid root proves what the data is if you get it. It does not guarantee anyone will give it to you, which is the data availability problem and is a genuinely separate and unsolved-by-Merkle issue in blockchain design.

Boundary

  • Security is exactly the hash’s collision resistance. SHA-1-based trees are broken; the ceiling is the birthday bound at $2^{b/2}$.
  • Domain separation is mandatory. Without distinguishing leaf and internal hashes, second-preimage attacks apply, as Bitcoin demonstrated.
  • Membership only. Absence needs a sorted or sparse variant.
  • Proofs are $\log n$, not constant. Cryptographic accumulators and vector commitments give constant-size proofs, at the cost of trusted setup or much heavier mathematics.
  • The root’s authenticity is assumed. Distribution of the root is a separate problem, usually solved with signatures or gossip.

The move to carry: a hash authenticates a blob and forces all-or-nothing verification, while a tree of hashes authenticates the same blob and lets you verify any piece of it in logarithmic work. That one structural change is why the same data structure appears independently in version control, TLS infrastructure, filesystems, replicated databases, and every blockchain.