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

blevm aggregator: range proof specs #148

Open
tuxcanfly opened this issue Feb 11, 2025 · 0 comments · May be fixed by #154
Open

blevm aggregator: range proof specs #148

tuxcanfly opened this issue Feb 11, 2025 · 0 comments · May be fixed by #154
Assignees
Labels
demo Needed to complete demo enhancement New feature or request

Comments

@tuxcanfly
Copy link
Contributor

Currently blevm aggregator proves two adjancent blocks. We need to to extend this to the range we want to prove from evm-prover. There are a couple of ways to do this:

iterate

We can simply extend the current aggregator to read a variable number of proofs and match each adjacent header hash. The variable number can be the first input to the program should be at least 2. This is the easiest to implement but it scales linearly with the number of blocks and is not parallellisable.

tree

We can turn the range into a binary, ternary, or 4-ary tree where each proof is a leaf node and they are pairwise aggregated into intermediate nodes until a root node remains. It is parallelisable and scales lograrithmically with number of blocks.

merge

We can split the range into left and right halves and recursively combine them, the base case being two adjacent blocks. When merging we can ensure continuity in the header hash. It is parallelisable and scales logarithmically with the number of blocks.

I think it's easiest to start with the iterative approach. If we want to optimize we can switch to the merge approach.

@tuxcanfly tuxcanfly linked a pull request Feb 12, 2025 that will close this issue
@rootulp rootulp added the enhancement New feature or request label Feb 13, 2025
@rootulp rootulp added the demo Needed to complete demo label Feb 14, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
demo Needed to complete demo enhancement New feature or request
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants