feat: mega zk features #9774

iakovenkos · 2024-11-06T11:37:43Z

Introduced MegaZKFlavor and its recursive counterpart.
The DeciderProver for MegaZKFLavor (MegaZKProver) generates random polynomials of small size to mask the round univariates in sumcheck. The evaluations of masking polynomials are batched by the ShpleminiProver/Verifier with the Gemini opening claims.
Such proofs could be verified recursively by running UltraRecursiveVerifier with MegaZKRecursiveFlavor.

…col/aztec-packages into si/zk-sumcheck-plus-shplemini

…tests

iakovenkos · 2024-11-07T12:14:41Z

barretenberg/cpp/src/barretenberg/stdlib/honk_verifier/oink_recursive_verifier.cpp

@@ -2,7 +2,9 @@

 #include "barretenberg/numeric/bitop/get_msb.hpp"
 #include "barretenberg/plonk_honk_shared/library/grand_product_delta.hpp"
-#include "barretenberg/transcript/transcript.hpp"
+#include "barretenberg/stdlib_circuit_builders/mega_recursive_flavor.hpp"
+#include "barretenberg/stdlib_circuit_builders/mega_zk_recursive_flavor.hpp"


moved flavors from the header

iakovenkos · 2024-11-07T12:22:45Z

barretenberg/cpp/src/barretenberg/stdlib/honk_verifier/ultra_recursive_verifier.test.cpp

@@ -1,10 +1,7 @@
 #include "barretenberg/stdlib/honk_verifier/ultra_recursive_verifier.hpp"
 #include "barretenberg/circuit_checker/circuit_checker.hpp"
 #include "barretenberg/common/test.hpp"
-#include "barretenberg/stdlib/hash/blake3s/blake3s.hpp"
-#include "barretenberg/stdlib/hash/pedersen/pedersen.hpp"
 #include "barretenberg/stdlib/primitives/curves/bn254.hpp"


removed redundant inclusions

iakovenkos · 2024-11-07T12:22:59Z

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

@@ -81,7 +81,7 @@ class MegaFlavor {

    // For instances of this flavour, used in folding, we need a unique sumcheck batching challenges for each
    // subrelation. This
-    // is because using powers of alpha would increase the degree of Protogalaxy polynomial $G$ (the combiner) to much.
+    // is because using powers of alpha would increase the degree of Protogalaxy polynomial $G$ (the combiner) too much.


iakovenkos · 2024-11-07T12:30:24Z

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

@@ -46,9 +46,9 @@ template <typename Flavor> struct ZKSumcheckData {
    // Constructor
    ZKSumcheckData(const size_t multivariate_d,
                   std::shared_ptr<typename Flavor::Transcript> transcript,
-                   std::shared_ptr<typename Flavor::ProvingKey> proving_key = nullptr)
+                   std::shared_ptr<typename Flavor::CommitmentKey> commitment_key = nullptr)


minor refinement, to make it work uniformly with Mega and VMs

iakovenkos · 2024-11-07T12:33:33Z

barretenberg/cpp/src/barretenberg/ultra_honk/mega_composer.test.cpp

 auto& engine = numeric::get_debug_randomness();

-class MegaHonkTests : public ::testing::Test {
-  protected:
+using FlavorTypes = ::testing::Types<MegaFlavor, MegaFlavorWithZK>;


turned it into a typed tests working with Mega and MegaZK

iakovenkos · 2024-11-07T12:34:03Z

barretenberg/cpp/src/barretenberg/ultra_honk/mega_transcript.test.cpp

@@ -11,15 +11,17 @@

 using namespace bb;



now it's typed

iakovenkos · 2024-11-07T12:37:28Z

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

-                                                                      Commitment::one(),
-                                                                      transcript);
+    BatchOpeningClaim<Curve> opening_claim;
+    if constexpr (!Flavor::HasZK) {


looks ugly, but it's temporary. i think we could template Shplemini on Flavor and get rid of this mess

iakovenkos · 2024-11-07T13:09:50Z

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

-        // u_{d-1} (1 - u_{d-1}) = 0 \f$. This equation is satisfied with probability ~ 1/|FF|, in such cases the prover
-        // has to abort and start ZK Sumcheck anew.
-        if constexpr (Flavor::HasZK) {
-            check_that_evals_do_not_leak_witness_data(multivariate_challenge);


don't need this with the new zk strategy

iakovenkos · 2024-11-07T13:11:12Z

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


-    auto [multivariate_challenge, claimed_evaluations, sumcheck_verified] =
+    sumcheck_output =


sumcheck output is templated on Flavor and has different number members dep on HasZK flag

…packages into si/zk-sumcheck-mega

iakovenkos · 2024-11-07T14:41:06Z

barretenberg/cpp/src/barretenberg/stdlib_circuit_builders/mega_zk_recursive_flavor.hpp

+    // BATCHED_RELATION_PARTIAL_LENGTH = algebraic degree of sumcheck relation *after* multiplying by the `pow_zeta`
+    // random polynomial e.g. For \sum(x) [A(x) * B(x) + C(x)] * PowZeta(X), relation length = 2 and random relation
+    // length = 3
+    static constexpr size_t BATCHED_RELATION_PARTIAL_LENGTH = NativeFlavor::BATCHED_RELATION_PARTIAL_LENGTH;


Once we have randomization in rows 1,2,3 in the ExecutionTrace, this value will be incremented by 1 compared to the non-zk Mega flavor

maramihali · 2024-11-07T15:06:55Z

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

    {
-        setup_zk_sumcheck_data(multivariate_d, transcript, proving_key);
+        setup_zk_sumcheck_data(multivariate_d, transcript, commitment_key);


it doesn't really make sense that ZKSumcheckData constructor just has a call to another method with the same parameters, it's an unnecessary layer of indirection, you could move the code in the constructor (also from setup_auxiliary_data).

Oh thanks! I'm still finding my way around constructors, cleaned up

maramihali · 2024-11-07T15:09:13Z

barretenberg/cpp/src/barretenberg/ultra_honk/oink_prover.hpp

-#include "barretenberg/stdlib_circuit_builders/ultra_flavor.hpp"
-#include "barretenberg/stdlib_circuit_builders/ultra_keccak_flavor.hpp"
-#include "barretenberg/transcript/transcript.hpp"
+// #include "barretenberg/transcript/transcript.hpp"


maramihali · 2024-11-07T15:17:42Z

barretenberg/cpp/src/barretenberg/ultra_honk/decider_prover.cpp

-                                         proving_key->gate_challenges);
+        if constexpr (Flavor::HasZK) {
+            auto commitment_key = std::make_shared<CommitmentKey>(proving_key->proving_key.circuit_size);
+            zk_sumcheck_data = ZKSumcheckData<Flavor>(numeric::get_msb(polynomial_size), transcript, commitment_key);


A third allocation of the commitment key is wasteful here (and the fact that you do not deallocate before sumcheck), I would prefer to have the libra polynomials committed to as part of Oink, before the commitment key is deallocated (and before the commitment key is allocated in ECCVM and Translator).

Also it seemes logical to have the generation of zk sumcheck data in Oink as other data that sumcheck is operating on

thanks for pointing this out! In all three places I switched to allocating a commitment_key of size Flavor::BATCHED_RELATION_PARTIAL_LENGTH, which is tiny and shouldn't cause any memory issues.

as a more general remark: although it's logical to commit to as many polynomials as possible in Oink, I think it's just way cleaner when the creation of these data, the commitments, and the modifications of these data are more localized: now it appears right before the sumcheck and a part of it is submiited to the Shplemini prover + in the Decider (Recursive) Verifier it is not spread between Oink and the Ultra Verifier

maramihali · 2024-11-07T15:20:41Z

barretenberg/cpp/src/barretenberg/ultra_honk/mega_composer.test.cpp

-class MegaHonkTests : public ::testing::Test {
-  protected:
+using FlavorTypes = ::testing::Types<MegaFlavor, MegaZKFlavor>;
+


will you please rename this file to mega_honk.test.cpp since there is no composer anymore

maramihali · 2024-11-07T15:21:46Z

barretenberg/cpp/src/barretenberg/benchmark/ultra_bench/mega_zk_honk.bench.cpp

+/**
+ * @brief Benchmark: Construction of a Ultra Honk proof for a circuit determined by the provided circuit function
+ */
+static void construct_proof_megahonk_zk(State& state,


I think that instead of duplicating the mega honk benchmark file you could just template the MegaHonk benchmark

I tried honestly, but it's not as nice as with the typed test suites, so prob we could keep two separate bench files for now (and maybe delete the one without zk, when we are done with zk)

maramihali · 2024-11-07T15:27:20Z

barretenberg/cpp/src/barretenberg/stdlib/honk_verifier/ultra_recursive_verifier.cpp

+            libra_commitments.push_back(libra_commitment);
+        };
+    }
+    SumcheckOutput<Flavor> sumcheck_output;


nit: SumcheckOutput sumcheck_output = sumcheck.verify(...

maramihali · 2024-11-07T15:27:51Z

barretenberg/cpp/src/barretenberg/stdlib/honk_verifier/ultra_recursive_verifier.cpp

-    auto [multivariate_challenge, claimed_evaluations, sumcheck_verified] =
-        sumcheck.verify(verification_key->relation_parameters, verification_key->alphas, gate_challenges);
-
+    BatchOpeningClaim<Curve> opening_claim;


maramihali · 2024-11-07T15:40:47Z

barretenberg/cpp/src/barretenberg/stdlib/honk_verifier/ultra_recursive_verifier.cpp

-                                                                Commitment::one(builder),
-                                                                transcript);
+    if constexpr (!Flavor::HasZK) {
+        opening_claim = Shplemini::compute_batch_opening_claim(key->circuit_size,


This if - else can be avoided if translator concatenation polynomials remain the last arguments in the function signature and the libra.commitments and evaluations are always passed to shplemini. The for loop in Shplemini would simply create no claims if the two data structures are empty.

great suggestion, thanks!

iakovenkos · 2024-11-08T09:12:25Z

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

                              const std::vector<bb::Univariate<FF, LENGTH>>& libra_univariates = {},
-                              const std::vector<FF>& libra_evaluations = {})
+                              const std::vector<FF>& libra_evaluations = {},


thanks for the suggestion. re-ordered the args in the prover and the verifier, bc concatenation groups are used less often than libra evals

maramihali · 2024-11-08T11:01:44Z

barretenberg/cpp/src/barretenberg/ultra_honk/decider_prover.cpp

@@ -33,7 +33,7 @@ template <IsUltraFlavor Flavor> void DeciderProver_<Flavor>::execute_relation_ch

        PROFILE_THIS_NAME("sumcheck.prove");
        if constexpr (Flavor::HasZK) {
-            auto commitment_key = std::make_shared<CommitmentKey>(proving_key->proving_key.circuit_size);
+            auto commitment_key = std::make_shared<CommitmentKey>(Flavor::BATCHED_RELATION_PARTIAL_LENGTH);


in a follow-up PR you would be able to refine this based on whether a realocation is needed

maramihali

thanks for the updates!

iakovenkos and others added 24 commits October 28, 2024 17:53

shplemini supports opening of libra masking univariates

2c37dc4

clean-up

7bbacc2

de-coupled sumcheck from zk sumcheck data

c78ed6e

eccvm native proves/verifies evals of masking polys

fe93b4d

debugging eccvm recursive

df7f731

debugggging still

0b3e50a

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

525ae12

eccvm recursive fixed

4298d52

opening proofs for libra polynomials in translator

bf468eb

translator relation degree changes reverted

ab9b81e

some clean-up

aca70fa

removed redundant line

b7584ba

clean-up

6403477

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

bec76b9

fix: link zero constraint relation in translator

8a1e95f

fix bb native tests

2504556

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

d18f0c2

clean up

937af2a

Merge branch 'si/zk-sumcheck-plus-shplemini' of github.com:AztecProto…

6824085

…col/aztec-packages into si/zk-sumcheck-plus-shplemini

fix build

95d4160

evaluation proofs for libra masking univariates in Mega + transcript …

6d35080

…tests

megahonk tests + bench

ac0afe5

mega with k recursive

b7b9fae

fixed mega transcript test + oink headers clean-up

db32e48

iakovenkos self-assigned this Nov 6, 2024

iakovenkos and others added 5 commits November 6, 2024 19:24

clean-up after review

69b913e

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

ed57e42

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

1775d41

resolve conflicts with 'master'

e8c691a

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

2dc2170

iakovenkos marked this pull request as draft November 7, 2024 12:12

iakovenkos commented Nov 7, 2024

View reviewed changes

Base automatically changed from si/zk-sumcheck-plus-shplemini to master November 7, 2024 12:49

iakovenkos added 3 commits November 7, 2024 12:51

clean up and renaming MegaFlavorWithZK to MegaZKFlavor

3157236

Merge branch 'master' into si/zk-sumcheck-mega

6a32b27

more clean up after merging

84bf601

iakovenkos commented Nov 7, 2024

View reviewed changes

cleaning

f2d4eb0

iakovenkos added the crypto cryptography label Nov 7, 2024

Merge branch 'master' into si/zk-sumcheck-mega

a94d29a

iakovenkos marked this pull request as ready for review November 7, 2024 13:15

iakovenkos requested a review from maramihali November 7, 2024 13:41

iakovenkos added 2 commits November 7, 2024 14:39

flavor clean-up

cef08d4

Merge branch 'si/zk-sumcheck-mega' of github.com:AztecProtocol/aztec-…

3fe9ed7

…packages into si/zk-sumcheck-mega

iakovenkos commented Nov 7, 2024

View reviewed changes

maramihali requested changes Nov 7, 2024

View reviewed changes

addressing comments

c24adea

iakovenkos commented Nov 8, 2024

View reviewed changes

maramihali reviewed Nov 8, 2024

View reviewed changes

maramihali approved these changes Nov 8, 2024

View reviewed changes

maramihali merged commit 2096dc2 into master Nov 8, 2024
47 checks passed

maramihali deleted the si/zk-sumcheck-mega branch November 8, 2024 11:02

AztecBot mentioned this pull request Nov 8, 2024

chore(master): Release 0.63.0 #9651

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

feat: mega zk features #9774

feat: mega zk features #9774

iakovenkos commented Nov 6, 2024 •

edited

Loading

iakovenkos Nov 7, 2024

iakovenkos Nov 7, 2024

iakovenkos Nov 7, 2024

iakovenkos Nov 7, 2024

iakovenkos Nov 7, 2024

iakovenkos Nov 7, 2024

iakovenkos Nov 7, 2024

iakovenkos Nov 7, 2024

iakovenkos Nov 7, 2024

iakovenkos Nov 7, 2024

maramihali Nov 7, 2024

iakovenkos Nov 7, 2024

maramihali Nov 7, 2024

maramihali Nov 7, 2024

maramihali Nov 7, 2024

iakovenkos Nov 7, 2024

maramihali Nov 7, 2024

iakovenkos Nov 7, 2024

maramihali Nov 7, 2024

iakovenkos Nov 7, 2024

maramihali Nov 7, 2024

maramihali Nov 7, 2024

maramihali Nov 7, 2024

iakovenkos Nov 7, 2024

iakovenkos Nov 8, 2024

maramihali Nov 8, 2024

maramihali left a comment


		auto [multivariate_challenge, claimed_evaluations, sumcheck_verified] =
		sumcheck_output =

feat: mega zk features #9774

feat: mega zk features #9774

Conversation

iakovenkos commented Nov 6, 2024 • 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

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

iakovenkos commented Nov 6, 2024 •

edited

Loading