Understanding PLONK (Part 1): Plonkish Arithmetization

Arithmetization refers to transforming computations into mathematical objects and then performing zero-knowledge proofs. Plonkish arithmetization is a specific arithmetization method in the Plonk proof system. Prior to the introduction of Plonkish, the mainstream circuit representation was R1CS, widely used in systems such as Pinocchio, Groth16, and Bulletproofs. In 2019, the Plonk scheme proposed a seemingly retrograde circuit encoding method. However, due to its extreme application of polynomial encoding, Plonk is no longer limited to “addition gates” and “multiplication gates” in arithmetic circuits, but can support more flexible “custom gates” and “lookup gates”.

Let’s first review the circuit encoding of R1CS, which is the most commonly used arithmetic scheme. Then we will compare it with the introduction of Plonkish encoding.

Arithmetic circuits and arithmeticization of R1CS

An arithmetic circuit consists of several multiplication gates and addition gates. Each gate has “two input” pins and one “output” pin, and any output pin can be connected to multiple input pins of gates.

First, let’s look at a very simple arithmetic circuit:

This circuit represents such a calculation:

$$(x_1+x_2)\cdot (2\cdot x_3)=out$$

There are 4 variables in the circuit, with three variables being input variables $(x_1,x_2,x_3)$, one output variable $out$, and one constant input with a value of $2$.

A circuit has two states: “blank state” and “operational state”. When the input variables do not have specific values, the circuit is in the “blank state”, and we can only describe the relationship between the circuit wires, or the structural topology of the circuit.

The next step is to encode the “blank state” of the circuit, which means encoding the positions of each gate and their interconnecting wire relationships.

R1CS is centered around multiplication gates in the graph, using three “selector” matrices to connect the “left input,” “right input,” and “output” of the multiplication gates to respective variables.

Let’s start by looking at the left input of the multiplication gate at the top of the diagram. It can be described using the table below:

This form has only one row, so we can use a vector $U=(0,1,1,0,0)$ to represent that the left input of the multiplication gate is connected to two variables, $x_1$ and $x_2$. Remember, all addition gates will be expanded into sums (or linear combinations) of multiple variables.

再看看其右输入，连接了一个变量 $x_3$ 和一个常数值，等价于连接了 $x_3$ 的两倍，那么右输入的选择子矩阵可以记为

Here, it can also be represented by a row vector $V=(0,0,0,2,0)$, where the $2$ represents the constant terminal of the circuit in the above diagram.

The output of the final multiplication gate can be described as $W=(0,0,0,0,1)$, with the output variable being $out$.

With three vectors (U, V, W), we can constrain the operation of the circuit through an “inner product” equation:

$$big(U\cdot (1,x_1,x_2,x_3,out))\cdot (V\cdot (1,x_1,x_2,x_3,out))=(W\cdot (1,x_1,x_2,x_3,out))$$

After simplifying this equation, we can obtain:

$$(x_1+x2)\cdot (2\cdot x_3)=out$$

If we substitute these variables with the assignment vector $(1,x_1,x_2,x_3,out)=(1,3,4,5,70)$, then the circuit operation can be verified through the “inner product” equation:

$$(U\cdot (1,3,4,5,70))\cdot (U\cdot (1,3,4,5,70))=W\cdot (1,3,4,5,70)$$

And if we have an incorrectly assigned vector, such as $(1,3,4,\boxed{0},70)$, it does not satisfy the “inner product equation”:

$$(U\cdot (1,3,4,\boxed{0},70))\cdot (U\cdot (1,3,4,\boxed{0},70))\ne W\cdot (1,3,4,\boxed{0},70)$$

The result of the left-side arithmetic is $0$, and the result of the right-side arithmetic is $70$. Of course, we can verify that $(1,3,4,0,0)$ is also a valid (satisfying circuit constraints) assignment.

Not every circuit has an assignment vector. Circuits that have a valid assignment vector are called satisfiable circuits. Determining whether a circuit is satisfiable is an NP-Complete problem and also an NP-hard problem.

The two multiplication gates in the examples are not the same. The multiplication gate above has variables in both inputs, while the multiplication gate below has a variable on one side and a constant on the other side. For the latter type of “constant multiplication gate”, we also consider them as special “addition gates”. As shown in the diagram below, the multiplication gate in the bottom right of the left circuit is equivalent to the addition gate in the bottom right of the right circuit.

So if a circuit contains more than two multiplication gates, we cannot use the inner product relationship between the vectors $U,V,W$ to represent the operation, and we need to construct an operation relationship between “three matrices”.

Multiple multiplication gates

For example, in the circuit shown below, there are two multiplication gates, and both their left and right inputs involve variables.

This circuit represents such a calculation:

$$(x_1+x2)\cdot (x3\cdot x4)=out$$

We encode the circuit based on the multiplication gates. In the first step, the multiplication gates in the circuit are numbered sequentially (the order of numbering doesn’t matter as long as it is consistent). The two multiplication gates in the diagram are encoded as #1 and #2.

And then we need to give variable names to the intermediate wires of each multiplication gate: for example, four input variables are denoted as $x_1,x_2,x_3,x_4$, with $x_5$ being the output of the second multiplication gate and also serving as the right input of the first multiplication gate. And $out$ is the output of the first multiplication gate. Therefore, we can obtain a vector of variable names:

$$(x_1,x_2,x_3,x_4,x_5,out)$$

The “blank state” of this circuit can be encoded using the following three matrices:

$$U,V,W\in {\mathbb{F}}^{n\times m}$$

I understand. Here is the text:

Where $n$ is the number of multiplication gates, and $m$ is approximately the number of wires. Each row of the matrix “selects” the input/output variables of the corresponding multiplication gate. For example, we define the left input matrix $U$ of the circuit:

The left input of the first multiplier gate is $(x_1+x_2)$, and the left input of the second multiplier gate is $x_3$. The right input matrix $V$ is defined as:

The right input of gate No. 1 is $x_5$, and the right input of the second multiplication gate is $x_4$. Finally, the output matrix $W$ is defined as follows:

We treat all the wire assignments as a vector: $\vec{a}$ (here using the letter $a$, taken from the first letter of Assignments)

In the above example, the “assignment vector” is

$$veca=(x_1,x_2,x_3,x_4,x_5,out)$$

So we can easily verify the following equation.

$$(U\cdot \vec{a})\circ (V\cdot \vec{a})=(W\cdot \vec{a})$$

The symbol $\circ$ represents Hadamard Product, which indicates “element-wise multiplication”. Expanding the above element-wise multiplication equation, we can obtain the operation process of this circuit:

\left[

Please note that in general, a “assignment vector” needs a variable with a fixed value of $1$, which is necessary to handle constant inputs in addition gates.

Advantages and disadvantages

Due to the R1CS encoding being centered around multiplication gates, the addition gates in the circuit do not increase the number of rows in the matrices $U,V,W$, thus having little impact on the performance of the Prover. The encoding of R1CS circuits is clear and simple, which facilitates the construction of various SNARK schemes on top of it.

The encoding scheme in the 2019 Plonk paper requires encoding both addition and multiplication gates, which seems to increase the number of constraints and decrease the proving performance. However, the Plonk team subsequently introduced additional gates besides multiplication and addition, such as gates for range checks and XOR operations. Moreover, Plonk supports any gate with polynomial relations between its inputs and outputs, known as Custom Gates, as well as state transition gates for implementing RAM. With the introduction of lookup gates, the Plonk scheme gradually became the preferred choice for many applications, and its encoding method also gained a dedicated term: Plonkish.

Plonkish Arithmetic Door

Looking back at the example circuit, we will number all three gates as $\text{1},\text{2},\text{3}$, and we will also mark the output value of the adder gate as variable $x_6$.

Clearly, the above circuit satisfies three constraints:

• $x_1+x_2=x_6$

• $x_3\cdot x_4=x_5$

• I understand. Here is the translation:

  “$x_6\cdot x_5=out$”

We define a matrix $W\in {\mathbb{F}}^{n\times 3}$ to represent the constraints (where $n$ is the number of arithmetic gates):

In order to differentiate addition and multiplication, we define a vector $Q\in {\mathbb{F}}^{n\times 5}$ to represent the operator.

So we can represent the three constraints using the following equations:

$$q_L\circ w_a+q_R\circ w_b+q_M\circ (w_a\cdot w_b)+q_C-q_O\circ w_c=0$$

If we substitute and expand the equation above, we can obtain the following constraint equations:

\left[

Simplified to:

\left[

This is exactly the calculation constraint of three arithmetic operations.

In summary, Plonkish requires a matrix $Q$ to describe the circuit’s blank state, while all assignments are written into the matrix $W$. For the exchange protocol between the Prover and Verifier, $W$ is the Prover’s witness, which is considered secret and kept confidential from the Verifier. The matrix $Q$ represents a circuit description that achieves consensus between both parties.

However, having only the $Q$ matrix is not sufficient to accurately describe the circuit in the example above.

Copy Constraints

Compare the following two circuits. Their Q matrices are completely identical, but they are completely different.

The difference between the two circuits lies in whether $x_5,x_6$ are connected to gate #1. If the Prover directly fills in the assignment of the circuit in the $W$ table, an “honest” Prover would fill in the same value in the positions $wa,1$ and $w$c,2; while a “malicious” Prover could fill in different values. If the malicious Prover also fills in different values in $wb,1$ and $w$c,3, then in reality, the Prover is proving the circuit on the right side of the diagram, not the agreed-upon circuit between the Verifier and the Prover (on the left side).

We need to add new constraints that require in the right circuit diagram $x_6=x_7$ and $x_5=x_8$. This is equivalent to demanding that when Prover fills in multiple positions in the table with the same variable, they must fill in equal values.

This requires a new type of constraint called “Copy Constraint”. Plonk uses “Permutation Proofs” to ensure that the values at multiple positions in the table $W$ satisfy the copy relationship. We continue to use the example of the circuit diagram above to illustrate its basic idea:

Imagine that we arrange all the position indices in table $W$ into a vector:

sigma0​=(wa,1​,wa,2,wa,3,wb,1​,wb,2,wb,3,wc,1,wc,2​,w_c,3​)

Then swap the two positions that should be equal, for example, in the figure above, it is required that $wa,1=w$ and $wb,1=w$. Thus, we obtain the following positional vectors:

sigma=(wc,2​,wa,2,wa,3,wc,3​,wb,2,wb,3,wc,1,wa,1​,w_b,1​)

Then we ask the Prover to prove that: $W$ table remains the same after the permutation above. The equality before and after the permutation ensures that the Prover cannot cheat.

Here’s another example, when constraining that three (or more) values in a vector must be equal, you only need to shift the values at these three (or more) positions cyclically (left or right), and then prove that the shifted vector is equal to the original vector. For example:

$$A=(b_1,b_2,\underline{a_1},b_3,\underline{a_2},b_4,\underline{a_3})$$

If we want to prove that $a_1=a_2=a_3$, then we only need to prove:

$$A^{\prime }=(b_1,b_2,\underline{a_3},b_3,\underline{a_1},b_2,\underline{a_2})\stackrel{?}{=}A$$

In the vector $A^{\prime }$ after shuffling, $a_1,a_2,a_3$ are moved and swapped to the right in sequence, meaning $a_1$ is placed in the original position of $a_2$, while $a_2$ is placed in the position of $a_3$, and $a_3$ is placed in the position of $a_1$.

If $A^{\prime }=A$, then all the values at the corresponding positions of $A^{\prime }$ and $A$ should be equal. It can be deduced that: $a_1=a_3$, $a_2=a_1$, $a_3=a_2$, which means $a_1=a_2=a_3$. This method is applicable to any number of equivalent relationships. (For the subsequent method of proving the equality of two vectors, please refer to the next chapter.)

So how to describe the exchange in the circuit assignment table? We only need to record the $\sigma$ vector, of course, the $\sigma$ vector can also be written in the form of a table:

Adding $\sigma$, the blank circuit can be described as $(Q,\sigma )$, where the assignment of the circuit is $W$.

$$mathsfPlonkish\_0\triangleq (Q,\sigma ;W)$$

Comparison again

The width of the $(U,V,W)$ table in R1CS depends on the number of wires, and the number of rows depends on the number of multiplication gates. This construction treats arithmetic circuits as consisting only of multiplication gates, but each gate has multiple input pins (up to the total number of wires). On the other hand, Plonkish treats addition and multiplication gates equally, and because there are only two input pins, the width of the $W$ table is fixed at three columns (although the table can be expanded to support more advanced gates). This feature allows Plonk to utilize the Permutation Argument for the implementation of copy constraints.

…, and thus our linear contraints are just wiring constraints that can be reduced to a permutation check.

按照 Plonk 论文的统计，一般情况下，算术电路中加法门的数量是乘法门的两倍。如果这样看来， $W$ 表格的行数会三倍于 R1CS 的矩阵。但这个让步会带来更多的算术化灵活度。

Circuit verification protocol framework

With the description and assignment of the circuit blank structure, we can roughly describe the protocol framework of Plonk.

First, the Prover and Verifier agree on a common circuit, $(Q,\sigma )$. Assuming the public output of the circuit is $out=99$, and $(x_1,x_2,x_3,x_4)$ are the secret inputs.

Fill in the $W$ matrix (Invisible to Verifier):

The additional fourth line is added to introduce an extra arithmetic constraint: $out=99$, where the value of $out$ is explicitly shown in the matrix $Q$.

The corresponding $Q$ matrix for the consensus of Prover and Verifier is

I understand. Here is the text:

“In the fourth line constraint, it ensures that $out=99$. By substituting $(q_L=0,q_R=0,q_M=0,q_C=99,q_O=1)$ into the arithmetic constraint below, we obtain $99-w_c=0$, which means $wc,4=99"."$$q_L\circ w_a+q_R\circ w_b+q_M\circ (w_a\cdot w_b)+q_C-q_O\circ w_c=0$$Toensurethatthevalueof$w_c$inthefirstrowisalso$99$,anadditionalcopyconstraintneedstobeaddedinthe$\sigma$matrix:thepositionofthevariable$outw_{c,1}$shouldbeswappedwiththeoutput$w_{c,4}$ofthefourthrow.$

References

• I understand. Here is the translation:

  [BG12] Bayer, Stephanie, and Jens Groth. “Efficient zero-knowledge argument for correctness of a shuffle.” Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2012.

• I understand. Here is the text:

  [GWC19] Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. “Plonk: Permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge.” Cryptology ePrint Archive (2019).