Skip to content

proof-system.md

Latest commit

 

History

History
205 lines (148 loc) · 6.35 KB

proof-system.md

File metadata and controls

205 lines (148 loc) · 6.35 KB
Raw

Shadow-EVM Proof System

This document explains the cryptographic proof system used by Shadow-EVM.

Overview

Shadow-EVM uses RISC Zero's proof system to generate Zero-Knowledge proofs of EVM execution. The system provides:

  • Computational Integrity: Proof that the EVM executed correctly
  • Succinctness: Small proof size (~256 bytes for Groth16)
  • Zero-Knowledge: Optional privacy for execution details
  • On-Chain Verification: Efficient Solidity verification

Proof Pipeline

┌─────────────────┐     ┌─────────────────┐     ┌─────────────────┐
│  RISC-V Guest   │────▶│    STARK Proof  │────▶│  Groth16 SNARK  │
│  (Execution)    │     │   (Succinct)    │     │ (On-Chain Ready)│
└─────────────────┘     └─────────────────┘     └─────────────────┘
     ~10M cycles            ~1MB proof            ~256 bytes

Stage 1: Guest Execution

The RISC-V guest program executes inside the ZK-VM:

  1. Fetch: Guest reads ExecutionInput from host
  2. Execute: ShadowExecutor runs the EVM transaction using revm
  3. Commit: Guest writes ExecutionCommitment to journal

All memory operations, arithmetic, and I/O are recorded by the prover.

Stage 2: STARK Proof

RISC Zero generates a STARK (Scalable Transparent ARgument of Knowledge):

  • Proves correct execution of RISC-V instructions
  • Recursively composes sub-proofs
  • Results in a succinct proof (~1MB)

Stage 3: Groth16 SNARK (Optional)

For on-chain verification, the STARK is wrapped in a Groth16 SNARK:

  • Constant-size proof (~256 bytes)
  • Constant verification time (~200k gas)
  • Requires trusted setup (RISC Zero provides this)

Commitment Structure

The ExecutionCommitment is the public output of the ZK proof:

pub struct ExecutionCommitment {
    /// Hash of ExecutionInput
    pub input_hash: Hash,
    /// Hash of ExecutionOutput
    pub output_hash: Hash,
    /// Pre-state root
    pub pre_state_root: Hash,
    /// Post-state root
    pub post_state_root: Hash,
    /// Combined commitment: keccak256(input_hash || output_hash)
    pub commitment: Hash,
}

Commitment Computation

input_hash    = keccak256(serialize(ExecutionInput))
output_hash   = keccak256(serialize(ExecutionOutput))
commitment    = keccak256(input_hash || output_hash)

This binds the specific execution input to its output, enabling:

  1. Replay Prevention: Each commitment is unique
  2. State Verification: On-chain contracts can verify state transitions
  3. Auditability: Anyone can verify the commitment matches known I/O

Journal Format

The journal is the public output of the ZK proof, formatted as:

┌─────────────────────────────────────────────────────────────────┐
│ Bytes 0-31   │ input_hash     │ Keccak256 of ExecutionInput     │
│ Bytes 32-63  │ output_hash    │ Keccak256 of ExecutionOutput    │
│ Bytes 64-95  │ pre_state_root │ State root before execution     │
│ Bytes 96-127 │ post_state_root│ State root after execution      │
│ Bytes 128-159│ commitment     │ Combined cryptographic binding  │
└─────────────────────────────────────────────────────────────────┘

Total: 160 bytes

Image ID

The Image ID is a unique identifier for the guest program:

let image_id: [u8; 32] = /* SHA256 of guest ELF */;

This ensures:

  1. The proof was generated by the exact Shadow-EVM guest code
  2. No malicious modifications to the executor
  3. Deterministic program identification

Security Guarantees

What the Proof Guarantees

Property Guarantee
Execution Correctness EVM executed according to specification
State Transition pre_state + tx = post_state
Determinism Same input always produces same output
Program Integrity Proof was generated by known guest

What the Proof Does NOT Guarantee

Property Reason
Input Validity Caller must verify input is appropriate
State Existence Pre-state must be proven to exist on-chain
Economic Security Separate from cryptographic security

On-Chain Verification

The Solidity verifier performs:

function verify(bytes calldata seal, bytes calldata journal) external {
    // 1. Verify Groth16 proof
    bool valid = riscZeroVerifier.verify(seal, imageId, sha256(journal));
    require(valid);
    
    // 2. Decode commitment from journal
    ExecutionCommitment memory c = decodeJournal(journal);
    
    // 3. Record state transition
    stateTransitions[c.preStateRoot] = c.postStateRoot;
}

Gas Costs

Operation Approximate Gas
Groth16 Verification ~200,000
Journal Decoding ~5,000
State Storage ~20,000
Event Emission ~5,000
Total ~230,000

Compare to running complex EVM logic on-chain: millions of gas.

Proof Modes

Development Mode

shadow-evm prove --input tx.json --output proof.bin --dev
  • Fast proof generation (~seconds)
  • NOT cryptographically secure
  • For testing only

Production Mode

shadow-evm prove --input tx.json --output proof.bin
  • Full STARK + Groth16
  • Cryptographically secure
  • Takes longer (~minutes to hours)

Proof Aggregation (Future)

Multiple proofs can be aggregated into a single proof:

┌───────┐  ┌───────┐  ┌───────┐
│Proof 1│  │Proof 2│  │Proof 3│
└───┬───┘  └───┬───┘  └───┬───┘
    │          │          │
    └──────────┼──────────┘
               │
         ┌─────▼─────┐
         │ Aggregate │
         │   Proof   │
         └───────────┘

This enables:

  • Batch verification (pay gas once for many proofs)
  • Recursive composition (proofs of proofs)
  • Throughput scaling