PLONK stands for Permutations over Lagrange-bases for Oecumenical Non Interactive Arguments of Knowledge. From hereon we shall simply write plonk.
Plonk is a general-purpose zero-knowledge proof scheme which solves a huge issue inherited in traditional zksnarks proof systems like Groth16: the non-universal one-time trusted setup. The trusted setup is a preprocessing phase which creates a Structured Reference String (SRS) that is available to both prover and verifier. The reason why an SRS is created is to prevent the prover from cheating and creating fake proofs and thus fulfilling the soundness property. The problem with a non-universal one-time trusted setup is that it’s a one-time event which means every circuit needs a new SRS to be generated, which results in slow verification time. Plonk solves this problem by creating a single SRS that’s used for an unlimited number of arbitrary circuits (of a certain maximum size). This string is also updatable, which improves security.
Plonk can be constructed as follow:
Program (code)→ Arithmetic circuit → Constraint systems → Permutation checks → Polynomial commitments (A batched version of KZG10)
We will use the following example to be able to explain each step and the transition from one to the other. For a more detailed explanation, please check the original PLONK paper as it contains formal definitions and some interesting insights regarding efficiency etc.
Problem definition:
Prover wants to prove to Verifier that she knows the solution to the equation:
The goal is for Prover to evaluate the above function without revealing anything about the secret value
Prover creates a program to represent the problem in a function code, which then will be translated into an arithmetic circuit.
This step transforms a program into an arithmetic circuit where two basic components are being used: wires and gates. Plonk uses fan-in two gates; therefore each gate has a left input, a right input, and an output. A circuit with
Plonk is gate-based instead of R1CS-based like some proof systems, such as Groth16. A primary difference between the two systems is in how they handle addition gates; in R1CS, addition gates are cheap since wires that go from an addition to a multiplication gate are not labeled, which is not the case for a gate-based system. The reason why plonk uses a gate-based system rather than an R1CS system is that the linear constraints (which are just wiring constraints) can be reduced to a permutation check. To better understand the advantages and disadvantages of each of those designs check this article.
The following circuit translates the previous equation
The circuit is converted into a system of equations where the variables are the values on each of the wires, and there is one equation per gate. Let’s take our previous example:
$$\begin{equation*} \begin{dcases} \begin{align} a_1b_1-c_1 &=0 & \ a_2b_2-c_2 &=0 &\ a_3+b_3-c_3&=0 &\ a_4+b_4-c_4&=0 \end{align} \end{dcases} \end{equation*}$$
The final result is
for
Each
For an addition gate, we set:
For a constant gate setting
There are two types of constraints:
-
Gate constraints: Which represent the equations between the wires attached to the same gate. For example the equation
$(1)$ :$$a_1*b_1-c_1=0 $$ . -
Copy constraints: Plonk enforces copy constraints; these associate wires from the whole circuit that have the same value, for example the output of one gate would be associated with the input of its destination gate. These constraints are checked with a permutation argument. For example,
$c_1$ is the output of equation$(1)$ and is also an input for another gate, so we copy that constraint into a new one$a_2$ and we claim equality$c_1=a_2$ .
We introduce a permutation argument used to assure the correct execution of the circuit. It allows to check the connection between different wires inside of the circuit and make sure that the output of a certain circuit is equal to the input of another for example
Let
for each
The prover will be able to select an appropriate
Note that if this equality holds, we can substitute
and therefore the check effectively assures that
$$
(\phi_1, \dots, \phi_k) = \sigma^i((\phi_1, \dots, \phi_3))
$$
for all
PLONK uses a batched kate commitment form in order to improve verifier efficiency by allowing for a parallel opening of commitments for each evaluation point possible.
Let’s take
d-polynomial commitment scheme is a setting of
The commitment scheme has three steps, as follow:
-
$gen(d)$ : this step will generate a structured reference string$(srs)$ in a randomized way. The algorithm randomly chooses$x\in F$ and outputs
-
$com(,srs)$ : the commitment is computed as follows,$$com(,srs):=[\phi(x)]_1$$ -
$open:$ we present two scenarios:-
All evaluation points are equal
$z_1=z_2=........=z_t=z$ $$open({cm_i},{z_i},{s_i})$$ for$i \in [t]$ a. Verifier sends a random
$\gamma\in F$ b. Prover computes
$$h(x)=\sum_{i=1}^{t}\gamma^{i-1}.\dfrac{\phi_i(x)-\phi_i(z)}{x-z}$$ and then uses$srs$ to compute the commitment$W$ and send it to verifier$$W=h[(x)]_1$$
c. Verifier computes the following:
$$F=\sum_{i\in[t]}\gamma^{i-1}.cm_i ;and; v=[\sum_{i\in[t]}\gamma^{i-1}.s_i]_1$$ and accepts iff$$e(F-v,[1]_2).e(-W,[x-z]_2)=1$$ -
- Let
$z,z'$ be two distinct evaluation points and$t_1,t_2$ be the number of polynomials We will describe the protocol when there are two distinct points among$z_1,\dots, z_t$ . Let$z, z'$ be the distinct evaluation points and$t_1,t_2$ then number of polynomials ${f_i}{i\in [t_1]}, {f_i'}{i\in [t_2]}$ evaluated in$z, z'$ respectively.
Note that these protocols are not zero-knowledge. The notion of zero-knowledge is not even well defined for polynomial commitments. At the end, when we present the full protocol we will add blinders to add the zero-knowledge property to the Plonk protocol.
- $open( {cm_i}{i \in [t_1]},{cm_i'}{i \in [t_2]}, z, z', {s_i}{i \in [t_1]} {s_i'}{i \in [t_2]})$
- Verifier sends random challenges
$\gamma, \gamma' \in \mathbb{F}$ - Prover computes polynomials
$$
h(X) := \sum_{i=1}^{t_1} \gamma^{i-1} \frac{f_i(X) - f_i(z)}{X-z}\
h'(X):= \sum_{i=1}^{t_2} \gamma'^{i-1} \frac{f'_i(X) - f'_i(z')}{X-z'}
$$
and sends commitments
$W=[h(x)]_1, W'=[h'(x)]_1$ . - Verifier chooses random
$r' \in \mathbb{F}$ and computes $$ F:= \left( \sum_{i=1}^{t_1} \gamma^{i-1} \cdot cm_i - \left[ \sum_{i=1}^{t_1} \gamma^{i-1} s_i \right]1\right) +\ r' \cdot \left( \sum{i=1}^{t_2} \gamma'^{i-1} \cdot cm'i - \left[ \sum{i=1}^{t_2} \gamma'^{i-1} s'_i \right]_1\right) $$ - Verifier accepts iff $$ e(F +z \cdot W + r'z'\cdot W', [1]_2) = e(W + r'\cdot W', [x]_2) $$
- Verifier sends random challenges
Extending the left side of the check we get $$ e(F +z \cdot W + r'z'\cdot W', [1]2) =\ e( \left( \sum{i=1}^{t_1} \gamma^{i-1} \cdot cm_i - \left[ \sum_{i=1}^{t_1} \gamma^{i-1} s_i \right]1\right) + r' \cdot \left( \sum{i=1}^{t_2} \gamma'^{i-1} \cdot cm'i - \left[ \sum{i=1}^{t_2} \gamma'^{i-1} s'_i \right]1\right)\ + z \cdot \sum{i=1}^{t_1} \gamma^{i-1} \frac{[f_i(x) - f_i(z)]1}{x-z} +\ r'z' \cdot \sum{i=1}^{t_2} \gamma'^{i-1} \frac{[f'_i(x) - f'_i(z')]_1}{x-z'}, [1]2) =\ e( \left( \sum{i=1}^{t_1} \gamma^{i-1} \cdot [f_i(x)]1 - \left[ \sum{i=1}^{t_1} \gamma^{i-1} f_i(z) \right]1\right) + r' \cdot \left( \sum{i=1}^{t_2} \gamma'^{i-1} \cdot [f'_i(x)]1 - \left[ \sum{i=1}^{t_2} \gamma'^{i-1} f'_i(z) \right]1\right)\ + z \cdot \sum{i=1}^{t_1} \gamma^{i-1} \frac{[f_i(x) - f_i(z)]1}{x-z} +\ r'z' \cdot \sum{i=1}^{t_2} \gamma'^{i-1} \frac{[f'_i(x) - f'_i(z')]_1}{x-z'}, [1]2) =\ e( \left( \sum{i=1}^{t_1} \gamma^{i-1} \cdot [f_i(x) - f_i(z)]1 \right) + r' \cdot \left( \sum{i=1}^{t_2} \gamma'^{i-1} \cdot [f'_i(x) - f'_i(z)]1 \right)\ + z \cdot \sum{i=1}^{t_1} \gamma^{i-1} \frac{[f_i(x) - f_i(z)]1}{x-z} +\ r'z' \cdot \sum{i=1}^{t_2} \gamma'^{i-1} \frac{[f'_i(x) - f'_i(z')]_1}{x-z'}, [1]2) =\ e( \left( \sum{i=1}^{t_1} \gamma^{i-1} \cdot [f_i(x) - f_i(z)]1 \right) (1 + \frac{z}{x-z}) +\ r' \cdot \left( \sum{i=1}^{t_2} \gamma'^{i-1} \cdot [f'_i(x) - f'_i(z)]_1 \right) (1 + \frac{z'}{x-z'}), [1]2) =\ e( \left( \sum{i=1}^{t_1} \gamma^{i-1} \cdot [f_i(x) - f_i(z)]1 \right) (\frac{x}{x-z}) +\ r' \cdot \left( \sum{i=1}^{t_2} \gamma'^{i-1} \cdot [f'_i(x) - f'_i(z)]_1 \right) (\frac{x}{x-z'}), [1]_2) $$
From the right side we get $$ e(W + r' \cdot W', [x]2) =\ e( \sum{i=1}^{t_1} \gamma^{i-1} \frac{[f_i(x) - f_i(z)]1}{x-z}\ + r' \cdot \sum{i=1}^{t_1} \gamma'^{i-1} \frac{f'_i(x) - f'_i(z')}{x-z'} , [x]_2) $$
Common preprocessed input:
The prover only uses the
$$ n,\ srs \rightarrow ([x]1, [x^2]1,\dots,[x^{n+2}]1),\ (q_M, q_L, q_R, q_O, q_C){i=1}^n \rightarrow \begin{cases} q_M(X) = \sum{i=1}^n q{Mi} L_i(X)\ q_L(X)= \sum_{i=1}^n q_{Li} L_i(X),\ q_R(X)= \sum_{i=1}^n q_{Ri} L_i(X),\ q_O(X)= \sum_{i=1}^n q_{Oi} L_i(X),\ q_C(X)= \sum_{i=1}^n q_{Ci} L_i(X), \end{cases}\ \sigma(X) \rightarrow \begin{cases} S_{\sigma_1}(X) = \sum_{i=1}^n \sigma(i) L_i(X),\ S_{\sigma_2}(X) = \sum_{i=1}^n \sigma(n+i) L_i(X),\ S_{\sigma_3}(X) = \sum_{i=1}^n \sigma(2n+i) L_i(X),\ \end{cases}\ $$
The public input values will be written as part of the set of wires.
Having
The prover input is the set of values assigned to each wire:
Prover input:
Round 1 -- Commit to wire values.
Generate random blinding scalars $(b_1,\dots,b_9) \in \mathbb{F}p$ Compute wire polynomials $$ a(X) = (b_1 X + b_2)Z_H(X) + \sum{i=1}^n w_i L_i(X)\ b(X) = (b_3 X + b_4)Z_H(X) + \sum_{i=1}^n w_{n+i} L_i(X)\ c(X) = (b_5 X + b_6)Z_H(X) + \sum_{i=1}^n w_{2n+i} L_i(X) $$
Compute commitments: $$ [a]_1 := [a(x)]_1, [b]_1 := [b(x)]_1, [c]_1 := [c(x)]_1 $$
Output
Round 2 -- Permutation polynomial
Compute challenges
Compute permutation polynomial
Compute
Output
Round 3
Compute quotient challenge
Compute quotient polynomial
Note that all terms of the polynomial are divided by
Split
Compute $[t_{lo}]1 := [t{lo}(x)]1$, $[t{mid}]1 := [t{mid}(x)]1$, $[t{hi}]1 = [t{hi}(x)]_1$
Output $([t_{lo}]1, [t{mid}]1, [t{hi}]_1)$
Round 4
Compute evaluation challenge
Compute opening evaluations at
Compute linearisation polynomial
Compute linearisation evaluation at
Output ($\bar{a}, \bar{b},\bar{c}, \bar{s}{\sigma_1}, \bar{s}{\sigma_2}, \bar{z}_\omega, \bar{t}, \bar{r}$)
Round 5
Compute opening challenge
Compute opening proof polynomial
Compute opening proof polynomial
Compute $[W_\zeta]1:=[W\zeta(x)], [W_{\zeta \omega}]1:=[W{\zeta \omega}(x)]$
Return $$ \pi_{SNARK} = ([a]_1, [b]1, [c]1, [z]1, [t{lo}]1, [t{mid}]1, [t{hi}]1, [W\zeta]1, [W{\zeta \omega}]1, \ \bar{a}, \bar{b}, \bar{c}, \bar s{\sigma_1}, \bar s{\sigma_2}, \bar{r}, \bar z\omega ) $$
Compute multipoint evaluation challenge
Verifier preprocessed input:
$$[q_M]_1 := [q_M(x)]1,[q_L]1 := [q_L(x)1,[q_R]1 := [q_R(x)]1,$$ $$[q_O]1 := [q_O(x)]1,[q_C]1 := [q_C(x)]1,[s{\sigma{1}}]1 := [S{\sigma{1}}(x)],$$ $$[s{\sigma{2}}]1 := [S{\sigma{2}}(x)],[s{\sigma{3}}]1 := [S{\sigma{3}}(x)],([1]_2, [x]_2)$$
Verifier input: $(w_i){[l]}, \pi{SNARK}$
-
Validate $([a]_1, [b]_1, [c]_1, [z]1, [t{lo}]1, [t{mid}]1, [t{hi}]_1, [W_z]1, [W{z \omega}]_1 ) \in \mathbb{G}_1$
-
Validate
$(\bar a, \bar b, \bar c, \bar s_{\sigma_1}, \bar s_{\sigma_2}, \bar z, \bar z_\omega) \in \mathbb{F}_p^7$ -
Validate
$(w_i)({i \in [l]}) \in \mathbb{F}_p^l$ -
Compute challenges from common input public input and the elements of
$\pi_{SNARK}$ :$\beta, \gamma, \alpha, \zeta, v, u \in \mathbb{F}_p$ -
Compute
$Z_H(\zeta) = \zeta^n -1$ -
Compute
$L_1(\zeta) = \frac{\omega (\zeta^n - 1)}{n (\zeta - \omega)}$ -
Compute Public input polynomial evaluation
$PI(\zeta) = \sum_{i\in[l]} w_i L_i(\zeta)$ -
Compute quotient polynomial evaluation $$ \bar t = \frac{ \bar r + PI(\zeta) - ( (\bar a + \beta \bar s_{\sigma_1} + \gamma) (\bar b + \beta \bar s_{\sigma_2} + \gamma) (\bar c + \gamma) \bar z_\omega ) \alpha - L_1(\zeta) \alpha^2 }{ Z_H(\zeta) } $$
-
First part of batched polynomial commitment
$[D]_1 := v \cdot [r]_1 + u\cdot [z]_1$ : $$ v (\bar a \bar b [q_M]_1 +\bar a [q_L]_1 +\bar b [q_R]_1 +\bar c [q_O]1 +[q_C]1 )+$$ $$[z]1 ((\bar a + \beta \zeta + \gamma)(\bar b + \beta k_1 \zeta + \gamma)(\bar c + \beta k_2 \zeta + \gamma)\alpha v + L_1(\zeta)\alpha^2 v +u)$$ $$ - (\bar a + \beta \bar s{\sigma_1} \zeta + \gamma)(\bar b + \beta \bar s{\sigma_2} \zeta + \gamma)\alpha v\beta \bar z\omega[s{\sigma_3}]_1$$ -
Compute the fully batched polynomial commitment
$[F]_1$ : $$ [F]1 := [t{lo}]1 + \zeta^n [t{mid}]1 + \zeta^{2n} [t{hi}]_1 + [D]_1 + v^2 \cdot [a]_1 + v^3 \cdot [b]_1 + v^4 \cdot [c]1 + v^5 \cdot [s{\sigma_1}]1 + v^6 \cdot [s{\sigma_2}]_1 $$ -
Compute group-encoded bath evaluation $[E]1$: $$ [E]1 := \left[ \bar t + v \bar r + v^2 \bar a + v^3 \bar b + v^4 \bar c + v^5 \bar s{\sigma_1} + v^6 \bar s{\sigma_2} + u \bar z_\omega \right]_1 $$
-
Batch validate all evaluations $$ e( [W_\zeta]1) + u \cdot [W{\zeta \omega}]_1), [x]2 ) \stackrel{?}{=} e( \zeta \cdot [W\zeta]1) + u \zeta \omega \cdot [W{\zeta \omega}]_1) + [F]_1 - [E]_1, [1]_2 ) $$