PlonK Permutation Check
Moin! This blog hasn't been updated for a while and it is a shame. A newer post is long overdue. Recently I have been diving into more SNARK and STARK protocols, One of the latest as the $\mathcal{P} \mathfrak{lon} \mathcal{K}$ protocol. In a series of posts to come I would like to take some notes about it.
What is $\mathcal{P} \mathfrak{lon} \mathcal{K}$ about?
Intro
$\mathcal{P} \mathfrak{lon} \mathcal{K}$ is, as the original paper states it, a protocol for "universal full-succinct zk-SNARK". The name itself is an abbreviation for "Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge". That's a lot of words some or all of which I don't know so let's try to dive in what is actually going on in the paper and in the protocol. SNARK and STARK protocols allow us to generate (succinct) proofs of execution of some programs over given data. I will first very quickly describe what $\mathcal{P} \mathfrak{lon} \mathcal{K}$ does and what the "easy" checks are. I will assume that the reader is familiar with all the preliminaries that would be appropriate here, such as the KZG scheme, Pairing-friendly Elliptic Curves, Fields, and so on. My goal is then to go a bit deeper into the actual meat and bones of the original paper which is believed to be the 5-th part of the paper "Polynomial protocols for identifying permutations". For a deeper dive into the material of the paper prior to the 5-th chapter I highly recommend Dan Boneh's lecture from the ZKP MOOC.
The Easy Part
Let's quickly refresh the easier part of $\mathcal{P} \mathfrak{lon} \mathcal{K}$: how the computation is performed, how the trace is constructed and how the "easy" constraints are constructed.
The system allows us to prove traces of executions of programs described in the form of circuits. The computations are done over some field $\mathbb{F}$.
As an example of such a circuit consider the following one with two addition gates and one multiplication gate:
or, in the form of a polynomial:
$$ y = (x_1 + x_2)(x_3 + x_4) $$
If the computation of this circuit is performed over the values of the field $\mathbb{F_13}$, namely $x_1 = 2, x_2 = 3, x_3 = 4, x_4 = 6$, then at each step of execution we will compute the following values:
$$ t_1 = x_1 + x_2 = 5, t_2 = x_3 + x_4 = 10 \newline y = t_1 \cdot t_2 = 5 \cdot 10 = 50 \equiv 11 \pmod{13} $$
Or, if we name the left and the right input of every node in the circuit respectively $a$ and $b$ and its output $c$, in table form:
$$ \begin{array}{|c|c|c|} \hline a & b & c \\ \hline 2 & 3 & 2 + 3 = 5 \\ \hline 4 & 6 & 4 + 6 = 10 \\ \hline 5 & 10 & 5 \cdot 10 = 50 \equiv 11 \pmod{13} \\ \hline \end{array} $$
And so to capture the both types of computations (addition and multiplication) and the equality of the results a constraint is introduced with the help of selectors $\mathcal{Q} = (\mathbf{q_L}, \mathbf{q_R}, \mathbf{q_O},\mathbf{q_M}, \mathbf{q_C})$ that either enable or disable respectively multiplication or addition operation within the following equation:
$$ \mathbf{q_L} \cdot a_i + \mathbf{q_R} \cdot b_i + \mathbf{q_O} \cdot c_i + \mathbf{q_M} \cdot (a_i \cdot b_i) + \mathbf{q_C} = 0 $$
By switching the selector values we can turn the above equation into an addition or multiplication gate checks. If we add selector columns to the above trace table:
$$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline a & b & c & \mathbf{q_L} & \mathbf{q_R} & \mathbf{q_O} & \mathbf{q_M} & \mathbf{q_C} \\ \hline 2 & 3 & 5 & 1 & 1 & -1 & 0 & 0 \\ \hline 4 & 6 & 10 & 1 & 1 & -1 & 0 & 0 \\ \hline 5 & 10 & 11 & 0 & 0 & -1 & 1 & 0 \\ \hline \end{array} $$
What we check in the "easy" part of the protocol is the equality of all of the above constraints to zero (ZeroCheck gadget) and also the "correctness" of assignment of inputs and outputs (meaning that they equal the claimed values). The way it is done in detail is best described in Dan Boneh's lecture that was mentioned earlier and in a lot of materials easily found online, such as Understanding PLONK by Vitalik Buterin.
As it turns out the above checks are not enough to actually check the correctness of the program execution since just running a ZeroCheck on each row constraint does not tell us much other than the fact that we have "seen" some polynomials that are equal to zero on claimed points. As a matter of fact these checks allow a dishonest prover to provide a set of zero polynomials that by definition equal to $0$ everywhere and they would perfectly satisfy the constraints described above. The problem is that those check every single row without checking the relations between rows. They do not check that the output of first gate (5) becomes the first input to the third gate (5). Checking all relations between the rows of the trace is what the "hard" part of the protocol is about.
The Hard Part
Now let's get to the harder part that the original paper calls "The heart of our universal SNARK", namely the "Polynomial Protocols for identifying permutations". I am going to cite the chapter step by step and try to unfold the logic behind each step and add a pen and paper example to it.
$\exists \text{ a multiplicative subgroup } H \subset \mathbb{F}$, of order $n$ with generator $\mathbf{g}$.
Note: my understanding of notation in the paper is that $[n]$ means a range of numbers starting with $0$ up to $n-1$.
For $i \in [n]$, we denote by $L_i(X)$ the element of $\mathbb{F}_{<n}[X]$ with $L_i(g^i) = 1$ and $L_i(a) = 0 \quad \forall a \in H, a \neq \mathbf{g}^i$, i.e. $\{L_i\} _{i \in [n]}$ is a Lagrange basis for $H$.
What the Lagrange Bases allow us to do is to select a specific row in the evaluation table of some polynomial.
$$ \begin{array}{|c|c|c|c|c|} \hline H & f & L_0 & L_1 & L_2 \\ \hline 1 & 2 & 1 & 0 & 0 \\ \hline 3 & 5 & 0 & 1 & 0 \\ \hline 9 & 7 & 0 & 0 & 1 \\ \hline \end{array} $$
Multiplying a polynomial by the $L_i$ allows us to constrain only the $i$-th row of the polynomial. $L_o(X) * f(X) = 0$ will only enforce $f(\omega^0) \equiv f(1) = 0$.
The Lagrange Bases allow the following claim:
Claim 5.1. Fix $i \in [n]$, and $Z, Z^* \in \mathbb{F}[X]$. Then $L_i(a)(Z(a) - Z^*(a)) = 0$ for each $a \in H$ if and only if $Z(\mathbf{g}^i) = Z^*(\mathbf{g}^i) $.
The Permutation
Next, a permutation is defined:
For $f, g \in \mathbb{F}_{<d}[X]$ and a permutation $\sigma : [n] -> [n]$, we write $g = \sigma(f)$ if $\forall i \in [n], g(\mathbf{g}^i) = f(\mathbf{g}^{\sigma(i)})$.
What this says is that we have a rule by which we shuffle the powers of generator $\mathbf{g}$ of $H$ and that the evaluations of $f,g$ w.r.t. that shuffle should match. Let's have a look at example:
Let the permutation $\sigma$ be defined as
$$ \sigma(0) = 1, \sigma(1) = 2, \sigma(2) = 0 $$
And so if we have a function $f$ defined by the following table (note the powers of $\omega$)
$$ \begin{array}{|c|c|} \hline H & f \\ \hline 1 = \omega^0 & 2 \\ \hline 3 = \omega^1 & 5 \\ \hline 9 = \omega^2 & 7 \\ \hline \end{array} $$
in this case the permutation performs a rotating shift, but in the general case obviously it can be any bijective permutation.
$g$ has to have the same evaluations over the powers of $\omega$ shuffled according to the permutation $\sigma$:
$$ \begin{array}{|c|c|} \hline H & g \\ \hline 3 = \omega^1 & 7 \\ \hline 9 = \omega^2 & 2 \\ \hline 1 = \omega^0 & 5 \\ \hline \end{array} $$
And merging and sorting the three tables by $H$:
$$ \begin{array}{|c|c|c|} \hline H & f & g \\ \hline 1 = \omega^0 & 2 & 5 \\ \hline 3 = \omega^1 & 5 & 7 \\ \hline 9 = \omega^2 & 7 & 2 \\ \hline \end{array} $$
$g$ is the evaluations of $f$ shuffled accordingly to $\sigma$, or in this particular example just shifted one position right with rotation.
Permutation Checking
What the protocol aims to do is to allow $\mathbf{P_{poly}}$ (the prover) to prove that $g = \sigma(f)$
Identity and shuffle polynomials
Before introducing the protocol, two more polynomials called "preprocessed polynomials" are introduced:
$\mathsf{S}_{\mathsf{ID}} \in \mathbb{F}_{<n}[X]$ defined by $\mathsf{S_{ID}}(\mathbf{g}^i) = i; ~ \forall i \in [n]$
$\mathsf{S}_{\sigma} \in \mathbb{F}_{<n}[X]$ defined by $\mathsf{S}_{\sigma}(\mathbf{g}^i) = \sigma(i); ~ \forall i \in [n]$
These are the identity and permutation polynomials
$$ \begin{array}{|c|c|c|c|c|} \hline H & i & \sigma(i) & \mathsf{S}_{\mathsf{ID}} & \mathsf{S}_{\sigma} \\ \hline 1 = \omega^0 & 0 & 1 & 0 & 1 \\ \hline 3 = \omega^1 & 1 & 2 & 1 & 2 \\ \hline 9 = \omega^2 & 2 & 0 & 2 & 0 \\ \hline \end{array} $$
The Protocol
- The Verifier $\mathbf{V_{poly}}$ samples random $\beta,\gamma \in \mathbb{F}$.
- Sample polys
- $f' := f + \beta \cdot \mathsf{S_{ID}} + \gamma$, (meaning $f'(\mathsf{g}^i) = f(\mathsf{g}^i) + \beta \cdot i + \gamma ~ \forall i \in [n]$)
- $g' := g + \beta \cdot \mathsf{S_{\sigma}} + \gamma$ (meaning $g'(\mathsf{g}^i) = g(\mathsf{g}^i) + \beta \cdot \sigma(i) + \gamma ~ \forall i \in [n]$)
-
$\mathbf{P_{poly}}$ computes $Z \in \mathbb{F}_{<n}[X]$, s.t. $Z(\mathbf{g}) = 1$ and $\forall i \in \{2,..,n\}$
$$ Z(\mathbf{g}^i) = \prod_{1 \leq j < i} f'(\mathbf{g}^j) / g'(\mathbf{g}^j) $$
-
$\mathbf{P_{poly}}$ sends $Z$.
-
$\mathbf{V_{poly}}$ checks that $\forall a \in H$:
- $L_1(a)(Z(a) - 1) = 0$
- $Z(a)f'(a) = g'(a)Z(a \cdot \mathbf{g})$.
Okay, but what does this all mean, what does it allow us to prove and why all of this works and is useful to us.
Why is proving $g = \sigma(f)$ useful?
Remember, our ultimate goal w.r.t. wiring checks in $\mathcal{P} \mathfrak{lon} \mathcal{K}$ is to check that the execution trace is "wired" correctly, namely that that the outputs and the inputs of gates have matching values when there exists a wire between them. This would bind a series of unrelated gate constraints (one for each row of the trace) with each other.
Let's look again at the trace of $f$ mentioned earlier:
$$ \begin{array}{|c|c|c|} \hline a & b & c \\ \hline 2 & 3 & 2 + 3 = 5 \\ \hline 4 & 6 & 4 + 6 = 10 \\ \hline 5 & 10 & 5 \cdot 10 = 50 \equiv 11 \pmod{13} \\ \hline \end{array} $$
Here we want to check if $c_0 = a_2 \equiv 5$ and that $c_1 = b_2 \equiv 10$.
Let's just for a moment look at the values from the above table as a one-dimensional array of elements of length $9$:
$$ \begin{array}{|c|c|c| c|c|c| c|c|c|} \hline 2 & 4 & 5 & 3 & 6 & 10 & 5 & 10 & 11 \\ \hline \end{array} $$
From this point on, I am no longer preserving the original circuit computation over $\mathbb{F_{13}}$. I only reuse the trace values as a toy vector over $\mathbb{F}_{19}$ so that we have a subgroup of size $9$.
Remember, that in the definition of the permutation we first need a multiplicative subgroup $H \subset \mathbb{F}$ of order $n$ with generator $\omega$. In a field $\mathbb{F}_{19}$ there exists a multiplicative subgroup of size $9$ with $\omega = 4$ (for reasons, you can check it yourself).
Let's write out the values of this subgroup in both exponentiations of the generator and values form:
$$ \begin{array}{|c|c|c| c|c|c| c|c|c|} \hline 4^0 & 4^1 & 4^2 & 4^3 & 4^4 & 4^5 & 4^6 & 4^7 & 4^8 \\ \hline 1 & 4 & 16 & 7 & 9 & 17 & 11 & 6 & 5 \\ \hline \end{array} $$
Now let's add these toy evaluations of $f$ to the same table, together with the corresponding $i$ values:
$$ \begin{array}{|c|c|c|c| c|c|c| c|c|c|} \hline i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline \omega^i & 4^0 & 4^1 & 4^2 & 4^3 & 4^4 & 4^5 & 4^6 & 4^7 & 4^8 \\ \hline \omega^i & 1 & 4 & 16 & 7 & 9 & 17 & 11 & 6 & 5 \\ \hline f & 2 & 4 & 5 & 3 & 6 & 10 & 5 & 10 & 11 \\ \hline \end{array} $$
And so we view the values of $f$ as evaluations over $\langle \omega \rangle$. We want to prove that two $5$ values in their positions are equal to each other, same about $10$ values. So how can we use the permutation to check it is to create a permutation $\sigma$ that permutes the groups of values we want to check which would lead us to a new polynomial $g$ as defined above and if the check $g = \sigma(f)$ passes, this means that after permuting the values $5$ and $5$ and $10$ and $10$ have remained unchanged and as such they are equal to each other.
let's add $\sigma(i)$ and $g$ to the table and highlight the permutation:
$$ \begin{array}{|c|c|c|c| c|c|c| c|c|c|} \hline i & 0 & 1 & \colorbox{red}{2} & 3 & 4 & \colorbox{yellow}{5} & \colorbox{red}{6} & \colorbox{yellow}{7} & 8 \\ \hline \omega^i & 4^0 & 4^1 & 4^2 & 4^3 & 4^4 & 4^5 & 4^6 & 4^7 & 4^8 \\ \hline \omega^i & 1 & 4 & 16 & 7 & 9 & 17 & 11 & 6 & 5 \\ \hline f & 2 & 4 & \colorbox{red}{5} & 3 & 6 & \colorbox{yellow}{10} & \colorbox{red}{5} & \colorbox{yellow}{10} & 11 \\ \hline \sigma (i) & 0 & 1 & \colorbox{red}{6} & 3 & 4 & \colorbox{yellow}{7} & \colorbox{red}{2} & \colorbox{yellow}{5} & 8 \\ \hline \end{array} $$
Again, the idea is that for wiring checks we choose a permutation $\sigma$ that shuffles the positions that must contain the same wire value. If the assignment is invariant under this permutation, then the values inside every cycle of $\sigma$ are equal, and the circuit trace is wired correctly.
Which permutations $\sigma$ can we choose?
The algebraic fact we rely on here is that a vector invariant under a permutation is constant on each cycle of that permutation, but not necessarily between different cycles.
Now, can we choose any permutation? That is not the case, let's have a look at a counterexample where we want to check that four values in a given vector equal each other.
$$ \begin{array}{|c|c|c|c| c|c|c| c|c|c|} \hline i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline \omega^i & 4^0 & 4^1 & 4^2 & 4^3 & 4^4 & 4^5 & 4^6 & 4^7 & 4^8 \\ \hline \omega^i & 1 & 4 & 16 & 7 & 9 & 17 & 11 & 6 & 5 \\ \hline f & 2 & 4 & 5 & 3 & 6 & 5 & 5 & 5 & 11 \\ \hline \end{array} $$
(in terms of correct computations of the circuit the above no longer makes sense, we are just reasoning about some polynomial here)
So we want to check if evaluations at positions $i \in \{2, 5, 6, 7\}$ are the same. Let's try to permute it as $\{6, 7, 2, 5\}$.
$$ \begin{array}{|c|c|c|c| c|c|c| c|c|c|} \hline i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline \omega^i & 4^0 & 4^1 & 4^2 & 4^3 & 4^4 & 4^5 & 4^6 & 4^7 & 4^8 \\ \hline \omega^i & 1 & 4 & 16 & 7 & 9 & 17 & 11 & 6 & 5 \\ \hline f & 2 & 4 & 5 & 3 & 6 & 5 & 5 & 5 & 11 \\ \hline \sigma (i) & 0 & 1 & \colorbox{red}{6} & 3 & 4 & \colorbox{red}{7} & \colorbox{red}{2} & \colorbox{red}{5} & 8 \\ \hline \end{array} $$
good, now let's add a function $f'$ that has completely different values in the same cells and let's add functions $g,g'$ permuting the evaluations $f,f'$ accordingly.
$$ \begin{array}{|c|c|c|c| c|c|c| c|c|c|} \hline i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline \omega^i & 4^0 & 4^1 & 4^2 & 4^3 & 4^4 & 4^5 & 4^6 & 4^7 & 4^8 \\ \hline \omega^i & 1 & 4 & 16 & 7 & 9 & 17 & 11 & 6 & 5 \\ \hline f & 2 & 4 & 5 & 3 & 6 & 5 & 5 & 5 & 11 \\ \hline f' & 2 & 4 & 1 & 3 & 6 & 2 & 3 & 4 & 11 \\ \hline \sigma (i) & 0 & 1 & \colorbox{red}{6} & 3 & 4 & \colorbox{green}{7} & \colorbox{blue}{2} & \colorbox{yellow}{5} & 8 \\ \hline g & 2 & 4 & \colorbox{blue}{5} & 3 & 6 & \colorbox{yellow}{5} & \colorbox{red}{5} & \colorbox{green}{5} & 11 \\ \hline g' & 2 & 4 & \colorbox{blue}{3} & 3 & 6 & \colorbox{yellow}{4} & \colorbox{red}{1} & \colorbox{green}{2} & 11 \\ \hline \end{array} $$
On these examples we see that $g = \sigma(f)$ and $g' = \sigma(f')$, even though $f'$ is not invariant under $\sigma$. But what if we tried to construct a malicious $m$ s.t. it would have non-matching values in positions $\{2,5,6,7\}$ and yet on permutation $m' = \sigma(m)$?
$$ \begin{array}{|c|c|c|c| c|c|c| c|c|c|} \hline i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline \omega^i & 4^0 & 4^1 & 4^2 & 4^3 & 4^4 & 4^5 & 4^6 & 4^7 & 4^8 \\ \hline \omega^i & 1 & 4 & 16 & 7 & 9 & 17 & 11 & 6 & 5 \\ \hline \sigma (i) & 0 & 1 & \colorbox{red}{6} & 3 & 4 & \colorbox{green}{7} & \colorbox{blue}{2} & \colorbox{yellow}{5} & 8 \\ \hline m & 2 & 4 & \colorbox{red}{15} & 3 & 6 & \colorbox{green}{16} & \colorbox{blue}{15} & \colorbox{yellow}{16} & 11 \\ \hline m' & 2 & 4 & \colorbox{blue}{15} & 3 & 6 & \colorbox{yellow}{16} & \colorbox{red}{15} & \colorbox{green}{16} & 11 \\ \hline \end{array} $$
This happens because the permutation we have chosen does not contain one cycle going through the whole value block, instead the chosen $\sigma$ decomposes into two cycles: $(2, 6), (5, 7)$ and so our malicious assignment is invariant under the chosen $\sigma$.
However, if $\sigma$ was chosen to contain one cycle through the whole block, that wouldn't be the problem. For example a following cycle $(2 ~ 5 ~ 6 ~ 7)$. For more info about cyclic permutations, there is this article
Why does the protocol work and what are those $\beta$ and $\gamma$ for?
For the full intuition why those shifts are needed I would refer the reader to this hackmd, here I will just briefly reiterate over the idea of a grand product.
Imagine we have two sets of numbers
$$ \begin{cases} a = (a_1, ..., a_n) \\ b = (b_1, ..., b_n) \end{cases} $$
and we want to check if these two sets contain the same elements, possibly in different orders. Certainly we do not want to do an honest element-by-element check.
The first idea could be to just check of the product of the elements match:
$$ \prod_{i\in [n]} a_i \stackrel{?}{=} \prod_{i\in [n]} b_i, $$
That would successfully prove that $a = (1, 1, 2, 3)$ equals the set $b = (3, 2, 1, 1)$ and not equal to $c = (1, 1, 2, 4)$. However, it will also prove that $a = (1, 1, 2, 3)$ equals to $m = (1, 1, 1, 6)$.
But if we were to add a random shift to each value the check would work:
$$ \prod_{i\in [n]} (a_i+\gamma) \stackrel{?}{=} \prod_{i\in [n]} (b_i+\gamma) $$
Why exactly is that the case? If we viewed the following as a polynomial over $X$:
$$ P(X) = \prod_{i\in [n]} (a_i+ X) - \prod_{i\in [n]} (b_i+ X) $$
then if at a random point $X = \gamma$ this polynomial is zero, by the Schwartz-Zippel Lemma either the polynomial is zero everywhere, or we hit one of its few roots by chance. So with high probability the sets match.
Ok, so this is what a random $\gamma$ is for. But what is random $\beta$ for? So, $\gamma$ lets us just say that "these multisets are the same", but we still need to prove a sort of per-element equation in the structure of $g = \sigma(f)$.
For example, take the following evaluations of $f$ and $g$, and let $\sigma$ swap $0$ and $1$:
$$ \begin{array}{|c|c|c|} \hline i & 0 & 1 \\ \hline \omega^i & \omega^0 & \omega^1 \\ \hline f & 10 & 20 \\ \hline g & 10 & 20 \\ \hline \sigma(i) & 1 & 0 \\ \hline \end{array} $$
As multisets, $f$ and $g$ are equal, so checking only
$$ \prod_{i \in [n]} (f_i + \gamma) \stackrel{?}{=} \prod_{i \in [n]} (g_i + \gamma) $$
would pass. But this is not enough to prove $g = \sigma(f)$, because $\sigma(f) = (20, 10)$. What $\beta$ does is bind every value to its position. Instead of comparing just values, we compare value-label pairs compressed into one field element:
$$ \begin{array}{|c|c|c|} \hline i & 0 & 1 \\ \hline f_i + \beta \cdot i + \gamma & 10 + \gamma & 20 + \beta + \gamma \\ \hline g_i + \beta \cdot \sigma(i) + \gamma & 10 + \beta + \gamma & 20 + \gamma \\ \hline \end{array} $$
$$ \prod_{i \in [n]} (f_i + \beta \cdot i + \gamma) \stackrel{?}{=} \prod_{i \in [n]} (g_i + \beta \cdot \sigma(i) + \gamma). $$
In this example these products are not equal as polynomials in $\beta$ and $\gamma$, unless the values actually agree with the chosen permutation.
The rest of the paper
The rest of the paper introduces a general case for checking a permutation "across" the values of several polynomials $f_1,...,f_k \in \mathbb{F}_{<d}[X]$.
It is basically a generalization of the ideas above that we need to check permutations over all of the three columns of gate evaluations within the execution trace. Later, when this is encoded in the PLONK protocol, the paper also moves from the $H$ multiplicative subgroup of $\mathbb{F}$ to a union of cosets. And then in next parts (6 and 7) the constraint systems and the whole protocol are formally described. However, for today I would want to make a stop here since my main goal was to explain the logic behind the permutation checks as arguably this is the least approachable part of the paper. Hope this is helpful to anyone and have a great day!