feat: added a UnivariateMonomial representation to reduce field ops in protogalaxy+sumcheck #10401

zac-williamson · 2024-12-04T18:03:51Z

Summary:

client_ivc_bench.sh benchmark has been improved by approx 10% (26218ms vs 29306ms)

In both protogalaxy + sumcheck, the basic representation of the edge of the boolean hypercube is now a degree-1 monomial instead of a MAX_RELATION_DEGREE-degree monomial

The class UnivariateMonomial can efficiently evaluate low-degree monomial relations of up to degree-2. The relations in the relations directory have been reworked to perform initial low-degree algebraic computations using UnivariateMonomial, only converting to a full Monomial object once the UnivariateMonomial would otherwise exceed degree-2

Reason why we do all of this:

for MegaFlavor, extend_edges was converting every flavour polynomial into a degree-11 Univariate. This was introducing 9 Fp additions * NUM_ALL_ENTITIES per row in the circuit. Given the sparse trace structure we are working with, this is a lot of computation that this PR makes redundant
for each relation, we check if it can be skipped by typically calling is_zero on a selector. The selector poly is in Univariate form (MegaFlavor = degree-11) which is 11 Fp zero-checks. MegaFlavor has 9 skippable relations which is 99 Fp zero-checks. With the new degree-2 representation this is reduced to only 18 Fp zero-checks
The number of raw Fp add and mul operations required to evaluate our relations is reduced. For example, in the permutation argument each */+ operation in the accumulate function was costing us 11 Fp muls/adds. It is cheaper to compute low-degree sub-terms in the coefficient representation before extend inginto point-evaluation representation

e.g. consider (in the protogalaxy case where challenges are degree-1 univariates) (w_i + \beta * S_i + \gamma) for i = 0,1,2,3. In coefficient representation this term can be computed with 8 Fp adds and 3 Fp muls. Extending into a degree-11 point evaluation form costs 18 Fp adds for a total of 26 Fp adds and 3 Fp muls.

In master branch, using Univariate<11> this computation costs us 20 Fp adds and 10 Fp muls. Assuming an add is 1/3 the cost of a mul, this makes the new approach cost 35 Fp add-equivalent operations vs 50 Fp add-equivalent

Overall in the new approach, the number of field operations to compute the permutation argument has reduced by 30%

github-actions · 2024-12-04T19:12:01Z

Changes to circuit sizes

Generated at commit: 91ffc1a56dc870f358d9e252ab8bea60d25ba554, compared to commit: e23fd0dd95f193070e4a646ce5953d22e8a09476

🧾 Summary (100% most significant diffs)

Program	%	Circuit size (+/-)	%
rollup_base_public	0.00%	-14 ✅	-0.00%
rollup_base_private	0.00%	-14 ✅	-0.00%
rollup_block_root	0.00%	-42 ✅	-0.00%
rollup_block_merge	0.00%	-28 ✅	-0.00%
rollup_root	0.00%	-28 ✅	-0.00%
rollup_merge	0.00%	-28 ✅	-0.00%
parity_root	0.00%	-56 ✅	-0.00%
private_kernel_empty	0.00%	-14 ✅	-0.00%

Full diff report 👇

Program	ACIR opcodes (+/-)	%	Circuit size (+/-)	%
rollup_base_public	3,851,252 (0)	0.00%	12,617,703 (-14)	-0.00%
rollup_base_private	3,619,773 (0)	0.00%	11,224,925 (-14)	-0.00%
rollup_block_root	682,326 (0)	0.00%	4,293,357 (-42)	-0.00%
rollup_block_merge	32,406 (0)	0.00%	1,900,773 (-28)	-0.00%
rollup_root	32,390 (0)	0.00%	1,900,759 (-28)	-0.00%
rollup_merge	1,791 (0)	0.00%	1,744,924 (-28)	-0.00%
parity_root	4,290 (0)	0.00%	3,487,877 (-56)	-0.00%
private_kernel_empty	967 (0)	0.00%	864,991 (-14)	-0.00%

jeanmon

I just looked at the AVM related changes.

jeanmon · 2024-12-05T09:24:43Z

barretenberg/cpp/src/barretenberg/vm/avm/generated/flavor.hpp

@@ -121,6 +121,9 @@ class AvmFlavor {
    using VerifierCommitmentKey = AvmFlavorSettings::VerifierCommitmentKey;
    using RelationSeparator = AvmFlavorSettings::RelationSeparator;

+    // indicates when evaluating sumcheck, edges must be extended to be MAX_TOTAL_RELATION_LENGTH
+    static constexpr bool USE_SHORT_MONOMIALS = false;


Please port this change in bb-pilcom/bb-pil-backend/templates/flavor.hpp.hbs
Alternatively, you can ping AVM team and we can do it.

Note that the recursive flavor .hpp counterpart is not generated (therefore no change there)

just updated flavor.hpp.hbs

jeanmon · 2024-12-05T09:26:25Z

barretenberg/cpp/src/barretenberg/vm/avm/recursion/recursive_flavor.hpp

@@ -25,6 +25,9 @@ template <typename BuilderType> class AvmRecursiveFlavor_ {

    using Relations = AvmFlavor::Relations_<FF>;

+    // indicates when evaluating sumcheck, edges must be extended to be MAX_TOTAL_RELATION_LENGTH
+    static constexpr bool USE_SHORT_MONOMIALS = false;


Would it make sense to align it with the native flavor?
What I mean is to set it:
static constexpr bool USE_SHORT_MONOMIALS = NativeFlavor::USE_SHORT_MONOMIALS;

good call, updated

maramihali · 2024-12-05T12:32:34Z

barretenberg/cpp/src/barretenberg/ultra_honk/decider_keys.hpp

+        // Set the size corresponding to the number of rows in the execution trace
+        // Iterate over the prover polynomials' views corresponding to each proving key
+        for (size_t dpk_idx = 0; auto& get_all : prover_polynomials_views) {
+            // Iterate over all columns in the trace execution of an proving key and extract their value at row_idx.


Suggested change

// Iterate over all columns in the trace execution of an proving key and extract their value at row_idx.

// Iterate over all columns in the trace execution of a proving key and extract their value at row_idx.

maramihali · 2024-12-05T12:42:50Z

barretenberg/cpp/src/barretenberg/ultra_honk/decider_keys.hpp

+        typename Flavor::template ProverUnivariates<2> results;
+        // Set the size corresponding to the number of rows in the execution trace
+        // Iterate over the prover polynomials' views corresponding to each proving key
+        for (size_t dpk_idx = 0; auto& get_all : prover_polynomials_views) {


get_all can be made const I believe and made renamed view

could you clarify by what you mean by "renamed view"? I don't fully understand

sorry "made renamed" was a typo, I meant rename to view and make const. But no strong preference to the name, was just thinking that you're iteration over something called views

maramihali · 2024-12-05T12:45:49Z

barretenberg/cpp/src/barretenberg/sumcheck/sumcheck.hpp

@@ -115,7 +115,8 @@ transcript. These operations are taken care of by \ref bb::BaseTranscript "Trans
 The Sumcheck output is specified by \ref bb::SumcheckOutput< Flavor >.
 */
 template <typename Flavor> class SumcheckProver {
-
+    // PartiallyEvaluatedMultivariates OR ProverPolynomials


maybe move this comment above ProverPolynomials and PartiallyEvaluatedMultivariates

maramihali

Left a couple of questions and requests for extra tests of interaction betweenUnivariate and UnivariateMonomial classes

maramihali · 2024-12-05T12:46:43Z

barretenberg/cpp/src/barretenberg/stdlib_circuit_builders/ultra_recursive_flavor.hpp

@@ -54,6 +54,9 @@ template <typename BuilderType> class UltraRecursiveFlavor_ {
    using NativeFlavor = UltraFlavor;
    using NativeVerificationKey = NativeFlavor::VerificationKey;

+    // indicates when evaluating sumcheck, edges can be left as degree-1 monomials
+    static constexpr bool USE_SHORT_MONOMIALS = true;


Suggested change

static constexpr bool USE_SHORT_MONOMIALS = true;

static constexpr bool USE_SHORT_MONOMIALS = UltraFlavor::USE_SHORT_MONOMIALS;

maramihali · 2024-12-05T12:47:04Z

barretenberg/cpp/src/barretenberg/stdlib_circuit_builders/mega_recursive_flavor.hpp

@@ -40,6 +40,8 @@ template <typename BuilderType> class MegaRecursiveFlavor_ {
    using NativeFlavor = MegaFlavor;
    using NativeVerificationKey = NativeFlavor::VerificationKey;

+    // indicates when evaluating sumcheck, edges can be left as degree-1 monomials
+    static constexpr bool USE_SHORT_MONOMIALS = true;


ditto here, use the value from the native flavor

maramihali · 2024-12-05T12:48:37Z

barretenberg/cpp/src/barretenberg/relations/ultra_arithmetic_relation.hpp

+            // tmp *= scaling_factor;
+            // std::get<0>(evals) += tmp;
+
+            using MonomialAccumulator = typename Accumulator::MonomialAccumulator;


MonomialAccumulator can be used from above?

maramihali · 2024-12-05T12:50:35Z

barretenberg/cpp/src/barretenberg/relations/ultra_arithmetic_relation.hpp

@@ -83,46 +83,98 @@ template <typename FF_> class UltraArithmeticRelationImpl {
                                  const FF& scaling_factor)
    {
        PROFILE_THIS_NAME("Arithmetic::accumulate");


Seems to me like everything has become a MonomialAccumulator so I think we could remove _m suffix from names, here and in all other relations

some of the later terms in the relation will be of the Accumulator type (e.g. tmp0 in this file).

I figured as a general rule it might be easier to read what's going on by applying a heuristic that _m indicates the type is a MonomialAccumulator, given we use auto type declarations for frequently

maramihali · 2024-12-05T12:52:59Z

barretenberg/cpp/src/barretenberg/eccvm/eccvm_flavor.hpp

@@ -40,6 +40,9 @@ class ECCVMFlavor {
    using RelationSeparator = FF;
    using MSM = bb::eccvm::MSM<CycleGroup>;

+    // indicates when evaluating sumcheck, edges must be extended to be MAX_TOTAL_RELATION_LENGTH
+    static constexpr bool USE_SHORT_MONOMIALS = false;


add to translator and eccvm recursive flavor?

fixed. I'm curious why the tests all passed without this. Do we not compile tests that use the sumcheck Prover for the translator and eccvm recursive flavours?

oh, now that I think about it, this flag is only useful for the prover, and given we only ever instantiate the verifiers with recursive flavors the flag is not necessary in them, my bad

maramihali · 2024-12-05T13:14:21Z

barretenberg/cpp/src/barretenberg/protogalaxy/protogalaxy_prover_internal.hpp

@@ -391,42 +405,43 @@ template <class DeciderProvingKeys_> class ProtogalaxyProverInternal {
        // doesn't skip computation), so we need to define types depending on the template instantiation
        using ThreadAccumulators = TupleOfTuples;
        using ExtendedUnivatiatesType =
-            std::conditional_t<skip_zero_computations, ExtendedUnivariates, ExtendedUnivariatesNoOptimisticSkipping>;
+
+            std::conditional_t<Flavor::USE_SHORT_MONOMIALS,


same question here as to whether we still do optimistic skipping

I think that we do still do optimistic skipping. I tried to trace where this type is used, and it seems to only be used when initialising the AllEntities data structure passed into the accumulate method for our relations.

In our relation classes, the Accumulator type is derived from the types in ContainerOverSubrelations. This in turn is the same as the type TupleOfTuplesOfUnivariates_ param in accumulate_relation_univariates from protogalaxy_prover_impl.hpp, which is the same as the TupleOfTuples param in compute_combiner which is, from what I can tell, the TupleOfTuplesOfUnivariates type defined in protogalaxy_prover.hpp and this type does support skipping

Phew. I might try to rationalise this a bit as I am not sure the template parameter propagation in the protogalaxy methods is required as the type used is defined in the class

I just pushed a change which removes the template parameter types in compute_combiner and accumulate_relation_univariates. The only time we need to not optimitically skip seems to be in combiner.test.cpp (which is why we needed parametrisable types), so I created bespoke methods for combiner.test.cpp by defining a new class PGInternalTest that inherits from ProtogalaxyProverInternal and adds back in methods that enable not skipping.

While this is more lines of code overall, I think it makes ProtogalaxyProverInternal cleaner and easier to read, as there are fewer template parameter propagation chains to follow when examining the code. wdyt?

maramihali · 2024-12-05T13:15:36Z

barretenberg/cpp/src/barretenberg/relations/auxiliary_relation.hpp

+        limb_subproduct += (w_1_shift_m * w_2_shift_m);
+        auto non_native_field_gate_1_m = limb_subproduct;
+        non_native_field_gate_1_m -= (w_3_m + w_4_m);
+        auto non_native_field_gate_1 = ShortAccumulator(non_native_field_gate_1_m) * ShortAccumulator(q_3_m);


will you add a brief comment as to why the ShortAccumulator transformation is required here?

added comment

maramihali · 2024-12-05T13:17:39Z

barretenberg/cpp/src/barretenberg/relations/databus_lookup_relation.hpp

@@ -184,16 +185,18 @@ template <typename FF_> class DatabusLookupRelationImpl {
    template <typename Accumulator, size_t bus_idx, typename AllEntities, typename Parameters>
    static Accumulator compute_write_term(const AllEntities& in, const Parameters& params)
    {
+        using MonomialAccumulator = typename Accumulator::MonomialAccumulator;
        using View = typename Accumulator::View;


View and ParameterView seem to be not used anymore?

maramihali · 2024-12-05T13:19:34Z

barretenberg/cpp/src/barretenberg/relations/ecc_op_queue_relation.hpp

-        auto lagrange_ecc_op = View(in.lagrange_ecc_op);
+        using MonomialAccumulator = typename Accumulator::MonomialAccumulator;
+
+        auto w_1 = Accumulator(MonomialAccumulator(in.w_l));


why do we handle things differently here in comparison to other relations?

the subrelation degree is very low (3) which makes it less efficient to use the coefficient basis, I think.

To do a degree-1 multiplication in the coefficient basis requires 3 Fp muls and 4 Fp adds (karatsuba multiplication). But a multiplication of a degree-3 Univariate only requires 3 Fp muls

I will add a comment explaining this

maramihali · 2024-12-05T13:23:00Z

barretenberg/cpp/src/barretenberg/relations/poseidon2_internal_relation.hpp


+        auto q_pos_by_scaling_m = (q_poseidon2_internal_m * scaling_factor);
+        auto q_pos_by_scaling = Accumulator(q_pos_by_scaling_m);


The call to Accumulator is because we need extra values to properly perform subsequent computations right?

Moved methods in ProtogalaxyProverInternal that did not optimistically skip into a separate class `PGInternalTest` in `combiner.test.cpp`

renamed "MonomialAccumulator" to "CoefficientAccumulator"

maramihali

Thanks for the updates!

maramihali · 2024-12-11T17:35:47Z

barretenberg/cpp/src/barretenberg/polynomials/univariate.hpp

@@ -102,17 +102,17 @@ template <class Fr, size_t domain_end, size_t domain_start = 0, size_t skip_coun
        evaluations[domain_end - 1] = prev;
    }

-    // explicit operator UnivariateMonomial<Fr, 2, 0, 0>() const
+    // explicit operator UnivariateCoefficientBasis<Fr, 2, 0, 0>() const


zac-williamson added 21 commits November 8, 2024 10:13

add monomial accumulator

1926c6b

wip

3c96f4f

relation updates

b38ff10

wip

0922902

wip

9c47d26

wip

f0673e2

wip

019d8aa

wip

af2df21

wip

ae4246e

wip

a5d457e

wip

1d0fbb0

wip

e66e3d6

wip

ec321d1

wip

5c07a8a

Merge branch 'master' into zw/monomial-accumulaator

32f9858

small cleanup

5d78d66

test inlines

a3e47d9

add short univariate case to sumcheck prover

911801f

move small computations within thread block

2a0b185

tweaks

da6b1a6

tweaks

81315c7

zac-williamson requested a review from maramihali December 4, 2024 18:03

zac-williamson requested review from jeanmon, IlyasRidhuan and fcarreiro as code owners December 4, 2024 18:03

jeanmon reviewed Dec 5, 2024

View reviewed changes

updated flavor.hpp.hbs to generate USE_SHORT_MONOMIALS

160e842

zac-williamson requested a review from Maddiaa0 as a code owner December 5, 2024 12:02

recursive_flavor derives USE_SHORT_MONOMIALS

e8d3508

compiler fixes

4b9af43

maramihali reviewed Dec 5, 2024

View reviewed changes

fcarreiro removed request for fcarreiro, IlyasRidhuan and Maddiaa0 December 5, 2024 15:06

zac-williamson added 6 commits December 10, 2024 13:55

reduced tparams in ProtogalaxyProverInternal

21b8d22

Moved methods in ProtogalaxyProverInternal that did not optimistically skip into a separate class `PGInternalTest` in `combiner.test.cpp`

Updated to reflect PR comments

3e1065b

more PR feedback

12959ef

more PR feedback

4e4aa74

added tests for UnivariateMonomial

f051728

renamed "UnivariateMonomial" to "UnivariateCoefficientBasis"

a099809

renamed "MonomialAccumulator" to "CoefficientAccumulator"

maramihali approved these changes Dec 11, 2024

View reviewed changes

zac-williamson added 4 commits December 12, 2024 11:35

Merge branch 'master' into zw/monomial-accumulaator

159c1aa

PR comments

2a627df

Merge branch 'master' into zw/monomial-accumulaator

2b05b43

Merge branch 'master' into zw/monomial-accumulaator

874e7ef

zac-williamson merged commit 15475f4 into master Dec 19, 2024
77 checks passed

zac-williamson deleted the zw/monomial-accumulaator branch December 19, 2024 15:12

	// Iterate over all columns in the trace execution of an proving key and extract their value at row_idx.
	// Iterate over all columns in the trace execution of a proving key and extract their value at row_idx.

	static constexpr bool USE_SHORT_MONOMIALS = true;
	static constexpr bool USE_SHORT_MONOMIALS = UltraFlavor::USE_SHORT_MONOMIALS;


		auto q_pos_by_scaling_m = (q_poseidon2_internal_m * scaling_factor);
		auto q_pos_by_scaling = Accumulator(q_pos_by_scaling_m);

feat: added a UnivariateMonomial representation to reduce field ops in protogalaxy+sumcheck #10401

feat: added a UnivariateMonomial representation to reduce field ops in protogalaxy+sumcheck #10401

Conversation

zac-williamson commented Dec 4, 2024

github-actions bot commented Dec 4, 2024 • edited Loading

Changes to circuit sizes

🧾 Summary (100% most significant diffs)

jeanmon 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

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

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

maramihali left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

github-actions bot commented Dec 4, 2024 •

edited

Loading