RFC 6962 tree profile, revision 2

This document fixes the Merkle tree that Tzun's logs use, the inclusion and consistency proofs over it, the way hashes and sizes are written, and the rules of a growing log, including the evidence log of each chain. The tree is the tree of RFC 6962 §2.1, unchanged, over leaves of 32 bytes.

Anchor builds on it: checkpoint bodies, origins, the anchor log, the published value, the publications and the record artifact that carries these proofs are defined there.

Tag. In a record artifact, "merkleSpec": "rfc6962" names §3 to §6 of this document (Anchor §8.1).

Revision. This is revision 2 of the profile.

Requirement keywords (MUST, MUST NOT, REQUIRED, SHOULD, SHOULD NOT, MAY) have their BCP 14 meaning only when written in capitals; Specs sets out the conventions shared by every part.

Vectors. In the conformance vectors (Vectors), merkle-rfc6962-vectors.json pins the tree hash, leaf hashes, audit paths, the distinctness rule and the root of the empty tree. merkle-consistency-vectors.json pins consistency proofs, their edge rules, the hash encoding and the census of §3.6. §9 states what conformance to them means.

0. Versions

• Specs states whether this revision is frozen. Once it is, it is never edited: a change to the tree, to a proof rule or to the encoding is made under a new merkleSpec value, and a change to a leaf rule under a new log kind (Anchor §2).
• Anchors under a test origin (Anchor §4.3.4) never fix a version.

1. Purpose

Tzun's claim for this layer is narrow and checkable: an auditor who holds a record, the published value of its epoch and a public view of where that value was published can confirm the record's position in its log with tree software Tzun did not write. That holds only if the tree is exactly a standard one. This document therefore adopts RFC 6962's tree without change, and adds only what the RFC leaves to each user: what a leaf is, how hashes are written, and what a proof does and does not establish.

2. Scope

Covered here:

• the Merkle Tree Hash, inclusion proofs and consistency proofs (§3);
• the encoding every reader and writer applies to hashes and sizes (§4);
• growing logs and the evidence log of each chain (§5);
• compact ranges, the state a log writer keeps between checkpoints (§5.5).

Covered in Anchor: checkpoint bodies and origins, the anchor log and its leaves, the published value P, publication kinds, the publisher manifest, the record artifact nonRepudiation.anchor, and the steps that verify an anchor.

Outside the scope of this profile:

1. Signed tree heads. A Tzun log states its head as a C2SP checkpoint body (Anchor §4), not as a Certificate Transparency STH.
2. Certificate Transparency's leaf structures (MerkleTreeLeaf, TimestampedEntry). A Tzun leaf is a 32-byte digest. Compatibility is claimed for the tree and its proofs only; §7 says exactly what that means.
3. What a digest is. An evidence leaf is integrity.canonicalDigest exactly as Record defines it. This document says only how digests are combined and where each one sits in a log.

3. The construction

Let D[n] = {d(0), d(1), …, d(n−1)} be an ordered list of n leaves. Each d(i) is 32 raw bytes. For an evidence leaf, those are the bytes obtained by decoding the hex of a record's integrity.canonicalDigest: the leaf is the 32 decoded bytes, never the 64 ASCII characters that spell them. Hashing the characters instead gives a different root at every size, a one-leaf tree included.

3.1 Merkle Tree Hash

MTH({})      = SHA-256()                                    the hash of the empty string
MTH({d(0)})  = SHA-256(0x00 ‖ d(0))                         a 33-byte input
MTH(D[n])    = SHA-256(0x01 ‖ MTH(D[0:k]) ‖ MTH(D[k:n]))    a 65-byte input, for n > 1,
               with k the greatest power of 2 below n

‖ joins raw bytes, with no separator and no length prefix. Leaves are never sorted: their order is the log's order of appending, and it changes the root.

MTH({}) is e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855. A Tzun log never takes the root of an empty tree (§5.4), but every implementation of the RFC agrees on this value, so the vectors pin it to confirm the hash function and the encoding before anything specific to Tzun is compared.

3.2 Computing the tree level by level

The recursive definition of §3.1 is normative. An implementation MAY compute the same root level by level, provided that when a level has an odd number of nodes, the last one is carried up to the next level unchanged and never paired with a copy of itself:

level ← [SHA-256(0x00 ‖ d) for each leaf d, in order]
while level has more than one node:
    next ← [SHA-256(0x01 ‖ level[j] ‖ level[j+1]) for j = 0, 2, 4, … while j + 1 < |level|]
    if |level| is odd: append level[|level| − 1] to next      carried up, not duplicated
    level ← next
root ← level[0]

This gives the same root as §3.1 at every size. Because the shape of the tree depends only on its size, two different lists of leaves never share a root through a duplicated last node, the ambiguity recorded as CVE-2012-2459.

3.3 Audit path (inclusion proof)

PATH(m, D[n]) is the audit path of RFC 6962 §2.1.1 for the leaf at index m:

PATH(0, {d(0)}) = {}                                  the empty path of a one-leaf tree
PATH(m, D[n])   = PATH(m, D[0:k]) : MTH(D[k:n])       when m < k
                = PATH(m − k, D[k:n]) : MTH(D[0:k])   when m ≥ k

where k is as in §3.1 and : appends one element. The path is ordered from the leaf end to the root end. Each element is a hash written under §4. No element says which side it joins on: a verifier works out the side of every step from the index of the leaf and the size of the tree.

3.4 Inclusion verification

This is the algorithm of RFC 9162 §2.1.3.2, which is normative here (RFC 6962 §2.1.1 defines the audit path but gives no algorithm for checking one). It climbs from the leaf towards the root, in the order the path is written:

verifyInclusion(leafDigest, leafIndex, treeSize, path, expectedRoot):
    if leafIndex ≥ treeSize: return false
    fn ← leafIndex
    sn ← treeSize − 1
    r  ← SHA-256(0x00 ‖ leafDigest)
    for each p in path, in order:
        if sn = 0: return false                      the path is longer than the tree allows
        if fn is odd or fn = sn:
            r ← SHA-256(0x01 ‖ p ‖ r)                r is a right child
            if fn is even:
                while fn ≠ 0 and fn is even: fn ← fn / 2;  sn ← sn / 2
        else:
            r ← SHA-256(0x01 ‖ r ‖ p)                r is a left child
        fn ← fn / 2;  sn ← sn / 2                    integer halving
    return sn = 0 and r = expectedRoot

The final test sn = 0 is required: it refuses a shortened path that happens to reach the right value. A verifier that walks down from the root instead of up from the leaf gets its first concatenation in the wrong order at n = 3.

3.5 Consistency proofs

A consistency proof shows that a log at size m is a prefix of the same log at size n.

Generation, RFC 6962 §2.1.2 (RFC 9162 §2.1.4.1), for 0 < m ≤ n:

PROOF(m, D[n])           = SUBPROOF(m, D[n], true)
SUBPROOF(m, D[m], true)  = {}
SUBPROOF(m, D[m], false) = {MTH(D[m])}
SUBPROOF(m, D[n], b)     = SUBPROOF(m, D[0:k], b) : MTH(D[k:n])          when m ≤ k
                         = SUBPROOF(m − k, D[k:n], false) : MTH(D[0:k])  when m > k
                           (k as in §3.1, for n > m)

The proof is an ordered list, innermost element first, each element a hash written under §4. PROOF(m, D[m]) is the empty list.

Verification, RFC 9162 §2.1.4.2, with Tzun's edge rules marked:

verifyConsistency(first, second, proof, firstRoot, secondRoot):
    if not (0 < first ≤ second): return false        Tzun: a proof from size 0 is always refused
    if first = second: return proof is empty and firstRoot = secondRoot
    if proof is empty: return false
    if first is a power of two: proof ← [firstRoot] followed by proof
    fn ← first − 1
    sn ← second − 1
    while fn is odd: fn ← fn / 2;  sn ← sn / 2
    fr ← proof[0];  sr ← proof[0]
    for each c in proof after the first element:
        if sn = 0: return false
        if fn is odd or fn = sn:
            fr ← SHA-256(0x01 ‖ c ‖ fr);  sr ← SHA-256(0x01 ‖ c ‖ sr)
            if fn is even:
                while fn ≠ 0 and fn is even: fn ← fn / 2;  sn ← sn / 2
        else:
            sr ← SHA-256(0x01 ‖ sr ‖ c)
        fn ← fn / 2;  sn ← sn / 2
    return fr = firstRoot and sr = secondRoot and sn = 0

Edge rules. The edgeRules and invalid entries of the consistency vectors pin each of them.

1. first MUST satisfy 0 < first ≤ second. A proof from size 0 is refused whether it is empty or not, and so is first = second = 0: a Tzun log is never published empty, and RFC 9162 defines no proof from the empty tree. Some libraries accept one (§9).
2. With first = second, a proof verifies only when it is empty and firstRoot = secondRoot.
3. With first < second, an empty proof is refused.
4. A proof of more than ⌈log₂(second)⌉ + 1 elements cannot verify. A verifier SHOULD refuse it by its length alone, before reading any element.

3.6 The one thing no proof authenticates: the tree size

A proof does not fix the size it was made for. To check a proof, a verifier rebuilds a root out of the path together with a size it has been given. When another size produces the same sequence of left and right steps, the computation is the same and the proof verifies again; nothing in the proof lets a verifier tell the two sizes apart. Over every honest proof whose larger size is at most 64 (the sizeMalleability section of the consistency vectors):

For inclusion, only the path of the last leaf, and of the second-to-last leaf in a tree of even size, fails under every other size. For consistency, only a log of odd size that grew by exactly one leaf pins the larger size.

Consequences.

• Every verifier takes sizes as explicit inputs, and those inputs MUST come from something authenticated: a checkpoint body whose digest is published (Anchor §6), or one that is signed.
• A bare root does not authenticate a tree. MTH does commit to the size, but no proof verifier recomputes MTH. That is why the value Tzun publishes is the digest of a checkpoint body, which states the size, rather than a root (Anchor §6). Certificate Transparency signs tree_size for the same reason.

4. Encoding

Every hash this document puts on the wire (leaf digests, roots, the elements of audit paths and of consistency proofs, and the hashes of a compact range) travels as a JSON string holding 64 hex digits, no more and no fewer.

• A writer MUST write lowercase ([0-9a-f]{64}).

• A reader MUST accept uppercase and mixed case, and MUST treat two spellings of the same bytes as equal, for instance by lowercasing before any comparison. Hashing always uses the decoded bytes, so case never changes a value.

• A reader MUST refuse any other spelling: a 0x prefix, 63 digits or 65, whitespace before or after, a newline at the end, or a value of another JSON type (a number, null, an object). A refused hash makes the proof it belongs to fail. It is never repaired.

• The whole string must match. A regular expression used for this MUST be anchored at both ends of the value. In Python, re.fullmatch does this, while re.match with $ also matches before a trailing newline.

• A proof is a JSON array. null is not an empty proof, and a single element that is not a valid hash makes the whole proof fail.

• Sizes and indices are integers from 0 to 2^53 − 1. A writer MUST write them with no fraction and no exponent. A reader applies these rules to the number's value:

  • a JSON boolean is never an integer (in Python, isinstance(True, int) is true, so the type has to be checked exactly);
  • a number whose value is integral reads as that integer: 3.0 and 1e0 read as 3 and 1, and -0 as 0, since a JavaScript reader cannot tell them apart from 3, 1 and 0;
  • a negative value, a fraction, and a value above 2^53 − 1 (such as 2^53) are refused.

  A reader that decodes JSON straight into a native integer type (Go's encoding/json refuses 41.0 for an int) decodes the number first and then applies these rules.

The encoding section of the consistency vectors pins the hash rule, with 6 spellings that MUST be accepted and 11 that MUST be refused, all with integer sizes. No vector file pins the integer rule; an implementation tests it with at least 3.0, 1e0 and -0 (read as 3, 1 and 0), 2^53 − 1 (accepted), and true and 2^53 (refused).

5. Logs

5.1 Growing logs

• A log is an append-only, ordered list of distinct 32-byte leaves. At size n its state is D[n], its first n leaves, and its root is MTH(D[n]).
• A log is never closed. Successive batches are successive sizes of one log, not separate trees. Each epoch commits to a later size of the same log, and committed sizes that follow one another are joined by a consistency proof (§3.5).
• A leaf never changes. Once a leaf is at index i, no writer rewrites, reorders or removes it. A leaf exists at i only if one exists at i − 1, so a log has no gaps.
• Every log uses this document's tree and proofs, and its kind fixes its leaf rule. A different leaf rule needs a different kind, never an edit to an existing one. A new kind that is kept per chain also needs a new anchorSpec, because tzun-anchor/1 gives a chain segment only to evidence (Anchor §4.3.1) and checks a record against the evidence leaf rule (Anchor §10.3 step 4).

Anchor defines two kinds: evidence (§5.2) and anchors (Anchor §5). A domain may anchor logs of other kinds; this revision defines no leaf rule for them beyond the preimage rule of §5.2 (Anchor §3).

5.2 The evidence log of a chain

Every evidence chain has a log of its own.

• A record commits to its own position. sequenceNumber is one of the hashed fields of the record (Record §4.1), so canonicalDigest binds leafIndex, and reordering or truncating a chain can be detected chain by chain.
• A leaf is fixed once written. Storing a record again never replaces its leaf. A record that no longer matches its leaf is therefore a finding about the record, never a new leaf.
• A leaf only for a stored record. A writer appends an evidence leaf only as a copy of the record it stores at that position: the record's evidence id, chain, sequenceNumber and canonicalDigest.
• Leaves of other kinds are never record digests. A writer computes every leaf of a source log whose kind is not evidence (Anchor §3) as the SHA-256 of a preimage that can never be a record's canonical bytes. A record's canonical bytes are a JSON object, which begins with { and holds no LF byte (Record §3.4); a preimage meets this rule when it begins with a fixed ASCII tag that ends in LF, such as tzun-<kind>/<n> followed by LF, or with a length prefix whose first byte is a decimal digit or -. Where a verifier cannot read a log's kind from its origin (Anchor §4.3.3), this rule is what keeps a leaf of another kind from verifying as a record's leaf.
• What an anchor over a leaf claims. An anchor proves that a digest sat at index s of the log by a time. That the digest is the one first captured at that position rests on how the store wrote the leaf, not on the anchor: a store that already held records when its logs were created takes their leaves from the records' digests at that moment, and an anchor over such a leaf shows only that the digest was at that index by that time.

5.3 Proofs over a log

A log writer MUST verify each consistency proof it generates, using a verifier implemented separately from the generator, before it stores or publishes the proof, so that a fault in the generator cannot vouch for its own output.

5.4 Constraints

1. The leaves of one log MUST be distinct. Evidence digests are distinct by construction, since the hashed fields of a record include its evidence id and its sequence number, so this refuses nothing honest. Building a tree over a list with a repeated leaf MUST fail rather than produce a tree whose set of leaves a reader could misread. Extending a compact range (§5.5) cannot see the leaves already behind it, so it MUST refuse a repeat among the leaves it adds, and the log writer MUST keep leaves distinct across the whole log, for example with a uniqueness constraint on the stored leaves.
2. No root is taken of an empty log. A committed size is at least 1, and building a tree over no leaves fails.
3. A log of size 1 has an empty inclusion proof. PATH(0, {d(0)}) is empty and the root is the leaf's hash, so "this digest is in the log" amounts to "this digest is the log". For an evidence log this happens only for the first record of a chain, in a checkpoint of size 1. A verifier reports the position ("record 1 of 1").

5.5 Compact ranges

A log writer extends a log from its stored state and the new leaves, without the old leaves.

• Definition. For a log holding n leaves, the compact range lists the roots of the perfect subtrees that together cover the leaves [0, n), largest (leftmost) first. It holds one hash per set bit of n, and the compact range of the empty log is the empty list.

• Root. The root of a non-empty log folds its compact range from the right:

  h ← hashes[last]
  for i from last − 1 down to 0: h ← SHA-256(0x01 ‖ hashes[i] ‖ h)
  

• Extension. From the compact range at size m and the leaves [m, n), a writer obtains the root at n, the compact range at n, PROOF(m, D[n]), and PATH(j, D[n]) for every m ≤ j < n. Root, range and PROOF together take O((n − m) + log n) hashes, each inclusion path adds O(log n), and no table of interior nodes is needed.

• Storage. A compact range is stored as { size, hashes }, with hashes written under §4. It is the writer's private state, appears in no published artifact, and is never needed to verify one.

6. What a valid proof does and does not establish

An inclusion proof establishes one thing: d(m) is at index m among the n leaves that produce the root. A consistency proof establishes that the log at size m is a prefix of the log at size n, given both roots.

Neither establishes:

• the size (§3.6);
• that the root was ever published. A root that arrives inside the artifact under examination is whatever the holder of the artifact chose. Only a checked publication (Anchor §7) shows that it was published.

A verdict therefore reports the two separately:

• merkleProofValid reports the two inclusion steps of Anchor §10.3 (the record inside its evidence log; the evidence log's checkpoint inside the anchor log);
• anchorValid and anchorReason report the anchor as a whole, publications included. Proofs that hold with no publication checked give anchorValid: null, never true.

6.1 An abstention is not a verdict, and a consumer may raise it

A verifier that cannot read a construction reports anchorValid: null, the same value it uses when no anchor is attached and when an anchor was not checked against its publication, and anchorReason says which. false means "decided, and it fails", and MUST NOT be used for a rule the verifier does not implement.

Two consequences are easy to get wrong:

1. An abstention is never turned into absence. When a record holds an anchor that cannot be read, it is not waiting for one: something was attached. Reporting it as pending would make a retry treat a written artifact as if it had never existed.
2. A monitoring consumer should raise what the verifier holds back. A verifier states what it knows; a monitor exists to notice that stored evidence can no longer be verified. A monitor therefore MUST raise the reasons unsupported_merkle_spec, unsupported_anchor_spec and legacy_blockchain_anchor as findings, even though each verdict is an abstention, and MUST NOT raise publication_not_checked or a record's waiting for its epoch, which are the ordinary state of a deployment with no header source and would only be noise (Anchor §10.10).

7. What "CT-compatible" means here

It means that the tree is byte for byte the tree of RFC 6962, so an auditor can check an inclusion or consistency proof with a widely reviewed library written by someone else, such as transparency-dev/merkle (proof.VerifyInclusion, proof.VerifyConsistency), the merkle package of certificate-transparency-go, Trillian's verifier, or Sigstore Rekor's. For inclusion they pass the leaf hash, the leaf index, the tree size, the path and the root. They do not need to run, read or trust any code of Tzun's to do it.

It does not mean that an off-the-shelf Certificate Transparency client works with Tzun evidence. Such clients speak the log API of Certificate Transparency and expect its leaf structures, while a Tzun leaf is a 32-byte digest and a Tzun log head is a C2SP checkpoint body whose digest is published (Anchor). What carries over is the proof algorithm, not the transport.

A statement of this property should keep the two apart: "verifiable with standard tools" is true; "works with a CT verifier out of the box" is not.

7.1 RFC 9162

RFC 9162 (Certificate Transparency version 2.0) succeeds RFC 6962 and does not change the Merkle tree. RFC 9162 §2.1.1 defines MTH({d[0]}) = HASH(0x00 || d[0]), MTH(D_n) = HASH(0x01 || MTH(D[0:k]) || MTH(D[k:n])) with k the largest power of two smaller than n, and MTH({}) = HASH(), which is §3.1 of this document; the RFC describes its differences from RFC 6962 as clarifications and editorial work. The tree is therefore identical under both.

That is the whole of the overlap. Tzun is not compliant with RFC 9162, which would mean operating a Certificate Transparency log: its HTTP endpoints, signed certificate timestamps, signed tree heads, declared signature algorithms, precertificate handling, the transparency_info TLS extension and the X.509 transparency information extension. None of that is implemented, and none of it applies to evidence records. The leaves differ as well: an RFC 9162 leaf is a TransItem, while a Tzun leaf is a digest. The tree function is the same; its inputs are Tzun's.

The accurate statement is: inclusion and consistency proofs use the Certificate Transparency Merkle tree (RFC 6962 §2.1, unchanged in RFC 9162 §2.1.1), so standard CT tree libraries can verify them in place of software Tzun wrote.

8. Legacy artifacts

• The record artifact is nonRepudiation.anchor (Anchor §8). The member nonRepudiation.blockchainAnchor is a legacy form that no writer populates. A verifier that finds it without anchor abstains with legacy_blockchain_anchor, whatever it contains, so a legacy path is never read under this profile's rules.
• Nothing in this document is written on chain. What is published is the digest of the anchor log's checkpoint body, which states the origin, the size and the root (Anchor §6).
• Within nonRepudiation.anchor, a missing or unknown merkleSpec abstains with unsupported_merkle_spec (Anchor §10.3 step 1), and a path element that is not a hash under §4, such as one containing ":", is false, malformed_merkle_path (step 2).
• Reading a path never throws. A value that is not an array, an element that is not a string, and a string that breaks §4 are each reported as a malformed path, never raised as an error.

9. Conformance

An implementation conforms when, for every entry of merkle-rfc6962-vectors.json:

1. MTH over leafDigests equals root;

2. the leaf hash of d(i) equals leafHashes[i];

3. PATH(m, D) equals proofs[m].auditPath;

4. §3.4 returns true for every listed proof, and false when any one byte of the leaf, the root or any element of the path is changed;

5. the two roots of distinctnessVectors differ; an implementation for which they are equal duplicates the last node and does not conform.

   Root distinctness is a property of MTH (§3.1), and the vectors pin it. Refusing to build a tree over repeated leaves is a property of tree construction (§5.4). A conforming implementation reproduces distinctnessVectors.a.root and refuses to build a tree over distinctnessVectors.b.leafDigests; it offers no way around that refusal just to meet this item. b.root is the value the hash rule gives that list of leaves, not an output any Tzun code path is expected to produce;

6. MTH({}) equals emptyTreeRoot.root;

and, for every entry of merkle-consistency-vectors.json:

7. every entry of valid verifies under §3.5, and a generator reproduces its proof exactly from leafDigests[0:second];
8. every entry of invalid is refused;
9. every entry of encoding has the outcome its verifies member states (§4);
10. an implementation that keeps compact ranges (§5.5) produces, for every 0 ≤ m ≤ n ≤ 64, the same root, range and proofs as a computation from all the leaves.

What the consistency vectors hold. valid holds every pair 0 < first ≤ second ≤ 16, and chosen pairs up to 64 on either side of each power of two: 237 proofs. invalid holds 426 cases. Its mutations (each proof element and each root with one bit flipped, sizes swapped, proofs shortened and lengthened, equal sizes with a non-empty proof or with different roots) are applied to all valid pairs whose second size is at most 8, and to 11 larger pairs, and the cases with first = 0 and with first > second are added separately. Flipping every bit of every pair belongs in an implementation's own tests rather than in the file. sizeMalleability documents §3.6 and is not a conformance requirement.

Libraries. transparency-dev/merkle at its tag v0.0.2 accepts five of the 426 invalid entries: the four proofs from first = 0 with an empty proof, and the case first = second = 0, because its check for equal sizes runs before its check for size 0. Its commit fbbcd741 (v0.0.3-0.20260921095310-fbbcd741c3d1) refuses all 426. An implementation built on a library that accepts a proof from size 0 MUST apply edge rule 1 of §3.5 itself.