Sparse Merkle Tree

The state commitment scheme. Every block header carries a single 32-byte SMT root that commits to every account's balance and replay-protection state. The root is a pure function of the effects of the block applied to its parent's state.

1. Formal Definition

A Sparse Merkle Tree is a binary tree of fixed depth in which every key in a 2^256 domain has a reserved leaf position. Unlike a standard Merkle tree built only from existing leaves, an SMT reserves space for the entire key universe; most positions are empty and collapse to a canonical zero hash.

Definition 1.1 (Sparse Merkle Tree)

  A Sparse Merkle Tree over key universe K = {0,1}^256 is a tuple:

    SMT = (D, Node, Hash, Empty)

  where:
    D     = 256  (tree depth)
    Node  = Leaf(key, value) | Branch(left, right)
    Hash  = { H_leaf: K × V → {0,1}^256
            , H_branch: {0,1}^256 × {0,1}^256 → {0,1}^256
            }
    Empty = {0}^256

  The root of a set of leaves L ⊆ K × V is defined recursively:

    Root(∅) = Empty

    Root({(k, v)}) = H_leaf(k, v)

    Root(L) where |L| > 1:
      Let k_1, k_2 ∈ keys(L) diverge first at bit d.
      Then Root(L) = H_branch(
          Root({l ∈ L : bit(key(l), d) = 0}),
          Root({l ∈ L : bit(key(l), d) = 1})
      )

Two properties follow directly from the definition. First, the root is a pure function of the set L — no ordering, no history, no side state. Second, the tree is a commitment — given the root, no party can produce a different leaf set with the same root without breaking hash collision resistance.

2. Node Structure

Two node types appear in the tree. No extension nodes, no null nodes, no leaf-straddling nodes. The absence of these is what makes the implementation small and the proof format fixed.

enum Node {
    Leaf   { key: H256, value: H256 },
    Branch { left:  H256, right: H256 },
}

Empty = [0u8; 32]

A Branch stores only the hashes of its two children. A Leaf stores a full key-value pair. An empty subtree is not represented at all — it is the constant EMPTY. This is what makes the tree sparse: the 2^256 possible positions are not stored, only the ones that have been inserted.

Single-leaf compression. A subtree containing exactly one leaf is that leaf. No branch is created just to hold a single leaf at depth 200. This compression is what makes the effective depth of the tree small in practice — a tree with millions of accounts has an effective depth in the range of 30-64, not 256.

3. Hashing

The SMT uses Poseidon2 over the Goldilocks field (2^64 - 2^32 + 1) for internal node hashing and SHA3-256 for content hashing. The split is deliberate: internal hashing needs to be provable inside a STARK; content hashing needs to be collision-resistant.

H_leaf(key, value)     = Poseidon2_W8( D_LEAF   ‖ key ‖ value )
H_branch(left, right)  = Poseidon2_W8( D_BRANCH ‖ left ‖ right )
H_key(bytes)           = Poseidon2_W8( D_KEY    ‖ bytes )

Domain prefixes:
  D_LEAF   = "SAHYADRI_SMT_LEAF_V1"
  D_BRANCH = "SAHYADRI_SMT_BRANCH_V1"
  D_KEY    = "SAHYADRI_SMT_KEY_V1"

Content hash:
  H_content(state) = SHA3-256( "SAHYADRI_ACCOUNT_STATE_V1" ‖ canonical_bytes(state) )

Why Poseidon2 for tree hashing. A Merkle path must be verifiable inside a STARK. Poseidon2 over Goldilocks has ~300 AIR constraints per permutation. SHA3-256 has ~30,000. The 100× reduction is what makes in-circuit Merkle verification feasible on commodity hardware. A tree hashed with SHA3-256 could not be used as a commitment inside a STARK — the constraint count would be prohibitive.

Why SHA3-256 for content hashing. The content hash commits to the full state of an account. It is hashed once, outside the STARK, when the account state changes. It does not need to be constraint-efficient — it needs to be collision-resistant and fast. SHA3-256 delivers both.

Domain separation. Three distinct prefixes are used for leaf, branch, and key hashing. Without them, an adversary could substitute a leaf hash for a branch hash and produce a forged Merkle path. The prefixes prevent every cross-type collision in a single step, and they are enforced at the crate level — a caller cannot bypass them by reimplementing a hash.

4. Canonical Roots

This property is what makes the SMT compatible with a DAG. In a naive Merkle tree, the root depends on insertion order. In an SMT with single-leaf compression, it does not.

Claim 4.1 (Order independence)

  For any set of leaves L = {(k_1, v_1), ..., (k_n, v_n)}:

    ∀ permutations σ of {1..n}:
      Root({(k_σ(1), v_σ(1)), ..., (k_σ(n), v_σ(n))}) = Root(L)

  Proof sketch:

    By induction on n.

    n = 1:  trivially root is H_leaf(k_1, v_1).

    n > 1:  Let d be the first depth at which two keys in L diverge.
            Every pair of keys with the same prefix up to d but
            different bit at d determines the same branch split.
            Both children are themselves SMTs over subsets of L.
            By induction, each child's root is independent of order.
            Therefore the parent's root is independent of order.

The property is verified empirically with a property test that shuffles every permutation of 64 keys and asserts a single resulting root:

#[test]
fn insert_order_does_not_matter() {
    let ids: Vec<u32> = (0..64).collect();
    let mut rev = ids.clone();
    rev.reverse();

    let (mut s1, mut s2) = (MemStore::default(), MemStore::default());
    assert_eq!(build(&mut s1, &ids), build(&mut s2, &rev));
}

Why this matters in a DAG. In a linear chain, blocks are ordered and the commitment scheme could depend on ordering. In SahyadriDAG, blocks arrive in parallel and each block's effects are determined by its selected parent, not by network timing. Two nodes may receive the same mergeset in different orders due to propagation delay. Without canonical roots, every node would compute a different state commitment and the network would silently fork.

5. Storage Model

State is distributed across three stores. Each serves a distinct purpose and no store duplicates the work of another.

Store 1: SMT Node Store
  Key:   H_node = Hash(node_bytes)
  Value: node_bytes
  Purpose: content-addressed node storage
  Update: append-only — writes never overwrite existing nodes

Store 2: Account State Store
  Key:   H_content = SHA3-256(canonical_bytes(state))
  Value: AccountState
  Purpose: content-addressed state snapshots
  Update: append-only — dedupes identical states

Store 3: Account Roots Store
  Key:   block_hash
  Value: SMT root at that block
  Purpose: per-block root pointer
  Update: overwrite on reorg

The three stores are deliberately separated. The node store holds structure; the state store holds content; the roots store holds pointers. A reorg replaces the root pointer but never touches the node or state stores — every historical node and state remains valid because they are content-addressed.

6. The Transition Function

The function that computes a new root from a parent root and a block's effects is a pure function. No disk writes, no external state, no time-dependence. Given identical inputs, it returns identical output on every node.

pub fn compute_block_account_changes(
    parent_root:  H256,
    smt_overlay:  &mut impl NodeStore,
    state_store:  &dyn AccountStatesStoreReader,
    flash_txs:    &[FlashTransaction],
    rewards:      &[(ScriptPublicKey, u64)],
    daa_score:    u64,
) -> Result<(H256, Vec<(ScriptPublicKey, AccountState)>), AccountError> {

    let mut touched: HashMap<ScriptPublicKey, AccountState> = HashMap::new();

    // 1. Apply flash txs — debit sender, credit recipient, record flash_id
    for tx in flash_txs {
        // ... read state, apply delta, push FlashEntry
    }

    // 2. Apply coinbase rewards
    for (miner_spk, amount) in rewards {
        // ... credit miner
    }

    // 3. Prune expired flashes on all touched accounts
    for state in touched.values_mut() {
        state.prune_recent_flashes(daa_score);
    }

    // 4. Update SMT and produce the new root
    let mut root = parent_root;
    for (spk, state) in touched.iter() {
        let key = account_key_hash(spk);
        let leaf = if state.is_empty() {
            None
        } else {
            Some(state.content_hash().as_bytes())
        };
        root = sahyadri_smt::update(smt_overlay, root, &key, leaf)?;
    }

    Ok((root, touched.into_iter().collect()))
}

Three properties of this function are load-bearing:

Property 6.1 (Purity)
  The function has no side effects. It does not write to disk,
  read external state, or depend on time. Given (parent_root,
  flash_txs, rewards, daa_score), the output is deterministic.

Property 6.2 (Shared by producer and verifier)
  The block producer and the block verifier call the same function.
  There is no "miner code" and "validator code" that could drift
  apart. Divergence in block template or verification is
  structurally impossible.

Property 6.3 (Overlay isolation)
  The function writes only to an overlay store. The persistent
  node store is not touched. On rejection, the overlay is
  discarded — no cleanup required.

7. The Overlay Store

The overlay store is a write-through buffer over the persistent node store. Reads fall through to disk; writes accumulate in memory. The persistent store is only flushed when a block commits.

pub struct OverlayStore<'a, B: NodeStore> {
    base:    &'a B,
    pending: HashMap<H256, Node>,
}

impl<'a, B: NodeStore> NodeStore for OverlayStore<'a, B> {
    fn get(&self, hash: &H256) -> Option<Node> {
        self.pending.get(hash).cloned()
            .or_else(|| self.base.get(hash))
    }

    fn put(&mut self, node: Node) -> H256 {
        let h = node.hash();
        self.pending.insert(h, node);
        h
    }
}

Reorging a block means discarding the overlay and re-pointing to the parent's root. No tree nodes are destroyed. No state is rebuilt. Because every historical root lives in the account roots store keyed by block hash, any block's state can be reconstructed by replaying only that block's effects onto its parent's root — O(log n) work, not O(history).

8. Canonical State Encoding

The content hash of an account must be stable across reorgs, pruning, and any reordering of internal structures. This requires a canonical byte encoding of the state.

pub fn to_canonical_bytes(&self) -> Vec<u8> {
    let mut out = Vec::with_capacity(12 + self.recent_flashes.len() * 40);
    out.extend_from_slice(&self.balance.to_le_bytes());

    let mut flashes: Vec<&FlashEntry> = self.recent_flashes.iter().collect();
    flashes.sort_by(|a, b| a.flash_id.as_bytes().cmp(&b.flash_id.as_bytes()));

    out.extend_from_slice(&(flashes.len() as u32).to_le_bytes());
    for f in flashes {
        out.extend_from_slice(&f.flash_id.as_bytes());
        out.extend_from_slice(&f.expiry_daa_score.to_le_bytes());
    }
    out
}

Three deliberate design choices:

Choice 8.1: Flashes sorted by flash_id
  Reorgs and pruning can reorder the in-memory vector. If the hash
  were order-sensitive, a reorg could silently change a committed
  root and fork the chain. Sorting by flash_id makes the hash
  stable across every possible reordering.

Choice 8.2: block_hash excluded from hash
  Each FlashEntry carries a block_hash used to unwind the specific
  block that added it during a reorg. That field is local to a
  node's reorg bookkeeping — it is not part of what the network
  commits to. Excluding it means two nodes that saw the same flash
  in different blocks still agree on state.

Choice 8.3: Empty account = absent leaf
  A state with zero balance and no flashes is not stored as a leaf
  containing zeros. It is deleted from the tree entirely. This
  ensures that reading an account once and never reading it produce
  identical roots — avoiding a subtle non-determinism that would
  otherwise force every node to agree on which accounts were "seen."

9. Proofs

Two proof types are supported: inclusion (a key-value pair is present) and exclusion (a key is absent). Both are O(depth) in size and O(depth) in verification time.

Proof structure:

  Proof {
      siblings: Vec<H256>,     // one per level, root-down
      terminal: Terminal,      // Leaf(key, value) or Empty
  }

Verification:

  Reconstruct(key, proof) → H256
    h = HashTerminal(proof.terminal)
    for i = d-1 downto 0:
      h = if bit(key, i) = 0:
            H_branch(h, siblings[i])
          else:
            H_branch(siblings[i], h)
    return h

Inclusion:
  Accept ⟺ Reconstruct(key, proof) = trusted_root
        ∧ terminal = Leaf(key, value)

Exclusion:
  Accept ⟺ Reconstruct(key, proof) = trusted_root
        ∧ ( terminal = Empty
          ∨ terminal = Leaf(key', _) ∧ key' ≠ key
            ∧ shares_prefix(key', key, depth) )

Why the key check matters. Without the key comparison in the inclusion case, an adversary could substitute a leaf with a different key at the same position and still produce a valid Merkle path. The path is determined by the query key, not by the leaf's key — the verifier must check that the leaf it received is for the key it queried.

Why the divergent-leaf check matters. In the exclusion case, a prover could place an arbitrary leaf at the wrong depth and produce a path that happens to reconstruct the correct root. Theshares_prefix check requires that the divergent leaf share the correct prefix up to the divergence point, which forces the prover to be honest about where the queried key's path terminates.

10. Complexity

OperationTimeSpaceNotes
Read one accountO(d) = 256 hashes worst caseO(d)Effective d typically < 64
Update one accountO(d) writesO(d)Only the path is rewritten
Apply one block (M txs)O(M · d)O(M · d)Independent of chain length
Verify one blockO(M · d)O(M · d)Same function as apply
Reorg one blockO(1)O(1)Pointer swap in roots store
Inclusion proofO(d) siblingsO(d)Typically < 2 KB
Exclusion proofO(d) siblingsO(d)Same shape as inclusion

The 256-depth worst case is theoretical. Because single-leaf subtrees are compressed, the effective depth for any real tree is bounded by the number of bits actually shared between adjacent keys. For a network with millions of accounts, typical path lengths are far below 64, making both proofs and updates cheap in practice.

11. Why DAG-Native Commitment Requires Canonical Roots

In a linear chain, the parent of a block is unambiguous. A commitment scheme that depends on ordering would work fine. In SahyadriDAG, neither is true. Blocks arrive in parallel, the mergeset of a block is determined by its parents, and different nodes can see the same mergeset in different arrival orders.

Linear chain commitment:

  Root(B_n) = Apply(B_n, Root(B_{n-1}))
  Order of application is forced by chain structure.
  No ambiguity about which blocks come first.

DAG commitment:

  Root(B_n) = Apply(B_n, Root(selected_parent(B_n)))
  Order within a mergeset is undefined.
  Two nodes may see parallel blocks in different orders.

  Requirement: Apply must be order-independent.
  The SMT is the only commitment scheme that satisfies this
  without imposing additional ordering assumptions.

The SMT's canonical-root property is what allows the account_commitment field in every block header to be meaningful agreement between nodes — even when those nodes received blocks in different orders.

12. Post-Quantum Properties

The commitment path does not depend on any pre-quantum cryptographic primitive. Every hash is either Poseidon2 over Goldilocks or SHA3-256; every signature is ML-DSA-65.

Component              Algorithm          Quantum security

SMT node hash          Poseidon2           ~128-bit (Goldilocks, 256-bit output)
Content hash           SHA3-256            ~128-bit preimage (Grover)
Signature              ML-DSA-65           NIST Level 3 (lattice)
Key derivation         Poseidon2           ~128-bit

No elliptic curves. No pairing-based crypto. No trusted setup.

Grover's algorithm offers a quadratic speedup against preimage search, so both Poseidon2 and SHA3-256 retain roughly 128-bit preimage resistance under a quantum adversary. For collision resistance, the best known quantum attack against SHA3-256 gives approximately 2^85 operations — still computationally infeasible. Poseidon2's field arithmetic does not admit a Shor-style attack because it is not based on a hidden-subgroup problem.

The implication for state: an account state transition that is valid today remains valid under a future quantum adversary, provided the account holder still controls their private key. No upgrade, no re-signing, no migration.

13. Known Limitations

Four issues are known and pending:

Issue 13.1: Legacy account transactions still accepted
  Legacy nonce-based transactions are outside the SMT commitment
  path today, but the validator does not yet reject them. This is
  a known gap and will be closed by removing the legacy path
  entirely.

Issue 13.2: Flash-window vector has no hard cap
  A burst of flash transactions within the window grows the
  sender's recent_flashes vector and therefore their leaf hash.
  A cap is planned to bound per-account state size.

Issue 13.3: Batch flash validation rejects on duplicate
  Under mergeset acceptance, the same flash transaction can appear
  in parallel blocks. The validator should skip duplicates rather
  than reject the whole batch. This fix is pending.

Issue 13.4: Recursive state proof not yet implemented
  A client can verify any block's state given that block's header.
  Booting a new node still requires obtaining a trusted header.
  With the Poseidon2 SMT shift complete, STARK-friendly state
  proofs are now feasible; the recursive aggregation layer is the
  next milestone.

14. Summary

The SMT is the state commitment scheme. It compresses every account's balance and replay-protection state into a single 32-byte root stored in every block header. It is deterministic, order-independent, reorg-safe, and post-quantum. Above all, it is a pure function of a block's effects on its parent's state.

That purity is the foundation for everything above it. State proofs. Light clients. Cross-chain verification. Reorgs that cost almost nothing. A network whose nodes can be small, verifiable, and free of historical debt.

Every proof of account state — every balance check, every credential verification, every cross-chain attestation — reduces to a single comparison against the SMT root. The primitive is small, but it is the one that everything else depends on.