###### tags: `Aztec Connect Specs`

# Implementation of the Simplified Plonk
**Disclaimer:** This documentation was written on August, 2021. It is intended to give readers a high-level understanding. The codebase is the canonical source of truth, and over time this document might fall behind the implementation details of the code.
##### Author: Arijit
{%hackmd theme-dark %}
The latest [version](https://eprint.iacr.org/2019/953.pdf) of the Plonk paper (a note on this can be found [here](https://hackmd.io/RHldDrETShifpfSVBh4RxQ)) differs slightly from the actual implementation (based on an older [version](https://eprint.iacr.org/eprint-bin/getfile.pl?entry=2019/953&version=20200903:165011&file=953.pdf), implementation follows [this](https://raw.githubusercontent.com/arielgabizon/plonk-addendum/master/plonk-pubinputs.pdf) version for public inputs). In this project, we have implemented the latest version (we call this the simplified Plonk here and in the code).

*PR*: [https://github.com/AztecProtocol/aztec2-internal/pull/469](https://github.com/AztecProtocol/aztec2-internal/pull/469)

*Acknoledgement*: This project would not have been possible without the help and support I have received from Suyash, Zac, and Ariel. A good starting point might be [this](https://app.gitbook.com/@aztec-protocol/s/mini-barretenberg-projects/barretenberg-docs/components-of-barretenberg) document written by Suyash which gives an overview of the codebase.

### Overview of the Changes:
In the simplified Plonk, the definition of the linearization polynomial $r(X)$ is changed in such a way that it verifies the commitments $[t_{lo}]_1$, $[t_{mid}]_1$, and $[t_{hi}]_1$ and evaluates to zero at point $\mathfrak{z}$. As a result, we do not have to include $\bar{r}=r(\mathfrak{z}) = 0$ in the transcript. This reduces the proof size.

In the verifier side, to reduce the number of scalar multiplications, $r(X)$ is split into constant and non-constant terms as follows.
$$
r(X) = r'(X) + r_0.
$$
While computing $[D]_1$, we consider $r'(X)$ instead of $r(X)$. This results in saving in terms of scalar multiplications. In step 11 of the verifier, we include $-r_0$ in $[E]_1$. The negation effectively brings back $r(X)=r'(X) + r_0$ when we do $[F]_1 - [E]_1$ in step 12 of the verifier.

To implement the above changes, we need to make the following modifications in the code:
1. We need to change the definition of $r(X)$ which is computed in the fifth round in `prover.cpp`.
2. We need to change the numerator of $W_z(X)$ accordingly. The numerator is computed in the `batch_open()` function invoked in the sixth round in `prover.cpp`.
3. In step 8 of the verifier, we need to compute the constant term $r_0$ of the polynomial $r(X)$.
4. In step 9, we need to set the $\nu$ challenge to 1.
5. In step 10, we add $-Z_H(\mathfrak{z})(t_{lo}(X)+\mathfrak{z}^nt_{mid}(X)+\mathfrak{z}^{2n}t_{hi}(X))$ to $[F]_1$ instead of $t_{lo}(X)+\mathfrak{z}^nt_{mid}(X)+\mathfrak{z}^{2n}t_{hi}(X)$.
6. In step 11, we add $-r_0$ in place of $(\bar{t} + \nu \bar{r})$ to $[E]_1$. Note that in implementation, we avoid taking powers of $\nu$ and instead generate them independently. For this reason, we do not have to change the challenges for $\bar{a}, \bar{b}$, and so on.

Below we describe how we have incorporated the above changes.
### Changes at the Fifth Round:
1. We need to change the linearization polynomial as follows
\begin{align}
r(X) =& \ (\bar{a}\bar{b}q_M(X) + \bar{a}q_L(X) + \bar{b}q_R(X) + \bar{c}q_O(X) +q_C(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)\alpha \\
&− (\bar{a} + \beta\bar{s}_{\sigma 1}+ \gamma)( \bar{b}+ \beta \bar{s}_{\sigma 2} + \gamma)\color{red}{( \bar{c}}+ \beta S_{\sigma 3}(X) + \color{red}{\gamma)}\bar{z}_{\omega}\alpha \\
&+ \alpha^3(z(X)-\color{red}{1}) L_1(\mathfrak{z}) + \color{red}{ \alpha^2(\bar{z}_{\omega}-\Delta_{PI}) L_n(\mathfrak{z}) - Z_H(\mathfrak{z})(t_{lo}(X)+\mathfrak{z}^nt_{mid}(X)+\mathfrak{z}^{2n}t_{hi}(X))} \\
& = (\bar{a}\bar{b}q_M(X) + \bar{a}q_L(X) + \bar{b}q_R(X) + \bar{c}q_O(X)+ +q_C(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)\alpha \\
&− (\bar{a} + \beta\bar{s}_{\sigma 1}+ \gamma)( \bar{b}+ \beta \bar{s}_{\sigma 2} + \gamma)\beta S_{\sigma 3}(X)\bar{z}_{\omega}\alpha + \alpha^3 z(X) L_1(\mathfrak{z}) \\
& − \color{green}{(\bar{a} + \beta\bar{s}_{\sigma 1}+ \gamma)( \bar{b}+ \beta \bar{s}_{\sigma 2} + \gamma)(\bar{c}+\gamma)\bar{z}_{\omega}\alpha} - \color{green}{\alpha^3 L_1(\mathfrak{z}) + \alpha^2(\bar{z}_{\omega}-\Delta_{PI}) L_n(\mathfrak{z})} \\
&- \color{blue}{Z_H(\mathfrak{z})(t_{lo}(X)+\mathfrak{z}^nt_{mid}(X)+\mathfrak{z}^{2n}t_{hi}(X))}.
\end{align}
The red colored terms in the first step of the above equation are the new terms that are introduced in the simplified version. We have split them into two parts shown by green and blue colors. The green part is implemented in the `compute_linear_contribution()` function in `permutation_widget_impl.hpp`. The blue part is implemented in `compute_linearisation_coefficients()` in `prover.cpp`. This is because the quotient polynomial $t(X)$ gets updated in the `plookup_widget_impl.hpp` which is invoked after `permutation_widget_impl.hpp` is invoked in case of Ultra Plonk. We want to use the quotient polynomial after it gets updated in the `transition_widget`s.
#### Notes:
1. The constant coefficient $r[0]$ should be initialized with the constant term $-(\bar{a} + \beta\bar{s}_{\sigma 1}+ \gamma)( \bar{b}+ \beta \bar{s}_{\sigma 2} + \gamma)(\bar{c}+\gamma)\bar{z}_{\omega}\alpha - \alpha^3 L_1(\mathfrak{z})+ \alpha^2(\bar{z}_{\omega}-\Delta_{PI}) L_n(\mathfrak{z})$. They should not appear in the loop iteration.
3. The value of $r[n]$ should be set as `r[n] = -key->quotient_large[3 * n] * lagrange_evals.vanishing_poly * z_pow_two_n` as `t_high` is a degree $n+1$ polynomial (because of root [cutting](https://hackmd.io/1DaroFVfQwySwZPHMoMdBg?view)).
4. The multiplication of powers of $\alpha$ is opposite to that is there in the paper.

### Changes at the Sixth Round:
In the current implementation, we have
\begin{align}
W_{\mathfrak{z}}(X) = \frac{M(X)}{X - \mathfrak{z}},
\end{align}
where $M(X)$ is,
\begin{align}
M(X) &= (t_{lo}(X)+\mathfrak{z}^nt_{mid}(X)+\mathfrak{z}^{2n}t_{hi}(X)) - \bar{t}) + \nu(r(X)-\bar{r}) + \nu^2(a(X)-\bar{a}) \\
&+ \nu^3(b(X)-\bar{b}) + \nu^4(c(X)-\bar{c}) + \nu^5(S_{\sigma1}(X)-\bar{s}_{\sigma1}) + \nu^6(S_{\sigma2}(X)-\bar{s}_{\sigma2}).
\end{align}
Following the simplified Plonk, we need to change $M(X)$ to
\begin{align}
M'(X) &= r(X) + \nu(a(X)-\bar{a}) + \nu^2(b(X)-\bar{b}) + \nu^3(c(X)-\bar{c}) \\
& + \nu^4(S_{\sigma1}(X)-\bar{s}_{\sigma1}) + \nu^5(S_{\sigma2}(X)-\bar{s}_{\sigma2}).
\end{align}

This is done in the `batch_open()` function in the `kate_commitment_scheme.cpp`.

### Changes at the Verifier's algorithm:
Step 8: Instead of computing `t_eval`, we need to compute `r_0` i.e. the constant term in the $r(X)$ polynomial given by
$$
r_0 = \alpha^2(\bar{z}_{\omega}-\Delta_{PI}) L_n(\mathfrak{z}) -(\bar{a} + \beta\bar{s}_{\sigma 1}+ \gamma)( \bar{b}+ \beta \bar{s}_{\sigma 2} + \gamma)(\bar{c}+\gamma)\bar{z}_{\omega}\alpha - \alpha^3 L_1(\mathfrak{z}).
$$

We notice that this is already computed in step 8 of the old version and subtracted from $\bar{r}$ to compute the numerator of $\bar{t}$. This is implemented in `compute_quotient_evaluation_contribution()` function in `permutation_widget_impl.hpp`. We have passed in an `fr` variable `r_0` in this function to take advantage of the code and calculate $r_0$.

*Step 9:* Here we calculate $[D]_1$. The components of it are calculated in `append_scalar_multiplication_inputs()`. In the new version, the `linear_new` (the $\nu$ challenge that is associated with $[r]_1$) challenge is set to 1. We implement this change in `standard_composer.hpp`, `turbo_composer.hpp`, and `plookup_composer.hpp`. There we also ensure that $\bar{t}$ is not evaluated in the verifier for simplified plonk.

*Step 10 and 11*: The changes here as described in the above section have been done in the `batch_verify()` function of `kate_commitment_scheme.cpp`.

### Changes Needed for Turbo Plonk

The new_version of the Plonk does not work with Turbo Plonk unless we do some more changes. This is mainly due to the fact that $t(X)$ polynomial for this case have some *non-linear terms* which is zero in case of the Standard Plonk. So we need to include the additional non-linear terms in $r(X)$ in the above equation, so that those terms get canceled with the corresponding non-linear terms in $t(X)$ and we get $r(\mathfrak{z}) = 0$ at the end of the fifth round of the prover. This is done by the following steps.
1. We have added `compute_non_linear_terms()` method in `compute_linear_contribution()` and `compute_quotient_evaluation_contribution()` functions in `transition_widget.hpp`, when `use_simplified_plonk` is true.

### Changes Needed for Ultra Plonk

In Ultra Plonk, some additional terms are included in $t(X)$ in terms of $Z_{lookup}$. Below we describe an interesting issue we faced for the case of Ultra Plonk and how we fixed it.

### Note: A Mind Boggling Issue with Ultra Plonk.
###### *The issue*:
The simplified Plonk does not work for Ultra Plonk in spite of the changes made for Standard Plonk and Turbo Plonk. We investigate the issue and noticed that `t_eval` is modified in `compute_quotient_evaluation_contribution()` function in `plookup_widget_impl.hpp` and some constant is added to `t_eval`. We call this constant $r_{plookup}$. As `r_0` mimics the `t_eval` computation, we added $r_{plookup}$ to `r_0`. Now all the tests pass, but $r(\mathfrak{z})$ is found to be non-zero. This is concerning because of the following reason. The term $r(\mathfrak{z}) \neq 0$ implies that $(X - \mathfrak{z})$ does not divide the numerator of $W_{\mathfrak{z}}(X)$ which is given by,
\begin{align}
M'(X) &= r(X) + \nu(a(X)-\bar{a}) + \nu^2(b(X)-\bar{b}) + \nu^3(c(X)-\bar{c}) \\
& + \nu^4(S_{\sigma1}(X)-\bar{s}_{\sigma1}) + \nu^5(S_{\sigma2}(X)-\bar{s}_{\sigma2}).
\end{align}
This implies that the commitment $[W_{\mathfrak{z}}(X)]_1$ must be invalid and the verification must fail. But it does not!

###### *Explanation* :
Let us denote the linearization polynomials for Standard Plonk and Ultra Plonk by $r_s(X)$ and $r_p(x)$. To be precise, $r_s(X)$ is the version of the polynomial $r(X)$ which we are using following standard Plonk computation and which causes the above issue. The polynomial $r_p(X)$ is the polynomial which ideally should be $r(X)$ in case of Ultra Plonk. As there are no contribution in the linearization polynomial in the `compute_linear_contribution()` function in `plookup_widget_impl.hpp`, we infer that,
$$
r_p(X) = r_s(X) + r_{plookup}.
\tag{1}
$$
Ideally $r_p(\mathfrak{z})=0$. Putting this in equation (1) we get,
$$
r_{plookup} = -r_s(\mathfrak{z}).
\tag{2}
$$
Let $F(X)$ define the following polynomial,
\begin{align}
F(X) &= r_s(X) + \nu a(X) + \nu^2 (b(X) + \nu^3 c(X) + \nu^4 S_{\sigma1}(X) + \nu^5 S_{\sigma2}(X) \\
&= r_s(X) + \nu k(X)
\end{align}
To compute $W_{\mathfrak{z}}(X)$, we compute $F(X)$ in `batch_open()` function in `kate_commitment_scheme.cpp` and pass it to another function, namely, `compute_opening_polynomial()` which is also defined in `kate_commitment_scheme.cpp`. This function computes $\frac{F(X)-F(\mathfrak{z})}{X-\mathfrak{z}}$ and set it to $W_{\mathfrak{z}}(X)$. Let us ponder over the numerator.
\begin{align}
F(X) - F(\mathfrak{z}) &= (r_s(X) - r_s(\mathfrak{z})) + \nu (k(X) - k(\mathfrak{z})), \\
&\stackrel{(1)}{=} r_p(X) + \nu (k(X) - k(\mathfrak{z})).
\end{align}
The equality (1) follows from equations (1) and (2).

Hence in spite of setting $r_s(X)$ (which has non-zero evaluation at $\mathfrak{z}$) instead of $r_p(X)$ as an argument for the `batch_open()` function for computing $W_{\mathfrak{z}}(X)$, we eventually computed the correct value of $W_{\mathfrak{z}}(X)$ and its commitment. In the verifier side, we have added $r_{plookup}$ to `r_0`. Hence the linearlization polynomial becomes $r_p(X)$ instead of $r_s(X)$, and everything works fine.

To fix the above issue, we have added $r_{plookup}$ to $r[0]$ (the constant component of the linearization polynomial) in the function `compute_linear_contribution()` in `plookup_widget_impl.hpp` to make it $r_p(X)$ instead of $r_s(X)$. We also included an assertion check that $r(\mathfrak{z})=0$ in the `compute_linearisation_coefficients()` function executed at the fifth round of `prover.cpp`.

Below we describe the various tests for checking our code.
### Test
The below code performs a single test, used in the preliminary stage.
Location: `aztec2-internal/barretenberg/build`
Compile code by : `make proof_system_tests `
Run test to print values :`./src/aztec/plonk/proof_system/proof_system_tests --gtest_filter=*verify_arithmetic_proof_small`

To check Standard/Turbo/Ultra Plonk:
`make composer_tests && ./src/aztec/plonk/composer/composer_tests --gtest_filter=(standard/turbo/plookup)_composer*`

Some other Barretenberg tests:
* `make proof_system_tests && ./src/aztec/plonk/proof_system/proof_system_tests`
* `make stdlib_verifier_tests && ./src/aztec/stdlib/recursion/verifier/stdlib_verifier_tests`

## Error Handling
1. Error: Compiler seeks waffle::ProverBase instead of ProverBase in the arguments of the template classes in prover.cpp.
Error message: `/mnt/user-data/arijit/aztec2-internal/barretenberg/src/aztec/plonk/proof_system/prover/prover.cpp:412:47: fatal error: no template named 'ProverBase'; did you mean 'waffle::ProverBase'?`
Reason: Mistakenly added an extra curly brace.
2. Error: `nu_challenge` in verifier does not match with that of the prover even we make necessary changes in the respective composer.
Reason: The file `verifier_test.cpp` uses a local version of polynomial manifest in the `verifier_helpers` namespace.