Halo 2: Recursive Zero-Knowledge Proofs for Blockchain Scalability

Halo 2: Recursive Zero-Knowledge Proofs for Blockchain Scalability

Halo 2 is a proving system developed by Zcash that enables efficient recursive zero-knowledge proofs without a trusted setup. It builds on PLONK (PLONKish arithmetization) with several innovations: recursive proof composition (proofs verifying other proofs), no trusted setup (transparent), and support for lookup tables and custom gates. Halo 2 powers Zcash's transition to a privacy-preserving, scalable architecture and is used in various blockchain projects for proof aggregation and verifiable computation.

To understand Halo 2 properly, it helps to be familiar with PLONK, zk-SNARKs, and elliptic curve cryptography.

┌─────────────────────────────────────────────────────────────────────────┐
│                            Halo 2 Overview                               │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                          │
│   Key Innovations:                                                       │
│   ┌─────────────────────────────────────────────────────────────────┐   │
│   │ • Recursive Proof Composition (proof verifies another proof)    │   │
│   │ • No Trusted Setup (transparent, no toxic waste)               │   │
│   │ • PLONKish Arithmetization (custom gates, lookups)              │   │
│   │ • Efficient Proof Aggregation (batch many proofs into one)      │   │
│   └─────────────────────────────────────────────────────────────────┘   │
│                                                                          │
│   Recursive Proofs:                                                      │
│   ┌─────────────────────────────────────────────────────────────────┐   │
│   │  Proof A (tx1) ──┐                                             │   │
│   │  Proof B (tx2) ──┼──→ Recursive Proof R ──→ Verifier           │   │
│   │  Proof C (tx3) ──┘     (R verifies A, B, C)                    │   │
│   └─────────────────────────────────────────────────────────────────┘   │
│                                                                          │
│   Comparison with Other Systems:                                        │
│   ┌───────────────┬─────────────┬─────────────┬───────────────┐         │
│   │ Feature       │ Groth16     │ PLONK       │ Halo 2        │         │
│   ├───────────────┼─────────────┼─────────────┼───────────────┤         │
│   │ Trusted Setup │ Per-circuit │ Universal   │ None          │         │
│   │ Recursive     │ No          │ Limited     │ Yes (native)  │         │
│   │ Aggregation   │ No          │ Yes (wrap)  │ Yes (efficient)│         │
│   │ Proof Size    │ ~200 bytes │ ~400 bytes  │ ~2-4 KB       │         │
│   │ Lookup Tables │ No          │ Yes         │ Yes           │         │
│   └───────────────┴─────────────┴─────────────┴───────────────┘         │
│                                                                          │
└─────────────────────────────────────────────────────────────────────────┘

What Is Halo 2?

Halo 2 is a zero-knowledge proving system that enables efficient recursive proof composition without a trusted setup. It extends PLONK with techniques that allow a proof to verify another proof, creating chains or trees of proofs. This enables succinct blockchains where a single proof can summarize entire blockchain history, rollup compression where many transactions are aggregated into one proof, and privacy-preserving applications with nested proofs.

• Recursive Proof Composition: A Halo 2 proof can verify another Halo 2 proof, allowing proofs to be nested arbitrarily. Enables incremental verifiable computation and succinct blockchains.
• No Trusted Setup (Transparent): No toxic waste or multi-party computation ceremony required. Parameters generated from public randomness, anyone can verify setup.
• PLONKish Arithmetization: Flexible constraint system with custom gates and lookup tables. Efficient for complex applications (zkEVM, privacy, etc.).

Why Halo 2 Matters

Recursive proofs address fundamental scalability limitations of blockchain systems. Halo 2 makes recursion practical and efficient.

• Succinct Blockchains (Blockchain Compression): A single proof can verify entire blockchain history (from genesis to current state). New nodes sync by verifying one proof, not replaying all transactions. Zcash is transitioning to this model.
• Rollup Scalability (Proof Aggregation): Aggregating many transaction proofs into one reduces L1 verification cost. Rollups can scale to thousands of transactions per second with one proof.
• Incremental Verifiable Computation (IVC): Long-running computations can be proved incrementally (proof size constant). Enables verifiable database updates, private state transitions, zk-rollups with state proofs at each block.
• No Trusted Setup (Security): Eliminates risk of toxic waste compromise. No reliance on multi-party computation ceremony. Parameters publicly verifiable.
• Privacy Applications (Zcash): Shielded transactions using recursive proofs. Zcash uses Halo 2 for its next-generation protocol.

Use Case                    Without Recursion                With Halo 2
─────────────────────────────────────────────────────────────────────────────
Blockchain Syncing          Download all blocks              Verify single proof
Rollup Transactions         Many proofs on L1                Single aggregated proof
Verifiable Database         One proof per update             One proof accumulates all updates
Private Set Membership      Many proofs per item             Single nested proof
Zcash                         Shielded: per tx proof         Recursive shielded pool

How Halo 2 Works (Recursive Proofs)

Standard Proving (non-recursive):
  Prove: I know x s.t. f(x) = y.

Recursive Proving (Halo 2):
  Prove: I know a proof π that verifies (without revealing π contents).

Key insight: Verification of a proof is a computation.
  Halo 2 can prove that verification succeeded.

Nested recursion:
  Level 1: π₁ proves tx₁
  Level 2: π₂ proves that π₁ verifies
  Level 3: π₃ proves that π₂ verifies
  ...

Result: One proof of infinite chain.

Implementation:
  Verification circuit contains pairing checks (elliptic curve operations).
  Halo 2 uses cycle of elliptic curves (Pallas and Vesta) for efficient recursion.

Curve A: Pallas (scalar field = base field of Vesta)
Curve B: Vesta (scalar field = base field of Pallas)

Why cycle?
  • Proofs on curve A can verify proofs on curve B
  • Proofs on curve B can verify proofs on curve A
  • Enables arbitrary nesting depth
  • No trusted setup for either curve

Alternative (single curve):
  • Would require expensive non-native field arithmetic
  • Cycle makes recursion practical

Halo 2 vs Other Proving Systems

Property                Groth16     PLONK       STARKs      Halo 2
─────────────────────────────────────────────────────────────────────────────
Trusted Setup           Per-circuit Universal   None        None
Proof Size              ~200B       ~400B       ~100KB      ~2-4KB
Verification Time       Very fast   Fast        Moderate    Moderate
Recursive Proofs        No          Wrapper     Yes (heavy) Yes (efficient)
Aggregation Efficiency  Poor        Moderate    Good        Excellent
Post-Quantum Security   No          No          Yes         No
Proof Generation Time   Fast        Moderate    Slow        Moderate
Lookup Tables           No          Yes         Yes         Yes
Adoption                High        High        Moderate    Growing

Halo 2 Applications

Zcash (Privacy Cryptocurrency)

Zcash is transitioning from Sprout/Sapling to Halo 2. Removes trusted setup requirement (previous Zcash used trusted setup). Enables recursive proofs for shielded pool scaling. Enables Orchard protocol (new shielded addresses). Removes dependency on multi-party computation ceremony.

Proof Aggregation (Rollups)

Halo 2 can aggregate many transaction proofs into one. Reduces L1 verification cost (one verification per batch). Use cases: privacy rollups, ZK rollups, any batched ZK application.

Verifiable Database (Incremental Updates)

Prove that a sequence of database updates was applied correctly with recursive accumulation. Useful for verifiable data structures (Merkle tree proofs). Each proof verifies the previous proof and new update.

zkEVM (Ethereum Rollups)

Some zkEVM projects exploring Halo 2 for recursion; proof aggregation for multiple blocks; efficient state transition proofs.

Project                 Use of Halo 2
─────────────────────────────────────────────────────────────────────────────
Zcash (Orchard)         Shielded transactions, no trusted setup
Scroll                  zkEVM rollup (proof aggregation)
DarkFi                  Anonymous DeFi applications
Nexus                   Verifiable computation
Nomos                   Privacy-preserving rollups

Halo 2 Anti-Patterns

• Using Halo 2 for Non-Recursive Single Proofs (Overkill): Halo 2 overhead higher than PLONK for single proof. Use PLONK directly if recursion not needed. Recursion benefits only for aggregation or chain of proofs.
• Not Leveraging Lookup Tables: Custom gates not enough for complex constraints. Use lookup tables for efficient range checks and bitwise operations. Reduces constraint count drastically.
• Insufficient Understanding of Curve Cycle: Must understand underlying fields when implementing circuits. Mistaking scalar vs base field leads to incorrect constraints.
• Poor Circuit Design for Recursion: Recursive circuits must be efficient (witness generation time). Inlining verification circuit without optimization leads to large proofs. Use Halo 2's built-in recursion APIs efficiently.
• No Formal Verification for Nested Proofs: Recursive proofs increase attack surface (bugs in verification circuit). Verify each layer independently; use audit tools.

[X] Using Halo 2 for single, small circuits
[X] Not using lookup tables for range checks
[X] Ignoring curve cycle constraints (field mismatch)
[X] Inefficient recursive circuit design
[X] No testing of nested proofs

[✓] Use PLONK for single proofs (no recursion)
[✓] Use lookup tables to reduce constraints
[✓] Respect field orders (Pallas, Vesta)
[✓] Optimize recursion (accumulate state efficiently)
[✓] Test for all nesting levels

Halo 2 Best Practices

• Use Halo 2 When Recursion Required: Aggregating many proofs (rollups). Building succinct blockchains (Zcash). Incremental verifiable computation (IVC). For single proofs, use PLONK (smaller and faster).
• Leverage Lookup Tables Extensively: Use range checks (value < 2^16, 2^32). Bitwise operations (AND, XOR, NOT) via lookup tables. Fixed-base cryptography (e.g., Pedersen hashes). Reduces proof size and prover time.
• Profile Recursive Proof Size: Halo 2 proofs may be larger (2-4 KB) for deep recursion. Use recursion depth small (10-100). Use proof aggregation to flatten nesting.
• Use Established Libraries: Halo2 library by Zcash (Rust). PSE's halo2 library (maintained). halo2_proofs (core library). circom-compatible halo2 (via SnarkJS).
• Test Recursive Circuits Thoroughly: Test base case (no recursion). Test one level of recursion. Test multi-level recursion (3+ levels). Verify proofs at each level.

use halo2_proofs::plonk::*;

// Define circuit for one step
struct StepCircuit {
    pub prev_state: Value,
    pub new_state: Value,
    pub public_input: Value,
}

impl Circuit for StepCircuit {
    // Circuit definition with constraints
    // ...
}

// Recursive accumulation
let mut accumulator = None;

for (prev, new) in state_updates {
    let circuit = StepCircuit {
        prev_state: Value::known(prev),
        new_state: Value::known(new),
        public_input: ...,
    };

    let proof = prove(¶ms, circuit, accumulator);
    accumulator = Some(proof);
}

// Final proof verifies entire sequence

Requirement                         Recommended System
─────────────────────────────────────────────────────────────────────────────
Single proof, small circuit         Groth16
Single proof, large circuit          PLONK
Proof aggregation for rollup        Halo 2 (recursive)
No trusted setup              Halo 2 or STARKs (Halo 2 more efficient for recursion)
Recursive proof composition         Halo 2 (native)
Verifiable computation (long chain)  Halo 2 (IVC)
Post-quantum security               STARKs (not Halo 2)

Halo 2 Resources and Libraries

Frequently Asked Questions

1. What is the difference between Halo 2 and PLONK?
   Halo 2 is built on PLONKish arithmetization but adds recursion (proofs verifying proofs) and removes trusted setup. PLONK requires universal trusted setup (Powers of Tau). Halo 2 is transparent (no setup). Halo 2 supports efficient recursion (nested proofs).
2. Is Halo 2 quantum-safe?
   No. Halo 2 relies on elliptic curve cryptography (discrete log problem). Pallas and Vesta curves are vulnerable to Shor's algorithm. For post-quantum, consider STARKs.
3. Does Halo 2 require a trusted setup?
   No. Halo 2 is completely transparent (no trusted setup). This is a major advantage over Groth16 and PLONK. Parameters derived from public constants (no secret randomness). Anyone can verify setup correctness.
4. What is the curve cycle in Halo 2?
   Halo 2 uses two elliptic curves (Pallas and Vesta) where each curve's scalar field matches the other's base field. This enables efficient recursive proof verification (no non-native field arithmetic). Cycle of curves is essential for performance.
5. Can Halo 2 aggregate arbitrary proofs?
   Yes, Halo 2 can recursively compose proofs of the same type. For arbitrary proof types, need conversion to Halo 2 format. But aggregation is native within Halo 2 ecosystem.
6. What should I learn next after Halo 2?
   After mastering Halo 2, explore PLONK fundamentals, recursive proof composition, Zcash Orchard protocol, incremental verifiable computation (IVC), and ZK-rollups for blockchain scaling.