Certificate Transparency Proofs

This document specifies the Certificate Transparency proof formats clients use to verify the ENC enclave event log without trusting the node: CT inclusion and consistency proofs for the log itself, bundle membership proofs that tie individual events to a CT leaf, and the Signed Tree Head (STH) the sequencer publishes as the trust root. SMT membership / non-membership proofs (for current enclave state) are specified separately in smt.md.

Table of Contents

1. Overview
2. CT Proofs
3. Wire Format (JSON)
4. Bundle Construction (RFC 9162)

Overview

The ENC protocol uses two types of Merkle proofs:

These Merkle proofs prove inclusion against a root the client already trusts. To instead prove that a root transition old_root → new_root is itself valid under the RBAC rules — letting a client trust a fresh state_hash in O(1) without replaying the log — see the zero-knowledge validity-proof layer in zk.md. For proofs of current enclave state against a known state_hash, see smt.md.

CT Proofs

Bundle Membership Proof

Proves that an event is part of a specific bundle.

{
  event_id: <32 bytes>,
  bundle_index: <number>,
  bundle_size: <number>,    // total event count in the bundle; needed for odd-size promotion
  siblings: [<hash>, ...]
}

Where:

• event_id — the event being proven
• bundle_index — position of event within the bundle (0-indexed)
• bundle_size — total number of events in the bundle (>= 1); used by the verifier to detect odd-leaf promotion at each layer
• siblings — Merkle proof siblings from event_id to events_root, in leaf-to-root order (siblings[0] is the deepest sibling). Carried (odd-promoted) leaves contribute NO sibling at the layer where they were carried up.

hash       = event_id
index      = bundle_index
n          = bundle_size
sib_i      = 0
while n > 1:
    if index == n - 1 and (n % 2 == 1):
        # Odd promotion — last leaf at an odd-sized layer is carried up
        # unchanged. No sibling consumed; no hash step at this layer.
        pass
    else:
        s = siblings[sib_i]; sib_i += 1
        if index % 2 == 0:
            hash = H(0x01, hash, s)         # current is left child
        else:
            hash = H(0x01, s, hash)         # current is right child
    index = index >> 1
    n     = (n + 1) >> 1                    # ceil(n / 2) — size of next layer
require sib_i == siblings.length            # no excess siblings
require hash == events_root

• bundle_index is the event's 0-indexed position within the bundle.
• The LSB of index determines left (0) or right (1) at each level.
• After each layer, shift index right and recompute n = ceil(n/2) for the next layer's size.
• The odd-promotion check (index == n - 1 and n % 2 == 1) reflects the RFC 9162-style root construction: when a layer has an odd number of nodes, the rightmost node is carried up to the next layer unchanged (no node_hash applied).Reference: computeEventsRoot and the parity-matching Rust at.
• Siblings are ordered leaf-to-root; the verifier consumes siblings[0] at the deepest non-promoted layer.

Bundle with 4 events, verifying event at bundle_index = 2, bundle_size = 4:

        events_root
           /    \
         h01    h23
        /  \   /  \
       e0  e1 e2  e3   ← bundle_index: 0, 1, 2, 3

• Start: hash = e2, index = 2, n = 4, sib_i = 0
• Layer 0 (n=4): index=2, n-1=3, not last. LSB(2)=0 → hash = H(0x01, hash, siblings[0]) where siblings[0] = e3. sib_i=1, index=1, n=2.
• Layer 1 (n=2): index=1, n-1=1, IS last but n=2 is even — not odd promotion. LSB(1)=1 → hash = H(0x01, siblings[1], hash) where siblings[1] = h01. sib_i=2, index=0, n=1.
• Loop ends. hash == events_root. siblings = [e3, h01] (length 2).

Bundle with 3 events, verifying event at bundle_index = 2, bundle_size = 3:

        events_root = H(0x01, h01, e2)
            /    \
          h01     e2     ← layer 1: e2 carried up
         /  \    /
        e0  e1  e2       ← bundle_index: 0, 1, 2

• Start: hash = e2, index = 2, n = 3, sib_i = 0
• Layer 0 (n=3): index=2 == n-1=2 AND n is odd → ODD PROMOTION, no sibling consumed. index=1, n=2.
• Layer 1 (n=2): index=1, n-1=1, last but n=2 even — normal. LSB(1)=1 → hash = H(0x01, siblings[0], hash) where siblings[0] = h01. sib_i=1, index=0, n=1.
• Loop ends. hash == events_root. siblings = [h01] (length 1).

With bundle_size = 1, the bundle contains one event, the loop body never runs, siblings == [], and events_root == event_id.

CT Inclusion Proof

Proves that a bundle exists at a specific position in the log.

{
  tree_size: <uint64>,
  leaf_index: <uint64>,
  path: [<hash>, ...]
}

Where:

• tree_size — number of bundles in the tree when proof was generated
• leaf_index — 0-based position of the bundle in the log
• path — sibling hashes from leaf to root

leaf_hash = H(0x00, events_root, state_hash)

Where events_root is the Merkle root of event IDs in the bundle, and state_hash is the SMT root after the bundle.

1. Set fn = leaf_index, sn = tree_size - 1, r = leaf_hash
2. For each p in path:
   • a. If sn == 0: FAIL (proof too long)
   • b. If LSB(fn) == 1 or fn == sn:
     • r = H(0x01, p, r)
     • While LSB(fn) == 0 and fn != 0: fn >>= 1; sn >>= 1
   • c. Else:
     • r = H(0x01, r, p)
   • d. fn >>= 1; sn >>= 1
3. Verify sn == 0 and r == expected_root

Tree size: 7, Leaf index: 5
Initial: fn=5, sn=6
 
Step 1 (p[0]): LSB(5)=1 → r=H(0x01,p[0],r), shift → fn=2, sn=3
Step 2 (p[1]): LSB(2)=0, fn≠sn → r=H(0x01,r,p[1]), shift → fn=1, sn=1
Step 3 (p[2]): fn==sn → r=H(0x01,p[2],r), shift → fn=0, sn=0
 
Final: sn=0 ✓, compare r to expected_root

1. Single-element tree (tree_size = 1, leaf_index = 0):
   • Initial: fn = 0, sn = 0
   • path is empty (no siblings)
   • Skip the loop and verify r == expected_root directly
2. Leaf at last position (leaf_index = tree_size - 1):
   • Valid case; algorithm handles via fn == sn condition

CT Consistency Proof

Proves that an earlier log state is a prefix of the current state.

{
  tree_size_1: <uint64>,
  tree_size_2: <uint64>,
  path: [<hash>, ...]
}

Where:

• tree_size_1 — size of the older (smaller) tree
• tree_size_2 — size of the newer (larger) tree
• path — sibling hashes proving consistency

Precondition: tree_size_1 <= tree_size_2. If tree_size_1 > tree_size_2, reject with INVALID_RANGE error immediately.

1. If tree_size_1 == tree_size_2: verify path has 1 element equal to both roots
2. If tree_size_1 is a power of 2: prepend first_hash to path
3. Set fn = tree_size_1 - 1, sn = tree_size_2 - 1
4. While LSB(fn) == 0: shift both fn and sn right by 1
5. Set fr = path[0], sr = path[0]
6. For each c in path[1:]:
   • If sn == 0: FAIL
   • If LSB(fn) == 1 or fn == sn: set fr = H(0x01, c, fr), sr = H(0x01, c, sr), then while LSB(fn) == 0 and fn != 0: shift both right by 1
   • Else: set sr = H(0x01, sr, c)
   • Shift both fn and sn right by 1
7. Verify fr == first_hash, sr == second_hash, and sn == 0

Based on RFC 9162 Section 2.1.4.

Signed Tree Head (STH)

The sequencer signs the CT root periodically to create a checkpoint.

{
  t:   <timestamp>,
  ts:  <tree_size>,
  r:   <root_hash>,
  sig: <signature>
}

Where:

• t — Unix milliseconds when STH was generated
• ts — number of bundles in the tree
• r — CT root hash (32 bytes)
• sig — Schnorr signature over the STH

message = "enc:sth:" || be64(t) || be64(ts) || r
sig = schnorr_sign(sha256(message), seq_priv)

Where r is the raw 32-byte root hash (NOT hex-encoded). The message is binary concatenation:

• "enc:sth:" = 8 bytes UTF-8
• be64(t) = 8 bytes big-endian
• be64(ts) = 8 bytes big-endian
• r = 32 bytes raw

Total: 56 bytes before SHA-256.

{
  "t": 1706000000000,
  "ts": 1000,
  "r": "<hex64>",
  "sig": "<hex128>"
}

1. Reconstruct message: "enc:sth:" || be64(t) || be64(ts) || hex_decode(r)
2. Verify: schnorr_verify(sha256(message), sig, seq_pub)

Full Event Proof

To fully prove an event exists and verify its state:

1. Bundle membership proof — proves event_id is in bundle's events_root
2. CT inclusion proof — proves bundle is in CT tree
3. SMT proof — proves state claim against bundle's state_hash

This two-level structure allows efficient bundling while maintaining per-event verifiability.

Wire Format (JSON)

The normative wire format is JSON.

CT Inclusion Proof

{
  "ts": 1000,
  "li": 42,
  "p": ["<hex>", ...]
}

CT Consistency Proof

{
  "ts1": 500,
  "ts2": 1000,
  "p": ["<hex>", ...]
}

Bundle Membership Proof

{
  "ei": 2,
  "s": ["<hex>", ...]
}

Note: With bundle.size = 1, the bundle contains one event, so s is empty and ei is 0.

Note: Wire format omits event_id as the verifier already knows the event being proven from request context. For self-contained proofs (e.g., archival), include event_id separately.

Bundle Construction (RFC 9162)

How the sequencer assembles events into CT leaves and grows the append-only Merkle tree. Follows RFC 9162.

• CT root: Single hash representing the entire event history AND state
• Inclusion proof: Proves a specific event exists at a given position in the log
• Consistency proof: Proves an earlier log state is a prefix of the current state

Events are grouped into bundles (see spec.md §Bundle Configuration). Each bundle produces one CT leaf.

bundle = {
  events: [event_id_0, event_id_1, ..., event_id_N],
  state_hash: <SMT root after last event in bundle>
}

Before any events (including Manifest), the SMT is empty:

empty_state_hash = sha256("")
                 = 0xe3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855

The Manifest event is always in bundle 0. The bundle's state_hash is the SMT root AFTER Manifest's init entries have been applied.

events_root = merkle_root(events)  // binary Merkle tree of event IDs
leaf_hash = H(0x00, events_root, state_hash)

Where:

• events_root — Merkle root of event IDs in this bundle
• state_hash — SMT root AFTER the last event in this bundle is applied

For N events in a bundle:

1. If N = 1: events_root = event_ids[0] (no tree needed)
2. If N > 1: Build a binary Merkle tree over event IDs:
   • Leaf: event_id (raw 32-byte hash, no prefix)
   • Internal node: H(0x01, left, right)
   • Built bottom-up by pairing adjacent nodes; if a level has an odd number of nodes, the final unpaired node is carried up unchanged to the next level (it is NOT duplicated or padded).
   • Example: 3 events → H(0x01, H(0x01, e0, e1), e2) (e2 carried up, never duplicated)

Events within a bundle are ordered by their sequence number (seq). The first event has the lowest seq, the last has the highest. This ordering is deterministic and verifiable.

Bundles are numbered sequentially starting from 0. An event's bundle membership is determined by bundle boundaries:

• bundle_0 contains events from seq=0 until size or timeout reached
• bundle_N contains events from boundary[N-1] + 1 until size or timeout reached
• boundary[N] = seq of last event in bundle N

event.seq belongs to bundle_N where:
  boundary[N-1] < event.seq <= boundary[N]
  (boundary[-1] = -1 for the first bundle)

During log replay or migration, bundle boundaries are reconstructed by applying the same closing rules (size/timeout). If CT root matches after reconstruction, bundle assignment is correct.

Config: bundle.size = 3, timeout = 5000ms
 
seq=0,1,2 (ts: 1000ms) → bundle_0, boundary[0]=2
seq=3,4,5 (ts: 3000ms) → bundle_1, boundary[1]=5
seq=6     (ts: 9000ms) → bundle_2, boundary[2]=6 (timeout hit)
 
Query: which bundle is seq=4?
Answer: bundle_1 (because 2 < 4 <= 5)

node_hash = H(0x01, left_child, right_child)

The 0x00 and 0x01 prefixes prevent second-preimage attacks by distinguishing leaf nodes from internal nodes.

The CT tree follows RFC 9162 Section 2.1 (Merkle Tree algorithm):

• Bundles are CT leaves, numbered sequentially (bundle_0, bundle_1, ...).
• Tree grows as bundles are appended
• The Merkle Tree Hash (MTH) is computed recursively (RFC 9162 §2.1), with NO padding or leaf duplication. For n leaves D:
  • MTH([]) = 0x00…00 (32 zero bytes) — the sentinel root for an empty CT. NOTE: This is [0u8; 32], NOT sha256("") — the empty-tree sentinel deliberately differs from the SMT's empty-subtree hash sha256("") (see smt.md).
  • MTH([d0]) = leaf_hash(d0) — a single leaf is its own hash (it is NOT re-hashed).
  • MTH(D[0:n]) = H(0x01 || MTH(D[0:k]) || MTH(D[k:n])) for n > 1, where k is the largest power of two strictly less than n.
• For non-power-of-two n this yields an unbalanced tree; the trailing leaves are promoted up the right spine, never padded/duplicated.
• Example: 5 bundles split at k = 4 → H(0x01 || MTH([b0..b3]) || MTH([b4]))

CT root (5 bundles, RFC 9162 §2.1 — split at largest power of two < n):
 
              root
             /    \
          h0123    b4        ← b4 is a lone leaf promoted up; no padding
          /   \
        h01   h23
       /  \   /  \
      b0  b1 b2  b3

This matches RFC 9162 exactly and is required for working inclusion AND consistency proofs. Pad-with-last (duplicating the final leaf to the next power of two) MUST NOT be used — it cannot support RFC 9162 consistency proofs.

To prove an event exists and verify state:

1. Bundle membership proof — proves event_id is in the bundle's events_root
2. CT inclusion proof — proves bundle is in the CT tree

With bundle.size = 1, the events_root equals the single event_id, and bundle membership proof is trivial.

The CT leaf binds each bundle to the enclave state after that bundle:

state_hash[bundle_0] = SMT root after all events in bundle 0
state_hash[bundle_N] = SMT root after all events in bundle N

Within a bundle, state changes are applied sequentially:

For events [e_0, e_1, ..., e_k] in bundle:
  state = apply(state, e_0)
  state = apply(state, e_1)
  ...
  state = apply(state, e_k)
  bundle.state_hash = state

State-changing events (modify SMT): Manifest, Move, Grant, Revoke, Transfer, Gate, AC_Bundle, Shared, Own, Update, Delete, Pause, Resume, Terminate, Migrate.

Non-state-changing events: Content Events (app-defined customs).

Since state_hash is deterministic from the log, anyone can recompute and verify it. If a node provides incorrect state_hash values, the CT root will not match.

Note: State changes take effect immediately for authorization (in-memory). The state_hash in CT reflects the state at bundle boundaries for proof purposes.

When clients query enclave state (RBAC or event status) mid-bundle, two modes are available:

• Verified queries: Use for audits, disputes, high-stakes operations
• Current queries: Use for real-time apps (chat, collaboration)

Nodes SHOULD support both modes.

::: extension-point id=ct-default-query-mode class=impl_defined_default reason: choice between verified (paid SMT-proof round-trip) and current (no proof) is a per-deployment tradeoff between latency and verification strength

A node's default query mode (when a caller omits the mode parameter) is chosen by the implementation. Nodes SHOULD document their choice. :::

With default bundle.timeout = 5000 ms, verified queries MAY be up to 5 seconds stale. Nodes SHOULD document their bundle configuration and expected staleness.

• Client verifies an event is part of the canonical log
• Client verifies the enclave state at any point in history
• Client verifies the log they cached is still valid (consistency with current log)
• Detect if a node is presenting different log histories to different clients
• Checkpoint for migration (CT root proves both log and state)

Proof serialization formats are specified in §Wire Format (JSON) above.