Halo2

Halo2 replaces the traditional trusted setup ceremony with a transparent setup mechanism. Instead of generating a common reference string through multi-party computation, Halo2 uses the inner product argument from Bulletproofs combined with a cycle of elliptic curves. This eliminates the 'toxic waste' security risk entirely—no secret parameters are ever generated that could compromise the system if leaked. The setup is universal and updatable, meaning a single set of public parameters supports any circuit up to a bounded size.

Halo2 achieves incrementally verifiable computation (IVC) through recursive proof composition. The verifier's algorithm is itself expressed as an arithmetic circuit, allowing a new proof to attest to the validity of a previous proof plus new computation. This creates a chain of proofs where:

• Each step produces a constant-size proof
• Verification time remains O(log n) regardless of total computation length
• The prover can indefinitely extend a computation while maintaining a single succinct proof

Halo2 uses a 2-cycle of elliptic curves (typically Pasta curves: Pallas and Vesta) to enable efficient recursion. The key insight is that the base field of one curve equals the scalar field of the other. This allows:

• Arithmetic operations for one curve's proof verification to be expressed natively in the other curve's circuit
• Efficient field arithmetic without expensive non-native field emulation
• Seamless alternation between proving and verification layers

The Pasta curve cycle was specifically designed for Halo2's recursive architecture, minimizing constraint overhead for recursive verification.

Halo2 employs a multivariate polynomial commitment scheme based on the inner product argument. The prover commits to polynomials representing the circuit's gate wiring and witness values, then opens them at random evaluation points. Key properties:

• Hiding and binding: commitments reveal nothing about the polynomial while preventing the prover from changing values
• Succinctness: commitment and opening proof sizes are logarithmic in the polynomial degree
• Additive homomorphism: enables efficient batching of multiple polynomial openings into a single proof

Halo2 uses a Plonkish arithmetization that generalizes the standard Plonk constraint system. Circuits are defined using:

• Custom gates: arbitrary polynomial constraints over multiple rows and columns, not limited to simple addition and multiplication
• Lookup arguments: efficiently prove that a value appears in a precomputed table, enabling optimized verification of non-arithmetic operations like SHA-256 or Keccak
• Permutation arguments: enforce copy constraints across cells without requiring separate wiring polynomials

This flexibility allows developers to express complex operations like hash functions or elliptic curve arithmetic with far fewer constraints than R1CS.

Halo2 implements the UltraPlonk variant, which extends the standard Plonk protocol with:

• Plookup integration: efficient set membership proofs for table lookups, dramatically reducing constraints for bitwise operations and range checks
• Flexible gate types: support for arithmetic, boolean, and custom polynomial gates in the same circuit
• Generalized permutation checks: handle complex wiring patterns across multiple columns and rows

The UltraPlonk arithmetization enables Halo2 circuits to be significantly more compact than equivalent R1CS or vanilla Plonk circuits, reducing prover time and memory usage.