# Plonk Protocol

## The Vanishing Polynomial
The polynomial that vanishes on the set $H$ can be expressed as:

$$
Z_H(x) = (x - 1)(x - \omega)(x - \omega^2) \ldots (x - \omega^{n-1})
$$

For sufficiently large $n$, evaluating $Z_H(x)$ directly becomes cumbersome. However, leveraging the property $\omega^n = 1$, we can simplify this expression to:

$$
Z_H(x) = x^n - 1
$$

To verify this, for any $x \in H$ (specifically $x = \omega^i$), we compute:

$$
(\omega^i)^n - 1 = (\omega^n)^i - 1 = 1^i - 1 = 0
$$

Thus, $Z_H(x) = x^n - 1$ effectively captures all the roots in $H$.

### Context and Parameters
The size of the set $H$ corresponds to the number of gates in a circuit, while the size of the finite field $\mathbb{F}_p$ represents a security parameter, with $p$ typically much larger than $n$. This relationship indicates that $H$ is a subset of the field $H \subset \mathbb{F}_p$, establishing a practical environment for polynomial operations.

## Lagrange Interpolation
We interpolate a vector $v$ of size $n$ using the Lagrange basis. The polynomial representation $v(x)$ can be expressed as:

$$
v(x) = \sum_{i=1}^{n} v_i L_i(x)
$$

where $L_i(x)$ is defined as:

$$
L_i(x) = \prod_{\substack{k \in H \\ k \neq \omega^i}} \frac{x - k}{\omega^i - k}
$$

### Properties of Lagrange Basis
The Lagrange basis polynomials $L_i(x)$ satisfy:

- $L_i(\omega^i) = 1$
- $L_i(\omega^j) = 0$ for $j \neq i$

This property ensures that $v(\omega^i) = v_i$ for all $i$, accurately reconstructing the polynomial from its evaluations at the roots in $H$.

## Schwartz-Zippel Lemma

Let $\mathbb{F}$ be a field and let $f(x_1, x_2, \ldots, x_n)$ be a polynomial of total degree $d$, where $f$ is not the zero polynomial. Let $S$ be a finite subset of $F$. If $r_1, r_2, \ldots, r_n$ are chosen uniformly and independently at random from $S$, then the probability that $f(r_1, r_2, \ldots, r_n) = 0$ is given by:

$$
\Pr(f(r_1, r_2, \ldots, r_n) = 0) \leq \frac{d}{|S|}.
$$

### Proof of the Lemma

We will prove this lemma by induction on $n$, the number of variables. The base case for $n = 1$ has already been established.

#### Inductive Step

Assume the lemma holds for $n-1$ variables. We can express $f$ as a polynomial in the first variable:

$$
f(x_1, x_2, \ldots, x_n) = x_1^k c_k(x_2, \ldots, x_n) + x_1^{k-1} c_{k-1}(x_2, \ldots, x_n) + \cdots + c_0(x_2, \ldots, x_n),
$$

where $c_k(x_2, \ldots, x_n)$ is a polynomial in $x_2, \ldots, x_n$ that is not the zero polynomial.

##### Application of the Inductive Hypothesis

By the inductive hypothesis, the probability that $c_k(r_2, \ldots, r_n) = 0$ for uniformly chosen $r_2, \ldots, r_n$ from $S$ is:

$$
\Pr(c_k(r_2, \ldots, r_n) = 0) \leq \frac{d-k}{|S|}.
$$

If $c_k(r_2, \ldots, r_n) \neq 0$, then the polynomial $f(x_1, r_2, \ldots, r_n)$ is a non-zero polynomial in $x_1$ of degree $k$.

By the base case, the probability that a uniformly chosen $r_1$ from $S$ satisfies $f(r_1, r_2, \ldots, r_n) = 0$ is:

$$
\Pr(f(r_1, r_2, \ldots, r_n) = 0 \mid c_k(r_2, \ldots, r_n) \neq 0) \leq \frac{k}{|S|}.
$$

#### Total Probability

To summarize, if $f(r_1, r_2, \ldots, r_n) = 0$, then either:

1. $c_k(r_2, \ldots, r_n) = 0$
2. $f(x_1, r_2, \ldots, r_n) = 0$ for $r_1$ where $c_k(r_2, \ldots, r_n) \neq 0$

Thus, the total probability can be expressed as:

$$
\Pr(f(r_1, r_2, \ldots, r_n) = 0) \leq \Pr(c_k(r_2, \ldots, r_n) = 0) + \Pr(c_k(r_2, \ldots, r_n) \neq 0) \cdot \Pr(f(r_1, r_2, \ldots, r_n) = 0 \mid c_k(r_2, \ldots, r_n) \neq 0).
$$

Substituting the bounds obtained from the inductive hypothesis and the base case, we have:

$$
\Pr(f(r_1, r_2, \ldots, r_n) = 0) \leq \frac{d-k}{|S|} + \left(1 - \frac{d-k}{|S|}\right) \cdot \frac{k}{|S|}.
$$

This simplifies to:

$$
\Pr(f(r_1, r_2, \ldots, r_n) = 0) \leq \frac{d-k + k}{|S|} = \frac{d}{|S|}.
$$

Therefore, we conclude:

$$
\Pr(f(r_1, r_2, \ldots, r_n) = 0) \leq \frac{d}{|S|}.
$$

This completes the proof.

## Gate Representation
We consider an arithmetic circuit consisting of two types of gates: addition and multiplication. Each gate is represented in a tabular format where inputs and outputs are structured as follows:

$$
\text{Gate}_i: \text{Left Input} \quad | \quad \text{Right Input} \quad | \quad \text{Output}
$$

### Example Circuit


For our example circuit, we define the following variables:
- Public inputs: $x_1$, $x_2$
- Secret input: $s_1$

Given the values $x_1 = 2$, $x_2 = 1$, and $s_1 = 3$, we can express the computation through vectors:
- $w_l = [x_1, x_2, s_1] = [2, 1, 3]$
- $w_r = [x_2, s_1, s_1] = [1, 3, 3]$
- $w_o = [3, 3, 9]$ (representing the output)

Here, $n$ denotes the size of the circuit, which is equivalent to the number of gates.

## Constraint System Definition

### Structure of the Constraint System

The constraint system $\mathscr{C}$ is defined as follows:

- Let $m$ and $n$ be positive integers representing the number of wires and gates, respectively.

- The query vector $\mathscr{Q}$ is given by:
$$
\mathscr{Q} = (q_l, q_r, q_o, q_m, q_c) \in (\mathbb{F}^{n})^{5}
$$
where each $q_l, q_r, q_o, q_m, q_c \in \mathbb{F}^{n}$ serves as selector vectors.

## Instantiations of the Constraint System

### Arithmetic Circuits

An arithmetic circuit with fan-in 2 can be captured by the following:

1. Set $m$ to the total number of wires.
2. For each gate $i \in [n]$:
- Assign $l_i$, $r_i$, and $o_i$ to the indices of the left, right, and output wires respectively.
3. Define $q_l, q_r, q_o, q_m, q_c$ based on the gate type:
- For multiplication:
$$
(q_l)_i = 0, \quad (q_r)_i = 0, \quad (q_m)_i = 1, \quad (q_o)_i = -1
$$
- For addition:
$$
(q_l)_i = 1, \quad (q_r)_i = 1, \quad (q_m)_i = 0, \quad (q_o)_i = -1
$$
4. Set $(q_c)_i = 0$ for all $i$.

### Booleanity Constraints

To enforce a boolean constraint $w_j \in \{0, 1\}$ for some $j \in [m]$, we set:
- For some $i \in [n]$:
$$
l_i = r_i = j, \quad (q_l)_i = -1, \quad (q_m)_i = 1, \quad (q_r)_i = (q_o)_i = (q_c)_i = 0
$$

### Enforcing Constants

To enforce the constraint $w_j = a$ for a fixed $j \in [m]$ and $a \in \mathbb{F}$:
- Set:
$$
l_i = j, \quad (q_l)_i = 1, \quad (q_m)_i = (q_r)_i = (q_o)_i = 0, \quad (q_c)_i = -a
$$

### Preparation for Public Inputs

We say that $\mathscr{C}$ is prepared for $\ell$ public inputs if:
$$
l_i = i, \quad (q_l)_i = 1, \quad (q_m)_i = (q_r)_i = (q_o)_i = (q_c)_i = 0
$$

The public input polynomial:
$$
PI(X) := \prod_{i \in [\ell]} (-x_i \cdot L_i(X))
$$

## The SNARK Proof Relation
We aim to prove statements of knowledge related to the values of two sets of variables, $\mathtt{x}$ and $\mathtt{w}$.
Consider witness vector $w$ which has size $3n$ and is composed of $w_l, w_r, w_o$ such that $w = (w_{l_1}, \ldots, w_{l_n}, w_{r_1}, \ldots, w_{r_n}, w_{o_1}, \ldots, w_{o_n}).$ Specifically, we consider:

- $\mathtt{x} = (w_i)_{i \in [\ell]}$
- $\mathtt{w} = (w_i)_{i = \ell + 1}^{3n}$

### Definition of the Relation
The relation $\mathcal{R}$ consists of all pairs $(\mathtt{x}, \mathtt{w})$ that satisfy the following polynomial equation for every $i \in [n]$:

$$
q_{m_i} w_i w_{n+i} + q_{l_i} w_i + q_{r_i} w_{n+i} + q_{o_i} w_{2n+i} + q_{c_i} + PI_i = 0
$$

Here, we utilize the shorthand $q_i = q(\omega^i)$, $PI_i = PI(\omega^i)$ where $\omega$ is a primitive $n$-th root of unity in the finite field $\mathbb{F}$.

### Polynomial Components
The components of the equation can be interpreted as follows:

- $q_{m_i} w_i w_{n+i}$: Represents a multiplication constraint involving two variables from the inputs.
- $q_{l_i} w_i$: Linear constraint involving the input variable $w_i$.
- $q_{r_i} w_{n+i}$: Another linear constraint involving the paired variable $w_{n+i}$.
- $q_{o_i} w_{2n+i}$: Represents an additional term affecting the output variables.
- $q_{c_i}$: A constant term that completes the polynomial equation.

## Round 1

The first round of the protocol comprises three main steps:
1. Generation of Random Blinding Scalars: $(b_1, \ldots, b_9) \in \mathbb{F}_p$.
2. Computation of Wire Polynomials: $a(x), b(x), c(x)$.
3. Computation and Output of Commitments: $[a]_1, [b]_1, [c]_1 \in \mathbb{G}_1$

### Blinding Techniques

#### Blinding Polynomial Commitments
To conceal the committed polynomial $f(x)$, we utilize randomization techniques. The PlonK protocol achieves this by modifying the polynomial as follows:

$$
f'(x) = Z_H(x) \cdot \text{some expression} + f(x)
$$

By this construction, $f'(x)$ retains the same values as $f(x)$ over the domain $H$:

$$
f(x) = f'(x) \quad \forall x \in H
$$

This guarantees that while the polynomial values at points in $H$ remain unchanged, the overall appearance of the polynomial is randomized.

#### Blinding Scalars
When revealing evaluations of $f(x)$ at challenge points $(z_1, z_2, \ldots, z_k)$, we modify the polynomial using random blinding scalars $(b_1, b_2, \ldots, b_{k+1}) \in \mathbb{F}_p$:

$$
f'(x) = (b_1 + b_2 x + b_3 x^2 + \ldots + b_{k+1} x^k) Z_H(x) + f(x)
$$

Here, the number of random coefficients must be at least $k + 1$, where $k$ is the number of evaluations revealed. This construction maintains the zero-knowledge property since, despite $f'(x)$ being altered, it still evaluates to $f(x)$ at points in $H$.

#### Security Considerations
The randomization introduced by blinding ensures that the evaluations of the polynomials at random challenge points do not reveal information about the original polynomial. The probability of randomly selecting an element from $H$ in comparison to the larger field $\mathbb{F}_p$ is negligible, maintaining the zero-knowledge property of the protocol. If challenge points are selected outside of $H$, the polynomial $f'(x)$ provides additional security, making it difficult to extract the original polynomial from its blinded form.

### Computing Wire Polynomials in the KZG Commitment Scheme

#### Notation and Definitions
We utilize the notation $[f]_1$ to denote commitments to polynomials evaluated at a secret point $\tau$ as follows:

$$
[f]_1 = G_1^{f(\tau)}
$$

where $G_1$ represents a generator of the elliptic curve used in the commitment scheme. The evaluation of polynomials at the point $\tau$ forms the basis for our commitments.

#### Construction of Wire Polynomials
In Round 1 of the protocol, the prover constructs polynomials from the computation table's columns, specifically the left, right, and output wire values. Each column is expressed as a wire polynomial through Lagrange interpolation, enhanced with random coefficients to ensure privacy.

#### Left Wire Polynomial
The left wire polynomial $a(x)$ is defined as:

$$
a(x) = (b_1 x + b_2) Z_H(x) + \sum_{i=1}^{n} w_{i} L_i(x)
$$

where:
- $(b_1, b_2)$ are random blinding coefficients,
- $Z_H(x)$ is the vanishing polynomial defined previously,
- $L_i(x)$ are the Lagrange basis polynomials ensuring that $a(x)$ interpolates the values $w_{i}$ at points in $H$.

#### Right Wire Polynomial
The right wire polynomial $b(x)$ is constructed similarly:

$$
b(x) = (b_3 x + b_4) Z_H(x) + \sum_{i=1}^{n} w_{n + i} L_i(x)
$$

where $(b_3, b_4)$ are another set of random coefficients.

#### Output Wire Polynomial
The output wire polynomial $c(x)$ is given by:

$$
c(x) = (b_5 x + b_6) Z_H(x) + \sum_{i=1}^{n} w_{2n+i} L_i(x)
$$

with $(b_5, b_6)$ representing the final set of random coefficients.

#### Commitment to Wire Polynomials
After constructing the wire polynomials, the prover commits to each polynomial as follows:

$$
[a]_1 = G_1^{a(\tau)}, \quad [b]_1 = G_1^{b(\tau)}, \quad [c]_1 = G_1^{c(\tau)}
$$

These commitments secure the polynomials evaluated at the secret point $\tau$ and bind the prover to the values contained within the polynomials.

## Round 2

In this round, the prover performs the following steps:

1. Receives permutation challenges $\beta = \mathcal{H}(\text{transcript}, 0)$ and $\gamma = \mathcal{H}(\text{transcript}, 1)$.
2. Computes the permutation polynomial $z(x)$.
3. Generates and outputs the commitment $[z]_1 \in \mathbb{G}_1$.

### Efficient Verification of Permutations in Zero-Knowledge Proofs

A permutation of a set is a specific arrangement of its elements. For example, given a set $S = (a, b, c)$, the arrangements $[c, b, a]$ and $[b, a, c]$ are valid permutations, while $[b, b, c]$ is not. In the context of arithmetic circuits, ensuring that certain wire values are consistent is vital. This report outlines how to construct and verify permutations within these circuits.

#### Understanding Permutations
A permutation is defined as a mapping $\sigma: S \rightarrow S$ that represents a reordering of the elements of $S$. In arithmetic circuits, wires corresponding to outputs must match their respective inputs, leading to constraints that can be represented mathematically.


##### Constraints from Gates
Each gate in an arithmetic circuit establishes relationships among wire values. For example, if $\text{gate}_i$ outputs to $\text{gate}_j$, we have:

$$
\text{output of } \text{gate}_i = \text{input to } \text{gate}_j.
$$

To verify these relationships, we can organize wire values into equivalence classes.

This is how the permutation $\sigma$ would look for the example diagram from arithmetization.


No matter on the input of the circuit the values in the equivalence class must always contain the same value. This specific circuit thus has copy constraints
$$
w_2 = w_4, \quad w_3 = w_7, \quad w_6 = w_8
$$
We can prove that the copy constraints hold by showing that $w_i = \sigma(w_i)$ holds for every index $i$. Say there is constraint $w_i = w_j = w_k = w_l$ and we get:
$$
\vdots
$$
$$
w_i = \sigma(w_i) \rightarrow w_i = w_j
$$
$$
w_j = \sigma(w_j) \rightarrow w_j = w_k
$$
$$
w_k = \sigma(w_k) \rightarrow w_k = w_l
$$
$$
w_l = \sigma(w_l) \rightarrow w_l = w_i
$$
$$
\vdots
$$
Naturally, the expressions above are satisfied if and only if $w_i = w_j = w_k = w_l.$ That is the core idea that will be used in the permutation check.

#### Permutation Verification
To verify that two vectors $p$ and $q$:

$$
p = [p_1, p_2, \ldots, p_n], \quad q = [q_1, q_2, \ldots, q_n]
$$

are permutations of each other, we aim for a more efficient verification than naive element-wise comparison.

##### Initial Polynomial Product Check
A straightforward method involves checking:

$$
p_1 \times p_2 \times \ldots \times p_n \stackrel{?}{=} \sigma(q_1) \times \sigma(q_2) \times \ldots \times \sigma(q_n).
$$

While this method is correct due to the commutative property of multiplication, it lacks soundness; different vectors can yield the same product, leading to false positives.

##### Enhanced Polynomial Evaluation
To enhance soundness, we sample a random element $\gamma$ and reformulate our check:

$$
(P(\gamma) = (p_1 + \gamma) \cdot (p_2 + \gamma) \cdots (p_n + \gamma)),
$$

$$
(Q(\gamma) = (\sigma(q_1) + \gamma) \cdot (\sigma(q_2) + \gamma) \cdots (\sigma(q_n) + \gamma)).
$$

We verify:

$$
P(\gamma) \stackrel{?}{=} Q(\gamma).
$$

This check leverages polynomial properties; if $P(\gamma)$ and $Q(\gamma)$ are equal for a randomly chosen $\gamma$, it suggests that the polynomials are equivalent with high probability.

#### Intra-vector Permutation Check
While the previous check demonstrates the concept, we now define a specific permutation $\sigma: H \rightarrow H$ on two vectors.

##### Tuple Encoding
Elements are encoded as tuples:

$$
(\text{value}, \text{index}).
$$

This allows us to represent the elements from a chosen domain of evaluation $H$. For example, a permutation could swap two elements, as shown in the visual representation below.


##### Linear Combinations for Verification
We construct a linear combination of the encoded tuples:

$$
(w_i, \omega^{i-1}) \rightarrow w_i + \beta \omega^{i-1},
$$

where $\beta$ is randomly sampled. The essential property we require is:

$$
(a, b) = (a', b') \iff a + \beta b = a' + \beta b'.
$$

This is guaranteed if $a + \beta b$ and $a' + \beta b'$ are viewed as polynomials evaluated at $\beta$. By ensuring the linear combinations are equal, we can assert with high probability that the tuples are equivalent.

#### Combining Verification Approaches
We now synthesize our methods into a coherent framework. To verify a specific permutation, we utilize the polynomial evaluation framework alongside the linear combinations of tuples:

$$
(w_1 + \beta 1 + \gamma) \cdots (w_n + \beta \omega^{n-1} + \gamma) \stackrel{?}{=} (w_1 + \beta \sigma(1) + \gamma) \cdots (w_n + \beta \sigma(\omega^{n-1}) + \gamma).
$$

This can be expressed as:

$$
1 \stackrel{?}{=} \frac{\prod_{i=1}^n (w_i + \beta \omega^{i-1} + \gamma)}{\prod_{i=1}^n (w_i + \beta \sigma(\omega^{i-1}) + \gamma)}.
$$

This formulation ensures that we can verify the copying constraints of the arithmetic circuit through the lens of permutations.

### Equality of Polynomial Products Implies Coefficient Equality

Let us consider the following scenario:
- A permutation $\sigma$ of the set $[n]$.
- Two sequences of elements $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$ belonging to a field $\mathbb{F}$.
- Random variables $\beta$ and $\gamma$ chosen uniformly from $\mathbb{F}$.

We assume that:

$$
\prod_{i \in [n]} (a_i + \beta \cdot i + \gamma) = \prod_{i \in [n]} (b_i + \beta \cdot \sigma(i) + \gamma)
$$

with a probability greater than $\frac{n}{|F|}$ for $\beta$ and $\gamma$ randomly selected from $F$.

Our goal is to prove that $b_i = a_{\sigma(i)}$ for all $i \in [n]$.

#### Step 1: Application of the Schwartz-Zippel Lemma

According to the Schwartz-Zippel lemma, if two polynomials are equal at a large number of randomly chosen points, they must be equal as polynomials over the entire field. From our assumptions, we can express the polynomial relationship as:

$$
\prod_{i=1}^{n} (a_i + iX + Y) = \prod_{i=1}^{n} (b_i + \sigma(i)X + Y)
$$

where $X$ and $Y$ are formal variables.

#### Step 2: Analysis of Factors

It is important to note that the ring $F[X, Y]$ is a Unique Factorization Domain (UFD), which means every polynomial can be factored uniquely into irreducible factors. The irreducible factors in this context are linear polynomials (degree 1 in $X$ and $Y$).

Thus, the linear factors on both sides of the equation must correspond one-to-one, indicating that each factor on the left-hand side must match a corresponding factor on the right-hand side.

#### Step 3: Establishing a One-to-One Correspondence Between Factors

Let $M$ be a factor on the left-hand side and $M'$ be the corresponding factor on the right-hand side. Then, we can express this relationship as:

$$
M = c \cdot M'
$$

for some non-zero constant $c \in F^*$ (the set of invertible elements in $F$).

#### Step 4: Proving $c = 1$

In the equation above, since the coefficient of $Y$ in each factor is $1$, it follows that $c$ must also equal $1$. If $c$ were different from $1$, then the coefficients of $Y$ would differ between the two sides, contradicting the equality. Therefore, we have:

$$
M = M'.
$$

#### Step 5: Drawing Conclusions for Each $i$

Consequently, for each factor $(a_i + iX + Y)$ on the left-hand side, there exists a corresponding factor $(b_j + \sigma(j)X + Y)$ on the right-hand side, with $j = \sigma(i)$. This leads us to the equality:

$$
a_{\sigma(i)} + \sigma(i)X + Y = b_i + \sigma(i)X + Y.
$$

By comparing the constant terms, we can deduce:

$$
b_i = a_{\sigma(i)} \quad \text{for all } i \in [n].
$$

This completes the proof of the claim, confirming that if the polynomial products are equal with high probability over chosen values, then the coefficients must align according to the specified permutation.

### Polynomial Protocols for Identifying Permutations

At the core of our universal SNARK (Succinct Non-interactive Argument of Knowledge) lies a mechanism for verifying permutations of polynomials. The central concept involves checking whether two polynomials $g$ and $f$ relate through a permutation $\sigma$. Specifically, we establish conditions under which $g = \sigma(f)$, ensuring that this verification is both efficient and sound against potential malicious provers.

#### Degree Bounds

We define two parameters, $n$ and $d$, where $n \leq d$. Here, $n$ represents the degree of the honest prover’s polynomials, while $d$ is the maximum degree bound enforced on potentially malicious provers. For the analysis of prover efficiency, we consider a degree bound of $n$, whereas soundness is analyzed with the degree bound $d$.

#### Claim A.1

For a fixed $i \in [n]$ and polynomials $Z, Z^* \in F[X]$, the condition

$$
L_i(a)(Z(a) - Z^*(a)) = 0 \quad \text{for each } a \in H
$$

holds if and only if

$$
Z(\omega^i) = Z^*(\omega^i).
$$

#### The Protocol for Polynomial Verification

##### Inputs

We consider polynomials $f, g \in \mathbb{F}_{<n}[X]$ and a permutation $\sigma: [n] \to [n]$, we write $g = \sigma(f)$ if for each $i \in [n], g(\omega^i) = f(\omega^{\sigma(i)})$.

##### Protocol Steps

1. **Randomization**: The verifier $V_{\text{poly}}$ selects random values $\beta, \gamma \in F$ and sends them to the prover $P_{\text{poly}}$.

2. **Polynomial Transformation**:
Define the transformed polynomials:
$$
f' := f + \beta \cdot \text{SID} + \gamma, \quad g' := g + \beta \cdot S_\sigma + \gamma,
$$
where
$$
\text{SID}(\omega^i) = i \quad \text{and} \quad S_\sigma(\omega^i) = \sigma(i) \text{ for each } i \in [n].
$$

3. **Computation of $Z$**:
The prover computes a polynomial $Z \in \mathbb{F}_{<n}[X]$ such that:
$$
Z(\omega) = 1,
$$
and for $i \in \{2, \ldots, n\}$:
$$
Z(\omega^i) = \prod_{1 \leq j < i} \frac{f'(\omega^j)}{g'(\omega^j)}.
$$
If any product term becomes undefined (which occurs with negligible probability over $\gamma$), the protocol is aborted.

4. **Sending $Z$**: The prover sends $Z$ to the verifier.

5. **Verification Checks**:
The verifier checks the following conditions for all $a \in H$:
- **Check 1**:
$$
L_1(a)(Z(a) - 1) = 0.
$$
- **Check 2**:
$$
Z(a) f'(a) = g'(a) Z(a \cdot \omega).
$$
The verifier outputs "accept" (acc) if all checks hold.

##### Soundness Analysis

For fixed $f, g \in \mathbb{F}_{<d}[X]$, the probability that $V_{\text{poly}}$ outputs "accept" when $g \neq \sigma(f)$ is negligible.

**Proof**: Suppose $g \neq \sigma(f)$. By Claim A.1, with overwhelming probability (negligible over the choice of $\beta, \gamma$), we have:

$$
a := \prod_{i \in [n]} f'(\omega^i) \neq b := \prod_{i \in [n]} g'(\omega^i).
$$

Assuming $\beta, \gamma$ are chosen such that $g'(\omega^i) \neq 0$ for all $i \in [n]$, we will show that $V_{\text{poly}}$ must reject.

From the first check, we know $Z(\omega) = 1$. From the second check, we derive inductively that for each $i \in [n]$:

$$
Z(\omega^{i+1}) = \prod_{1 \leq j \leq i} \frac{f'(\omega^j)}{g'(\omega^j)}.
$$

In particular, substituting for $i = n$ gives:

$$
1 = Z(\omega) = Z(\omega^{n+1}) = \frac{a}{b} \neq 1,
$$

leading to a contradiction. Thus, $V_{\text{poly}}$ rejects when $g \neq \sigma(f)$.

### Checking Extended Permutations

Let $k$ be the number of polynomials and $d$ be their maximum degree. Given $f_1, \ldots, f_k \in \mathbb{F}_{<d}[X]$ and a permutation $\sigma : [kn] \to [kn]$, we define the relationship:

$$
(g_1, \ldots, g_k) = \sigma(f_1, \ldots, f_k)
$$

if the following holds:

Define the sequences $(f_{(1)}, \ldots, f_{(kn)}), (g_{(1)}, \ldots, g_{(kn)}) \in \mathbb{F}^{kn}$ by:

$$
f_{((j-1) \cdot n + i)} := f_j(\omega^i), \quad g_{((j-1) \cdot n + i)} := g_j(\omega^i)
$$

for each $j \in [k]$ and $i \in [n]$. Then we require $g_{(\ell)} = f_{(\sigma(\ell))}$ for every $\ell \in [kn]$.

#### Preprocessed Polynomials

The polynomials $\text{SID}_1, \ldots, \text{SID}_k \in \mathbb{F}_{<n}[X]$ are defined as follows:

$$
\text{SID}_j(\omega^i) = (j - 1) \cdot n + i \quad \text{for each } i \in [n].
$$

Notably, we include only $\text{SID} = \text{SID}_1$ in the set of preprocessed polynomials since $\text{SID}_j(x)$ can be computed via:

$$
\text{SID}_j(x) = \text{SID}(x) + (j - 1) \cdot n.
$$

For each $j \in [k]$, we define $S_{\sigma_j} \in \mathbb{F}_{<n}[X]$ by:

$$
S_{\sigma_j}(\omega^i) = \sigma((j - 1) \cdot n + i) \quad \text{for each } i \in [n].
$$

#### Protocol Steps

1. **Initialization**: The verifier $V_{\text{poly}}$ selects random values $\beta, \gamma \in \mathbb{F}$ and sends them to the prover $P_{\text{poly}}$.

2. **Transformation**:
Define the polynomials:
$$
f_j' := f_j + \beta \cdot \text{SID}_j + \gamma, \quad g_j' := g_j + \beta \cdot S_{\sigma_j} + \gamma.
$$
For $j \in [k]$ and $i \in [n]$:
$$
f_j'(\omega^i) = f_j(\omega^i) + \beta((j - 1) \cdot n + i) + \gamma, \quad g_j'(\omega^i) = g_j(\omega^i) + \beta \cdot \sigma((j - 1) \cdot n + i) + \gamma.
$$

3. **Composite Polynomial Definition**:
Define the combined polynomials:
$$
f'(X) := \prod_{j=1}^{k} f_j'(X), \quad g'(X) := \prod_{j=1}^{k} g_j'(X).
$$

4. **Computation of $Z$**:
The prover computes $Z \in \mathbb{F}_{<n}[X]$ such that:
$$
Z(\omega) = 1,
$$
and for $i \in \{2, \ldots, n\}$:
$$
Z(\omega^i) = \prod_{1 \leq j < i} \frac{f'(\omega^j)}{g'(\omega^j)}.
$$
Any undefined products are managed similarly to the previous protocol.

5. **Sending $Z$**: The prover sends $Z$ to the verifier.

6. **Verification Checks**:
The verifier checks the following for all $a \in H$:
- **Check 1**:
$$
L_1(a)(Z(a) - 1) = 0.
$$
- **Check 2**:
$$
Z(a) f'(a) = g'(a) Z(a \cdot \omega).
$$
The verifier outputs "accept" (acc) if all checks hold.

#### Soundness Lemma

For fixed polynomials $f_1, \ldots, f_k, g_1, \ldots, g_k \in \mathbb{F}_{<d}[X]$ and a permutation $\sigma$ on $[kn]$, if $(g_1, \ldots, g_k) \neq \sigma(f_1, \ldots, f_k)$, then for any strategy of $P_{\text{poly}}$, the probability of $V_{\text{poly}}$ outputting "accept" is negligible.

**Proof**: The condition $(g_1, \ldots, g_k) \neq \sigma(f_1, \ldots, f_k)$ implies that with high probability over $\beta, \gamma \in \mathbb{F}$, the product $F$ of the values $\{f_j'(\omega^i)\}_{j \in [k], i \in [n]}$ differs from the product $G$ of the values $\{g_j'(\omega^i)\}_{j \in [k], i \in [n]}$. Specifically, we have:

$$
F = \prod_{i \in [n]} f'(\omega^i), \quad G = \prod_{i \in [n]} g'(\omega^i).
$$

The subsequent steps of the protocol mirror those of the previous sections, explicitly verifying if these products are equal.

### Inter-Vector Verification
To check whether the vectors $w_l, w_r, w_o$ are permutations of each other, we begin by concatenating them into a single vector $w$:

$$
w = (w_{l_1}, w_{l_2}, \ldots, w_{l_n}, w_{r_1}, w_{r_2}, \ldots, w_{r_n}, w_{o_1}, w_{o_2}, \ldots, w_{o_n}),
$$

which has a size of $3n$. The domain $H$ is insufficient to index $w$ due to its size; hence, we extend the domain to:

$$
H' = H \cup (k_1 H) \cup (k_2 H),
$$

where $k_1, k_2 \in \mathbb{F}_p$ are chosen to ensure that all elements in $H, k_1 H, k_2 H$ are distinct.

#### Permutation Function
We define a permutation function:

$$
\sigma^*: [1, 2, \ldots, 3n] \rightarrow H'
$$

This function will facilitate the required rotations across equivalence classes, aligning the indexing appropriately.

#### Verification Expression
The core of our verification mechanism can be expressed as:

$$
1 \stackrel{?}{=} \prod_{i=1}^n \frac{p(i)}{q(i)},
$$

where:

$$
p(i) = (w_i + \beta \omega^i + \gamma)(w_{n+i} + \beta k_1 \omega^i + \gamma)(w_{2n+i} + \beta k_2 \omega^i + \gamma),
$$

$$
q(i) = (w_i + \beta \sigma^*(i) + \gamma)(w_{n+i} + \beta \sigma^*(n+i) + \gamma)(w_{2n+i} + \beta \sigma^*(2n+i) + \gamma).
$$

This expression must hold for each $i$. However, it may be undefined if $q(i) = 0$. Such occurrences are statistically insignificant, and the protocol can be designed to retry with new random samples for $\beta$ and $\gamma$ if necessary.

### The Permutation Polynomial
To convince the verifier that the permutation check is valid without revealing the underlying values, we construct a permutation polynomial defined as follows:

$$
z'(\omega^0) = 1,
$$

$$
z'(\omega^i) = \prod_{j=1}^i \frac{p(j)}{q(j)} \quad \text{for } i \in [1 \ldots n-1].
$$

#### Polynomial Construction
The polynomial $z(x)$ encodes the products of ratios, representing the original and permuted sets. If all ratios equal 1, it indicates that the copying constraints are satisfied. We can compute the polynomial values over the extended domain $H$:

$$
(z'(\omega), z'(\omega^2), z'(\omega^3), \ldots, z'(\omega^{n-1})) = \left(\frac{p(1)}{q(1)}, \frac{p(1)p(2)}{q(1)q(2)}, \ldots, \prod_{i=1}^{n-1} \frac{p(i)}{q(i)}\right).
$$

#### Ensuring Polynomial Evaluation at $\omega^0$
To ensure that the permutation polynomial evaluates to 1 at $\omega^0$, we add the Lagrange basis polynomial $L_1(x)$:

$$
z(x) = (b_7 x^2 + b_8 x + b_9) Z_H(x) + L_1(x) + z'(x),
$$

where $Z_H(x)$ is a polynomial that vanishes on the domain of $H$, and $z'(x)$ is a polynomial that introduces randomness.

## Round 3

Round overview:
1. Compute quotient challenge $\alpha = \mathcal{H}(\text{transcript})$
2. Compute quotient polynomial $t(x)$
3. Split $t(x)$ into polynomials of smaller degree
4. Compute and blind polynomial parts $t_{\text{lo}}(x), t_{\text{mid}}(x), t_{\text{high}}(x)$
5. Commit and output $[t_{\text{lo}}]_1, [t_{\text{mid}}]_1, [t_{\text{high}}]_1$

### Zero test

#### Theoretical Background
Let $f(x)$ be a polynomial defined over a domain $H$. If $f(x)$ evaluates to zero for every element in $H$, it follows that every element of $H$ is a root of the polynomial. Therefore, we can express $f(x)$ as:
$$
f(x) = g(x) Z_H(x),
$$
where $Z_H(x)$ is the vanishing polynomial defined over $H$. The polynomial $Z_H(x)$ has the property that $Z_H(h) = 0$ for all $h \in H$. This implies that $f(x)$ is zero on the entire domain $H$ if and only if it is divisible by $Z_H(x)$.

#### Divisibility Check
To verify that $f(x)$ is divisible by $Z_H(x)$, the verifier will perform a check at a randomly chosen point $z$:
$$
f(z) \stackrel{?}{=} g(z) Z_H(z).
$$
This equation provides a method to confirm the divisibility of $f(x)$ by $Z_H(x)$ through evaluation at the point $z$.

#### Security of the Check
The validity of this check hinges on the fact that if $f(x)$ is not zero over the domain $H$, it cannot be expressed as $f(x) = g(x) Z_H(x)$ for any polynomial $g(x)$. Consequently, if $f(z) \neq g(z) Z_H(z)$, the verifier can conclude that $f(x)$ does not evaluate to zero across the entire domain.

##### Commitment Scheme Utilization
To ensure the evaluations $f(z)$ and $g(z)$ correspond to their respective polynomials $f(x)$ and $g(x)$, we utilize the KZG polynomial commitment scheme. This scheme allows for the commitment to the polynomials while ensuring that the values can be verified without revealing the polynomials themselves.

#### Protocol Overview


The verification protocol can be structured as a non-interactive proof system utilizing an oracle $\mathcal{H}$ to generate a challenge $z$ based on the current transcript. The steps of the protocol are as follows:

1. **Commitment Phase**: The prover commits to the polynomial $f(x)$ using the KZG commitment scheme, obtaining a commitment $[f(x)]$.

2. **Challenge Generation**: The verifier queries the oracle $\mathcal{H}$, which produces a random challenge $z$ based on the current state of the transcript.

3. **Evaluation and Response**:
- The prover evaluates $f(z)$ and $Z_H(z)$ and computes $g(z)$ such that the equation holds.
- The prover sends the evaluations $f(z)$ and $g(z)$ to the verifier along with the commitment.

4. **Verification**: The verifier checks the equality:
$$
f(z) \stackrel{?}{=} g(z) Z_H(z).
$$
If this holds true, the verifier concludes that $f(x)$ evaluates to zero on the domain $H$.

### Checking permutation polynomial

#### Initial Condition
The first criterion for verifying the polynomial $z(x)$ is to ensure that:
$$
z(\omega^0) = 1,
$$
where $\omega$ is a primitive root of unity. If this condition does not hold, we need to validate the cumulative product given by:
$$
z(\omega^i) = \prod_{1 \leq j < i} \frac{p(j)}{q(j)},
$$
which states that the evaluation of $z(x)$ at certain points corresponds to the product of the ratios of polynomials $p(j)$ and $q(j)$.

#### Polynomial Equivalence Conditions
To formally verify $z(x)$, we must check the following conditions:

1. **Evaluation Check**:
$$
(z(x) - 1) L_1(x) = 0,
$$
where $L_1(x)$ is a linear polynomial that vanishes at $\omega^0$. This condition ensures that $z(x)$ correctly evaluates to 1 at this root.

2. **Functional Relation**:
$$
z(x) \tilde{p}(x) = \tilde{q}(x) z(x \omega),
$$
where $\tilde{p}(x)$ and $\tilde{q}(x)$ are defined as:
$$
\tilde{p}(x) = (a(x) + x\beta + \gamma)(b(x) + k_1 x\beta + \gamma)(c(x) + k_2 x\beta + \gamma),
$$
$$
\tilde{q}(x) = (a(x) + S_{\sigma_1}(x) \beta + \gamma)(b(x) + S_{\sigma_2}(x) \beta + \gamma)(c(x) + S_{\sigma_3}(x) \beta + \gamma).
$$
This condition ensures that the mappings defined by $\tilde{p}(x)$ and $\tilde{q}(x)$ conform to the expected relationships that $z(x)$ must satisfy as a permutation polynomial.

#### Functions $\tilde{p}(x)$ and $\tilde{q}(x)$

##### Rationale for Using $\tilde{p}(x)$ and $\tilde{q}(x)$
The functions $\tilde{p}(x)$ and $\tilde{q}(x)$ are derived from the interpolations of the values $w$ and $\sigma^*$, rather than directly from evaluations at the roots of unity as is the case for $p(x)$ and $q(x)$. This means that both $\tilde{p}(x)$ and $\tilde{q}(x)$ agree on the evaluation domain $H$:
$$
\forall i \in [0, 1, \ldots, n - 1]: p(i) = \tilde{p}(\omega^i) \text{ and } q(i) = \tilde{q}(\omega^i).
$$
The use of $\tilde{p}(x)$ and $\tilde{q}(x)$ allows the verifier to check the correctness of the permutation polynomial with respect to the original polynomials $a(x), b(x), c(x)$ that interpolate $w$. This establishes a foundational verification mechanism, ensuring that the prover's computations are based on the correct input values.

### Computing the Quotient Polynomial $t(x)$

#### Composition of $t(x)$
The quotient polynomial $t(x)$ can be conceptually complex, but it can be systematically decomposed into three parts:
$$
t(x) = t_1(x) \frac{1}{Z_H(x)} + t_2(x) \frac{\alpha}{Z_H(x)} + t_3(x) \frac{\alpha^2}{Z_H(x)},
$$
where:
- $t_1(x) = (a(x) q_l(x) + b(x) q_r(x) + c(x) q_o(x) + a(x) b(x) q_m(x) + PI(x) + q_{ci})$
- $t_2(x) = ( \tilde{p}(x) z(x)) - ( \tilde{q}(x) z(\omega x))$
- $t_3(x) = (z(x) - 1) L_1(x)$

#### Explanation of Each Component
1. **First Component $t_1(x)$**: This part ensures that each arithmetic gate is evaluated correctly. If $t_1(x)$ evaluates to zero at $\omega^i$, it signifies that gate $i$ has been computed correctly.

2. **Second Component $t_2(x)$**: This component corresponds to the verification check for the equality $\tilde{p}(x) z(x) = \tilde{q}(x) z(x \omega)$. Rearranging gives:
$$
\tilde{p}(x) z(x) - \tilde{q}(x) z(x \omega) = 0,
$$
which verifies the relationship between $\tilde{p}(x)$ and $\tilde{q}(x)$ under the polynomial $z(x)$.

3. **Third Component $t_3(x)$**: This is the verification for the first condition $z(\omega^0) = 1$, ensuring the polynomial $z(x)$ meets the necessary initialization condition.

### Security Considerations
Each component $t_1(x)$, $t_2(x)$, and $t_3(x)$ is divided by the vanishing polynomial $Z_H(x)$ and multiplied by coefficients $(1, \alpha, \alpha^2)$. This multiplication serves to enhance security by preventing straightforward exploits. For instance, if $t_1(x) = 0$ and $t_2(x) = -t_3(x)$, it could falsely suggest that $t(x) = 0$ without all components being valid. Multiplying by random linear combinations mitigates this risk and is a standard practice in cryptographic proofs.

### Splitting the Quotient Polynomial

#### Motivation for Degree Constraints
The degree of $t(x)$ must be controlled to adhere to the assumptions made during the Structured Reference String (SRS) setup. Specifically, we aim to ensure that the polynomials involved maintain a maximum degree of $n$. This limitation is crucial for the efficiency of evaluations and the overall performance of the cryptographic protocol.

#### Decomposition of $t(x)$
We can express $t(x)$ in a split form:
$$
t(x) = t_{lo}'(x) + x^n t_{mid}'(x) + x^{2n} t_{hi}'(x),
$$
where:
- $t_{lo}'(x)$: a polynomial of degree less than $n$,
- $t_{mid}'(x)$: a polynomial of degree less than $n$,
- $t_{hi}'(x)$: a polynomial with a maximum degree of $n + 5$.

#### Degree Analysis of $t(x)$
The maximum degree of $t(x)$ is determined primarily by the term $t_2(x)$, which involves products of polynomials $a(x)$, $b(x)$, $c(x)$, and the permutation polynomial $z(x)$. Each of these polynomials has specific degree limits:
- $a(x), b(x), c(x)$ have a maximum degree of $n + 1$,
- $z(x)$ has a maximum degree of $n + 2$.

Thus, the combined maximum degree before division by $Z_H(x)$ would be $4n + 5$. However, since $t_2(x)$ is divided by the vanishing polynomial $Z_H(x)$ with a degree of $n$, the resulting maximum degree of $t(x)$ is:
$$
\text{Degree}(t(x)) = 4n + 5 - n = 3n + 5.
$$

#### Representation of $t(x)$
The polynomial $t(x)$ can thus be expressed in terms of its coefficients:
$$
t(x) = c_0 + c_1 x + c_2 x^2 + \ldots + c_{3n + 5} x^{3n + 5}.
$$
From this representation, we can extract the components as follows:
- **Low Degree Component**:
$$
t_{lo}'(x) = c_0 + c_1 x + c_2 x^2 + \ldots + c_{n - 1} x^{n - 1},
$$
- **Middle Degree Component**:
$$
t_{mid}'(x) = \frac{c_n x^n + c_{n + 1} x^{n + 1} + \ldots + c_{2n - 1} x^{2n - 1}}{x^n},
$$
- **High Degree Component**:
$$
t_{hi}'(x) = \frac{c_{2n} x^{2n} + c_{2n + 1} x^{2n + 1} + \ldots + c_{3n + 5} x^{3n + 5}}{x^{2n}}.
$$

#### Random Coefficient Concealment
To ensure the privacy of the polynomial commitments and maintain the protocol's zero-knowledge properties, the prover introduces random coefficients $b_{10}, b_{11} \in \mathbb{F}_p$ to disguise the polynomials:
- **Low Degree Polynomial**:
$$
t_{lo}(x) = t_{lo}'(x) + b_{10} x^n,
$$
- **Middle Degree Polynomial**:
$$
t_{mid}(x) = t_{mid}'(x) - b_{10} + b_{11} x^n,
$$
- **High Degree Polynomial**:
$$
t_{hi}(x) = t_{hi}'(x) - b_{11}.
$$

Note that we have $t(x) = t_{lo}(x) + x^n t_{mid}(x) + x^{2n} t_{hi}(x)$.

### Commitment Computation
Finally, we compute the commitments for each of the split polynomials:
$$
[t_{lo}]_1, \quad [t_{mid}]_1, \quad [t_{hi}]_1,
$$
and proceed to the next phase of the protocol, where we will compute the polynomial openings and illustrate a technique to minimize the number of openings required.

## Round 4

Round overview:
1. Compute evaluation challenge $\mathfrak{z} = \mathcal{H}(\text{transcript})$
2. Compute and output opening evaluations $\bar{a}, \bar{b}, \bar{c}, \bar{z_{\omega}}, \bar{S}_{\sigma_1}, \bar{S}_{\sigma_2}$

### Linearisation polynomial

Consider the identity:

$$
f_1(x) f_2(x) - f_3(x) = 0
$$

for $x$ in a domain $H$. In the traditional approach, the prover commits to the polynomials $f_1, f_2,$ and $f_3$ and provides their evaluations at a random point $\mathfrak{z}$:

$$
\bar{f}_1 = f_1(\mathfrak{z}), \quad \bar{f}_2 = f_2(\mathfrak{z}), \quad \bar{f}_3 = f_3(\mathfrak{z}).
$$

The verifier then checks the condition:

$$
\bar{f}_1 \bar{f}_2 - \bar{f}_3 \stackrel{?}{=} 0.
$$

This method requires the transmission of three field elements, which can be inefficient.

#### Linearization Technique

To optimize this process, we propose a linearization trick that reduces the number of communicated elements to two. The key is to construct a linear polynomial $l(x)$ defined as:

$$
l(x) = \bar{f}_1 f_2(x) - f_3(x).
$$

##### Commitments and Openings

The prover commits to the polynomials $[f_1]_1, [f_2]_1,$ and $[f_3]_1$. Instead of sending all three evaluations, the prover sends:

1. $\bar{f}_1 = f_1(\mathfrak{z})$
2. $\bar{l} = \bar{f}_1 f_2(\mathfrak{z}) - f_3(\mathfrak{z})$

In this scheme, the verifier can reconstruct the commitment to the linear polynomial $l(x)$:

$$
[l]_1 = \bar{f}_1 [f_2]_1 - [f_3]_1.
$$

This relationship leverages the properties of the group formed by the commitments, where one can add commitments but cannot directly multiply them.

##### Verification

The verifier checks the correctness of the proof by confirming:

$$
\bar{l} \stackrel{?}{=} 0.
$$

Since $l(x)$ is constructed as:

$$
l(x) = \bar{f}_1 f_2(x) - f_3(x),
$$

the condition $\bar{l} = 0$ implies:

$$
\bar{f}_1 \bar{f}_2 - \bar{f}_3 \stackrel{?}{=} 0.
$$

Thus, the verification process remains intact while reducing the number of communicated field elements from three to two.

### **Polynomial Openings in PlonK**

#### **Polynomial Evaluations at Challenge Point $\mathfrak{z}$**

The prover evaluates a set of polynomials at the challenge point $\mathfrak{z}$. These evaluations are commonly referred to as *openings*. The general form of the polynomial openings is as follows:

- $\bar{a} = a(\mathfrak{z})$
- $\bar{b} = b(\mathfrak{z})$
- $\bar{c} = c(\mathfrak{z})$

Here, $a$, $b$, and $c$ are polynomials representing various components of the proof, such as commitments to secrets or intermediate values. The values $\bar{a}$, $\bar{b}$, and $\bar{c}$ are the evaluations of these polynomials at the challenge point $\mathfrak{z}$. These evaluations serve as a commitment to the values of $a$, $b$, and $c$ at $\mathfrak{z}$, and the verifier will check the consistency of these evaluations during the proof verification phase.

#### **Permutation Polynomial Evaluations**

The PlonK protocol involves permutation polynomials $S_{\sigma_1}$ and $S_{\sigma_2}$, which are crucial for verifying the correctness of the permutation relations within the proof. These polynomials are evaluated at the challenge point $\mathfrak{z}$ to produce the corresponding values:

- $\bar{S}_{\sigma_1} = S_{\sigma_1}(\mathfrak{z})$
- $\bar{S}_{\sigma_2} = S_{\sigma_2}(\mathfrak{z})$

However, there is a subtlety in the evaluation of the third permutation polynomial $S_{\sigma_3}$. Notably, $\bar{S}_{\sigma_3}$ is **not** included in the evaluations sent by the prover. This omission is intentional and contributes to the non-interactive nature of the proof system. The prover only sends two permutation polynomial evaluations ($\bar{S}_{\sigma_1}$ and $\bar{S}_{\sigma_2}$) because these suffice for the verifier to check the validity of the permutation relations.

#### **The Evaluation at $\mathfrak{z} \omega$ for Permutation Polynomials**

An interesting aspect of the PlonK protocol is the evaluation of permutation polynomials at $\mathfrak{z} \omega$ instead of just $\mathfrak{z}$. Specifically, the evaluation of the permutation polynomials occurs at the point $\bar z_\omega = z(\omega \mathfrak{z})$, where $\omega$ is a generator of a cyclic group, and $z$ is a polynomial encoding the transformation. The reason for this change lies in the structure of the permutation checks and ensures that the prover cannot trivially manipulate the permutation relations.

This transformation, $\mathfrak{z} \omega$, introduces a shift in the domain of the permutation polynomials. The evaluation at this shifted point ensures that the permutation consistency checks are carried out in a manner that reflects the underlying group structure, providing additional security guarantees against certain types of manipulation.

## Round 5

Round overview:
1. Compute opening challenge $v \in \mathbb{F}_p = \mathcal{H}(\text{transcript})$
2. Compute linearisation polynomial $r(x)$
3. Compute opening proof polynomial $W_\mathfrak{z}(x)$
4. Compute opening proof polynomial $W_{\mathfrak{z}\omega}(x)$
5. Calculate commitments $[W_\mathfrak{z}]_1, \quad [W_{\mathfrak{z}\omega}]_1$
6. Return proof $\pi$

### **Linearization of the Polynomial Quotient $t(x)$**

#### **Polynomial Decomposition and Degree Reduction**

In the third round, the quotient polynomial $t(x)$ is divided into three polynomials $t_1(x), t_2(x), t_3(x)$, which are then restructured as follows:

$$
t(x) = t_{lo}(x) + x^n t_{mid}(x) + x^{2n} t_{hi}(x)
$$

This division is intended to reduce the degree of the original polynomial $t(x)$ by splitting it into lower-degree components. Specifically, the polynomial $t(x)$ is expressed as a linear combination of these three parts, each multiplied by progressively higher powers of $x$, which allows for easier manipulation and evaluation during the proof process.

The division also results in the following key equation, which is central to the linearization process:

$$
0 = t_1(x) + \alpha t_2(x) + \alpha^2 t_3(x) - Z_H(x) \left( t_{lo}(x) + x^n t_{mid}(x) + x^{2n} t_{hi}(x) \right)
$$

Here, $\alpha$ is a constant and $Z_H(x)$ is a polynomial associated with the homomorphic commitment to the polynomial $t(x)$. The expression above forms the basis for the construction of the linearization polynomial $r(x)$, which will be used to verify the correctness of the proof.

#### **The Linearization Polynomial $r(x)$**

The next step is to construct the linearization polynomial $r(x)$, which represents a combination of the polynomials $t_1(x), t_2(x), t_3(x)$, and certain evaluated polynomials such as $\bar{a}, \bar{b}, \bar{c}, \bar{z_\omega}$, and $\bar{S_{\sigma_1}}, \bar{S_{\sigma_2}}$, all of which were computed in the fourth round of the protocol. The linearization polynomial is defined as:

$$
r(x) = r_1(x) + \alpha r_2(x) + \alpha^2 r_3(x) - Z_H(\mathfrak{z}) \left( t_{lo}(x) + \mathfrak{z}^n t_{mid}(x) + \mathfrak{z}^{2n} t_{hi}(x) \right)
$$

This equation shows how $r(x)$ is composed of three parts:

- $r_1(x)$, which represents the first check corresponding to $t_1(x)$ in the original quotient polynomial.
- $r_2(x)$, which linearizes $t_2(x)$, representing the second permutation check.
- $r_3(x)$, which corresponds to $t_3(x)$ and represents the first permutation check.

Each of these components plays a specific role in verifying the correctness of the proof, as explained in the following sections.

#### **Components of $r_1(x), r_2(x), r_3(x)$**

##### **The Polynomial $r_1(x)$**

The polynomial $r_1(x)$ represents the first check related to the arithmetic circuit in the original polynomial quotient $t_1(x)$. It can be written as:

$$
r_1(x) = \bar{a} \bar{b} q_m(x) + \bar{a} q_l(x) + \bar{b} q_r(x) + \bar{c} q_o(x) + PI(\mathfrak{z}) + q_c(x)
$$

Here, $q_m(x), q_l(x), q_r(x), q_o(x), PI(\mathfrak{z}), q_c(x)$ are various polynomials associated with the arithmetic relations in the circuit, while $\bar{a}, \bar{b}, \bar{c}$ are the evaluated values of the polynomials at the challenge point $\mathfrak{z}$. This term effectively encodes the verification of arithmetic checks on the prover’s commitments.

##### **The Polynomial $r_2(x)$**

The polynomial $r_2(x)$ linearizes the second quotient polynomial $t_2(x)$, corresponding to the second permutation check. It is defined as:

$$
r_2(x) = (\bar{a} + \beta \mathfrak{z} + \gamma)(\bar{b} + \beta k_1 \mathfrak{z} + \gamma)(\bar{c} + \beta k_2 \mathfrak{z} + \gamma) z(x) - (\bar{a} + \beta \bar{s}_{\sigma1} + \gamma)(\bar{b} + \beta \bar{s}_{\sigma2} + \gamma)(\bar{c} + \beta s_{\sigma3}(x) + \gamma) \bar{z}_\omega
$$

This equation captures the linear relation between the evaluated values of the polynomials $\bar{a}, \bar{b}, \bar{c}$ and the permutation polynomials $\bar{s}_{\sigma1}, \bar{s}_{\sigma2}, \bar{s}_{\sigma3}$, which encode the permutation checks in the circuit.

##### **The Polynomial $r_3(x)$**

Finally, $r_3(x)$ corresponds to the first permutation check and is given by:

$$
r_3(x) = (z(x) - 1) L_1(\mathfrak{z})
$$

This term verifies the consistency of the permutation relations encoded in $z(x)$, ensuring that the permutation check holds true for the provided commitments.

### First Opening Proof Polynomial $W_{\mathfrak{z}}(X)$

The first opening proof polynomial $W_{\mathfrak{z}}(X)$ is constructed to prove the evaluation of a set of polynomials $r(x)$, $a(x)$, $b(x)$, $c(x)$, $S_{\sigma_1}(x)$, and $S_{\sigma_2}(x)$ at the point $\mathfrak{z}$. In particular, it verifies the following relations:

$$
r(\mathfrak{z}) = 0
$$
$$
a(\mathfrak{z}) = \bar{a}, \quad b(\mathfrak{z}) = \bar{b}, \quad c(\mathfrak{z}) = \bar{c}
$$
$$
S_{\sigma_1}(\mathfrak{z}) = \bar{S}_{\sigma_1}, \quad S_{\sigma_2}(\mathfrak{z}) = \bar{S}_{\sigma_2}
$$

Here, $\bar{a}, \bar{b}, \bar{c}, \bar{S}_{\sigma_1}, \bar{S}_{\sigma_2}$ are the expected values of the respective polynomials at $\mathfrak{z}$. To verify these equations efficiently, we do not directly check the values of the polynomials at $\mathfrak{z}$, but instead use a series of quotient polynomials that are constructed as follows.

#### Constructing the Proof Polynomial

For each polynomial $f(x)$ (where $f(x)$ is one of the polynomials in the list $r(x), a(x), b(x), c(x), S_{\sigma_1}(x), S_{\sigma_2}(x)$), the opening proof polynomial is constructed as:

$$
\frac{f(x) - \bar{f}}{x - \mathfrak{z}} \quad \text{proves} \quad f(\mathfrak{z}) = \bar{f}
$$

This is done for all relevant polynomials. The prover then combines these individual proof polynomials using a linear combination of random challenges $(1, v, v^2, v^3, v^4, v^5)$, where $v$ is a challenge that is provided by the verifier during the interaction. The challenge is a random value that helps ensure that the proof is non-trivial and prevents the prover from cheating.

The combined polynomial is then given by:

$$
W_{\mathfrak{z}}(X) = \frac{1}{X - \mathfrak{z}} \left(
\begin{aligned}
&r(X) \\
&+ v(a(X) - \bar{a}) \\
&+ v^2(b(X) - \bar{b}) \\
&+ v^3(c(X) - \bar{c}) \\
&+ v^4(S_{\sigma_1}(X) - \bar{S}_{\sigma_1}) \\
&+ v^5(S_{\sigma_2}(X) - \bar{S}_{\sigma_2})
\end{aligned}
\right)
$$

This polynomial $W_{\mathfrak{z}}(X)$ is the opening proof polynomial for the point $\mathfrak{z}$, and it serves the purpose of proving that the aforementioned relations hold at $\mathfrak{z}$. The verifier can check the correctness of the proof by evaluating the polynomial at the challenge value $v$.

### Second Opening Proof Polynomial $W_{\mathfrak{z} \omega}(X)$

In a similar fashion, a second opening proof polynomial is constructed to prove the evaluation of a polynomial $z(x)$ at the point $\mathfrak{z} \omega$, where $\omega$ is a primitive root of unity. This is important in many cryptographic settings where multiple points are used to perform polynomial commitments, and proofs are needed at different evaluation points.

The second opening proof polynomial $W_{\mathfrak{z} \omega}(X)$ is defined as:

$$
W_{\mathfrak{z} \omega}(x) = \frac{z(x) - \bar{z}_\omega}{x - \mathfrak{z} \omega}
$$

Here, $\bar{z}_\omega$ represents the expected value of the polynomial $z(x)$ at $\mathfrak{z} \omega$, and the polynomial proves that the evaluation of $z(x)$ at $\mathfrak{z} \omega$ equals $\bar{z}_\omega$. The key difference between this polynomial and $W_{\mathfrak{z}}(X)$ is that it is constructed for the point $\mathfrak{z} \omega$ rather than $\mathfrak{z}$.

### Return Proof

At the end of this round, the prover can finally send the whole proof:
$$
\pi_{\text{SNARK}} = ([a]_1, [b]_1, [c]_1, [z]_1, [t_{lo}]_1, [t_{mid}]_1, [t_{hi}]_1, [W_\mathfrak{z}]_1, [W_{\mathfrak{z} \omega}]_1, \bar{a}, \bar{b}, \bar{c}, \bar{S}_{\sigma_1}, \bar{S}_{\sigma_2}, \bar{z}_\omega)
$$

Compute multipoint evaluation challenge $u \in \mathbb{F}$:
$$
u = \mathcal{H}(\text{transcript})
$$

## Verification Algorithm for $\pi_{\text{SNARK}}$

The verification process follows a structured sequence of steps to ensure that all commitments, evaluations, and mathematical checks are valid. Below we describe the algorithm in detail.

### Validate Group Membership

The first step in the verification process is to ensure that the provided commitments are valid elements of the elliptic curve group $\mathbb{G}_1$. Specifically, we check that the following commitments:
$$
([a]_1, [b]_1, [c]_1, [z]_1, [t_{\text{lo}}]_1, [t_{\text{mid}}]_1, [t_{\text{hi}}]_1, [W_\mathfrak{z}]_1, [W_{\mathfrak{z} \omega}]_1) \in \mathbb{G}_1^9
$$
lie within the group $\mathbb{G}_1$. For each commitment, the verifier ensures that the elliptic curve equation holds:
$$
y^2 = x^3 + ax + b
$$
where $x$ and $y$ are the coordinates of the elliptic curve point, and $a$ and $b$ are the curve parameters. If any of these commitments fail this check, the proof is rejected.

### Validate Polynomial Evaluations

Next, the verifier checks that the polynomial evaluations provided by the prover are valid. These include:
$$
(\bar{a}, \bar{b}, \bar{c}, \bar{s}_{\sigma_1}, \bar{s}_{\sigma_2}, \bar{z}_{\omega}) \in \mathbb{F}_6
$$
Each of these values must be a valid element of the field $\mathbb{F}_6$, and thus the verifier checks that the evaluations fall within the expected range of the finite field.

### Validate Witness Values

The prover provides a sequence of witness values $(w_i)_{i \in [\ell]}$, which are elements of the field $\mathbb{F}^\ell$. The verifier ensures that each witness value is valid, i.e., $w_i \in \mathbb{F}_p$ for all $i \in [\ell]$.

### Challenge Computation

The verifier computes several challenges $\beta, \gamma, \alpha, \mathfrak{z}, v, u \in \mathbb{F}_p$ based on the common inputs, public input, and the elements of $\pi_{\text{SNARK}}$. The challenges are used to ensure the consistency of the prover's claims. In an interactive protocol, these challenges would be directly generated by the verifier, but in a non-interactive setting, they are derived from the protocol transcript via a random oracle.

### Zero Polynomial Evaluation

The zero polynomial $Z_H(\mathfrak{z})$ is computed at the challenge point $z$ as follows:
$$
Z_H(\mathfrak{z}) = \mathfrak{z}^n - 1
$$
where $n$ is the number of elements in the set $H$. This polynomial vanishes at $\mathfrak{z} = 1$, and its evaluation at $z$ is used in subsequent verification steps.

### Lagrange Polynomial Evaluation

The Lagrange basis polynomial $L_1(\mathfrak{z})$ is computed at the challenge point $\mathfrak{z}$. This polynomial is used for interpolation and is defined as:
$$
L_1(\mathfrak{z}) = \frac{\omega(\mathfrak{z}^n - 1)}{n(\mathfrak{z} - \omega)}
$$
The evaluation of this polynomial is used in the final check for the validity of the commitments and evaluations.

### Public Input Polynomial Evaluation

The public input polynomial $PI(z)$ is constructed from the sequence of witness values $w_i$ and their corresponding Lagrange basis evaluations $L_i(\mathfrak{z})$. The polynomial is evaluated at the challenge point $\mathfrak{z}$ as follows:
$$
PI(\mathfrak{z}) = \sum_{i \in [\ell]} w_i L_i(\mathfrak{z})
$$
The result is a scalar value that is used in the next steps of the verification.

### Compute $r_0$ and $r'(X)$

The verifier computes the constant term $r_0$ of the polynomial $r(X)$, which is used in the commitment check. The constant term is given by:
$$
r_0 = PI(\mathfrak{z}) - L_1(\mathfrak{z})\alpha^2 - \alpha (\bar{a} + \beta \bar{s}_{\sigma_1} + \gamma)(\bar{b} + \beta \bar{s}_{\sigma_2} + \gamma)(\bar{c} + \gamma)\bar{z}_\omega
$$
The remaining part of the polynomial $r'(X)$ is given by:
$$
r'(X) := r(X) - r_0
$$

### Batched Polynomial Commitment Scheme

#### Problem Setup

We assume that a prover has two polynomials $f_1(x)$ and $f_2(x)$ defined over a finite field $\mathbb{F}_p$. The prover commits to these polynomials and wishes to prove the values of $f_1(z)$ and $f_2(z)$ at a challenge point $z \in \mathbb{F}_p$. Specifically, the prover needs to prove the following relationships:

$$
f_1(z) = v_1, \quad f_2(z) = v_2
$$

where $v_1$ and $v_2$ are the claimed evaluations of the polynomials at $z$.

#### Batched Polynomial Commitment Scheme

##### Batched Check Protocol

Rather than verifying each commitment independently, we combine the two polynomials into a single commitment using a random scalar $u \in \mathbb{F}_p$. The evaluation of the combined polynomial at $z$ is then given by the following linear combination:

$$
u \cdot f_1(z) + f_2(z) = u \cdot v_1 + v_2
$$

This approach leverages the linearity of the polynomial evaluation to reduce the number of required checks. For any $u \in \mathbb{F}_p$, if $f_1(z) = v_1$ and $f_2(z) = v_2$, the equation holds true. The security of the scheme relies on the fact that if the prover is honest, the left-hand side will always equal the right-hand side for any random choice of $u$.

##### Significance of the Approach

This method is sound because, for polynomials $f_1$ and $f_2$, which are both evaluated at the same point $z$, the equation will hold for any random value of $u$. More formally, we can conclude that:

$$
f_1(z) = v_1, \quad f_2(z) = v_2 \iff u \cdot f_1(z) + f_2(z) = u \cdot v_1 + v_2
$$

This relation holds with high probability because the random variable $u$ is chosen from a sufficiently large finite field $\mathbb{F}_p$. If the polynomials do not match the claimed values at $z$, the equation will almost certainly not hold for a random choice of $u$.

##### Polynomial for the Combined Commitment

To formalize the combined polynomial, we define the batched polynomial as:

$$
f_{\text{batch}}(x) = u \cdot f_1(x) + f_2(x)
$$

This polynomial represents the linear combination of the two polynomials, $f_1(x)$ and $f_2(x)$, weighted by the scalar $u$. The evaluation of $f_{\text{batch}}(x)$ at $z$ provides the combined value of the evaluations of $f_1(x)$ and $f_2(x)$.

##### Commitment to the Batched Polynomial

The commitment to the batched polynomial $f_{\text{batch}}(x)$ is defined as:

$$
[f_{\text{batch}}]_1 = u \cdot [f_1]_1 + [f_2]_1
$$

where $[f_1]_1$ and $[f_2]_1$ are the commitments to the polynomials $f_1(x)$ and $f_2(x)$, respectively. The prover only needs to send the commitment $[f_{\text{batch}}]_1$ and a proof of evaluation for $f_{\text{batch}}(x)$ at $z$, which simplifies the verification process.

### Batched Polynomial Commitment $[D]_1$

The first part of the batched polynomial commitment is computed as follows:
$$
[D]_1 := [r']_1 + u \cdot [z]_1
$$
where the term $u \cdot [z]_1$ corresponds to a challenge-based scalar multiplication. The term $[D]_1$ is updated with several other terms, including products of the witness values, the commitments to the polynomials $q_M$, $q_L$, $q_R$, $q_O$, and $q_C$, and terms involving the challenges $\beta$, $\gamma$, and $\mathfrak{z}$.

$$
[D]_1 := \begin{aligned}
& \bar{a} \bar{b} \cdot [q_M]_1 + \bar{a} \cdot [q_L]_1 + \bar{b} \cdot [q_R]_1 + \bar{c} \cdot [q_O]_1 + [q_C]_1 \\
& + \left( (\bar{a} + \beta \mathfrak{z} + \gamma)(\bar{b} + \beta k_{1} \mathfrak{z} + \gamma)(\bar{c} + \beta k_{2} \mathfrak{z} + \gamma) \alpha + L_1(\mathfrak{z}) \alpha^2 + u \right) \cdot [z]_1 \\
& - \left( (\bar{a} + \beta \bar{s}_{\sigma 1} + \gamma)(\bar{b} + \beta \bar{s}_{\sigma 2} + \gamma) \alpha \beta \bar{z}_w \right) \cdot [s_{\sigma 3}]_1 \\
& - Z_H(\mathfrak{z}) \left( [t_{lo}]_1 + \mathfrak{z}^n \cdot [t_{mid}]_1 + \mathfrak{z}^{2n} \cdot [t_{hi}]_1 \right)
\end{aligned}
$$

### Full Batched Polynomial Commitment $[F]_1$

Next, the full batched polynomial commitment is computed by adding several terms:
$$
[F]_1 := [D]_1 + v \cdot [a]_1 + v^2 \cdot [b]_1 + v^3 \cdot [c]_1 + v^4 \cdot [s_{\sigma_1}]_1 + v^5 \cdot [s_{\sigma_2}]_1
$$
This commitment includes both the verifier's challenges and the commitments to various polynomials from the prover's input.

### Group-Encoded Batch Evaluation $[E]_1$

The group-encoded evaluation $[E]_1$ is computed as:
$$
[E]_1 := \left( -r_0 + v \bar{a} + v^2 \bar{b} + v^3 \bar{c} + v^4 \bar{s}_{\sigma_1} + v^5 \bar{s}_{\sigma_2} + u \bar{z}_\omega \right) \cdot [1]_1
$$
where $[1]_1$ is the identity element in the elliptic curve group.

### Batched Pairing Check

Finally, the verifier performs the batched pairing check:
$$
e([W_\mathfrak{z}]_1 + u \cdot [W_{\mathfrak{z} \omega}]_1, [\tau]_2) = e(\mathfrak{z} \cdot [W_\mathfrak{z}]_1 + u \mathfrak{z} \omega \cdot [W_{\mathfrak{z} \omega}]_1 + [F]_1 - [E]_1, [1]_2)
$$
where $e$ denotes the elliptic curve pairing operation. This check ensures the consistency of all the commitments and evaluations and confirms that the proof is valid.

## References

1. https://eprint.iacr.org/2019/953.pdf
2. https://www.maya-zk.com/blog/plonk-overview
3. https://brilliant.org/wiki/schwartz-zippel-lemma/