Qi Zhou @ EthStorage
An optimistic rollup periodically submits L2 transactions in batches to L1 with each batch being
$(T_n, h(S_n))$
where $n$ is the batch index, $T_n$ is the list of L2 transactions, $S_n$ is the post-state in a set of KV pairs evaluated by the rollup proposer, and $h()$ is a hash function of the state, e.g., returning the root hash of a Merkle Patrica Tree (MPT) representing the state implemented by EVM.
If the proposer submits an incorrect off-chain execution result of batch $n$, i.e., $h(f(S_{n-1}, T_n)) \neq h(S_n)$ where $f()$ is the state transition function, a challenger can challenge the result on-chain via an post-state fraud proof. To determine the proposer or the challenger is faulty, the fraud proof will run an interactive on-chain dispute game with inputs $h(S_{n-1})$ and $T_n$.
This optimistic rollup approach requires each batch to contain the post-state hash. However, one performance bottleneck of L2 execution is to compute the post-state hash in MPT $h(S_n)$ by the L2 proposer for each batch (e.g., by the sequencer), which results in a large number of IOs for reading/writing the MPT.
An approach to accelerate the execution is to replace the MPT with flat KV, adopted by Erigon / Reth stage sync and fast EVM execution idea here. In our internal benchmark with Ethereum mainnet data, the performance gain of flat KV can be 2x or more. Furthermore, the gain increases as the state size increases. However, how to apply flat KV in L2 execution while enabling fraud proof is an open question.
The proposed idea will submit an L2 batch as
$(T_n, h(\Delta_n))$ where $\Delta_n = S_n - S_{n-1}$ is the set of the states (KV pairs) in difference. Since we do not need to post $h(S_n)$ for every batch, the L2 transactions can be executed on a state implemented by a flat KV storage. Further, since $|\Delta_n| << |S_n|$, the hash of the state diff can be computed very efficiently.
The L1 rollup contract also maintains the most-recent finalized state hash as $h(S_r)$ where $r$ is the batch index of the most-recent finalized state hash. Note that $h(S_r)$ can be also updated by a sequencer, however, it does not have to be updated as frequently as the batches. This means that it is possible that $n >> r$.
When a challenger finds $h(f(S_{n-1}, T_n) - S_{n-1}) \neq h(\Delta_n)$, it could initiate a two-stage fraud proof and verify the claim as follows.
To initiate a challenge, the challenger will prove the claim $h(f(S_{n-1}, T_n) - S_{n-1}) \neq h(\Delta_n)$ with additional claim of the post state hash $h(S'_{n-1})$ of batch $n-1$.
Depending on the response of the sequencer, we have two cases