Halo2 Part II, Proving system

In the previous part, we described how to make a polynomial that someone wants to prove into a table, using PLONKish arithmetization. After that, we will explain how the zk-SNARK protocol works. One needs a lookup table or permutation argument, but I will postpone it.

Circuit commitment

Suppose the prover makes a table with advice(private), instance(public), and fixed(constant, selector) columns. As explained in Part I, let $a_i$ be $(n-1)$-degree polynomials which interpolate every advice and instance column, and $f_i$ interpolates fixed columns. Then, the prover commits every polynomial using a proper polynomial commitment scheme such as IPA or KZG. I will explain more about this. For now, let's just regard general PCS.

After commitment, the verifier makes a random challenge $y\in \mathbb{F}p$. Suppose the prover has a satisfied circuit so that ${\text{gate}}_j({\omega }^k)=0$ for each row $k$ and gate $j$. In the previous example, we had only one gate, but one can make several gate constraints. Since ${\text{gate}}_j({\omega }^k)=0$ for all $0\le k<n$, ${\text{gate}}_j(X)$ is divided by $X^n-1$. Let

$$h(x)=\frac{{\text{gate}}_0(X)+y\cdot {\text{gate}}_1(X)+\cdots +y^{d-1}\cdot {\text{gate}}_{d-1}(X)}{X^n-1}$$

be a quotient polynomial. Since we committed $a_i$ and $f_i$ which are of degree $n-1$, the prover needs to split $h(X)$ into $d-1$ many polynomials of degree at most $n-1$. Note that $\mathrm{deg}h(X)=d(n-1)-n=(d-1)(n-1)-1$. Then, the prover commits each $h_i$ such that

$$h(X)=h_0(X)+X^n{h}_1(X)+\cdots +X^{n(d-2)}{h}_{d-2}(X).$$

Vanishing argument

Next, the verifier wants to check the prover has proper polynomials $a_i(X),f_i(X),h_i(X)$. For this, the verifier makes a random challenge $x\in {\mathbb{F}}_p$. Then, the prover sends evaluations of all polynomials and rotated polynomials used in ${\text{gate}}_j(X)$. For example, if

$${\text{gate}}_0(X)=f(X)(a_1(X)a_2(X)+a_3(X)-a_1(\omega X))$$

then the prover need to send $f(x),a_i(x),a_1(\omega x),h_i(x)$. When receiving all the evaluations, the verifier checks the equation

$${\text{gate}}_0(x)+y{\text{gate}}_1(x)+\cdots +y^{d-1}{\text{gate}}_{d-1}(x)=(x^n-1)(h_0(x)+x^n{h}_1(x)+\cdots +x^{n(d-2)}{h}_{d-2}(x))$$

and whether the evaluations work well with previous commitments. To do this for several evaluations efficiently, halo2 uses the multipoint opening argument. I will talk about this after explaining how the polynomial commitment works.

To commit and open the polynomials, the original halo2 from ZCash uses the inner product argument. This is a modified version of [BCCGC16] I posted here. After that, PSE uses the KZG commitment scheme instead. I will explain two different versions of halo2 in the next series of posts.