State Proofs

Prove that an account holds a given balance — or that it does not exist — against a single 32-byte root, without revealing the rest of the tree.

Overview

A state proof is a compact cryptographic witness that a particular key-value pair is (or is not) present in the Sahyadri account tree at a specific block. It lets any client verify state without holding the full database, without trusting the node that served the proof, and without replaying any block history.

Proofs are produced by the SMT directly. Every Sahyadri node can generate them for any account at any block whose root it knows — including historical blocks — because the tree is content-addressed and every root is retained in the account_roots_store.

The proof primitive is not bolted on. It is a first-class feature of the SMT crate that produces every block header's commitment. The same tree that commits to state also attests to it.

Why State Proofs Matter

Without state proofs, every participant must either (a) run a full node, or (b) trust a centralized RPC provider. Both are bad options for a decentralized network. State proofs collapse this to a third path: verify cryptographically what you need, ignore the rest.

This is the difference between "trust me" and "verify yourself." Sahyadri's design makes the second option available on any device that can run SHA3.

Inclusion Proof

An inclusion proof shows that key → value exists under a given root. The prover walks the tree from the root to the leaf and records every sibling hash it passes.

Structure:

struct Proof {
    siblings: Vec<H256>,   // one per tree level, root-down
    terminal: Terminal,    // the leaf at the end of the path
}

enum Terminal {
    Empty,
    Leaf { key: H256, value: H256 },
}

The verifier recomputes the root from the terminal and the sibling hashes, walking upward:

fn compute_root(key: &H256, proof: &Proof) -> H256 {
    let mut h = match &proof.terminal {
        Terminal::Empty         => EMPTY,
        Terminal::Leaf { key, value } => hash_leaf(key, value),
    };
    for (i, sib) in proof.siblings.iter().enumerate().rev() {
        h = if bit(key, i) == 0 {
            hash_branch(&h, sib)   // we are the left child
        } else {
            hash_branch(sib, &h)   // we are the right child
        };
    }
    h
}

The bit(key, i) check is what makes this reversible. The verifier must know, at every level, whether the reconstructed hash was the left child or the right child. The path through the tree is exactly the bit sequence of the key, most-significant-bit first.

Verification succeeds if and only if:

• The recomputed root equals the trusted root, and
• The terminal leaf's key matches the queried key.

The second condition is critical. Without it, an adversary could substitute a leaf with a different key and still produce a valid path — because the path is determined by the query key, not by the leaf's key. Verifying both is what binds the proof to the actual key being queried.

Exclusion Proof

An exclusion proof is harder to produce in most Merkle variants. A standard Merkle tree can only prove what is present, not what is absent. An SMT makes exclusion proofs trivial because every key has a reserved path — if the path is empty or hits a different leaf, the key is provably absent.

Two distinct cases produce a valid exclusion proof:

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

The shares_prefix check prevents a subtle attack. Without it, a malicious prover could place an unrelated leaf at the wrong depth in the tree, and the resulting hash might coincidentally match the root. Requiring that the divergent leaf shares the correct prefix up to the point where the paths split ensures the proof is honest about where the query key's path actually terminates.

fn shares_prefix(a: &H256, b: &H256, n: usize) -> bool {
    (0..n).all(|i| bit(a, i) == bit(b, i))
}

Proof Size Analysis

Both proof types are O(depth) in size, where depth is the effective height of the compressed tree. In the worst theoretical case this is 256, but real trees are far shorter.

Worst case, a proof is under 9 KB — roughly 2.5x the size of a single Dilithium3 signature (3.3 KB). For networks with millions of accounts, typical proofs run 200 bytes to 1 KB, which is smaller than a Dilithium3 signature.

Compare this to a UTXO-style proof, which must include every unspent output of an address. For a busy address, this can run into tens of kilobytes. Account state maps naturally to a single leaf, so proof size is bounded by tree depth, not by account activity.

Proof Generation

Generating a proof is a matter of walking the tree from root to leaf and recording the sibling hashes along the way:

pub fn prove<S: NodeStore>(
    store: &S,
    root: H256,
    key: &H256,
) -> Result<Proof, SmtError> {
    let mut siblings = Vec::new();
    let mut cur = root;
    let mut depth = 0usize;

    loop {
        if cur == EMPTY {
            return Ok(Proof {
                siblings,
                terminal: Terminal::Empty,
            });
        }
        match store.get(&cur).ok_or(SmtError::MissingNode(cur))? {
            Node::Leaf { key: k, value } => {
                return Ok(Proof {
                    siblings,
                    terminal: Terminal::Leaf { key: k, value },
                });
            }
            Node::Branch { left, right } => {
                if depth >= TREE_DEPTH {
                    return Err(SmtError::DepthExceeded);
                }
                if bit(key, depth) == 0 {
                    siblings.push(right);
                    cur = left;
                } else {
                    siblings.push(left);
                    cur = right;
                }
                depth += 1;
            }
        }
    }
}

Generation is O(depth) in time and space. It touches only the path from root to leaf — no other part of the tree is read. On the server side, this means a proof for any account is a few hundred hash-map lookups.

RPC Endpoint

The Sahyadri node exposes a state-proof RPC on the standard wRPC interface:

get_account_proof(
    address:    Address,
    block_hash: Option<Hash>,   // defaults to virtual tip
) -> {
    block_hash: String,
    account_root: String,
    key:        String,          // hex-encoded SMT key
    proof: {
        siblings: Vec<String>,   // hex-encoded H256, root-down
        terminal: {
            kind:  "Empty" | "Leaf",
            key:   Option<String>,   // present iff Leaf
            value: Option<String>,   // content-hash of AccountState
        },
    },
    state:      Option<{
        balance:        u64,
        recent_flashes: Vec<{ flash_id: String, expiry_daa_score: u64 }>,
    }>,
    state_hash: String,
}

The node resolves the requested block's root from account_roots_store, walks the tree from that root, and returns the proof. No consensus interaction, no mining, no state mutation. Purely a read operation.

An account that exists returns Some(state) plus an inclusion proof. An absent account returns None plus an exclusion proof. The client never needs to trust which case the server chose — it verifies the proof either way.

Client Verification Flow

Code: Verifying a Proof in Rust

A complete verification function for a client that already holds a trusted root:

use sahyadri_smt::{verify_inclusion, verify_exclusion, Proof, Terminal, H256};

pub enum VerifiedAccount {
    Present { balance: u64, flashes: u32 },
    Absent,
}

pub fn verify_account_proof(
    trusted_root: &H256,
    account_key: &H256,
    proof: &Proof,
) -> Option<VerifiedAccount> {
    match &proof.terminal {
        Terminal::Empty => {
            if verify_exclusion(trusted_root, account_key, proof) {
                Some(VerifiedAccount::Absent)
            } else {
                None
            }
        }
        Terminal::Leaf { value, .. } => {
            if verify_inclusion(trusted_root, account_key, value, proof) {
                // value is the content_hash of the account state.
                // Fetch the full state from the state store if needed.
                Some(VerifiedAccount::Present {
                    balance: 0,          // resolved from state store
                    flashes: 0,
                })
            } else {
                None
            }
        }
    }
}

In a browser, the same logic compiles to WebAssembly through the Sahyadri WASM SDK. In an embedded device, the Rust core compiles to no_std + alloc for a footprint under 100 KB. The proof format and verification algorithm are identical everywhere.

Use Cases

Security Analysis

A state proof is only as strong as the cryptographic primitives it rests on. Every assumption is explicit:

There is no trusted third party in the proof path. The verifier's only assumption is that the block header it started from was produced by honest consensus — which is the same assumption every full node makes. Proofs add zero new trust assumptions.

Comparison with Other Proof Systems

SMT proofs are not the smallest in the field — Groth16 proofs are ~10x smaller. But they are one of the few proof systems here that is post-quantum, transparent (no setup), and cheap enough to verify on any device without requiring a specialized proving circuit or a ceremony. For account-state membership, they hit a useful balance.

Limitations

Being honest about what state proofs do not do is as important as what they do:

• They prove state, not transitions. 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.
• They require a trusted root. A client that does not verify headers is trusting whichever root it was given. The root is the trust anchor; the proofs are the mechanism.
• They do not compress history. 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.
• They are not private by default. The proof reveals which account is being queried and, in the inclusion case, the balance being proven. Privacy requires additional mechanisms (blinded queries, batch proofs, or ZK wrapping).
• They do not replace header verification. A proof can only be as trustworthy as the root it is checked against. Consensus-level security still comes from PoW + ghostDAG, not from SMT proofs alone.

None of these are blockers. They are the boundary of what the primitive promises. Everything inside that boundary is cryptographically enforced.

Summary

State proofs collapse the trust required to interact with Sahyadri down to a single hash comparison. They power light clients, bridges, audits, and DWN authorization without needing every participant to store or replay the chain. The primitive is implemented and the RPC surface is live on every full node.

A 32-byte root, a few hundred sibling hashes, and one SHA3 comparison. That 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 — quantum-resistant.