State Proofs
A cryptographic witness that a key-value pair exists, or does not exist, in the account tree at a specific block. Verified against a single 32-byte root. Requires no chain download, no trusted node, no replay.
1. Formal Definition
A state proof is a tuple of hashes and a terminal description such that a deterministic verification function reconstructs the tree root from the tuple alone.
Definition 1.1 (State Proof)
A state proof for key k at root R is:
π = ( s_0, s_1, ..., s_{d-1}, τ )
where:
s_i ∈ {0,1}^256 is the sibling hash at level i
d is the depth of the terminal
τ is a Terminal: Leaf(key, value) or Empty
A proof is valid against key k and root R iff:
Reconstruct(k, π) = R
∧ ( τ = Empty ∧ ¬∃ leaf at path(k) )
∨ ( τ = Leaf(k', v) ∧ k' = k )
Definition 1.2 (Reconstruct)
Reconstruct(k, π):
h ← HashLeaf(τ)
for i = d-1 downto 0:
if bit(k, i) = 0:
h ← HashBranch(h, s_i)
else:
h ← HashBranch(s_i, h)
return hThe reconstruction is deterministic. Two verifiers running Reconstruct(k, π) on identical inputs produce identical outputs. There is no randomness, no environment, no timing dependency.
The second clause of validity is not optional. Without the key-match condition, an adversary could substitute a leaf with a different key at the same tree position and still produce a valid path, because the path is defined by the query key — not by the leaf's key.
2. The Sparse Merkle Tree
The state commitment is a Sparse Merkle Tree over the Goldilocks field, using Poseidon2 for internal hashing and SHA3-256 for content addressing. A Sparse Merkle Tree is a Merkle tree with a fixed domain: every possible 256-bit key has exactly one reserved leaf, whether or not the leaf is populated.
SMT structure:
Depth: 256 (fixed)
Empty leaf: 0^256 (all-zero)
Leaf hash: Poseidon2_W8( D_LEAF ‖ key ‖ value )
Branch hash: Poseidon2_W8( D_BRANCH ‖ left ‖ right )
Domain prefixes: D_LEAF = "SAHYADRI_SMT_LEAF_V1"
D_BRANCH = "SAHYADRI_SMT_BRANCH_V1"
Content-addressing:
Two nodes with identical (key, value) sets produce identical root,
regardless of insertion order. Root depends only on the leaf set.The domain prefixes prevent second-preimage attacks that would allow a leaf hash to be substituted for a branch hash. They are enforced at the crate level; not a convention that callers can bypass.
The tree is compressed: a subtree holding a single leaf is collapsed into that leaf. Effective depth is well under 64 in practice. Proof size and generation cost are bounded by the compressed depth, not the theoretical maximum.
3. Inclusion Proof
An inclusion proof demonstrates that key → value exists at the queried position. The prover walks from root to leaf, recording every sibling hash along the way. The proof terminates at the leaf itself.
Algorithm 3.1 (Prove-Inclusion)
Input: root R, key k
Output: π = (s_0, ..., s_{d-1}, τ = Leaf(k, value))
h ← R
π.siblings ← []
for i = 0, 1, ..., 255:
match h:
Empty:
return (π, Empty) -- exclusion proof
Leaf(k', v):
return (π, Leaf(k', v)) -- inclusion proof
Branch(left, right):
if bit(k, i) = 0:
π.siblings.push(right)
h ← left
else:
π.siblings.push(left)
h ← right
error: DepthExceeded -- cannot happen at valid depthGeneration is O(d) in both time and space, where d is the compressed depth of the tree. The prover touches only the path from root to leaf; the rest of the tree is never read.
4. Exclusion Proof
An exclusion proof demonstrates that key does not exist under the queried root. Standard Merkle trees cannot produce such proofs because leaves have no reserved positions. In a Sparse Merkle Tree, every key has a reserved path, so absence is provable by the shape of the path itself.
Two distinct terminal cases yield a valid exclusion proof:
Case 1: Empty terminal The walk from R terminated at an empty subtree. The key was never inserted. Reconstruction from (π.siblings, Empty) yields R. No additional check is needed. Case 2: Divergent leaf The walk terminated at a leaf with key k' ≠ k. Because the tree is compressed, k' occupies the single-leaf subtree that would have contained k. Reconstruction from (π.siblings, Leaf(k', v)) yields R. Verification requires k' ≠ k AND prefix(k', k, d) holds — that is, k' and k share the same first d bits, and their paths diverge at exactly the terminal level.
Algorithm 4.1 (Verify-Exclusion)
Input: root R, key k, proof π = (siblings, τ)
Output: accept or reject
match τ:
Empty:
return Reconstruct(k, π) == R
Leaf(k', v):
if k' == k: -- this is inclusion, not exclusion
return reject
if not prefix_matches(k', k, depth(π)):
return reject -- divergent leaf is misplaced
return Reconstruct(k, π) == RThe prefix_matches check is required. Without it, an adversary could place an arbitrary leaf at the wrong depth and produce a path that happens to reconstruct the correct root. Requiring the divergent leaf to share the correct prefix up to the divergence point guarantees that the proof is honest about where the queried key's path terminates.
5. Verification
Verification is a single deterministic pass. Given a trusted root, a query key, and a proof, the verifier recomputes the root and compares. No network calls, no external state, no trusted node.
Algorithm 5.1 (Verify-State-Proof)
Input: root R, key k, proof π = (siblings, τ)
Output: accept with value, or reject
match τ:
Empty:
if Reconstruct(k, π) ≠ R:
return reject
return accept(Absent)
Leaf(k', v):
if k' ≠ k:
-- this is an exclusion proof via divergent leaf
if not prefix_matches(k', k, depth(π)):
return reject
if Reconstruct(k, π) ≠ R:
return reject
return accept(Absent)
-- inclusion proof
if Reconstruct(k, π) ≠ R:
return reject
return accept(Present(k, v))Reconstruct executes in O(d) hash operations. For a tree of depth 256, this is at most 256 Poseidon2 permutations — under 1 millisecond on any device from the last decade.
6. Proof Size Bound
Proof size is O(d), with the constant depending on the hash width and terminal encoding:
Bound 6.1 (Proof Size)
|π| = d · 32 bytes + |terminal|
where:
d = compressed depth of the tree (typically < 64)
|terminal| = 1 byte (Empty) or 65 bytes (Leaf: tag + key + value)
Typical: d ≈ 20-50, |π| ≈ 0.7-1.7 KB
Worst: d = 256, |π| ≈ 8.2 KBA UTXO-style proof must include every unspent output controlled by an address. For an address with many outputs, this can grow to tens of kilobytes. Account-based state maps to a single leaf, so proof size is bounded by tree depth rather than account activity.
7. RPC Interface
Every full node exposes state-proof generation on the standard wRPC interface. The handler resolves the block's account commitment from persistent storage, walks the tree, and returns the proof. No consensus interaction, no state mutation.
get_account_proof(
address: Address,
block_hash: Option<Hash>, -- defaults to virtual tip
) -> {
block_hash: Hex, -- block whose root was used
account_root: Hex, -- root committed in the header
key: Hex, -- SHA3-256 of the CSM32 script
proof: {
siblings: [Hex; d], -- root-down, 32 bytes each
terminal: {
kind: "Empty" | "Leaf",
key: Option<Hex>,
value: Option<Hex>, -- content-hash of AccountState
},
},
state: Option<AccountState>, -- present iff terminal.kind = Leaf
state_hash: Hex, -- SHA3-256 of serialized state
}An account that exists returns a Leaf terminal plus the deserialized AccountState. An absent account returns an Empty terminal. The client cannot rely on the node's choice; it must verify the proof independently. The node has no discretion — it either produces a proof that verifies or it does not.
8. Verification Flow
The client-side flow is five deterministic steps. Each step is local; none involve network trust.
Flow 8.1 (Client State Verification)
Step 1: Obtain trusted root
- Verify a block header (PoW, DAG ordering)
- Extract account_commitment from the header
- This is the only trusted input in the entire flow.
Step 2: Request proof
- Call get_account_proof(address, block_hash) on any peer
- Peer choice is irrelevant; proof is self-authenticating
Step 3: Reconstruct root
- Run Reconstruct(key, proof) locally
- Cost: O(d) hash operations, < 1 ms on any device
Step 4: Compare against trusted root
- Accept iff Reconstruct(key, proof) == trusted_root
- Also verify terminal key matches query key (per Definition 1.1)
Step 5: Use verified state
- Balance or absence is now cryptographically authenticated
- No further checks required; downstream logic can proceedSteps 1 and 2 are the only steps that touch external data. Steps 3 and 4 are pure computation. Step 5 is application logic. The trust anchor is entirely in step 1 — everything downstream is arithmetic.
9. Implementation Reference
The reference implementation compiles to native Rust, WebAssembly for browsers, and no_std + alloc for embedded devices. The algorithm and proof format are identical on every platform.
// FILE: crates/sahyadri-smt/src/verify.rs
// Core verification primitives.
use crate::{Proof, Terminal, H256, hash_leaf, hash_branch};
pub fn reconstruct(key: &H256, proof: &Proof) -> H256 {
let mut h = match &proof.terminal {
Terminal::Empty => H256::zero(),
Terminal::Leaf { key, value } => hash_leaf(key, value),
};
for (i, sibling) in proof.siblings.iter().enumerate().rev() {
h = if bit(key, i) == 0 {
hash_branch(&h, sibling)
} else {
hash_branch(sibling, &h)
};
}
h
}
pub fn verify_inclusion(
trusted_root: &H256,
key: &H256,
expected_value: &H256,
proof: &Proof,
) -> bool {
match &proof.terminal {
Terminal::Leaf { key: k, value } => {
k == key
&& value == expected_value
&& reconstruct(key, proof) == *trusted_root
}
Terminal::Empty => false,
}
}
pub fn verify_exclusion(
trusted_root: &H256,
key: &H256,
proof: &Proof,
) -> bool {
match &proof.terminal {
Terminal::Empty => reconstruct(key, proof) == *trusted_root,
Terminal::Leaf { key: k, .. } => {
k != key
&& prefix_matches(k, key, proof.siblings.len())
&& reconstruct(key, proof) == *trusted_root
}
}
}
fn prefix_matches(a: &H256, b: &H256, n: usize) -> bool {
(0..n).all(|i| bit(a, i) == bit(b, i))
}The complete verification path is under 100 lines. This is deliberate: verification correctness should be readable. Any reviewer can trace the flow from proof to trusted root in a single sitting.
10. Security Analysis
Security of state proofs rests on three properties. Each is stated as a formal bound on the adversary's success probability.
Assumption 10.1 (Hash resistance)
Poseidon2 over Goldilocks has:
- Collision resistance: 2^128 classical, 2^64 quantum
- Second preimage: 2^256 classical, 2^128 quantum
Assumption 10.2 (Content addressing)
Two distinct (key, value) sets produce distinct roots.
Root equality ⟹ leaf set equality (modulo hash collision).
Assumption 10.3 (Trusted root)
Client trusts exactly one thing: the block header it has
independently verified. All proof security is relative to this.Adversary capabilities and their mitigations:
Threat 10.4 (Forged proof)
Attacker fabricates π such that Reconstruct(k, π) = R for
a (key, value) pair not present in the tree.
Requires: finding Poseidon2 collision (2^128 classical)
or second preimage (2^256 classical).
Bound: Pr[forged proof accepted] ≤ 2^{-128} + negl(λ).
Threat 10.5 (Stale root substitution)
Attacker serves a proof against an old root the client still trusts.
Mitigation: client binds proof to specific block hash. Proof against
a different block's root is rejected before reconstruction.
Threat 10.6 (Malicious node)
Node returns fabricated proof or a proof against a different block.
Mitigation: node has zero trust weight. Proof either verifies against
the client's trusted root or is rejected. Client can rotate peers
freely without correctness loss.
Threat 10.7 (Cross-fork replay)
Proof from fork A is submitted as proof from fork B.
Mitigation: each block has a unique root. Cross-fork proofs fail
reconstruction against fork B's root. No cross-fork replay possible.
Threat 10.8 (Denial of service)
Node serves nonsense proofs to waste client resources.
Mitigation: verification is O(d) with d ≤ 256, sub-millisecond on
any device. Cost of rejecting a bad proof is negligible.No threat requires a trusted third party for mitigation. The protocol does not rely on a certificate authority, a designated RPC, or a permissioned set of provers. The verifier's only assumption is that its own header verification was correct.
11. Complexity
| Operation | Time | Space | Notes |
|---|---|---|---|
| Root lookup | O(1) | O(1) | Indexed by block hash |
| Proof generation | O(d) | O(d) | d = compressed depth, typical 20-50 |
| Proof verification | O(d) | O(d) | Hash count = d, independent of state size |
| State update | O(d) | O(d) | Writes d new nodes; unchanged nodes are shared |
| Storage growth | O(1) per update | O(d) per update | Content-addressed; unchanged nodes not rewritten |
The critical property: verification cost is bounded by tree depth, not by account count. A chain with 1,000 accounts and a chain with 1 billion accounts both verify a state proof in the same number of hash operations.
12. Limitations
A state proof does not prove everything. What it does not prove is as important as what it does.
What state proofs do NOT prove:
1. Consensus validity.
A state proof tells you "account X had balance Y at block B."
It does not prove "block B was produced by honest mining."
That requires header verification (PoW + DAG ordering).
2. Trusted root independence.
A client that does not verify headers is trusting whichever root
it was given. The root is the trust anchor. The proof is the
mechanism. A proof against a fabricated root proves nothing.
3. Historical compression.
Each proof is against a single block's root. To prove the same
account across a year of blocks, you need a year's worth of
proofs — unless you check only the latest, which supersedes
all previous.
4. Query privacy.
The proof reveals the queried key. For account balances, this
reveals which address is being checked. Privacy requires
additional mechanisms (batched queries, blinded proofs,
or ZK-wrapped proofs).
5. Non-membership of dynamic sets.
State proofs prove non-membership at a specific block. If the
account is created in a later block, the exclusion proof
remains valid for the earlier block only.None of these are defects. They are boundaries of the primitive's contract. Everything inside the boundary is cryptographically enforced.
13. Summary
A state proof reduces the trust required to interact with Sahyadri to a single hash comparison. The verifier trusts one block header and everything else is arithmetic. This is the primitive that makes light clients, bridges, solvency audits, and decentralized identity authorization possible without full nodes or trusted RPC providers.
The proof primitive is not bolted on. It is the same Sparse Merkle Tree that produces every block's account_commitment. Every node that commits to state also attests to it. The proof format is fixed, the verification path is under 100 lines, and the security argument rests on a hash function and a verifier's own header check.
A 32-byte root, a few hundred sibling hashes, and one hash comparison. This is what stands between an attacker and a forged balance claim. It is small enough to run on a phone, fast enough to run on a browser tab, and — for the primitives it relies on — post-quantum secure.