Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Commit multiple columns using a single Merkle Tree #47

Merged
merged 18 commits into from Jun 13, 2023

Conversation

schouhy
Copy link
Contributor

@schouhy schouhy commented Jun 8, 2023

This PR adds the following:

  1. Use a modified version of Merkle trees that don't hash back to Field Elements and builds the entire tree using bytes.
  2. Instead of building a Merkle tree for each column of the RAP, use a single Merkle tree for the trace columns of the main part of the RAP another Merkle tree for the second part. The data of each leaf of these merkle trees are the vectors of evaluations of all the polynomials involved.

There are two merkle trees for each part of the RAP because the prover needs to commit to the first ones before getting the RAP challenges from the verifier. Improvements on this are left for another PR.

Benchmarking CAIRO/fibonacci/10: Collecting 10 samples in estimated 31.762 s (99
CAIRO/fibonacci/10      time:   [31.787 ms 32.771 ms 34.208 ms]
                        change: [-42.359% -40.011% -37.434%] (p = 0.00 < 0.05)
                        Performance has improved.
Benchmarking CAIRO/fibonacci/30: Collecting 10 samples in estimated 32.952 s (44
CAIRO/fibonacci/30      time:   [67.688 ms 68.215 ms 69.366 ms]
                        change: [-38.890% -36.275% -33.590%] (p = 0.00 < 0.05)
                        Performance has improved.

@codecov-commenter
Copy link

codecov-commenter commented Jun 8, 2023

Codecov Report

Merging #47 (2556a4a) into main (7f0178e) will increase coverage by 0.18%.
The diff coverage is 99.54%.

@@            Coverage Diff             @@
##             main      #47      +/-   ##
==========================================
+ Coverage   97.84%   98.02%   +0.18%     
==========================================
  Files          33       33              
  Lines        4956     5075     +119     
==========================================
+ Hits         4849     4975     +126     
+ Misses        107      100       -7     
Impacted Files Coverage Δ
src/fri/fri_decommit.rs 0.00% <ø> (ø)
src/proof.rs 0.00% <ø> (ø)
src/lib.rs 98.94% <99.24%> (+0.50%) ⬆️
src/fri/fri_commitment.rs 100.00% <100.00%> (ø)
src/fri/mod.rs 98.85% <100.00%> (ø)
src/prover.rs 99.83% <100.00%> (-0.01%) ⬇️
src/verifier.rs 99.25% <100.00%> (-0.02%) ⬇️

... and 1 file with indirect coverage changes

📣 We’re building smart automated test selection to slash your CI/CD build times. Learn more

@schouhy schouhy marked this pull request as ready for review June 13, 2023 15:12
@gabrielbosio gabrielbosio added this pull request to the merge queue Jun 13, 2023
Merged via the queue into main with commit 71ac73d Jun 13, 2023
3 of 5 checks passed
@gabrielbosio gabrielbosio deleted the optimize-merkle branch June 13, 2023 17:49
feltroidprime pushed a commit to feltroidprime/lambdaworks_cairo_prover that referenced this pull request Jun 15, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

6 participants