Aztec Connect SpecsDisclaimer: 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.
The latest version of the Plonk paper (a note on this can be found here) differs slightly from the actual implementation (based on an older version, implementation follows this 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
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 document written by Suyash which gives an overview of the codebase.
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:
prover.cpp.batch_open() function invoked in the sixth round in prover.cpp.Below we describe how we have incorporated the above changes.
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.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).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.
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.
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.
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.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.
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!
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.
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_testsmake stdlib_verifier_tests && ./src/aztec/stdlib/recursion/verifier/stdlib_verifier_tests/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'?nu_challenge in verifier does not match with that of the prover even we make necessary changes in the respective composer.verifier_test.cpp uses a local version of polynomial manifest in the verifier_helpers namespace.
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe