SNARKs and STARKs

zk-SNARKs

Zero-Knowledge Succinct Non-Interactive Argument of Knowledge

How SNARKs Work

1. Circuit Representation: Express computation as an arithmetic circuit
2. R1CS Constraint System: Convert to Rank-1 Constraint System
3. QAP Transformation: Encode as Quadratic Arithmetic Program
4. Polynomial Commitment: Commit to polynomials representing the witness
5. Proof Generation: Create succinct proof using cryptographic primitives

Popular SNARK Constructions

Trusted Setup Ceremonies

Many SNARKs require a Multi-Party Computation (MPC) ceremony:

• Multiple participants generate randomness
• Each participant's contribution can be verified
• At least one honest participant ensures security
• "Toxic waste" must be destroyed after ceremony

zk-STARKs

Zero-Knowledge Scalable Transparent Argument of Knowledge

How STARKs Work

1. Execution Trace: Represent computation as a trace of states
2. Polynomial Interpolation: Encode trace as polynomials
3. FRI Protocol: Prove low-degree of polynomials
4. Merkle Proofs: Provide cryptographic commitments

Advantages over SNARKs

• No Trusted Setup: Uses only hash functions
• Post-Quantum Security: Based on symmetric cryptography
• Scalability: Proving time scales well with computation size
• Transparency: All parameters publicly verifiable

Trade-offs

• Larger proof sizes (~200 KB vs ~288 bytes)
• Higher verification costs
• Newer technology with less battle-testing

Comparison Table

Emerging Hybrids

New constructions combine benefits of both:

• BooSTARKs: STARKs with SNARK-like proof sizes
• Binius: Binary field arithmetic for efficiency

Next: Applications