Halo2 Part I, PLONKish arithmetization

Halo2 is a Rust library that enables zk-SNARK protocol. From this article, I'd like to explain how the halo2 works and how we can efficiently apply our proof. The main source of this summary is the halo2 Book and this.

To prove a general arithmetic relation, we first want to represent the relation as a set of polynomials(or a table). To compare, I will explain how the original PLONK does arithmetization briefly.

PLONK

Given a polynomial, for example, $x_1{x}_2+x_3=x_4$, we can split this into a set of equations that contain only one addition or multiplication, which is called a gate. In the example, we may set

$$x_1{x}_2=x_5$$

$$x_5+x_3=x_4$$

Then, express these equations of the form

$$q_L{a}_L+q_R{a}_R+q_O{a}_O+q_M{a}_L{a}_R+q_C=0$$

where $q_{\ast }\in {\mathbb{F}}_p[X]$ are selector polynomials and $a_{\ast }\in {\mathbb{F}}_p[X]$ are witness polynomials. The selectors are chosen by the form of the equation. In the example, the first equation determines $q_{\ast }[1]$ and the second determines $q_{\ast }[-1]$ (here, $-1$ is a primitive 2nd root of unity). That is,

$$(q_L[1],q_R[1],q_O[1],q_M[1],q_C[1])=(1,1,0,-1,0)$$

$$(q_L[-1],q_R[-1],q_O[-1],q_M[-1],q_C[-1])=(1,1,-1,0,0)$$

Then, we can uniquely determine degree 1(the number of gates minus one) polynomials $q_{\ast }$ by Lagrange interpolation. As the prover knows the witnesses, the prover can determine $a_{\ast }$ with some permutation check technique. In the example, we should provide information that the output of the first gate $x_5$ equals the left input of the second gate. I will explain this in detail later. The point is that the PLONK requires each gate to be the exact form.

PLONKish

The PLONKish arithmetization has a more flexible structure than PLONK. We do not restrict the gate to have only one operation. To express $x_1{x}_2+x_3=x_4$, we may make a first gate to have addition and multiplication both. To visualize we make a table for a circuit, each row corresponds to a gate.

Because we don't fix any exact form, we should specify what the gates represent. For this, we introduce constraint polynomial

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

Here, each polynomial corresponds to each column, $a_1(\omega X)$ is a rotated polynomial where $\omega$ is a primitive $n$th root of unity in ${\mathbb{F}}_p$ (which exists if the number of rows $n$ divides $p-1$). The rotated polynomial represents the relatively next row. $f(X)$ is called a selector polynomial which enables turn on/off constraint for each row. In the example, we want to turn on the constraint for only the first row. 

We want to choose proper $f(X)$ and $a_i(X)$ such that the circuit is satisfied only if $\text{gate}({\omega }^k)=0$ for each $0\le k<n$. Such polynomials can be found by Lagrange interpolation. That is, we choose $f(X)$ and $a_i(X)$ which interpolates the $k$-th value for each column.

In the next post, I will explain how the proof protocol works.