technology ： How to design zkVM circuit

Custom doors

In the design zkvm When the circuit is , Due to the need to identify many custom doors , So a lot of binary selectors have been introduced （binary selector）.

With ( site ) Division gate （（field）division gate） For example , We plan to design a door to verify q, x, y Between the three elements q = x/y The relationship is established .

For convenience , We do not perform field division operations at the circuit level , Instead, it is implemented by verifying the following logical relationships .

X * inv_y = q
inv_y∗y = 1 / / Make sure y≠0

Between these two elements , There is an equal relationship . therefore , We have the following Trace surface :

Yes w_0,w_1,w_2,w_3 Column definition polynomial w_0(x), w_1(x), w_2(x), w_3(x), Then the row corresponding to the division operation should meet ：

w_0(x) . w_3(x) - w_2(x) = 0 w_1(x) . w_3(x) - 1 = 0

To ensure that the above relationship can be satisfied in the corresponding row , You need a selector to partition it to constrain validation .

therefore , We introduced a new column s_{div} = {0,0,…1,…0}$. When it is converted to a polynomial s_{div}(x) when , The above formula 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

Combination selector （Combined Selector）

From the example above , We can see that when we define a new custom door , You need to introduce a selector column s* To correspond to this door .

If we use t * (x) Represents the constraint polynomial corresponding to the gate , We can finally get the following 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

…

Because the prover needs to promise all polynomials in the process of generating the proof , Introduce too many selector polynomial It will increase the workload of certifiers and verifiers .

therefore , You need to optimize the number of selectors , At the same time, the following two conditions must be met ：

• selector polynomial There is no loss , That is, only certain doors can be used ;
• Less selector polynomial

stay “Plonky2： Fast recursive parameters and PLONK and FRI”(https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf) in , There is an optimization method “Binary-Tree Based Selector”, It will selector polynomial To reduce the number of log(k), k Is the number of custom doors .

stay Halo2 Papers ,zcash The team proposed a new optimization method , A smaller number of polynomials can be realized ( And constrained polynomials t∗(x) And are constrained polynomials max_degree The set parameters are related to ).

To make it easier to understand , Let's take a simple example ( For a particular algorithm , see also Selector combination - The halo2 Book)

We can see , We are 4 A custom door setting 4 Selector Columns , As mentioned earlier , That's not what we want .

This will increase the workload of the verifier and the verifier . Here we define a new column q, Satisfy :

If we are a selector s_{add}, s_{div}, s_{cube}, s_{sqrt} Define a set {s_{add}, s_{div}, s_{cube}, s_{sqrt}( It is called disjoint , Even if there is no common point between possible lines ), So according to the column q The definition of , We have ：

ad locum , Column based q Define a new selector polynomial form , For numbers kselector polynomial, We have

:

for example , For constraints ：s_add⋅t_add(x) = 0, I could rewrite it as :

Expand the above formula to :

Then we get the truth diagram :

You can see , 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 constraint as ：

For the above constraints , We just need to do the polynomial q(x) Make a commitment . But here's the thing , This approach also increases the degree of constraints .

up to now , We have achieved two things ：

• selector polynomial There is no loss , That is, only certain doors can be used ;
• Less selector polynomial

Of course , The degree of constraint in the protocol is limited , Therefore, the number of selectors participating in the combination is bounded , That is, the number of single combinatorial selectors depends on the constraint polynomial t Of Degree and max_degree The boundary value of *(x).

therefore , Need more combined Columns , Anyway, the quantity is still much less than the original .

Source：https://hackernoon.com/how-to-design-the-zkvm-circuit

About

ChinaDeFi - ChinaDeFi.com It's a research driven DeFi Innovation organizations , We are also a blockchain development team . From all over the world every day 500 Close to a good source of information 900 In the content , Looking for deeper thinking 、 Sort out more systematic content , Provide decision-making assistant materials to the Chinese market at the fastest speed .

Layer 2 friends sharing same hobby - Welcome to Layer 2 Interested blockchain technology enthusiasts 、 Study and analyze people and Gavin（ WeChat : chinadefi） contact , Discuss together Layer 2 Landing opportunities . Please pay attention to our official account of WeChat “ Decentralized financial community ”.