feat: Simplify relation containers #2619

codygunton · 2023-10-02T13:35:38Z

The main goal of this PR is to simplify the construction of the containers that we use to accumulate relation values (in sumcheck and, soon, in Protogalaxy folding).

Core changes

Expose a View alias for each of the primitives that needs one (Univariate, field and field_t).
Add nested container classes that can be instantiated from a std::array of sizes. Credit: https://stackoverflow.com/a/60440611
Remove AccumulatorsAndViews types, replacing each with simply an accumulator type with a intrinsic notion of view.

Other changes

Bring ECCVM more in line with the rest of the relation and circuit builder code.
Add a get_row function to avoid passing index values to some functions.
Use more explicit or more appropriate type names (e.g., RelationUnivariates becomes TupleOfTuplesOfUnivariates, ClaimedEvaluations becomes AllValues outside of sumcheck, where it is now used in the execution trace builders).
Replace some autos with useful template parameter names, still deducing the types.
Deduce more types, especially in accumulate functions where now it is possible, since we don't have an 'alias container type' grouping a type with a view.
Use a more idiomatic approach to identify non-linearly independent subrelations.
Get rid of special proxy functions to accumulate functions.
Compile time calculation of individual relation lengths, possible now that the subrelation lengths live in a std::array.
Relations (always fully static) are no longer instantiated anywhere.

…tion-containers

ledwards2225

Looks great. Just a few comments/questions about naming

ledwards2225 · 2023-10-06T23:55:47Z

barretenberg/cpp/src/barretenberg/honk/flavor/ecc_vm.hpp

-    using RelationUnivariates = decltype(create_relation_univariates_container<FF, Relations>());
-    using RelationValues = decltype(create_relation_values_container<FF, Relations>());
+    using TupleOfTuplesOfUnivariates = decltype(create_relation_univariates_container<FF, Relations>());
+    using TupleOfTuplesOfValues = decltype(create_relation_values_container<FF, Relations>());


Tuple of array of values?

Yes, it should be this, thanks.

ledwards2225 · 2023-10-07T00:00:25Z

barretenberg/cpp/src/barretenberg/honk/flavor/goblin_ultra.hpp

-    using RelationUnivariates = decltype(create_relation_univariates_container<FF, Relations>());
-    using RelationValues = decltype(create_relation_values_container<FF, Relations>());
+    using TupleOfTuplesOfUnivariates = decltype(create_relation_univariates_container<FF, Relations>());
+    using TupleOfTuplesOfValues = decltype(create_relation_values_container<FF, Relations>());


ledwards2225 · 2023-10-07T00:20:06Z

barretenberg/cpp/src/barretenberg/proof_system/circuit_builder/eccvm/eccvm_circuit_builder.hpp

@@ -501,31 +502,26 @@ template <typename Flavor> class ECCVMCircuitBuilder {
            .eccvm_set_permutation_delta = eccvm_set_permutation_delta,
        };

-        auto rows = compute_full_polynomials();
-        const size_t num_rows = rows[0].size();
+        auto polynomials = finalize();


this seems a bit awkward - why is finalize better?

I was trying to bring this in line with what's done in Ultra where finalize is called at the beginning of check_circuit.

But I see your point and I see that the flow in ECCVM has diverge more than I had realized, so I'm renaming to compute_polynomials.

ledwards2225 · 2023-10-07T00:44:37Z

barretenberg/cpp/src/barretenberg/proof_system/relations/ecc_vm/ecc_lookup_relation.hpp


    static constexpr std::array<bool, 2> SUBRELATION_LINEARLY_INDEPENDENT = { true, false };

-    template <typename AccumulatorTypes>
-    static Accumulator<AccumulatorTypes> convert_to_wnaf(const auto& s0, const auto& s1)


surprised this is going away. Did it just move somewhere? or it wasn't used?

Ah, i found it

ledwards2225 · 2023-10-07T00:50:14Z

barretenberg/cpp/src/barretenberg/proof_system/relations/ecc_vm/ecc_transcript_relation.hpp


-    static constexpr size_t LEN_1 = 6; // arithmetic sub-relation
-    template <template <size_t...> typename AccumulatorTypesContainer>
-    using GetAccumulatorTypes = AccumulatorTypesContainer<LEN_1,


hah. I didn't know how silly this had gotten

Yeah that's a lotta LEN_1s

ledwards2225 · 2023-10-07T00:56:28Z

barretenberg/cpp/src/barretenberg/proof_system/relations/relation_types.hpp

-        return std::get<subrelation_index>(Relation::SUBRELATION_LINEARLY_INDEPENDENT);
-    }
+    using UnivariateAccumulator0 = std::tuple_element_t<0, TupleOfUnivariatesOverSubrelations>;
+    using ValueAccumulator0 = std::tuple_element_t<0, ArrayOfValuesOverSubrelations>;


This seems a bit funny. Why do we need a special alias for the type of the first element? Can you add a comment explaining why the first element in the tuple is special?

…tion-containers

maramihali · 2023-10-10T21:54:37Z

barretenberg/cpp/src/barretenberg/proof_system/relations/relation_types.hpp

+/**
+ * @brief Check whether a given subrelation is linearly independent from the other subrelations.
+ *
+ * @details More often than not, we want multiply each subrelation contribution by a power of the relation separator


Suggested change

* @details More often than not, we want multiply each subrelation contribution by a power of the relation separator

* @details More often than not, we want to multiply each subrelation contribution by a power of the relation separator

maramihali · 2023-10-10T22:00:21Z

barretenberg/cpp/src/barretenberg/proof_system/relations/relation_types.hpp

+ *
+ * @details More often than not, we want multiply each subrelation contribution by a power of the relation separator
+ * challenge. In cases where we wish to define a subrelation that merges into another, we encode this in a boolean array
+ * `SUBRELATION_LINEARLY_INDEPENDENT` in the relation. If no such array is defined, then the default case where all


This is a very helpful comment and I think what's missing is a sentence explaining why we use this array i.e. what is the connection between linear independence and a subrelation merging into another

maramihali · 2023-10-10T22:14:14Z

barretenberg/cpp/src/barretenberg/proof_system/relations/nested_containers.hpp

+
+// Types needed for sumcheck and folding.
+template <typename FF, auto LENGTHS>
+using TupleOfUnivariates = typename TupleOfContainersOverArray<barretenberg::Univariate, FF, LENGTHS>::type;


My slight confusion about this might be caused by English being my second language but it took me a bit to parse that TupleOfContainersOverArray means "we take a tuple of containers from an array", and I still want to double check with you that this is correct. Reading the *OverFoo phrasing is the part that confused me throught the changes in PR.

maramihali · 2023-10-10T22:35:40Z

barretenberg/cpp/src/barretenberg/proof_system/relations/relation_types.hpp

-            accumulator, input, relation_parameters, scaling_factor);
-    }
+    using TupleOfUnivariatesOverSubrelations = TupleOfUnivariates<FF, RelationImpl::SUBRELATION_LENGTHS>;
+    using ArrayOfValuesOverSubrelations = ArrayOfValues<FF, RelationImpl::SUBRELATION_LENGTHS>;



While reading through other modifications of the PR that use either of these two using declarations, I found myself going back to here to remind myself how to visualise their structure, maybe having a descriptive example as comments would really help in future use.

Also, I think ArrayOfValues is confusing because underneath it is several tuples of values (..right?). If that is the case ArrayOfScalarTuples instead of ArrayOfValues sprang to mind as a better name.

codygunton added 6 commits September 27, 2023 21:46

Get rid of proxies to accumulate.

13f2957

More explicit names for accumulator types.

b4d7f6d

Step: Containers from arrays.

02e304a

WIP on accumulate interface

0812041

It works

8798c6a

Add get_row and rename ClaimedEvaluations

7f87044

codygunton self-assigned this Oct 3, 2023

codygunton added 23 commits October 3, 2023 16:00

This index does nothing?

af3241e

Format -_-

afdd72b

Get rid of index in gp computation.

af8e251

get_row in compute_logderivative_inverse

6b44bd3

compute_read_term WIP

13d6577

Name type

dff0c38

Ditto compute_write_term

a989d4f

Supply Accumulator0 type

0a6a6c4

r/w predicates and cleanup

7c66273

Make circuit builder build.

b413e51

Merge remote-tracking branch 'origin/master' into cg/pg-simplify-rela…

01bcdb8

…tion-containers

Fix (??)

3329eb4

No more get_view

d30ab50

Lookup relation

65cfd43

GenPermSort relation

1c4d011

EllipticRelation

1286417

ECCOpQueue

b0e26b0

Aux relation

806b1eb

Permutation relation

5f81c32

proof_system_tests compiles.

4beb688

Everything builds.

af25ed9

No templates in relation_types.hpp

56b0908

Four type sin relation_types.hpp

cf66000

codygunton added 16 commits October 5, 2023 19:08

Rename (better grammar)?

8dc4c58

RELATION_LENGTH is calculated dynamically

908f485

Nix LEN_s and getters

8ee72d2

Clarify around extended_edges

d3ec8a2

Resolve TODOs

dc3e46d

accumulate functions can infer types

41fb68f

Tweaks in review 1.

a6e22b1

Use generic template parameter name

7b2e885

More review.

8ea3674

Move subrelation_is_linearly_independent to fn.

b0dccce

Credit

ad5050b

unnamed scope is fine?

d16c09c

Add illustrative test.

a552815

Rename compute_full_polynomails; use get_row

29a8422

Finishing touches

7ab6829

Merge remote-tracking branch 'origin/master' into cg/pg-simplify-rela…

1caa638

…tion-containers

codygunton marked this pull request as ready for review October 6, 2023 22:53

ledwards2225 approved these changes Oct 9, 2023

View reviewed changes

codygunton added 3 commits October 10, 2023 17:56

Respond to Luke's review.

2a91100

Merge remote-tracking branch 'origin/master' into cg/pg-simplify-rela…

2650429

…tion-containers

Whoops--staged missing change.

c1ac0ed

codygunton mentioned this pull request Oct 11, 2023

feat: protogalaxy perturbator! #2624

Merged

4 tasks

codygunton merged commit 99c5127 into master Oct 11, 2023

codygunton deleted the cg/pg-simplify-relation-containers branch October 11, 2023 16:54

AztecBot mentioned this pull request Oct 11, 2023

chore(master): Release 0.8.10 #2766

Merged

maramihali reviewed Oct 11, 2023

View reviewed changes

codygunton mentioned this pull request Oct 17, 2023

Simplify relations code AztecProtocol/barretenberg#720

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

feat: Simplify relation containers #2619

feat: Simplify relation containers #2619

codygunton commented Oct 2, 2023 •

edited

Loading

ledwards2225 left a comment

ledwards2225 Oct 6, 2023

codygunton Oct 10, 2023

ledwards2225 Oct 7, 2023

ledwards2225 Oct 7, 2023

codygunton Oct 10, 2023

codygunton Oct 10, 2023

ledwards2225 Oct 7, 2023

ledwards2225 Oct 7, 2023

ledwards2225 Oct 7, 2023

codygunton Oct 10, 2023

ledwards2225 Oct 7, 2023

maramihali Oct 10, 2023

maramihali Oct 10, 2023

maramihali Oct 10, 2023

maramihali Oct 10, 2023

	* @details More often than not, we want multiply each subrelation contribution by a power of the relation separator
	* @details More often than not, we want to multiply each subrelation contribution by a power of the relation separator

feat: Simplify relation containers #2619

feat: Simplify relation containers #2619

Conversation

codygunton commented Oct 2, 2023 • edited Loading

Core changes

Other changes

ledwards2225 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

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

codygunton commented Oct 2, 2023 •

edited

Loading