Merkle Tree Explained: Hash Trees, Inclusion Proofs and Anti-Entropy in Git, Cassandra, Dynamo-Style Stores and Certificate Transparency
A browser can check that one certificate sits inside a public log of billions of entries by downloading roughly a kilobyte. Two database replicas holding a terabyte each can find the handful of rows on which they disagree without shipping the terabyte. Both tricks rest on the same 1979 idea: the merkle tree, a tree of hashes in which every parent commits to everything beneath it.
The structure matters more in 2026 than it did five years ago. Certificate Transparency logs moved to tile-based “static” APIs, Sigstore shipped a tile-backed Rekor v2, and Git has committed to SHA-256 as the default for new repositories in Git 3.0. Each of these is a design decision about hash trees.
The thesis of this guide is simple: the hash function is the easy part; the shape of the tree decides which question it can answer. You will leave with proof-size maths, a tested Python implementation of RFC 9162 proofs, and a map of which shape fits which system.
What this covers: construction and domain separation, inclusion and consistency proofs, anti-entropy repair, Git, ZFS, IPFS, Certificate Transparency and Rekor, failure modes, and a merkle tree vs hash list comparison.
Context and Background
Ralph Merkle filed US patent 4,309,569, “Method of providing digital signatures”, on 5 September 1979; it was granted on 5 January 1982. The tree-authentication idea also appears in his 1979 Stanford PhD thesis and in the CRYPTO ’87 paper “A Digital Signature Based on a Conventional Encryption Function”. His goal was signatures built from hash functions alone: commit to many one-time public keys with a single root, then prove any one of them belongs with a short path.
That goal survived. Hash-based signature schemes such as XMSS, LMS and SPHINCS+ (standardised by NIST as SLH-DSA) are direct descendants, and they are a pillar of post-quantum cryptography. But the broader engineering legacy is the Merkle tree itself, which escaped cryptography and became a workhorse in storage and distributed systems.
Four families of systems use the Merkle tree today. Version control (Git, Mercurial) uses them to name and verify snapshots. Filesystems such as ZFS and Btrfs use them to detect silent corruption. Replicated databases descended from Amazon’s Dynamo (Cassandra, ScyllaDB, Riak) use them for anti-entropy repair. Transparency logs (Certificate Transparency, Sigstore Rekor, Go’s checksum database) use them to make append-only claims publicly auditable.
These families rarely talk to each other, and the folklore differs. Database engineers think of a Merkle tree as a diffing tool; security engineers think of it as a proof system; storage engineers think of it as a checksum hierarchy. All three are right, and the confusion between them causes real bugs, which we will catalogue later.
If you have read our guide to probabilistic data structures like Bloom filters and HyperLogLog, note the contrast. A Bloom filter answers membership approximately, with false positives, and proves nothing to a third party. A Merkle proof answers membership exactly and is verifiable by anyone who trusts only the root hash. That third-party verifiability is the property that makes transparency logs possible.
The canonical modern specification of a log-shaped Merkle tree is RFC 9162, Certificate Transparency Version 2.0, published in December 2021, which obsoletes RFC 6962 (2013). We use its definitions throughout because they are precise, widely implemented, and fix two classic pitfalls.
The Merkle Tree Reference Architecture: Construction, Proofs and Domain Separation
A Merkle tree hashes each data record into a leaf, then repeatedly hashes pairs of child hashes into parent hashes until one root remains. The root commits to every record and its position. A Merkle proof for one record is the list of sibling hashes on its path to the root: about log2(n) hashes for n records.

Figure 1: A four-leaf Merkle tree using RFC 9162 domain separation. Leaves are hashed with a 0x00 prefix and interior nodes with 0x01. To prove D3, the verifier needs only L2 and N01.
Figure 1 shows four records D0 to D3. Each leaf hash is H(0x00 || record). Each interior node is H(0x01 || left || right). The root is a single 32-byte value under SHA-256. To prove D3 is in the tree, the server sends L2 and N01; the verifier computes L3 from D3, then N23 from L2 and L3, then the root from N01 and N23, and compares.
How RFC 9162 builds the tree for any n
Many textbook Merkle tree examples assume a power-of-two number of leaves. Real logs grow one entry at a time, so they need a rule for every n. RFC 9162 defines the Merkle Tree Hash recursively: the empty tree hashes to HASH(); one leaf hashes to HASH(0x00 || d[0]); and for n greater than one, let k be the largest power of two smaller than n, then MTH(D_n) = HASH(0x01 || MTH(D[0:k]) || MTH(D[k:n])).
That split rule produces a “left-full” tree. The left subtree is always a perfect power-of-two tree, and the ragged edge lives on the right. This is not cosmetic. Once the first k entries form a perfect subtree, that subtree’s hash never changes as the log grows, which is what makes consistency proofs and cacheable tiles possible.
Contrast this with Bitcoin’s transaction tree, which pads an odd level by duplicating the last hash. As the Bitcoin Optech write-up on Merkle tree vulnerabilities explains, a block with transactions A, B, C then has the same root as A, B, C, C. That ambiguity became CVE-2012-2459, a denial-of-service via cached invalid blocks. The RFC 9162 split rule never duplicates, so no two different leaf lists share a shape-ambiguous root.
Why the 0x00 and 0x01 prefixes matter
In a Merkle tree without domain separation, an interior node and a leaf are hashed the same way. An interior node’s preimage is just 64 bytes: two child hashes concatenated. An attacker can therefore present those 64 bytes as if they were a single leaf record and produce a valid-looking proof for a “record” that was never logged. This is the classic second-preimage attack on a naive Merkle tree.
The one-byte prefixes close the hole. A leaf is always H(0x00 || x) and a node is always H(0x01 || l || r), so a node preimage can never be reinterpreted as a leaf preimage without finding a real hash collision. Bitcoin learned this the hard way too: its leaves and nodes both use double SHA-256 with no prefix, so a 64-byte transaction can masquerade as an interior node (CVE-2017-12842). Lightweight clients that check only “this root commits to my transaction” are the ones at risk.
The broader rule is that a proof must bind the leaf’s index and the tree size, not just the hash path. RFC 9162 verification takes leaf_index and tree_size as inputs and uses them to decide, at each level, whether the sibling sits on the left or right. A verifier that accepts arbitrary left/right flags lets an attacker move a leaf around the tree.
Proof size: the worked maths
In any Merkle tree, the audit path for one leaf contains at most one sibling per level. For a perfectly balanced tree of n leaves that is log2(n) hashes; for an RFC 9162 tree it is at most ceil(log2(n)).
Take a log of 1,000,000 entries. log2(1,000,000) = ln(1,000,000) / ln(2) = 13.8155 / 0.6931 ≈ 19.93, so the path holds at most 20 hashes. With SHA-256 each hash is 32 bytes, so the proof is 20 × 32 = 640 bytes. Verification costs 21 hash computations: one leaf hash plus 20 node hashes.
Now compare a flat hash list. To verify one entry against a single signed digest of a list, the verifier needs every entry hash: 1,000,000 × 32 bytes = 32,000,000 bytes, or 32 MB. The Merkle tree cuts the proof by a factor of 50,000. Grow the log to one billion entries and the tree proof rises only to 30 hashes, 960 bytes, while the hash list grows to 32 GB. That gap is the whole merkle tree vs hash list argument in one line.
| Leaves n | Max proof hashes | Proof bytes (SHA-256) | Flat hash list bytes |
|---|---|---|---|
| 1,024 | 10 | 320 | 32,768 |
| 1,000,000 | 20 | 640 | 32,000,000 |
| 1,000,000,000 | 30 | 960 | 32,000,000,000 |
The cost moves to the writer. Appending a leaf to a Merkle tree touches one hash per level, so O(log n) work, and the log operator must store or recompute interior nodes. That trade is almost always worth it, because readers vastly outnumber writers in every system we discuss.
Consistency proofs: proving the log only grew
Inclusion is half the story. A transparency log must also prove that today’s tree of n entries extends yesterday’s tree of m entries without rewriting any of the first m. RFC 9162 calls this a consistency proof: “the list of nodes in the Merkle Tree required to verify that the first m inputs D[0:m] are equal in both trees.”
The left-full shape makes this cheap. The old tree decomposes into a handful of perfect subtrees whose hashes still exist inside the new tree. The proof supplies those subtree hashes plus the right-hand siblings needed to climb to the new root. The verifier recomputes both the old root and the new root from the same list; if both match, the prefix is unchanged. Proof size is again logarithmic, on the order of log2(n) hashes.
Consistency is what turns a signed root into an accountable commitment. A log that shows one history to Alice and another to Bob (“split view”) cannot produce a consistency proof linking both views. Monitors and witnesses that compare roots catch it.
Walk-Through: A Tested Python Implementation of Merkle Proofs
The code below implements a Merkle tree per RFC 9162: the Merkle Tree Hash, inclusion proofs, and consistency proofs, including the verification algorithms from sections 2.1.3.2 and 2.1.4.2. It is deliberately recursive and unoptimised so it reads like the spec. We tested it exhaustively for every tree size from 1 to 39, every leaf index, and every older size m.
import hashlib
def H(b: bytes) -> bytes:
return hashlib.sha256(b).digest()
def leaf_hash(d: bytes) -> bytes:
return H(b"\x00" + d) # RFC 9162 leaf prefix
def node_hash(l: bytes, r: bytes) -> bytes:
return H(b"\x01" + l + r) # RFC 9162 interior prefix
def split(n: int) -> int:
"""Largest power of two strictly smaller than n (n > 1)."""
k = 1
while k << 1 < n:
k <<= 1
return k
def mth(leaves):
n = len(leaves)
if n == 0:
return H(b"")
if n == 1:
return leaf_hash(leaves[0])
k = split(n)
return node_hash(mth(leaves[:k]), mth(leaves[k:]))
def inclusion_proof(m, leaves):
"""PATH(m, D[n]) from RFC 9162 section 2.1.3.1, ordered leaf-to-root."""
n = len(leaves)
if n <= 1:
return []
k = split(n)
if m < k:
return inclusion_proof(m, leaves[:k]) + [mth(leaves[k:])]
return inclusion_proof(m - k, leaves[k:]) + [mth(leaves[:k])]
def verify_inclusion(index, size, leaf, proof, root):
"""Verification algorithm of RFC 9162 section 2.1.3.2."""
if index >= size:
return False
fn, sn = index, size - 1
r = leaf_hash(leaf)
for p in proof:
if sn == 0:
return False
if fn & 1 or fn == sn:
r = node_hash(p, r)
if not fn & 1:
while fn & 1 == 0 and fn != 0:
fn >>= 1
sn >>= 1
else:
r = node_hash(r, p)
fn >>= 1
sn >>= 1
return sn == 0 and r == root
def _subproof(m, leaves, complete):
n = len(leaves)
if m == n:
return [] if complete else [mth(leaves)]
k = split(n)
if m <= k:
return _subproof(m, leaves[:k], complete) + [mth(leaves[k:])]
return _subproof(m - k, leaves[k:], False) + [mth(leaves[:k])]
def consistency_proof(m, leaves):
"""PROOF(m, D[n]) from RFC 9162 section 2.1.4.1."""
if m == 0 or m == len(leaves):
return []
return _subproof(m, leaves, True)
def verify_consistency(m, n, old_root, new_root, proof):
"""Verification algorithm of RFC 9162 section 2.1.4.2."""
if m == n:
return old_root == new_root and not proof
if m == 0 or m > n or not proof:
return False
if m & (m - 1) == 0: # m is an exact power of two
proof = [old_root] + proof
fn, sn = m - 1, n - 1
while fn & 1:
fn >>= 1
sn >>= 1
fr = sr = proof[0]
for c in proof[1:]:
if sn == 0:
return False
if fn & 1 or fn == sn:
fr = node_hash(c, fr)
sr = node_hash(c, sr)
if not fn & 1:
while fn & 1 == 0 and fn != 0:
fn >>= 1
sn >>= 1
else:
sr = node_hash(sr, c)
fn >>= 1
sn >>= 1
return fr == old_root and sr == new_root and sn == 0
if __name__ == "__main__":
log = [f"cert-{i}".encode() for i in range(7)]
root7 = mth(log)
p = inclusion_proof(3, log)
print("inclusion ok:", verify_inclusion(3, 7, log[3], p, root7), "proof len:", len(p))
print("tampered :", verify_inclusion(3, 7, b"evil", p, root7))
root4 = mth(log[:4])
cp = consistency_proof(4, log)
print("consistency ok:", verify_consistency(4, 7, root4, root7, cp))
forked = log[:2] + [b"rewritten"] + log[3:]
print("fork detected :", not verify_consistency(4, 7, root4, mth(forked), consistency_proof(4, forked)))
Running it prints:
inclusion ok: True proof len: 3
tampered : False
consistency ok: True
fork detected : True
Three details deserve attention. First, the verifier never trusts the proof’s ordering or a left/right flag; it derives sibling position from index and size, which is how RFC 9162 prevents leaf relocation. Second, the “fork detected” line shows a log operator who rewrote entry 2 after publishing a four-entry root: the new seven-entry root cannot be linked to the old one. Third, production code must also check that size matches a signed tree head, because an unsigned size is just another attacker-controlled input.
For production, do not ship this recursion. Real logs store interior nodes, or the tile layout described below, so that proofs are lookups rather than recomputation. The Go packages in the transparency-dev ecosystem and Google’s certificate-transparency-go implement the same algorithms with storage.
Certificate Transparency end to end
A certificate transparency log applies these Merkle tree proofs to the Web PKI. Every publicly trusted TLS certificate is expected to appear in multiple logs, so that a mis-issued certificate for your domain becomes publicly visible rather than silently usable.

Figure 2: The Certificate Transparency flow. The log’s Merkle tree lets monitors verify append-only growth with consistency proofs and lets clients verify a certificate’s presence with an inclusion proof.
The sequence in Figure 2 runs as follows. A certificate authority submits a precertificate and gets back a signed promise to include it (an SCT in RFC 6962 terms). The log appends the leaf and signs a new tree head committing to size n and root hash. Monitors fetch consistency proofs between successive heads, then scan the new leaves for certificates naming domains they watch. Clients and auditors can request inclusion proofs for specific entries.
The biggest change since RFC 9162 is operational rather than cryptographic. Classic RFC 6962 logs exposed dynamic endpoints such as get-proof-by-hash and get-sth-consistency, and every proof was computed on request. The C2SP Static CT API and the related tlog-tiles specification instead publish the Merkle tree as immutable flat files called tiles.
Each tile holds up to 256 hashes, one 8-level slice of the tree; the Tessera layout package fixes TileHeight = 8 and TileWidth = 1 << TileHeight. Because a full tile never changes, a CDN can cache it forever. A client that wants a proof downloads the few tiles covering its path and computes the proof locally.
Let’s Encrypt’s June 2025 retrospective on a year of running Sunlight, Filippo Valsorda’s Static CT implementation, reports that browsers now officially accept Static CT API logs, still alongside at least one traditional RFC 6962 log. It cites an estimated total cost of around $10,000 per year for Valsorda’s single-server Sunlight log and says its own static logs cost far less than its RFC 6962 logs. Other implementations include Google’s Trillian Tessera, Cloudflare’s Azul, and Itko.
Sigstore Rekor: the same tree for software artifacts
Sigstore’s Rekor log applies the identical Merkle tree structure to software signing. When you sign a container image or a release artifact with Cosign, a record of the signature lands in Rekor, and the bundle you ship carries an inclusion proof. Our deep dive on SLSA and Sigstore supply-chain architecture covers the signing side; here the interesting part is the log.
Sigstore announced Rekor v2 general availability on 10 October 2025. Its backend moved to a tile-backed transparency log built on Tessera, with a read API that serves tiles and entries. Uploads go to a single /api/v2/log/entries endpoint and are batched, so they take a few seconds. The redesign drops the search index, keeps only the hashedrekord and dsse entry types, uses per-shard URLs distributed through TUF, and moves signed timestamps to a separate timestamp authority. Rekor v1 continues to run in parallel.
The lesson is that both Certificate Transparency and Rekor converged on the same architecture: a left-full Merkle tree, published as cacheable tiles, with signed checkpoints and external witnesses. The tree shape from RFC 9162 is what makes the tiles immutable.
Deeper Analysis: Hash Tree Anti-Entropy in Dynamo-Style Stores
Leaderless replicated databases face a different question. Two or three replicas own the same key range, writes sometimes reach only some of them, and hinted handoff or read repair do not catch everything. The question is not “is this item in the set” but “where do our two sets differ, and how do we find it cheaply?” This is hash tree anti-entropy.
Amazon’s Dynamo paper (SOSP 2007) made the pattern famous. Each node keeps a separate Merkle tree for each key range it hosts. Two replicas of a range exchange roots; if they match, the range is in sync and nothing else moves. If not, they compare children and descend only into subtrees whose hashes differ, until they reach the leaves that disagree.
Note the naming trap in our title. “Dynamo-style” means the 2007 paper’s design and its open-source descendants such as Cassandra and Riak. Amazon DynamoDB, the managed service, is a different system whose internal replica-repair mechanism is not publicly documented in this level of detail, so we make no claims about it.

Figure 3: Anti-entropy repair in a Dynamo-style store. Replicas hash the same token buckets, a coordinator compares trees, and only mismatched leaf ranges are streamed.
Shape must be agreed in advance
The crucial difference from a transparency log is how leaves are defined. Two replicas with different data must still build a Merkle tree of identical shape, or comparison is meaningless. So the leaves are not individual records but fixed buckets of the key space, typically contiguous token ranges of the consistent-hash ring.
If you have read our guide to database sharding with consistent and rendezvous hashing, you will recognise the dependency. The Merkle tree’s leaves are carved from token ranges, so when membership changes and ranges are re-sliced, those trees must be rebuilt. The Dynamo paper acknowledges this cost of node joins and departures.
Here is a compact sketch of the idea. Both replicas bucket keys by hash into 1,024 leaves, hash each bucket’s sorted contents, build a binary tree, and descend from the root.
import hashlib
DEPTH = 10 # 2**10 = 1,024 leaf buckets per key range
def h(b: bytes) -> bytes:
return hashlib.sha256(b).digest()
def bucket(key: str) -> int:
# Bucket by key hash so both replicas agree on tree shape regardless of content.
return int.from_bytes(h(key.encode())[:4], "big") >> (32 - DEPTH)
def build(store: dict):
leaves = [[] for _ in range(1 << DEPTH)]
for k, v in store.items():
leaves[bucket(k)].append(h(k.encode() + b"\x00" + v))
level = [h(b"\x00" + b"".join(sorted(x))) for x in leaves]
tree = [level]
while len(level) > 1:
level = [h(b"\x01" + level[i] + level[i + 1]) for i in range(0, len(level), 2)]
tree.append(level)
return tree[::-1] # tree[0] is the root level
def diff(a, b, lvl=0, idx=0, out=None, stats=None):
out = [] if out is None else out
stats["compared"] += 1
if a[lvl][idx] == b[lvl][idx]:
return out
if lvl == len(a) - 1:
out.append(idx)
return out
for c in (2 * idx, 2 * idx + 1):
diff(a, b, lvl + 1, c, out, stats)
return out
if __name__ == "__main__":
r1 = {f"user:{i}": f"v{i}".encode() for i in range(100_000)}
r2 = dict(r1)
r2["user:42"] = b"stale"
del r2["user:99999"]
stats = {"compared": 0}
buckets = diff(build(r1), build(r2), stats=stats)
print("divergent buckets:", buckets, "hashes compared:", stats["compared"])
On our run, 100,000 keys with one stale value and one missing key produced two divergent buckets after comparing 39 node hashes. A flat hash list of the same 1,024 buckets would have compared all 1,024. The exact bucket indices depend on the hash, but the count of comparisons scales with (divergent leaves × depth), not with the number of buckets.
Cassandra repair: what the tree saves and what it does not
Apache Cassandra’s anti-entropy repair is the most widely operated example. The Cassandra repair documentation describes repair as comparing data using Merkle trees, “a hierarchy of hashes”, and streaming the differences for out-of-sync sections between nodes. Each replica runs a validation pass that reads the data in the range and hashes it into the tree; the coordinator compares the trees and triggers streaming.
The docs distinguish full repair, which covers all data in the token range, from incremental repair, the default, which covers only data written since the last incremental repair. Full repairs should still run occasionally to catch disk corruption, operator error or bugs. A preview mode (-prv) builds and compares trees and prints the expected streaming without moving data. A validate mode (-vd) compares trees of already-repaired data.
The scheduling guidance is concrete: incremental repair every one to three days and full repair every one to three weeks as a starting point. With the default 10-day gc_grace_seconds, the docs suggest repairing every node at least every seven days. Miss that window and deleted data can resurrect, because a tombstone may be purged on one replica before the other replica learns of the delete.
Here is the insight most write-ups miss: the Merkle tree saves network, not disk. Building the tree requires reading and hashing every row in the range on every replica. For a cold, large table, that validation pass is the dominant cost of repair, and no tree shape can avoid it. Incremental repair helps precisely because it shrinks the set of data that must be validated.
Leaf granularity and overstreaming: worked numbers
The Merkle tree’s resolution is bounded, so each leaf covers a slice of data, and a mismatch streams the whole slice. Operator documentation from AxonOps cites roughly 32,768 (2^15) segments per repair session by default and a minimum stream unit of about 30 MB for a 1 TB table. The configurable depth and memory budget differ across Cassandra versions, so check your release rather than trusting a single number.
Now an illustrative calculation. Take a 1 TB table split into 32,768 leaves: 1,000,000 MB / 32,768 ≈ 30.5 MB per leaf. Suppose 100 rows have diverged, scattered uniformly. The expected number of pairs that collide in one leaf is about 100 × 99 / (2 × 32,768) ≈ 0.15, so roughly 100 leaves mismatch. Repair then streams about 100 × 30.5 MB ≈ 3 GB to fix 100 rows: amplification of many orders of magnitude.
Two levers reduce it. Repairing smaller token subranges gives each tree a finer resolution, because the same leaf budget covers less data; this is what subrange repair tools exploit. Running repair more often keeps the divergent set small, so fewer leaves mismatch. Deeper trees cost coordinator memory, which is why Cassandra caps them.
The Merkle tree comparison itself is cheap by contrast. With depth 15 and 100 divergent leaves, a top-down descent touches at most about 2 × 100 × 15 = 3,000 node hashes, versus 32,768 leaf hashes for a flat comparison. In practice Cassandra sends whole trees to the coordinator rather than doing an interactive descent, but the tree is still a few megabytes at most, which is negligible next to validation I/O.
The same idea elsewhere: CRDT sync and range-based reconciliation
Merkle tree diffing appears wherever two parties must reconcile large sets over a slow link. Offline-first systems, like the ones in our guide to CRDT-based digital twin synchronisation at the edge, often pair CRDT merge semantics with a hash summary so peers can skip unchanged state. The CRDT decides what the merged value is; the hash tree decides which values need merging at all.
The limitation is that fixed-bucket trees degrade when data is skewed. If one tenant’s keys dominate a few buckets, those leaves stay coarse while others are nearly empty. Content-defined or adaptively split trees fix this at the price of agreeing on split rules, which is exactly the problem the next section’s systems solve.
Content-Addressed Trees: Git, ZFS and IPFS
The third use of hash trees is naming content by its hash, so identity and integrity are the same thing. Here the structure is usually a Merkle DAG, a directed acyclic graph in which nodes can share children, rather than a strict binary tree.
Git’s object model
Git stores four object types: blobs (file contents), trees (directory listings that map names and modes to blob or tree hashes), commits (a root tree hash, parent commit hashes, author and message), and annotated tags. Each object’s ID is the hash of its type, length and content. A commit is therefore the root of a Merkle tree over its entire snapshot and, through its parents, to the whole history.
This is why git fsck can verify a repository end to end and why a single changed byte in an old file changes every descendant commit ID. It is also why Git can deduplicate: two directories with identical contents share one tree object. Diffing two commits is a Merkle descent: identical subtree hashes are skipped without reading their contents.
Git’s hash is the weak spot. SHA-1 collisions became practical with the 2017 SHAttered attack, and Git responded by using a collision-detecting SHA-1 variant. The longer-term fix is SHA-256 object format, which has been non-experimental since Git 2.42 in 2023.
Git’s own BreakingChanges document states that in Git 3.0 “the default hash function for new repositories will be changed from ‘sha1’ to ‘sha256′”, conditional on ecosystem readiness, and that there is no plan to deprecate SHA-1 repositories. LWN’s September 2026 coverage reported that GitLab and Forgejo support SHA-256 repositories while GitHub support was still missing, and that Git 3.0 is planned for April 2027. Treat that date as a published plan, not a shipped fact.
Interoperability is the hard part. A SHA-256 repository cannot simply reference SHA-1 object IDs, because tree entries embed fixed-size binary hashes. That is a direct consequence of the Merkle design: every parent commits to its children’s exact hash bytes, so changing the hash function changes every node.
ZFS: a checksum tree for storage
ZFS applies the Merkle tree idea to blocks on disk. Each block pointer carries the checksum of the block it points to, and pointers are themselves stored in parent blocks, up to the uberblock at the top. Reading a block verifies it against the checksum held by its parent, so a block can never vouch for itself. That design, widely described as a self-validating Merkle tree, lets ZFS detect silent corruption, misdirected writes and phantom writes, then repair from a redundant copy.
The OpenZFS documentation says the checksum property defaults to on, which means fletcher4 for ordinary datasets and sha256 when deduplication is enabled. Supported algorithms also include sha512, skein, edonr and blake3, with blake3 gated by the org.openzfs:blake3 pool feature. Fletcher4 is fast but not cryptographic; it guards against accidental corruption, not a malicious writer, which is fine for a local filesystem.
IPFS and the Merkle DAG
IPFS splits files into chunks, hashes each into a content identifier (CID), and links chunks under parent nodes to form a Merkle DAG. Any peer can serve any block, because the receiver verifies each block against the CID it asked for. Identical chunks across files deduplicate automatically.
Shape matters here too: the same file chunked differently gets a different root CID. IPIP-0499 on UnixFS CID profiles documents the legacy unixfs-v0-2015 profile (256 KiB maximum chunks, up to 174 children per node) and a modern unixfs-v1-2025 profile (1 MiB chunks, up to 1,024 children). Two tools with different defaults will produce different CIDs for byte-identical files, a frequent source of confusion.
Ethereum’s Merkle Patricia Trie belongs to this family too: it commits to account and storage state so light clients can verify individual values. We mention it only by name, since its encoding rules deserve their own article.
Choosing the Right Shape: A Decision Map
The four systems above use the same primitive for four different questions. Getting the question right determines the Merkle tree shape, and the wrong shape is the root of most hash-tree design mistakes.

Figure 4: Choose the hash tree shape by the question it must answer. Append-only proofs need an RFC 9162 left-full tree; replica diffing needs a fixed-shape bucket tree; content identity needs a chunked Merkle DAG.
| Dimension | Transparency log (CT, Rekor) | Anti-entropy (Dynamo, Cassandra) | Content addressing (Git, IPFS, ZFS) | Flat hash list |
|---|---|---|---|---|
| Question answered | Is X logged; did history only grow | Where do replicas differ | What is this content; is it intact | Is the whole set unchanged |
| Leaf definition | One entry, in append order | Fixed bucket of key space | Object, chunk or block | One item |
| Proof to third party | Yes, inclusion and consistency | No, peers trust each other | Yes, via content ID | Only with all hashes |
| Single-item proof size | ~log2(n) hashes | Not applicable | Path length in DAG | n hashes |
| Update cost | O(log n) per append | Rebuild per repair pass | Rewrite path to root | O(1) append, O(n) to verify |
| Typical hash | SHA-256 | Implementation-specific | SHA-1 or SHA-256 in Git; fletcher4 or SHA-256 in ZFS | Any |
| Main failure mode | Split view, unsigned sizes | Overstreaming, stale trees | Hash migration, chunking drift | Proofs too large |
The flat hash list column is the honest baseline. If you only ever verify the whole set at once, for example a release manifest checked in full, a hash list is simpler and perfectly adequate. The tree pays off when parties need to verify one item, or find a few differences, without touching everything.
Trade-offs, Gotchas, and What Goes Wrong
Missing domain separation. Covered above, but it is still the most common bug in a home-grown Merkle tree. If leaves and nodes are hashed the same way, a 64-byte node preimage can pose as a leaf. Prefix leaves and nodes differently, or use distinct tagged hashes as Bitcoin’s Taproot does.
Odd-node duplication. Padding by duplicating the last hash makes different leaf lists collide on one root, as CVE-2012-2459 showed. Use the RFC 9162 split rule, or include the leaf count in the root commitment.
Unbound tree size and index. A proof verified without a signed tree size lets an attacker present a different-shaped tree. Always verify the signature over the tree head first, then the proof against that size.
Split views. A malicious log can sign two different roots for two audiences. Inclusion proofs alone do not catch it; you need consistency proofs plus gossip or witnesses that compare checkpoints. This is why Rekor’s batching was designed with witnessing in mind and why CT relies on multiple independent monitors.
Trusting the root out of band. A Merkle proof is only as good as your copy of the root. If an attacker controls the channel that delivers the root, the proof is theatre. Anchor roots in signatures from keys you distribute separately, as TUF does for Rekor shard URLs.
Anti-entropy overstreaming and I/O. Coarse leaves stream far more than the diverged rows, and validation scans compete with production reads. Repair subranges, run incremental repair frequently, schedule full repairs off-peak, and watch compaction backlog. Our guide to LSM-tree compaction and write amplification explains why validation reads interact badly with a busy compaction queue.
Stale trees after topology change. In Dynamo-style stores, a membership change re-slices token ranges and invalidates cached trees. Plan repairs after scaling events, not before.
Clock-free does not mean order-free. A Merkle tree tells you two replicas differ, not which value is newer. Conflict resolution still needs timestamps, vector clocks or CRDT semantics; see our explainer on hybrid logical clocks and vector clocks.
Hash agility. Every node commits to exact child hash bytes, so changing the hash function means rebuilding the whole Merkle tree. Git’s multi-year SHA-256 transition is the cautionary tale. Version your hash algorithm in the root or log parameters from day one, as RFC 9162 does with its hash algorithm parameter and registry.
Canonical serialisation. Two implementations that serialise the same logical record differently produce different leaf hashes. Define a canonical encoding for leaves, including field order, integer width and string normalisation, before you ship.
Practical Recommendations
Start by writing down the question your structure must answer, then pick the shape. If third parties must verify membership or append-only growth, build the Merkle tree exactly as RFC 9162 specifies, or better, adopt a maintained tile-based log library such as Tessera rather than writing proofs yourself. If peers must find differences, use a fixed-shape bucket tree over your partitioning scheme and size leaves against your data volume. If you need content identity and deduplication, use a Merkle DAG with pinned chunking parameters.
For Cassandra operators, treat repair as a capacity-planning problem, not a cron entry. Measure validation duration per table, repair within gc_grace_seconds, prefer subrange and incremental repair for large tables, and run a preview repair before a large full repair to estimate streaming.
For supply-chain teams, verify Merkle tree inclusion proofs offline in your admission controllers and keep checkpoints so you can later prove consistency. Pair it with the SBOM and VEX practices in our guide to CycloneDX vs SPDX and vulnerability triage, so that what you log is also what you can audit.
A short checklist:
- Prefix leaves with 0x00 and nodes with 0x01, or use tagged hashes.
- Never duplicate odd nodes; use the largest-power-of-two split.
- Verify the signed tree head before any proof, and bind index and size.
- Collect consistency proofs between checkpoints you have seen.
- Record the hash algorithm in the root metadata.
- Define a canonical leaf encoding and test it across implementations.
- For anti-entropy, size leaves so one mismatch streams an acceptable amount.
Frequently Asked Questions
What is a Merkle tree in simple terms?
A Merkle tree is a tree of hashes. Each data record is hashed into a leaf, and each parent node is the hash of its children’s hashes, up to a single root hash. Because every parent depends on everything beneath it, changing any record changes the root. That lets you summarise a huge dataset with one 32-byte value, prove a single record belongs with a short path of sibling hashes, and find where two copies differ by comparing hashes top-down instead of comparing every record.
How big is a Merkle proof for one million items?
A Merkle proof contains one sibling hash per tree level, so for n items it holds about log2(n) hashes. For 1,000,000 items, log2 is about 19.93, so the proof has at most 20 hashes. With SHA-256 at 32 bytes per hash, that is 640 bytes, and verification needs 21 hash computations. A flat hash list would require all one million hashes, 32 MB, to verify the same item against a single digest. Even at one billion items the tree proof is only 30 hashes, or 960 bytes.
What is the difference between a Merkle tree and a hash list?
A hash list stores the hash of every item and usually signs a digest of the list. Verifying one item against that digest needs the whole list, so proof size grows linearly with n. A Merkle tree arranges the same hashes hierarchically, so one item’s proof is logarithmic, and two copies can be diffed by descending only into mismatched branches. Hash lists are simpler and fine when you always verify everything at once. Trees win when you verify individual items or reconcile large sets.
How does Cassandra use Merkle trees for repair?
During anti-entropy repair, each replica reads the data in a token range and builds a Merkle tree whose leaves cover slices of that range. A coordinator compares the trees from all replicas and identifies leaf ranges whose hashes differ. Cassandra then streams those whole ranges between replicas to bring them in sync. The tree minimises network comparison, but building it requires reading all data in the range, so validation I/O dominates repair cost. Coarse leaves also cause overstreaming when only a few rows differ.
What is a consistency proof in Certificate Transparency?
A consistency proof shows that a newer version of a log, with n entries, contains an older version with m entries as an unchanged prefix. RFC 9162 defines it as the list of tree nodes needed to verify that the first m inputs are equal in both trees. The verifier recomputes both the old and new root hashes from the proof. If both match the signed tree heads, the log only appended. Monitors and witnesses use these proofs to detect logs that rewrite history or show different views to different users.
Is SHA-1 still safe for Git’s Merkle tree?
Git uses a collision-detecting variant of SHA-1 that blocks the known SHAttered-style attacks, so existing repositories are not trivially forgeable today. However, Git’s BreakingChanges document says Git 3.0 will default new repositories to SHA-256, citing NIST’s deprecation of SHA-1 and expected future attacks. SHA-256 repositories have been supported without the experimental label since Git 2.42. Forge support is uneven: GitLab and Forgejo support it, while GitHub support was reported missing as of September 2026. SHA-1 repositories are not planned for deprecation.
Further Reading
- Probabilistic data structures: Bloom filters, HyperLogLog, Count-Min Sketch and cuckoo filters — the approximate-membership counterpart to exact Merkle proofs.
- Database sharding with consistent hashing, rendezvous hashing and resharding — how token ranges, the leaves of anti-entropy trees, are carved and moved.
- SBOM and VEX: CycloneDX vs SPDX for supply-chain vulnerability triage — what to put in the artifacts you log in Rekor.
- SLSA and Sigstore software supply-chain security architecture — the signing pipeline that feeds transparency logs.
- RFC 9162: Certificate Transparency Version 2.0 — the normative definitions of the Merkle Tree Hash, inclusion proofs and consistency proofs.
- Apache Cassandra repair documentation — full, incremental, preview and validate repair modes and scheduling guidance.
By Riju — about
