Sin7Y is a tech team that explores layer 2, cross-chain, ZK, and privacy computing. #WHAT IS HAPPENING IN BLOCKCHAIN#
The algorithm mentioned in the Halo2 book is a little bit obscure. Here we will use a simple example to briefly express its main idea. First, let’s look at a definition:
Define: cycle (a, b, c) => represents the cyclic mapping relationship between elements, namely: map[a] = b, map[b] = c, map[c] = a, which can be extended to an arbitrary-sized cycle.
Now, consider a polynomial f(x), whose partial points are as shown in the following table:
Note1: For ease of understanding, ignore the zero knowledge features for now;
Note2: In Halo2, all the information of the circuit is represented by a table, the size of which depends on the size of the circuit.
Similar to a lookup argument, we will discuss the equality property between the elements of multiple columns of data on the table (2krows, index starts from 0), that is, copy constraint. As shown in the figure below, there are three sets of data, which occupy the three columns of the table (the data format of the cell is shown in the upper right corner of the figure):
As shown in the figure: there are three columns of data, corresponding to the values of three polynomials V3(X), V5(X), V7(X), when {X = 0…2k-1}. It can be found that we have performed copy constraint on the values between different polynomials (copy constraint, shown by the purple and blue lines in the figure). Next, we will use the permutation argument to prove the corresponding X to the values that we set to be equivalent, is valid.
Next, we will use the permutation argument to prove the corresponding X of the values that we set to be equivalent, is valid.
Step1: Label and define permutation index polynomial S
Unlike the lookup argument, the permutation argument clearly specifies the specific position of the equal value, as V3(1) = V5(0) shown in the figure, etc.; therefore, a new polynomial needs to be defined to represent the index correspondence relationship among different polynomials, as shown in the figure below:
S( col:i, row:j )=σ^i′.w^j′
Taking the polynomial V7(X) with column index = 7 as an example, the true value of the corresponding permutation index polynomial S7(col:i, row:j) is shown on the right side of the figure.
Step2: Generate the proof
Based on the set of permutation index polynomials S = {Si} generated by Step1, we need to ensure that the following equation holds:
Note: If the indexes of the three polynomials are reordered (regardless of the original order, starting from 0, the polynomial indexes are 0, 1, 2 in order), then the above equation can be simply expressed as:
where the permutation index polynomial is defined as: S_col:i (w^row:j )=σ^i′.w^j′
The principle is shown in the figure below:
Due to the introduction of random numbers β and γ, when and only if the copy constraints are really met, the two cells connected by the purple line and the blue line in the figure can be guaranteed to be equal with a probability close to 1 (according to the Schwartz-Zippel theorem). So the final result of multiplying the numerators and that of denominators are also equal.
Define the polynomial Z to satisfy Z(W^0) = Z(W^n) = 1, for 0 <j <n, then:
The corresponding constraint is:
Similar to the lookup argument, we need to introduce some random numbers to achieve zero knowledge. If the total number of rows is 2k, the number of valid rows is u, and the number of invalid rows is t, then u + t +1 = 2k must be satisfied.
Two new selectors have been added:
q_blind, the last t line, the value is 1, and the others are 0
qlast, the value of row u is 1, and others are 0 (between usable rows and blind rows)
Then the above constraint needs to be modified to:
The constraint on line 0 remains unchanged:
(1−Zp(X))⋅I0(X)=0
Constraint on line u:
(Zp(X)^2−Zp(X))⋅q_last (X)=0
According to the formula of polynomial Zp(X), Z(u) = 1 (the set of numerator and denominator values are the same). It is worth noting that this constraint constrains Z(u) within the range of {0,1}, but the probability of being 0 is very small.
Note: code in halo2\src\plonk\permutation\prover.rs: fn construct()
According to the formula, it can be found that when the number of polynomials (m) participating in the permutation argument is large, the degree of constraining polynomials will exceed the degree bound defined by SRS.
Therefore, it is necessary to perform division with the cumulative multiplication process above, shown in the figure below:
As shown in Figure 5, take the segmentation granularity as 2 as an example, and m=3 is assumed. We first perform a cumulative multiplication operation on the polynomials V3(X) and V5(X). At this time, it is marked as Zp,0(X) and Zp,0(w0) = 1. When the cumulative multiplication reaches the last point, that is, j = u (u is a valid rows number), mark it as Zp,0(wu); then the cumulative multiplication of the second chunk is initated, and it is marked as Zp,1(X), satisfying Zp,1(w0) = Zp,0(wu). Until the last point, Zp,1(wu) = 1 must be satisfied.
In summary, the constraint becomes:
Among them，0 ≤ a < b; b = ceil(m / b)
The first line of constraint remains unchanged:
(1−Z_p,0(X))⋅l_0(X)=0
The following requirement must be met among multiple chunks:
(Z_p,a(X)−Z_p,a−1.(w^u.X))⋅l_0(X)=0
The last line needs to meet:
(Z_p,b−1(X)^2−Z_p,b−1(X))⋅q_last (X)=0