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
| Operation | Time | Space | Notes |
|---|---|---|---|
| Read one account | O(d) = 256 hashes worst case | O(d) | Effective d typically < 64 |
| Update one account | O(d) writes | O(d) | Only the path is rewritten |
| Apply one block (M txs) | O(M · d) | O(M · d) | Independent of chain length |
| Verify one block | O(M · d) | O(M · d) | Same function as apply |
| Reorg one block | O(1) | O(1) | Pointer swap in roots store |
| Inclusion proof | O(d) siblings | O(d) | Typically < 2 KB |
| Exclusion proof | O(d) siblings | O(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.