Proving system

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.

Example

To aid our explanations, we will at times refer to the following example constraint system:

Four advice columns $a, b, c, d$ .
One fixed column $f$ .
Three custom gates:
- $a \cdot b \cdot c_{- 1} - d = 0$
- $f_{- 1} \cdot c = 0$
- $f \cdot d \cdot a = 0$

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.

Prover		Verifier
	$\leftarrow$	$t (X) = (X^{n} - 1)$
	$\leftarrow$	$F = [F_{0}, F_{1}, \dots, F_{m - 1}]$
$A = [A_{0}, A_{1}, \dots, A_{m - 1}]$	$\to$
	$\leftarrow$	$θ$
$L = [(A_{0}^{'}, S_{0}^{'}), \dots, (A_{m - 1}^{'}, S_{m - 1}^{'})]$	$\to$
	$\leftarrow$	$β, γ$
$Z_{P} = [Z_{P, 0}, Z_{P, 1}, \dots]$	$\to$
$Z_{L} = [Z_{L, 0}, Z_{L, 1}, \dots]$	$\to$
	$\leftarrow$	$y$
$h (X) = \frac{gate _{0} ( X ) + \dots + y ^{i} \cdot gate _{i} ( X )}{t ( X )}$
$h (X) = h_{0} (X) + \dots + X^{n (d - 1)} h_{d - 1} (X)$
$H = [H_{0}, H_{1}, \dots, H_{d - 1}]$	$\to$
	$\leftarrow$	$x$
$e v a l s = [A_{0} (x), \dots, H_{d - 1} (x)]$	$\to$
		Checks $h (x)$
	$\leftarrow$	$x_{1}, x_{2}$
Constructs $h^{'} (X)$ multipoint opening poly
$U = Commit (h^{'} (X))$	$\to$
	$\leftarrow$	$x_{3}$
$q_{evals} = [Q_{0} (x_{3}), Q_{1} (x_{3}), \dots]$	$\to$
$u_{eval} = U (x_{3})$	$\to$
	$\leftarrow$	$x_{4}$

Then the prover and verifier:

Construct $finalPoly (X)$ as a linear combination of $Q$ and $U$ using powers of $x_{4}$ ;
Construct $finalPolyEval$ as the equivalent linear combination of $q_{evals}$ and $u_{eval}$ ; and
Perform $InnerProduct (finalPoly (X), x_{3}, finalPolyEval) .$

TODO: Write up protocol components that provide zero-knowledge.

The halo2 Book

Proving system

Example

tl;dr