# **Permutation Argument**

### **Input**:
$f, g\in\mathbb{F}_{<d}[X]$.

### **Goal**:
Prove that $g$ is a permutation of $f$, denoted $g = \sigma(f)$. This equation is defined as $g(\omega^i) = f(\omega^{\sigma(i)})$ for all $i\in[n]$.

:::info
**Copy Constraints:**
The goal is to prove $a_i = a_{\sigma(i)}$ for all $i$. This is a specific case of the general permutation argument where $g = f$ and $f(\omega^i) = a_i$. Thus, it reduces to prove $f(\omega^i) = f(\omega^{\sigma(i)})$.
:::

### **Permutation Check with Grand Product**

The permutation condition $g = \sigma(f)$ is satisfied if and only if the following equation holds:

$$
\prod_i \frac{f'(\omega^i)}{g'(\omega^i)} = 1
$$

Where:

$$
f'(\omega^i) = f(\omega^i) + \beta \cdot S_{ID}(\omega^i) + \gamma
$$

$$
g'(\omega^i) = g(\omega^i) + \beta \cdot S_{\sigma}(\omega^i) + \gamma
$$

Here:

- $S_{ID}(\omega^i) = i$: Represents the identity mapping.
- $S_{\sigma}(\omega^i) = \sigma(i)$: Represents the permutation mapping.

## Accumulator

A **permutation polynomial** $P$ is used to accumulate the grand product:

- Initialization: $P(\omega^0) = 1$.
- $P(\omega^{i+1}) = \prod_{j<i+1} \frac{f'(\omega^j)}{g'(\omega^j)}(=P(\omega^{i})\frac{f'(\omega^i)}{g'(\omega^i)})$.

The existence of $P$ implies the grand product condition is satisfied:

$$
\prod_i \frac{f'(\omega^i)}{g'(\omega^i)} = 1
$$

Because $\prod_i \frac{f'(\omega^i)}{g'(\omega^i)}=P(\omega^{n})=P(1)=P(\omega^{0}) =1$

It is again equivalent to prove the following polynomial equation
$P(\omega x) \cdot g'(x) - P(x) \cdot f'(x)=Z(x)H(x),$
where $Z(x)=\prod_{i=0}^{n-1}(x-\omega^i)=x^n-1$ is called the vanishing/zero polynomial and $H(x)$ the quotient polynomial.
:::info
If the left hand side polynomial is perfectly divisible by $Z(x)$, then with high probability the permutation relation is satisfied.
:::

### **Protocol**

1. Verifier chooses random parameters: $\beta$ and $\gamma$.

2. Prover computes $f',g'$ and the permutation polynomial $P$ using interpolation on domain $\{\omega^0,\omega^1,...,\omega^{n-1}\}$.
3. We use a PCS to prove $$(P(\omega x) \cdot g'(x) - P(x) \cdot f'(x))-Z(x)H(x) =0.$$
Since $P$ is queried at both points $x$ and $\omega x$. During the evaluation, construct the [multipoint opening argument](https://zcash.github.io/halo2/design/proving-system/multipoint-opening.html) to check that all evaluations are consistent with their corresponding commitments.

## References
- [Plonk paper](https://eprint.iacr.org/2019/953)
- [How PLONK Works: Part 2. Copy Constraints](https://scryptplatform.medium.com/how-plonk-works-part-2-1072dcd7634a)
- [The halo2 Book. Permutation argument](https://zcash.github.io/halo2/design/proving-system/permutation.html)