###### 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_widgets. #### 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.