ZK-STARKs

PrivChain uses ZK-STARKs (Zero-Knowledge Scalable Transparent Arguments of Knowledge) as its core proving system. This choice provides post-quantum security, transparency, and scalability.

What are ZK-STARKs?

Zero-knowledge proofs allow you to prove you know something without revealing what you know. ZK-STARKs are a specific type with unique advantages:

graph LR
    subgraph Prover["Agent (Prover)"]
        Secret[Secret Knowledge]
        Compute[Computation]
    end
    
    subgraph Proof["ZK-STARK Proof"]
        P[Small Proof ~100KB]
    end
    
    subgraph Verifier["Chain (Verifier)"]
        V[Fast Verification]
        Accept[✅ Accept/Reject]
    end
    
    Secret --> Compute
    Compute --> P
    P --> V
    V --> Accept

STARKs vs SNARKs

Property	ZK-STARKs	ZK-SNARKs
Trusted Setup	❌ Not required	✅ Required
Post-Quantum	✅ Secure	❌ Vulnerable
Proof Size	~100-400 KB	~200 bytes
Proving Time	Faster	Slower
Verification	Slightly slower	Very fast
Transparency	✅ Fully transparent	❌ Requires trust

Why We Chose STARKs

1. No Trusted Setup: SNARKs require a "ceremony" where secret parameters are generated. If anyone keeps these secrets, they can forge proofs. STARKs eliminate this risk entirely.

2. Post-Quantum Security: STARKs rely on hash functions (collision resistance), not elliptic curves. They remain secure against quantum computers.

3. Transparency: All parameters are public and verifiable. No hidden assumptions.

How PrivChain Uses STARKs

Privacy Pool Proofs

When withdrawing from a privacy pool, you generate a STARK proof that:

// Conceptual proof structure
interface WithdrawalProof {
  // Public inputs (visible on-chain)
  nullifier: string;      // Prevents double-spend
  root: string;           // Merkle root of deposits
  recipient: string;      // Withdrawal address
  
  // Private inputs (never revealed)
  note: string;           // Your secret deposit note
  path: string[];         // Merkle path to your deposit
}

The proof demonstrates:

• ✅ You know a valid note
• ✅ The note corresponds to a real deposit
• ✅ You haven't spent this note before
• ❌ WITHOUT revealing which deposit is yours

Agent Identity Proofs

Prove agent attributes without revealing identity:

// Prove reputation without revealing identity
const proof = await privchain.identity.proveAttribute({
  attribute: 'reputation_score',
  predicate: 'greater_than',
  value: 100,
  // Proves: "My reputation > 100" without revealing actual score or identity
});

Proof of Agent Work

Validate computation was performed correctly:

// Prove work completion
const proof = await privchain.work.proveCompletion({
  taskHash: '0x...',
  outputHash: '0x...',
  computeSteps: 1000000,
  // Proves: "I ran this computation correctly"
});

Technical Deep Dive

Arithmetization

STARKs convert computations into polynomial equations:

Computation → Execution Trace → Polynomial Constraints → Proof

1. Execution Trace: Record all intermediate values
2. Polynomial Interpolation: Convert trace to polynomials
3. Constraint System: Define rules the computation must follow
4. FRI Protocol: Prove polynomials are low-degree (valid)

FRI (Fast Reed-Solomon IOP)

The core of STARK verification uses the FRI protocol:

graph TD
    P[Polynomial P(x)] --> C1[Commit Layer 1]
    C1 --> C2[Commit Layer 2]
    C2 --> C3[Commit Layer 3]
    C3 --> Final[Final Check]
    
    Query[Random Queries] --> C1
    Query --> C2
    Query --> C3
    
    Final --> Verify[✅ Verified]

Security Parameters

PrivChain STARK configuration:

Parameter	Value	Security
Field	Goldilocks (64-bit)	128-bit
Hash	Poseidon	STARK-friendly
Blowup Factor	8	Proof soundness
Query Count	30	~128-bit security

Performance

Typical proof generation times (on modern CPU):

Operation	Constraints	Proving Time	Proof Size
Transfer	~10K	0.5s	50 KB
Withdrawal	~100K	2s	100 KB
Identity Proof	~50K	1s	80 KB
Work Proof	~1M	15s	200 KB

GPU Acceleration

Proof generation can be accelerated 10-50x with GPU provers. The SDK automatically uses GPU when available.

Verifier Contracts

STARK verification happens on-chain via optimized Solana programs:

// Verification cost
const verificationCost = {
  computeUnits: 200_000, // ~0.00001 SOL
  time: '50ms',
  proofSize: '100 KB'
};

Further Reading

• STARK Paper - Original academic paper
• STARKs, Part I - Vitalik's explanation
• StarkWare - Leading STARK implementation

FAQ

Q: Why are STARK proofs larger than SNARK proofs?

A: STARKs trade proof size for transparency and quantum resistance. The larger proofs (~100KB vs ~200B) are still practical for on-chain verification.

Q: Can I generate proofs in a browser?

A: Yes, but it's slow. We recommend server-side proof generation or using our relayer network for browser-based agents.

Q: What happens when quantum computers arrive?

A: Nothing! STARKs are already quantum-resistant. Your historical proofs remain valid and secure.