Relax restriction to a single looked table for CTL

[matthiasgoergens]

EDIT: it's perhaps better to get https://github.com/0xPolygonZero/plonky2/pull/1577 in first, and then I rebase this PR.

In our use of plonky2, we have a few instances where we need both several looked and several looking tables. Think of these lookups as many-to-many multiplexers, or a kind of bus. Looking tables can be thought of as pushing values with an obligation to process them onto the bus, looked tables can be seen as pulling values to discharge that obligation.

My first attempt changed from looked_table to looked_tables, but then I noticed that thanks to logup, we don't need this complication: looked_tables are just looking_tables with negative multiplicities.

Thus we can get a simpler system by just removing looked_table completely, and giving people tools to negate the multiplicities of their lookup tables.

We also preserve the old CrossTableLookup::new, which applies the negation to the passed looked_table automatically to keep the API as compatible as possible.

This PR only touches cross table lookups. We could do the same for the intra-table lookups in starky/src/lookup.rs. But that's for a separate PR.

[Nashtare]

Thank you @matthiasgoergens , it's a good idea! But I tried running this PR against the integration tests in zk_evm (for example add11_yml), and CTLs and Lookups failed. So I was wondering whether this was also the case for you or if maybe I had messed something up when testing?

This branch is based on an older version of #1577 which was broken (and that @matthiasgoergens now fixed). After rebasing this should go away I believe.

[LindaGuiga]

Thank you @matthiasgoergens , it's a good idea! But I tried running this PR against the integration tests in zk_evm (for example add11_yml), and CTLs and Lookups failed. So I was wondering whether this was also the case for you or if maybe I had messed something up when testing?

This branch is based on an older version of #1577 which was broken (and that @matthiasgoergens now fixed). After rebasing this should go away I believe.

Indeed, it works with those changes, thanks!

[matthiasgoergens]

Could you please tell me how to run the zk_evm tests? Is it just 'cargo test' in there (after fixing the dependencies to point at my plonky2 branch)? Or something more involved? Thanks!

Btw, do you have a way to run some benchmarks for zk_evm? I mean, I found some micro-benchmarks in the repo, but I'm looking for something more substantial that covers more of the system (but hopefully doesn't run for longer than a minute or perhaps five at most for one iteration).

That's because I have some ideas for speeding up plonky2 that work for our system, but I want to make sure they don't make life worse for you.

(And chances are, if it helps two unrelated system, it's probably a good idea in general.)

[Nashtare]

@matthiasgoergens For testing, yes you can just run cargo --release --test --package evm_arithmetization within zk_evm repo: https://github.com/0xpolygonzero/zk_evm/.

For benchmarking purposes, we usually would do it against real-life examples, with zero-bin: https://github.com/0xpolygonzero/zero-bin/. There you can use the stdio mode to pass a block trace as input, and generate an entire proof for the block. If you need an access endpoint / block traces to play with, feel free to reach me in DM.

[Nashtare]

@matthiasgoergens Could you address the few comments / rebase with latest main so we can get this into the next release?

[matthiasgoergens]

@matthiasgoergens Could you address the few comments / rebase with latest main so we can get this into the next release?

Please see the new version.

[gio256]

@matthiasgoergens thanks for this PR.

Can I be of any help getting this across the line? Happy to take it from here or just get it caught up to main.