Understanding PLONK
Weihong Wang

All the constraint proving systems are designed to compress many constraint checks into one. The general way to obtain such compression is by taking a random linear combination of the constraints. The more difficult constraints to be compressed are linear relations between the system variables which is Plonk dedicated to solving.

Firstly, we need to know why we need PLONK and what PLONK works for.

A. Arithmetic Circuit (Constraint System)

Notes: Given a program. convert it into a circuit.

Take another constraint system as an example:

image-20220730164703733

In this situation, $a_i$ and $b_i$ are the variables (user inputs), besides, $\omega_i$ and $w_i’$ are the weight of each wire which can be used to control the different inputs.

if we want to represent the simplest addition gate: $a_1 + b_3 = output$, we need to set:
$$
\omega_1 = 1, \omega_2 = 0, \omega_3 = 0, …, \omega_n = 0 \
\omega_1’ = 0, \omega_2’ = 0, \omega_3’= 1, …, \omega_n’ = 0 \
$$
And if we want to build another gate, we can just link the $left_input$ and the $right_input$ to these variables $a_i$, $b_i$, and use the weight of every wire as the switch.

image-20220731000612533

Under such a situation, it is easy to ensure that the first black wire and the first red wire are the same input.

Now let us consider a constraint system like this:

image-20220803211103636

Although in the circuit, we can easily find that $c_1 = a_2$, $c_2 = a_3$ because they share the same wire.

In the constraint system of PLONK, the wires connected to each gate are independent, making it possible for malicious provers to connect wires with different values to the gates which expect wires with the same value. To prevent such cases, we need to add some more constraints on the values of wires, which are called copy constraints.

B. Equations Setup (Gate Constraints)

NOTES: Convert the variables of the circuits into multiple equations.

On the gates and wires, we have two types of constraints: gate constraints (equations between wires attached to the same gate, eg. $a_1⋅b_1=c_1$) and copy constraints (claims about equality of different wires anywhere in the circuit, eg. $a_0=a_1=b_1=b_2=a_3$ or $c_0=a_1$).

From the circuit, we can generate the list of gate constraints (using the gates) and the list of copy constraints (using the wire). The copy constraints will be converted into the permutation table later (check the permutation between sets of wires). Now we are talking about the gate constraints.

Firstly, each equation is of the following form. ($L$ = Left, $R$ = Right, $O$ = output, $M$ = Multiplication, $C$ = Constant). Change the value of $Q$ to toggle on or off.
$$
Q_{L_i}a_i + Q_{R_i}b_i + Q_{O_i}c_i + Q_{C_i} + Q_{M_i}a_ib_i = 0
$$
For example,

Gate Type $Q_{L_i}$ $Q_{R_i}$ $Q_{O_i}$ $Q_{C_i}$ $Q_{M_i}$
Multiplication 0 0 -1 0 1
Addition 1 1 -1 0 0
Constant (for left value) 1 0 -1 -x 0

‼️ Extension:

Here we can do some extensions to the equations. For example, in the case: $a_1 + b_1 + a_1 * b_1 = c_1$, $Q_{L_1} = 1, Q_{R_1} = 1, Q_{C_1} = -1, Q_{M_1} = 1$.

image-20220803212657160

Through this, we can convert all these gates into multiple equations.
$$
\left{
\begin{aligned}
a_1 * b_1 &= c_1;(Q_{L_1} = 0, Q_{R_1} = 0, Q_{O_1} = -1, Q_{C_1} = 0, Q_{M_1} = 1)\
a_2 + b_2 &= c_2;(Q_{L_2} = 1, Q_{R_2} = 1, Q_{O_2} = -1, Q_{C_1} = 0, Q_{M_1} = 0)\
a_3 + b_3 &= c_3;(Q_{L_3} = 1, Q_{R_3} = 1, Q_{O_3} = -1, Q_{C_1} = 0, Q_{M_1} = 0)\
a_4 * b_4 &= c_4;(Q_{L_4} = 0, Q_{R_4} = 0, Q_{O_4} = -1, Q_{C_1} = 0, Q_{M_1} = 1)\
a_5 + c_5 &= c_5;(Q_{L_5} = 1, Q_{R_5} = 1, Q_{O_5} = -1, Q_{C_1} = 0, Q_{M_1} = 0)\
\end{aligned}
\right.
$$
And now we have a bunch of $a_i$, $b_i$ and $c_i$ values.

x Gate 1 Gate 2 Gate 3 Gate 4 Gate n
$a(x)$ $a_1$ $a_2$ $a_3$ $a_4$ $a_n$
$b(x)$ $b_1$ $b_2$ $b_3$ $b_4$ $b_n$
$c(x)$ $c_1$ $c_2$ $c_3$ $c_4$ $c_n$
image-20220731034646778

Can we use the sets of values to define the polynomials?

C. Polynomials Construction

Notes: Change the set of equations into a single polynomial equation.

Then we can compute the values of all the wires and convert them into 3 polynomials: $a(x)$, $b(x)$, $c(x)$.

Typically, there are two forms to represent a polynomial.

  • 1/ Evaluation form: degree < 4 polynomials of (-2, 1, 0, 1) at points (0, 1, 2, 3)
  • 2/ Coefficient form: $y = x^3 - 5x^2 + 7x - 2$ (in some field $F$)

As shown in the table above, the number means the No. of the gate and every gate has its according inputs and outputs. Take $a$ as the example, it is like “degree < n polynomials of ($a_1$, $a_2$, $a_3$, …, $a_n$) at points (1, 2, 3, …, n)”.

You can change the evaluation form to coefficient form through Lagrange interpolation.

From the calculation, we can get 3 polynomials: $a(x)$, $b(x)$, $c(x)$.

And for all $x \in F$, (here $F = {1, 2, 3, …, n}$ ),
$$
Q_{L}(x)a(x) + Q_R(x)b(x) + Q_O(x)c(x) + Q_M(x)a(x)b(x) + Q_C(x) = 0
$$
We are still discussing the same equations.

🌿Extensions about quotient polynomials.

$f(x) = 0, \forall x \in H$, $H = {h_1, h_2, …, h_n}$ in $F$

$f(x) = x^3 - 5x^2 + 7x - 2$

$f(x) = (h_1 - x)(h_2 - x)…t(x)$

The $t(x)$ is the quotient polynomials, and $Z_H(x) = (h_1 - x)(h_2 - x)…(h_n - x)$ is the vanishing polynomial for $H$.

$Z_H(x)*t(x) $ will equal zero for all coordinates with the particular domain $H$ that we care about, but not necessarily outside of it.

If the polynomial $f(x)$ is 0 from $x = 1$ to $n$, then it can be divisible by $Z_H(x)$.

Then we can change the equation to:
$$
Q_{L}(x)a(x) + Q_R(x)b(x) + Q_O(x)c(x) + Q_M(x)a(x)b(x) + Q_C(x) = Z_H(x)t(x)
$$
where $Z_H(x) = (x-0)(x-1)(x-2)…(x-(n-1))$ (here we start from 0 to $n-1$)

D. Permutation Argument (Copy Constraints)

Notes: How to ensure the equation relations between wires?

Here is the constraint system:
$$
\left{
\begin{aligned}
a_1 * b_1 - c_1 &= 0\
a_2 + b_2 - c_2 &= 0\
a_3 + b_3 - c_3 &= 0\
a_4 * b_4 - c_4 &= 0\
a_5 + b_5 - c_5 &= 0\
\end{aligned}
\right.
$$
Here we skipped the basic permutation in one polynomial.

In the $Plonk$ protocol, it checks a permutation “across” the values of several polynomials.

  1. Give each variable a unique index.

    image-20220731175644657

    The X coordinates would be slices of a permutation across all three sets.

    In the definition of the paper, suppose we have multiple polynomials $f_1$, …, $f_k$ $\in$ $F_{<d}[X]$ and a permutation $\sigma$: $[kn] \rightarrow [kn]$. … We also have $g_{(l)} = f_{(\sigma(l))}$

    For each $j \in [k]$, $i \in [n]$, $S_{ID_j}(x) = S_{ID}(x) + (j - 1) \cdot n$. In our problem, $k$ means the number of the polynomials (it is 3 in our problem). $n$ means the number of gates (it is 5 in our problem).

    X 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
  2. Using the copy constraints to construct the permutation table.
    $$
    \left{
    \begin{aligned}
    a_2 = c_1\
    a_3 = c_2\
    a_5 = c_4\
    b_5 = c_3\
    \end{aligned}
    \right.
    $$

    X 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    $\sigma(X)$ 1  11   12  4  14  6 7 8 9  13   2   3   10   5  15
  3. Calculate $f_j’ := f_j + \beta \cdot S_{ID_j} + \gamma$ , $g_j’ := g_j + \beta \cdot S_{\sigma_j} + \gamma$

    1 2 3 4 5
    $f_1’(X)$ $a_1 + \beta\cdot 1+\gamma$ $a_2 + \beta \cdot 2 + \gamma$ $a_3 + \beta \cdot 3 + \gamma$ $a_4 + \beta \cdot 4 + \gamma$ $a_5 + \beta \cdot 5 + \gamma$
    $f_2’(X)$ $b_1 + \beta \cdot 5 + \gamma$ $b_2 + \beta \cdot 6 + \gamma$ $b_3 + \beta \cdot 8 + \gamma$ $b_4 + \beta \cdot 9 + \gamma$ $b_5 + \beta \cdot 10 + \gamma$
    $f_3’(X)$ $c_1 + \beta \cdot 11 + \gamma$ $c_2 + \beta \cdot 12 + \gamma$ $c_3 + \beta \cdot 13 + \gamma$ $c_4 + \beta \cdot 14 + \gamma$ $c_5 + \beta \cdot 15 + \gamma$
    1 2 3 4 5
    $g_1’(X)$ $a_1 + \beta\cdot 1+\gamma$ $c_1 + \beta \cdot 11 + \gamma$ $c_2 + \beta \cdot 12 + \gamma$ $a_4 + \beta \cdot 4 + \gamma$ $c_4 + \beta \cdot 14 + \gamma$
    $g_2’(X)$ $b_1 + \beta \cdot 5 + \gamma$ $b_2 + \beta \cdot 6 + \gamma$ $b_3 + \beta \cdot 8 + \gamma$ $b_4 + \beta \cdot 9 + \gamma$ $c_3 + \beta \cdot 13 + \gamma$
    $g_3’(X)$ $a_2 + \beta \cdot 2 + \gamma$ $a_3 + \beta \cdot 3 + \gamma$ $b_5 + \beta \cdot 10 + \gamma$ $a_5 + \beta \cdot 5 + \gamma$ $c_5 + \beta \cdot 15 + \gamma$
  4. As defined in the paper:

    • Define $f’$, $g’$ $\in$ $F_{<kn}[X]$ by
      $$
      f’(X) := \prod_{j\in[k]}f_j’(X), g’(X) := \prod_{j\in[k]}g_j’(X),
      $$

    • $Z \in F_{<n}[X]$, such that $Z(g) = 1$; and for $i \in {2,…,n}$
      $$
      Z(g^i) = \prod_{1\leq j < i}f’(g^j) / g’(g^j)
      $$
      Tips: In the actual calculation, we are using the group. Need to replace the X (1, 2, 3, 4, …, n) with (1, $\omega$, $\omega^2$, $\omega^3$, …, $\omega^{n-1}$). Simultaneously, use $\omega^i$, $g * \omega^i$ , $g^2 * \omega^i$.

  5. The final check by verifier for all $a \in H$:

    • $L_1(a)(Z(a) - 1) = 0$

      $L_1(a)$ is the Lagrange basis. Definition: If $a = g^i$, $L_i(a) = 1$, otherwise, $L_i(a) = 0$. $L_i$ reduce point checks to range checks.

      Here, actually, the verifier is checking whether $Z(g) = 1$

    • $Z(a)f’(a) = g’(a)Z(a \cdot g)$

      A related convenience is that multiplicative subgroups interact well with Lagrange bases. When $a = g^n$, $a \cdot g = g^{n+1} = g$. We are back to the beginning!

      Here, if $a \neq g^n$, clearly, the equation is established according to the definition of $Z(g^i)$, $f’(X)$ and $g’(X)$. And if $a = g^n$,
      $$
      \begin{aligned}
      Z(a) = Z(g^n) = \prod_{1\leq j < n}f’(g^j)/g’(g^j) &= \frac{f’(g^1)f’(g^2)…f’(g^{n-1})}{g’(g^1)g’(g^2)…g’(g^{n-1})}\
      Z(a\cdot g) = Z(g^{n+1}) = Z(g) &= 1\
      \frac{Z(a)}{Z(a\cdot g)} \cdot \frac{f’(a)}{g’(a)} &= 1\
      \frac{f’(g^1)f’(g^2)…f’(g^{n-1})}{g’(g^1)g’(g^2)…g’(g^{n-1})} \cdot \frac{f’(g^n)}{g’(g^n)} &= 1\
      \end{aligned}
      $$
      This is to check whether the product of every value is the same after permutation.

‼️ Question:

  1. why we need the $\beta$ and the $\gamma$ ?

    Prevent the prover cheating. And the value of $\beta$ and $\gamma$ can only be revealed after the prover has finished the commitment of $a(x)$, $b(x)$, $c(x)$. And $\beta$ and $\gamma$ usually generate from the hashes of commitments to $a(x)$, $b(x)$ and $c(x)$.

E. Polynomial Commitments Scheme

Notes: There is a set of equations between the polynomials that need to be checked. Do this by making commitments to the polynomials, opening them at some random $z$.

Now we have these three types of polynomials: wire assignments $a(x)$, $b(x)$, $c(x)$, coordinate accumulators $P_a(x)$, $P_b(x)$, $P_c(x)$, $P_a’(x)$, $P_b’(x)$ , $P_c’(x)$, and the according quotients. $H_1(x)$, $H_2(x)$, … , $H_6(x)$.
$$
\textcolor{red}{f(x)} = Q_{L}(x)\textcolor{red}{a(x)} + Q_R(x)\textcolor{red}{b(x)} + Q_O(x)\textcolor{red}{c(x)} + Q_M(x)\textcolor{red}{a(x)b(x)} + Q_C(x) = Z_H(x) \textcolor{red}{t(x)}
$$
The black polynomials are known to all, and the red polynomials are only known to prover $P$. If $P$ wants to prove that he knows what the red polynomials are, he needs to give the correct equation $f(z) = Z_H(z) \cdot t(z)$ at any random $z$.

1/ Verifier directly sends the $z$

image-20220801202605260

In this situation, $V$ selects “$z$”. And $P$ needs to prove that $f(z) = Z_H(z)\cdot t(z)$. $P$ can easily cheat, for example, $f(z) = t(z) = 0$. There is no restriction that $P$ uses those $Q_i(x)$ gates.

2/ $P$ sends the values of the polynomial

image-20220801204219976

Since $V$ knows the circuit and the gate values (the black polynomials), instead of sending $f(z)$, $P$ sends $a(z)$, $b(z)$, $c(z)$, $t(z)$. And then $V$ checks:
$$
Q_{L}(z)a(z) + Q_R(z)b(z) + Q_O(z)c(z) + Q_M(z)a(z)b(z) + Q_C(z) = Z_H(z)t(z)
$$
It will be valid for all the $z$ in the field. But the prover can still cheat because $P$ knows $z$ before giving the value of $a(z)$, $b(z)$, $c(z)$, $t(z)$. $P$ can just construct corresponding values to satisfy the requirements of the equation.

3/ Force $P$ to make commitments (Kate Polynomial Commitments Scheme)

Kate PCS is a paring-based PCS. It can create very short proofs. But it requires trusted setup.

Through the structured reference string, we will generate a bunch of points that need to keep smt secret.

Let us consider the coefficient form of $f(x)$: $f(x) = f_0 + f_1 x + f_2 x^2 + … + f_n x ^n$.

$z$, $f(z)$, $\pi$

a) SETUP

  1. Select a random $s$ from the field $F$, and there is an elliptic group of order $p$ and $G$ is the generator.

  2. Generate a set of elliptic curve points: ${G, [s]G, [s^2]G, ……}$. (The $[s]$ symbol means $s$ is unknown to everyone and remains secret. )

    For reading convenience, we use ${T_0, T_1, T_2, …}$ to represent ${G, [s]G, [s^2]G^2, …}$.

    $s$ is a secret that is forgotten once the procedure is finished.

    Anyone who needs to make a polynomial commitment will need to use these points.

b) COMMIT

A commitment to a degree-d polynomial is made by multiplying each of the first d+1 points in the proving key by the corresponding coefficient in the polynomial, and adding the results together.
$$
\begin{aligned}
f(s) \cdot G &= [f_0]T_0 + [f_1]T_1 + [f_2]T_2 + … \
&= [f_0]G + [f_1][s]G + [f_2][s^2]G + …\
&= [f_0 + f_1s + f_2s^2 + …]G\
\end{aligned}
$$
$[f_0 + f_1s + f_2s^2 + …]$ is the evaluation of $f(s)$.

c) EVALUATION PROOF

Given $z$ and $com(f)$, $P$ needs to compute $f(z)$, $V$ then checks whether $f(z)$ is the honest answer.

$$
f(x) - f(z) = (x - z)t(x)
$$

$P$ sends $com(t(s))$ to $V$.
$$
\begin{aligned}
\textcolor{green}{com(f(s))} &= [f_0 + f_1s + f_2s^2 + …]\cdot G\
\textcolor{orange}{com(t(s))} &= [t_0 + t_1s+ t_2s^2 + …]\cdot G\
com(f(z)) &= f(z) \cdot G\
\
com(f(s)) - com(f(z)) &= com(f(s) - f(z))\
&= com((s - z)\cdot t(s))\
&= com(s-z) \cdot com(t(s)) \ \

\textcolor{green}{com(f(s))} - com(f(z)) &= \textcolor{pink}{com(s-z)} \cdot \textcolor{orange}{com(t(s))}
\end{aligned}
$$
$com(s-z)$ is in group $G_2$.

image-20220804101057224

image-20220801204617548

F. Optimization in $Plonk$

Notes: Integrate multiple polynomials