# PLonk Arithmetization

So far, we have explored the structure of STARKs, which had broken down into three key parts:

* **Trace Generation**: In the first part, we generated the trace, constructed the trace polynomial using Lagrange interpolation, and commit to that polynomial.
* **Applying Constraints**: The second part involves applying constraints to the trace polynomial, ensuring it satisfies the desired properties.
* **Commitment**: Finally, in the third part, we commit to all the FRI layers derived during the process.

From this structure, we can deduce the central components required to build a proof system: the trace and its corresponding constraints. Once these are defined, we can proceed with the commitments.

In this blog, we will delve into PLONK arithmetization, exploring how constraints can be structured within tables.

## PAIRs - AIRs with preprocessed columns
In the preprocessed AIR, we introduce t additional parameter as a predefined column $c_1, \ldots, c_t \in F^n.$ Now, our trace contains t predefined columns in addition to w witness column supplied by the prover. These t predefined columns refer to selectors, and are introduced to construct some non-uniform constraints.
Let’s consider an example where we use a selector column, where t=2 and w=2
t={s1,s2} and w={a,b}.
**PAIR for addition and multiplication.** Let’s construct a **PAIR** where we perform an addition on some rows, and a multiplication on other rows. For this purpose, we define the “addition selector” $s_1$, and the “multiplication selector” $s_2$. The constraint polynomial is:

$$
f(X_1, X_2, X_1^{\text{next}}, X_2^{\text{next}}) = s_1 \cdot \left(A^{\text{next}} - (A + B)\right) + s_2 \cdot \left(A^{\text{next}} - A \cdot B\right).
$$

Let’s check the constraint on row $i = 1$, where only the addition operation is enabled:

$$
f(X_1, X_2, X_1^{\text{next}}, X_2^{\text{next}}) = 1 \cdot (1 - (0 + 1)) + 0 \cdot (1 - (0 \cdot 1)) = 0;
$$

and row $i = 3$, where both operations are enabled:

$$
f(X_1, X_2, X_1^{\text{next}}, X_2^{\text{next}}) = 1 \cdot (4 - (2 + 2)) + 1 \cdot (4 - (2 \cdot 2)) = 0.
$$

\
\begin{array}{|c|c|c|c|c|}
\hline
\text{step} & s_1 & s_2 & a & b \\
\hline
i = 1 & 1 & 0 & 0 & 1 \\
i = 2 & 0 & 1 & 1 & 2 \\
i = 3 & 1 & 1 & 2 & 2 \\
i = 4 & 0 & 1 & 4 & 0 \\
\hline
\end{array}

---

## Randomized AIR with Preprocessing (RAP)
This model allows for a round of interaction with the verifier. The verifier sends randomness. In a later round, randomness from the earlier rounds can be used as variables in constraints. This enables local constraints( between the adjacent rows) to check global properties (over all the rows). This AIR will be used to check the multiset equality between two sets.
Let’s illustrate an example of RAP. Suppose we have a width-2 AIR and want to check that the columns provided by the prover are permutations of each other.
Assume that the values of one column are {a1,...,an} and values of other column are {b1,....,bn}
From the Schwartz-Zippel Lemma, we know that to check they are a permutation of each other, it suffices to check that for a uniformly chosen $\gamma \in F$, we have with high probability:

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

With high probability over $\gamma$, the factors of the RHS are all non-zero, and in that case, this is equivalent to:

$$
\prod_{i \in [n]} \frac{(a_i + \gamma)}{(b_i + \gamma)} = 1.
$$

A RAP of length $n+1$ and total width 3 can be formed like this:

1. The prover first sends the columns $(a_1, \ldots, a_n, 0)$ and $(b_1, \ldots, b_n, 0)$.
2. The verifier sends random $\gamma \in F$.
3. The prover uses the verifier challenges gamma to construct the running product $\vec{Z}$ (1,z1,..,zn) such that for each $i \in [n]$:

$$
z_i = \prod_{1 \leq j \leq i} \frac{(a_j + \gamma)}{(b_j + \gamma)}.
$$

To check the correctness of RAP:
Let us consider an example where $b$ simply contains a shift of the elements in $a$. To check that $z$ (vector) was correctly constructed as a running product, we introduce column $z$ to the execution trace.

$$
z_i = \prod_{1 \leq j \leq i} \frac{(a_j + \gamma)}{(b_j + \gamma)} \quad \forall i \in [n]
$$

$$
\begin{array}{|c|c|c|c|}
\hline
\text{step} & a & b & z \\
\hline
i = 1 & a_1 & a_2 & 1 \\
i = 2 & a_2 & a_3 & \frac{(a_1 + \gamma)}{(a_2 + \gamma)} \\
i = 3 & a_3 & a_1 & \frac{(a_1 + \gamma)(a_2 + \gamma)}{(a_2 + \gamma)(a_3 + \gamma)} \\
i = 4 & a_1 & a_2 & \frac{(a_1 + \gamma)(a_2 + \gamma)(a_3 + \gamma)}{(a_2 + \gamma)(a_3 + \gamma)(a_1 + \gamma)} \\
\hline
\end{array}
$$

To check the correctness of the $z$-vector, we can check the following constraints on column $z$:
1. Boundary constraint that the third column starts with one.
2. At each step, we check the constraint:

$$
Z^{\text{next}} \cdot (B + \gamma) - Z \cdot (A + \gamma) = 0.
$$

As an example, applying this on the row $i = 2$ checks:

$$
\frac{(a_1 + \gamma)(a_2 + \gamma)}{(a_2 + \gamma)(a_3 + \gamma)} \cdot (a_3 + \gamma) - \frac{(a_1 + \gamma)}{(a_2 + \gamma)} \cdot (a_2 + \gamma) = 0.
$$

3. At the final row $i = n$:

$$
z_n = \prod_{i \in [n]} \frac{(a_i + \gamma)}{(b_i + \gamma)} = 1.
$$

The second constraint enforces that the $z$ is accumulating the products of $a$ and $b$ as expected.

---

## Arguments
For proving the brainfuck ISA, we use two related but distinct arguments known as permutation and evaluation arguments.

### Permutation Argument
To check that two tables contain the same set of values, possibly in a different order, we use the permutation argument. This technique is similar to the RAP, but instead of proving multiset equality on a single column, we prove it on multiple columns. We can assume that the prover has access to random scalars $a,b,c,..$supplied by the verifier. The prover can use these scalars to compress multiple columns to one, by taking a weighted vectorial sum.
This construction of taking weighted sum allows us to reduce a claim about the identical sets of rows of two tables, to an equivalent but easier-to-prove a claim about the identical sets of two rows.
For example- if a table has 3 columns as $x,y,z$ then the verifier passes the challenges as $a,b,c$ and the prover will take the vectorial sum of all 3 columns as $ax+by+cz$ to reduce the permutation claim on the 3 column to one column of the weighted vectorial sum
The verifier uses the same scalars to compute the same weighted sum in select coordinates but obviously never accesses the entire vector, and the verifier checks whether the value computed by him will be equal to the value supplied by the prover at that point or not.
Both tables are now reduced to a single column by taking the weighted vectorial sum. Let the element in these columns be $(c_i)_i$ and $(k_i)_i$ and we can use the same algorithm as used in RAP and form an extended column that computes the products $\prod_i (\alpha - c_i)$ and $\prod_i (\alpha - k_i)$, respectively. Specifically, the transition constraint for this extension column is:

$$
\forall i > 0: \ e_{i-1} \cdot (\alpha - c_i) = e_i
$$

where $e_i$ represents the value from the extension column.

$$
\begin{array}{|c|c|}
\hline
c_i & e \\
\hline
w & \alpha - w \\
x & (\alpha - w)(\alpha - x) \\
y & (\alpha - w)(\alpha - x)(\alpha - y) \\
z & (\alpha - w)(\alpha - x)(\alpha - y)(\alpha - z) \\
\hline
\end{array}
$$
$$
\begin{array}{|c|c|}
\hline
k_i & e \\
\hline
x & \alpha - x \\
y & (\alpha - x)(\alpha - y) \\
w & (\alpha - x)(\alpha - y)(\alpha - w) \\
z & (\alpha - x)(\alpha - y)(\alpha - w)(\alpha - z) \\
\hline
\end{array}
$$
If the two columns do contain the same values but in a different order, then the products should be the same:

$$
\prod_i (\alpha - c_i) = \prod_i (\alpha - k_i).
$$

----

### Evaluation Arguments
Evaluation Arguments will be used when we need to check that one table’s list of rows appears in order as a sublist of another table’s list of rows.
Both table columns are compressed into one column with the same technique of weighted vectorial sum with verifier-supplied weights $a,b,c,..$ Additionally, the larger table has to have an indicator column or we can say the selector column, that takes the value 1 if row i is a part of the sublist relation and 0 if it is not and we need to show $(c_i)_{i|j_i=1}$ = $(k_j)_j$
The evaluation argument is somewhat similar to the permutation, there is only one difference in the permutation argument we compute the running product, and in the case of the evaluation argument we will compute the running sum multiplied by some random element supplied by the verifier.
The transition constraints for the evaluation argument are given by
$$
\forall i > 0 : e_i = j_i \cdot (\alpha e_{i-1} + c_i) + (1 - j_i) \cdot e_{i-1} \text{ for the larger table}
$$

$$
\forall j > 0 : e_j = \alpha e_{j-1} + k_j \text{ for the smaller one.}
$$

Note that the factors $j_i$ and $(1 - j_i)$ enforce the conditional accumulation of a new term. Specifically, in un-indicated rows, the running sum does not change, whereas in indicated rows it changes in the same way that it changes in the smaller table.

$$
\begin{array}{|c|c|c|}
\hline
j_i & c_i & e_i \\
\hline
0 & u & 0 \\
1 & x & x \\
0 & v & x \\
1 & y & \alpha x + y \\
0 & w & \alpha x + y \\
1 & z & \alpha^2 x + \alpha y + z \\
\hline
\end{array}
$$

$$
\begin{array}{|c|c|}
\hline
c_j & e_j \\
\hline
x & x \\
y & \alpha x + y \\
z & \alpha^2 x + \alpha y + z \\
\hline
\end{array}
$$

You can see that the final term will be equal in both the tables if the larger table contains the sublist of the smaller table in the same order. However, if the order in the larger table is different from that of the smaller table, then the value computed at the last will also differ.

---
We have covered Plonk Arithmetization and the concept of Arguments successfully. We will now look at the working of our zkVM (STARK Engine) in the [next blogpost](https://hackmd.io/@Muskan05/rJ-exWiLJl).