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 for columns then the rows corresponding to the division operation shall satisfy： w_0(x), w_1(x), w_2(x), w_3(x) w_0,w_1,w_2,w_3 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”( ), 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. https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf 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”, , accessed: 2022-02-06 https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf

Trace

Understanding the Sinsemilla Hash Function in OlaVM

What is a TinyRAM Instruction Set?

Nominated for 2022 - HackerNoon Contributor of the Year - Optimization

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Architecture

Nominated for 2022 - HackerNoon Contributor of the Year - Blockchain

Too Long; Didn't Read

How to Design the ZKVM Circuit

How to Design the ZKVM Circuit

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

A Study on Parallel Execution: Everything You Need to Know

06/09/2018: Biggest Stories in the Cryptosphere

07/09/2018: Biggest Stories in the Cryptosphere

0x Protocol, Waves, and EtherDelta: Solutions and Limitations of Distrust

03/09/2018: Biggest Stories in the Cryptosphere

A Study on Parallel Execution: Everything You Need to Know

06/09/2018: Biggest Stories in the Cryptosphere

07/09/2018: Biggest Stories in the Cryptosphere

0x Protocol, Waves, and EtherDelta: Solutions and Limitations of Distrust

03/09/2018: Biggest Stories in the Cryptosphere

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps