$$
\def\Zp{{\mathbb{Z}_p}}
\def\F{{\mathbb{F}}}
\def\Bit{{\{0, 1\}}}
\def\PI{{\textsf{PI}}}
\def\bold#1{\boldsymbol{#1}}
\def\stop{{\rlap{\quad.}\hphantom{}}}
\def\qed{{\rlap{\quad \tiny\blacksquare}\hphantom{}}}
\def\par{{\thinspace {\parallel} \thinspace}}
\def\hso{{\hspace{1pt}}}
$$

# 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 * 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_lx_l + s_rx_r + s_mx_lx_r = s_ox_o + c
$$
* $s_l, s_r, s_o, s_m \in \Bit$ are boolean **selectors**
* $x_l, x_r, x_o \in \F$ are values used in arithmetic
* $c \in \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_lx_r = 1x_o + 0$ |
| Multiplication | $l * r = o$ | $0x_l + 0x_r + 1x_lx_r = 1x_o + 0$ |
| Assign Constant <br> (Public Input) | $l = 5$ <br> $r = 5$ <br> $l + r = 5$ <br> $l * r = 5$ | $1x_l + 0x_0 + 0x_lx_r = 0x_o + 5$ <br> $0x_l + 1x_r + 0x_lx_r = 0x_o + 5$ <br> $1x_l + 1x_r + 0x_lx_r = 0x_0 + 5$ <br> $0x_l + 0x_r + 1x_lx_r = 0x_o + 5$ |
| Exponentiation | $(l * r) * r = o$ | $$\eqalign{{\small\text{(0)}} & \ \ 0x_l + 0x_r + 1x_lx_r = 1x_o \\ {\small \text{(1)}} & \ \ 0x_l + 0x_r + 1x_o^{(0)}x_r = 1x_o}$$ |


**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**:
| $\boldsymbol{x_l}$ | $\boldsymbol{x_r}$ | $\boldsymbol{x_o}$ | $\boldsymbol{s_l}$ | $\boldsymbol{s_r}$ | $\boldsymbol{s_m}$ | $\boldsymbol{s_o}$ | $\boldsymbol{c}$ |
| ------------------ | ------------------ | ------------------ | ------------------ | ------------------ | ------------------ | ------------------ | ---------------- |
| $x_l^{(1)}$ | $x_r^{(1)}$ | $x_o^{(1)}$ | $s_l^{(1)}$ | $x_r^{(1)}$ | $s_m^{(1)}$ | $s_o^{(1)}$ | $c^{(1)}$ |
| $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ |
| $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 $\boldsymbol{x_l}$, $\boldsymbol{x_r}$, and $\boldsymbol{x_o}$ with values (the **witnesses**) such that every constraint is satisfied.

<br>

**Example:** $a * 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.

| | $\boldsymbol{x_l}$ | $\boldsymbol{x_r}$ | $\boldsymbol{x_o}$ | $\boldsymbol{s_l}$ | $\boldsymbol{s_r}$ | $\boldsymbol{s_m}$ | $\boldsymbol{s_o}$ | $\boldsymbol{c}$ |
|-| ------------------ | ------------------ | ------------------ | ------------------ | ------------------ | ------------------ | ------------------ | ---------------- |
| $a * 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$ |

$$
\textbf{Equality Constraints:} \\
x_o^{(1)} = x_l^{(3)} \\
x_l^{(1)} = x_r^{(3)} \\
x_o^{(3)} = x_o^{(4)}
$$

## Compressing Constraint Checks

We would like to replace $n$ constraint checks (i.e. $\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 $\textsf{zip}(\mathbb{H}, \textbf{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 $\boldsymbol{x_l}$ as $x_l(X)$ we use the evaluation form $\{(\omega^1, x_l^{(1)}), \dots, (\omega^n, x_l^{(1)})\}$.

| $\mathbb{H}$ | $\boldsymbol{x_l}$ | $\boldsymbol{x_r}$ | $\boldsymbol{x_o}$ | $\boldsymbol{s_l}$ | $\boldsymbol{s_r}$ | $\boldsymbol{s_m}$ | $\boldsymbol{s_o}$ | $\boldsymbol{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)}$ |
|$\vdots$|
| $\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 \quad.
$$ 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) \stop
$$ 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:
$$
\eqalign{
V(X) &= X^n - 1 \\
~\\
V(\omega^i) &= (\omega^i)^n - 1 \\
&= \omega^{in \text{ mod } n} - 1 \\&
= \omega^0 - 1 \\
&= 1 - 1 \\
&= 0
}
$$ 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) \stop
$$

The constraint system is **satisfied** if its polynomial representation $s_l(X)x_l(X) + \dots - c(X)$ is divisible by $V(X)$ without remainder.
$$
V(X) \mathbin{\large|} 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.

<br>

**Example:** I know $(a, b)$ such that $a + b = a * 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 * 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 * b$:

<br>

To prove equality of wires we apply a **permutation check** across the constraint system values $\boldsymbol{x_l}, \boldsymbol{x_r}, \boldsymbol{x_o}$. We join each of the three columns into a single array of length $3n$:
$$
\boldsymbol{u} = \boldsymbol{x_l} \parallel \boldsymbol{x_r} \parallel \boldsymbol{x_o} = (x_l^{(1)}, \dots, x_l^{(n)}, x_r^{(1)}, \dots, x_r^{(n)}, x_o^{(1)}, \dots, x_o^{(n)}) \quad.
$$ and create a permutation $\sigma \in S_{3n}$ that acts on $\boldsymbol{u}$ to produce an array $\boldsymbol{v} = \sigma(\boldsymbol{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.

:::spoiler **Side Note:** permutation cycles
Given a permutation $\sigma \in S_6$ where:
$$
\sigma = \begin{bmatrix}
1 & 2 & 3 & 4 & 5 & 6 \\
2 & 1 & 4 & 6 & 5 & 3
\end{bmatrix}
$$ we can write $\sigma$ in **cycle notation**: $\sigma = (1 \ 2)(3 \ 4 \ 6)(5)$ or simply $(1 \ 2)(3 \ 4 \ 6)$. An $m$-cycle is a subset of $m$ elements that repeat after $m$ applications of $\sigma$, e.g. the $2$-cycle $(1 \ 2)$ maps $1 \rightarrow 2$ then $2 \rightarrow 1$.
:::

<br>

:::spoiler **Example:** permutation of constraint system values
Given a constraint system of $n = 3$ constraints:
$$
\boldsymbol{x_l} = (x_l^{(1)}, x_l^{(2)}, x_l^{(3)}) \\
\boldsymbol{x_r} = (x_r^{(1)}, x_r^{(2)}, x_r^{(3)}) \\
\boldsymbol{x_l} = (x_o^{(1)}, x_o^{(2)}, x_o^{(3)}) \\~\\
\eqalign{
\boldsymbol{u} = \boldsymbol{x_l} \parallel \boldsymbol{x_r} \parallel \boldsymbol{x_l} = \thinspace (&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
}
$$ and wiring:
$$
\eqalign{
& x_l^{(1)} = x_l^{(2)} \\
& x_o^{(1)} = x_r^{(2)} = x_l^{(3)}
}
$$ we create a permutation $\sigma$, which operates on a set containing $|\bold{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 $\boldsymbol{u}$ as:
$$
\sigma = (1 \ 2)(3 \ 5 \ 7) \quad.
$$ The permuted vector $\boldsymbol{v} = \sigma(\boldsymbol{u}) = (u_{\sigma_1}, \dots, u_{\sigma_{3n}})$ is:
$$
\eqalign{
\boldsymbol{v} = \thinspace (&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 \quad\quad.
}
$$ 
:::
<br>

The unpermuted array $\boldsymbol{u}$ is encoded into the polynomial:
$$
u(X) = \prod_{i \in [3n]} (iX + u_i)
$$ and the permuted array $\boldsymbol{v}$ is encoded into the polynomial:
$$
v(X) = \prod_{i \in [3n]} (\sigma_iX + v_i).
$$ where $\sigma_i$ is the index in $\boldsymbol{u}$ that permutes into $v_i$, i.e. $v_i = u_{\sigma_i}$ and $\bold{v} = \sigma(\bold{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:
$$
\eqalign{
u_i(X) &= (iX + u_i) \\
v_i(X) &= (\sigma_iX + v_i) \quad.
}
$$

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:
$$
\eqalign{
u_i(X) &\neq v_i(X) \quad\quad \text{if } i \neq \sigma_i \\
u_{\sigma_i}(X) &= v_i(X) \\
\Rightarrow \prod_{i \in [3n]} u_i(X) &= \prod_{i \in [3n]} v_i(X)
}
$$ thus the following relation holds:
$$
{u(X) \over v(X)} = \prod_{i \in [3n]} {(iX + u_i) \over (\sigma_iX + v_i)} = \prod_{i \in [3n]} {u_i(X) \over v_i(X)} = 1 \quad.
$$

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 ${u(\beta) \over v(\beta)} = 1$, is negligible.

<br/>

:::spoiler **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_iX + 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:
$$
{u(X) \over v(X)} = \prod_{i \in [3n]} {(iX + u_i + \gamma) \over (\sigma_iX + v_i + \gamma)} = 1 \quad.
$$
:::

<br/>

:::spoiler **Side Note:** the trace of a running product.
The trace of a running product is an array $\bold{s}$ whose first element is $1$ an contains the value of the product after each multiplicand, e.g.
$$
\prod_{i \in [3]} x^i \\
\bold{s} = (1, 1 {*} x^1, 1 {*} x {*} x^2, 1 {*} x {*} x^2 {*} x^3)
$$
:::

<br/>

The verifier chooses a random $\beta$ for the prover to evaluate ${u(\beta) \over v(\beta)}$ and the prover constructs a **grand product** array $\boldsymbol{s} = (s_1, \dots, s_{3n})$ that represents $u(\beta) \over v(\beta)$, i.e. $\bold{s}$ is the trace of the product $u(\beta) \over v(\beta)$:
$$
\eqalign{
s_1 &= 1 \\
s_2 &= s_1 {u_1(\beta) \over v_1(\beta)} &= (1) {u_1(\beta) \over v_1(\beta)} \\
s_3 &= s_2{u_2(\beta) \over v_2(\beta)} &= \left(1 {u_1(\beta) \over v_1(\beta)} \right) {u_2(\beta) \over v_2(\beta)} \\
& \vdots \\
s_{3n} &= s_{3n - 1} {u_{3n - 1}(\beta) \over v_{3n - 1}(\beta)} &= \left( 1 {u_1(\beta) \over v_1(\beta)} \dots {u_{3n - 2}(\beta) \over v_{3n - 2}(\beta)} \right) {u_{3n - 1}(\beta) \over v_{3n - 1}(\beta)}
}
$$

$\boldsymbol{s}$ is recursive in that its $i^{th}$ element is equal to the previous element times $u_{i - 1}(\beta) \over v_{i - 1}(\beta)$:
$$
s_i = s_{i - 1} {u_{i - 1}(\beta) \over v_{i - 1}(\beta)} \quad\quad \text{where: } i \in [2, 3n] \quad.
$$

Notice that the $u(\beta) \over v(\beta)$ can be computed from $\bold{s}$ by multiplying its last element by the last product term in $u(\beta) \over v(\beta)$:
$$
{u(\beta) \over v(\beta)} = \prod_{i \in [3n]} {u_i(\beta) \over v_i(\beta)} = s_{3n} {u_{3n}(\beta) \over 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} = \langle \omega \rangle = \{\omega^1, \dots, \omega^{3n}\} \subset \F$ and image $\bold{s}$ such that:
$$
\forall i \in [3n]: s(\omega^i) = s_i \quad.
$$ Notice that the following relation holds for a pair of **neighboring inputs** $\omega^i$ and $\omega^{i + 1}$:
$$
\eqalign{
s_{i + 1} & = s_i {u_i(\beta) \over v_i(\beta)} \\
\Rightarrow s(\omega^{i + 1}) & = s(\omega^i) {u_i(\beta) \over v_i(\beta)} & \quad.
}
$$

Given $s(X)$, the verifier wants to check that $\boldsymbol{v}$ is a permutation of $\boldsymbol{u}$ according to $\sigma$. The verifier checks that the permutation identity holds at the last element in $\boldsymbol{s}$:
$$
\eqalign{
{u(\beta) \over v(\beta)} & \overset{?}= 1 \\
\Rightarrow s(\omega^{3n}) {u_{3n}(\beta) \over v_{3n}(\beta)} & \overset{?}= 1
}
$$ and that $\boldsymbol{s}$ is a correctly constructed running product $s_i = s_{i - 1} {u_{i - 1}(\beta) \over v_{i - 1}(\beta)}$:
$$
\eqalign{
s(\omega^{3n}) &\overset{?}= s(\omega^{3n - 1}){u_{3n - 1}(\beta) \over v_{3n - 1}(\beta)} & \\
& \ \vdots \\
s(\omega^2) &\overset{?}= s(\omega^1) {u_1(\beta) \over v_1(\beta)} & \\
s(\omega^1) &\overset{?}= 1 & \quad.
}
$$

If ${u(\beta) \over v(\beta)} = 1$ at the random challenge $\beta$ then $u(X) = v(X)$, which implies $\bold{v} = \sigma(\bold{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 $\bold{a} = (a_1, \dots, a_n)$ *set difference* $\bold{a}'$ as the difference between adjacent elements of $\bold{a}$:
$$
\eqalign{
& \bold{a}' &= (a_{i + 1} - a_i)_{i \in [n - 1]} & \\~
\\
\text{e.g. } & \bold{a} &= (2, 6, 4) & \\
& \bold{a}' &= (6 - 2, 4 - 6) = (4, -2) & \quad.
}
$$

Given arrays $\bold{a}$ and $\bold{b}$, if $\bold{b}$ is a subarray of $\bold{a}$, then the set difference of $\textsf{sorted}(\bold{a} \parallel \bold{b})$ contains $|\bold{b}|$ number of zeros because each $b_i$ is inserted next to an $a_j$ having the same value:
$$
\eqalign{
\text{e.g. } & \bold{a} &= (1, 3, 4, 7) & \\
& \bold{b} &= (1, 7) & \\
& \bold{c} &= \textsf{sorted}(\bold{a} \parallel \bold{b}) = (1, 1, 3, 4, 7, 7) & \\
& \bold{c}' &= (0, 2, 1, 3, 0) & \\
& \bold{c}' & \text{contains } |\bold{b}| = 2 \text{ zeros} & .
}
$$ However, this alone does not prove that an array is a subarray of $bold{a}$ because we can find an array$\bold{f} \not\subset \bold{a}$ where the set difference of $\textsf{sorted}(\bold{a} \parallel \bold{f})$ contains $|\bold{f}|$ number of zeros:
$$
\eqalign{
\text{e.g. } & \bold{a} &= (1, 1) & \\
& \bold{f} &= (3, 3) & \\
& \bold{g} &= \textsf{sorted}(\bold{a} \parallel \bold{f}) = (1, 1, 3, 3) \\
& \bold{g}' &= (0, 0) \\
& \bold{g}' & \text{contains } |\bold{f}| = 2 \text{ zeros} & .
}
$$

However, given a random value $\gamma$, we can test (w.h.p.) that an array $\bold{b}$ is subarray of an array $\bold{a}$ by shifting all elements by $\gamma$:

$$
\eqalign{
\text{e.g. } & \bold{a} + \gamma &= (a_1 + \gamma, \dots, a_n + \gamma) & \\
& \bold{b} + \gamma &= (b_1 + \gamma, \dots, b_{m} + \gamma) & \\
& \bold{c} &= \textsf{sorted}(\bold{a} \parallel \bold{b}) = (1, 1, 3, 4, 7, 7) & \\
& \bold{c}' &= (0, 2, 1, 3, 0) & \\
& \bold{c}' & \text{contains } |\bold{b}| = 2 \text{ zeros} & .
}
$$

<br/>
<br/>
<br/>
<br/>
<br/>
<br/>

## Multiset Checks (Right-Shift Schwartz-Zippel)

Given two arrays $\bold{a}$ and $\bold{b}$ of equal length $n$, if both $\bold{a}$ and $\bold{b}$ contain the same elements, regardless of their ordering, then the products of the arrays' elements will be equal:
$$
\eqalign{
\bold{a} & = (x, y, z) \ \ & \\
\bold{b} & = (x, z, y) = \sigma(\bold{a}) \ \ & \\
a_1a_2a_3 & = b_1b_2b_3 & .
}
$$ However, the products of two [equally lengthed] arrays' elements being equal does not guarantee that $\bold{a}$ and $\bold{b}$ contain the same elements, e.g.
$$
\eqalign{
\bold{a} &= (x, y, z) \\
\bold{b} &= \left( {x \over 2}, {z \over 2}, 4y \right) \neq \sigma(\bold{a}) \\
\prod_{i \in [n]} a_i &= \prod_{i \in [n]} b_i \quad\quad.
}
$$ 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$:
$$
\bold{a} = (x, y, z) \\
\bold{b} = (x, z, y) \\
(a_1 + \gamma)(a_2 + \gamma)(a_3 + \gamma) = (b_1 + \gamma)(b_2 + \gamma)(b_3 + \gamma) \\
\Longrightarrow \bold{b} = \sigma(\bold{a}) \quad.
$$

# 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:
$$
f(X) = c(X - a_1)\dots(X - a_n) \\
\text{roots}(f) = \{a_1, \dots, a_n\}
$$ where $c$ is a constant. If we don't care about the sign of the roots we can write:
$$
f(X) = c(X + a_1)\dots(X + a_n) \\
\text{roots}(f) = \{-a_1, \dots, -a_n\} \quad.
$$

A polynomial that has a linear factor $(iX - a)$ has a root at $a \over i$:
$$
\eqalign{
f(X) &= \prod_{i \in [n]}(iX - a_i) \\
&= c(X - {a_1 \over 1})\dots(X - {a_n \over n}) \quad\quad \text{where: } c = 1 * \dots * n \\
\text{roots}(f) &= \left\{ {a_1 \over 1}, \dots, {a_n \over n} \right\} \quad.
}
$$

## Encoding Sets and Arrays into Polynomials

We can encode a set of values $\{a_1, \dots, a_n\}$ into a unique polynomial:
$$
f(X) = \prod_{i \in [n]}(X - a_i) \\
\text{roots}(f) = \{a_1, \dots, a_n\} \quad.
$$

<br>

We can encode an array $(a_1, \dots, a_n)$ into a unique polynomial where each root encodes an array element and its position:
$$
f(X) = \prod_{i \in [n]}(iX - a_i) \\
\text{roots}(f) = \left\{ {a_1 \over 1}, \dots, {a_n \over n} \right\} \quad.
$$

<br>

**Side Note:** if an array is a permutation of another, e.g. $\boldsymbol{a} = (a_1, \dots, a_n)$ and $\boldsymbol{b} = (b_1, \dots, b_n) = \sigma(\boldsymbol{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_iX - b_i)
$$ e.g. $\boldsymbol{a} = (5, 6, 7)$ and $\boldsymbol{b} = (6, 7, 5) = \sigma(\boldsymbol{a})$:
$$
\eqalign{
a_1 & \rightarrow b_3 \quad & (\sigma_3 = 1) \\
a_2 & \rightarrow b_1 & (\sigma_1 = 2) \\
a_3 & \rightarrow b_2 & (\sigma_2 = 3)
} \\
~\\
\eqalign{
\prod_{i \in [n]} (iX - a_i) &= \prod_{i \in [n]} (\sigma_iX - b_i) \\
(1X - a_1)(2X - a_2)(3X - a_3) &= (\sigma_1X - b_1)(\sigma_2X - b_2)(\sigma_3X - b_3) \\
(1X - 5)(2X - 6)(3X - 7) &= (2X - 6)(3X - 7)(1X - 5)
}
$$

## Schwartz-Zippel

Given two univariate polynomials:
$$
f(X) = (X + a_1)\dots(X + a_n) \\
g(X) = (X + b_1)\dots(X + b_n)
$$ Schwartz-Zippel says that for a random input $\gamma \leftarrow \F$ the probability that different polynomials $f(X) \neq g(X)$ evaluate to the same value $f(\gamma) = g(\gamma)$ is very low.
$$
\Pr[f(\gamma) = g(\gamma) \mid f(X) \neq g(X)] \leq {\max(d_f, d_g) \over |\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 \F$:
$$
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) \neq g(X)] \leq {\max(d_f, d_g) \over |\F|}
$$ 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:
$$
f(X) = (1X - a_1)\dots(nX - a_n) \\
\text{roots}(f) = \left\{ {a_1 \over 1}, \dots, {a_n \over n} \right\}
$$ thus, we can use Schwartz-Zippel to test **array equality** (i.e. $\forall i \in [n]: a_i = b_i$).

PLONK uses Schwartz-Zippel (on random input $\lambda \leftarrow \F$) with a random right-shift $\delta \leftarrow \F$ to check array equality:
$$
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) \neq g(X)] \leq {\max(d_f, d_g) \over |\F|} \quad.
$$

### 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 \F^n$
$$
\Pr[f(x_1, \dots, x_n) = 0] \leq {d \over |\F|} \quad.
$$

### 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] \quad.
$$

## Low-Degree Extension

Given an array $\bold{a} = (a_1, \dots, a_n) \in \F^n$ and a subset $S = \{s_1, \dots, s_n\} \subset \F$, then the low-degree extension of $\bold{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)\}$:
$$
\forall i \in [n]: a(s_i) = a_i \quad.
$$

## Cosets (todo)

We associate each value in the constraint system with a unique value in $\mathbb{F}$:
$$
\eqalign{
\boldsymbol{x_l} &\rightarrow \mathbb{H}_1 \quad\quad\quad & \forall i \in [n]: x_l^{(i)} \rightarrow \omega^i \\
\boldsymbol{x_r} &\rightarrow \mathbb{H}_2 & \forall i \in [n]: x_r^{(i)} \rightarrow 2\omega^i \\
\boldsymbol{x_o} &\rightarrow \mathbb{H}_3 & \forall i \in [n]: x_o^{(i)} \rightarrow 3\omega^i
}
$$ 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$:
$$
\boldsymbol{u} = (\omega^1, \dots, \omega^n, 2\omega^1, \dots, 2\omega^n, 3\omega^1, \dots, 3\omega^n)
$$