feat: Goblin recursive verifier #1822

ledwards2225 · 2023-08-25T19:28:59Z

Updates the existing Ultra recursive verifier to allow for goblinized group operations. (Currently limited to batch_mul)

Checklist:

Remove the checklist to signal you've completed it. Enable auto-merge if the PR is ready to merge.

If the pull request requires a cryptography review (e.g. cryptographic algorithm implementations) I have added the 'crypto' tag.
I have reviewed my diff in github, line by line and removed unexpected formatting changes, testing logs, or commented-out code.
Every change is related to the PR description.
I have linked this pull request to relevant issues (if any exist).

kevaundray · 2023-08-28T17:48:34Z

circuits/cpp/barretenberg/cpp/src/barretenberg/stdlib/primitives/biggroup/biggroup_goblin.hpp

+        auto op_tuple = builder->queue_ecc_mul_accum(point.get_value(), scalar.get_value());
+
+        // Adds constraints demonstrating proper decomposition of point coordinates.
+        // Note: may need to do point.x.assert_is_in_field() prior to the assert_eq() according to Kesha.


The mental model I have for assert equal is "this is a memcpy but for circuits", in particular:

memcpy does not assert things are equal

and memcpy(a,b) is not the same as memcpy(b,a)

hmm yeah taking a closer look there is a big DO NOT USE IN CIRCUITS warning. Definitely don't understand the details here but it's on the list of things to figure out. Either way the fact that this mistake can be made is a bad sign

Rumata888 · 2023-09-04T13:21:44Z

circuits/cpp/barretenberg/cpp/src/barretenberg/honk/pcs/gemini/gemini.hpp

+        // achieved through a builder Simulator, the stdlib codepath should become the only codepath.
+        if constexpr (Curve::is_stdlib_type) {
+            std::vector<GroupElement> commitments = { batched_f, batched_g };
+            auto one = Fr::from_witness(r.get_context(), 1);


This creates a non-constrained witness, so one can become anything. You probably just wanted Fr(1).

Updated to Fr(ctx, 1); so that the builder can be used correctly in the naf decomp in batch_mul.

Rumata888 · 2023-09-04T13:22:29Z

circuits/cpp/barretenberg/cpp/src/barretenberg/honk/pcs/kzg/kzg.hpp

-                lhs -= GroupElement::one(ctx) * claim.opening_pair.evaluation;
-            }
+            auto builder = verifier_transcript.builder;
+            auto one = Fr::from_witness(builder, 1);


Same issue with one being an unconstrained witness

Rumata888 · 2023-09-04T13:23:39Z

circuits/cpp/barretenberg/cpp/src/barretenberg/honk/pcs/shplonk/shplonk.hpp

-            for (const auto& val : vanishing_evals) {
-                inverse_vanishing_evals.emplace_back(val.invert());
+            auto builder = nu.get_context();
+            evaluation_zero = Fr::from_witness(builder, 0);


Same constraint issue

Rumata888 · 2023-09-04T13:24:08Z

circuits/cpp/barretenberg/cpp/src/barretenberg/honk/pcs/shplonk/shplonk.hpp

+            // [G] = [Q] - ∑ⱼ ρʲ / ( r − xⱼ )⋅[fⱼ] + G₀⋅[1]
+            //     = [Q] - [∑ⱼ ρʲ ⋅ ( fⱼ(X) − vⱼ) / ( r − xⱼ )]
+            commitments.emplace_back(Q_commitment);
+            scalars.emplace_back(Fr::from_witness(builder, 1)); // Fr(1)


And here, too

Rumata888 · 2023-09-04T13:46:34Z

...arretenberg/cpp/src/barretenberg/stdlib/recursion/honk/verifier/ultra_recursive_verifier.cpp

-{}
-
-template <typename Flavor>
-UltraRecursiveVerifier_<Flavor>& UltraRecursiveVerifier_<Flavor>::operator=(UltraRecursiveVerifier_&& other) noexcept


Why did you delete these? Just curious, not a comment on the decision

These are not currently in use and it's not clear they will be needed. I prefer to implement them and check their correctness as needed rather than leave them around to be used incorrectly.

Rumata888

Everything looks good, I'm just worried about the from_witness issue.

Rumata888

LGTM

🤖 I have created a new Aztec Packages release --- ## [0.1.0-alpha60](v0.1.0-alpha59...v0.1.0-alpha60) (2023-09-06) ### Features * Goblin recursive verifier ([#1822](#1822)) ([f962cb6](f962cb6)) * initial `is_valid` eip1271 style wallet + minimal test changes ([#1935](#1935)) ([f264c54](f264c54)) ### Bug Fixes * benchmark git repo ([#2041](#2041)) ([3c696bb](3c696bb)) * cli canary & deployment ([#2053](#2053)) ([1ddd24a](1ddd24a)) * **rpc:** Fixes getNodeInfo serialisation ([#1991](#1991)) ([0a29fa8](0a29fa8)) ### Miscellaneous * **circuits:** - use msgpack for cbind routines of native private kernel circuits ([#1938](#1938)) ([3dc5c07](3dc5c07)) * **docs:** API docs stucture ([#2014](#2014)) ([9aab9dd](9aab9dd)) * Update function selector computation ([#2001](#2001)) ([e07ea1a](e07ea1a)) --- This PR was generated with [Release Please](https://github.com/googleapis/release-please). See [documentation](https://github.com/googleapis/release-please#release-please). Co-authored-by: github-actions[bot] <41898282+github-actions[bot]@users.noreply.github.com>

iAmMichaelConnor added the crypto cryptography label Aug 26, 2023

ledwards2225 force-pushed the lde/goblin_recursive_verifier branch from 6d654db to 3d95476 Compare August 28, 2023 17:32

kevaundray reviewed Aug 28, 2023

View reviewed changes

codygunton assigned ledwards2225 Aug 28, 2023

ledwards2225 force-pushed the lde/goblin_recursive_verifier branch 3 times, most recently from 67eefe8 to d9d2b0c Compare September 1, 2023 13:33

ledwards2225 requested a review from Rumata888 September 1, 2023 20:57

ludamad force-pushed the master branch from e2c543c to 0036e07 Compare September 3, 2023 22:02

Rumata888 reviewed Sep 4, 2023

View reviewed changes

ledwards2225 force-pushed the lde/goblin_recursive_verifier branch from d9d2b0c to e52d884 Compare September 5, 2023 18:59

ledwards2225 added 13 commits September 5, 2023 19:41

proper goblin batch mul in biggroup; tests passing

c422de1

convert muls in Gemini to batch mul

0da55f9

convert Shplonk to batch mul

eb7f119

template recursive verifier on goblin flag

77ca9af

batch mul in kzg

ebee778

remove unneeded else in batch mul

2566a06

add test for goblin batch mul

fe578f1

comments and cleanup

abfdc34

todos with issue numbers in gemini

7b27b3d

WiP alternative constraints

ef387fb

update constraints in batch mul

2eebc7a

fix unconstrained witnesses and do add accum in batch mul

9abfd42

update zero evaluation and comments

05e872f

ledwards2225 force-pushed the lde/goblin_recursive_verifier branch from b7ae155 to 05e872f Compare September 5, 2023 19:41

Rumata888 approved these changes Sep 5, 2023

View reviewed changes

ledwards2225 merged commit f962cb6 into master Sep 5, 2023

ledwards2225 deleted the lde/goblin_recursive_verifier branch September 5, 2023 22:31

github-actions bot mentioned this pull request Sep 5, 2023

chore(master): release 0.1.0-alpha60 #2040

Merged

github-actions bot mentioned this pull request Sep 8, 2023

chore(master): Release 0.5.2 #2141

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

feat: Goblin recursive verifier #1822

feat: Goblin recursive verifier #1822

ledwards2225 commented Aug 25, 2023

kevaundray Aug 28, 2023

ledwards2225 Aug 28, 2023

Rumata888 Sep 4, 2023 •

edited

Loading

ledwards2225 Sep 5, 2023 •

edited

Loading

Rumata888 Sep 4, 2023

ledwards2225 Sep 5, 2023

Rumata888 Sep 4, 2023

ledwards2225 Sep 5, 2023

Rumata888 Sep 4, 2023

ledwards2225 Sep 5, 2023

Rumata888 Sep 4, 2023

ledwards2225 Sep 5, 2023

Rumata888 left a comment

Rumata888 left a comment

feat: Goblin recursive verifier #1822

feat: Goblin recursive verifier #1822

Conversation

ledwards2225 commented Aug 25, 2023

Checklist:

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Rumata888 Sep 4, 2023 • edited Loading

Choose a reason for hiding this comment

ledwards2225 Sep 5, 2023 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Rumata888 left a comment

Choose a reason for hiding this comment

Rumata888 left a comment

Choose a reason for hiding this comment

Rumata888 Sep 4, 2023 •

edited

Loading

ledwards2225 Sep 5, 2023 •

edited

Loading