Two trees.

A document hash forces a choice nobody should have to make: disclose everything, or disclose something unverifiable. The way out is a Merkle tree over fields rather than a digest over bytes — plus a second tree over records, doing an entirely different job. This paper gives both constructions at byte level, and the encoding defect that made an earlier version of the first one accept a value that had been changed.

§1The problem with hashing a document

Take the ordinary approach. A record is serialised, hashed, and the digest is signed. Anyone can recompute the digest and check the signature. This is correct, standard, and it satisfies the first two requirements from Paper 001.

Now remove one field, because it names a third party, or reveals a commercial term, or is simply irrelevant to the matter at hand. The digest no longer recomputes. The recipient's only options are to take the redaction on trust — which returns us to the operator's word — or to demand the unredacted record, which forces disclosure of things that were legitimately withheld.

This is not an exotic corner case. It is the normal shape of disclosure: relevance is scoped, confidentiality is protected, and both of those are contemplated by the instruments that compel production in the first place.^[1] A construction that treats any withholding as tampering has misunderstood what it is for.

§2Two false starts worth walking through

Hash each field independently

The obvious repair: commit to H(value) per field. Withholding then means disclosing the hash instead of the value, and everything else still checks.

This fails immediately, and it fails worst on exactly the fields most worth withholding. A hash conceals a value only insofar as the value is unguessable. Consider a withheld boolean: an examining party computes H(true) and H(false) and reads the answer. A withheld severity from a five-value enumeration takes five hashes. A withheld monetary amount known to be a round figure in a plausible range takes a few million — that is, under a second. The withheld field is only as private as its value space is large, and low-entropy fields are the common case.

Salt each field, and stop there

So salt: commit to H(salt ‖ value) with a fresh random salt per field, disclosed alongside the value and withheld alongside it. Now the guessing attack fails, because the adversary cannot compute a candidate hash without the salt.

But nothing binds the fields into a record. Given a bag of independent commitments, a discloser can drop one entirely and the remainder still verifies — because there is no statement anywhere about how many fields there were or which. Deletion becomes invisible, which is precisely the property we were trying to obtain.

What is needed is a structure that (a) commits to the set as a whole, (b) lets an individual leaf be replaced by its hash without disturbing the whole, and (c) makes an absence visible as an absence. That structure is a Merkle tree, and the leaves are fields.

§3The first tree: over the fields of one record

Order the record's top-level fields by path. For each, generate a random salt and compute a leaf. The record's identity is the Merkle root over those leaves, computed per RFC 6962.^[2]

The leaf is where the care goes:

// one field's commitment — every component length-prefixed
leaf(path, value, salt) =
    SHA-256( 0x02
           ‖ u32be(len P) ‖ P        P = utf8(canonical(path))
           ‖ u32be(len S) ‖ S        S = 16 raw salt bytes, exactly
           ‖ u32be(len V) ‖ V )      V = utf8(canonical(value))

The 0x02 prefix separates a field leaf from the tree's own 0x00 leaf and 0x01 interior-node prefixes, so no value in one domain can be presented as a value in another. canonical is deterministic JSON with keys sorted recursively — so the same facts always produce the same bytes, and formatting can never break a check.

Note that the path is canonicalised too, which means it is JSON-encoded, quotes included. That is not decoration: it makes the path a self-delimiting encoded value rather than a raw string, which matters for the same reason the length prefixes do.

§4The defect: when two different records have the same commitment

The construction above is the corrected one. The first version was this, and the difference is easy to miss:

// the earlier, defective form
leaf(path, value, salt) = SHA-256( 0x02 ‖ P ‖ S ‖ V )
// with the salt validated as "at least 16 bytes"

No length prefixes, and a minimum salt length rather than a fixed one. Both of those look harmless. Together they are a collision, and it is available to the party who writes the record — which, per Paper 001, is the adversary we care about.

honest record
  P ‖ S                    ‖ "12345"
      └── 16 bytes ──┘      └─ 5 bytes ─┘

the same bytes, re-presented
  P ‖ S ‖ "12"             ‖ "345"
      └── 18 bytes ──┘      └─ 3 bytes ─┘

the concatenation is byte-identical → identical leaf
                              → identical Merkle root
                              → identical record commitment

The repair is two independent changes, and it is worth being explicit about why both, since either alone appears sufficient:

• Length-prefix every component. With u32be(len) before each field, the boundaries are recoverable from the hashed bytes; moving a byte from the value into the salt now changes two length words and the digest with them.
• Fix the salt at exactly 16 bytes. A variable-length secret component adjacent to attacker-chosen data is the ingredient that made the attack possible at all.

Either fix closes this specific attack. Both are applied because a construction that depends on a single property being upheld is one refactor away from failing, and because "at least" in a length check is a pattern that reappears. Defence here is cheap; the failure is silent.

§5Withholding, and why the label needs its own commitment

To withhold a field, the discloser publishes the field's leaf hash and drops the value and the salt together. The root still recomputes, so every other field verifies untouched, and — crucially — the withholding is visible as a withholding rather than as an absence. A recipient can see that a field exists, what it is called, and that it was not shown.

That last clause hides a subtlety that took a second review to surface. The path is committed, inside the leaf. But a verifier holding a withheld field has neither the value nor the salt, and so cannot recompute that leaf — which means it cannot check the path either. The label is therefore unverified, and a discloser can relabel it:

what the recipient is shown
  auditRef       withheld      leaf = 8b5652140e0a0c83…

what was actually committed
  contractRef    withheld      leaf = 8b5652140e0a0c83…   ← same leaf

The verifier confirms the record — and in doing so confirms a false answer to the one question a redacted record exists to answer: what was withheld? "A routine audit reference" and "a commercial contract reference" are different disclosures, and the construction as described cannot tell them apart.

The fix is a second, separate commitment carried by every withheld field:

pathCommitment(path) = SHA-256( 0x03 ‖ u32be(len P) ‖ P )

Distinct prefix, same length discipline, and independently checkable without the salt. A verifier now confirms the label of a field whose value it cannot see, which is exactly the right amount of knowledge to give it.

§6The second tree: over records, doing a different job

The tree in §3 protects the inside of one record. A second tree, built over records rather than fields, protects a record's place in history — and conflating the two is a reliable source of confusion.

Over the second tree, two proofs matter, and they answer different questions:

• Inclusion. Given a record and roughly log₂(n) sibling hashes, anyone can recompute the published root. This proves the record belongs to the log without revealing any other record. For disclosure that is the whole game: the volume you hand over is set by relevance rather than by the shape of your storage, and it grows with the logarithm rather than the count.
• Consistency. Given an earlier root and the current one, a proof that the earlier tree is a prefix of the current one — that records were appended and none of the earlier ones were edited, reordered or removed between two observations. This is what turns "here is a root" into "here is a root that still contains the one you were given last quarter".

§7Two details of RFC 6962 that implementations get wrong

Both trees use the Certificate Transparency construction rather than a hand-rolled one, and there are two places where a plausible-looking implementation is subtly different — both of which have caused real vulnerabilities.

Domain separation between leaves and nodes

A leaf is SHA-256(0x00 ‖ data); an interior node is SHA-256(0x01 ‖ left ‖ right). Without those prefixes, a value that is an interior node in one reading can be presented as a leaf in another, and two different record sets can be made to share a root. The prefixes cost one byte and remove the entire class.

Odd nodes are promoted, never duplicated

When a level has an odd number of nodes, the common shortcut is to duplicate the last one so it can be paired. RFC 6962 does not do this: it splits at the largest power of two strictly less than n, which promotes the unpaired node up a level unchanged. The difference is not cosmetic. Duplicating the final node makes distinct trees collide — a tree of n leaves can be made to produce the same root as a tree with the last leaf repeated. This is the defect catalogued as CVE-2012-2459, and it is the reason a tree implementation should be checked against the RFC rather than written from the diagram.

One further value worth pinning: the root of the empty tree is SHA-256 of the empty string. Implementations disagree here more often than anywhere else, usually by returning zero or by treating it as undefined, and it is the first vector any cross-implementation corpus should contain.

§8What is deliberately not decided here

The construction commits to top-level fields. That is the shallowest granularity that satisfies the requirement, and it is a choice rather than a necessity: a deeper one — a leaf per nested path, or per array element — is equally implementable and gives finer redaction at the cost of a larger disclosure and a more complex proof.

Which granularity is right depends on what records contain, and what records contain is a product decision, not a property of the construction. These notes deliberately stop at the boundary. Likewise absent: any opinion about field naming, event taxonomy or classification. A construction that is indifferent to its payload can be reused; one that encodes a schema cannot.