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.

Sign up for GitHub

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

Jump to bottom

feat(example): poseidon-based merkle-tree benchmark #285

Open
cyphersnake opened this issue Jun 11, 2024 · 7 comments
Open

feat(example): poseidon-based merkle-tree benchmark #285

cyphersnake opened this issue Jun 11, 2024 · 7 comments
Assignees
@cyphersnake

Comments

@cyphersnake
Copy link
Collaborator

cyphersnake commented Jun 11, 2024 •
edited by chaosma
Loading

Start with initial tree state. The initial tree can be fully filled with default values (e.g. hash(NULL)). Then batch update the merkle tree by a list of nodes.

Public Input
[Old Root Hash, Root Hash]
Private Input
Vec<(leaf_index, new_leaf_value)>
@cyphersnake cyphersnake self-assigned this Jun 11, 2024
@cyphersnake cyphersnake changed the title feat(example): real-world circuit bench feat(example): poseidon-based merkle-tree benchmark Jun 13, 2024
@chaosma
Copy link
Collaborator

chaosma commented Jun 13, 2024

when tree height is large e.g. 32 levels, then it is practical to start with default tree.

In bottom level (level 1), each leaf has default value v1=hash(NULL)
In next level (level 2), each node has default value v2=hash(v1,v1),
...
The root of merkle tree has default value v32=hash(v31,v31)

cyphersnake added a commit that referenced this issue Jun 13, 2024
@cyphersnake
refactor(ivc): take out step-circuit's ownership
5e40ef8 
**Motivation**
Part of #285

Our API should allow step-circuit to be changed between rounds of folding

**Overview**
It's just that now IVC is taking the step circuit from the ref
@cyphersnake cyphersnake mentioned this issue Jun 13, 2024
Merged
cyphersnake added a commit that referenced this issue Jun 14, 2024
@cyphersnake
refactor(ivc): take out step-circuit's ownership (#286)
83bd299 
**Motivation**
Our API should allow step-circuit to be changed between rounds of
folding. As part of #285, we will change the private input (merkle-tree
leaves changing) at each iteration of folding

**Overview**
It's just that now IVC is taking the step circuit from the ref
@cyphersnake
Copy link
Collaborator Author

FYI

Apart from the benchmark itself, the only thing left is the correctness of the merkle-tree calculation on-circuit

Now you can rearrange the sibling in the counting of the original root and the new one - and the circuit will think that everything is correct, but it is wrong. I'll fix it tomorrow by fixing the order of hash input with index.

But except for this nuance - the circuit is ready and working and folding

https://github.com/snarkify/sirius-test-circuits

@cyphersnake cyphersnake mentioned this issue Jun 24, 2024
Closed
@cyphersnake
Copy link
Collaborator Author

I finished to implement merkle-tree-update-circuit, collect data for all the batch we are interested in, moved to the task of implementing this circuit within halo2, so far the problem is that MockProver passes, but does not work full IPA. I'm figuring it out

@cyphersnake
Copy link
Collaborator Author

cyphersnake commented Jun 27, 2024 •
edited
Loading

Benchmark Update:

  • Code and scripts for data collection are ready
  • halo2-kzg - given by keygen/prove are collecting
    • Verify is broken, although the code is taken directly from halo2 library. I plan to still try to figure out what could be the issue.
    • BatchSize=10 take 3141s, expected very long run for BatchSize=60,80,100
    • Also the brach with kzg support can't go to master yet, because it broke all tests, postpone this
  • memory-usage - will be collect after halo2-kzg, it will take a long time to build because dhat slows down the program several times.

@cyphersnake
Copy link
Collaborator Author

Added to kzg-halo2curves branch

  • cache for keygen
  • Parameterization by env variable (cache clean & repeat_count)

BATCH_UPDATE_SIZE=1 cargo merkle-halo2-kzg
where 1 is size of batch update

For refresh keygen:
REFRESH_KEYGEN=true BATCH_UPDATE_SIZE=1 cargo merkle-halo2-kzg

This was referenced Jul 11, 2024
Merged
Merged
cyphersnake added a commit that referenced this issue Jul 11, 2024
@cyphersnake
feat(gadgets): impl merkle-tree
05cb442 
**Motivation**
Within #285 we used this gadget as a test gadget, however, due to the
fact that benchmarks will now be systematic I suggest adding it to the
main codebase

**Overview**
The implementation is a bit rough and not generalized everywhere, but it
works, so I suggest to add it to the project in this form and add an
issue for refactoring
cyphersnake added a commit that referenced this issue Jul 11, 2024
@cyphersnake
feat: migrate to halo2-scroll (#301)
3fff676 
**Issue Link / Motivation**
Using one version of halo2curves will allow us to unfreeze #287,
halo2-kzg for #285 and fix smaller bugs

**Changes Overview**
- Migrating to halo2curves and reimporting it from the crate root
- Minor edits and fixes related to another version of halo2
@cyphersnake cyphersnake mentioned this issue Jul 11, 2024
Merged
cyphersnake added a commit that referenced this issue Jul 11, 2024
@cyphersnake
feat(script): add span-fields to output (#302)
0e329ef 
**Motivation**
Without fields, information about span is incomplete, part of #285

**Overview**
Simply add the required fields to the output on the basis of logs
@cyphersnake cyphersnake mentioned this issue Jul 12, 2024
Merged
@cyphersnake cyphersnake mentioned this issue Jul 15, 2024
Closed
cyphersnake added a commit that referenced this issue Jul 16, 2024
@cyphersnake
feat(examples): merkle-tree-gadget (#303)
7304e98 
**Motivation**
Within #285 we used this gadget
as a test gadget, however, due to the
fact that benchmarks will now be systematic I suggest adding it to the
main codebase

**Overview**
The implementation is a bit rough and not generalized everywhere, but it
works, so I suggest to add it to the project in this form and add an
issue for refactoring
cyphersnake added a commit that referenced this issue Jul 16, 2024
@cyphersnake
feat(example): add merkle-{ipa,kzg} examples (#305)
fa08349 
**Motivation**
For systematic performance measurements we need references and halo2
based on ipa & kzg can act as them
Part of #285 

**Overview**
- Added halo2 code samples to run, parameters are passed through
cli-args
- Renamed cargo-alias, added abbreviation `re`('run example') instead of
postfix '-example'
@cyphersnake
Copy link
Collaborator Author

https://gist.github.com/cyphersnake/75b3f8d16991a9f1947b710a24e2a109

@cyphersnake
Copy link
Collaborator Author

Memory Usage

Repeat Count: 2

Name repeat_count Memory Footprint Memory Footprints Block Max Memory Usage Max Memory Blocks
sirius 2 21.77 GB 322927063 1.89 GB 57045
halo2_ipa 2 26.24 GB 422344955 1.90 GB 2485
halo2_kzg 2 12.02 GB 160411251 1.67 GB 2396

Repeat Count: 10

Name repeat_count Memory Footprint Memory Footprints Block Max Memory Usage Max Memory Blocks
halo2_kzg 10 25.96 GB 160392012 6.70 GB 2396
halo2_ipa 10 113.34 GB 2049823224 7.58 GB 2485
sirius 10 74.65 GB 1486734509 3.28 GB 57055

Repeat Count: 20

Name repeat_count Memory Footprint Memory Footprints Block Max Memory Usage Max Memory Blocks
sirius 20 154.73 GB 2958469916 6.04 GB 56699
halo2_kzg 20 44.98 GB 160380315 13.39 GB 2396
halo2_ipa 20 225.03 GB 4084189583 15.16 GB 2485

Repeat Count: 40

Name repeat_count Memory Footprint Memory Footprints Block Max Memory Usage Max Memory Blocks
sirius 40 304.45 GB 5885159838 11.78 GB 26319
halo2_kzg 40 82.70 GB 160368672 26.78 GB 2396
halo2_ipa 40 447.49 GB 8152945299 30.32 GB 2487

Repeat Count: 60

Name repeat_count Memory Footprint Memory Footprints Block Max Memory Usage Max Memory Blocks
halo2_kzg 60 153.27 GB 160368915 53.55 GB 2396
halo2_ipa 60 711.79 GB 12221733855 60.63 GB 2489
sirius 60 484.60 GB 8829676425 23.42 GB 26319

Repeat Count: 80

Name repeat_count Memory Footprint Memory Footprints Block Max Memory Usage Max Memory Blocks
halo2_ipa 80 878.74 GB 16290514087 60.63 GB 2485
halo2_kzg 80 153.27 GB 160368906 53.55 GB 2396
sirius 80 565.79 GB 11671429819 23.42 GB 26319

Repeat Count: 100

Name repeat_count Memory Footprint Memory Footprints Block Max Memory Usage Max Memory Blocks
halo2_kzg 100 153.27 GB 160368948 53.55 GB 2396
sirius 100 685.12 GB 14580294679 23.42 GB 26319
halo2_ipa 100 1045.70 GB 20359294333 60.63 GB 2489

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@cyphersnake cyphersnake

Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

feat(bench): poseidon-merkle tree snarkify/sirius
2 participants
@chaosma @cyphersnake