Disclaimer: This write up introduces some basic tricks and definitions that one will bump into while trying to learn Plonk. This article is neither precise nor exhaustive. Its objective is to provide some intuition for those jumping onto Plonk and some fun for those who love math.

Is it an ELI5 article?

Lagrange interpolation

• The idea of Lagrange interpolation is that, taking a number of points, one can reconstruct the polynomial passing through all of these points. In particular, first we construct a polynomial for each point that (i) passes through that point and (ii) equals zero in all other points. We then sum up all of the polynomials.

• To describe what exactly we are talking about… Let $F$ be a field and $H$ be a subgroup of $F$ of order $n$. Lagrange polynomial $L_x$ is a polynomial of degree $n-1$ that vanishes (equals zero) in all points of $H$ except for $x$ and at point $x$, $L_x(x)=1$. As this polynomial vanishes in all points except for $x$, it has a very sparse representation: $L_X(X)=(c_x(X_n-1))/(X-x)$ where $c_x$ is some constant. This sparsity allows Verifier to compute Lagrange polynomials on its own (i.e. it’s not too heavy).

Permutation check

• Permutation check allows us to check that two sets contain the same elements regardless of their order. The idea of this check is to multiply all elements (1) in the initial order and (2) after the permutation, introducing randomness, and ensure that the results are equal.

Cosets

• Cosets are used to decompose the underlying set into disjoint subsets of equal size. The initial set equals the sum of all cosets. In the diagram below, $S$ is the underlying cosets and $S_0$, $S_1$, $S_2$, $S_3$, $S_4$, $S_5$ are the cosets of equal size such as $S_0+ S_1+ S_2+ S_3+ S_4+ S_5=S$.

Quotient polynomial

To explain what a quotient polynomial is, let’s represent $p(x)$ as $p(x)=s(x)q(x)+r(x)$. Then we say that $q(x)$ is the quotient polynomial of $p(x)$ and $s(x)$, while $r(x)$ is the reminder. Using quotient polynomials, one can check in a simple way if $x=x_0$ is a root of a specific polynomial. Following the notations we introduced above, if $x=x_0$ is really a root of $y=p(x)$, then $p(x)-y$ can be divided by $(x-x_0)$ and as a result we will get another polynomial $q(x)$.

n-th roots of unity

An $n$-th root of unity is a complex number such that when raised to some positive integer power $n$ equals one: $⍵^n=1$. $n$-th roots of unity is defined as a set of all such numbers: $Ω_n=\{⍵∈C|⍵^n=1\}$ where $C$ is the set of complex numbers. A complex number is defined as $⍵=a+ib$ such that $a,b∈R$, $i^2=-1$ where $a$ refers to the real number part and $b$ to the imaginary part. $⍵^n=1$ can be represented as a unit circuit:

• A set of complex numbers includes all numbers of such form: $C=\{⍵=a+ib, a,b∈R, i^2=-1\}$.

• Roots of unity are often used to construct cosets because they are conveniently decomposable into cosets.

Polynomial commitment

• Polynomial commitment allows a committer to commit to a polynomial with a short string that can be used by a verifier to confirm claimed evaluations of the committed polynomial.

• There are different types of polynomial commitments, but in the context of Plonk-ish arithmetization, we are especially interested in the KZG commitment (pairing-based). A nice property of KZG is that it is additively homomorphic. That is, if $[f]$ is the commitment of $f(x)$ and $[g]$ is the commitment of $g(x)$, then $[f+g]$ if the commitment of $f(x)+g(x)$.

Circuit

• When we are talking about Plonk, most of the time we are talking about polynomials. However, when it comes to a circuit, we have a table of wires and selectors that one can think about as the following:

where $w$ stands for “wire” and $q$ stands for “selector.” The depth of the table equals the number of gates $n$.

For those feeling like ready to go one level deeper – check the book “Programmable Cryptography” by 0xPARC. Chapters on snark (Plonk) are absolutely awesome.