RFC 6962 Merkle tree and consistency proofs, explained

One root commits to every entry and its position

RFC 6962 was written for Certificate Transparency logs, but section 2.1 defines a general construction. Its introduction says why a log wants one: "The append-only property of each log is technically achieved using Merkle Trees, which can be used to show that any particular version of the log is a superset of any particular previous version."

The tree hash has three rules:

• An empty list hashes to "the hash of an empty string": MTH({}) = SHA-256().
• One entry is a leaf: MTH({d(0)}) = SHA-256(0x00 || d(0)).
• For n > 1, "let k be the largest power of two smaller than n", and MTH(D[n]) = SHA-256(0x01 || MTH(D[0:k]) || MTH(D[k:n])).

The 0x00 and 0x01 prefixes separate leaf hashes from inner-node hashes. The RFC states the reason in a parenthesis: "This domain separation is required to give second preimage resistance." The list does not have to be a power of two. In the RFC's words the tree "may thus not be balanced; however, its shape is uniquely determined by the number of leaves". Two parties with the same entries in the same order compute the same root.

The rules fit in a few lines of Python:

import hashlib
H = lambda b: hashlib.sha256(b).digest()
leaf = lambda d: H(b"\x00" + d)
node = lambda l, r: H(b"\x01" + l + r)

def split(n):                      # largest power of two < n
    k = 1
    while k * 2 < n: k *= 2
    return k

def mth(D):
    if len(D) == 0: return H(b"")
    if len(D) == 1: return leaf(D[0])
    k = split(len(D))
    return node(mth(D[:k]), mth(D[k:]))

Run over seven entries d0 to d6 (the ASCII strings), this gives the root 73a590fb266b81557040b146b9d479e2a1b5849b125167642f5b64866f1d5c7d. Over d0 to d2 it gives c64c5b9326951a2db82d5462565696286659d1c7a4a26a92703568f63462f7ba. Those two roots are the example for the rest of this entry.

An inclusion proof is the list of siblings along one path

An audit path answers whether an entry is in the log without sending the log. The RFC defines it as "the shortest list of additional nodes in the Merkle Tree required to compute the Merkle Tree Hash for that tree". The verifier hashes the entry as a leaf and combines it with each node on the path in turn, up to a root. "If the root computed from the audit path matches the true root, then the audit path is proof that the leaf exists in the tree."

The path is short because each step needs just the sibling subtree's hash. In the RFC's seven-leaf example the path for d0 is [b, h, l], three nodes for seven entries. The size of a consistency proof is "bounded above by ceil(log2(n)) + 1", which for a log of one million entries is 21 nodes.

What an inclusion proof does not show is that the log is the one you meant. It proves that a leaf is under a root. Whether the root itself is the right one is a question about where you got it. That is the same problem the next section has, in a sharper form.

A consistency proof shows that a later root extends an earlier one

Section 2.1.2 opens with the purpose: "Merkle consistency proofs prove the append-only property of the tree." Given a root over n entries and "a previously advertised hash" over the earlier m, the proof is the list of nodes needed to verify that the m inputs "are equal in both trees".

The RFC's example for a seven-entry tree is PROOF(3, D[7]) = [c, d, g, l], where "c, g are used to verify hash0, and d, l are additionally used to show hash is consistent with hash0". With the entries above, the four nodes are:

The verifier holds the old root, the new root and these four nodes, and does not need the entries. It rebuilds the old root as H(0x01 || g || c) and compares it to the recorded one. It rebuilds the new root as H(0x01 || H(0x01 || g || H(0x01 || c || d)) || l) and compares that to the current one. Computing both with the same script, the rebuilt old root equals c64c5b93… and the rebuilt new root equals 73a590fb….

Now rewrite entry d1 in the seven-entry log and keep everything else. The new root is fa0543d8f766622ec6bbe5c9e2c3ea6ffacc5c6703a5828d0774c9816515126e, and the root over d0 to d2 no longer equals the recorded c64c5b93…. A proof built from the rewritten tree rebuilds a different size-3 root. A proof that rebuilds the recorded size-3 root has to use the original g, and then it rebuilds the original size-7 root, not fa0543d8…. The two roots cannot both match without a SHA-256 collision, so the edit is caught without anyone re-reading the entries.

Dropping the newest entries leaves a valid tree

Take the same log and drop d5 and d6. The remaining five entries hash to 2b650a5633502111de1a865b3581e012a91dc1f8b780ddf646a44873dec93163. That is a perfectly good tree. Nothing in it records that two more entries existed.

A verifier that recorded size 7, root 73a590fb… sees size 5 and rejects. The definition requires m ≤ n, so there is no consistency proof from a size-7 root to a size-5 tree. A verifier that recorded nothing sees a valid log.

This is why the RFC puts the weight on keeping roots. Its section 7.3 says violation of the append-only property "is detected by global gossiping, i.e., everyone auditing logs comparing their versions of the latest Signed Tree Heads". In Certificate Transparency that comparison is done by whoever audits logs. A single-operator audit log has to arrange the same thing on purpose, by writing each new root somewhere the log's operator cannot edit.

Two practical consequences follow:

• Record size:root after every verification run, not just when something looks wrong. A root recorded after the damage proves nothing about the damage.
• A recorded root helps when the party who wrote it is not the party who can rewrite the log. Storing it next to the log file defends against accidents, not against an operator with write access to both.

RFC 9162 obsoletes RFC 6962 and keeps the tree rules

RFC 6962's status section says it "is not an Internet Standards Track specification; it is published for examination, experimental implementation, and evaluation". RFC 9162 carries "Obsoletes: 6962" and the same Experimental category. Its section 2.1.1 gives the tree definition again with the same 0x00 and 0x01 prefixes and the same split at the largest power of two below n. One difference is in wording: it writes HASH for the log's chosen algorithm where RFC 6962 writes SHA-256. A builder who wants to reuse the tree should cite both documents and state which hash function the log uses.

Where Mandare fits, and what it does not do

The ledger in Mandare's open-source repository uses this tree. The verifier source states the contract: leaf index i is the ledger entry with sequence number i + 1, and "the leaf INPUT is the raw 32 bytes of that entry's entry_hash". The implementation is hand-written and its test file takes its vectors from the Certificate Transparency reference implementation (transparency-dev/merkle). This applies to CLI v0.1.0, which npm view @mandarelabs/cli version reported on 12 October 2026. mandare verify prints a line of the form tree: size=<n> root=<hex> for a valid chain, and the CLI reference documents the --prev-head flag, which takes the same pair written as <size>:<root>.

Recording and checking a root uses one flag:

mandare verify --db ledger.db                                  # prints tree: size=N root=…
mandare verify --db ledger.db --prev-head <size>:<root>        # later run

The second run reports CONSISTENT when the current tree extends the recorded head, ROLLBACK DETECTED when the ledger has fewer entries, and INCONSISTENT when "recorded head is not a prefix of the current tree". A comment in the library's verifyConsistency records a review finding: a recorded head of size 0 must carry the empty-tree root, because silently ignoring that root "would bless a garbage recorded head".

Mandare automates the recording step with a witness: a separate process that stores each head the door sends and, per the witnessing document, refuses a submission that is not "a provable append-only extension". The demo transcript shows the effect on a truncated copy:

[verify]  truncated copy, self-anchored:      chain VALID — the lie is locally perfect
…
[verify]  truncated copy, --witness:      TRUNCATION DETECTED (exit 1)

Limits, next to the claims they limit:

• Without a recorded head or a witness, mandare verify calls a truncated ledger valid. The transcript line above says so, and the threat model lists truncation as invisible to self-anchored verification.
• The witness has to run on infrastructure the operator cannot rewrite. In the single-host Docker stack it shares the machine, and the repo's example README says a full-root operator controls both sides.
• A single witness is a single party. The witnessing document says a malicious witness "can lie by omission" and that running a second one is the standard remedy, which the protocol permits.
• There has been no external audit of the tree code. The repository documents AI-assisted review passes, and its S8 review document, dated 9 August 2026, says the external audit is still pending.

For how the witness avoids seeing log content, see proofs, not data. For what a log is required to record in the first place, see EU AI Act Article 12 and agent logs.