ADR-0007: State commitment tree: sorted-leaf now, sparse for witnessed insertion

Status: accepted (accepted for v1, with a stated migration trigger). Dated 2026-08-26.

2026-09-04: the sparse migration now gates a devnet re-initialization. ADR-0016 shortened the challenge window to 48 hours and ADR-0009's enforcer PDA still needs to become a chain's dispute authority, and both are fixed at scc_initialize with no setter — so they need a new chain, and a new chain is a redeploy of four programs (see ADR-0016 condition 3). The owner decided the same day to wait for the sparse tree rather than pay for that twice. Until it lands, the deposit-credit one-step class leaves account-creating credits opaque, which is this ADR's own migration trigger arriving in practice.
The tree itself landed the same day: crates/solieum-sparse-tree, 12 tests. Depth 256, leaf address = the key's own bits, so insertion and deletion are ordinary update_root calls over one path. Proofs carry a 256-bit bitmap and only the non-empty siblings — 321 bytes and 8 siblings over 256 accounts — and non-inclusion is provable, which insertion witnesses need, since you cannot prove you may create an account without first proving it is absent. update_root takes no leaf_count: a key pins its own position, so the public input this ADR called the caller's error to prevent no longer exists. Measured cost is 257 hash calls per proof and 1,020 for a two-account witnessed step — order 100,000 CU at Solana's sha256, roughly 5x the 19,216 CU transfer class, and a CU number the program must confirm itself per ADR-0008. What remains for the migration is everything above the tree: the node's state root, the trace's witness types, the portal's prove_withdrawal, the dispute game's witnessed one-steps, and a genesis born with the new shape.

Status: accepted for v1, with a stated migration trigger (2026-08-26) · Prompt: §6 C5, §6 C7

Context: crates/solieum-state-tree (16 + update_root = 25 tests) backs the bridge's withdrawal proofs and the witnessed one-step verifier (svm-spike scenarios K and M, one_step_verify_witnessed measured at 19 216 CU). Building those exposed a real limit that must be recorded, not papered over.

Decision

v1 uses a sorted-leaf binary Merkle tree. Leaves are (key, value_hash) sorted by key; internal nodes hash their two children; a lone node is promoted, never duplicated. Proofs are compact (⌈log₂ n⌉ siblings, fewer on promotion paths), and update_root recomputes the root after changing existing leaves' values from a bounded witness — merging shared paths, preferring recomputed nodes over stale recorded siblings.

This is exactly right for what v1 needs: withdrawal inclusion proofs and the witnessed one-step verifier for in-place account mutation (system transfers — lamports change, the leaf set does not). Both are demonstrated on-chain.

The limit, stated plainly

A sorted-leaf tree cannot witness insertion (or deletion) in bounded work. Inserting a key at sorted position p shifts every leaf ≥ p right by one, which changes the pairing and promotion structure of the entire right portion of the tree — up to O(n) internal nodes, not O(log n). No bounded witness can express that, so one_step_verify_witnessed cannot be extended to account creation (SystemProgram::CreateAccount, or a first-time write to a fresh PDA) on this tree. The witnessed class is therefore in-place mutation of already-committed accounts, and that boundary is enforced in the program, not assumed.

This is not a bug in update_root; it is a property of the tree shape. It is the standard reason production fraud-proof systems commit account state in a sparse Merkle tree (fixed depth, key hashes to a fixed leaf position, so insertion is an ordinary update at a determined leaf and IS witness-bounded) rather than a sorted-append tree.

Consequence and migration trigger

v1 ships the sorted tree. The witnessed one-step verifier covers in-place mutation; the sequencer handles account creation/deletion at batch boundaries by re-committing the tree (full recompute, which it can afford — it holds the whole state), and those steps, if disputed, fall to the placeholder verifier until migration.
Migrate to a sparse Merkle tree (depth-256, key = H(pubkey)) when the witnessed class must include account creation — i.e. when disputes over creation steps must be resolvable on-chain rather than deferred. That is a new crate implementing the same injected-hasher / free-verify / update_root seams (so solieum-bridge and the dispute-game program change only which tree type they name), plus non-membership proofs the sorted tree does not provide. Proofs grow from ⌈log₂ n⌉ to a padded ~256 (compressible for empty subtrees), which is the cost of the property.

Reversal / non-goals

If v1's disputed traces never contain creation steps in practice (the common case: transfers and in-place updates dominate), the sparse migration may never be needed, and the sorted tree's smaller proofs are a real saving. The decision is deliberately deferred to evidence, not taken preemptively.