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

Add CTLs across segment proofs #755

Open
sai-deng opened this issue Oct 28, 2024 · 2 comments
Open

Add CTLs across segment proofs #755

sai-deng opened this issue Oct 28, 2024 · 2 comments
Assignees

Comments

@sai-deng
Copy link
Contributor

sai-deng commented Oct 28, 2024

@4l0n50 mentioned an great idea this morning to have all Keccak operations at the last segment, along with some assembly logic changes.

I think it may also be possible to implement this as cross-lookup among segment proofs. Instead of performing Keccak CTL check within the root (segment) circuit, we could modify the segment aggregation circuit to include CTL across segment proofs. This way, we can move all Keccak operations into a single segment and use it as the global lookup table for all other segments.

This method should also help reduce the size of other tables, including the kernel size in the memory table, among others. As a result, we can achieve improved recursion and proving speeds.

@github-project-automation github-project-automation bot moved this to Backlog in Zero EVM Oct 28, 2024
@sai-deng sai-deng self-assigned this Oct 28, 2024
@Nashtare
Copy link
Collaborator

Related issue (benefiting from cross segment CTLs): #244

@sai-deng
Copy link
Contributor Author

Some thoughts on implementation details:

We first need to generate all segment traces, which could be a drawback as it requires more memory. Next, we need to observe the trace caps of tables in all segments before generating the random oracles and starting the proving process. We will make the challenger state and all challenges public inputs for segment proofs. In the last segment, we need to ensure that the challenger’s outputs match the public challenge values.

@Nashtare Nashtare added this to the Performance Tuning milestone Nov 4, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
Status: Backlog
Development

No branches or pull requests

2 participants