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

Optimizations for Keccak memory machine and adjacent sub machines #2022

Open
qwang98 opened this issue Nov 4, 2024 · 2 comments
Open

Optimizations for Keccak memory machine and adjacent sub machines #2022

qwang98 opened this issue Nov 4, 2024 · 2 comments

Comments

@qwang98
Copy link
Collaborator

qwang98 commented Nov 4, 2024

Things I've thought of/heard of so far:

  1. One of the following to replace add_sub submachine calls
    a. Implement add4 logic in main machine, putting carry in unused cells of the main machine
    b. Usestd::machines::small_field::pointer_arith::increment_ptr instead

  2. Fix many links to the memory machine (a language fix).

  3. (Suggested by @georgwiese but I'm not sure how) Fix memory machine, which currently uses one additional fixed column for each permutation call, and another accumulation column overall.

@qwang98
Copy link
Collaborator Author

qwang98 commented Nov 4, 2024

After implementing 1.b. in #1832 and testing with the same witness generation time as simply using 100 add_sub links, I think 1.a. would have similar results. It's essentially the same as 1.b., but just one fewer carry column (carry will be stored in unused cells in the main machine).

@qwang98
Copy link
Collaborator Author

qwang98 commented Nov 14, 2024

Update: 1.b. doesn't work in #1832 because we can't disable is_zero constraint in rows other than the first and the last. This is because carry column from increment_ptr implicitly returns a constraint, but isn't explicitly returned by the increment_ptr function, and therefore make_conditional won't disable is_zero constraint properly.

Instead of relying on existing constraint API, I implemented the pointer addition logic within the Keccak main machine itself in #2089.

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

No branches or pull requests

1 participant