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 h

The 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 depth

Generation 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, π) == R

The 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 KB

A 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 proceed

Steps 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

OperationTimeSpaceNotes
Root lookupO(1)O(1)Indexed by block hash
Proof generationO(d)O(d)d = compressed depth, typical 20-50
Proof verificationO(d)O(d)Hash count = d, independent of state size
State updateO(d)O(d)Writes d new nodes; unchanged nodes are shared
Storage growthO(1) per updateO(d) per updateContent-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.