Sin7Y Tech Review (27): Combined Selector

Customized gate

When designing the zkvm circuit, because of many custom gates determined, there are a lot of binary selectors are introduced. Taking the (field) division gate as an example, we plan to design a gate to verify that the relationship

$q=x/y$ works among three elements

$q,x,y$. For convenience, we will not perform the field division operation at the circuit level, instead, we will make it by verifying the following logical relationship:

$$\begin{gathered} x\ast in{v}_y=q \\ in{v}_y\ast y=1//ensurey\ne 0 \end{gathered}$$
Between the two elements, there is an equal relationship. Therefore, we have the following Trace table:

Step	$$s_{\ast }$$	…	$$s_{div}$$	…	$$w_0$$	$$w_1$$	$$w_2$$	$$w_3$$
…	…	…	…	…
k	0	0	1	0	x	y	q	$$in{v}_y$$	//division
…	…	…	…	…

Define the polynomial

$w_0(x),w_1(x),w_2(x),w_3(x)$ for columns

$w_0,w_1,w_2,w_3$, then the rows corresponding to the division operation shall satisfy：

$$\begin{gathered} w_0(x)\cdot w_3(x)-w_2(x)=0 \\ {w}_1(x)\cdot w_3(x)-1=0 \end{gathered}$$
To ensure that the relationship above can be satisfied in the corresponding row, a selector is needed to make the corresponding division to constrain the verification. Therefore, we have introduced a new column

$s_{div}=\{0,0,...1,...0\}$$. When it is transformed to the polynomial

$s_{div}(x)$, the above equation will be:

$$\begin{gathered} s_{div}(x)\cdot (w_0(x)\cdot w_3(x)-w_2(x))=0 \\ {s}_{div}(x)\cdot (w_1(x)\cdot w_3(x)-1)=0 \end{gathered}$$

Combined selector

From the example above, we can see that when we define a new customized gate, a selector column

$s_{\ast }$ needs to be introduced to correspond to the gate. If we represent the corresponding constraint polynomial of the gate with

$t_{\ast }(x)$, we can obtain the following constraints finally:

$$\begin{gathered} s_{add}(x)\cdot t_{add}(x)=0 \\ {s}_{div}(x)\cdot t_{add}(x)=0 \\ {s}_{cube}(x)\cdot t_{cube}(x)=0 \\ {s}_{sqrt}(x)\cdot t_{sqrt}(x)=0 \\ ... \end{gathered}$$
For the prover needs to conduct commitments to all polynomials during the proof generation, overmuch selector polynomials introduced will increase the workload of the prover and the verifier. Therefore, it is necessary to optimize the selector number while the following two conditions must be satisfied:

1. There is no loss for the meaning of selector polynomial, that is, only specific gates can be used;
2. Less selector polynomial

In "Plonky2: Fast Recursive Arguments with PLONK and FRI"(https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf), there is an optimization method "Binary-Tree Based Selector", which reduces the number of the select polynomial to

$log(k)$, and

$k$ is the number of the customized gate. In the Halo2 paper, the zcash team has put forward a new optimization method, which may realize a smaller number of the polynomial (in correlation with the constraint polynomial

$t_{\ast }(x)$ and the parameters set for the constraint polynomial max_degree).

To understand it easier, let's take a simple example (for specific algorithm, please refer to Selector combining - The halo2 Book)

Step	$$s_{add}$$	$$s_{div}$$	$$s_{cube}$$	$$s_{sqrt}$$	$$w_0$$	$$w_1$$	$$w_2$$	$$w_3$$
0	1	0	0	0	$$a_0$$	$$b_0$$	$$c_0$$	$$d_0$$	//add
1	0	1	0	0	$$a_1$$	$$b_1$$	$$c_1$$	$$d_1$$	//division
2	0	0	1	0	$$a_2$$	$$b_2$$	$$c_2$$	$$d_2$$	//cube
3	0	0	0	1	$$a_3$$	$$b_3$$	$$c_3$$	$$d_3$$	//sqrt

We can see that we have set 4 selector columns for 4 kinds of customized gates, which are not what we want just like the aforementioned. Therefore, this will increase the workload of the prover and the verifier. Here we define a new column

$q$, satisfying:

$$q=\{\begin{array}{ll}k& \text{if }theselectorlabelledkis1\\ 0& \text{if }alltheselectorsis0\end{array}$$

If we define a set

$\{s_{add},s_{div},s_{cube},s_{sqrt}\}$ (called as disjoint, that is to make there is no common point between possible rows) for selectors

$s_{add},s_{div},s_{cube},s_{sqrt}$, then based on the definition of column

$q$, we have:

Step	$$s_{add}$$	$$s_{div}$$	$$s_{cube}$$	$$s_{sqrt}$$	$$q$$	$$w_0$$	$$w_1$$	$$w_2$$	$$w_3$$
0	1	0	0	0	1	$$a_0$$	$$b_0$$	$$c_0$$	$$d_0$$	//add
1	0	1	0	0	2	$$a_1$$	$$b_1$$	$$c_1$$	$$d_1$$	//division
2	0	0	1	0	3	$$a_2$$	$$b_2$$	$$c_2$$	$$d_2$$	//cube
3	0	0	0	1	4	$$a_3$$	$$b_3$$	$$c_3$$	$$d_3$$	//sqrt

Here, define a new selector polynomial form based on column

$q$, and for the number

$k$ selector polynomial, we have:

$$q(x)\prod _{1\le h\le len(selectors),h\ne k}(h-q(x))$$

For example, for the constraint:

$s_{add}\cdot t_{add}(x)=0$, can be rewritten into:

$$q(x)\prod _{1\le h\le len(selectors),h\ne 1}(h-q(x))\cdot t_{add}(x)=0$$

The above formula can be expanded into:

$$q(x)\cdot (2-q(x))\cdot (3-q(x))\cdot (4-q(x))\cdot t_{add}(x)=0$$
Set

$$combine{d}_q(x)=q(x)\cdot (2-q(x))\cdot (3-q(x))\cdot (4-q(x))$$

Then, the true value figure is obtained:

x	$$combine{d}_q(x)$$	$$s_{add}(x)$$
0	1	1
1	0	0
2	0	0
3	0	0

It can be seen that it does the same thing as the original selector. Therefore, for constraints

$$\begin{gathered} s_{add}(x)\cdot t_{add}(x)=0 \\ {s}_{div}(x)\cdot t_{add}(x)=0 \\ {s}_{cube}(x)\cdot t_{cube}(x)=0 \\ {s}_{sqrt}(x)\cdot t_{sqrt}(x)=0 \\ ... \end{gathered}$$
We can rewrite the constrains into:

$$\begin{gathered} q(x)\prod _{1\le h\le len(selectors),h\ne 1}(h-q(x))\cdot t_{add}(x)=0 \\ q(x)\prod _{1\le h\le len(selectors),h\ne 2}(h-q(x))\cdot t_{add}(x)=0 \\ q(x)\prod _{1\le h\le len(selectors),h\ne 3}(h-q(x))(x)\cdot t_{cube}(x)=0 \\ q(x)\prod _{1\le h\le len(selectors),h\ne 4}(h-q(x))\cdot t_{sqrt}(x)=0 \\ ... \end{gathered}$$

For the constraints above, we only need to conduct commitment to the polynomial

$q(x)$. But it is worth noting that, this method has also increased the degree of the constraint.

So far, we have achieved the two points mentioned above:

1. There is no loss for the meaning of selector polynomial, that is, only specific gates can be used;
2. Less selector polynomial

Of course, there are limitations to the constrained Degree in the protocol, so the selector number participating in the combine is bounded, that is, the number of the single combined selector depends on the boundary value of the Degree and max_degree of the constraint polynomial

$t_{\ast }(x)$. Therefore, more combined columns are needed, and anyway, the number is still much smaller than the original one.

For more handling cases and algorithm details, please refer to Selector combining - The halo2 Book.

References

1. "The halo2 Book", https://zcash.github.io/halo2/design/implementation/selector-combining.html
2. Polygon Zero Team, "Plonky2: Fast Recursive Arguments with PLONK and FRI", https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf, accessed: 2022-02-06