feat: Honk recursive verifier Pt. 1 #1488

ledwards2225 · 2023-08-09T20:09:32Z

Early-stage UltraHonk recursive verifier.

The idea is to have a single UltraVerifier class that is instantiated with a genuine builder for recursive verification and a simulated builder for native verification. (This is as opposed to Plonk which has two separate implementations). Some notes:

At the moment I've created a UltraRecursiveVerifier_ in the stdlib. It is essentially a duplicate of the existing UltraVerifier_ with some very minor changes. Once a Simulator is in place, this will become the one and only verifier and the original will be deleted.
Although the UltraRecursiveVerifier_ itself is duplicated from UltraVerifier_, the bulk of the actual verification logic takes place in the SumcheckVerifier, GeminiVerifier, and ShplonkVerifier, which are not duplicated; they are the same classes used by the native verifier. The only addition is a handful of constexpr if's to facilitate differences between native and stdlib behavior, e.g. performing a batch mul (stdlib) vs doing naive accumulation (native).

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).

ledwards2225 · 2023-08-16T22:20:04Z

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

@@ -186,136 +186,7 @@ ProverOutput<Curve> GeminiProver_<Curve>::compute_fold_polynomial_evaluations(st
    return { fold_poly_opening_pairs, std::move(fold_polynomials) };
 };



I've moved the definitions of the the GeminiVerifier methods back to the header. This avoids a lot of pain, at least while we need to instantiate it with both native and stdlib Curves. It should be easy to revert once this is no longer the case (see bberg issue no. 673)

ledwards2225 · 2023-08-16T22:57:03Z

circuits/cpp/barretenberg/cpp/src/barretenberg/proof_system/flavor/flavor.hpp

@@ -250,25 +250,6 @@ template <class FF, typename Tuple, std::size_t Index = 0> static constexpr auto
    }
 }

-/**


This is unrelated to this work but was unused and should have been removed previously.

maramihali

looks good, only had some comments for things that were a bit unclear

maramihali · 2023-08-18T10:21:53Z

circuits/cpp/barretenberg/cpp/src/barretenberg/stdlib/utility/utility.hpp

+     * @tparam T
+     * @tparam LENGTH (used only for containers which specify a length, e.g. array/Univariate)
+     */
+    template <typename T, size_t LENGTH = 0> struct CorrespondingNativeType {


Looking at how this is used in the codem shortening the name to NativeType would still make sense, so it's not that verbose.

maramihali · 2023-08-18T10:29:29Z

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

+}
+
+/**
+ * @brief This function verifies an Ultra Honk proof for given program settings.


not related to this PR but program setting is from an older version of the proof system and should be replaced by flavor, right? (same for the UltraVerifier)

Updated, thanks

maramihali · 2023-08-18T11:10:32Z

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

+    const auto pub_inputs_offset = transcript.template receive_from_prover<uint32_t>("pub_inputs_offset");
+
+    // Extract native integer types for these basic quantities for use in subsequent operations
+    auto circuit_size_native = static_cast<size_t>(circuit_size.get_value());


This was a bit confusing to look at. I presume subsequent operations expect size_t and you get uint32_t from the transcript which is why this is needed but I would rather just cast on circuit_size and avoid creating a circuit_size_native(same for the other things).

I agree this is ugly. Its a bit more complicated than what you described because when we extract these quantities from the transcript in the recursive setting they are field_t's representing simple quantities (circuit size, public input size, etc.). However, in certain places we need to use them as simple (native) integers (e.g. in the loop below for extracting the public inputs from the transcript). So we could avoid naming these things and just use static_cast<size_t>(stdlib_type.get_value()) if you think that's more clear. Maybe just a better name than "..._native" would be best?

Went ahead and just ditched these in favor of using the static cast in place. Don't love that either but it might be more clear than defining these additional variables

yeah it took me a bit to understand the point of native variables and I think the in-place cast (and maybe comments why they're there) might be better

maramihali · 2023-08-18T11:32:39Z

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

+    info("Batched eval: num gates = ", builder->get_num_gates() - prev_num_gates);
+    prev_num_gates = builder->get_num_gates();
+
+    // Construct vectors of scalars for batched unshifted and to-be-shifted commitments


Can you add some more detailed comments here why this diverges from the native implementation?

Comment added

maramihali · 2023-08-18T11:45:24Z

...s/cpp/barretenberg/cpp/src/barretenberg/stdlib/recursion/honk/transcript/transcript.test.cpp


-    // Confirm that the native and stdlib transcripts have generated the same manifest
+    // Confirm that the native and stdlib verifier transcripts have generated the same manifest
    EXPECT_EQ(transcript.get_manifest(), native_transcript.get_manifest());

    // TODO(luke): This doesn't check much of anything until hashing is constrained in the stdlib transcript


what does this mean?

When I implemented the stdlib Transcript for Honk, I "stubbed out" the hashing portion, i.e. it does not currently lay down contraints to emulate hashing. I did this at Codys suggestion for expediency since it was a big pain to get the result to agree with the native hash (pedersen + blake3) and we are going to be changing the hash very soon anyway.

Added the issue number and a clearer comment

maramihali · 2023-08-18T11:59:17Z

circuits/cpp/barretenberg/cpp/src/barretenberg/honk/sumcheck/polynomials/barycentric_data.hpp

@@ -3,6 +3,12 @@
 #include <algorithm>
 #include <array>

+// TODO(#674): We need the functionality of BarycentricData for both field and field_t. The former is "literal" i.e. is


Suggested change

// TODO(#674): We need the functionality of BarycentricData for both field and field_t. The former is "literal" i.e. is

// TODO(#674): We need the functionality of BarycentricData for both field and field_ct. The former is "literal" i.e. is

field and field_t are the names of class templates (native and stdlib, respectively), field_ct is an alias for the specialization of field_t with a particular builder. So I think field and field_t are the correct terms here

ah, I see, misunderstood all of this, thanks for clarifying

maramihali · 2023-08-18T12:00:40Z

circuits/cpp/barretenberg/cpp/src/barretenberg/honk/sumcheck/polynomials/barycentric_data.hpp

@@ -3,6 +3,12 @@
 #include <algorithm>
 #include <array>

+// TODO(#674): We need the functionality of BarycentricData for both field and field_t. The former is "literal" i.e. is
+// compatible with constexpr operations, and the former is not. The functions for computing the pre-computable arrays in


hm literal is a confusing term - i think native (which, at least for me, means non-circuit stuff) is more appropriate

Literal is a c++ term/concept which roughly means "compatible with constexpr expressions". Apparently the concept is being deprecated since this is actually quite difficult to define. Anyway, for our purposes, native vs stdlib is really the important distinction so I've gotten rid of the term "literal"

ah! the more you know about c++. Are concepts all together being deprecated?

No definitely not. There used to be a std::is_literal_type method that when called on our field would return true (indicating that it's 'constexpr' in some sense). But this particular concept is apparently quite tricky to define so the recommendation is to define your own concept that more specifically qualifies the stuff you need. For example, does it have a constexpr constructor and assignment operator, etc.

maramihali · 2023-08-18T12:03:36Z

...ts/cpp/barretenberg/cpp/src/barretenberg/honk/sumcheck/polynomials/barycentric_data.test.cpp

@@ -14,6 +14,19 @@ TYPED_TEST_SUITE(BarycentricDataTests, FieldTypes);

 #define BARYCENTIC_DATA_TESTS_TYPE_ALIASES using FF = TypeParam;

+/**
+ * @brief Ensure auxilliary arrays (e.g. big_domain) are computed at compile time if possible (i.e. if FF is literal)


first, I noticed literal here and was confused what you are refering to

changed language to native

maramihali · 2023-08-18T12:05:59Z

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

-            inverse_vanishing_evals.emplace_back(z_challenge - claim.opening_pair.challenge);
+            vanishing_evals.emplace_back(z_challenge - claim.opening_pair.challenge);
+        }
+        // If recursion, invert elements individually, otherwise batch invert


add a comment explaining that inversion is quite cheap in circuits and there's no need for batching

maramihali · 2023-08-18T12:16:23Z

circuits/cpp/barretenberg/cpp/src/barretenberg/honk/flavor/ultra_recursive.hpp

+
+namespace proof_system::honk::flavor {
+
+class UltraRecursive {


can you add a comment that this class is mostly similar to the Ultra flavor class except the curve is intantiated with the stdlib types and you have removed stuff that is only relevant for the prover (since only a verifier is instantiated with UltraRecursive)? and other differences that maybe I haven't spotted.

thanks, done

ledwards2225 changed the title ~~Lde/recursive verifier~~ feat: Honk recursive verifier Aug 9, 2023

ledwards2225 self-assigned this Aug 9, 2023

ledwards2225 changed the title ~~feat: Honk recursive verifier~~ feat: Honk recursive verifier Pt. 1 Aug 9, 2023

maramihali added the crypto cryptography label Aug 10, 2023

ledwards2225 force-pushed the lde/recursive_verifier branch 4 times, most recently from bd0057b to 8e07148 Compare August 16, 2023 21:25

ledwards2225 commented Aug 16, 2023

View reviewed changes

ledwards2225 force-pushed the lde/recursive_verifier branch from 779f3c2 to af0eae8 Compare August 17, 2023 16:34

ledwards2225 requested a review from maramihali August 17, 2023 16:57

maramihali reviewed Aug 18, 2023

View reviewed changes

ledwards2225 added 15 commits August 18, 2023 16:35

shell of stdlib flavor and recursive verifier test

e0f24fa

sumcheck recursive verify is building

b124338

verifies and passes check circuit through sumcheck

6673bdc

move recursive vk constructor to flavor

e3a88c5

unsatisfying but working barycentric solution

2477b64

get rid of is_literal_type

eadeaf9

things working prior to gemini reduce verify

e30f756

tests passing through gemini

e6a60d4

building and running through Shplonk

481a482

better stdlib code paths in shplonk

bd78acf

debugging prints

fa67966

added computation of pairing points and pairing check in test

a50b1ff

comments and cleanup

cbf04fa

test commenting and cleanup

76c7640

lots of comment and naming updates based on review

6a22879

ledwards2225 force-pushed the lde/recursive_verifier branch from af0eae8 to 6a22879 Compare August 18, 2023 16:40

maramihali approved these changes Aug 18, 2023

View reviewed changes

ledwards2225 merged commit 4669555 into master Aug 18, 2023

ledwards2225 deleted the lde/recursive_verifier branch August 18, 2023 17:02

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: Honk recursive verifier Pt. 1 #1488

feat: Honk recursive verifier Pt. 1 #1488

ledwards2225 commented Aug 9, 2023 •

edited

Loading

ledwards2225 Aug 16, 2023 •

edited

Loading

ledwards2225 Aug 16, 2023

maramihali left a comment

maramihali Aug 18, 2023

ledwards2225 Aug 18, 2023

maramihali Aug 18, 2023

ledwards2225 Aug 18, 2023

maramihali Aug 18, 2023

ledwards2225 Aug 18, 2023 •

edited

Loading

ledwards2225 Aug 18, 2023

maramihali Aug 18, 2023

maramihali Aug 18, 2023

ledwards2225 Aug 18, 2023

maramihali Aug 18, 2023

ledwards2225 Aug 18, 2023

ledwards2225 Aug 18, 2023

maramihali Aug 18, 2023

ledwards2225 Aug 18, 2023

maramihali Aug 18, 2023

maramihali Aug 18, 2023

ledwards2225 Aug 18, 2023

maramihali Aug 18, 2023

ledwards2225 Aug 18, 2023

maramihali Aug 18, 2023

ledwards2225 Aug 18, 2023

maramihali Aug 18, 2023

ledwards2225 Aug 18, 2023

maramihali Aug 18, 2023

ledwards2225 Aug 18, 2023

		@@ -186,136 +186,7 @@ ProverOutput<Curve> GeminiProver_<Curve>::compute_fold_polynomial_evaluations(st
		return { fold_poly_opening_pairs, std::move(fold_polynomials) };
		};

                   }
               }
-              /**

	// TODO(#674): We need the functionality of BarycentricData for both field and field_t. The former is "literal" i.e. is
	// TODO(#674): We need the functionality of BarycentricData for both field and field_ct. The former is "literal" i.e. is


		namespace proof_system::honk::flavor {

		class UltraRecursive {

feat: Honk recursive verifier Pt. 1 #1488

feat: Honk recursive verifier Pt. 1 #1488

Conversation

ledwards2225 commented Aug 9, 2023 • edited Loading

Checklist:

ledwards2225 Aug 16, 2023 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

maramihali left a 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

ledwards2225 Aug 18, 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

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

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

ledwards2225 commented Aug 9, 2023 •

edited

Loading

ledwards2225 Aug 16, 2023 •

edited

Loading

ledwards2225 Aug 18, 2023 •

edited

Loading