search

powdr-labs / powdr

A modular stack for zkVMs, with a focus on productivity, security and performance.
Apache License 2.0
412 stars 81 forks source link

Optimizations for Keccak memory machine and adjacent sub machines #2022

Open qwang98 opened 2 weeks ago

qwang98 commented 2 weeks ago

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 commented 2 weeks ago

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 commented 4 days ago

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.