feat: protogalaxy interfaces #2125

maramihali · 2023-09-08T11:27:50Z

This PR introduces the concept of an Instance and slightly reworks the components of Honk as follows:

an Instance contains and is responsible for creating all the polynomials resulting from a circuit and required to generate a proof (the functionality that performs these operations has been hence moved from the Composer and Prover to the Instance). This abstraction is necessary for implementing ProtoGalaxy since we are going to fold polynomials. Moreover, it makes certain tests in Honk more lightweight as we no longer have to create a full Prover to produce polynomials from a finalised circuit.
the Composer now creates an Instance from a finalised circuit and creates a Prover and Verifier from an Instance (or several Instances in the case of ProtoGalaxy).

The Instance abstraction is currently only supported by UltraHonk.

Then, I introduced shells for the ProtoGalaxyProver and ProtoGalaxyVerifier and data structures involved in folding.

Resolves #684 and partially resolves #681 (might also need to provide some shell in the circuits library to fully resolve this one).

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

maramihali · 2023-09-10T14:15:57Z

circuits/cpp/barretenberg/cpp/src/barretenberg/honk/instance/instance.hpp

+// The responsability of a Prover is to commit, add to transcript while the Instance manages its polynomials
+template <UltraFlavor Flavor> class Instance_ {
+  public:
+    using Circuit = typename Flavor::CircuitBuilder;


at this stage in the code, we're not building a circuit anymore so Circuit is a more fitting name, I have also done some renaming so CircuitBuilder variables are now called builder rather than circuit_constructor when we're actually building circuits

Makes sense to me + reads nicely.

maramihali · 2023-09-11T12:26:35Z

circuits/cpp/barretenberg/cpp/src/barretenberg/honk/instance/instance.hpp

+// The responsability of a Prover is to commit, add to transcript while the Instance manages its polynomials
+// TODO: we might wanna have a specialisaition of the Instance class for the Accumulator
+template <UltraFlavor Flavor> class Instance_ {
+  public:


As an initial design I think we can use a single Instance structure to refer to both normal instances (whose folding parameters will be 0 and which will be created from circuits) and accumulated instances (which will be created from a FoldingResult i.e. the accumulated result from the work of PG prover and PG verifier) but we can revisit this as we're building the full PG prover and verifier.

maramihali · 2023-09-11T12:34:57Z

circuits/cpp/barretenberg/cpp/src/barretenberg/honk/proof_system/folding_result.hpp

+    using ProverPolynomials = typename Flavor::ProverPolynomials;
+    using FoldingParameters = typename Flavor::FoldingParameters;
+    ProverPolynomials folded_prover_polynomials;
+    std::vector<uint8_t> folding_data;


This is the content of the transcript and in UltraProver it's a plonk::proof which seemed confusing to use in this case.

Yeah I hate that, we need AztecProtocol/barretenberg#656

maramihali · 2023-09-11T13:47:23Z

circuits/cpp/barretenberg/cpp/src/barretenberg/honk/proof_system/protogalaxy_prover.cpp

+#include "barretenberg/proof_system/flavor/flavor.hpp"
+namespace proof_system::honk {
+template <UltraFlavor Flavor>
+ProtoGalaxyProver_<Flavor>::ProtoGalaxyProver_(std::vector<std::shared_ptr<Instance>> insts)


not sure if shared_ptr is the right way to go so i'm open to feedback, but afaiu you can't have a vector of references

Hm, well essentially all of the data in an instance is already handled through a shared pointer, so copying an instance should be inexpensive, but then again there are these vectors it contains, and you've already implemented instance handling through shared pointers, and that seems fine for now.

maramihali · 2023-09-11T16:21:57Z

circuits/cpp/barretenberg/cpp/src/barretenberg/honk/instance/instance.hpp

+
+    // The number of public inputs has to be the same for all instances because they are
+    // folded element by element.
+    std::vector<FF> public_inputs;


Also we can't have the case where instance A has 50 inputs and instance B has 3 inputs and from index 4 to 50 instance B has zeros because, on one hand this is wasteful and on the other hand the number of actual public inputs matter for the compute_public_input_delta function

maramihali · 2023-09-13T14:33:25Z

circuits/cpp/barretenberg/cpp/src/barretenberg/honk/proof_system/prover_library.hpp

@@ -1,17 +0,0 @@
-#pragma once


I was able to remove the prover_library because only the Instance was using it. We could do the same with the grand_product_library if we sunset StandardHonk or it is updated to suport instances.

maramihali · 2023-09-13T14:34:36Z

circuits/cpp/barretenberg/cpp/src/barretenberg/honk/proof_system/prover_library.test.cpp

-#include <vector>
-
-using namespace proof_system::honk;
-namespace prover_library_tests {


some tests here were testing the grand_product_library which I have moved in the grand_product_library.test.cpp.

codygunton

Thanks for this very solid work. I have some follow-on requests (many fairly trivial, a few more involved) that I think will make it even stronger and more robust.

barretenberg/cpp/src/barretenberg/honk/instance/instance.hpp

codygunton · 2023-09-13T20:01:34Z

barretenberg/cpp/src/barretenberg/benchmark/honk_bench/benchmark_utilities.hpp

@@ -224,11 +224,21 @@ void construct_proof_with_specified_num_iterations(State& state,
        test_circuit_function(builder, num_iterations);

        auto composer = Composer();
-        auto ext_prover = composer.create_prover(builder);
-        state.ResumeTiming();
+        if constexpr (Composer::NAME_STRING == "UltraHonk") {


Please use the type system for this (one of the Is concepts) and not the name string. I think the name string can go away from the Instance definition.

I'd like to get rid of the NAME_STRING altogether but it was needed for something. But in the past using identifiers lead to really confusing code.

barretenberg/cpp/src/barretenberg/honk/instance/instance.hpp

codygunton · 2023-09-13T20:11:30Z

barretenberg/cpp/src/barretenberg/benchmark/honk_bench/benchmark_utilities.hpp

+            auto proof = ext_prover.construct_proof();
+
+        } else {
+            auto ext_prover = composer.create_prover(builder);


How much more work would it be to implement for StandardHonk? I know we talked about this and I suggested doing Ultra only, but now that I see it leads a major divergence in structure and also in interace, I'm in favor of bringing Standard along for the ride. Should be routine now that you've done the same for Ultra, right?

erm, couple of hours max, will do

but the divergence around here is between honk and plonk now

Not ideal, but we have accepted divergence with Plonk if it means improving Honk.

barretenberg/cpp/src/barretenberg/honk/proof_system/protogalaxy_verifier.cpp

codygunton · 2023-09-13T20:49:12Z

circuits/cpp/barretenberg/cpp/src/barretenberg/honk/instance/instance.hpp

+// The responsability of a Prover is to commit, add to transcript while the Instance manages its polynomials
+template <UltraFlavor Flavor> class Instance_ {
+  public:
+    using Circuit = typename Flavor::CircuitBuilder;


Makes sense to me + reads nicely.

codygunton · 2023-09-13T20:50:19Z

circuits/cpp/barretenberg/cpp/src/barretenberg/honk/proof_system/folding_result.hpp

+    using ProverPolynomials = typename Flavor::ProverPolynomials;
+    using FoldingParameters = typename Flavor::FoldingParameters;
+    ProverPolynomials folded_prover_polynomials;
+    std::vector<uint8_t> folding_data;


Yeah I hate that, we need AztecProtocol/barretenberg#656

codygunton · 2023-09-13T20:58:47Z

circuits/cpp/barretenberg/cpp/src/barretenberg/honk/proof_system/protogalaxy_prover.cpp

+#include "barretenberg/proof_system/flavor/flavor.hpp"
+namespace proof_system::honk {
+template <UltraFlavor Flavor>
+ProtoGalaxyProver_<Flavor>::ProtoGalaxyProver_(std::vector<std::shared_ptr<Instance>> insts)


Hm, well essentially all of the data in an instance is already handled through a shared pointer, so copying an instance should be inexpensive, but then again there are these vectors it contains, and you've already implemented instance handling through shared pointers, and that seems fine for now.

codygunton · 2023-09-13T21:05:06Z

barretenberg/cpp/src/barretenberg/honk/instance/instance.hpp

+
+    FoldingParameters folding_params;
+    // Used by the prover for domain separation in the transcript
+    uint32_t index;


This index usage feels kinda bad and brittle. When you create the vector of shared pointers to instances, why can't we just use the index of the pointer in that vector?

I've mocked out related things in my combiner work, and I ended up defining an Instances object that wraps multiple instances. What do you think about implementing that and having that class manage the domain separation?

aztec-packages/circuits/cpp/barretenberg/cpp/src/barretenberg/protogalaxy/combiner.hpp

Line 11 in e74d800

template <typename Flavor, size_t NUM_> struct Instances {

What about having a lightweight Instances class that encapsulates NUM_-many Instance objects. I've tentatively added a TODO (+issue: AztecProtocol/barretenberg#725) to smoothen things out?

maramihali · 2023-09-14T09:36:18Z

barretenberg/cpp/src/barretenberg/honk/composer/ultra_composer.hpp

@@ -62,24 +54,23 @@ template <UltraFlavor Flavor> class UltraComposer_ {
    UltraComposer_& operator=(UltraComposer_ const& other) noexcept = default;


You've noticed in the files i've added that explicit constructors are not needed. I only added them because they were also present here but it seems that they are not needed here either (by "seems" I mean code compiles and tests pass if I remove them). Can they be removed here as well?

maramihali · 2023-09-15T11:25:58Z

barretenberg/cpp/src/barretenberg/benchmark/honk_bench/benchmark_utilities.hpp

-        auto ext_prover = composer.create_prover(builder);
-        state.ResumeTiming();
+        if constexpr (Composer::NAME_STRING == "UltraHonk") {
+            auto instance = composer.create_instance(builder);


ideally, I think the benchmarks should be templated by Flavor

🤖 I have created a release *beep* *boop* --- <details><summary>aztec-packages: 0.7.5</summary> ## [0.7.5](aztec-packages-v0.7.4...aztec-packages-v0.7.5) (2023-09-15) ### Features * Protogalaxy interfaces ([#2125](#2125)) ([b45dd26](b45dd26)) * Renamed `nargoVersion` as `compatibleNargoVersion` ([#2338](#2338)) ([6f9e0f1](6f9e0f1)) ### Bug Fixes * Add retry around docker login and revive spot_run_test_script ([#2346](#2346)) ([79e5f05](79e5f05)) * Unbox command. ([#2337](#2337)) ([e9bc9c6](e9bc9c6)) ### Miscellaneous * Increase guides-dapp-testing test timeout ([#2343](#2343)) ([1cebe2c](1cebe2c)) * Use retries by default on rpc client fetch ([#2342](#2342)) ([f4ffd68](f4ffd68)) </details> <details><summary>barretenberg.js: 0.7.5</summary> ## [0.7.5](barretenberg.js-v0.7.4...barretenberg.js-v0.7.5) (2023-09-15) ### Miscellaneous * **barretenberg.js:** Synchronize aztec-packages versions </details> <details><summary>barretenberg: 0.7.5</summary> ## [0.7.5](barretenberg-v0.7.4...barretenberg-v0.7.5) (2023-09-15) ### Features * Protogalaxy interfaces ([#2125](#2125)) ([b45dd26](b45dd26)) </details> --- This PR was generated with [Release Please](https://github.com/googleapis/release-please). See [documentation](https://github.com/googleapis/release-please#release-please).

maramihali added the crypto cryptography label Sep 8, 2023

maramihali self-assigned this Sep 8, 2023

maramihali force-pushed the mm/pg-interfaces branch 7 times, most recently from 461a24e to 8e480cb Compare September 11, 2023 16:17

maramihali commented Sep 11, 2023

View reviewed changes

maramihali requested a review from codygunton September 11, 2023 16:18

maramihali marked this pull request as ready for review September 11, 2023 16:18

maramihali force-pushed the mm/pg-interfaces branch from 8e480cb to 398797a Compare September 11, 2023 16:19

maramihali commented Sep 11, 2023

View reviewed changes

maramihali force-pushed the mm/pg-interfaces branch 11 times, most recently from 19a2420 to cd1f647 Compare September 12, 2023 13:14

maramihali added 5 commits September 12, 2023 13:32

wip

94418e5

more wip

f98e95f

even more wip

0749289

more wip

06c02ac

more wip

884318a

maramihali added 2 commits September 13, 2023 11:14

cleanup of namings

4e11ee8

cleanup

67ace3b

maramihali commented Sep 13, 2023

View reviewed changes

remove prover_library

cf4435f

maramihali force-pushed the mm/pg-interfaces branch from b6764d9 to cf4435f Compare September 13, 2023 15:07

maramihali and others added 6 commits September 13, 2023 15:48

add instance.test.cpp that i forgot to add

c7a6282

add grand_product_library.test.cpp that i forgot to add

0157a1c

chore: move bb for merge

62e0c62

chore: remove build-system for merge

b5de3a9

Merge

8f07bd4

resolve merge conflicts

7e3bf57

maramihali force-pushed the mm/pg-interfaces branch from 442492b to 7e3bf57 Compare September 13, 2023 18:30

codygunton requested changes Sep 13, 2023

View reviewed changes

actually delete prover_library and resolve comments

78a643b

maramihali commented Sep 14, 2023

View reviewed changes

maramihali added 3 commits September 14, 2023 10:37

address some review comments

1eb15fb

start work to make standard honk support instances

4fba3a2

continue work for standard honk with instances

ce7d33c

maramihali commented Sep 15, 2023

View reviewed changes

maramihali requested a review from codygunton September 15, 2023 11:53

Merge branch 'master' into mm/pg-interfaces

7406e65

maramihali force-pushed the mm/pg-interfaces branch from a830dae to 7406e65 Compare September 15, 2023 12:09

Merge branch 'master' into mm/pg-interfaces

599d20a

maramihali mentioned this pull request Sep 15, 2023

Remove using namespace in barretenberg header files #2216

Open

codygunton approved these changes Sep 15, 2023

View reviewed changes

codygunton merged commit b45dd26 into master Sep 15, 2023
2 checks passed

codygunton deleted the mm/pg-interfaces branch September 15, 2023 19:29

AztecBot mentioned this pull request Sep 15, 2023

chore(master): Release 0.7.5 #2345

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

feat: protogalaxy interfaces #2125

feat: protogalaxy interfaces #2125

maramihali commented Sep 8, 2023 •

edited

Loading

maramihali Sep 10, 2023 •

edited

Loading

codygunton Sep 13, 2023

maramihali Sep 11, 2023

maramihali Sep 11, 2023

codygunton Sep 13, 2023

maramihali Sep 11, 2023

codygunton Sep 13, 2023

maramihali Sep 11, 2023

maramihali Sep 13, 2023

maramihali Sep 13, 2023

codygunton left a comment

codygunton Sep 13, 2023

codygunton Sep 13, 2023

codygunton Sep 13, 2023

maramihali Sep 14, 2023

maramihali Sep 15, 2023

codygunton Sep 15, 2023

codygunton Sep 13, 2023

codygunton Sep 13, 2023

codygunton Sep 13, 2023

codygunton Sep 13, 2023

codygunton Sep 13, 2023

maramihali Sep 15, 2023

maramihali Sep 14, 2023 •

edited

Loading

maramihali Sep 15, 2023

		@@ -62,24 +54,23 @@ template <UltraFlavor Flavor> class UltraComposer_ {
		UltraComposer_& operator=(UltraComposer_ const& other) noexcept = default;

feat: protogalaxy interfaces #2125

feat: protogalaxy interfaces #2125

Conversation

maramihali commented Sep 8, 2023 • edited Loading

Checklist:

maramihali Sep 10, 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

codygunton 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

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

maramihali Sep 14, 2023 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

maramihali commented Sep 8, 2023 •

edited

Loading

maramihali Sep 10, 2023 •

edited

Loading

maramihali Sep 14, 2023 •

edited

Loading