# (deprecated) Plonk Notes

This module explains how (turbo) PLONK SNARK work.

### PLONK Constraint System
The standard constraint system for $m$ variables and $n$ constraints is specified by selector vectors $\mathbf{q_L}, \mathbf{q_R}, \mathbf{q_O}, \mathbf{q_M}$, and input indices vectors $\mathbf{a},\mathbf{b},\mathbf{c},$ such that
an input $x\in \mathbb{F}^{m}$ satisfies the constraint system if:
$$
\forall i\in [n]\colon x_{a[i]} * q_L[i] + x_{b[i]} * q_R[i] + x_{a[i]} * x_{b[i]} * q_M[i] = x_{c[i]} * q_O[i]
$$

Note that for equation above
+ $m$ variables include all public inputs/outputs, witness and intermediate variables within a circuit
+ allows to specify arithmetic circuits gates by setting $q_M[i] = 1$ for $\bigoplus$ gates and $q_L[i] = q_R[i] = 1$ for $\bigotimes$ gates.
+ that input indices vectors are mapping gate/constraint index to variable/wire index, thus the wiring permutation ($\pi\colon \mathbb{F}^{3n} \rightarrow \mathbb{F}^{3n}$) can be derived from $\mathbf{a},\mathbf{b},\mathbf{c}$
+ can be more general, as other combination can be added. Moreover, additional selector polynomials can be added with little cost to support more complex gates (Turbo PLONK).

### Constraint System $\rightarrow$ PolyIOP
To convert PLONK constraint system to a polynomial IOP, we need to:

1. express gate constraint
+ by encoding selector vectors as polynomials of degree $n$ over field $\mathbb{F}$
+ expanding the input witness to 3 vectors of length $n$, representing left, right, and output values of each gate, then encoding as polynomials $f_1(X)$, $f_2(X)$ and $f_3(X)$ of degree $n$.
2. express wiring constraint
+ by encoding the permutation $\pi\colon \mathbb{F}^{3n} \rightarrow \mathbb{F}^{3n}$ that correctly maps each value with the wiring of the circuit (for example, the output of $i$-th gate must be the left input $j$-th gate) to polynomial relations

All polynomials are interpolated at points ${g^i}$ where $g$ is a generator of group $H$ of order $n$ ($\langle g \rangle = H$).

Then, the "gate constraint" is satisfiable if for $\forall i \in \lbrace 0..n-1\rbrace$:
$f_1(g^i) * q_L(g^i) + f_2(g^i) * q_R(g^i) + f_1(g^i) * f_2(g^i) * q_M(g^i) - f_3(g^i) * q_O(g^i) = 0$

Let $k_1$, $k_2$ and $k_3$ such that $k_iH$ are distinct cosets of $H$.
That is, $\forall x \in k_iH, x \notin k_jH\quad (i \neq j \land i,j \in \lbrace 1,2,3\rbrace)$.

Let $\pi$ be a permutation over $[3n]\colon \mathbb{F}^{3n} \rightarrow \mathbb{F}^{3n}$,
define polynomials $\pi_1, \pi_2, \pi_3$ such that:
$\pi_j(g^s) = k_lg^t, \quad\text{if } \pi[(j-1)*n + s] = (l-1)*n + t$.
That is, $s$-th element in group $j$, is mapped to $t$-th element in group $l$, for $j, l \in \lbrace 1,2,3 \rbrace$, and $s,t \in \lbrace 0..n-1 \rbrace$.
Meaning, for example if $j$ = 1 and $l$ = 2, the left input of the $s$-th gate is the same wire as the right input of $t$-th gate.

To arithmetize the permutation constraints, we interpolate polynomial $\Sigma$ s.t.
$\Sigma(g^0) = 1$, and for $\gamma, \delta \in_R \mathbb{F}$, $i \in [n]$:

$$
\Sigma(g^{i+1}) = \Sigma(g^i) * \prod_{j=1}^3\frac{f_j(g^i) + \gamma * k_j g^i + \delta}{f_j(g^i) + \gamma * \pi_j(g^i) + \delta}
$$

Then $\Sigma(g^n)\neq 1$ with overwhelming probability, if $f_1, f_2, f_3$ do not satisfy the permutation,

To check the permutation polynomial $\Sigma$, the verifier ensures the following relations are correct:

$$
\begin{cases}
\Sigma(1) = 1 & ,i=0 \\
\Sigma(g^{i+1})* \prod_{j=1}^3(f_j(g^i) + \gamma * \pi_j(g^i) + \delta) - \Sigma(g^i)* \prod_{j=1}^3(f_j(g^i) +\gamma * k_j*g^i + \delta) = 0 & ,i\in [n]
\end{cases}
$$

Or equivalently, that $\forall X \in H$:
$$
\begin{cases}
(\Sigma(X) -1) * \frac{X^n -1}{X-1} = 0 \\
\Sigma(g*X)* \prod_{j=1}^3(f_j(X) + \gamma * \pi_j(X) + \delta) - \Sigma(X)* \prod_{j=1}^3(f_j(X) + \gamma * k_j*X + \delta) = 0
\end{cases}
$$

Combining the gate constraints and wiring constraints together, the verifier checks the following equation for $\forall X \in H, \alpha \in_R \mathbb{F}$:

$$
\begin{align}
P(X) & = f_1(X) * q_L(X) + f_2(X) * q_R(X) + f_2(X) * f_3(X) * q_M(X) - f_2(X) * q_O(X) \\
& + \alpha * \lbrace\Sigma(g*X)* \prod_{j=1}^3(f_j(X) + \gamma * \pi_j(X) + \delta) - \Sigma(X)* \prod_{j=1}^3(f_j(X) + \gamma * k_j*X + \delta) \rbrace \\
& + \alpha^2*\lbrace(\Sigma(X) -1) * \frac{X^n -1}{X-1}\rbrace \\
& = 0
\end{align}
$$

To check this equation, the prover computes the quotient polynomial $Q(X) =\frac{P(X)}{(X^n - 1)}$
and convinces the verifier that for $\forall X \in H$, $P(X) - Q(X)*(X^n-1) = 0$.
For this purpose, a random challenge $\beta$ is sampled uniformly random in the field,
and the verifier checks that $P(\beta) - \frac{Q(\beta)}{(\beta^n -1)} = 0$.

### PolyIOP + PolyComm $\rightarrow$ SNARK

Compiling the PolyIOP argument system with a polynomial commitment schemes(PCS) (e.g. [KZG10], [BFS19]) and Fiat-Shamir Transform, we can get a SNARK.
More importantly, the preprocessing of the argument system doesn't involve circuit-specific Structured Reference String (SRS), but only possibly some PCS-specific SRS, thus making a universal SNARK possible.
Some PCS (e.g. [BFS19], [Lee20]) takes one step further, avoiding a private/trusted setup and SRS altogether by having a public transparent setup, thus resulting in a SNARK without trusted setup.

### PLONK SNARK Protocol
**Preprocessing:**
Verifier and prover deterministically samples a group $H$ of order $n$, and derive its distinct cosets: $k_1H,k_2H,k_3H,$ as the evaluation domain for the quotient polynoimal $Q(X)$ during online phase.

Compute polynomials $q_L, q_R, q_M, q_O, \pi_1, \pi_2, \pi_3$, the verifier stores commitments to these polynomials.

**Online:**
1. Prover uses extended witness to interpolate polynomials $f_1,f_2,f_3$, commit to them, and append the commitments to the proof.
2. The random challenges $\gamma$ and $\delta$ are sampled.
3. Prover interpolate polynomial $\Sigma$. Commit to it, and append the commitment to the proof.
4. The random challenge $\alpha$ is sampled.
5. Prover computes polynomials $P(X)$ and $Q(X)$. It splits $Q(X)$ into 3 degree-$n$ polynomials $Q_0, Q_1, Q_2$, commits, and append the commitment to the proof.
6. The random challenge $\beta$ is sampled.
7. Prover computes linearization polynomial $L(X)$:
$$
\begin{align}
L(X) & = f_1(\beta) * q_L(X) + f_2(\beta) * q_R(X) + f_1(\beta) * f_2(\beta) * q_M(X) - f_3(\beta) * q_O(X) \\
& + \alpha * \lbrace\Sigma(X)* \prod_{j=1}^3(f_j(\beta) + \gamma * k_j*\beta + \delta)\rbrace \\
& - \alpha * \lbrace\Sigma(g*\beta)* \prod_{j=2}^3(f_j(\beta) + \gamma * \pi_j(\beta) + \delta)\rbrace *\gamma*\pi_3(X) \\
& + \alpha^2 * \lbrace(\Sigma(X)-1) * \frac{\beta^n - 1}{\beta - 1} \rbrace\\
\end{align}
$$

8. Prover appends $f_1(\beta), f_2(\beta), f_3(\beta), \pi_1(\beta), \pi_2(\beta), L(\beta), \Sigma(\beta*g)$ to the proof, together with a batch proof of the correctness of these values, including a proof for $Q(\beta) = Q_0(\beta) + \beta^{n} * Q_1(\beta) + \beta^{2n} * Q_2(\beta)$.
9. Verifier computes element
$$
\begin{align}
Q(\beta) &= \frac{P(\beta)}{(\beta^n -1)} \\
& = \frac{L(\beta) - \alpha * (\Sigma(g*\beta)* \prod_{j=2}^3(f_j(\beta) + \gamma * \pi_j(\beta) + \delta)*f_3(\beta + \delta) -
\frac{\beta^n - 1}{\beta - 1}}{\beta^n -1}
\end{align}
$$

10. Verifier homomorphically derives commitment to $L(X)$
11. Verifier batch verify the eval proofs for $f_1(\beta), f_2(\beta), f_3(\beta), \pi_1(\beta), \pi_2(\beta), L(\beta), \Sigma(\beta*g),
Q(\beta) = Q_0(\beta) + \beta^{n} * Q_1(\beta) + \beta^{2n} * Q_2(\beta)$.

**Adding Zero-Knowledge:**
- each $f_i$ polynomial is randomized by adding a blinding polynomial of degree 1 that vanishes on $H$: $f_i(X) \rightarrow (b_{i,1} + X * b_{i,2}) * (X^n - 1) + f_i(X)$
- Since $\Sigma(X)$ is opened in two points, we blind it with a degree 2 polynomial $\Sigma(X) \rightarrow (b_1 + X * b_2 + X^2 * b_3) * (X^n - 1) + \Sigma(X)$
Since, random polynomial vanishes on H, it does not affect correctness nor soundness of the protocol.

## Contributors
Fernando Krell, Binyi Chen, Philippe Camacho, Alex Xiong