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:
x * inv_y = q
inv_y∗y=1 //ensure y≠0
Between the two elements, there is an equal relationship. Therefore, we have the following Trace table:
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：
w_0(x) . w_3(x) - w_2(x) = 0 w_1(x) . w_3(x) - 1 = 0
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:
s_{div}(x) ⋅ (w_0(x) ⋅ w_3(x) - w_2(x)) = 0
s_{div}(x) ⋅ (w_1(x) ⋅ w_3(x) - 1) = 0
Combined Selector
From the example above, we can see that when we define a new customized gate, a selector column s* needs to be introduced to correspond to the gate.
If we represent the corresponding constraint polynomial of the gate with t∗(x), we can obtain the following constraints finally:
s_{add}(x) ⋅ t_{add}(x) = 0
s_{div}(x) ⋅ t_{add}(x) = 0
s_{cube}(x) ⋅ t_{cube}(x) = 0
s_{sqrt}(x) ⋅ t_{sqrt}(x) = 0
...
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:
-
There is no loss for the meaning of selector polynomial, that is, only specific gates can be used;
-
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∗(x) and the parameters set for the constraint polynomial max_degree).
To understand it easier, let’s take a simple example (for a specific algorithm, please refer to Selector combining - The halo2 Book)
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:
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:
Here, define a new selector polynomial form based on column q, and for the number k selector polynomial, we have:
For example, for the constraint: s_add ⋅ t_add(x) = 0, can be rewritten into:
The above formula can be expanded into:
Set
Then, the true value figure is obtained:
It can be seen that it does the same thing as the original selector. Therefore, for constraints:
s_{add}(x) ⋅ t_{add}(x) = 0
s_{div}(x) ⋅ t_{add}(x) = 0
s_{cube}(x) ⋅ t_{cube}(x) = 0
s_{sqrt}(x) ⋅ t_{sqrt}(x) = 0
...
We can rewrite the constraints into:
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:
-
There is no loss for the meaning of selector polynomial, that is, only specific gates can be used;
-
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∗(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
-
“The halo2 Book”,
https://zcash.github.io/halo2/design/implementation/selector-combining.html
-
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