Batch Proof witnesses works over range

[eyusufatik]

Witness is a widely used term through out our repository. For this part of the documentation we’ll define

Witness: Hints for batch proof circuit for state data.

We have two witnesses in the batch proof circuit.

State witness: Vector of (value, JMT proof) pairs.

JMT proof: Jellyfish-Merkle Tree proof with respect to the root.

Offchain witness: Vector of values. This is introduced in the Kumquat fork. The verification of the data provided by the offchain witness is left for sov-modules. This is only used for EVM smart contracts right now. The hash of the code of smart contracts in EVM is already committed to the state. So instead of putting the smart contract code into the state tree (JMT), thus the code ends up in DA through our state diffs, we commit the hash to the state, and check if the provided code by the offchain witness has the hash in the state.

The witness generation is done by the prover. When the prover runs an L2 block, it keeps track of state reads (and writes) through the WorkingSet passed to the STF. At the end of the run of the L2 block, the prover saves the witnesses generated to LedgerDB. When the prover creates input for the batch proof, these witnesses are passed to the circuit as input. The working set is also used in the circuit side, and the circuit storage implementation ZkStorage pops witness elements from the witnesses given as input.

The WorkingSet also acts as a cache on top of the storage, so once a value is read from the storage, it is then served from the WorkingSet.

The ProverStorage-Witness-ZkStorage relationship is only implemented per L2 block. However, we run multiple L2 blocks in a single run of the batch proof circuit. With the current implementation, we reset the working set after every L2 block, meaning that keys read from the state or the offchain witness are re-read (and re-verified) if they are used again in another L2 block in the same run of the circuit.

If we could generate the witnesses for a range of L2 blocks, we would do way less witness verifications resulting in dramatic decrease in cycle counts.

Needed changes:

1. On the circuit side, WorkingSet ‘s are not resetted after a run of the L2 block so that we can keep using it as a cache over multiple L2 blocks. There is some problems regarding state root calculation and JMT update proofs that we'll need to figure out here.
2. The batch prover can create witnesses over an L2 block range.
3. The batch prover is aware of the memory limitations of the circuit, so it make sure for a given range of L2 blocks, the size of the cache (WorkingSet) will not go over 20 MBs. Meaning that for a range found in sequencer commitments, the batch prover prepares it Vec<(Witness, OffchainWitness)> for subranges that won’t cause the circuit to go over its memory limits.