Use a hash chain when you are the only verifier. Use a Merkle tree — a versioned one, with consistency proofs — the moment a third party must check one record without reading every record before it. Crosby and Wallach put the gap at USENIX Security 2009: an 800 MB chain trace against a 3 KB tree proof, same claim, 80 million events.
Ross Jones — Founder, The Hopium Lab. Last modified 22 July 2026.
The decision is about the verification interface you expose, not the bytes on disk. Amazon QLDB shipped both at once — hash-chained journal for ordering, Merkle digest for proof — so the two are not exclusive. Recompute-forward is the failure where the party holding the only commitment edits a past record, recomputes every commitment after it, and every check still passes. Neither structure fixes recompute-forward. Say that out loud before choosing between them.
What does each structure cost when someone actually verifies it?
A hash chain costs O(n−k): the verifier replays every event between the record at index k and the commitment being checked. Crosby and Wallach's Table 1 (USENIX Security '09, Montreal, August 2009, pp. 317–334) puts a history tree at O(log₂ n) for the same proof. A classic chain has the form C_i = H(C_{i-1} || X_i) and, in the paper's words, does not permit events to be skipped.
The k carries more weight than the O. A chain proof against a commitment issued five minutes ago is a handful of hashes; against one issued in March it is the whole quarter. Hence the headline: 800 MB to prove one randomly chosen event out of 80 million, against a 3 KB proof of the same claim.
A hash chain is not expensive to verify. A hash chain is cheap against a recent commitment and ruinous against an old one. The cost is the distance, never the structure.
Trees are not free. Crosby's table charges the history tree O(log₂ n) on append where a chain pays O(1), and the paper scopes "strictly dominates" to proof generation time and proof sizes. Anyone quoting the claim without that qualifier is doing advocacy. Crosby and Wallach's own rebuttal is that the write-side advantage is fleeting: the 2009 prototype sustained 1,750 events per second on one CPU core, 10,500 with signatures offloaded, corresponding to 1.1 TB of throughput per week. Append cost is rarely the binding constraint. Proof cost, once a third party is in the room, always is.
Who is verifying, and how many of them are there?
Count the verifiers, then ask whether any is entitled to see one record and nothing else. Volume is the wrong discriminator, and the paper says as much directly: chaining schemes are feasible at low event volumes or where every auditor already receives every event. Ten million records with one verifier holding a full copy is a chain problem.
| Decision input | Hash chain | History tree (versioned Merkle) |
|---|---|---|
| Membership proof for record k (Crosby Table 1) | O(n−k) — every intervening event | O(log₂ n) |
| Append cost | O(1) | O(log₂ n) |
| Many auditors | Each must eventually receive every event; cost is events × auditors | Each receives only the portions it audits; cost stays proportional to events |
| Selective disclosure | Impossible — the proof is the intervening records | Native — a path of sibling digests discloses nothing else |
| Proving two commitments share a past | Replay the interval between them | Incremental proof, O(log₂ n) (Crosby Table 1); RFC 6962 §2.1.2 bounds its consistency proof at ceil(log₂(n)) + 1 nodes |
| Stops recompute-forward | No | No |
| Correct when | You are the only verifier, or every auditor already gets every event | A third party checks one record, or auditors have disjoint scopes, or commitments are old |
The multi-auditor row is the one people skip: a chain's cost scales as events times auditors, a tree's as events alone.
Does a Merkle tree stop you rewriting entry five?
No. Recompute-forward is the failure where the party holding the only commitment edits a past record, recomputes every commitment after it, and every check still passes — and recomputing a Merkle root costs no more than recomputing a chain tip. A tree fixes the size of a proof. A tree changes nothing about who holds the head.
Crosby and Wallach's threat model states the condition plainly: a centralised but totally untrusted logger, audited by one or more auditors, at least one assumed incorruptible, with commitments gossiped between them. Strip the auditors out and the data structure is decoration. Without auditing, the paper concludes, clients cannot detect a logger that fails to log events, removes unaudited events, or forks the log.
A root hash proves nothing to a party who can only obtain that root from you.
The structural fix lives outside the log. C2SP tlog-witness specifies it: a witness signs your checkpoint only after verifying a consistency proof against the last checkpoint it signed, and a set of witnesses — ideally an odd number, so a quorum is unambiguous — makes a split view detectable. A checkpoint is three lines: origin string, tree size, base64 root hash. Getting copies of those three lines outside your trust boundary does more for the design than any structure choice. In evidence layer reviews, the missing piece is almost never the maths — it is that nobody outside the building holds a copy of the head.
What do the two RFCs actually bound?
Both RFCs bound exactly one thing: the number of nodes in a consistency proof, "bounded above by ceil(log2(n)) + 1". RFC 6962 §2.1.2 (June 2013) states it; RFC 9162 §2.1.4.1 (December 2021) repeats the sentence verbatim. It is not the number people quote. The string log2 appears exactly once in each document, and neither RFC states any bound on an inclusion proof anywhere.
The familiar ceil(log₂(n)) figure for inclusion is still true: the PATH() construction in RFC 6962 §2.1.1 splits at the largest power of two below n, so depth tops out at ceil(log₂(n)). It is derivable from the construction, not quotable from the document. Write "the construction yields at most", never "the RFC states". Names matter too: RFC 6962 §2.1.1 says Merkle audit path; the term inclusion proof arrives with RFC 9162 §2.1.3. Using 9162's vocabulary against 6962's section numbers is the tell that a post was written from memory.
One distinction earns its keep. A plain Merkle tree gives inclusion proofs and nothing else: it cannot show that two different roots make consistent claims about the same past. Crosby and Wallach's contribution was the versioned computation over the tree, which is why the paper says history tree; RFC 6962 does the same job with separate consistency-proof machinery. Leaf and node hashing must also be domain-separated, which has its own post.
Should you still cite RFC 6962 in 2026?
Yes, for the tree mathematics, and never as a live operational recommendation. The header block of RFC 9162 reads "Obsoletes: 6962", and any reader with a browser can check that. Both documents are Category: Experimental, neither is Standards Track, and claiming otherwise is the cheapest correction anybody will earn against you.
Document status and deployed cryptography have diverged. RFC 9162 obsoletes 6962 on paper, with no public evidence of a production CT v2 log; the ecosystem standardised the Static CT API instead, which states that all cryptographic operations are as specified by RFC 6962 and calls itself an alternative encoding. The read path moved to static tiles. The tree maths did not move.
The transition has dates. Let's Encrypt made its RFC 6962 logs read-only on 30 November 2025 and shut them down on 28 February 2026, citing annual cloud costs approaching seven figures for the relational-database design and repeated Maximum Merge Delay breaches. Amazon QLDB reached end of support on 31 July 2025, and the recommended migration offers no cryptographic verification. Let's Encrypt and QLDB are both precedent. Neither is somewhere to send a workload today.
Where does the choice go wrong in production?
Six named failures: three caused by picking the wrong structure, three that survive whichever structure you pick.
- Recompute-forward. The commitment never leaves your infrastructure, so an edit plus a recomputation verifies cleanly. Structure-agnostic. Fix by moving the head, not the maths.
- Old-commitment cliff. A chain sized against yesterday's anchor, then asked to prove a record against a quarterly one. O(n−k) with k three months back is the 800 MB case.
- Auditor fan-out. A chain that worked for one auditor, then a second and third arrive with narrower scopes. Cost multiplies and the proof hands each of them everyone else's records.
- Plain-tree substitution. A Merkle root published on a schedule, called append-only, with no consistency proof between consecutive roots. Membership in a tree that may share no past with the previous one is not the claim anybody wanted.
- Self-witnessing. Checkpoints countersigned by a service running in the same account under the same credentials.
- Unbounded proof acceptance. A verifier that accepts a proof of any length for any index — a soundness hole that survives every structure choice above.
Tamper-evident is not tamper-resistant. Both structures make an edit detectable afterwards; neither prevents it, and no amount of hashing makes a suppressed event appear.
What is the decision procedure?
Four questions in order, then the build items both structures share.
CHAIN OR TREE — DECISION PROCEDURE v1.0 (22 July 2026)
The Hopium Lab. Supports a conformity case. Confers none. Not legal advice.
Recompute-forward: the failure where the party holding the only
commitment edits a past record, recomputes every commitment after it,
and every check still passes.
1. WHO VERIFIES?
Only you .............................. chain is sufficient
One auditor who receives everything ... chain is sufficient
Any party entitled to ONE record ...... tree, mandatory
Auditors with disjoint scopes ......... tree, mandatory
2. HOW OLD IS THE COMMITMENT BEING PROVED AGAINST?
Minutes ... chain proof is O(n-k) with k near n. Fine.
Months .... chain proof is the whole quarter. Tree.
3. MUST A PROOF DISCLOSE ONLY THE RECORD IT PROVES?
No ........ chain
Yes ....... tree. A chain proof IS the intervening records.
4. DO YOU HOLD THE ONLY COMMITMENT?
Yes ....... neither structure helps. Fix question 4 before
arguing about questions 1 to 3.
No ........ name the parties, and name how they compare notes.
BUILD, EITHER WAY
[ ] Domain-separated leaf and node hashing (0x00 / 0x01)
[ ] Consistency proof checked on a schedule; failure pages a human
[ ] Checkpoint = origin string, tree size, root hash, signed
[ ] >= 2 witnesses countersign, each verifying consistency against
the last checkpoint IT signed, not the one you hand it
[ ] A verifier a third party runs offline against an export
[ ] Proof-size regression test at your projected 3-year n
DO NOT SHIP IF
[ ] The only copy of the head sits inside your trust boundary
[ ] "Append-only" rests on a plain Merkle root with no consistency
proof ever computed
[ ] The verifier accepts a proof of any length for any index
Question 4 is the one worth arguing about, and most writing on the subject answers questions 1 to 3 and stops. Pick the structure that matches who has to check the work, then go and find somebody willing to hold a copy of the head.
Ross Jones, Founder, The Hopium Lab. Engineering guidance, not legal advice.