[SCITT] Review of draft-fassbender-scitt-time-anchor-02: Appendix D.3 Merkle construction, Section 3 verification independence

[Tiago Pinto <[e-mail]>]

Hi all,

I read draft-fassbender-scitt-time-anchor-02 with interest. The core design decision, making the block-height binding the normative temporal value and demoting block.time(H) to an informative "Reference Wall-Clock Projection", is a genuinely useful clarification, and I think the two-layer model in Section 2.6.6 deserves to survive into whatever this document becomes.

I have two substantive comments, each with a proposed fix, and a short list of editorial nits at the end.

1. The Merkle construction in Appendix D.3 is ambiguous and does not match the standard it cites
------------------------------------------------------------------------------------------------

The pseudocode in D.3 step 2 admits at least three computable readings that produce different roots for the same input:

(a) The comment in step 2c states that level elements are hex-encoded strings and that concatenation is hex-string concatenation hashed as ASCII. Sustaining that reading across levels requires re-encoding each SHA-256 output to hex, an operation the pseudocode does not contain.

(b) Read literally, SHA-256 returns bytes, so from level 1 upward the elements are raw digests, contradicting the step 2c comment. With an odd number of leaves this reading is not even executable: the promoted element is a string while its future sibling is bytes, and SORT fails on the mixed comparison.

(c) An implementer who decodes the hex leaves to bytes from the start, precisely the "second implementer" the draft warns about, obtains a third root.

Using the four artifact hashes from the draft's own Appendix E as leaves, the three readings plus the reference construction give four distinct roots:

    reading 1 (hex domain): sha256:ddef9f3ceb2ace663e73816411f70f457ae00b902d10cf42bedc51c9110fafd5
    reading 2 (literal) : sha256:d73fad1e08deeca96ce4a5e5b1f29cfd67de38892188747fceb5237226305a65
    reading 3 (raw bytes) : sha256:2fe59137748168c77130988bc3015088493f53f70c56fd0fcfeb4928a25e8c6e
    RFC 6962 2.1 MTH : sha256:f461f2de3ad4cf3880fd26eadb0f09326a523221d0df20b71cfafde11ae8fa6b

A self-contained reproduction script is included at the end of this message.

Two related issues:

First, step 2 cites [RFC9162] Section 2.1, but the construction differs structurally from the Merkle Tree Hash defined there (a smaller point: the MTH is defined in Section 2.1.1; Section 2.1 itself contains no construction). The differences: it sorts each sibling pair lexicographically (the MTH preserves leaf order), it omits the 0x00/0x01 leaf and node prefixes, it hashes ASCII hex rather than raw bytes, and it pairs sequentially rather than splitting at the largest power of two less than n. Whatever construction is intended, citing RFC 9162 for it is misleading, and dropping the leaf/node prefixes removes a stated security property: RFC 9162 notes that this domain separation is "required to give second preimage resistance".

Second, Section 6.12 states that the batch integrity threat "is remediated by the Batch Anchoring algorithm (Appendix D.3), which specifies deterministic leaf ordering (lexicographic sort before concatenation)". The algorithm sorts pairs, not the leaf list, so input order still changes the root. Over all 24 permutations of the same four leaves, reading (a) produces 3 distinct roots. The remediation claimed in 6.12 is therefore not provided by the algorithm as written.

Proposed fix: specify the RFC 6962 Section 2.1 MTH verbatim, over raw byte leaves, as the batch construction. That single change resolves the encoding ambiguity, restores domain separation, makes the RFC 9162 citation accurate, and, if combined with sorting the full leaf list once before tree construction (or, alternatively, dropping the determinism claim from 6.12 and making the per-leaf .ots proof carry the ordering), makes Section 6.12 true. If a custom construction is preferred instead, it needs a complete byte-level specification plus test vectors that include the intermediate tree, not only the leaves.

2. Section 3.1 does not deliver the verification independence that Section 3.2 claims
-------------------------------------------------------------------------------------

Section 3.2 and Figure 3 state that a conformant verifier needs only the artifact bytes, the .ots proof, and Bitcoin block headers ("Only Bitcoin block headers needed"). Section 1.3 likewise notes that block headers are sufficient. The algorithm in Section 3.1, however, does something different:

- Step 6 requires fetching the full Bitcoin transaction and comparing its OP_RETURN output. That is transaction data, not header data.
- No step verifies an SPV inclusion proof of that transaction against the merkle root in the block header, and no step validates the header chain or its proof of work. A verifier using a block explorer, which the text explicitly permits, is trusting the explorer for block inclusion. The effective trust root becomes the data source, not Bitcoin consensus.
- No step checks confirmation depth, although Section 6.2 states that "The Verification Algorithm (Section 3.1) requires a minimum confirmation depth before accepting an anchor as valid", and the k >= 6 requirement in Section 1.3 exists only as a producer-side promotion rule, which Section 6.11 itself says the verifier must not rely on. As written, a conformant verifier returns "valid" for a commitment in a block with one confirmation.

Note also that step 6 cannot be executed against a pruned full node, which discards old transaction data while retaining all block headers; header-based verification has no such limitation.

I want to stress that the independence property itself is achievable, and the OTS reference implementation the draft builds on already achieves it: a completed Bitcoin attestation resolves the commitment path to the transaction Merkle root of the block, which is then compared against the merkle root field of the block header. Header-only verification is how the underlying protocol actually works; it is also the simplified payment verification model described in section 8 of the Bitcoin whitepaper that the draft already cites as [NAKAMOTO].

Proposed fix: align Section 3.1 with that behavior. Replace the FETCH-TX/OP_RETURN comparison with resolution of the proof path to the block's transaction Merkle root and comparison against the header, add an explicit confirmation-depth check with a stated minimum, and state the header-source assumptions (local full node, header chain with validated proof of work, or an explicitly trusted header cache). With those changes the strong claims in Section 3.2 and Figure 3 become true of the algorithm rather than of the surrounding prose.

Editorial nits
--------------

- Section 5.2, Assumption A4 points to "Section 5.2.1", which does not exist.
- Section 5.3 refers to "the security argument of Section 5.3"; presumably Section 5.4 is meant.
- Section 7 cites "(Section 2.6.3, Assumption A3)"; A3 is defined in Section 2.6.2, and A3 itself states that it does not depend on any timestamp field.
- The four numbered requirements in Section 2.5 all render as "1.".

Reproduction script
-------------------

    #!/usr/bin/env python3
    # Reproduction: ambiguity of BATCH-ANCHOR step 2 (Appendix D.3),
    # draft-fassbender-scitt-time-anchor-02. Leaves are the four
    # artifact hashes from Appendix E (E.1 to E.4).
    import hashlib, itertools

    LEAVES = [
     "781bb71a88c82d1f009178d3e2a48fba5023f52f510553ce74bf8d64db9985dd",
     "67b86bc99ad01edf7351610f57291d2884c20309bf3355fbc4020b6426eaa6be",
     "644f84d34a4dd97a6ce3e8dfd9c73adb7ba2d97bd98d92adbeb38d2e3780e70d",
     "367a1cf0f5e5c80dceea6564c440b7a499e273e5673be8833524bfc867ec7583",
    ]
    H = lambda b: hashlib.sha256(b).digest()

    def root_hex(leaves): # reading 1: hex-string domain at every level
        level = list(leaves)
        while len(level) > 1:
            nxt = []
            for i in range(0, len(level), 2):
                if i+1 < len(level):
                    a, b = sorted([level[i], level[i+1]])
                    nxt.append(hashlib.sha256((a+b).encode()).hexdigest())
                else:
                    nxt.append(level[i])
            level = nxt
        return "sha256:" + level[0]

    def root_literal(leaves): # reading 2: literal (SHA-256 returns bytes)
        level = list(leaves)
        while len(level) > 1:
            nxt = []
            for i in range(0, len(level), 2):
                if i+1 < len(level):
                    a, b = sorted(level[i:i+2])
                    data = (a+b).encode() if isinstance(a, str) else a+b
                    nxt.append(H(data))
                else:
                    nxt.append(level[i])
            level = nxt
        r = level[0]
        return "sha256:" + (r.hex() if isinstance(r, bytes) else r)

    def root_bytes(leaves): # reading 3: raw bytes at every level
        level = [bytes.fromhex(x) for x in leaves]
        while len(level) > 1:
            nxt = []
            for i in range(0, len(level), 2):
                if i+1 < len(level):
                    a, b = sorted(level[i:i+2])
                    nxt.append(H(a+b))
                else:
                    nxt.append(level[i])
            level = nxt
        return "sha256:" + level[0].hex()

    def mth(l): # RFC 6962 Section 2.1 MTH, leaves = raw bytes
        if len(l) == 1:
            return H(b"\x00" + l[0])
        k = 1
        while k*2 < len(l):
            k *= 2
        return H(b"\x01" + mth(l[:k]) + mth(l[k:]))

    print("reading 1 (hex domain):", root_hex(LEAVES))
    print("reading 2 (literal) :", root_literal(LEAVES))
    print("reading 3 (raw bytes) :", root_bytes(LEAVES))
    print("RFC 6962 2.1 MTH :", "sha256:" + mth([bytes.fromhex(x) for x in LEAVES]).hex())
    roots = {root_hex(p) for p in itertools.permutations(LEAVES)}
    print("distinct roots over all 24 leaf-order permutations:", len(roots))

Best regards,
Tiago Pinto