How to Design the ZKVM Circuit by@sin7y

How to Design the ZKVM Circuit

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.
image
Sin7Y HackerNoon profile picture

Sin7Y

Sin7Y is a tech team that explores layer 2, cross-chain, ZK, and privacy computing. #WHAT IS HAPPENING IN BLOCKCHAIN#

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:


image

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:


  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∗(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)


image

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:


image
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:


image
Here, define a new selector polynomial form based on column q, and for the number k selector polynomial, we have:


image


For example, for the constraint: s_add ⋅ t_add(x) = 0, can be rewritten into:


image


The above formula can be expanded into:


image

Set

image


Then, the true value figure is obtained:


image

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:


image
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∗(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


react to story with heart
react to story with light
react to story with boat
react to story with money
Sin7Y HackerNoon profile picture
by Sin7Y @sin7y.Sin7Y is a tech team that explores layer 2, cross-chain, ZK, and privacy computing. #WHAT IS HAPPENING IN BLOCKCHAIN#
Read my stories
L O A D I N G
. . . comments & more!