The Halo 2 proving system can be broken down into five stages:
- Commit to polynomials encoding the main components of the circuit:
- Cell assignments.
- Permuted values and products for each lookup argument.
- Equality constraint permutations.
- Construct the vanishing argument to constrain all circuit relations to zero:
- Standard and custom gates.
- Lookup argument rules.
- Equality constraint permutation rules.
- Evaluate the above polynomials at all necessary points:
- All relative rotations used by custom gates across all columns.
- Vanishing argument pieces.
- Construct the multipoint opening argument to check that all evaluations are consistent with their respective commitments.
- Run the inner product argument to create a polynomial commitment opening proof for the multipoint opening argument polynomial.
These stages are presented in turn across this section of the book.
To aid our explanations, we will at times refer to the following example constraint system:
- Four advice columns .
- One fixed column .
- Three custom gates:
The table below provides a (probably too) succinct description of the Halo 2 protocol. This description will likely be replaced by the Halo 2 paper and security proof, but for now serves as a summary of the following sub-sections.
|Constructs multipoint opening poly|
Then the prover and verifier:
- Construct as a linear combination of and using powers of ;
- Construct as the equivalent linear combination of and ; and
TODO: Write up protocol components that provide zero-knowledge.