yes, another trilemma
Thanks to Gabriel Coutinho de Paula (Cartesi), Ed Felten (Arbitrum), and Kelvin Fichter (Optimism) for reviewing the article.
When thinking about optimistic rollups, we originally envisioned systems with fixed challenge periods that any single honest challenger could secure. Because we took these properties for granted, we started focusing on other issues like the Verifiers’ Dilemma: if a fraud proof system works, no one will ever submit invalid roots, so no one is incentivized to check the chain, creating in return an incentive to submit invalid roots. The issue can be solved either by elaborated techniques, or by simply dismissing the problem: explorers, RPC providers, bridges, and other infra providers will have to run full nodes, and since any of them can be the single honest challenger, in practice the chain will always be secure.
We went even further, claiming that economic incentives are not even really necessary to protect the chain: anyone can be the challenger, and assuming they can bear the gas cost of performing the challenges, everything is fine. As it turns out, this statement greatly underestimates the resource requirements that defenders need. In April 2024, an ethresearch forum post titled “Fraud proofs are broken” by Gabriel (from Cartesi) tried to argue that the vision of having fixed delay proof systems with a 1 out of N assumption seems fundamentally impossible. The reason behind this claim is found in resource exhaustion attacks: an attacker can try to make the protocol confirm an invalid state root by economically outlasting honest defenders, who would then have no more funds to protect the system. If defenders need a lot of funds, the N in “1 out of N” might become dangerously small. Techniques aimed at solving this type of attack seem to greatly affect other desirable properties of the system, like fixed challenge periods. This trade-off space will be presented as the fraud proof trilemma, and, as we will see, each project has taken a different approach with its own distinct balance. The goal of the blogpost is to allow users, developers, and protocol designers to better understand these systems and spark a conversation around optimistic rollup security and their incentives.
_(1).png)
In this article, we will generally introduce fraud proof systems and their variants, namely single vs multi-round and onchain vs offchain protocols. Then, we’ll present a basic example of a resource exhaustion attack, and how different concurrency approaches can address the issue, but also affect settlement delays. The trilemma will be then defined, highlighting the trade-off between safety, promptness, and decentralization. The 4 major multi-round fraud proof systems will be described and compared in detail, namely the (old) Arbitrum Classic protocol, the (new) Arbitrum’s BoLD protocol, Optimism’s fault proofs (OPFP), and the Cartesi protocol. The challenge period length will be discussed, as well as a possible attack that takes advantage of imperfect information. Finally, we will discuss whether fraud proofs make sense at all if we have ZK.
A blockchain state is computed by applying its state transition function (STF) on an ordering of its transactions. Given that full nodes should converge on the same view of the network, such STF must be deterministic. Rollups, instead of gossiping blocks filled with transactions on their own p2p network and having their own consensus to define the ordering, delegate these tasks to a separate network called the base layer, or L1. While a rollup can also share blocks over p2p and have a separate consensus for sequencing, the final source of truth is always L1 as L2 can equivocate (i.e. post different data or with a different ordering on L1). Once L1 collects the transaction batches and finalizes an ordering, the rollup full nodes are able to compute the final state that results from them. If users want to bridge assets between the two networks, they need a way to tell the rollup that some tokens are locked on L1 and to mint them on L2, and to withdraw they need to tell L1 that tokens have been burned on L2 and to release them. To do this, both systems need to know about each other state. L2 full nodes have to fetch the data and their ordering from L1, implying that they need to run L1 full nodes themselves and can already read its state trustlessly. Since L1 nodes do not run L2 nodes, we need to convince them about the L2 state by other means. Moreover, since the full L2 state cannot be entirely published on L1, a cryptographic commitment of it is published in the form of state roots. Computing such commitments by executing all L2 transactions on L1 is mostly infeasible, so we must use sublinear strategies such as ZK proofs or fraud proofs that allow the bridge to only accept correct state roots. The former succinctly proves that all state roots are correct, while the latter just proves incorrect state roots wrong, accepting the others “optimistically”. Since accepting an invalid state root can allow an attacker to steal all funds in the bridge, we must design these protocols very carefully. In this article, we’ll focus on optimistic rollups.
Transitions of 1024 steps from the initial state (S_0) to the next state (S_1024). The S_0 state is already mutually accepted, like the STF used.
How to prove that an incorrect state transition is wrong? The trivial solution is to execute all the L2 transactions past the previous confirmed state on L1, either to entirely calculate the next correct state root or to prove specific faults. This is the approach that was taken by Fuel v1, the first optimistic rollup to be live on mainnet, only supporting simple payments. While this might work for simple app-specific rollups, re-executing an entire general purpose VM execution inside another VM is far more challenging. The initial version of Optimism, called OVMv1, tried implementing single-round fraud proofs for the EVM, but the complexities of purely simulating the EVM inside itself, (e.g. see the optimistic time-travel attack) made them abandon this approach. Celestia implements two types of single-round fraud proofs, one to prove incorrectly generated extended data, which has to do with the Reed-Solomon erasure coding of the data, and the other one for state transitions. The latter is not live yet on mainnet, and, given its minimal VM, Celestia is thinking about moving directly to ZK. Another single-round approach is the one planned by Taiko: nodes can propose state roots of blocks using SGX proofs, which can be later challenged and proved wrong by a single ZK proof.
While ZK can enable single-round proofs for computations that cannot be simply re-executed on the base layer, very long computations and very high throughput chains can be challenging to be proven even with ZK. In such systems, the asserter and the challenger, which agree on an initial state and disagree on the final, work together to restrict the space of disagreement and reduce what is needed to be re-executed on L1, possibly to one single simple instruction, or something that is feasible to be proven with ZK. At the time of writing, the only project using multi-round fraud proofs with final step executed with ZK is Kroma. As their fraud proof system is still a work in progress, it will not be described in this article.
The trivial technique to find the single instruction of disagreement consists in repeatedly publishing onchain the state root produced after executing one transaction at a time from the previously agreed one, or in other words a linear search. For the nerds, a linear search takes $O(n)$ time where $n$ is the number of steps in the trace. Since in the worst case the protocol needs one interaction for each step, the onchain cost will result similarly to executing all the steps, making it impractical.
An example of interactive fraud proof with linear search.
A faster search ($O(\log n)$) consists in performing a bisection over the execution trace, where the asserter asks the challenger whether they agree on the state after executing half of the steps: if they agree on the midpoint, it means they surely disagree on the second half. Otherwise, it means they surely disagree on the first half. The protocol continues recursively by providing the midpoint of either the first half or the second half of the remaining execution trace until a single instruction is found, where both parties agree on a state and disagree right after executing one step. This process also takes the name of bisection game. Finally, given the data provided as DA, the single instruction is executed on L1.