Zero-Knowledge Proofs

Module 2 of Advanced Protocols

What Are Zero-Knowledge Proofs?

A zero-knowledge proof (ZKP) lets you prove you know something without revealing what you know.

The Classic Example: Ali Baba's Cave

     ┌─────────────────┐
     │                 │
     │    A ←───┐      │
     │         │      │
     │    ┌────┴────┐ │
Entrance │         │ │
────────►│  Magic  │ │
     │   │  Door   │ │
     │   │         │ │
     │   └────┬────┘ │
     │        │      │
     │    B ──┘      │
     │               │
     └───────────────┘

Peggy (Prover) knows the magic word.
Victor (Verifier) wants proof.

1. Victor waits at entrance
2. Peggy enters, chooses path A or B (Victor doesn't see)
3. Victor shouts "come out path A!" or "come out path B!"
4. Peggy comes out the requested path
5. Repeat 20 times

If Peggy doesn't know the word, she has 50% chance each time.
20 successes = 99.9999% confidence she knows.
Victor learns NOTHING about the word itself.

Properties of Zero-Knowledge Proofs

1. Completeness

If the statement is true and both parties are honest, the verifier will be convinced.

2. Soundness

If the statement is false, no cheating prover can convince an honest verifier (except with negligible probability).

3. Zero-Knowledge

The verifier learns nothing beyond the validity of the statement. They couldn't distinguish a real proof from a simulation.

Why ZKPs Matter for Blockchain

Scalability (ZK Rollups)

Prove 10,000 transactions are valid with one small proof:

Without ZK: Verify each of 10,000 txs = 10,000 operations
With ZK:    Verify one proof = 1 operation

Result: Orders of magnitude more throughput

Privacy

Prove transaction validity without revealing:

• Who sent it
• Who received it
• How much was sent

Compliance

Prove you're on a whitelist without revealing identity:

Traditional: "I'm John Smith, here's my ID"
With ZK: "I can prove I'm on the approved list" (reveals nothing else)

ZK Proof Systems Comparison

ZK-SNARKs

Succinct Non-interactive ARgument of Knowledge

Properties

• Succinct: Small proof size, fast verification
• Non-interactive: Single message from prover to verifier
• ARgument: Computationally sound (not information-theoretic)
• Knowledge: Prover must "know" the witness

How They Work (Simplified)

1. Computation → Arithmetic Circuit
   "I know x where hash(x) = y"
   ↓
   Converted to mathematical constraints

2. Circuit → R1CS (Rank-1 Constraint System)
   ↓
   System of equations

3. R1CS → QAP (Quadratic Arithmetic Program)
   ↓
   Polynomial representation

4. QAP → Proof
   ↓
   Cryptographic proof using elliptic curves

The Trusted Setup Problem

Groth16 SNARKs require a "toxic waste" ceremony:

Generate parameters:
τ (tau) = random secret

Public parameters derived from τ
τ must be DESTROYED

If anyone knows τ, they can create fake proofs!

Solution: Multi-Party Computation (MPC)

• Many participants contribute randomness
• Only ONE needs to be honest
• Zcash ceremony had 87 participants

ZK-STARKs

Scalable Transparent ARgument of Knowledge

Key Differences from SNARKs

How STARKs Work (Simplified)

1. Algebraic Intermediate Representation (AIR)
   ↓
   Computation as polynomial constraints

2. FRI Protocol (Fast Reed-Solomon IOP)
   ↓
   Commit to polynomial using Merkle trees

3. Verification
   ↓
   Check random points satisfy constraints

Advantages

• No trusted setup (transparent)
• Quantum-resistant (uses hash functions only)
• Scales better for large computations

Disadvantages

• Larger proof sizes
• More complex implementation

PLONK and Universal Setup

Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge

The Universal Setup Advantage

Groth16: New ceremony for each circuit
         Circuit A → Setup A
         Circuit B → Setup B

PLONK:   One ceremony for all circuits
         Universal Setup → Works for A, B, C, ...

Popular Variants

• TurboPLONK: Optimized lookup tables
• UltraPLONK: Custom gates for efficiency
• Halo 2: Recursive proofs without trusted setup

Recursive Proofs

Proofs that verify other proofs:

Proof₁ (valid txs 1-100)
Proof₂ (valid txs 101-200)
Proof₃ (valid txs 201-300)
        ↓
Recursive Proof: "Proof₁, Proof₂, Proof₃ are all valid"
        ↓
Final Proof: One proof covers all 300 txs

Applications

• Mina Protocol: Entire blockchain in 22KB
• Incrementally Verifiable Computation: Prove long computations
• Proof Aggregation: Combine many proofs into one

ZK in Practice: Use Cases

1. ZK Rollups

// Simplified ZK rollup verifier
contract Rollup {
    function submitBatch(
        bytes32 newStateRoot,
        bytes calldata proof
    ) external {
        require(
            verifier.verify(
                [oldStateRoot, newStateRoot, txHash],
                proof
            ),
            "Invalid proof"
        );
        stateRoot = newStateRoot;
    }
}

2. Private Transactions (Zcash, Tornado Cash)

Prove:
- "I have a valid unspent note in the commitment tree"
- "I know the secret key for this note"
- "The nullifier prevents double-spending"

Without revealing:
- Which note is being spent
- Who is sending/receiving
- The amount

3. Identity/Credentials

Traditional: "Here's my passport showing I'm over 18"
ZK: "I can prove I'm over 18 without revealing my age or identity"

Applications:
- KYC without data exposure
- Voting eligibility
- Professional credentials

4. Gaming

• Prove you made a valid move (chess, card games)
• Hidden information games (fog of war)
• Provably fair randomness

Building ZK Applications

Tooling Landscape

Simple Example: Hash Preimage

// Circom circuit: prove you know preimage of hash
pragma circom 2.0.0;

include "circomlib/circuits/poseidon.circom";

template HashPreimage() {
    signal input preimage;  // Private input (witness)
    signal input hash;      // Public input

    component hasher = Poseidon(1);
    hasher.inputs[0] <== preimage;

    // Constraint: hash(preimage) must equal claimed hash
    hash === hasher.out;
}

component main {public [hash]} = HashPreimage();

Workflow

1. Write circuit (define constraints)
2. Compile to R1CS/arithmetic circuit
3. Generate proving/verification keys
4. Create proof (with private witness)
5. Verify proof (with public inputs)

Performance Considerations

Prover Time

Creating proofs is expensive:

Small circuit (1K constraints): ~1 second
Medium circuit (100K constraints): ~30 seconds
Large circuit (10M constraints): ~10 minutes

Hardware acceleration helps:
- GPU proving: 10-100x faster
- ASICs: Even faster (in development)

Circuit Optimization

Fewer constraints = faster proving

Expensive operations:
- Division (many constraints)
- Comparisons
- Non-native field arithmetic

Cheap operations:
- Addition
- Multiplication by constant
- Hash functions (if designed for ZK)

Future Developments

Folding Schemes (Nova, SuperNova)

Incrementally build proofs without full recursion overhead:

• Proof for step 1
• "Fold" step 2 into proof
• Continue folding...
• Final verification is cheap

Client-Side Proving

Run provers in browsers/phones:

• WASM-based provers
• Lightweight proof systems
• Privacy without infrastructure

ZK Coprocessors

Offload ZK computation:

• Prove heavy computation happened correctly
• Verify cheaply on-chain
• Examples: Axiom, RISC Zero

Key Takeaways

1. ZKPs prove knowledge without revealing it - revolutionary for privacy and scaling
2. SNARKs: Small proofs, fast verification, need trusted setup
3. STARKs: No trusted setup, quantum resistant, larger proofs
4. PLONK: Universal setup, flexible, widely used
5. ZK Rollups use ZKPs for L2 scaling
6. Privacy applications: Transactions, identity, compliance
7. Prover efficiency is the main bottleneck - improving rapidly
8. The future: Recursive proofs, client-side proving, ZK everywhere