Skip to content

0201-stwo-cairo-integration.md

Latest commit

 

History

History
350 lines (270 loc) · 10.1 KB

0201-stwo-cairo-integration.md

File metadata and controls

350 lines (270 loc) · 10.1 KB

RFC-0201: STWO and Cairo Integration for Zero-Knowledge Proofs

Status

Implemented

Summary

Integrate STWO (Circle STARK prover/verifier) and Cairo (provable programming language) into Stoolap Chain. Establishes infrastructure for proof compression, confidential queries, and L2 scaling.

Motivation

The blockchain SQL database provides verifiable state via HexaryProofs, but faces three fundamental limitations:

  1. Proof Bandwidth - Verifying N rows requires N separate proofs (~68 bytes each)
  2. No Privacy - All data and queries are public on-chain
  3. Limited Throughput - Every transaction executes on-chain

Zero-knowledge proofs using STWO and Cairo address all three limitations:

  • Compression: Aggregate many proofs into one STARK proof
  • Privacy: Prove query results without revealing underlying data
  • Scalability: Execute off-chain, verify on-chain

Specification

Data Structures

/// Cairo program identifier (blake3 hash of source)
pub type CairoProgramHash = [u8; 32];

/// Compiled Cairo program metadata
pub struct CairoProgram {
    pub hash: CairoProgramHash,
    pub source: String,              // Cairo source code
    pub sierra: Vec<u8>,             // Sierra IR
    pub casm: Vec<u8>,               // Cairo Assembly Machine
    pub version: u32,                // Cairo compiler version
}

/// Registry of approved Cairo programs
pub struct CairoProgramRegistry {
    pub programs: BTreeMap<CairoProgramHash, CairoProgram>,
    pub allowlist: BTreeSet<CairoProgramHash>, // Programs approved for on-chain use
}

/// STARK proof generated by STWO
pub struct StarkProof {
    pub program_hash: CairoProgramHash,
    pub inputs: Vec<u8>,
    pub outputs: Vec<u8>,
    pub proof: Vec<u8>,              // STWO proof format
    pub public_inputs: Vec<u8>,      // Public inputs for verification
}

/// ZK operation variant
pub enum ZKOperation {
    SubmitProof {
        proof: StarkProof,
        gas_limit: u64,
    },
    RegisterProgram {
        program: CairoProgram,
    },
    VerifyProof {
        proof: StarkProof,
    },
}

Cairo Program Compilation

impl CairoProgram {
    /// Compile Cairo source to Sierra
    pub fn compile_to_sierra(source: &str) -> Result<Vec<u8>, CompileError>;

    /// Compile Sierra to CASM
    pub fn compile_to_casm(sierra: &[u8]) -> Result<Vec<u8>, CompileError>;

    /// Compute program hash from source
    pub fn compute_hash(source: &str) -> CairoProgramHash;
}

STWO Prover Interface

pub struct STWOProver {
    config: ProverConfig,
}

impl STWOProver {
    /// Generate STARK proof for Cairo program execution
    pub fn prove(
        &self,
        program: &CairoProgram,
        inputs: &[u8],
    ) -> Result<StarkProof, ProverError>;

    /// Verify STARK proof
    pub fn verify(
        &self,
        proof: &StarkProof,
        expected_outputs: &[u8],
    ) -> Result<bool, VerifyError>;
}

Cairo Program Registry

impl CairoProgramRegistry {
    /// Register new Cairo program
    pub fn register(&mut self, program: CairoProgram) -> Result<(), RegistryError>;

    /// Get program by hash
    pub fn get(&self, hash: &CairoProgramHash) -> Option<&CairoProgram>;

    /// Add program to allowlist (governance action)
    pub fn allowlist_add(&mut self, hash: CairoProgramHash) -> Result<(), RegistryError>;

    /// Check if program is allowed for on-chain use
    pub fn is_allowed(&self, hash: &CairoProgramHash) -> bool;
}

Operation Execution

impl ExecutionContext {
    /// Execute ZK operation with gas metering
    pub fn execute_zk_operation(
        &mut self,
        op: ZKOperation,
    ) -> Result<ExecutionResult, ExecutionError> {
        match op {
            ZKOperation::SubmitProof { proof, gas_limit } => {
                self.verify_and_store_proof(proof, gas_limit)
            }
            ZKOperation::RegisterProgram { program } => {
                self.register_program(program)
            }
            ZKOperation::VerifyProof { proof } => {
                self.verify_proof_only(proof)
            }
        }
    }

    /// Verify proof and store if valid
    fn verify_and_store_proof(
        &mut self,
        proof: StarkProof,
        gas_limit: u64,
    ) -> Result<ExecutionResult, ExecutionError>;

    /// Register Cairo program in registry
    fn register_program(
        &mut self,
        program: CairoProgram,
    ) -> Result<ExecutionResult, ExecutionError>;

    /// Verify proof without storing (read-only)
    fn verify_proof_only(
        &self,
        proof: StarkProof,
    ) -> Result<ExecutionResult, ExecutionError>;
}

Core Cairo Programs

The following Cairo programs are bundled with Stoolap Chain:

  1. state_transition.cairo

    • Validates RowTrie state transitions
    • Inputs: previous_root, operations[], new_root
    • Outputs: valid (bool)

  2. hexary_verify.cairo

    • Verifies HexaryProof in Cairo
    • Inputs: row_id, value, proof, expected_root
    • Outputs: valid (bool)

  3. merkle_batch.cairo

    • Verifies batch of Merkle proofs
    • Inputs: proofs[], expected_root
    • Outputs: valid (bool), count (u64)

Encoding Format

StarkProof Encoding (Solana-style)

Field Size Description
program_hash 32 bytes Blake3 hash of Cairo source
inputs_len 4 bytes Length of inputs
inputs variable Program inputs
outputs_len 4 bytes Length of outputs
outputs variable Program outputs
proof_len 4 bytes Length of STWO proof
proof variable STWO proof bytes
public_inputs_len 4 bytes Length of public inputs
public_inputs variable Public inputs for verification

CairoProgram Encoding

Field Size Description
hash 32 bytes Blake3 hash
source_len 4 bytes Length of source
source variable Cairo source code
sierra_len 4 bytes Length of Sierra IR
sierra variable Sierra bytes
casm_len 4 bytes Length of CASM
casm variable CASM bytes
version 4 bytes Cairo compiler version

Gas Costs

  • Register program: 100,000 gas (one-time)
  • Submit proof: 50,000 + (proof_size / 100) gas
  • Verify proof: 100,000 + (public_inputs_size / 10) gas

Safety Limits

  • Maximum program source: 1 MB
  • Maximum proof size: 500 KB
  • Maximum public inputs: 100 KB
  • Maximum programs per registry: 10,000

Rationale

Why Native Rust Integration?

  1. Performance - Direct linking vs IPC/HTTP overhead
  2. Simplicity - Single binary deployment
  3. Safety - Compile-time guarantees, no external dependencies

Why Cairo Program Allowlist?

  1. Security - Prevent arbitrary code execution
  2. Gas Safety - Predictable verification costs
  3. Governance - Community control of approved programs

Why Blake3 for Program Hash?

  1. Speed - Faster than SHA-256 for large source files
  2. Security - Cryptographically secure
  3. Uniqueness - Guaranteed collision resistance

Why Bundle Core Programs?

  1. Bootstrapping - Basic functionality available at genesis
  2. Trust - Core programs audited with chain
  3. Consistency - All nodes have same reference implementations

Implementation

Phase 1: Core Infrastructure

  1. STWO Dependency

    • Add stwo crate to Cargo.toml
    • Implement prover wrapper
    • Add verifier wrapper

  2. Cairo Compiler Integration

    • Add cairo-lang-compiler as build dependency
    • Implement compilation pipeline
    • Add program hash computation

  3. Program Registry

    • Implement CairoProgramRegistry
    • Add persistence to state
    • Implement allowlist management

  4. ZK Operations

    • Add ZKOperation enum
    • Implement execution in ExecutionContext
    • Add gas metering

  5. Core Cairo Programs

    • Write state_transition.cairo
    • Write hexary_verify.cairo
    • Write merkle_batch.cairo
    • Compile and bundle

Dependencies

  • Requires: RFC-0101, RFC-0102, RFC-0103 (all accepted)
  • Enables: RFC-0202 (Compressed Proofs), RFC-0203 (Confidential Queries), RFC-0204 (L2 Rollup)

Testing Requirements

  • Unit tests for all components
  • Integration tests for end-to-end flow
  • Property tests for proof verification
  • Fuzzing for compiler integration
  • Benchmarks for proof generation/verification

Performance Targets

Metric Target
Program compilation <5s for 1KB source
Proof generation <1s for simple program
Proof verification <100ms on Cairo VM
Program registration <500ms
Registry lookup <1ms

Security Considerations

  1. Program Allowlist - Only approved programs can execute
  2. Gas Metering - Prevent resource exhaustion
  3. Proof Size Limits - Prevent DoS via large proofs
  4. Deterministic Compilation - Same source always produces same hash
  5. Sandboxed Execution - Cairo VM provides isolation
  6. Formal Verification - Core programs should be formally verified

Backward Compatibility

This RFC adds new functionality without breaking existing behavior:

  • Existing operations continue to work
  • HexaryProofs remain supported
  • New ZK operations are opt-in

Related Use Cases

Related RFCs

Open Questions

  1. Should program registration require a bond to prevent spam?
  2. What's the governance process for allowlisting programs?
  3. Should there be a program deprecation mechanism?
  4. How do we handle STWO protocol upgrades?

References