feat: removed redundant scalar muls from the verifiers using shplemini #9392

iakovenkos · 2024-10-24T10:38:17Z

Reduced the number of scalar multiplications to be performed by the native and recursive verifiers running shplemini
Slightly re-shuffled the entities in Translator and ECCVM, so that entitied to be shifted and their shifts form contiguous ranges
This is useful for amortizing the verification costs in the case of ZK sumcheck
The Translator recursive verifier circuit is now around 820K gates as opposed to 1700K. For other Flavors, the numbers are not as dramatic, but there's still around -10% in scalar muls and the sizes of recursive verifiers.

github-actions · 2024-10-24T11:00:01Z

Changes to circuit sizes

Generated at commit: a50fedb8152b39e1e3b863fdae8f14b0008761b8, compared to commit: 7766c8e714185d6e8b9fa392d7f371fb30da8f1a

🧾 Summary (100% most significant diffs)

Program	%	Circuit size (+/-)	%
rollup_base	0.00%	-78,088 ✅	-2.33%
public_kernel_tail	0.00%	-78,087 ✅	-3.44%
public_kernel_merge	0.00%	-78,087 ✅	-7.08%
rollup_block_merge	0.00%	-156,173 ✅	-8.19%
rollup_root	0.00%	-156,173 ✅	-8.19%
rollup_merge	0.00%	-156,141 ✅	-8.20%
rollup_block_root	0.00%	-234,229 ✅	-8.22%
parity_root	0.00%	-312,315 ✅	-8.24%
private_kernel_empty	0.00%	-78,055 ✅	-8.30%

Full diff report 👇

Program	ACIR opcodes (+/-)	%	Circuit size (+/-)	%
rollup_base	478,886 (0)	0.00%	3,278,882 (-78,088)	-2.33%
public_kernel_tail	258,538 (0)	0.00%	2,191,958 (-78,087)	-3.44%
public_kernel_merge	52,901 (0)	0.00%	1,024,210 (-78,087)	-7.08%
rollup_block_merge	7,499 (0)	0.00%	1,751,100 (-156,173)	-8.19%
rollup_root	7,483 (0)	0.00%	1,751,086 (-156,173)	-8.19%
rollup_merge	3,876 (0)	0.00%	1,747,898 (-156,141)	-8.20%
rollup_block_root	4,502 (0)	0.00%	2,614,728 (-234,229)	-8.22%
parity_root	5,717 (0)	0.00%	3,478,203 (-312,315)	-8.24%
private_kernel_empty	671 (0)	0.00%	861,907 (-78,055)	-8.30%

…l/aztec-packages into si/shplemini-shifts-removal

iakovenkos · 2024-10-25T12:01:10Z

barretenberg/cpp/src/barretenberg/translator_vm/translator_circuit_builder.hpp

@@ -96,53 +96,58 @@ class TranslatorCircuitBuilder : public CircuitBuilderBase<bb::fr> {
        X_LOW_Y_HI,
        X_HIGH_Z_1,
        Y_LOW_Z_2,
-        P_X_LOW_LIMBS,                    // P.xₗₒ split into 2 68 bit limbs


had to sort the entities differently to get a contiguous range of repeating commitments

iakovenkos · 2024-10-25T12:02:16Z

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

@@ -122,91 +128,91 @@ class ECCVMFlavor {
    template <typename DataType> class WireEntities {
      public:
        DEFINE_FLAVOR_MEMBERS(DataType,
-                              transcript_add,                              // column 0


had to sort the entities differently to get a contiguous range of repeating commitments

iakovenkos · 2024-10-25T12:03:28Z

barretenberg/cpp/src/barretenberg/stdlib_circuit_builders/mega_flavor.hpp

@@ -77,7 +90,7 @@ class MegaFlavor {
    static constexpr size_t BATCHED_RELATION_PARTIAL_LENGTH = MAX_PARTIAL_RELATION_LENGTH + 1;
    static constexpr size_t NUM_RELATIONS = std::tuple_size_v<Relations>;
    // The total number of witnesses including shifts and derived entities.
-    static constexpr size_t NUM_ALL_WITNESS_ENTITIES = 23;
+    static constexpr size_t NUM_ALL_WITNESS_ENTITIES = NUM_WITNESS_ENTITIES + NUM_SHIFTED_WITNESSES;


Luke pointed out that this constant got stale. Now it should be more robust

iakovenkos · 2024-10-25T12:06:06Z

barretenberg/cpp/src/barretenberg/commitment_schemes/shplonk/shplemini.hpp

@@ -439,5 +439,71 @@ template <typename Curve> class ShpleminiVerifier_ {
            commitments.emplace_back(std::move(fold_commitments[j]));
        }
    }
+


the main feature introduced in this PR

maramihali

I think this work should be restructed a bit differently, as I mentioned in the other comments I think a single data structure with the required index constants should be created in the flavors (well maybe two given the concatenation edge case) and passed to Shplemini. Also I think remove_shifted_commitments should be a method isolated in Shplemini not called from the verifiers. I added some more thoughts in my comments.

maramihali · 2024-10-29T19:12:16Z

barretenberg/cpp/src/barretenberg/commitment_schemes/shplonk/shplemini.hpp

+     * of scalars. This method iterates over the commitments and scalars in a BatchOpeningClaim object
+     *
+     */
+    static void remove_shifted_commitments(BatchOpeningClaim<Curve>& accumulator,


I think this method should probably not be called from the verifier classes, but rather be part of the "reduce_verify" stage in Shplemini, in which a BatchOpeningClaim is computed and then the shifted commitments are removed.

maramihali · 2024-10-29T19:13:36Z

barretenberg/cpp/src/barretenberg/ultra_honk/decider_verifier.cpp

+                                                                Commitment::one(),
+                                                                transcript);
+    Shplemini::remove_shifted_commitments(opening_claim,
+                                          Flavor::TO_BE_SHIFTED_WITNESSES_START,


These indexes should be passed as a single data structure constructed in the flavor

done, created a struct for this

maramihali · 2024-10-29T19:15:38Z

barretenberg/cpp/src/barretenberg/commitment_schemes/ipa/ipa.test.cpp

+
+    // Generate multilinear polynomials, their commitments (genuine and mocked) and evaluations (genuine) at a random
+    // point.
+    auto mle_opening_point = this->random_evaluation_point(log_n); // sometimes denoted 'u'


We really need to clean up these pcs test files by having single methods that generate input rather than duplicating code over and over again (similar to what we do for circuits). I previously added an issue on this. Just saying, not suggesting that it's something that should be done in this PR

maramihali · 2024-10-29T19:23:11Z

barretenberg/cpp/src/barretenberg/translator_vm/translator_verifier.cpp

+                                          Flavor::NUM_SHIFTED_WITNESSES,
+                                          Flavor::TO_BE_CONCATENATED_START,
+                                          Flavor::CONCATENATED_START,
+                                          Flavor::NUM_CONCATENATED);


i think NUM_CONCATENATED can be determined from the other inputs no?

maramihali · 2024-10-29T19:26:04Z

barretenberg/cpp/src/barretenberg/commitment_schemes/shplonk/shplemini.hpp

+     * verifier.
+     *
+     * @details The Shplemini verifier gets the access to multiple groups of commitments, some of which are duplicated
+     * by design. This method combines the scalars associated with these repeating commitments, reducing the total


will you please explain why here?

expanded slightly
I think, the real answer - it's just easier to have those entities and shifts

iakovenkos · 2024-11-12T17:03:44Z

barretenberg/cpp/src/barretenberg/stdlib_circuit_builders/ultra_flavor.hpp

+    static constexpr size_t NUM_SHIFTED_TABLES = 4;
+
+    // A container to be fed to ShpleminiVerifier to avoid redundant scalar muls
+    static constexpr RepeatedCommitmentsData REPEATED_COMMITMENTS =


still somewhat ugly here, but I think expressing everything in terms of numbers of entities is a better practice than just constants with the required indexes. e.g. someone would delete shifted tables - delete the constant - nothing would be broken

maramihali

approved, pending a follow-up cleanup PR to remove the use of erase if possible, also a small comment

maramihali · 2024-11-12T17:57:39Z

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

-    static constexpr size_t SHIFTED_WITNESSES_START = 90;
+    static constexpr size_t NUM_ALL_WITNESS_ENTITIES = NUM_WITNESS_ENTITIES + NUM_SHIFTED_ENTITIES;
+    // Container to be fed to ShpleminiVerifier to avoid redundant scalar muls, the first number is the index of the
+    // first witness to be shifted. -1 appears because WitnessEntities contain


unfinished comment?

iakovenkos and others added 10 commits October 13, 2024 22:53

added a method to remove shifted commitments

4702ddd

eccvm supports shifted removal

ebb5c06

Merge branch 'master' into si/zk-sumcheck-plus-shplemini

738565e

removed shifted comms from mega and eccvm verifiers

fc161ec

translator draft adjustments

b417485

Merge branch 'master' into si/shplemini-shifts-removal

33fc216

translator 820k

ed20963

removed shifted commitments in all shplemini verifiers

630e10c

restored zeromorph's master state

7a2028a

Merge branch 'master' into si/shplemini-shifts-removal

4f5edc4

iakovenkos added 4 commits October 25, 2024 11:52

tests + docs + clean-up

4ac6cc7

Merge branch 'si/shplemini-shifts-removal' of github.com:AztecProtoco…

9086b3e

…l/aztec-packages into si/shplemini-shifts-removal

Merge branch 'master' into si/shplemini-shifts-removal

acbd1a5

noisy empty lines removed

3392bec

iakovenkos commented Oct 25, 2024

View reviewed changes

iakovenkos added the e2e-prover-full CI: Enables this CI job. label Oct 25, 2024

iakovenkos self-assigned this Oct 25, 2024

iakovenkos requested a review from maramihali October 25, 2024 14:53

maramihali requested changes Oct 29, 2024

View reviewed changes

maramihali reviewed Oct 29, 2024

View reviewed changes

iakovenkos and others added 6 commits November 12, 2024 11:59

resolving comments

a1d1796

Merge branch 'master' into si/shplemini-shifts-removal

4681a19

added offset for zk

96cc1b0

small fixes

8eff6aa

Merge branch 'master' into si/shplemini-shifts-removal

774f117

reverted changes in ultra and mega/removed assert

df0fd90

iakovenkos commented Nov 12, 2024

View reviewed changes

iakovenkos and others added 2 commits November 12, 2024 17:08

slightly changed docs [skip ci]

5898638

Merge branch 'master' into si/shplemini-shifts-removal

4c7360b

maramihali approved these changes Nov 14, 2024

View reviewed changes

iakovenkos mentioned this pull request Nov 14, 2024

Refactor the removal of repeated commitments in Shplemini + Better structure in Flavors' entities AztecProtocol/barretenberg#1151

Open

iakovenkos and others added 3 commits November 14, 2024 17:11

fixed comment

0ca39f9

Merge branch 'master' into si/shplemini-shifts-removal

90482ca

added a todo

5af5391

iakovenkos enabled auto-merge (squash) November 14, 2024 17:33

iakovenkos merged commit e07cac7 into master Nov 14, 2024
42 checks passed

iakovenkos deleted the si/shplemini-shifts-removal branch November 14, 2024 17:45

AztecBot mentioned this pull request Nov 14, 2024

chore(master): Release 0.63.0 #9651

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

feat: removed redundant scalar muls from the verifiers using shplemini #9392

feat: removed redundant scalar muls from the verifiers using shplemini #9392

iakovenkos commented Oct 24, 2024 •

edited

Loading

github-actions bot commented Oct 24, 2024 •

edited

Loading

iakovenkos Oct 25, 2024

iakovenkos Oct 25, 2024

iakovenkos Oct 25, 2024

iakovenkos Oct 25, 2024 •

edited

Loading

maramihali left a comment

maramihali Oct 29, 2024

iakovenkos Nov 12, 2024

maramihali Oct 29, 2024

iakovenkos Nov 12, 2024

maramihali Oct 29, 2024

maramihali Oct 29, 2024

maramihali Oct 29, 2024

iakovenkos Nov 12, 2024

iakovenkos Nov 12, 2024 •

edited

Loading

maramihali left a comment

maramihali Nov 12, 2024

feat: removed redundant scalar muls from the verifiers using shplemini #9392

feat: removed redundant scalar muls from the verifiers using shplemini #9392

Conversation

iakovenkos commented Oct 24, 2024 • edited Loading

github-actions bot commented Oct 24, 2024 • edited Loading

Changes to circuit sizes

🧾 Summary (100% most significant diffs)

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

iakovenkos Oct 25, 2024 • edited Loading

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

iakovenkos Nov 12, 2024 • edited Loading

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

iakovenkos commented Oct 24, 2024 •

edited

Loading

github-actions bot commented Oct 24, 2024 •

edited

Loading

iakovenkos Oct 25, 2024 •

edited

Loading

iakovenkos Nov 12, 2024 •

edited

Loading