Halo 2 Guide
Abstract
This volume of The Zcash Arboretum develops the proof system that Orchard uses: Halo 2, the argument by which the author of a shielded Action convinces every validator that the Action is well formed while disclosing nothing about the note, the key, or the Merkle path behind it. It assumes the Math Guide, whose finite fields, polynomials and evaluation domains, elliptic curves, and probability are used throughout without re-derivation, and the Crypto Guide, whose definitions it instantiates rather than restates: arguments of knowledge and zero knowledge, the Fiat–Shamir transform, Pedersen vector commitments, and the polynomial-commitment interface with its compilation recipe.
The running example is knowledge of x with
Contents
- 1 Introduction
-
2 Arithmetisation: from a computation to committed polynomials
- 2.1 From computation to a grid of constraints
- 2.2 From the grid to polynomials
- 2.3 From vanishing to a single identity
- 2.4 Why checking one random point is a proof
- 2.5 PLONKish arithmetisation
- 2.6 Enforcing the wiring: the permutation argument
- 2.7 Proving a value sits in a table: lookups
- 2.8 The lookup argument
- 2.9 Why the prover cannot wriggle: binding commitments
-
3 The inner-product polynomial commitment
- 3.1 The problem: an inner product in fewer than d group elements
- 3.2 One fold, every step written out
- 3.3 The recursion: k rounds to a single scalar
- 3.4 The verifier’s work: structured scalars and the final generator
- 3.5 Why it is binding: extraction from three transcripts
- 3.6 Zero knowledge: what the blinders hide and what they do not
- 3.7 A complete toy opening, carried by script
- 3.8 Halo 2’s specifics: parameters, generators from a hash, the deferred multi-scalar multiplication, and the proof bytes
-
4 The Halo 2 proof system
- 4.1 From statement to circuit: arithmetisation in practice
- 4.2 Instance columns and binding the public statement
- 4.3 Removing the verifier: the Fiat–Shamir transform
- 4.4 The multipoint opening argument
- 4.5 The complete Halo 2 protocol
- 4.6 Zero knowledge: hiding the witness in Halo 2
- 4.7 Halo 2 as a compiled polynomial IOP
- 5 A rigorous treatment of knowledge soundness
- 6 The verifier’s decision and its implication chain
- 7 Recursive proof composition and accumulation schemes