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 \leq 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 $\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) \left( a_1(X) a_2(X) + a_3(X) - a_1(\omega X) \right)$$
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.
댓글
댓글 쓰기