Sparse Merkle Tree (SMT)

This document specifies the Enclave State SMT: a 168-bit-deep sparse Merkle tree keyed by namespace || sha256(raw_key)[0:20], storing RBAC bitmasks, event status, and KV state. The SMT commits to current enclave state and is bound into the CT log via the per-bundle state_hash.

Table of Contents

1. Tree Structure
2. Namespaces
3. Key Construction
4. Leaf Values
5. Hash Construction
6. Proofs
7. Collision Analysis
8. Performance
9. State-Changing Events
10. State Binding
11. Proof Binding (CT + SMT)
12. Storage

Tree Structure

The following dimensions are normative; implementations MUST use these exact values.

The 160-bit entry path matches Ethereum address length, providing the same collision safety properties.

Namespaces

The 1-byte namespace prefix separates independent state domains:

Namespaces 0x03 through 0xff are RESERVED and MUST NOT be written by any current event.

Key Construction

RBAC Key

path = 0x00 || sha256(id_pub)[0:160 bits]

Where id_pub is the raw 32-byte secp256k1 x-only public key. Implementations MUST always compute sha256(id_pub) even though id_pub is already 32 bytes; this ensures uniform distribution across the tree.

Event Status Key

path = 0x01 || sha256(event_id)[0:160 bits]

Notation: sha256(x)[0:160 bits] means the first 160 bits (20 bytes) of the SHA-256 hash. The full key is 21 bytes: 1-byte namespace prefix + 20-byte truncated hash.

API Key Construction

When calling the State Proof API, clients provide the 32-byte raw key (id_pub or event_id). The node internally constructs the 21-byte SMT key by:

1. Selecting namespace based on the namespace parameter.
2. Computing sha256(key)[0:160 bits].
3. Concatenating: namespace_byte || truncated_hash.

The response k field contains the full 21-byte SMT key for verification.

Leaf Values

RBAC

value = <bitmask: bits 0-7 State enum, bits 8+ trait flags>

RBAC bitmasks (State enum + trait flags packed per rbac/overview.md §1.1) MUST be encoded as 32-byte big-endian unsigned-integer byte strings:

• Pad with leading zeros to exactly 32 bytes.
• Example: bitmask 0x100000002 → 0x0000.00100000002 (32 bytes).

These 32 bytes are the SMT leaf value verbatim — they MUST NOT be wrapped in CBOR before hashing. The leaf hash is leaf_hash = H(0x20 || key || value) where value is the 32-byte byte string directly. In JSON proofs (see proof.md), the same 32-byte value is hex-encoded as 64 characters.

Zero Bitmask

When the bitmask reduces to 0 (State is OUTSIDER AND no trait flags set — see rbac/overview.md), the leaf MUST be removed from the SMT. An identity with bitmask 0 is semantically equivalent to "not in tree". This follows the same pattern as Event Status where "(not in tree) = Active".

A non-membership proof for an identity means "currently has bitmask 0 (OUTSIDER with no traits)"; it does NOT distinguish "never had any State / trait" from "had State / traits, all cleared." The SMT tracks current state only, not history. To prove historical assignment, use a CT inclusion proof for the originating Move or Grant event.

Event Status

The Event Status leaf values are normative; implementations MUST encode each status exactly as shown. The length difference unambiguously distinguishes Deleted from Updated.

Wire format disambiguation. In CBOR encoding, the 1-byte deleted marker (0x00) and the 32-byte update_event_id are distinguishable by their length prefix:

• Deleted: CBOR encodes as 0x40 0x00 (1-byte bytestring) or 0x00 (integer zero).
• Updated: CBOR encodes as 0x58 0x20 <32 bytes> (32-byte bytestring).

This prevents any collision between deleted status and an update_event_id that happens to start with zeros.

Proof Interpretation

| Proof type | SMT proof result | Interpretation | |---|---| | Event Status | Non-membership (null) | Active OR never existed | | Event Status | Membership (0x00) | Deleted | | Event Status | Membership (32 bytes) | Updated to this event | | RBAC | Non-membership (null) | OUTSIDER with no traits (or never had any State / trait) | | RBAC | Membership (32 bytes) | Has this State + trait bitmask |

To distinguish "Active" from "never existed" for events, combine with a CT inclusion proof. To prove historical State / trait assignment, use a CT inclusion proof for the originating Move / Grant event.

Distinguishing event outcomes.

For Event Status proofs, a non-membership proof (null) means:

• The event is currently Active OR it never existed.
• To distinguish: obtain a CT inclusion proof for the event.
  • If CT inclusion succeeds: event was created → currently Active.
  • If CT inclusion fails: event never existed.

For RBAC proofs, a non-membership proof means:

• Identity currently has bitmask 0 (OUTSIDER with no traits).
• To prove historical State / trait assignment, obtain a CT inclusion proof for the originating Move / Grant event.

Hash Construction

The hash constructions below are normative; implementations MUST use these exact domain separators and operand orders.

Leaf Hash

leaf_hash = H(0x20, key, value)

Internal Node Hash

node_hash = H(0x21, left_child, right_child)

Empty Node

empty_hash = sha256("")
           = 0xe3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855

Implementations MUST hardcode the empty-node constant and MUST NOT compute it at runtime.

Proofs

SMT proof structure and verification are defined in proof.md.

Collision Analysis

Same security margin as Ethereum addresses.

Performance

Note: computation is always O(168) regardless of tree sparsity. Empty siblings are still hashed.

State-Changing Events

Only certain events modify the SMT.

RBAC Namespace (0x00)

Each RBAC event MUST update the SMT exactly as specified below.

KV State Namespace (0x02)

Event Status Namespace (0x01)

Update chaining. Multiple Updates to the same event are allowed. Each Update overwrites the previous value:

• First Update: SMT[event_A] = update_event_B.
• Second Update: SMT[event_A] = update_event_C.
• Final state: SMT[event_A] = update_event_C.

The SMT always stores the latest update_event_id. To trace the full Update history, use CT inclusion proofs to find all Update events referencing the original target_event_id.

Lifecycle Events (KV State Namespace 0x02)

Lifecycle events MUST write the same Shared("lifecycle") KV slot used by other Shared singletons (see spec.md §6 and rbac.md §8.7). Formally: LIFECYCLE_KV_KEY = buildKVKey("lifecycle", none), and all four applyPause / applyResume / applyTerminate / applyMigrate target this key — only the encoded byte differs. The SMT carries the current lifecycle state directly — it is NOT derived from the event log.

Events that do NOT modify SMT

• Content events (e.g., a custom message event) MUST NOT modify the SMT directly.

State Binding

The SMT root (state_hash) is bound to the event log via the Certificate Transparency (CT) structure, not via the event hash itself.

CT Leaf Hash

The CT leaf hash construction below is normative.

leaf_hash = H(0x00, events_root, state_hash)

Where:

• events_root — Merkle root of event IDs in this bundle (see spec.md for bundle structure).
• state_hash — SMT root AFTER the last event in this bundle is applied.

Note. With bundling, state_hash is recorded per bundle, not per event. For bundle.size == 1, events_root equals the single event_id.

Proof Binding (CT + SMT)

The CT root proves both log integrity AND state integrity. To verify a state claim, the client needs:

1. CT inclusion proof — proves the event exists at position N in the log.
2. SMT proof — proves the state against state_hash at position N.

Verification Flow

1. Obtain the event, bundle membership proof, and CT inclusion proof from the node.
2. Verify bundle membership: confirm event_id is in the bundle's events_root.
3. Verify CT inclusion proof: recompute path from leaf_hash = H(0x00, events_root, state_hash) to CT root.
4. Verify SMT proof against the state_hash from step 3.

Unified checkpoint. The CT root alone is sufficient to prove both:

• Event log integrity (which events exist, in what order).
• State integrity (what the SMT root was after each event).

This simplifies migration and audit: a single ct_root value commits to the entire enclave history and state.

Storage

• Implementations SHOULD store only non-empty nodes.
• Empty subtrees MUST be computed on-demand from the precomputed empty_hash constant.
• Historical states MAY be pruned.

Enclave State SMT

The enclave maintains a single Sparse Merkle Tree (SMT) that stores both:

• RBAC state (namespace 0x00) — identity → bitmask (State enum + trait flags).
• Event status state (namespace 0x01) — event ID → status (active/updated/deleted).
• KV state (namespace 0x02) — key → value hash (Shared/Own slots, lifecycle, gates).

The SMT uses:

• Trimmed depth (shorter than 256 bits) for efficiency
• Flag bits to distinguish entry types (RBAC vs Event Status)

Implementation details (depth, flag encoding, proof format) are specified in smt.md.

The SMT leaf/node hash is Poseidon2 over BN254 (SNARK-native), which lets the node emit a zero-knowledge validity proof that a state transition old_root → new_root is valid under the RBAC rules — verifiable by a client in O(1) without replaying the log. This works either as a bounded per-transition proof or as a single folded (Nova IVC) proof attesting the enclave's entire unbounded transition history in O(1). See zk.md → Folding.

• Path: derived from id_pub (trimmed + flag)
• Leaf value: identity bitmask (State enum in bits 0-7, trait flags in bits 8+)

• Path: derived from event_id (trimmed + flag)
• Leaf value: status + reference to U/D event

The SMT root hash represents the complete enclave state (both RBAC and event status). This single root can be used to verify any state query.

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 deepest-first order: index 0 is the sibling at depth 167 (leaf level), index 1 at depth 10, index 2 at depth 0 (root level). This ordering matches the verification walk (leaf-to-root), which consumes siblings front-to-back.Reference: verify / _smtVerifyStep and prove / verify.

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.

SMT Proof Wire Format (JSON)

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