Epic: ZK Proving of the State Transition Function

[tac0turtle]

Goal

Make the Evolve STF provable inside a zkVM. The end state: a prover takes a block + witness artifact, executes the STF inside a zkVM (Jolt, RISC Zero, or SP1), and produces a proof that any verifier can check — enabling trustless light clients, rollup settlement, and bridging.

Scope

1. Deterministic STF & Read-Trace Plumbing

• Ensure STF overlay uses deterministic data structures (BTreeMap, no randomized state)
• Add read-trace collection to ExecutionState (read_keys(), base_read_keys())
• Add witness types to stf_traits (ReplayWitnessEnvelope, BlockReadWitness, ReadWitnessEntry, ReadProofEnvelope)
• Add ReadProofProvider and ReadProofVerifier traits
• Add replay_block_strict / replay_block_strict_from_artifact STF APIs
• Add canonical output commitment helpers (tx outcomes, events, state changes)
• Add configurable storage hashing (blake3 default, sha256 optional)
• Add commitment version locking and startup validation

2. Storage Provability

The storage layer needs to support authenticated reads so a verifier can confirm the STF operated on correct pre-state.

• Implement ReadProofProvider for the current storage backend (inclusion + exclusion proofs)
• Typed proof codec (ReadProofEnvelope::V1) with canonical borsh encoding
• Strict verification mode (decode -> re-encode -> byte equality check)
• Storage hash algorithm metadata persisted and enforced at chain level
• Evaluate merkle tree structure for proof size — current QMDB proofs may be large; benchmark and consider alternatives if needed

3. Witness Generation Pipeline

• Witness builder that captures a complete ReplayWitnessEnvelope during block execution
• Include: pre-state root, block context, tx IDs, authenticated read proofs, expected public outputs
• Canonical borsh encoding with version envelope
• Witness size benchmarks (target: reasonable for zkVM memory constraints)
• Witness generation integrated into node operation (optional mode, not default)

4. zkVM Integration — Evaluate & Implement

Evaluate three backends and implement at least one end-to-end:

Jolt

• Determine if Evolve's STF can compile to Jolt's guest (RISC-V target, no_std constraints)
• Benchmark: proof generation time, memory, proof size, verification time

RISC Zero

• Assess RISC Zero zkVM guest compatibility with Evolve STF
• Evaluate risc0-zkvm guest SDK constraints (no_std, memory limits, syscall support)
• Benchmark: same metrics as Jolt

SP1

• Assess Succinct SP1 guest compatibility
• Evaluate precompile availability (keccak256, secp256k1 — critical for ETH tx verification)
• Benchmark: same metrics as Jolt

Deliverable: Written comparison of all three with recommendation. Implement the winner as first backend.

• Guest program that takes witness artifact, executes replay_block_strict_from_artifact, commits public inputs
• Host program that generates proof and serializes proof bundle
• Verifier that checks proof against expected public inputs
• Feature-gated backend selection

5. STF Compatibility for zkVM Targets

The STF and its dependencies need to compile to RISC-V / zkVM guest targets. This is likely the largest workstream.

• Audit STF dependency tree for no_std compatibility
• Remove or gate any std-only dependencies in the proving path (filesystem, networking, threads, system time)
• Ensure all crypto operations used in STF (keccak256, secp256k1 ECDSA verification) are available in guest or via precompiles
• Ensure borsh serialization works in guest
• Gate rayon parallel execution out of proving path (sequential execution required in zkVM)
• Create a zk-guest feature flag that strips the STF to only what's needed inside the prover
• Test: STF compiles for riscv32im-risc0-zkvm-elf or equivalent target

6. Proof Verification & Consensus Integration

• Define where/how proofs are verified (on-chain verifier account? external verifier service?)
• Proof bundle format finalized (ProofBundleV1 with backend, public inputs, proof bytes)
• Public inputs exposed in block metadata (RPC, gRPC)
• Optional proof verification mode (feature-gated, not consensus-critical initially)
• Document upgrade path from optional verification to consensus-required

7. Testing & Fixtures

• Golden fixture suite: valid proof, tampered artifact (must fail), tampered tx payload (must fail)
• Fixture compatibility tests across releases (schema version lock)
• E2E script: generate witness -> prove -> verify
• Simulator integration: generate witnesses during simulation runs, verify replay determinism
• CI job: build guest program, run verification on fixtures (placeholder proofs initially, real proofs nightly)

Design Considerations

• no_std boundary: The proving path must be no_std compatible. This means the STF, storage access layer (via witness), and all codec/crypto must work without the standard library. Everything outside the proving boundary (witness generation, proof serialization, RPC) can remain std.
• Precompiles matter: SP1 and RISC Zero provide accelerated precompiles for keccak256 and secp256k1. Since Evolve uses both for ETH compatibility, precompile support significantly reduces proving cost. This may be the deciding factor between backends.
• Sequential execution: zkVMs execute sequentially. The STF's rayon-based parallel tx validation must be gated out in the proving path.
• Witness size: Each proven block needs its full read witness. Proof of a block touching 10K keys with 1KB avg proof per key = ~10MB witness. Need to benchmark and potentially batch/compress.
• Incremental approach: Ship placeholder proofs first (the infrastructure), then swap in real proofs. This lets us validate the pipeline end-to-end before optimizing proving performance.

Success Criteria

1. A guest program compiles Evolve's STF to a zkVM target (at least one of Jolt/RISC Zero/SP1).
2. Given a block and its witness artifact, the prover generates a valid proof.
3. The verifier confirms the proof matches the expected public inputs (pre-state root, post-state root, tx commitments).
4. Fixture tests prevent regression on witness/proof format compatibility.
5. Written evaluation of all three zkVM backends with benchmarks.

References

• Jolt — a16z zkVM
• RISC Zero — RISC Zero zkVM
• SP1 — Succinct SP1 zkVM

[tac0turtle]

Consideration: ZK-Friendly Hash for QMDB Merkle Tree (Poseidon)

The issue mentions configurable storage hashing (blake3/sha256) but doesn't address the proving cost of the Merkle hash function itself. This is potentially the single largest constraint on proving performance.

The problem

Every state proof requires re-hashing Merkle paths inside the zkVM. Hash cost in a SNARK circuit:

Hash	Constraints per invocation
SHA-256	~25,000
Keccak-256	~150,000
Blake3	~15,000
Poseidon	~300

For a block touching 10K keys in a tree of depth ~20, that's ~200K hash invocations per block proof. At SHA-256 rates that's ~5 billion constraints just for Merkle path verification. With Poseidon it's ~60 million — a ~80x reduction.

Why this doesn't break Ethereum compatibility

Analyzed the ev-rs codebase — swapping QMDB's internal hasher is invisible to the Ethereum compat surface:

• Transaction format: Uses keccak256 for tx hashes, ECDSA for signatures — completely separate from QMDB, untouched.
• JSON-RPC: state_root is passed through as opaque B256 (32 bytes). Neither eth-jsonrpc nor chain-index recompute it. The hash algorithm doesn't matter to consumers.
• Wallets/tooling: MetaMask, ethers.js, etc. never verify state roots client-side.
• State proofs (eth_getProof): ev-rs already uses QMDB instead of Ethereum's Merkle Patricia Trie + keccak256. State proof compatibility was never present, so changing the hasher is the same level of incompatibility.

The only secondary hashing in chain-index/src/integration.rs (compute_tx_root, compute_receipts_root) is internal to the indexer and independent of QMDB.

QMDB is already generic

qmdb_impl.rs parameterizes the DB type over the hasher:

Db<C, StorageKey, StorageValueChunk, Sha256, EightCap, 64, Merkleized<Sha256>, Durable>

The path would be implementing commonware's hasher trait for a Poseidon backend, then swapping the type parameter. Candidate Rust crates: neptune (Filecoin/Lurk), poseidon2 (Horizen).

Recommendation

Add Poseidon as a storage hash option alongside blake3/sha256 in the configurable hashing work (Section 1). For the zkVM backend evaluation (Section 4), benchmark proving cost with and without Poseidon Merkle hashing — it may dominate total proving time and influence the backend decision.

Ref: EIP-5988 (Poseidon Hash Function Precompile)