Sparse Merkle Tree (SMT)

This document specifies the implementation details for the Enclave State SMT referenced in the main protocol spec.

Tree Structure

Property	Value
Total depth	168 bits (21 bytes)
Namespace prefix	8 bits (1 byte)
Entry path	160 bits (20 bytes)
Hash function	SHA256
Empty value	`sha256("")`

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

Namespaces

Namespace	Hex	Purpose
RBAC	`0x00`	Role assignments
Event Status	`0x01`	Update/Delete tracking
Reserved	`0x02–0xFF`	Future use

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

Selecting namespace based on namespace parameter
Computing sha256(key)[0:160 bits]
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>

CBOR Encoding:

Role bitmasks are encoded as 32-byte big-endian byte strings for CBOR hashing:

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

Padding Scope:

The 32-byte padding is applied during CBOR encoding for SMT leaf hash computation (leaf_hash = H(0x20, key, value)). In JSON proofs (see proof.md), the same 32-byte value is hex-encoded as 64 characters. The padding is persistent — it represents the actual leaf value stored in SMT.

Zero Bitmask:

When all roles are revoked (bitmask = 0), the leaf is removed from the SMT. An identity with no roles is semantically equivalent to "not in tree". This follows the same pattern as Event Status where "(not in tree) = Active".

Historical Membership (Intentional Design): A non-membership proof for an identity means "currently has no roles" — it CANNOT and DOES NOT distinguish between "never had roles" and "had roles, all revoked." This is intentional: the SMT tracks current state only, not history. To prove historical membership, use a CT inclusion proof for the Grant event that assigned the role.

Event Status:

Value	Meaning
(not in tree)	Active
`0x00` (1 byte)	Deleted
`<update_event_id>` (32 bytes)	Updated

Encoding: Deleted status is a single zero byte (0x00). Updated status is the 32-byte update_event_id. This unambiguously distinguishes the two cases.

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)	No roles (or never had roles)
RBAC	Membership (32 bytes)	Has these roles (bitmask)

To distinguish "Active" from "never existed" for events, combine with CT inclusion proof. To prove historical role membership, use CT inclusion proof for the Grant event.

Distinguishing Event Outcomes:

For Event Status proofs, if you receive a non-membership proof (null):

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 no roles
To prove historical role assignment, obtain a CT inclusion proof for the Grant event

Hash Construction

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

Hardcoded constant — do not compute at runtime.

Proofs

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

Collision Analysis

Entries	Collision probability
1 billion	~10^-30
1 trillion	~10^-24
100 trillion	~10^-20

Same security margin as Ethereum addresses.

Performance

Operation	Cost
Single SHA256	~1 μs
SMT update	168 hashes = ~170 μs
Proof verification	168 hashes = ~170 μs
Throughput	~6,000 updates/sec

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):

Event	SMT Update
Manifest	Initialize leaves from `init` entries (State + trait bits)
Move	Set State enum (bits 0-7); clear trait flags unless `preserve: true`
Grant	Set trait bit for target identity; optionally registers push endpoint
Revoke	Clear trait bit for target identity
Transfer	Clear trait bit from operator, set trait bit on target (atomic)
Gate	Write gate state to KV namespace (`Shared("gate:<alias>")`)
AC_Bundle	Batch updates (atomic)

KV State Namespace (0x02):

Event	SMT Update
Shared	`SMT[H(0x02 \|\| key)] = H(content)` — enclave-wide singleton
Own	`SMT[H(0x02 \|\| key \|\| identity)] = H(content)` — per-identity slot

Event Status Namespace (0x01):

Event	SMT Update
Update	`SMT[target_event_id] = update_event_id`
Delete	`SMT[target_event_id] = 0`

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.

Events that do NOT modify SMT:

Content events (e.g., Chat_Message)
Lifecycle events: Pause, Resume, Terminate, Migrate

Lifecycle state is derived from the event log, not stored in SMT.

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:

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:

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

Verification Flow:

Obtain the event, bundle membership proof, and CT inclusion proof from the node
Verify bundle membership: confirm event_id is in the bundle's events_root
Verify CT inclusion proof: recompute path from leaf_hash = H(0x00, events_root, state_hash) to CT root
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

Store only non-empty nodes
Empty subtrees computed on-demand
Historical states MAY be pruned