# Composition of cyclic proof system.

$$ \def\F{\mathbb F} \def\Z{\mathbb Z} $$

## Introduction

The single most important theorem in modern proof systems is the Schwarz-Zippel lemma, so let's introduce it now:

**Theorem.** *(Schwartz–Zippel)*

**Definition.** *(Proof system). Given a claim $c \in \mathcal C$ and witness $w \in \mathcal W$*.

`setup`

: $(Entropy, \lambda) \rightarrow K$`proof`

: $(\mathcal C, \mathcal W) \rightarrow \mathcal P$.`verify`

: $(\mathcal C, \mathcal W) \rightarrow \mathcal P$.

In the remainder we assume we are talking about a specific instance of a proof, meaning the claim and witness are fixed.

**Definition.** *(Algebraic expressions). $\F[\{X_0, X_1, \dots\}]$* Is this a free-semiring?

**Definition.** *(Polynomial proof system). Given a field $\F$*

Parameters: $\F$, $\F[X]$.

Setup polynomials: $Q_0(X), Q_1(X), \dots$. (**to do**)

Witness polynomials: $P_0(X), P_1(X), \dots, P_M(X)$.

Constraint expressions: $f_0(X, P_0, P_1, \dots, P_M), f_1(\dots)$.

**Definition.** *(Cyclic polynomial proof system). A polynomial proof system where for each witness polynomial $P_i$ there is a primitive root of unity $\omega_{N_i}$ of order $N_i = \deg P_i + 1$. Setup and witness polynomials are defined by a vector $\vec w_i \in \F^{N_i}$ and $P_i$ is the polynomial resulting from interpolation of the vector on $⟨ω_{N_i}⟩$ such that $P_i(\omega_{N_i}^j) = w_{ij}$. All access to $P_i$'s in the constraint expression is of the form $P_i(\omega_{N_i}^k X)$ with $k \in \Z$. This allows us to relate witness value $w_{i,j}$ with $w_{i,j + k}$.*

**Note.** In the case of starks, the witness vectors $\vec w_i$ are all of the same length, called the *trace length*. This allows the interpolated values $w_{ij}$ to be layed out in an $N \times M$ matrix, called the *trace table*. The witness vectors are called *columns* or *registers*.

**To do.** Generallize to expressions of the form $P_i(\omega^k X^e)$ which will allow relating $i$ with $e \cdot i + k$, which in turn may allow the $2i$, $2i + 1$ offsets required for Vitalik's data availability proof.

**To do.** Show how to generalize

**Definition.** *(Degree of constraints). The maximum degree of $f_i$ in the arguments $P$ (so excluding the degree of $X$).

We can write repeating polynomial relationships between witness values.

**Note.** In practice we want to keep the degree of these relationships low, typically just $2$ or $3$. It is always possible to re-write higher degree constraint systems to an equivalent lower degree one by introducing new witness polynomials and new constraints.

**Definition.** *(Constraint values). Unconstraint values in the RS that can be set to anything.*

**Definition.** *(Empty proof). Proof of given size where all values are unconstraint.*

## Transformations and compositions

We will start by introducing some obvious invariants of proof systems. For starters, adding unused witness polynomials maintains the proof:

**Lemma.** *(Extension). Adding more unconstraint witness polynomials.*

We can also change the order of the witness polynomials:

**Lemma.** *(Permutation of witness polynomials). An RS proof system is invariant under a permutation of the order of the witness polynomials.*

We can also rotate things around

**Lemma.** *(Scaling). An RS proof system is invariant under multiplication of each constraint expression by a constant.*

**Lemma.** *(Rotation). An RS proof system is invariant under an affine transform $X \mapsto \omega_N X^i$ with corresponding rotation of the witness polynomials.*

**Lemma.** *(Rotation). An RS proof system is invariant under an affine transform $X \mapsto \omega_N^k X^i$ in constraint polynomials witness access and $X \mapsto \omega_N^{-k} X$ for the $X$ argument.*

**Lemma.** *(Interpolation). An RS proof system is invariant under an affine transform $X \mapsto X^k$ where $k \vert N$ and ( to do).*

Combined, these rotation and interpolation have the effect of mapping $X=\omega_N^i$ to $X=\omega_N^{e \cdot i + k}$; it is an affine transform of the exponent with a corresponding inverse transform in the witness.

**Lemma.** *(Folding). An RS proof system with $M$ witness polynomials of degrees $n_i$ can be transformed into an RS proof system with $M/2$ polynomials of degree $2 n_i$.*

**To do.** Generalize to roots of unity other than binary powers of two.

**To do.** Generalize to roots of unity other than binary powers of two, allowing more complex foldings than halfing/doubling.

**Lemma.** *(Repeated folding). .*

**Lemma.** *(Projection). Given two RS proof systems such that the second fits in the unconstraint cells of the first, they can be merged.*

**Lemma.** *(Horizontal composition). Two proof systems can be composed horizontally.*

**Lemma.** *(Vertical composition). Two proof systems can be composed vertically if all their constraints are the same.*

The previous lemmas give us some leeway to make them the same.

**Lemma.** *(Matched horizontal composition). Can be composed horizontally.*

## Special cyclic polynomial proof systems

Vector equality

Set equality

Permutation check

Univariate rowcheck

Univariate sumcheck

Row check

Lincheck

## Example cyclic polynomial proof systems

MiMC/Poseidon/etc.

Plonk/RedShift

Aurora

Marlin

Fractal

## Overview of low degree tests

**Lemma.** *(Degree raising). Given a polynomial $P$ with degree bound $\deg P ≤ k$ and an LDE test for degree $N$ with $k ≤ N$, we can test the degree-bound of the polynomial.*

$$ P'(X) = (\alpha + \beta \cdot X^k) \cdot P(X) $$

**Lemma.** *(Degree halving).*

$$ P(X) = P'(X^2) + X \cdot P''(X^2) $$

**Note.** Degree halving doubles the number of polynomials to be LDE tested.

**Lemma.** *(Combining low degree tests).*

$$ P'(X) = \sum_i \alpha_i P_i(X) $$

Using the above three lemmas, a single low-degree test can verify arbitrary degree bounds on a set of polynomials.