$$$$

PLONK Arithmetization

PLONK v.s. Halo

Similarities: proofs systems, use polynomial commitment schemes, same constraint system (constraint polynomial, BG12 permutations, lookup tables, custom gates)

Differences: PLONK requires a trusted-setup, PLONK uses pairings, Halo has proof recursion (2-cycle of elliptic curve groups), PLONK uses a Kate-like PCS, Halo uses a Hyrax-like PCS

Timeline:

[Standard] PLONK (Aug-2019) - proof system via polynomial commitments using a single updateable trusted-setup. Uses pairings, a non-R1CS constraint-system, BG12 permutation proofs, and Kate-like polynomial commitments.

Halo (Sep-2019) - proof recursion via elliptic curve cycles, no pairings, no trusted setup, Hyrax-like PCS.

TurboPLONK (late-2019/early-2020) - PLONK with custom gates/constraints.

plookup (Nov-2020) - extends PLONK with lookup tables (replace expensive computations with key-value maps to lookup a computation's output on an input, currently lookup tables focus on replacing bitwise operations such as bitwise AND and XOR).

UltraPLONK (late-2020) - PLONK with custom gates and lookup tables, i.e. combines TurboPLONK and plookup (makes many algorithms that are SNARK unfriendly, more friendly). Side note: using lookup tables and custom gates allows for efficient modular arithmetic in a field smaller than the PLONK field, which could allow for recursive proofs without cycles of elliptic curves (i.e. multiple base and scalar fields). Side note #2: Pedersen hashing within UltraPLONK is roughly as efficient as Poseidon.

Halo2 (late-2020) - combines UltraPLONK, a PCS that does not require a trusted-setup, and cycles of elliptic curves for recursion.

Question: Verification time is constant in PLONK, but is not in Halo/Halo2 because Halo's proof size varies with computation size? Zcash will rely on batch transaction verification to achieve something close to succinctness.

Standard PLONK Arithmetization

Arithmetization - breaks a general computation into a sequence of steps.

Example:

$a\ast b+23==100$:

Arithmetization converts a general computation into a system of polynomials (a set of interdependent polynomials) where each is constrained to a value. A general computation's set of polynomials is its constraint system. Every polynomial is of the same form.

Standard PLONK uses the constraint polynomial:

$$s_l{x}_l+s_r{x}_r+s_m{x}_l{x}_r=s_o{x}_o+c$$

• $s_l,s_r,s_o,s_m\in \{0,1\}$ are boolean selectors
• $x_l,x_r,x_o\in \mathbb{F}$ are values used in arithmetic
• $c\in \mathbb{F}$ is an optional constant used to assign constraint system values to a constant (public input)

which can encode addition, multiplication, and constant assignment.

		Constraint
Addition	$l+r=o$	$1x_l+1x_r+0x_l{x}_r=1x_o+0$
Multiplication	$l\ast r=o$	$0x_l+0x_r+1x_l{x}_r=1x_o+0$
Assign Constant (Public Input)	$l=5$ $r=5$ $l+r=5$ $l\ast r=5$	$1x_l+0x_0+0x_l{x}_r=0x_o+5$ $0x_l+1x_r+0x_l{x}_r=0x_o+5$ $1x_l+1x_r+0x_l{x}_r=0x_0+5$ $0x_l+0x_r+1x_l{x}_r=0x_o+5$
Exponentiation	$(l\ast r)\ast r=o$	$$\begin{array}{rl}\text{(0)}& 0x_l+0x_r+1x_l{x}_r=1x_o\\ \text{(1)}& 0x_l+0x_r+1x_o^{(0)}{x}_r=1x_o\end{array}$$

Note: a constraint may reference a value from another constraint, e.g. exponentiation. This is enforced via a permutation argument, not using constraint.

TODO: The

$s_l,s_r,s_o,s_m,c$ values define a computation. The

$x_l,x_r,x_o$ values are filled in by someone who knows how the computation proceeds (the inputs and outputs at each gate).

We can think of a computation's constraint system as a matrix:

${\mathit{x}}_{\mathit{l}}$	${\mathit{x}}_{\mathit{r}}$	${\mathit{x}}_{\mathit{o}}$	${\mathit{s}}_{\mathit{l}}$	${\mathit{s}}_{\mathit{r}}$	${\mathit{s}}_{\mathit{m}}$	${\mathit{s}}_{\mathit{o}}$	$\mathit{c}$
$x_l^{(1)}$	$x_r^{(1)}$	$x_o^{(1)}$	$s_l^{(1)}$	$x_r^{(1)}$	$s_m^{(1)}$	$s_o^{(1)}$	$c^{(1)}$
$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$
$x_l^{(n)}$	$x_r^{(n)}$	$x_o^{(n)}$	$s_l^{(n)}$	$x_r^{(n)}$	$s_m^{(n)}$	$s_o^{(n)}$	$c^{(n)}$

where the prover fills in the columns

${\mathit{x}}_{\mathit{l}}$,

${\mathit{x}}_{\mathit{r}}$, and

${\mathit{x}}_{\mathit{o}}$ with values (the witnesses) such that every constraint is satisfied.

Example:

$a\ast b+23==100$ (cont.)

The

$s$'s and equality constraints define a computation, the

$c$'s give an instance of the computation; the prover fills in

$x$ values to show that they know how a computation proceeds.

	${\mathit{x}}_{\mathit{l}}$	${\mathit{x}}_{\mathit{r}}$	${\mathit{x}}_{\mathit{o}}$	${\mathit{s}}_{\mathit{l}}$	${\mathit{s}}_{\mathit{r}}$	${\mathit{s}}_{\mathit{m}}$	${\mathit{s}}_{\mathit{o}}$	$\mathit{c}$
$a\ast b=c$	$x_l^{(1)}$	$x_r^{(1)}$	$x_o^{(1)}$	$0$	$0$	$1$	$1$	$0$
$d=23$	$x_l^{(2)}$	$x_r^{(2)}$	$x_o^{(2)}$	$1$	$0$	$0$	$0$	$23$
$c+d=e$	$x_l^{(3)}$	$x_r^{(3)}$	$x_o^{(3)}$	$1$	$1$	$0$	$1$	$0$
$f=100$	$x_l^{(4)}$	$x_r^{(4)}$	$x_o^{(4)}$	$1$	$0$	$0$	$0$	$100$

$$\begin{gathered} \mathbf{\text{Equality Constraints:}} \\ {x}_o^{(1)}=x_l^{(3)} \\ {x}_l^{(1)}=x_r^{(3)} \\ {x}_o^{(3)}=x_o^{(4)} \end{gathered}$$

Compressing Constraint Checks

We would like to replace

$n$ constraint checks (i.e.

$\mathrm{\forall }i\in [n]$ is the

$i^{th}$ constraint satisfied?) with a single check of some form. We do this by transforming the constraint system into a polynomial expression that is true if and only if the constraint system is satisfied.

Lagrange Interpolation

Lagrange interpolation converts a function's evaluation form

$\{(x_1,y_1),\dots ,(x_n,y_n)\}$ into a passing through each point.

Lagrange interpolation is used to represent each column as a polynomial:

$x_l(X),x_r(X),x_o(X),s_l(X),s_r(X),s_m(X),s_o(X),c(X)$, where each column's polynomial on the

$i^{th}$ input outputs the column's value in row

$i$.

We associate each matrix row

$i\in [n]$ with a unique value

${\omega }^i$ where the set of values associated with all rows is

$\mathbb{H}=\{{\omega }^1,\dots ,{\omega }^n\}$. Zipping this set of inputs with a column

$\mathsf{\text{zip}}(\mathbb{H},\mathbf{\text{column}})=\{({\omega }^1,a_1),\dots ,({\omega }^n,a_n)\}$ gives the evaluation form for a polynomial that outputs the

$i^{th}$ column value on row

$i$'s input

${\omega }^i$. Performing Lagrange interpolation on each column's evaluation form produces the polynomial that maps each row's input

${\omega }^i$ to the value in the column at that row

$a_i$. For example, to interpolate column

${\mathit{x}}_{\mathit{l}}$ as

$x_l(X)$ we use the evaluation form

$\{({\omega }^1,x_l^{(1)}),\dots ,({\omega }^n,x_l^{(1)})\}$.

$\mathbb{H}$	${\mathit{x}}_{\mathit{l}}$	${\mathit{x}}_{\mathit{r}}$	${\mathit{x}}_{\mathit{o}}$	${\mathit{s}}_{\mathit{l}}$	${\mathit{s}}_{\mathit{r}}$	${\mathit{s}}_{\mathit{m}}$	${\mathit{s}}_{\mathit{o}}$	$\mathit{c}$
${\omega }^1$	$x_l^{(1)}$	$x_r^{(1)}$	$x_o^{(1)}$	$s_l^{(1)}$	$x_r^{(1)}$	$s_m^{(1)}$	$s_o^{(1)}$	$c^{(1)}$
$⋮$
${\omega }^n$	$x_l^{(n)}$	$x_r^{(n)}$	$x_o^{(n)}$	$s_l^{(n)}$	$x_r^{(n)}$	$s_m^{(n)}$	$s_o^{(n)}$	$c^{(n)}$

Rewriting Constraint Checks as a Polynomial Expression

Given the set of interpolating polynomials, we use the constraint equation to write an expression that holds for every input

${\omega }^i\in \mathbb{H}$:

$$s_l({\omega }^i)x_l({\omega }^i)+s_l({\omega }^i)x_l({\omega }^i)+s_m({\omega }^i)x_l({\omega }^i)x_r({\omega }^i)=s_o({\omega }^i)x_o({\omega }^i)+c({\omega }^i)$$ moving the right hand side to the left, we rewrite the above as:

$$s_l({\omega }^i)x_l({\omega }^i)+s_l({\omega }^i)x_l({\omega }^i)+s_m({\omega }^i)x_l({\omega }^i)x_r({\omega }^i)-s_o({\omega }^i)x_o({\omega }^i)-c({\omega }^i)=0.$$ We can write the left hand side of the above equation as a polynomial:

$$s_l(X)x_l(X)+s_l(X)x_l(X)+s_m(X)x_l(X)x_r(X)-s_o(X)x_o(X)-c(X)$$ which that outputs

$0$ on every input

${\omega }^i$, i.e. has roots

${\omega }^1,\dots ,{\omega }^n$. We know some of the polynomial's roots, therefore we know part of its linear factorization contains the degree-1 terms

$(X-{\omega }^1)\dots (X-{\omega }^n)$:

$$s_l(X)x_l(X)+s_l(X)x_l(X)+s_m(X)x_l(X)x_r(X)-s_o(X)x_o(X)-c(X)=(X-{\omega }^1)\dots (X-{\omega }^n)h(X).\phantom{}$$ We call

$(X-{\omega }^1)\dots (X-{\omega }^n)$ the vanishing polynomial

$V(X)$ which outputs

$0$ on every input

${\omega }^i$:

$$V(X)=\prod _{i\in [n]}(X-{\omega }^i)$$ which in a cyclic multiplicative group of order

$n$ simplifies to:

$$\begin{array}{rl}V(X)& =X^n-1\\ \\ V({\omega }^i)& =({\omega }^i{)}^n-1\\ & ={\omega }^{in\text{ mod }n}-1\\ & ={\omega }^0-1\\ & =1-1\\ & =0\end{array}$$ and

$h(X)$ its cofactor polynomial. Thus, we can write the constraint system polynomial as as equality:

$$s_l(X)x_l(X)+s_l(X)x_l(X)+s_m(X)x_l(X)x_r(X)-s_o(X)x_o(X)-c(X)=V(X)h(X).\phantom{}$$

The constraint system is satisfied if its polynomial representation

$s_l(X)x_l(X)+\cdots -c(X)$ is divisible by

$V(X)$ without remainder.

$$V(X)|s_l(X)x_l(X)+s_l(X)x_l(X)+s_m(X)x_l(X)x_r(X)-s_o(X)x_o(X)-c(X)$$ Thus we can perform

$n$ constraint checks using a single polynomial division check.

Permutation Notation

A permutation

$\sigma$ that shuffles an array of

$n$ elements

$\sigma ((a_1,\dots ,a_n))=(b_1,\dots ,b_n)$ can be written:

$$\sigma =({\sigma }_1,\dots ,{\sigma }_n)$$ where

${\sigma }_1=2$ means that

$a_2\mapsto b_1$.

Equality Constraints

The polynomial division check ensures that the prover knows satisfying inputs and outputs for each gate, but does not ensure a correct wiring, e.g. the output of one gate is the input to another.

Example: I know

$(a,b)$ such that

$a+b=a\ast b$.

Applying the division check on the two gates proves that I know satisfying inputs and outputs for each gate in isolation, i.e. I know

$(a,b,c,d,e,f)$ such that

$a+b=e$ and

$c\ast d=f$:

adding copy constraints proves that the left inputs are equal, the right inputs are equal and the outputs are equal, i.e. I know

$(a,b)$ such that

$a+b=a\ast b$:

To prove equality of wires we apply a permutation check across the constraint system values

${\mathit{x}}_{\mathit{l}},{\mathit{x}}_{\mathit{r}},{\mathit{x}}_{\mathit{o}}$. We join each of the three columns into a single array of length

$3n$:

$$\mathit{u}={\mathit{x}}_{\mathit{l}}\parallel {\mathit{x}}_{\mathit{r}}\parallel {\mathit{x}}_{\mathit{o}}=(x_l^{(1)},\dots ,x_l^{(n)},x_r^{(1)},\dots ,x_r^{(n)},x_o^{(1)},\dots ,x_o^{(n)}).$$ and create a permutation

$\sigma \in S_{3n}$ that acts on

$\mathit{u}$ to produce an array

$\mathit{v}=\sigma (\mathit{u})=(u_{{\sigma }_1},\dots ,u_{{\sigma }_{3n}})$. We choose

$\sigma$ such that each subset of copied values forms a cycle, i.e. copied values are permuted with only their copies.

Side Note: permutation cycles

Given a permutation

$\sigma \in S_6$ where:

$$\sigma =\left[\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 2& 1& 4& 6& 5& 3\end{array}\right]$$ we can write

$\sigma$ in cycle notation:

$\sigma =(12)(346)(5)$ or simply

$(12)(346)$. An

$m$-cycle is a subset of

$m$ elements that repeat after

$m$ applications of

$\sigma$, e.g. the

$2$-cycle

$(12)$ maps

$1\to 2$ then

$2\to 1$.

Example: permutation of constraint system values

Given a constraint system of

$n=3$ constraints:

$$\begin{gathered} {\mathit{x}}_{\mathit{l}}=(x_l^{(1)},x_l^{(2)},x_l^{(3)}) \\ {\mathit{x}}_{\mathit{r}}=(x_r^{(1)},x_r^{(2)},x_r^{(3)}) \\ {\mathit{x}}_{\mathit{l}}=(x_o^{(1)},x_o^{(2)},x_o^{(3)}) \\ \begin{array}{rlllllllll}\mathit{u}={\mathit{x}}_{\mathit{l}}\parallel {\mathit{x}}_{\mathit{r}}\parallel {\mathit{x}}_{\mathit{l}}=(& x_l^{(1)},& x_l^{(2)},& x_l^{(3)},& x_r^{(1)},& x_r^{(2)},& x_r^{(3)},& x_o^{(1)},& x_o^{(2)},& x_o^{(3)})\\ & 1& 2& 3& 4& 5& 6& 7& 8& 9\end{array} \end{gathered}$$ and wiring:

$$\begin{array}{rl}& x_l^{(1)}=x_l^{(2)}\\ & x_o^{(1)}=x_r^{(2)}=x_l^{(3)}\end{array}$$ we create a permutation

$\sigma$, which operates on a set containing

$|\mathit{u}|=3n$ elements, such that each set of copied constraint system values forms a cycle:

$$\sigma =(x_l^{(1)}{x}_l^{(2)})(x_l^{(3)}{x}_r^{(2)}{x}_o^{(1)})$$ written in a less cumbersome way using indices in

$\mathit{u}$ as:

$$\sigma =(12)(357).$$ The permuted vector

$\mathit{v}=\sigma (\mathit{u})=(u_{{\sigma }_1},\dots ,u_{{\sigma }_{3n}})$ is:

$$\begin{array}{rlllllllll}\mathit{v}=(& x_l^{(2)},& x_l^{(1)},& x_o^{(1)},& x_r^{(1)},& x_l^{(3)},& x_r^{(3)},& x_r^{(2)},& x_o^{(2)},& x_o^{(3)})\\ & 2& 1& 7& 4& 3& 6& 5& 8& 9.\end{array}$$

The unpermuted array

$\mathit{u}$ is encoded into the polynomial:

$$u(X)=\prod _{i\in [3n]}(iX+u_i)$$ and the permuted array

$\mathit{v}$ is encoded into the polynomial:

$$v(X)=\prod _{i\in [3n]}({\sigma }_{i}X+v_i).$$ where

${\sigma }_i$ is the index in

$\mathit{u}$ that permutes into

$v_i$, i.e.

$v_i=u_{{\sigma }_i}$ and

$\mathit{v}=\sigma (\mathit{u})=(u_{{\sigma }_1},\dots ,u_{{\sigma }_{3n}})$. Also let

$u_i(X)$ and

$v_i(X)$ denote the

$i^{th}$ terms of

$u(X)$ and

$v(X)$ respectively:

$$\begin{array}{rl}{u}_i(X)& =(iX+u_i)\\ v_i(X)& =({\sigma }_{i}X+v_i).\end{array}$$

Notice that for each term

$v_i(X)$ in

$v(X)$ there is an identical term

$u_{{\sigma }_i}(X)$ in

$u(X)$, thus the polynomials

$u(X)$ and

$v(X)$ are the same, despite their

$i^{th}$ terms possibly being different:

$$\begin{array}{rl}{u}_i(X)& \ne v_i(X)\text{if }i\ne {\sigma }_i\\ u_{{\sigma }_i}(X)& =v_i(X)\\ \Rightarrow \prod _{i\in [3n]}{u}_i(X)& =\prod _{i\in [3n]}{v}_i(X)\end{array}$$ thus the following relation holds:

$$\frac{u(X)}{v(X)}=\prod _{i\in [3n]}\frac{(iX+u_i)}{({\sigma }_{i}X+v_i)}=\prod _{i\in [3n]}\frac{u_i(X)}{v_i(X)}=1.$$

This relation between a polynomial representing an array and a polynomial representing a permutation of the array can be tested using Schwartz-Zippel: given a random input

$\beta$ the probability the

$u(\beta )=v(\beta )$, or

$\frac{u(\beta )}{v(\beta )}=1$, is negligible.

Side Note: PLONK uses a slightly different relation.

PLONK actually defines

$u(X)=\prod _{i\in [3n]}(iX+u_i+\gamma )$ and

$v(X)=\prod _{i\in [3n]}({\sigma }_{i}X+v_i+\gamma )$ where the verifier chooses a random

$\gamma$ and sends it to the prover (which are equivalent via the right-shift Schwartz-Zippel lemma), thus in reality the above expression is:

$$\frac{u(X)}{v(X)}=\prod _{i\in [3n]}\frac{(iX+u_i+\gamma )}{({\sigma }_{i}X+v_i+\gamma )}=1.$$

Side Note: the trace of a running product.

The trace of a running product is an array

$\mathit{s}$ whose first element is

$1$ an contains the value of the product after each multiplicand, e.g.

$$\begin{gathered} \prod _{i\in [3]}{x}^i \\ \mathit{s}=(1,1\ast x^1,1\ast x\ast x^2,1\ast x\ast x^2\ast x^3) \end{gathered}$$

The verifier chooses a random

$\beta$ for the prover to evaluate

$\frac{u(\beta )}{v(\beta )}$ and the prover constructs a grand product array

$\mathit{s}=(s_1,\dots ,s_{3n})$ that represents

$\frac{u(\beta )}{v(\beta )}$, i.e.

$\mathit{s}$ is the trace of the product

$\frac{u(\beta )}{v(\beta )}$:

$$\begin{array}{rl}{s}_1& =1\\ s_2& =s_1\frac{u_1(\beta )}{v_1(\beta )}& =(1)\frac{u_1(\beta )}{v_1(\beta )}\\ s_3& =s_2\frac{u_2(\beta )}{v_2(\beta )}& =\left(1\frac{u_1(\beta )}{v_1(\beta )}\right)\frac{u_2(\beta )}{v_2(\beta )}\\ & ⋮\\ s_{3n}& =s_{3n-1}\frac{u_{3n-1}(\beta )}{v_{3n-1}(\beta )}& =(1\frac{u_1(\beta )}{v_1(\beta )}\dots \frac{u_{3n-2}(\beta )}{v_{3n-2}(\beta )})\frac{u_{3n-1}(\beta )}{v_{3n-1}(\beta )}\end{array}$$

$\mathit{s}$ is recursive in that its

$i^{th}$ element is equal to the previous element times

$\frac{u_{i-1}(\beta )}{v_{i-1}(\beta )}$:

$$s_i=s_{i-1}\frac{u_{i-1}(\beta )}{v_{i-1}(\beta )}\text{where: }i\in [2,3n].$$

Notice that the

$\frac{u(\beta )}{v(\beta )}$ can be computed from

$\mathit{s}$ by multiplying its last element by the last product term in

$\frac{u(\beta )}{v(\beta )}$:

$$\frac{u(\beta )}{v(\beta )}=\prod _{i\in [3n]}\frac{u_i(\beta )}{v_i(\beta )}=s_{3n}\frac{u_{3n}(\beta )}{v_{3n}(\beta )}=s_{3n+1}$$

The prover creates a polynomial

$s(X)$ using Lagrange interpolation on a publicly known set of

$3n$ inputs

$\mathbb{H}=⟨\omega ⟩=\{{\omega }^1,\dots ,{\omega }^{3n}\}\subset \mathbb{F}$ and image

$\mathit{s}$ such that:

$$\mathrm{\forall }i\in [3n]:s({\omega }^i)=s_i.$$ Notice that the following relation holds for a pair of neighboring inputs

${\omega }^i$ and

${\omega }^{i+1}$:

$$\begin{array}{rl}{s}_{i+1}& =s_i\frac{u_i(\beta )}{v_i(\beta )}\\ \Rightarrow s({\omega }^{i+1})& =s({\omega }^i)\frac{u_i(\beta )}{v_i(\beta )}& .\end{array}$$

Given

$s(X)$, the verifier wants to check that

$\mathit{v}$ is a permutation of

$\mathit{u}$ according to

$\sigma$. The verifier checks that the permutation identity holds at the last element in

$\mathit{s}$:

$$\begin{array}{rl}\frac{u(\beta )}{v(\beta )}& \stackrel{?}{=}1\\ \Rightarrow s({\omega }^{3n})\frac{u_{3n}(\beta )}{v_{3n}(\beta )}& \stackrel{?}{=}1\end{array}$$ and that

$\mathit{s}$ is a correctly constructed running product

$s_i=s_{i-1}\frac{u_{i-1}(\beta )}{v_{i-1}(\beta )}$:

$$\begin{array}{rll}s({\omega }^{3n})& \stackrel{?}{=}s({\omega }^{3n-1})\frac{u_{3n-1}(\beta )}{v_{3n-1}(\beta )}& \\ & ⋮\\ s({\omega }^2)& \stackrel{?}{=}s({\omega }^1)\frac{u_1(\beta )}{v_1(\beta )}& \\ s({\omega }^1)& \stackrel{?}{=}1& .\end{array}$$

If

$\frac{u(\beta )}{v(\beta )}=1$ at the random challenge

$\beta$ then

$u(X)=v(X)$, which implies

$\mathit{v}=\sigma (\mathit{u})$.

Proving Subarrays via Randomized Set Differences (Not Done)

Note: "ordered multiset" == "array"
Note: "subarray" == "order preserving subset of an array"

PLONK defines an ordered multiset's

$\mathit{a}=(a_1,\dots ,a_n)$ set difference

${\mathit{a}}^{\prime }$ as the difference between adjacent elements of

$\mathit{a}$:

$$\begin{array}{rlll}& {\mathit{a}}^{\prime }& =(a_{i+1}-a_i{)}_{i\in [n-1]}& \\ \\ \text{e.g. }& \mathit{a}& =(2,6,4)& \\ & {\mathit{a}}^{\prime }& =(6-2,4-6)=(4,-2)& .\end{array}$$

Given arrays

$\mathit{a}$ and

$\mathit{b}$, if

$\mathit{b}$ is a subarray of

$\mathit{a}$, then the set difference of

$\mathsf{\text{sorted}}(\mathit{a}\parallel \mathit{b})$ contains

$|\mathit{b}|$ number of zeros because each

$b_i$ is inserted next to an

$a_j$ having the same value:

$$\begin{array}{rlll}\text{e.g. }& \mathit{a}& =(1,3,4,7)& \\ & \mathit{b}& =(1,7)& \\ & \mathit{c}& =\mathsf{\text{sorted}}(\mathit{a}\parallel \mathit{b})=(1,1,3,4,7,7)& \\ & {\mathit{c}}^{\prime }& =(0,2,1,3,0)& \\ & {\mathit{c}}^{\prime }& \text{contains }|\mathit{b}|=2\text{ zeros}& .\end{array}$$ However, this alone does not prove that an array is a subarray of

$bolda$ because we can find an array

$\mathit{f}\not\subset \mathit{a}$ where the set difference of

$\mathsf{\text{sorted}}(\mathit{a}\parallel \mathit{f})$ contains

$|\mathit{f}|$ number of zeros:

$$\begin{array}{rlll}\text{e.g. }& \mathit{a}& =(1,1)& \\ & \mathit{f}& =(3,3)& \\ & \mathit{g}& =\mathsf{\text{sorted}}(\mathit{a}\parallel \mathit{f})=(1,1,3,3)\\ & {\mathit{g}}^{\prime }& =(0,0)\\ & {\mathit{g}}^{\prime }& \text{contains }|\mathit{f}|=2\text{ zeros}& .\end{array}$$

However, given a random value

$\gamma$, we can test (w.h.p.) that an array

$\mathit{b}$ is subarray of an array

$\mathit{a}$ by shifting all elements by

$\gamma$:

$$\begin{array}{rlll}\text{e.g. }& \mathit{a}+\gamma & =(a_1+\gamma ,\dots ,a_n+\gamma )& \\ & \mathit{b}+\gamma & =(b_1+\gamma ,\dots ,b_m+\gamma )& \\ & \mathit{c}& =\mathsf{\text{sorted}}(\mathit{a}\parallel \mathit{b})=(1,1,3,4,7,7)& \\ & {\mathit{c}}^{\prime }& =(0,2,1,3,0)& \\ & {\mathit{c}}^{\prime }& \text{contains }|\mathit{b}|=2\text{ zeros}& .\end{array}$$

Multiset Checks (Right-Shift Schwartz-Zippel)

Given two arrays

$\mathit{a}$ and

$\mathit{b}$ of equal length

$n$, if both

$\mathit{a}$ and

$\mathit{b}$ contain the same elements, regardless of their ordering, then the products of the arrays' elements will be equal:

$$\begin{array}{rll}\mathit{a}& =(x,y,z)& \\ \mathit{b}& =(x,z,y)=\sigma (\mathit{a})& \\ a_1{a}_2{a}_3& =b_1{b}_2{b}_3& .\end{array}$$ However, the products of two [equally lengthed] arrays' elements being equal does not guarantee that

$\mathit{a}$ and

$\mathit{b}$ contain the same elements, e.g.

$$\begin{array}{rl}\mathit{a}& =(x,y,z)\\ \mathit{b}& =(\frac{x}{2},\frac{z}{2},4y)\ne \sigma (\mathit{a})\\ \prod _{i\in [n]}{a}_i& =\prod _{i\in [n]}{b}_i.\end{array}$$ We can use a product equality check on the elements of two arrays to guarantee that the arrays contain the same elements by right-shifting every element of each array by a random value

$\gamma$:

$$\begin{gathered} \mathit{a}=(x,y,z) \\ \mathit{b}=(x,z,y) \\ (a_1+\gamma )(a_2+\gamma )(a_3+\gamma )=(b_1+\gamma )(b_2+\gamma )(b_3+\gamma ) \\ ⟹\mathit{b}=\sigma (\mathit{a}). \end{gathered}$$

Background

Linear Factors Contain Roots

A univariate polynomial

$f(X)$ having

$n$ roots

$\{a_1,\dots ,a_n\}$ can be written uniquely as

$n$ degree-

$1$ polynomials:

$$\begin{gathered} f(X)=c(X-a_1)\dots (X-a_n) \\ \text{roots}(f)=\{a_1,\dots ,a_n\} \end{gathered}$$ where

$c$ is a constant. If we don't care about the sign of the roots we can write:

$$\begin{gathered} f(X)=c(X+a_1)\dots (X+a_n) \\ \text{roots}(f)=\{-a_1,\dots ,-a_n\}. \end{gathered}$$

A polynomial that has a linear factor

$(iX-a)$ has a root at

$\frac{a}{i}$:

$$\begin{array}{rl}f(X)& =\prod _{i\in [n]}(iX-a_i)\\ & =c(X-\frac{a_1}{1})\dots (X-\frac{a_n}{n})\text{where: }c=1\ast \cdots \ast n\\ \text{roots}(f)& =\{\frac{a_1}{1},\dots ,\frac{a_n}{n}\}.\end{array}$$

Encoding Sets and Arrays into Polynomials

We can encode a set of values

$\{a_1,\dots ,a_n\}$ into a unique polynomial:

$$\begin{gathered} f(X)=\prod _{i\in [n]}(X-a_i) \\ \text{roots}(f)=\{a_1,\dots ,a_n\}. \end{gathered}$$

We can encode an array

$(a_1,\dots ,a_n)$ into a unique polynomial where each root encodes an array element and its position:

$$\begin{gathered} f(X)=\prod _{i\in [n]}(iX-a_i) \\ \text{roots}(f)=\{\frac{a_1}{1},\dots ,\frac{a_n}{n}\}. \end{gathered}$$

Side Note: if an array is a permutation of another, e.g.

$\mathit{a}=(a_1,\dots ,a_n)$ and

$\mathit{b}=(b_1,\dots ,b_n)=\sigma (\mathit{a})$ where

$\sigma =({\sigma }_1,\dots {\sigma }_n)$ is a permutation, then the following equality holds:

$$\prod _{i\in [n]}(iX-a_i)=\prod _{i\in [n]}({\sigma }_{i}X-b_i)$$ e.g.

$\mathit{a}=(5,6,7)$ and

$\mathit{b}=(6,7,5)=\sigma (\mathit{a})$:

$$\begin{gathered} \begin{array}{rll}{a}_1& \to b_3& ({\sigma }_3=1)\\ a_2& \to b_1& ({\sigma }_1=2)\\ a_3& \to b_2& ({\sigma }_2=3)\end{array} \\ \begin{array}{rl}\prod _{i\in [n]}(iX-a_i)& =\prod _{i\in [n]}({\sigma }_{i}X-b_i)\\ (1X-a_1)(2X-a_2)(3X-a_3)& =({\sigma }_{1}X-b_1)({\sigma }_{2}X-b_2)({\sigma }_{3}X-b_3)\\ (1X-5)(2X-6)(3X-7)& =(2X-6)(3X-7)(1X-5)\end{array} \end{gathered}$$

Schwartz-Zippel

Given two univariate polynomials:

$$\begin{gathered} f(X)=(X+a_1)\dots (X+a_n) \\ g(X)=(X+b_1)\dots (X+b_n) \end{gathered}$$ Schwartz-Zippel says that for a random input

$\gamma \leftarrow \mathbb{F}$ the probability that different polynomials

$f(X)\ne g(X)$ evaluate to the same value

$f(\gamma )=g(\gamma )$ is very low.

$$Pr[f(\gamma )=g(\gamma )\mid f(X)\ne g(X)]\le \frac{max(d_f,d_g)}{|\mathbb{F}|}$$

This allows us to test polynomial equivalency, i.e. is

$f(X)$ the same polynomial as

$g(X)$.

Schwartz-Zippel holds if every root of

$f(X)$ and

$g(X)$ is shifted by the a randomly chosen constant

$\delta \leftarrow \mathbb{F}$:

$$\begin{gathered} f(X)=(X+a_1+\delta )\dots (X+a_n+\delta ) \\ g(X)=(X+b_1+\delta )\dots (X+b_n+\delta ) \\ Pr[f(\gamma )=g(\gamma )\mid f(X)\ne g(X)]\le \frac{max(d_f,d_g)}{|\mathbb{F}|} \end{gathered}$$ because shifting two polynomials by the same value along the x-axis does not affect their equality.

We can encode the elements of a set

$\{a_1,\dots ,a_n\}$ into a polynomial

$f(X)=(X-a_1)\dots (X-a_n)$ and the set

$\{a_1,\dots ,a_n\}$ into a polynomial

$g(X)=(X-b_1)\dots (X-b_n)$ and use Schwartz-Zippel to test set equality (i.e. do sets

$\{a_1,\dots ,a_n\}$ and

$\{b_1,\dots ,b_n\}$ contain the same elements).

We can encode an array

$(a_1,\dots ,a_n)$ as a polynomial whose roots contains the array elements and their positions:

$$\begin{gathered} f(X)=(1X-a_1)\dots (nX-a_n) \\ \text{roots}(f)=\{\frac{a_1}{1},\dots ,\frac{a_n}{n}\} \end{gathered}$$ thus, we can use Schwartz-Zippel to test array equality (i.e.

$\mathrm{\forall }i\in [n]:a_i=b_i$).

PLONK uses Schwartz-Zippel (on random input

$\lambda \leftarrow \mathbb{F}$) with a random right-shift

$\delta \leftarrow \mathbb{F}$ to check array equality:

$$\begin{gathered} f(X)=(1X-a_1+\delta )\dots (nX-a_n+\delta ) \\ g(X)=(1X-b_1+\delta )\dots (nX-b_n+\delta ) \\ Pr[f(\lambda )=g(\lambda )\mid f(X)\ne g(X)]\le \frac{max(d_f,d_g)}{|\mathbb{F}|}. \end{gathered}$$

Multivariate Variant

The Schwartz-Zippel probability is the same for an

$n$-variate polynomial

$f(X_1,\dots ,X_n)$ and a randomly selected evaluation point

$(x_1,\dots ,x_n)\leftarrow {\mathbb{F}}^n$

$$Pr[f(x_1,\dots ,x_n)=0]\le \frac{d}{|\mathbb{F}|}.$$

Zero-Polynomial Variant

Given a random evaluation point such that

$f(x_1,\dots ,x_n)=0$, the probability that

$f(X_1,\dots ,X_n)$ is the zero-polynomial (always a zero-function) is the converse of the Schwartz-Zippel probability

$$Pr[f(X_1,\dots ,X_n)\text{ is the zero-polynomial}]=1-Pr[f(x_1,\dots ,x_n)=0].$$

Low-Degree Extension

Given an array

$\mathit{a}=(a_1,\dots ,a_n)\in {\mathbb{F}}^n$ and a subset

$S=\{s_1,\dots ,s_n\}\subset \mathbb{F}$, then the low-degree extension of

$\mathit{a}$ is the interpolation polynomial

$a(X)$ of degree

$d=n-1$ that passes through the points

$\{(s_1,a_1),\dots ,(s_n,a_n)\}$:

$$\mathrm{\forall }i\in [n]:a(s_i)=a_i.$$

Cosets (todo)

We associate each value in the constraint system with a unique value in

$\mathbb{F}$:

$$\begin{array}{rll}{\mathit{x}}_{\mathit{l}}& \to {\mathbb{H}}_1& \mathrm{\forall }i\in [n]:x_l^{(i)}\to {\omega }^i\\ {\mathit{x}}_{\mathit{r}}& \to {\mathbb{H}}_2& \mathrm{\forall }i\in [n]:x_r^{(i)}\to 2{\omega }^i\\ {\mathit{x}}_{\mathit{o}}& \to {\mathbb{H}}_3& \mathrm{\forall }i\in [n]:x_o^{(i)}\to 3{\omega }^i\end{array}$$ where

${\mathbb{H}}_1,{\mathbb{H}}_2,{\mathbb{H}}_3<\mathbb{F}$ are disjoint subgroups and

${\omega }^i\in \mathbb{H}$, . We then join the labels into an array of length

$3n$:

$$\mathit{u}=({\omega }^1,\dots ,{\omega }^n,2{\omega }^1,\dots ,2{\omega }^n,3{\omega }^1,\dots ,3{\omega }^n)$$