search

0xPolygonZero / zk_evm

Apache License 2.0
80 stars 36 forks source link

Improve recursion speed when the Keccak tables are empty #620

Open sai-deng opened 2 weeks ago

Nashtare commented 2 weeks ago

Is it what I was telling you during our sync? (With preprocessed LDEs / MT commitments)

Because if so this can be applied to most tables, not just Keccak (with some distinction as some tables have non-zero range check related columns)

sai-deng commented 2 weeks ago

I am just trying to modify the current recursion circuits (mostly on the root circuit). I am not sure how to get it working with preprocessed LDEs/MT commitments. Isn’t it used to commit to fixed tables instead of empty ones?

Nashtare commented 2 weeks ago

Hmm could you describe the ticket in more details then? As recursive chains cannot be proven without knowledge of all STARK proofs (to have the CAPs to seed the challenger), I'm not really sure I see how you'd improve the root specific part. Or is it in the context of STARK batching?

sai-deng commented 2 weeks ago

The simplest method in my mind is to have two types of root proofs: one with Keccak tables and one without. Both of them would be considered valid in the next recursion circuit.

Nashtare commented 2 weeks ago

Ah ok, what we had discussed of fully removing it. In that case this pruned root circuit can also remove KeccakSponge (unless you had assumed it already when writing the ticket)

I'm just curious on the impact of the segment aggregation layer, as it may grow fairly large as we now would be supporting conditionally 1 more underlying circuit

Nashtare commented 2 weeks ago

Actually the concern of circuit size would be alleviated with #621 so I don't think this is an actual problem

sai-deng commented 1 week ago

PR from Plonky2 side: https://github.com/0xPolygonZero/plonky2/pull/1626

sai-deng commented 1 week ago

Creating two root circuits turned out to be more complicated than I initially thought, due to the complexity of the system's recursion pipeline. As a result, I’ve decided to try a different approach: using a single root circuit, but within it, conditionally verifying the (shrunk) Keccak recursion proofs.

In the meantime, I will submit some refactoring PRs extracted from my current implementations.

Nashtare commented 12 hours ago

Looking at the minimal tables (i.e. only init section for continuations), we have:

TraceCheckpoint { arithmetic_len: 21, byte_packing_len: 0, cpu_len: 128, keccak_len: 0,
keccak_sponge_len: 0, logic_len: 0, memory_len: 66484 }, mem_before_len: 66040, mem_after_len: 66067

which means we can also conditionally disable BytePackingStark / Logic (/ Poseidon for cdk-erigon), on top of the Keccak tables.