Permutation Argument in Halo 2: Sin7Y Tech Review (15)

Bullet Points

1. Halo2 uses permutation argument technology to allow copy constraint on any number of columns;
2. It is basically similar to the permutation argument in Plonk, but the form of expression is different;
3. For the main branch of the corresponding Halo2 code, commit is: a7cd600eb60b1528159b92af5e426adcc615de1a
4. Halo2 book:
   https://zcash.github.io/halo2/design/proving-system/permutation.html

Technique Description

Permutation cycle

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:

If we don’t have any copy constraint now, we can treat the four X values as an independent permutation cycle, namely (0)(1)(2)(3); now, we have added the first copy constraint, f (0) = (f2). Obviously, cycle (1) and cycle (3) are not affected, and cycle (0) and cycle (2) will be combined into a big cycle. The combination algorithm can refer to the details of the Algorithm in the Halo2 book. The following figure is used to briefly illustrate the change process of the permutation cycle after adding multiple copy constraints:

Without zero knowledge

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.

Permutation Argument Protocol

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:

Introduce zero knowledge

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:

1. q_blind, the last t line, the value is 1, and the others are 0

2. 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.

Spanning a large number of columns

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