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

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

| x | 0 | 1 | 2 | 3 |
| ---- |:--- | --- |:---:| --- |
| F(X) | 3 | 3 | 3 | 3 |

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 (2^k^rows, 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 V~3~(X), V~5~(X), V~7~(X), when {X = 0…2^k^-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 V~3~(1) = V~5~(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:


Since different polynomials correspond to different column indexes, different evaluation domains can be distinguished by introducing column index (in Plonk, it is distinguished by introducing domain n, that is, if there are k polynomials, the domain of perm_index_poly is kn), and its mapping relationship can be expressed as:

$$
S(\text { col:i, row:j })=\sigma^{i^{\prime}} w^{j^{\prime}}
$$

Taking the polynomial V~7~(X) with column index = 7 as an example, the true value of the corresponding permutation index polynomial S~7~(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:

$$\prod_{j=0}^{n-1} \frac{\left(v_{3}\left(w^{j}\right)+\beta \cdot \delta^{3} \cdot \omega^{j}+\gamma\right)\left(v_{5}\left(w^{j}\right)+\beta \cdot \delta^{5} \cdot \omega^{j}+\gamma\right)\left(v_{7}\left(w^{j}\right)+\beta \cdot \delta^{7} \cdot \omega^{j}+\gamma\right)}{\left(v_{3}\left(w^{j}\right)+\beta \cdot S\left(3, \omega^{j}\right)+\gamma\right)\left(v_{5}\left(w^{j}\right)+\beta \cdot S\left(5, \omega^{j}\right)+\gamma\right)\left(v_{i}\left(w^{j}\right)+\beta \cdot S\left(7, \omega^{j}\right)+\gamma\right)}=1$$

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

$$\prod_{i=0}^{m-1} \prod_{j=0}^{n-1}\left(\frac{v_{i}\left(w^{j}\right)+\beta \cdot \delta^{i} \cdot \omega^{j}+\gamma}{v_{i}\left(w^{j}\right)+\beta \cdot S_{i}\left(\omega^{j}\right)+\gamma}\right)=1$$

where the permutation index polynomial is defined as：$S_{\text {col:i }}\left(w^{\text {row:j }}\right)=\sigma^{i^{\prime}} w^{j^{\prime}}$

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:

$$
\begin{aligned}
Z\left(W^{j+1}\right) &=\prod_{h=0}^{j} \prod_{i=0}^{m-1}\left(\frac{v_{i}\left(w^{h}\right)+\beta \cdot \delta^{i} \cdot \omega^{h}+\gamma}{v_{i}\left(w^{h}\right)+\beta \cdot S_{i}\left(\omega^{h}\right)+\gamma}\right) \\
&=Z\left(W^{j}\right) \prod_{i=0}^{m-1}\left(\frac{v_{i}\left(w^{j}\right)+\beta \cdot \delta^{i} \cdot \omega^{j}+\gamma}{v_{i}\left(w^{j}\right)+\beta \cdot S_{i}\left(\omega^{j}\right)+\gamma}\right)
\end{aligned}
$$

The corresponding constraint is:

$$
\begin{gathered}
Z_{p}(w X) \prod_{i=0}^{m-1}\left(v_{i}(x)+\beta \cdot S_{i}(X)+\gamma\right)-Z_{p}(X) \prod_{i=0}^{m-1}\left(v_{i}(X)+\beta \cdot \delta^{i} \cdot X+\gamma\right)=0 \\
l_{0} \cdot\left(1-Z_{p}(X)\right)=0
\end{gathered}
$$

### 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 2^k^, the number of valid rows is u, and the number of invalid rows is t, then u + t +1 = 2^k^ 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. q~last~, 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:

$$
\begin{gathered}
\left(1-\left(q_{\text {last }}(X)+q_{\text {blind }}(X)\right)\right) \cdot\left(Z_{p}(w X) \prod_{i=0}^{m-1}\left(v_{i}(x)+\beta \cdot S_{i}(X)+\gamma\right)\right. \\
-Z_{p}(X) \prod_{i=0}^{m-1}\left(v_{i}(X)+\beta \cdot \delta^{i} \cdot X+\gamma\right)=0
\end{gathered}
$$

The constraint on line 0 remains unchanged:

$$
\left(1-Z_{p}(X)\right)\cdot I_{0}(X)=0
$$

Constraint on line u:

$$
\left(Z_{p}(X)^{2}-Z_{p}(X)\right) \cdot q_{\text {last }}(X)=0
$$

According to the formula of polynomial Z~p~(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.

\begin{gathered}
\left(1-\left(q_{\text {last }}(X)+q_{\text {blind }}(X)\right)\right) \cdot\left(Z_{p}(w X) \prod_{i=0}^{m-1}\left(v_{i}(x)+\beta \cdot S_{i}(X)+\gamma\right)\right. \\
-Z_{p}(X) \prod_{i=0}^{m-1}\left(v_{i}(X)+\beta \cdot \delta^{i} \cdot X+\gamma\right)=0
\end{gathered}

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 V~3~(X) and V~5~(X). At this time, it is marked as Z~p,0~(X) and Z~p,0~(w^0^) = 1. When the cumulative multiplication reaches the last point, that is, j = u (u is a valid rows number), mark it as Z~p,0~(w^u^); then the cumulative multiplication of the second chunk is initated, and it is marked as Z~p,1~(X), satisfying Z~p,1~(w^0^) = Z~p,0~(w^u^). Until the last point, Z~p,1~(w^u^) = 1 must be satisfied.

In summary, the constraint becomes:

\begin{gathered}
\left(1-\left(q_{\text {last }}(X)+q_{\text {blind }}(X)\right)\right) \cdot\left(Z_{p, a}(w X) \prod_{i=a m}^{(a+1) m-1}\left(v_{i}(x)+\beta \cdot S_{i}(X)+\gamma\right)\right. \\
-Z_{p, a}(X) \prod_{i=a m}^{(a+1) m-1}\left(v_{i}(X)+\beta \cdot \delta^{i} \cdot X+\gamma\right)=0
\end{gathered}

Among them，0 ≤ a < b; b = ceil(m / b)

The first line of constraint remains unchanged:

$$
\left(1-Z_{p, 0}(X)\right) \cdot l_{0}(X)=0
$$

The following requirement must be met among multiple chunks:

$$
\left(Z_{p, a}(X)-Z_{p, a-1}\left(w^{u} X\right)\right) \cdot l_{0}(X)=0
$$

The last line needs to meet:

$$
\left(Z_{p, b-1}(X)^{2}-Z_{p, b-1}(X)\right) \cdot q_{\text {last }}(X)=0
$$