A from-scratch STARK (Scalable Transparent ARgument of Knowledge) proof system that generates and verifies Fibonacci sequence proofs on Solana. Single-transaction verification with 36-bit conjectured soundness (~1.24M CU).
Are you a Solana/ZK company?
Im open to submit a resume :)
STARK verification is computationally intensive — field inversions, Merkle proof checks, polynomial evaluations, FRI folding. This implementation fits full verification within Solana's 1.4M CU limit in a single transaction by:
- Goldilocks field (
p = 2^64 - 2^32 + 1): Fast modular reduction viau128intermediates, no division needed forreduce128 - Precomputed constants:
TWO_INV = (P+1)/2eliminates a field inversion per FRI fold - Solana SHA-256 syscall: Merkle hashing uses
sol_sha256(~100 CU) instead of software SHA-256 (~10,000 CU) - Zero-copy proof parsing:
QueryReaderwalks proof bytes in-place, no deserialization allocations - Proof-of-work grinding: 20-bit nonce search adds free security bits at prover cost only (~1M hash attempts, ~2 seconds)
- Single-tx verification: 4 queries verified in one transaction (~1.24M CU)
// Goldilocks reduction: 2^64 ≡ 2^32 - 1 (mod p), so no division
fn reduce128(x: u128) -> u64 {
let x_lo = x as u64;
let x_hi = (x >> 64) as u64;
let mid = (x_hi as u128) * ((1u128 << 32) - 1);
// ... two rounds of shift-and-add, no u128 division
}solana-stark-verify/
├── onchain/
│ └── lib.rs # On-chain STARK verifier (single file for solpg)
└── offchain/
└── src/main.rs # Off-chain prover + devnet transaction submission
┌─────────────────────────────────────────────────────────────┐
│ OFF-CHAIN: STARK Prover │
├─────────────────────────────────────────────────────────────┤
│ 1. Generate Fibonacci trace │
│ a[0]=1, a[1]=1, a[i+2] = a[i+1] + a[i] │
│ │
│ 2. Interpolate via IFFT, evaluate on LDE coset domain │
│ LDE domain = 512 points (16x blowup of 32-point trace) │
│ │
│ 3. Commit trace via Merkle tree → trace_root │
│ │
│ 4. Derive alpha from trace_root (Fiat-Shamir) │
│ Compute composition polynomial: │
│ C(x) = transition + α·b0 + α²·b1 + α³·b_result │
│ │
│ 5. Commit composition → composition_root │
│ │
│ 6. FRI protocol: 7 folding layers │
│ Each layer halves the domain, commits via Merkle tree │
│ Challenges derived via Fiat-Shamir from FRI roots │
│ │
│ 7. Grind for PoW nonce (20 bits, ~1M attempts) │
│ Also enforces unique query indices during grinding │
│ │
│ 8. Assemble proof: ~16KB │
│ Headers + Merkle roots + 4 query openings + FRI proofs │
└─────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────┐
│ ON-CHAIN: Upload & Verify │
├─────────────────────────────────────────────────────────────┤
│ 1. INIT (1 tx) — create account, store public inputs │
│ 2. WRITE_PROOF (~19 txs) — upload proof in 900-byte chunks │
│ 3. VERIFY (1 tx) — single-transaction verification: │
│ • Re-derive Fiat-Shamir challenges │
│ • Check 20-bit grinding proof-of-work │
│ • Reject duplicate query indices │
│ • Verify FRI final poly commitment (rebuild on-chain) │
│ • Verify trace Merkle proofs (3 per query) │
│ • Verify composition Merkle proofs │
│ • Evaluate AIR constraints at query points │
│ • Verify FRI with authenticated siblings │
│ • Check final polynomial consistency │
│ │
│ Total: ~21 transactions, ~1.24M CU for verification │
└─────────────────────────────────────────────────────────────┘
| Parameter | Value | Description |
|---|---|---|
| Field | Goldilocks (p = 2^64 - 2^32 + 1) | 64-bit prime with 2-adicity of 32 |
| Trace length | 32 | 2^5, Fibonacci sequence length |
| Blowup factor | 16 | LDE domain = 512 points |
| FRI layers | 7 | log2(512) - log2(4) folding steps |
| Queries | 4 | Random query positions |
| Grinding bits | 20 | Proof-of-work on query seed (~1M prover attempts) |
| Merkle depth | 9 | log2(512) |
| Final poly | 4 evaluations | Remaining after FRI folding |
| Conjectured soundness | 36 bits | 4 × log2(16) + 20 grinding |
| Constraint | Formula | Domain |
|---|---|---|
| Transition | T(g²x) - T(gx) - T(x) = 0 |
All trace points except last 2 |
| Boundary 0 | T(1) = a0 |
First trace element |
| Boundary 1 | T(g) = a1 |
Second trace element |
| Boundary result | T(g^{n-1}) = result |
Last trace element |
This verifier was hardened after a security audit. Every on-chain operation enforces:
| Check | Description |
|---|---|
| Authority binding | Only the initializing signer can write proofs or trigger verification |
| Hardcoded security params | num_queries, num_fri_layers, merkle_depth, grinding_bits are on-chain constants, not read from proof header |
| Proof header validation | Header values must exactly match on-chain constants or verification is rejected |
| Exact parameter pinning | trace_len must be exactly 32 and blowup must be exactly 16 — not just power-of-two within range |
| Grinding proof-of-work | Query seed must have 20 leading zero bits (nonce included in Fiat-Shamir) |
| Duplicate query rejection | All query indices must be unique — prevents soundness reduction from repeated queries |
| FRI final poly binding | Final polynomial Merkle root is rebuilt on-chain and verified against fri_roots[last] — prevents Fiat-Shamir transcript manipulation |
| FRI sibling authentication | Both val AND sibling get separate Merkle proofs — prevents forged sibling attacks |
| Write-after-verify freeze | Proof data writes are rejected once account status reaches verified (2) or failed (3) |
| Reinit protection | INIT rejects already-initialized accounts |
| Stale data clearing | Proof region is zeroed during initialization |
| Runtime field checks | inv(0) panics in release builds (not just debug) |
| Ownership verification | All accounts checked for owner == program_id |
| Bounds checking | WRITE_PROOF validates offset + length < account size |
| Account size guard | Rejects accounts with data smaller than header size |
| System | Approach | CU Cost | Proof Size | Security | Trusted Setup | Quantum-Safe |
|---|---|---|---|---|---|---|
| This project | From-scratch STARK | ~1.24M (1 tx) | ~16KB | 36-bit | No | Yes |
| pqzk-labs (Winterfell) | Library-based STARK | ~1.1M (1 tx) | 4.4KB | 128-bit | No | Yes |
| SP1 (Succinct) | STARK→Groth16 wrap | ~280K | 260B | 128-bit | Yes | No |
| RISC Zero | STARK→Groth16 wrap | <200K | 256B | 128-bit | Yes | No |
| groth16-solana (Light) | Groth16 via BN254 | <200K | 256B | 128-bit | Yes | No |
Why the security gap with pqzk-labs? Their 128-bit result proves a trivially small 8-row affine counter (1 constraint, degree 1). With only 8 trace rows, Merkle trees are shallow (depth 7) and FRI collapses quickly, so 30 queries fit in a single tx CU budget. Our 32-row Fibonacci trace with 4 constraints requires deeper Merkle trees (depth 9) and more FRI work per query.
Why not just use Groth16? STARK verification requires no trusted setup and is quantum-resistant (hash-based). Groth16 relies on elliptic curve assumptions broken by quantum computers and requires a trusted setup ceremony. This project demonstrates that native STARK verification on Solana is feasible — the security-CU tradeoff improves as Solana raises CU limits or as batched Merkle proofs reduce per-query costs.
| Offset | Size | Field |
|---|---|---|
| 0..8 | 8 bytes | Discriminator (STARK\0\0\0) |
| 8 | 1 byte | Status: 0=empty, 1=proof_loaded, 2=verified, 3=failed |
| 9..41 | 32 bytes | Authority pubkey |
| 48..56 | 8 bytes | a0 (first Fibonacci input) |
| 56..64 | 8 bytes | a1 (second Fibonacci input) |
| 64..72 | 8 bytes | result (claimed output) |
| 72..80 | 8 bytes | trace_len |
| 80..88 | 8 bytes | blowup_factor |
| 88 | 1 byte | batch_bitmap |
| 89..96 | 7 bytes | reserved |
| 96.. | ~16KB | Proof data |
| Opcode | Name | Data Format | Accounts |
|---|---|---|---|
| 0x01 | INIT | [0x01, a0(8), a1(8), result(8), trace_len(8), blowup(8)] |
[authority(s,w), account(s,w)] |
| 0x02 | WRITE_PROOF | [0x02, offset_u16_le, chunk...] |
[authority(s), account(w)] |
| 0x03 | VERIFY | [0x03] |
[authority(s), account(w)] |
| 0x04 | VERIFY_BATCH | [0x04, batch_index: u8] |
[authority(s), account(w)] |
# Install Solana CLI
sh -c "$(curl -sSfL https://release.solana.com/v2.2.0/install)"
# Install Rust
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | shThe on-chain program is a single file (onchain/lib.rs) designed for Solana Playground:
- Open beta.solpg.io
- Create a new project
- Paste
onchain/lib.rsintolib.rs - Build & Deploy to devnet
Or deploy via CLI:
cargo build-sbf
solana program deploy target/deploy/stark_verify.so --url devnetEdit offchain/src/main.rs:
const PROGRAM_ID: &str = ""; // Paste your deployed program ID here
const RPC_URL: &str = "https://api.devnet.solana.com";cd offchain
# With explicit keypair
cargo run --bin stark-devnet -- /path/to/keypair.json
# With default Solana CLI keypair
cargo run --bin stark-devnetThe pipeline:
- Generates a STARK proof for
fib(1, 1, 32) = 2178309 - Grinds for a 20-bit proof-of-work nonce with unique query indices (~1M attempts, ~2 seconds)
- Creates a verification account on-chain
- Uploads the ~16KB proof in ~19 chunked transactions
- Triggers single-tx on-chain verification (~1.24M CU)
- Reads account status to confirm
VERIFIED
| Operation | CU Cost | Notes |
|---|---|---|
| INIT | ~1,800 | Write header + clear proof region |
| WRITE_PROOF | ~1,300 | Per chunk (memcpy) |
| VERIFY | ~1,238,000 | All 4 queries in single tx |
The verify transaction checks all 4 queries: trace Merkle proofs + composition proof + AIR evaluation + 7 FRI layers with dual Merkle proofs + grinding check + duplicate query rejection + FRI final poly commitment + Fiat-Shamir re-derivation. Fits within 1.4M CU with ~160K headroom.
Header (76 bytes):
trace_root 32 bytes Merkle root of trace LDE
composition_root 32 bytes Merkle root of composition poly
num_fri_layers 2 bytes Must match on-chain constant (7)
num_queries 2 bytes Must match on-chain constant (4)
fri_final_poly_len 2 bytes Must match on-chain constant (4)
merkle_depth 2 bytes Must match on-chain constant (9)
grinding_nonce 4 bytes Proof-of-work nonce (20-bit grinding)
FRI Roots: 224 bytes 7 × 32-byte Merkle roots
Final Poly: 32 bytes 4 × 8-byte field elements
Per Query (×4):
trace_values 24 bytes t(x), t(gx), t(g²x)
trace_proofs 864 bytes 3 × 9 × 32-byte Merkle paths
comp_value 8 bytes composition polynomial at x
comp_proof 288 bytes 9 × 32-byte Merkle path
FRI layers variable 7 layers, each: val(8) + sib(8) + 2 Merkle proofs
- Fibonacci only — the AIR constraints are hardcoded for
a[i+2] = a[i+1] + a[i] - 36-bit soundness — production needs 80-128 bits (more queries via batched verification, or batched Merkle proofs)
- Small trace — 32 steps. Real-world STARKs operate on traces of 2^20+
- ~19 upload transactions — ~16KB proof chunked at 900 bytes/tx due to Solana tx size limits
- Single-threaded prover — no parallelism in FFT or Merkle tree construction
- Higher soundness — multi-batch verification for 80+ bit security, or batched Merkle proofs (Octopus algorithm)
- FRI folding factor 4 — reduce FRI layers from 7 to 3, fewer field inversions per query
- Configurable AIR — pluggable constraint systems beyond Fibonacci
- Lookup arguments — for range checks and memory consistency
- Recursive composition — verify a STARK proof inside a STARK proof
- GPU-accelerated prover — parallel FFT and Merkle hashing
- STARK paper — Ben-Sasson et al. (2018)
- FRI protocol — Fast Reed-Solomon IOP of Proximity
- Goldilocks field — 2^64 - 2^32 + 1 properties
- Anatomy of a STARK — Tutorial series
- Full L1 On-Chain ZK-STARK+PQC on Solana — pqzk-labs measurement study
- StarkWare: Safe and Sound — STARK Security — Grinding analysis
- Optimizing Merkle Tree Multi-Queries — Batched proof compression
- Winterfell STARK Prover — Reference implementation
- Solana Compute Budget — CU limits and syscalls
MIT
Built with field arithmetic, Fiat-Shamir transcripts, proof-of-work grinding, and single-tx on-chain verification