feat: ZeroMorph #2664

ledwards2225 · 2023-10-03T20:02:15Z

Adds ZeroMorph functionality (without zk) required to prove and verify batched multilinear evaluation claims, including efficient handling of shifts. For now, the protocol is fully laid out in a test. Incorporation into honk will be done in a separate PR.

The best resource for understanding this PR is this companion doc. The full batched protocol description therein matches the implementation.

Note: The goal of this first pass was to make the implementations as clear as possible. There are many simple optimizations that could be introduced to make things more efficient.

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

Very nice work! Thank you for the clear explanations in the code and HackMD. There are some things unclear to me and some suggestions.

barretenberg/cpp/src/barretenberg/honk/pcs/zeromorph/zeromorph.hpp

maramihali · 2023-10-10T12:45:41Z

barretenberg/cpp/src/barretenberg/honk/pcs/zeromorph/zeromorph.hpp

+        // Compute the q_k in reverse order, i.e. q_{n-1}, ..., q_0
+        for (size_t k = 0; k < log_N; ++k) {
+            // Define partial evaluation point u' = (u_{n-k-1}, ..., u_{n-1})
+            auto partial_size = static_cast<std::ptrdiff_t>(k + 1);


I'm slightly confused, mentioned it above as well cus if it's in accordance with the paper and hackmd u'=(u_k,...,u_n-1) and then the size of the size of this should be n - k I think?

fixed, thanks

ah ok, now i understand why the partial size is k+1 because you allocate the size of the vector as n-k-1. hm, maybe partial_size should be called something else because i interpreted it as u_partial

maybe evaluation_point_size

yeah it's slightly confusing, I wasn't totally happy with this code. To be clear though, partial_size is the size of u_partial

BTW, this algorithm for computing q_k is the one that will soon be replaced by Tohru with the more efficient algorithm detailed in the paper. So this code might go away entirely soon

maramihali · 2023-10-10T14:11:26Z

barretenberg/cpp/src/barretenberg/polynomials/polynomial.cpp

+    ASSERT(size_ >= static_cast<size_t>(1 << m));
+    size_t n = numeric::get_msb(size_);
+
+    // Partial evaluation is done in m rounds l = 0,...,m-1. At the end of round l, the polynomial has been partially


Can you give an intuition on this approach, it took me a bit to understand and decipher code

Yeah took me a while to figure out how to do this myself. For whatever reason the comments on methods in this class are in the header. I left a note about intuition there - maybe that's what you are looking for?

maramihali · 2023-10-10T14:38:28Z

barretenberg/cpp/src/barretenberg/honk/pcs/zeromorph/zeromorph.hpp

+     * @brief Compute partially evaluated zeromorph identity polynomial Z_x
+     * @details Compute Z_x, where
+     *
+     *  Z_x = x * \sum_{i=0}^{m-1} f_i + \sum_{i=0}^{l-1} g_i - v * x * \Phi_n(x)


did you miss the alphas here or am I misunderstanding something?

oh, they're implicitly multiplied before f_batched and g_batched provided as inputs

Yeah you're right that the alphas were missing from the original comment then it wasnt updated when I changed the input to be the batched forms. I still havent decided whether it makes sense to the batching inside the funciton or outside. I'll fix the comment for now and this will get resolved later

maramihali · 2023-10-10T14:49:31Z

barretenberg/cpp/src/barretenberg/honk/pcs/zeromorph/zeromorph.test.cpp

+            f_polynomial += g_batched.shifted();
+
+            // The batched evaluation should match the evaluation of the batched polynomial
+            // ASSERT_EQ(v_evaluation, f_polynomial.evaluate_mle(u_challenge));


why is this commented out?

This was just a debugging sanity check, removed

maramihali · 2023-10-10T14:58:56Z

barretenberg/cpp/src/barretenberg/honk/pcs/zeromorph/zeromorph.hpp

+            // Compute scalar y^k * x^{N - deg_k - 1}
+            auto scalar = y_challenge.pow(k);
+            scalar *= x_challenge.pow(N - deg_k - 1);
+            scalar *= Fr(-1);


is it more efficient to multiply by Fr(1) than have the subtraction on line 285?

The subtraction operator is actually not defined in this case, not entirely sure why. Possibly because these are affine points and we generally want to do operations in projective form? In any case, this will be changed in the follow on to be computed as a batch mul (since that's what's natural for the recursive computation and that's the one we care about)

Oh right, I forgot to think about affine and projective while reviewing the PR wops. Can you add a TODO + issue for adding batch mul and generally converting point operations to projective form?

This will all be handled in the immediate follow on but it's really not all that important anyway since the native verifier is basically nothing more than a debugging tool

maramihali · 2023-10-10T15:01:37Z

barretenberg/cpp/src/barretenberg/honk/pcs/zeromorph/zeromorph.hpp

+        for (auto& commitment : f_commitments) {
+            auto scalar = x_challenge * alpha_pow;
+            result = result + (commitment * scalar);
+            alpha_pow *= alpha;


here, in contrast with the prover, you multiply by alpha inside the function but I think you forgot the alphas in the equation that is part of documentation

Yes, you're right, thanks. Comment fixed

And again, I'll probably make the Prover/Verifier consistent in this sense, I just haven't figured out which way to go

maramihali

see my last comment, and other than that I am happy for this to get merged, again great work :)

maramihali · 2023-10-10T18:18:04Z

barretenberg/cpp/src/barretenberg/honk/pcs/zeromorph/zeromorph.hpp

+        // Compute the q_k in reverse order, i.e. q_{n-1}, ..., q_0
+        for (size_t k = 0; k < log_N; ++k) {
+            // Define partial evaluation point u' = (u_{n-k-1}, ..., u_{n-1})
+            auto partial_size = static_cast<std::ptrdiff_t>(k + 1);


maybe evaluation_point_size

huitseeker · 2023-10-12T16:34:22Z

This looks great! but the doc linked in the comment and PR (ref) isn't public 😢

ledwards2225 · 2023-10-12T20:07:03Z

This looks great! but the doc linked in the comment and PR (ref) isn't public 😢

Working to make it public - will keep you posted!

ledwards2225 · 2023-10-13T17:31:29Z

@huitseeker Should be public now

codygunton assigned ledwards2225 Oct 3, 2023

ledwards2225 force-pushed the lde/zeromorph_part_1 branch from 3d2c140 to d7d5c03 Compare October 4, 2023 20:01

ledwards2225 changed the title ~~Lde/zeromorph part 1~~ feat: ZeroMorph (single polynomial) Oct 4, 2023

ledwards2225 requested a review from maramihali October 4, 2023 22:22

ledwards2225 marked this pull request as ready for review October 4, 2023 22:22

ledwards2225 force-pushed the lde/zeromorph_part_1 branch 2 times, most recently from e203c89 to c91a95a Compare October 6, 2023 00:58

ledwards2225 changed the title ~~feat: ZeroMorph (single polynomial)~~ feat: ZeroMorph Oct 9, 2023

ledwards2225 force-pushed the lde/zeromorph_part_1 branch 2 times, most recently from c5c6ad9 to 94afb95 Compare October 9, 2023 17:14

maramihali reviewed Oct 10, 2023

View reviewed changes

ledwards2225 added 17 commits October 10, 2023 17:52

basic prover and test in place

280ebd7

flesh out quotient construction tests a bit

a03b6c7

batched quotient function and test

c3a0b65

partial evaluate functions plus one test

0a62db6

passing Zx and phi tests

f259b55

construct pi polynomial

7c705cf

partial evaluate mle function with test

cf3be98

function for computing q_k with passing test

c7b9c28

successful verification of single poly evaluation

bfe7428

remove new poly constructor that was causing probs

6ac4a61

signedness issue

18e0137

cleanup

ad88ba1

comments

531681e

batched version including shifts

b8999a3

fix build

892a172

fix function naming

4ff340c

comment adjustments based on maras review

26d8a0d

ledwards2225 force-pushed the lde/zeromorph_part_1 branch from 94afb95 to 26d8a0d Compare October 10, 2023 17:52

maramihali approved these changes Oct 10, 2023

View reviewed changes

name update plus comment

e86ccd4

ledwards2225 merged commit a006e5a into master Oct 10, 2023
2 checks passed

ledwards2225 deleted the lde/zeromorph_part_1 branch October 10, 2023 19:30

AztecBot mentioned this pull request Oct 10, 2023

chore(master): Release 0.8.10 #2766

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

feat: ZeroMorph #2664

feat: ZeroMorph #2664

ledwards2225 commented Oct 3, 2023 •

edited

Loading

maramihali left a comment

maramihali Oct 10, 2023

ledwards2225 Oct 10, 2023

maramihali Oct 10, 2023

maramihali Oct 10, 2023

ledwards2225 Oct 10, 2023

ledwards2225 Oct 10, 2023

maramihali Oct 10, 2023

ledwards2225 Oct 10, 2023

maramihali Oct 10, 2023

maramihali Oct 10, 2023

ledwards2225 Oct 10, 2023

maramihali Oct 10, 2023

ledwards2225 Oct 10, 2023

maramihali Oct 10, 2023

ledwards2225 Oct 10, 2023

maramihali Oct 10, 2023

ledwards2225 Oct 10, 2023

maramihali Oct 10, 2023

ledwards2225 Oct 10, 2023

ledwards2225 Oct 10, 2023

maramihali left a comment

maramihali Oct 10, 2023

huitseeker commented Oct 12, 2023

ledwards2225 commented Oct 12, 2023

ledwards2225 commented Oct 13, 2023

feat: ZeroMorph #2664

feat: ZeroMorph #2664

Conversation

ledwards2225 commented Oct 3, 2023 • edited Loading

Checklist:

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

maramihali left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

huitseeker commented Oct 12, 2023

ledwards2225 commented Oct 12, 2023

ledwards2225 commented Oct 13, 2023

ledwards2225 commented Oct 3, 2023 •

edited

Loading