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