zk-perp: Zero-Knowledge Perpetual DEX

A fully functional proof-of-concept for a perpetual futures decentralized exchange (DEX) that uses zero-knowledge proofs for state transition verification. Built with RISC Zero zkVM.

Table of Contents

1. Overview
2. Architecture
3. How It Works
4. Project Structure
5. Core Components
6. Running the System
7. API Reference
8. Technical Deep Dive

---

Overview

What is a Perpetual DEX?

A perpetual futures exchange allows traders to speculate on asset prices with leverage without expiration dates. Unlike traditional futures that expire quarterly, perpetuals use a funding rate mechanism to keep prices aligned with the underlying spot market.

Why Zero-Knowledge Proofs?

Traditional exchanges (even decentralized ones) require users to trust that:

• Order matching is fair
• Balances are computed correctly
• Liquidations happen at the right time

With ZK proofs, anyone can verify that every state transition follows the rules—without needing to trust anyone. The proofs are cryptographic guarantees that:

1. Orders matched at the correct prices
2. Balances updated correctly
3. All transactions were properly authorized
4. No funds appeared or disappeared

This Implementation

This PoC implements a sovereign rollup architecture:

• Sequencer: Processes transactions and generates ZK proofs
• DA Layer: Stores all transaction data for reproducibility
• Verifier: Independently verifies proofs

It replicates the architecture of Lighter but uses RISC Zero's zkVM instead of custom Plonky2 circuits.

---

Architecture

                                ┌─────────────────────────────────────┐
                                │           User Interface            │
                                │     (CLI, SDK, or Web Frontend)     │
                                └──────────────┬──────────────────────┘
                                               │
                                               ▼
┌──────────────────────────────────────────────────────────────────────────────┐
│                              SEQUENCER (HTTP API)                            │
│  ┌────────────────┐  ┌────────────────┐  ┌────────────────┐                  │
│  │ Transaction    │  │    Order       │  │    State       │                  │
│  │  Validation    │──▶│   Matching     │──▶│   Updates      │                  │
│  └────────────────┘  └────────────────┘  └────────────────┘                  │
│         │                    │                    │                          │
│         └────────────────────┴────────────────────┘                          │
│                              │                                               │
│                              ▼                                               │
│                     ┌────────────────┐                                       │
│                     │  Batch Builder │                                       │
│                     │ (100 txs or 5s)│                                       │
│                     └───────┬────────┘                                       │
│                             │                                                │
└─────────────────────────────┼────────────────────────────────────────────────┘
                              │
              ┌───────────────┴───────────────┐
              │                               │
              ▼                               ▼
┌─────────────────────────┐      ┌─────────────────────────┐
│     DA Layer            │      │      ZK Prover          │
│                         │      │                         │
│  ┌───────────────────┐  │      │  ┌───────────────────┐  │
│  │  batches/         │  │      │  │   RISC Zero       │  │
│  │  ├── 000001.batch │  │      │  │   zkVM Guest      │  │
│  │  ├── 000002.batch │  │      │  │                   │  │
│  │  └── ...          │  │      │  │   Verifies:       │  │
│  ├───────────────────┤  │      │  │   - Signatures    │  │
│  │  proofs/          │  │      │  │   - State roots   │  │
│  │  ├── 000001.proof │  │      │  │   - Matching      │  │
│  │  └── ...          │  │      │  │   - Margins       │  │
│  ├───────────────────┤  │      │  └───────────────────┘  │
│  │  index.json       │  │      │                         │
│  └───────────────────┘  │      │   Output: STARK Proof   │
│                         │      │                         │
└─────────────────────────┘      └───────────┬─────────────┘
                                             │
                                             ▼
                               ┌─────────────────────────┐
                               │       VERIFIER          │
                               │                         │
                               │  - Reads from DA        │
                               │  - Verifies proofs      │
                               │  - Tracks verified      │
                               │    state root           │
                               │                         │
                               │  Anyone can run this!   │
                               └─────────────────────────┘

---

How It Works

The Transaction Lifecycle

1. USER SUBMITS TRANSACTION
   │
   │  POST /tx { signed_transaction: { tx: {...}, signature: [...] } }
   │
   ▼
2. SEQUENCER RECEIVES TX
   │
   ├─► Verify ed25519 signature
   │   └─► Public key must match account owner
   │
   ├─► Validate transaction
   │   ├─► Account exists?
   │   ├─► Nonce correct?
   │   ├─► Sufficient balance?
   │   └─► Valid market/order params?
   │
   ├─► Execute against state
   │   ├─► Update account balances
   │   ├─► Match orders (if applicable)
   │   └─► Update positions
   │
   └─► Add to pending batch
   │
   ▼
3. BATCH PROCESSING (every 100 txs or 5 seconds)
   │
   ├─► Collect pending transactions
   │
   ├─► Compute state roots
   │   ├─► Pre-state root (before batch)
   │   └─► Post-state root (after batch)
   │
   ├─► Store batch in DA layer
   │
   └─► Generate ZK proof
   │
   ▼
4. ZK PROOF GENERATION (RISC Zero)
   │
   │  Input (private):
   │  ├─► Pre-state root
   │  ├─► Post-state root
   │  ├─► All transactions
   │  └─► Merkle witnesses
   │
   │  Guest program verifies:
   │  ├─► Each signature is valid
   │  ├─► Nonces are correct
   │  ├─► Balances update correctly
   │  ├─► Order matching is fair
   │  └─► State transitions are valid
   │
   │  Output (public journal):
   │  ├─► Pre-state root
   │  ├─► Post-state root
   │  ├─► Batch hash
   │  └─► Transaction count
   │
   ▼
5. PROOF STORED IN DA
   │
   │  Anyone can now verify the batch!
   │
   ▼
6. VERIFIER CHECKS PROOF
   │
   ├─► Load batch from DA
   ├─► Load proof from DA
   ├─► Verify proof against guest image ID
   ├─► Check state continuity (roots chain)
   └─► Update verified state

State Model: The Hypertree

The system maintains state across 6 Merkle trees, combined into a single root:

                    ┌─────────────────┐
                    │   Global Root   │
                    └────────┬────────┘
                             │
            ┌────────────────┴────────────────┐
            │                                 │
     ┌──────┴──────┐                  ┌───────┴───────┐
     │             │                  │               │
  ┌──┴──┐      ┌───┴───┐          ┌───┴───┐      ┌───┴───┐
  │     │      │       │          │       │      │       │
 T1    T2     T3      T4         T5      T6

Tree	Name	Contents	Key Format
T1	Account	Balances, nonces, metadata	hash(account_id)
T2	Account Orders	Orders per account	hash(account_id || market_id || idx)
T3	Order Book	All active orders	price_bits(64) || nonce(8)
T4	Position	Open positions	hash(account_id || market_id)
T5	Pool	LP pools (future)	hash(pool_id)
T6	System	Markets, oracle, config	hash(key)

Order Matching: Price-Time Priority

The order book uses a price-time priority matching algorithm:

Example: New BUY order arrives at $50,000

ASKS (Sell orders, sorted low→high):
┌─────────────────────────────────────────────────────────┐
│  $50,100  │ 1.0 BTC │ timestamp: 100  │ ← Not filled   │
│  $50,050  │ 0.5 BTC │ timestamp: 90   │ ← Not filled   │
│  $50,000  │ 0.3 BTC │ timestamp: 80   │ ← Filled 2nd   │
│  $50,000  │ 0.2 BTC │ timestamp: 70   │ ← Filled 1st   │ (earlier)
│  $49,950  │ 0.1 BTC │ timestamp: 60   │ ← Filled 0th   │ (best price)
└─────────────────────────────────────────────────────────┘

Matching order:
1. Best price first ($49,950 before $50,000)
2. At same price, earliest order first (timestamp 70 before 80)

This is exactly what the ZK proof verifies—that matching followed these rules.

---

Project Structure

zk-perp/
├── Cargo.toml              # Workspace configuration
├── README.md               # This file
│
├── crates/
│   ├── core/               # Shared types and cryptographic primitives
│   │   └── src/
│   │       ├── types/      # Order, Account, Position, Market
│   │       ├── merkle/     # Sparse Merkle Tree, SHA-256 hashing
│   │       ├── transactions/ # Transaction types (Deposit, PlaceOrder, etc.)
│   │       ├── batch.rs    # Batch input/output for ZK prover
│   │       └── crypto.rs   # ed25519 signatures
│   │
│   ├── orderbook/          # Order matching engine
│   │   └── src/
│   │       ├── book.rs     # BTreeMap-based order book
│   │       └── matching.rs # Price-time priority matching
│   │
│   ├── state/              # Global state management
│   │   └── src/
│   │       └── lib.rs      # GlobalState with all 6 trees
│   │
│   ├── oracle/             # Price feeds
│   │   └── src/
│   │       └── lib.rs      # MockOracle, SimulatedOracle
│   │
│   └── da/                 # Data Availability layer
│       └── src/
│           └── lib.rs      # AppendLog (file-based)
│
├── methods/                # RISC Zero guest program
│   ├── guest/
│   │   └── src/
│   │       └── main.rs     # ZK verification logic
│   └── build.rs
│
├── host/                   # Prover (generates ZK proofs)
│   └── src/
│       └── lib.rs          # Prover struct, proof generation
│
├── sequencer/              # Main application server
│   └── src/
│       ├── lib.rs          # Sequencer logic
│       └── api.rs          # HTTP API (Axum)
│
└── verifier/               # Standalone verification node
    └── src/
        ├── lib.rs          # Verification logic
        └── main.rs         # CLI and HTTP API

---

Core Components

1. Cryptographic Primitives (crates/core/src/crypto.rs)

Ed25519 Digital Signatures provide authentication:

// Generate a keypair
let keypair = Keypair::generate();

// Sign a transaction
let signed_tx = keypair.sign_transaction(&tx)?;

// Verify a signature
let valid = verify_transaction(&signed_tx, &public_key)?;

Ed25519 is chosen for:

• Fast signing and verification (critical for trading)
• 128-bit security level
• Deterministic signatures (same input = same signature)
• Compact signatures (64 bytes)

2. Merkle Trees (crates/core/src/merkle/)

Sparse Merkle Trees provide O(log n) proofs of state:

// A Merkle proof proves a value exists at a key
pub struct MerkleProof {
    pub key: Hash,           // The key being proved
    pub value: Hash,         // Hash of the value
    pub siblings: Vec<Hash>, // Sibling hashes along the path
    pub path: Vec<bool>,     // Direction at each level (left/right)
}

// Verification: rehash from leaf to root
fn verify(&self, root: &Hash) -> bool {
    let mut current = self.value;
    for (sibling, is_right) in self.siblings.iter().zip(self.path.iter()) {
        current = if *is_right {
            hash_pair(sibling, &current)
        } else {
            hash_pair(&current, sibling)
        };
    }
    current == *root
}

The tree structure:

Level 3 (root):     [H(H01, H23)]
                    /            \
Level 2:        [H01]            [H23]
               /     \          /     \
Level 1:    [H0]    [H1]     [H2]    [H3]
           /   \   /   \    /   \   /   \
Level 0:  V0   V1 V2   V3  V4   V5 V6   V7   (leaf values)

Proof for V2:
- value = V2
- siblings = [H3, H01]
- path = [false, true]  (left at level 1, right at level 2)

3. Order Book (crates/orderbook/)

The order book uses BTreeMap for efficient price-level management:

pub struct OrderBook {
    /// Bids sorted by price (highest first)
    bids: BTreeMap<Reverse<Price>, VecDeque<Order>>,
    /// Asks sorted by price (lowest first)
    asks: BTreeMap<Price, VecDeque<Order>>,
    /// Quick lookup of order locations
    order_locations: HashMap<OrderId, OrderLocation>,
}

Matching algorithm:

fn match_order(&mut self, taker: Order) -> Vec<Fill> {
    let fills = vec![];

    // For a BUY, iterate asks from lowest price
    // For a SELL, iterate bids from highest price
    let levels = match taker.side {
        Side::Bid => &mut self.asks,
        Side::Ask => &mut self.bids,
    };

    for (price, orders) in levels {
        // Check if price crosses (BUY price >= ASK price)
        if !price_crosses(taker.side, taker.price, *price) {
            break;
        }

        // Match against orders at this level (FIFO)
        while let Some(maker) = orders.front_mut() {
            let fill_qty = min(taker.remaining, maker.remaining);
            fills.push(Fill { maker, taker, qty: fill_qty, price: *price });

            // Update remaining quantities...
        }
    }

    fills
}

4. ZK Guest Program (methods/guest/src/main.rs)

The guest program runs inside RISC Zero's zkVM and verifies:

fn main() {
    // Read private inputs
    let input: BatchInput = env::read();

    // Verify each transaction
    for (tx, witness) in input.transactions.iter().zip(input.witnesses.iter()) {
        verify_transaction(&tx, &witness);
    }

    // Compute batch hash
    let batch_hash = compute_batch_hash(&input.transactions);

    // Commit public outputs to journal
    env::commit(&BatchOutput {
        pre_state_root: input.pre_state_root,
        post_state_root: input.post_state_root,
        batch_hash,
        tx_count: input.transactions.len() as u32,
    });
}

Transaction verification includes:

• Deposits: Account exists, nonce correct, balance increased
• Withdrawals: Sufficient balance, balance decreased correctly
• Place Order: Margin requirements met, matching follows price-time priority
• Cancel Order: Order exists, belongs to account
• Liquidations: Position is underwater at oracle price

5. Data Availability (crates/da/)

The DA layer ensures all data needed to verify or reconstruct state is available:

pub struct AppendLog {
    base_path: PathBuf,
    batch_cache: HashMap<u64, Batch>,
    index: DaIndex,
}

impl AppendLog {
    /// Append a batch with state continuity validation
    pub fn append_batch(
        &mut self,
        transactions: Vec<Transaction>,
        pre_root: Hash,
        post_root: Hash,
        batch_hash: Hash,
    ) -> Result<u64, DaError> {
        // Verify chain: pre_root must match previous post_root
        if self.index.last_batch_id > 0 {
            if pre_root != self.index.current_state_root {
                return Err(DaError::StateRootMismatch { ... });
            }
        }

        // Save batch to disk
        let batch = Batch { id, transactions, pre_root, post_root, ... };
        self.save_batch(&batch)?;

        // Update index
        self.index.current_state_root = post_root;
        Ok(batch_id)
    }
}

File structure:

data/
├── batches/
│   ├── 000001.batch   # Binary serialized batch
│   ├── 000002.batch
│   └── ...
├── proofs/
│   ├── 000001.proof   # Serialized RISC Zero receipt
│   └── ...
└── index.json         # Metadata (last batch, current root, etc.)

---

Running the System

Prerequisites

# Install Rust
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

# Install RISC Zero toolchain (for real ZK proving)
curl -L https://risczero.com/install | bash
rzup install

Build

# Clone the repository
cd zk-perp

# Build all crates
cargo build --release

# Run tests
cargo test

Start the Sequencer

# With mock proving (fast, for development)
cargo run --bin sequencer -- --port 8080 --data-dir ./data

# With real ZK proving (slow, ~16 seconds per batch)
cargo run --bin sequencer --features risc0 -- --port 8080 --real-proving

Start the Verifier

# In another terminal
cargo run --bin verifier -- --port 8081 --data-dir ./data

# With auto-verify on startup
cargo run --bin verifier -- --auto-verify

Example Workflow

# 1. Register an account
curl -X POST http://localhost:8080/accounts \
  -H "Content-Type: application/json" \
  -d '{"public_key": "0x1234..."}'

# 2. Check account
curl http://localhost:8080/accounts/0

# 3. Submit a deposit transaction
curl -X POST http://localhost:8080/tx \
  -H "Content-Type: application/json" \
  -d '{
    "transaction": {
      "tx": { "Deposit": { "account_id": 0, "asset_id": 0, "amount": "1000000000000000000", "nonce": 1 }},
      "signature": "0x..."
    }
  }'

# 4. Check orderbook
curl http://localhost:8080/markets/0/orderbook

# 5. Check verification status
curl http://localhost:8081/stats

---

API Reference

Sequencer API (Port 8080)

Endpoint	Method	Description
/health	GET	Health check with block number
/status	GET	System stats, DA stats, market info
/accounts	POST	Register new account
/accounts/:id	GET	Get account details
/accounts/:id/positions	GET	Get positions for account
/tx	POST	Submit signed transaction
/markets/:id/orderbook	GET	Get order book snapshot
/markets/:id/price	GET	Get current price
/admin/batch	POST	Trigger batch processing

Verifier API (Port 8081)

Endpoint	Method	Description
/health	GET	Health check
/stats	GET	Verification statistics
/batch/:id	GET	Get batch verification status
/batch/:id/verified	GET	Check if batch is verified
/verify	POST	Verify next pending batch
/verify/all	POST	Verify all pending batches

---

Technical Deep Dive

Zero-Knowledge Proofs: STARK vs SNARK

This system uses STARKs (via RISC Zero) rather than SNARKs:

Property	STARK	SNARK
Trusted setup	No	Usually yes
Post-quantum secure	Yes	No
Proof size	~100 KB	~200 bytes
Proving time	Slower	Faster
Verification time	Fast	Very fast

RISC Zero enables writing verification logic in Rust rather than specialized circuit languages, making development much faster.

How the ZK Proof Works

1. Execution: The sequencer executes transactions and records state changes
2. Witness Generation: For each state access, a Merkle proof (witness) is recorded
3. Guest Execution: The guest program re-executes inside the zkVM, verifying:
   • Every Merkle proof against the claimed roots
   • Business logic (margins, matching, balances)
4. Proof Generation: RISC Zero generates a STARK proof of correct execution
5. Verification: Anyone can verify the proof in milliseconds

The key insight: re-execution inside the zkVM proves the state transition is valid without revealing private data.

Signature Scheme: Ed25519

Ed25519 uses the Edwards curve:

y² = x³ + ax² + x  (where a = 486662)

Base point: G (standard generator)
Private key: k (256-bit scalar)
Public key: K = kG (point on curve)

Signing (message m):
  r = hash(private_key || m)  // deterministic nonce
  R = rG
  s = r + hash(R || K || m) * k
  signature = (R, s)

Verification:
  Check: sG == R + hash(R || K || m) * K

Merkle Tree Optimization: Zero Hashes

For sparse trees, most leaves are empty. Instead of storing all zeros, we precompute "zero hashes":

// zero_hash[0] = hash of empty leaf
// zero_hash[i] = hash(zero_hash[i-1], zero_hash[i-1])

static ZERO_HASHES: Lazy<[Hash; 256]> = Lazy::new(|| {
    let mut hashes = [[0u8; 32]; 256];
    // hashes[0] = ZERO_HASH (all zeros)
    for i in 1..256 {
        hashes[i] = hash_pair(&hashes[i-1], &hashes[i-1]);
    }
    hashes
});

This allows constant-time proofs for non-existent keys.

State Continuity

Every batch's pre_state_root must equal the previous batch's post_state_root. This creates an unbroken chain:

Genesis  →  Batch 1  →  Batch 2  →  Batch 3
Root₀    →  Root₁    →  Root₂    →  Root₃

Batch 1: pre_root = Root₀, post_root = Root₁
Batch 2: pre_root = Root₁, post_root = Root₂  ✓ (chains correctly)
Batch 3: pre_root = Root₂, post_root = Root₃  ✓

Both the DA layer and verifier enforce this continuity.

---

Security Considerations

What the ZK Proof Guarantees

• All signatures are valid
• Balances cannot go negative
• Order matching follows price-time priority
• State transitions are deterministic

What Requires Additional Trust

• Sequencer Liveness: The sequencer must be online to process transactions
• DA Availability: Batch data must be available for verification
• Oracle Prices: Currently uses mock/simulated prices

Production Hardening (Future Work)

1. Decentralized Sequencer: Multiple sequencers with leader election
2. External DA: Use Celestia, EigenDA, or similar
3. Chainlink Integration: Real price feeds with signature verification
4. Liquidation Bot: Automated position monitoring
5. Bridge Contracts: Connect to L1 for deposits/withdrawals

---

License

MIT License - See LICENSE file for details.

---

Contributing

This is a proof-of-concept implementation. Contributions welcome!

1. Fork the repository
2. Create a feature branch
3. Write tests for new functionality
4. Submit a pull request

---

Acknowledgments

• RISC Zero for the zkVM
• Lighter for the architectural inspiration
• The Rust community for excellent cryptographic libraries