Cryptographic Proofs

This document specifies proof formats for the ENC protocol.

Overview

The ENC protocol uses two types of Merkle proofs:

CT Proofs

Bundle Membership Proof

Proves that an event is part of a specific bundle.

{
  event_id: <32 bytes>,
  bundle_index: <number>,
  siblings: [<hash>, ...]
}

Where:

• event_id — the event being proven
• bundle_index — position of event within the bundle (0-indexed)
• siblings — Merkle proof siblings from event_id to events_root

1. Set hash = event_id, index = bundle_index
2. For each sibling s in siblings array (from leaf toward root):
   • If index is even (LSB = 0): hash = H(0x01, hash, s) — current is left child
   • If index is odd (LSB = 1): hash = H(0x01, s, hash) — current is right child
   • index = index >> 1 (shift right by 1)
3. Verify hash == events_root

• bundle_index is the event's 0-indexed position within the bundle
• The LSB (least significant bit) of index determines left (0) or right (1) at each level
• After each hash step, shift index right to get the parent's position
• Siblings are ordered from leaf level (closest to event) to root level

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

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

• Start: hash = e2, index = 2 (binary: 10)
• Step 1: LSB(2) = 0 → hash = H(0x01, hash, siblings[0]) where siblings[0] = e3
• Shift: index = 1
• Step 2: LSB(1) = 1 → hash = H(0x01, siblings[1], hash) where siblings[1] = h01
• Result: hash should equal events_root

With bundle.size = 1, the bundle contains one event, so siblings is empty 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 (always Schnorr; the alg field applies only to client signatures, not sequencer signatures)

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 SHA256.

{
  "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.

SMT Proofs

SMT proofs verify state claims (RBAC assignments, event status) against the state_hash.

Proof Structure

{
  key: <21 bytes>,
  value: <bytes | null>,
  bitmap: <21 bytes>,
  siblings: [<hash>, ...]
}

Where:

• key — 21-byte SMT key (namespace + truncated path)
• value — leaf value (null for non-membership proof)
• bitmap — 168 bits indicating which siblings are present (1) vs empty (0)
• siblings — only non-empty sibling hashes, in order

Empty siblings are omitted; verifier uses empty_hash for missing slots.

Bit N corresponds to depth N in the tree, where depth 0 is closest to the root and depth 167 is the leaf level.

Bit numbering within bytes: LSB-first. Bit 0 is the least significant bit (rightmost). Bit 7 is the most significant bit (leftmost).

For a proof with non-empty siblings at depths 0, 10, and 167:

• Bitmap bit 0 = 1 (sibling at root level)
• Bitmap bit 10 = 1 (sibling at depth 10)
• Bitmap bit 167 = 1 (sibling at leaf level)
• All other bits = 0

Serialized as 21 bytes (168 bits), with bit 0 = LSB of byte 0. The siblings array contains exactly 3 hashes, in depth order (0, 10, 167).

Depth D maps to: byte[D / 8], bit (D % 8) where bit 0 is LSB.

Example: depth 10 → byte[1], bit 2 (since 10 / 8 = 1, 10 % 8 = 2)

The 21-byte bitmap is serialized as a hex string in standard byte order:

• Byte 0 (containing bits 0-7) is the first two hex characters
• Byte 20 (containing bits 160-167) is the last two hex characters

Example: Depths 0, 10, 167 have siblings:

• Byte 0 = 0x01 (bit 0 set)
• Byte 1 = 0x04 (bit 10 = bit 2 of byte 1)
• Byte 20 = 0x80 (bit 167 = bit 7 of byte 20)
• Hex: "010400...80" (42 chars total)

Verification

1. Compute leaf hash: H(0x20, key, value) (or empty_hash if value is null)
2. For each depth from 167 to 0:
   • If bitmap bit is 1: use next sibling from array
   • If bitmap bit is 0: use empty_hash
   • Compute: H(0x21, left, right)
3. Compare with expected root (state_hash)

Non-Membership Verification

A non-membership proof proves that a key does not exist in the SMT.

1. Verify that value is null
2. Compute the expected leaf hash as empty_hash (the key has no value)
3. Follow the same path computation as membership verification
4. Compare result with expected root (state_hash)

If the computed root matches and the path is valid with an empty leaf, the key does not exist in the tree.

Empty Node Hash

empty_hash = sha256("")
           = 0xe3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855

Hardcoded constant — do not compute at runtime.

Wire Format (JSON)

The normative wire format for v1 is JSON.

SMT Proof

{
  "k": "<hex>",
  "v": "<hex | null>",
  "b": "<hex>",
  "s": ["<hex>", ...]
}

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.