Improve recursion speed when the Keccak tables are empty

[sai-deng]

No description provided.

[Nashtare]

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]

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]

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]

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]

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]

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

[sai-deng]

PR from Plonky2 side:
0xPolygonZero/plonky2#1626

[sai-deng]

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]

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) / MemAfter on top of the Keccak tables.