Sparse Merkle Tree (SMT)

The cryptographic backbone of Sahyadri's account state — how a single 32-byte root attests to every balance, every flash transaction, and every replay marker across the network, deterministically and post-quantum secure.

What is a Sparse Merkle Tree?

A Sparse Merkle Tree is a 256-level binary hash tree in which every one of the 2^256 possible keys has a predetermined path from the root. Unlike a standard Merkle tree, which is built only from the leaves that actually exist, an SMT reserves space for the entire key universe. Almost all of that space is empty — hence "sparse" — and empty subtrees collapse to a canonical zero hash.

In Sahyadri, the tree is indexed by a hash of each account's script public key. The leaf value is a hash of that account's state. Every block publishes the tree's root in its header. Any node, anywhere, on any machine, can independently recompute that root from the block's effects and reject the block if it disagrees. No trust, no whitelist, no checkpoint authority.

Tree Structure

The tree is binary and fixed-depth. Every leaf sits at depth 256. The path from the root to a key is determined by the bits of that key, read most-significant first:

path(key):
    for i in 0..256:
        bit = (key[i / 8] >> (7 - (i % 8))) & 1
        if bit == 0: go left
        else:        go right

There are exactly two node types:

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

A Branch stores the hashes of its two children. A Leaf stores a full key-value pair. There is no third type — no extension nodes, no null nodes. Empty subtrees are simply the constant EMPTY = [0u8; 32].

The shape of the tree is canonical. A subtree that contains 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 tree compact despite its depth, and it is what guarantees order-independence.

Hashing

Every hash in the tree is a domain-separated SHA3-256. The domain tags prevent cross-type collisions — a leaf hash can never equal a branch hash, and neither can equal an account key.

H_leaf(key, value)     = SHA3("SAHYADRI_SMT_LEAF_V1"   || key || value)
H_branch(left, right)  = SHA3("SAHYADRI_SMT_BRANCH_V1" || left || right)
H_key(bytes)           = SHA3("SAHYADRI_SMT_KEY_V1"    || bytes)

EMPTY = [0u8; 32]

SHA3-256 was chosen deliberately. It is the same primitive Sahyadri uses everywhere else (Dilithium3 internal hashing, PoW cSHAKE, address derivation), it has no known quantum-speedup beyond Grover's generic square-root, and it is already a workspace dependency. There is no hidden SHA-256 or Keccak-256 assumption in the commitment path.

Canonical Roots — Order Independence

This is the property that makes everything else possible. In a naive Merkle tree, the root depends on the order in which leaves were inserted. In an SMT with single-leaf compression, it does not.

Consider two leaves A and B whose keys differ first at bit d. Regardless of whether you insert A first or B first, the algorithm walks down to depth d, discovers the bit conflict, and creates a Branch containing both leaves. The Branch is at exactly the same depth, with the same children in the same positions. The resulting root is bit-for-bit identical.

fn split<S: NodeStore>(
    store: &mut S,
    depth: usize,
    ka: H256, va: H256,   // first leaf
    kb: H256, vb: H256,   // second leaf
) -> Result<H256, SmtError> {
    if depth >= TREE_DEPTH {
        return Err(SmtError::DepthExceeded);
    }
    let (ba, bb) = (bit(&ka, depth), bit(&kb, depth));
    if ba != bb {
        // Keys diverge at this depth — create a branch
        let ha = store.put(Node::Leaf { key: ka, value: va });
        let hb = store.put(Node::Leaf { key: kb, value: vb });
        let (l, r) = if ba == 0 { (ha, hb) } else { (hb, ha) };
        Ok(store.put(Node::Branch { left: l, right: r }))
    } else {
        // Same bit — recurse deeper
        let child = split(store, depth + 1, ka, va, kb, vb)?;
        let (l, r) = if ba == 0 { (child, EMPTY) } else { (EMPTY, child) };
        Ok(store.put(Node::Branch { left: l, right: r }))
    }
}

This is verified 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 does this matter in a DAG? Because ghostDAG delivers blocks in parallel. Two nodes may receive the same mergeset in different orders due to network timing. Without canonical roots, every node would compute a different state commitment and the network would silently fork. With canonical roots, order is irrelevant — the same set of effects always produces the same root.

Account State Encoding

An SMT leaf is only 32 bytes. It cannot hold a full account. So the leaf holds a content hash of the account state, and the actual state lives in a separate content-addressed store keyed by that hash.

Canonical State Encoding

The content hash of an account is computed from a byte-for-byte canonical serialization. Two states with the same balance and the same set of flash entries — regardless of insertion order or block origin — produce the same hash.

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
}

pub fn content_hash(&self) -> Hash {
    use sha3::{Digest, Sha3_256};
    let mut h = Sha3_256::new();
    h.update(b"SAHYADRI_ACCOUNT_STATE_V1");
    h.update(&self.to_canonical_bytes());
    Hash::from_slice(&h.finalize())
}

Three Deliberate Design Choices

Pruning Determinism

Expired flash entries are pruned during the block transition. A critical detail: pruning must be deterministic across nodes. The rule is that only accounts touched by a block are pruned in that block's transition, using that block's own DAA score. Untouched accounts keep their entries until some later block touches them. This guarantees every node prunes the same entries at the same block — because "touched" is determined by the block's effects, which are themselves deterministic.

Key Derivation

Account keys are hashed before entering the tree, with a dedicated domain tag:

account_key = SHA3(
    "SAHYADRI_SMT_KEY_V1" ||
    script_version (u16 LE) ||
    script_bytes
)

The script_version field is included so future changes to the script-public-key format cannot collide with existing keys. Domain separation between key hashes, leaf hashes, and branch hashes eliminates every possible cross-type collision in a single step.

Content-Addressed Nodes — Why Reorgs Are Free

Every node in the tree is stored by hash(node_bytes). This has an important consequence: the parent of a node can be identified by hash without loading either node's contents.

When a block is applied, the new root is computed entirely in an overlay store — a write-through buffer backed by the persistent node store. Reads fall through to disk. Writes accumulate in memory. The disk is only touched when the block commits, and even then, only the newly-created nodes are flushed.

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 from history. 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).

Storage also deduplicates naturally. Two blocks that leave the same account untouched share every ancestor of that account's leaf. Two blocks that differ only in which accounts moved share all other paths.

The Commitment Function

Every block's header carries an account_commitment field. It is computed by a pure function — no side effects, no database writes, no shared mutable state.

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()))
}

Notice what is absent: no disk writes, no database reads beyond the state-store interface, no mutable global state, no allocation of the entire tree. The function starts from parent_root, applies exactly the effects of one block, and returns the new root. Given the same inputs on two different machines, it returns bit-identical output.

Verification Flow

When a block arrives, a node performs the following steps. Every step is deterministic; none requires trust in the block producer.

State Proofs

Because the SMT supports proofs natively, any account's membership — or absence — can be proven against a specific root. Proofs are used by light clients, cross-chain bridges, and anyone who needs to verify state without holding the full database. An inclusion proof reveals the account key and value being proven; it is a cryptographic attestation, not a privacy-preserving one.

pub fn verify_inclusion(
    root: &H256, key: &H256, value: &H256, proof: &Proof,
) -> bool {
    match &proof.terminal {
        Terminal::Leaf { key: k, value: v }
            if k == key && v == value =>
        {
            compute_root(key, proof) == *root
        }
        _ => false,
    }
}

pub fn verify_exclusion(root: &H256, key: &H256, proof: &Proof) -> bool {
    match &proof.terminal {
        Terminal::Empty => compute_root(key, proof) == *root,
        Terminal::Leaf { key: k, .. } => {
            k != key
                && shares_prefix(k, key, proof.siblings.len())
                && compute_root(key, proof) == *root
        }
    }
}

Notice the exclusion proof shape: a valid exclusion proof either terminates at an empty subtree (the key was never inserted), or at a leaf whose key differs from the query but shares the same path prefix up to the point of divergence. Both cases are verifiable in O(log n).

Why Not UTXO?

Sahyadri's earlier design carried a UTXO multiset alongside an account store. The two were not redundant — the chain had simply never decided which model it used. The account model is what wallets, DID operations, and flash transactions already rely on. Keeping UTXO alive next to it produced three distinct problems.

Removing UTXO entirely and committing to account state via SMT collapses two systems into one, halves the cost of block application, and produces a state commitment that wallets, identity layers, and light clients can all consume with the same primitive.

Complexity & Performance

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.

Why DAG-Native Commitment Requires Canonical Roots

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

An SMT with canonical roots is the only commitment scheme that fits this model without imposing extra ordering assumptions:

• The root of a block is a pure function of its selected parent's root and its own effects.
• The effects of a mergeset are a set, not a sequence — no ordering is assumed or required.
• Two nodes with the same effects compute the same root regardless of the order in which they received them.

This is what allows the header's account_commitment field to be a meaningful cross-node agreement even in a DAG with parallel block production.

Post-Quantum Properties

The commitment path does not depend on any pre-quantum cryptographic primitive. Every hash is SHA3-256. Every signature that authorizes a state change is CRYSTALS-Dilithium3. There is no ECDSA, no Ed25519, no secp256k1, and no RSA anywhere in the chain from transaction to root.

Grover's algorithm offers a quadratic speedup against preimage search, so SHA3-256 retains roughly 128-bit preimage resistance against a quantum adversary. For collision resistance, the best known quantum attack (BHT) gives approximately 2⁸⁵ operations — still computationally infeasible, though lower than the classical 128-bit bound. Neither is a practical threat.

Dilithium3 is a NIST-selected post-quantum signature scheme built on lattice hardness assumptions, none of which are threatened by Shor's algorithm. Because commitment and signature schemes are both quantum-safe, 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.

What Is Distinct in Sahyadri

Sparse Merkle Trees are not new. Ethereum's state root uses a variant. Cosmos IAVL uses another. What is distinct is the specific combination of properties that Sahyadri's design delivers simultaneously:

Known Limitations

An honest account of what this design does not yet guarantee:

• Legacy account transactions are still accepted. They are outside the SMT commitment path today, but the validator does not yet reject them. This is a known gap and will be closed.
• Flash-window vector has no hard cap. A burst of flash transactions within the window grows the sender's vector and therefore their leaf hash. A cap is planned.
• Batch flash validation currently 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.
• No recursive state proof yet. A client can verify any block's state given that block's header. Booting a new node still requires obtaining a trusted header. A succinct proof that the current state descends from a well-known genesis is future work.

Summary

The SMT is what lets a 32-byte field in every block header attest to the entire economic and replay state of the network. It is deterministic, order-independent, reorg-safe, post-quantum, and — above all — a pure function of the 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.

Everything Sahyadri promises — decentralized identity, verifiable credentials, portable data ownership, quantum resistance — depends on this primitive being correct. It is the smallest piece of the protocol and the one that makes the rest possible.