PlonK

In this chapter, we will present the construction of GWC19, i.e., permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge.

PlonK is a succinct non-interactive zero-knowledge argument (SNARK) system that proves the correct execution of a program, i.e., in this case, an arithmetic circuit with only addition $(+)$ and multiplication $(\cdot)$ operations.

As an overview of the construction, we separate it into $2$ parts. First, we transform the arithmetic circuit into a set of constraints, called arithmetization and represented under some form of polynomials. Then, by applying some proof technique, it compiles the arithmetization into the proof.

Author(s): khaihanhtang

Plonk's Arithmetization

PlonK's arithmetization GWC19 breaks the circuit into a batch of gates, namely, multiplications, additions, multiplications with constants and additions with constants. For each gate, the operation is transformed into a unified form with respective selectors, uniquely determined by the gate without assigned inputs and output. On the other hand, since breaking circuit into gates introduces the inconsistencies among wires, we additionally apply copy constraints to wires to guarantee that such inconsistencies unavailable.

We describe circuit specification in Circuit Specification. Then, we discuss how to break the circuit into gates and label wires in Breaking Circuit. Then we present unified form of gate constraints in Gate Constraints and handling copy constraints in Copy Constraints.

Circuit Specification

Let $\mathbb{F}$ be a finite field. In this section, we describe the arithmetic circuit whose operations are over $\mathbb{F}$.

Let $\ell_{\mathsf{in}} \in \mathbb{N}$ be the number of input wires of the circuit $\mathcal{C}$. Assume that $\mathcal{C}$ has exactly $n$ gates. Each gate takes at most $2$ wires as inputs and returns $1$ output wires. In particular,

• Addition and multiplications gates takes $2$ inputs and return $1$ output.
• Gates of additions and multiplications with constants take $1$ input and return $1$ output.

Let's take a look at the following example.

Assume that $f(u, v) = u^2 + 3uv + v + 5$. Then the sequence are arranged in the following constraints, wrapped as below.

$$\left\{ \begin{array}{l} z_1 = u \cdot u &\text{(multiplication)}, \\ z_2 = u \cdot v &\text{(multiplication)}, \\ z_3 = z_2 \cdot 3 &\text{(multiplication with constant)}, \\ z_4 = z_1 + z_3 &\text{(addition)}, \\ z_5 = z_4 + v &\text{(addition)}, \\ z_6 = z_5 + 5 &\text{(addition with constant)}. \end{array}\right.$$

The input size is $\ell_{\mathsf{in}} = 2$ for variables $u, v$ and the output is $z_6$.

Breaking Circuit

To break the circuit into gates with wires separated, namely, no wire involves to $2$ or more gates, we use a set of labels $\mathcal{I} = \\{a_1, \dots, a_n, b_1, \dots, b_n, c_1, \dots, c_n\\}$ to denote the wire label of each gate. Let $x : \mathcal{I} \to \mathbb{F}$ be the function mapping wires to their respective wire values. Hence, $x(id)$ represents the value at wire $id \in \mathcal{I}$ For simplicity, we write $x_{id}$, in place of $x(id)$, for any $id \in \mathcal{I}$.

Specifically, for each $i \in \\{1, \dots, n\\}$, we denote by

• $x_{c_i} = x_{a_i}\circ x_{b_i}$ to denote the computation where $\circ$ is either addition or multiplication.
• $x_{c_i} = x_{a_i}\circ c$ to denote the computation where $\circ$ is either addition or multiplication with constant and $c$ is the constant.

At this point, we may be curious what value $x_{b_i}$ takes if $\circ$ is operation with constant. In fact, in this case $x_{b_i}$ can be seen as garbage and can take any value from $\mathbb{F}$. This value will affect neither security nor correctness of the system since the constraints in PlonK's arithmetization guarantee that such a compromise will not happen.

Let's take a look at the following example, taken from Circuit Specification.

We have $f(u, v) = u^2 + 3uv + v + 5$ and the constraints below.

$$\left\{ \begin{array}{l} z_1 = u \cdot u &\text{(multiplication)}, \\ z_2 = u \cdot v &\text{(multiplication)}, \\ z_3 = z_2 \cdot 3 &\text{(multiplication with constant)}, \\ z_4 = z_1 + z_3 &\text{(addition)}, \\ z_5 = z_4 + v &\text{(addition)}, \\ z_6 = z_5 + 5 &\text{(addition with constant)}. \end{array}\right.$$

By breaking circuit, we have the following constraints with respect to the above format, namely, using $\mathcal{I} = \{a_1, \dots, a_6, b_1, \dots, b_6, c_1, \dots, c_6\}$, where $n = 6$, and $x : \mathcal{I}\to \mathbb{F}$.

$$\left\{ \begin{array}{l} x_{c_1} = x_{a_1} \cdot x_{b_1}, \\ x_{c_2} = x_{a_2} \cdot x_{b_2}, \\ x_{c_3} = x_{a_3} \cdot 3, \\ x_{c_4} = x_{a_4} + x_{b_4}, \\ x_{c_5} = x_{a_5} + x_{b_5}, \\ x_{c_6} = x_{a_6} + 5 \end{array}\right.\text{ where } \left\{ \begin{array}{l} u = x_{a_1} = x_{a_2} = x_{b_1}, \\ v = x_{b_2} = x_{b_5}, \\ z_1 = x_{a_4} = x_{c_1}, \\ z_2 = x_{a_3} = x_{c_2}, \\ z_3 = x_{b_4} = x_{c_3}, \\ z_4 = x_{a_5} = x_{c_4}, \\ z_5 = x_{a_6} = x_{c_5}, \\ z_6 = x_{c_6}. \end{array}\right.$$

Notice that $v_{b_3}$ and $v_{b_6}$ are dismissed. These values can be any elements from $\mathbb{F}$ and do not have any effect to the arithmetization.

For equations in the system guaranteeing the correct computation of the operation, we call them gate constraints. For equations in the system guaranteeing the equalities, or consistencies, among wires, we call them copy constraints.

We first discuss the transformation of gate constraints into a common unified form with publicly determined selectors in Gate Constraints. Then, we discuss the method for guaranteeing copy constraints in Copy Constraints.

Gate constraints

At this stage, for each $i \in \\{1,\dots, n\\}$, we need to transform the computation of each gate to a unified form as follows: $q^O_i \cdot x_{c_i} + q^L_i \cdot x_{a_i} + q^R_i \cdot x_{b_i} + q^M_i \cdot (x_{a_i} \cdot x_{b_i}) + q^C_i = 0$ where $q_i^O, q_i^L, q_i^R, q_i^M, q_i^C$ are selectors uniquely determined by the corresponding gate. In particular,

• For addition gate, $(q_i^O, q_i^L, q_i^R, q_i^M, q_i^C) = (-1, 1, 1, 0, 0)$ since $(-1) \cdot x_{c_i} + 1 \cdot x_{a_i} + 1 \cdot x_{b_i} + 0 \cdot (x_{a_i} \cdot x_{b_i}) + 0 = 0$ is equivalent to $x_{c_i} = x_{a_i} + x_{b_i}$.

• For multiplication gate, $(q_i^O, q_i^L, q_i^R, q_i^M, q_i^C) = (-1, 0, 0, 1, 0)$ since $(-1) \cdot x_{c_i} + 0 \cdot x_{a_i} + 0 \cdot x_{b_i} + 1 \cdot (x_{a_i} \cdot x_{b_i}) + 0 = 0$ is equivalent to $x_{c_i} = x_{a_i} \cdot x_{b_i}$.

• For gate of addition with constant, $(q_i^O, q_i^L, q_i^R, q_i^M, q_i^C) = (-1, 1, 0, 0, c)$ since $(-1) \cdot x_{c_i} + 1 \cdot x_{a_i} + 0 \cdot x_{b_i} + 0 \cdot (x_{a_i} \cdot x_{b_i}) + c = 0$ is equivalent to $x_{c_i} = x_{a_i} + c$.

• For gate of multiplication with constant, $(q_i^O, q_i^L, q_i^R, q_i^M, q_i^C) = (-1, c, 0, 0, 0)$ since $(-1) \cdot x_{c_i} + c \cdot x_{a_i} + 0 \cdot x_{b_i} + 0 \cdot (x_{a_i} \cdot x_{b_i}) + 0 = 0$ is equivalent to $x_{c_i} = x_{a_i} \cdot c$.

We now take a look at the example achieved above, i.e.,

$$\left\{ \begin{array}{l} x_{c_1} = x_{a_1} \cdot x_{b_1}, \\ x_{c_2} = x_{a_2} \cdot x_{b_2}, \\ x_{c_3} = x_{a_3} \cdot 3, \\ x_{c_4} = x_{a_4} + x_{b_4}, \\ x_{c_5} = x_{a_5} + x_{b_5}, \\ x_{c_6} = x_{a_6} + 5. \end{array}\right.$$

In this example, we can transform the above system of equation into the unified form as follows:

$$\left\{ \begin{array}{l} (-1) \cdot x_{c_1} + 0 \cdot x_{a_1} + 0 \cdot x_{b_1} + 1 \cdot (x_{a_1} \cdot x_{b_1}) + 0 = 0, \\ (-1) \cdot x_{c_2} + 0 \cdot x_{a_2} + 0 \cdot x_{b_2} + 1 \cdot (x_{a_2} \cdot x_{b_2}) + 0 = 0, \\ (-1) \cdot x_{c_3} + 3 \cdot x_{a_3} + 0 \cdot x_{b_3} + 0 \cdot (x_{a_3} \cdot x_{b_3}) + 0 = 0, \\ (-1) \cdot x_{c_4} + 1 \cdot x_{a_4} + 1 \cdot x_{b_4} + 0 \cdot (x_{a_4} \cdot x_{b_4}) + 0 = 0, \\ (-1) \cdot x_{c_5} + 1 \cdot x_{a_5} + 1 \cdot x_{b_5} + 0 \cdot (x_{a_5} \cdot x_{b_5}) + 0 = 0, \\ (-1) \cdot x_{c_6} + 1 \cdot x_{a_6} + 0 \cdot x_{b_6} + 0 \cdot (x_{a_6} \cdot x_{b_6}) + 5 = 0. \end{array}\right.$$

Copy Constraints

Recall that gate constraints do not enforce the equalities of wire values making inconsistencies across the circuit. We generalize copy constraints to the following problem.

Let $k \in \{1, \dots, 3n\}$ and $\{i_1, \dots, i_k\} \subseteq \mathcal{I}$ satisfying $i_1 < i_2 < \dots < i_k$. We would like to show that

$$x_{i_1} = x_{i_2} = \dots = x_{i_k}.$$

The technique for proving this problem is tricky. We form the pairs of index-value and make them into a sequence

$$\big((i_1, x_{i_1}), (i_2, x_{i_2}), \dots, (i_k, x_{i_k})\big).$$

It can be observed that if $x_{i_1} = x_{i_2} = \dots = x_{i_k}$, then, if we rotate the indices among the pairs, we achieve a sequence

$$\big((i_k, x_{i_1}), (i_1, x_{i_2}), \dots, (i_{k - 1}, x_{i_k})\big)$$

that is permutation of the previous sequence. Notice that we just rotated the indices $1$ step to the left and this is the recommended rotation. This fact helps imply the other direction of the fact. For more details, we use the following observation

Observation. $\big((i_1, x_{i_1}), (i_2, x_{i_2}), \dots, (i_k, x_{i_k})\big)$ is a permutation of $\big((i_k, x_{i_1}), (i_1, x_{i_2}), \dots, (i_{k - 1}, x_{i_k})\big)$ if and only if $x_{i_1} = x_{i_2} = \dots = x_{i_k}$.

Proof. The proof is as follows:

"$\Leftarrow$": This direction is straightforward.

"$\Rightarrow$": Since the two sequences are permutation of each other, for $j \in \\{1, \dots, k\\}$ we consider $(i_j, x_{i_j})$ from the first sequence. It can be seen that $(i_j, x_{i_{(j \mod k) + 1}})$ from the second sequence is the only one that is equal $j \in \\{1, \dots, k\\}$ since they share the unique prefix $i_j$. Hence, $x_{i_j} = x_{i_{(j \mod k) + 1}}$. Following this argument, we see that $x_{i_1} = x_{i_2}, x_{i_2} = x_{i_3}, \dots, x_{i_{k - 1}} = x_{i_k}, x_{i_k} = x_{i_1}$. Thus, $x_{i_1} = x_{i_2} = \dots = x_{i_k}$.

General paradigm for proving copy constraints of the entire circuit

Recall that $x : \mathcal{I} \to \mathbb{F}$. We can deterministically determine a partition of $\mathcal{I}$ such that

$$\mathcal{I} = \bigcup_{j = 1}^{\ell_{\mathsf{in}} + n} \mathcal{I}_j$$

where $\ell_{\mathsf{in}} + n$ is the number of wires of the original circuits, namely, $\ell_{\mathsf{in}}$ input wires and $n$ output wires of all gates. Hence each subset $\mathcal{I}_j$ is the set of wire labels whose value are all equal to the same wire value of the original circuit. We hence obtain a rotation of indices for each subset $\mathcal{I}_j$. By unifying all those rotations, we achieve a permutation $\sigma : \mathcal{I}\to\mathcal{I}$ such that

$$\big((a_1, x_{a_1}), \dots, (a_n, x_{a_n}), (b_1, x_{b_1}), \dots, (b_n, x_{b_n}), (c_1, x_{c_1}), \dots, (c_n, x_{c_n})\big)$$

is a permutation of

$$\big((\sigma(a_1), x_{a_1}), \dots, (\sigma(a_n), x_{a_n}), (\sigma(b_1), x_{b_1}), \dots, (\sigma(b_n), x_{b_n}), (\sigma(c_1), x_{c_1}), \dots, (\sigma(c_n), x_{c_n})\big).$$

Such guaranteed permutation relation implies the consistencies among wires of the circuit.

Recall the example in Breaking Circuit with the following copy constraints.

$$\left\{ \begin{array}{l} u = x_{a_1} = x_{a_2} = x_{b_1}, \\ v = x_{b_2} = x_{b_5}, \\ z_1 = x_{a_4} = x_{c_1}, \\ z_2 = x_{a_3} = x_{c_2}, \\ z_3 = x_{b_4} = x_{c_3}, \\ z_4 = x_{a_5} = x_{c_4}, \\ z_5 = x_{a_6} = x_{c_5}, \\ z_6 = x_{c_6}. \end{array}\right.$$

We achieve the partition

$$\big\{\{a_1, a_2, b_1\}, \{b_2, b_5\}, \{a_4, c_1\}, \{a_3, c_2\}, \{b_4, c_3\}, \{a_5, c_4\}, \{a_6, c_5\}, \{c_6\}\big\}.$$

We hence can achive the permutation $\sigma: \mathcal{I}\to\mathcal{I}$ as follows:

$$\left\{ \begin{array}{l} \sigma(a_1) = b_1, &\sigma(a_2) = a_1, &\sigma(b_1) = a_2, \\ \sigma(b_2) = b_5, &\sigma(b_5) = b_2, \\ \sigma(a_4) = c_1, &\sigma(c_1) = a_4, \\ \sigma(a_3) = c_2, &\sigma(c_2) = a_3, \\ \sigma(b_4) = c_3, &\sigma(c_3) = b_4, \\ \sigma(a_5) = c_4, &\sigma(c_4) = a_5, \\ \sigma(a_6) = c_5, &\sigma(c_5) = a_6, \\ \sigma(c_6) = c_6. \end{array} \right.$$