8-bit Bulletproof Range Proofs on Solana

A proof-of-concept implementation of Bulletproof range proofs on Solana, enabling zero-knowledge verification that a committed value lies within the range [0, 255].

Are you a Solana/ZK company?

Im open to submit a resume :)

🔑 Key Innovation: Syscall Jailbreak

This implementation leverages the secp256k1 syscall jailbreak technique pioneered by deanmlittle/solana-secp256k1. Instead of implementing expensive elliptic curve scalar multiplication from scratch (which would blow through compute limits), we abuse the secp256k1_recover syscall to perform arbitrary EC operations at syscall-level efficiency.

The trick: secp256k1_recover is designed for signature recovery, but with carefully crafted inputs, we can coerce it into performing scalar multiplication:

// Fake "signature" that actually computes k * P
let s = mul_mod(k, &p.x, &CURVE_N);
let mut sig = [0u8; 64];
sig[0..32].copy_from_slice(&p.x.to_be_bytes());
sig[32..64].copy_from_slice(&s.to_be_bytes());
let recovered = secp256k1_recover(&[0u8; 32], recovery_id, &sig)?;

This gives us ~25,000 CU EC multiplications which makes this all possible (Thank you Dean).

---

🏗️ Architecture

Two Components

bp8/
├── program/           # On-chain Solana program (lib.rs)
│   └── lib.rs         # Bulletproof verifier (~1600 lines)
└── client/            # Off-chain Rust client (main.rs)
    └── main.rs        # Proof generation + transaction submission

On-Chain State

The verifier uses two PDAs:

PDA	Seed	Purpose
Generator PDA	["bp8-gen"]	Stores 18 elliptic curve generator points (1152 bytes)
State PDA	["bp8-state", payer, nonce]	Per-proof verification state (8 KB)

---

📊 Execution Flow

Phase 1: Setup (One-time)

┌─────────────────────────────────────────────────────────────┐
│                    GENERATOR SETUP                          │
├─────────────────────────────────────────────────────────────┤
│  1. OP_CREATE_GEN (0x01)                                    │
│     └─ Creates generator PDA                                │
│                                                             │
│  2. OP_WRITE_GENERATORS (0x02) × N chunks                   │
│     └─ Uploads 18 generator points:                         │
│        • H (blinding base)                                  │
│        • G (value base)                                     │
│        • g_0..g_7 (vector bases)                            │
│        • h_0..h_7 (vector bases)                            │
└─────────────────────────────────────────────────────────────┘

Phase 2: Proof Generation (Off-chain)

┌─────────────────────────────────────────────────────────────┐
│                 CLIENT: prove_range()                       │
├─────────────────────────────────────────────────────────────┤
│  Input: value (u64), gamma (random blinding)                │
│                                                             │
│  1. Pedersen Commitment                                     │
│     V = value·G + gamma·H                                   │
│                                                             │
│  2. Bit Decomposition                                       │
│     a_L[i] = (value >> i) & 1                               │
│     a_R[i] = a_L[i] - 1                                     │
│                                                             │
│  3. Vector Commitments (A, S)                               │
│     A = alpha·H + Σ(a_L[i]·g_i + a_R[i]·h_i)               │
│     S = rho·H + Σ(s_L[i]·g_i + s_R[i]·h_i)                 │
│                                                             │
│  4. Fiat-Shamir Challenges                                  │
│     y = H(A, S)                                             │
│     z = H(y, V)                                             │
│     x = H(z, T1, T2)                                        │
│                                                             │
│  5. Polynomial Evaluation                                   │
│     t_hat = t(x) = t_0 + t_1·x + t_2·x²                    │
│                                                             │
│  6. Inner Product Argument (log₂(n) rounds)                 │
│     Produces: L[0..2], R[0..2], a_scalar, b_scalar          │
│                                                             │
│  Output: 523-byte proof                                     │
└─────────────────────────────────────────────────────────────┘

Phase 3: On-chain Verification (56 transactions)

┌─────────────────────────────────────────────────────────────┐
│              ON-CHAIN VERIFICATION STEPS                    │
├─────────────────────────────────────────────────────────────┤
│  OP_CREATE_STATE (0x10)                                     │
│  └─ Allocate 8KB state PDA                                  │
│                                                             │
│  OP_INIT_PROOF (0x11)                                       │
│  └─ Parse proof, compute Fiat-Shamir challenges             │
│                                                             │
│  OP_VERIFY_STEP (0x20) × 56 calls:                          │
│  ┌──────────────────────────────────────────────────────┐   │
│  │ Steps 0-10:   Decompress proof points (V,A,S,T1,T2,  │   │
│  │               L[0-2], R[0-2])                         │   │
│  │                                                       │   │
│  │ Steps 11-13:  Compute inverse challenges x_j^{-1}     │   │
│  │                                                       │   │
│  │ Steps 14-16:  Build coefficient tables (y^i, 2^i)     │   │
│  │               Compute delta                           │   │
│  │                                                       │   │
│  │ Steps 17-22:  t(x) check LHS/RHS computation          │   │
│  │               LHS = t_hat·G + taux·H                  │   │
│  │               RHS = z²·V + delta·G + x·T1 + x²·T2     │   │
│  │                                                       │   │
│  │ Step 23:      VERIFY: LHS == RHS                      │   │
│  │                                                       │   │
│  │ Steps 24-35:  Inner product LHS accumulation          │   │
│  │               A + x·S + Σx²·L + Σx⁻²·R - mu·H        │   │
│  │                                                       │   │
│  │ Steps 36-37:  Compute IPA weights w_i, w_inv_i        │   │
│  │                                                       │   │
│  │ Steps 38-54:  Inner product RHS accumulation          │   │
│  │               (a·b)·U + Σ(a·w_i)·g_i +               │   │
│  │               Σ(b·w_inv_i·y^{-i})·h_i                 │   │
│  │                                                       │   │
│  │ Step 55:      VERIFY: IP_LHS == IP_RHS                │   │
│  │               ✓ PROOF VERIFIED                        │   │
│  └──────────────────────────────────────────────────────┘   │
└─────────────────────────────────────────────────────────────┘

---

🚀 Usage

Prerequisites

# Install Solana CLI
sh -c "$(curl -sSfL https://release.solana.com/v1.18.0/install)"

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

Deploy the Program

cd onchain
cargo build-sbf
solana program deploy target/deploy/bulletproof.so

Configure the Client

Edit offchain/src/main.rs:

const RPC_URL: &str = "https://api.devnet.solana.com";
const PROGRAM_ID: &str = "<YOUR-PROGRAM-ID>";
const PAYER_B58: &str = "<YOUR-KEYPAIR-BASE58>";

Initialize Generators (One-time)

cd offchain
cargo run -- init-generators

Generate and Verify a Proof

# Prove that 42 is in [0, 255]
cargo run -- prove 42 0

# Prove with a different nonce (for multiple proofs)
cargo run -- prove 100 1

# This will fail (value out of range)
cargo run -- prove 300 2

---

📁 Proof Structure

The 523-byte proof contains:

Field	Size	Description
V	33	Pedersen commitment to value
A	33	Vector commitment
S	33	Blinding vector commitment
T1	33	First polynomial commitment
T2	33	Second polynomial commitment
taux	32	Blinding factor
mu	32	Combined blinding
t_hat	32	Polynomial evaluation
a_scalar	32	Final IPA scalar
b_scalar	32	Final IPA scalar
L[0..2]	99	Left IPA commitments (3 × 33)
R[0..2]	99	Right IPA commitments (3 × 33)

---

🎯 Use Cases

Private Balance Verification

Prove your token balance is above a threshold without revealing the exact amount.

Blind Auctions

Commit to a bid, prove it's within valid range, reveal only if you win.

Gaming

Hidden stats, health points, or scores that can be verified without exposure.

Age/Credit Verification

Prove you meet a minimum requirement without revealing your exact age or credit score.

---

⚠️ Current Limitations (POC)

This is a proof of concept. Current limitations:

1. 56 transactions required - Each verification step is a separate tx
2. 8-bit range only - Values must be in [0, 255]
3. No batching - Steps could be combined to reduce tx count
4. Debug logging - Production would remove verbose logging
5. Single proof per state PDA - No aggregation yet

---

🔮 Roadmap

Future commits will focus on:

• Step Consolidation - Batch multiple steps per transaction (many steps use <50k CU)
• 16/32-bit Support - Extend range to larger values
• Proof Aggregation - Verify multiple proofs in parallel
• Gas Optimization - Remove debug logging (onchain and offchain lol)

---

🤝 Contributing

Are you a Solana/ZK company?

(Im open to submit a resume)

This project is at the intersection of:

• Zero-knowledge cryptography
• Solana program optimization
• Novel syscall exploitation techniques

If you're interested in:

• Extending to larger bit ranges
• Implementing other ZK primitives (Groth16)
• Building applications on top of this
• General cryptography on Solana

Please reach out!

• Open an issue
• Submit a PR

---

📚 References

• Bulletproofs Paper - Bünz et al.
• deanmlittle/solana-secp256k1 - Syscall jailbreak technique
• Solana secp256k1 Docs

---

📄 License

MIT

---

Built with ❤️ and a mass amount of syscall abuse