The “Why”s of Optimistic Rollup
Why does optimistic rollup have the properties it has, why is it secure and decentralized, and why is it the most promising avenue for scaling Ethereum today?
If you’re reading this post, you’ve surely heard of optimistic rollup, a promising new-ish scaling technique that was all of the buzz of this year’s DevCon. There have been several explainers published of how this technique works, but none of why it works. This has led to many teams now trying to implement optimistic rollup with their own spin, often to the detriment of the cryptoeconomic security of the whole system.
This post aims to focus on the latter topic for the first time: explaining why optimistic rollup scales sustainably and securely while remaining decentralized.
What Is Optimistic Rollup?
I wrote the first minimal viable spec for what is now known as optimistic rollup back in June. This spec provided a concrete parametrized high-level spec to the more general ideas introduced in my earlier paper, Building Scalable Decentralized Payment Systems (co-authored with Mikerah). The goal was to enable for the first time in blockchain history a permissionless, trust-minimized, scalable side chain.
Optimistic rollup works as follows: Anyone may commit to a side chain block permissionlessly, posting the entire block on-chain as calldata to be authenticated (i.e., Merkleized) and a bond. A new side chain block can only extend the tip of the side chain, which the on-chain contract keeps track of (in simplest terms, the contract runs a light client of the side chain, keeping side chain block header hashes in storage). Side chain blocks are finalized after a long delay (a system parameter, but should be quite long e.g., a week or two), which returns the bond. Withdrawals are initiated on the side chain, and can be completed through a non-interactive inclusion proof against a finalized side chain block. If a side chain block is invalid and not finalized, it, and all subsequent blocks, can be orphaned by submitting a non-interactive fraud proof, rolling back the tip of the chain and burning half the bonds and rewarding the other half to the fraud prover. All together, this allows a trust-minimized two-way bridge of funds.
Yep, it’s that simple. So why hasn’t this been implemented before?
I’ll Do You One Better: Why Is Optimistic Rollup?
As it turns out, there are a number of subtle differences between optimistic rollup and previous scaling proposals, making the former the most promising short- to medium-term scaling solution, and the latter mostly relegated to the history books. This section covers the intuitions behind these critical differences.
One of the key distinguishing features of optimistic rollup is merged consensus, a consensus protocol that is verifiable on-chain (save for actual block validation, which is done implicitly through fraud proofs). But what is a decentralized consensus protocol?
Decentralized consensus protocols consist of a few distinct features:
- A fork choice rule (how to choose between two otherwise valid chains)
- A block validity function (state transition function)
- A leader selection algorithm (who is permitted to attempt to progress the chain by extending its tip with a new block)
- A Sybil resistance mechanism (Proof-of-Work, Proof-of-Stake, etc.)
Together, they give a blockchain economic security: the cost of manipulating history. (Note that I’m ignoring some things here for the sake of brevity e.g., some decentralized consensus protocols are leaderless).
With optimistic rollup, the side chain is fork-free by construction, so a non-trivial fork choice rule is not needed. Block validity is executed off-chain, and can be proven incorrect on-chain through a fraud proof. This leaves us with leader selection and Sybil resistance.
The spec proposed a “first come, first serve” scheme, with the first transaction that extends the side chain simply being accepted. Leader selection is implicit and post-facto, while Sybil resistance is provided by the main chain itself (i.e., transaction fees and blocksize/gas limits). Why does this simple choice of leader selection work? Because the Ethereum chain already provides security. The only way for a side chain block to be orphaned is if it’s invalid or builds upon an invalid block, or if the Ethereum chain is re-orged. Valid blocks therefore have the same finality and security guarantees as Ethereum itself! As such, we don’t need a complex leader selection algorithm or an expensive Sybil resistance mechanism to provide security; security is provided for free so we can parametrize the system as simply as possible.
Okay, but what if we want to know the leader beforehand? One suggestion is you can just run PoS + RANDAO on-chain to do leader selection. A separate token is not needed, and is in fact detrimental to this process. From the Bitcoin design paper:
If a greedy attacker is able to assemble more CPU power than all the honest nodes, he would have to choose between using it to defraud people by stealing back his payments, or using it to generate new coins. He ought to find it more profitable to play by the rules, such rules that favour him with more new coins than everyone else combined, than to undermine the system and the validity of his own wealth.
The whole point of a native coin/token, as described by Nakamoto, is to incentivize an honest majority to secure the system. There is no “honest majority” in optimistic rollup, nor is there a separate notion of security, so a native token is completely unnecessary and would add nothing but friction over just using ETH.
Note that literally any leader selection scheme that runs entire on-chain can be used, not just the ones I’ve suggested here. A Proof-of-Burn auction can be used, for example.
This idea of merged consensus is a key distinguisher between optimistic rollup and proposals with lots of similarities, such as delayed state execution or shadow chains. The consensus protocol for optimistic rollup runs entirely on-chain in a smart contract; hence, it does not affect or require support from the main chain’s consensus rules. In contrast, delayed state execution and shadow chains apply state transitions automatically on-chain, which requires explicit support from the main chain’s consensus rules along with in-protocol incentives and penalties.
Now that we know how and why optimistic rollup is permissionless through merged consensus, why is it sustainably scalable?
The uncompressed Ethereum state (user balances and contract storage) size is ~45GB at the time of writing. Unlike history (transactions and blocks), state cannot be pruned by full nodes — it must be kept in its entirety in order to validate (i.e., execute) new transactions in new blocks. Even worse, many random accesses into the state must be performed in order to validate transactions, which requires that it be kept either in RAM — an impossibility for most consumer hardware — or on a fast NVMe SSD. State growth is the single biggest scaling bottleneck for Ethereum.
While it would certainly be possible to set a hard limit on the state size and not have to worry about state growth that way, the true solution to this problem is a form of state rent, charging ongoing costs for making use of state. However, deploying such a change to Ethereum is complex beyond imagination, and has been postponed indefinitely.
A practical solution that mitigates state growth to the point that it’s simply not an issue anymore is using blockchains as a data availability layer. First popularized by zk rollup, these schemes post side chain transaction data as calldata on the main chain, then use either validity proofs or fraud proofs to ensure correctness. It turns out that history is much, much cheaper than state (as in, orders of magnitude cheaper). The main chain can then be responsible for ensuring data availability, keeping track of rollup chain block headers, processing deposits and withdrawals, and checking validity/fraud proofs, none of which make particularly heavy use of state. By avoiding state, scaling in this way is sustainable long-term. Buterin provides an excellent summary of leveraging on-chain data availability for zk rollup and optimistic rollup here.
Note that while there have been suggestions that shadow chains are completely identical to optimistic rollup, that is patently untrue.
Now, the idea is to create an entire “shadow chain”, with computations happening off-chain but state transitions being committed back to the main chain after 100 blocks. Oracles can add new blocks to the “tail” of the chain, where a block consists of a list of transactions and a
[[k1, v1], [k2, v2] ... ]list of state transitions caused by those transactions. If a block is unchallenged for 100 blocks, the state transitions are applied automatically to the main chain.
In addition to being underspecified, the idea of shadow chains is to automatically apply state transitions on-chain, which does not help with state growth at all. Optimistic rollup does not apply any state transitions unless they are explicitly paid for by a user (i.e., a withdrawal).
Optimistic rollup places a huge emphasis on non-interactive fraud proofs. Why?
This obsession actually derives from wanting to avoid one of the shortcomings of Plasma Cash, namely the interactive exit challenge for invalid history. This interactive, multi-step challenge makes Plasma Cash particularly vulnerable to chain congestion attacks, in which an attacker floods the main chain with exits in an attempt to steal all funds from the Plasma contract (though, it is more resistant to these attacks than the dead end that is Plasma MVP). Only a single non-interactive fraud proof is needed to orphan any number of invalid optimistic rollup blocks (per side chain), making the system resilient to chain congestion. Caveat: as optimistic rollup uses fraud proofs, funds can still be stolen if the main chain is not censorship-resistant.
Withdrawals are also handled in a non-interactive manner in optimistic rollup, being initiated on the side chain and completed through a non-interactive inclusion proof against a finalized block on the main chain. This however necessitates that the side chain be permissionless, hence the need for merged consensus rather than a single Plasma-like operator.
The use of a non-interactive fraud proof also has benefits over an interactive verification game. Interactive verification games need to be played out over a long period of time. Given that optimistic rollup is fork free, an attacker can DoS the system by producing an invalid block and halting the side chain for the duration of the verification game. With non-interactive fraud proofs, fraud can be proven immediately (though with the caveat that what can be proven with fraud proofs is potentially more limited than with an interactive verification game — whether this limitation is actually meaningful for blockchain applications is up for debate).
Demystifying Transaction Latency Claims
Optimistic rollup does not reduce transaction latency. Every side chain block needs to be committed to the main chain, so you don’t get blocktimes lower than the main chain. Barring the use of fully-collateralized channels, there is no known secure and trustless way of reducing this latency.
You don’t have to wait until a side chain block is finalized to accept its transactions, however. Since optimistic rollup is fork-free, valid blocks that are accepted on-chain are guaranteed to eventually finalize, and all data is available (as all valid blocks are posted on-chain), users can perform client-side validation to immediately accept transactions.
Withdrawal latency seems like another issue at first glance, but is in fact not. In the usual case, users won’t have to wait until their withdrawals are finalized. In fact, that feature mostly exists for cryptoeconomic security, it should never be used under normal circumstances. The easy way to instantly withdraw funds it to atomic swap with a liquidity provider (or other user wanting to deposit into the rollup chain) on the main chain or another chain [see section Fast Withdrawals: Liquidity Providers].
On Data Availability Challenges
The original paper suggested (implicitly and explicitly) three ways of solving the data availability problem:
- Post all data on-chain all the time
- Use data availability challenges to only post the data when needed
- Use data availability proofs
The second case, data availability challenges, seems like a good simple solution. Unfortunately, if the defender pays for the challenge they can be griefed, and if the attacker pays for the challenge the system degenerates to simply posting all data on-chain all the time. Hence, when designing the spec the choice was made to go with posting all data all the time, and instead focus on making this cheaper and more efficient. Later on, using data availability proofs for optimistic rollup became feasible.
I’ve written a number of performance improvements that build upon the original minimal spec, summarized here. Note that the focus is mostly on UTXO-based payments and predicates rather than general smart contract execution.
Multi-Threaded Data Availability On Eth 1 —Authenticating (i.e., Merkleizing) data and other pre-processing steps are pure functions, in that they don’t touch any state at all. Therefore they can be parallelized. Using Ethereum in this manner will greatly reduce state usage and growth and, if 4-core computers are targeted, increase data availability throughput 4-fold. The first of what is planned to be several EIPs to implement this is EIP-2242: Transaction Postdata.
Compact Fraud Proofs for UTXO Chains Without Intermediate State Serialization —General-purpose fraud proofs for Ethereum-style smart contracts are expensive. In the UTXO data model, UTXOs are created at most once and consumed at most once, and each transaction totally describes its state transition. Block producers can append metadata to each input, claiming a particular specific output that generated it. If the claim is false, it can be proven non-interactively. An independent re-discovery of the fraud proof scheme described in BIP-141.
Practical parallel transaction validation without state lookups using Merkle accumulators (state lookup-less clients) — State lookups are expensive. Stateless clients remove this cost by eliminating state. Simpler: just eliminate state lookups. Witnesses are not outdated immediately, but can instead be valid for a few blocks. They must be compared against the state transitions of recent blocks, which can be computed statelessly in the UTXO data model.
On-Chain Non-Interactive Data Availability Proofs — Posting all data on-chain all the time is expensive and limits optimistic rollup to linear scalability (not an asymptotic problem compared to completely off-chain techniques such as Plasma, as Plasma Cash checkpointing is also linear). We can instead expose the ability of a consensus node to do data availability checks as an FFI function (e.g., through a precompile), which gives us quadratic scalability without sharding. This is the core idea of systems like Celestia, which promise significantly increased data availability throughput at low cost. Unlike Celestia however, implementing this on Ethereum would not provide the former’s scale-out property.
Trustless Two-Way Bridges With Side Chains By Halting — The forever-online requirements of side chains with a two-way bridge that uses fraud proofs could potentially be cumbersome for users. Unlike Plasma Cash, which is not amenable to watchtowers, watchtowers can be used for optimistic rollup. However, we can do even better: by completely and permanently halting the side chain after a predetermined amount of time, then providing a huge window (months) for users to submit fraud proofs to determine the valid head, the window in which users must be online is 1) known and 2) finite. Withdrawals are only allowed after this period has expired; users that want to withdraw their funds early can do so via atomic swaps with liquidity providers.
Teams Building Optimistic Rollup
Since the writing of the first optimistic rollup minimal spec months ago, I was excited to discover that many developer teams have started building out implementations of optimistic rollup, with various twists and modifications. Here’s a non-exhaustive list (order, inclusion, or exclusion should not be taken as endorsement or critique) of what we’ve seen publicly so far:
Fuel — UTXO data model focused on stablecoin payments. Can do arbitrary ERC-20 token and ether transfers and atomic exchanges, in the future will do predicate scripting. Close to long-lived public testnet release.
Arbitrum — Interactive verification game rather than non-interactive fraud proofs, general-purpose smart contracts. Other than that, the new Arbitrum rollup design is largely identical to optimistic rollup.
Interstate Network — General-purpose EVM-like smart contracts with fraud proofs.
NutBerry — Interactive verification game rather than non-interactive fraud proofs, general-purpose EVM-like smart contracts.
IDEX — “Optimized Optimistic Rollup” for their exchange.
The coming year will be a game-changer for Ethereum, as projects implementing optimistic rollup go live, massively increasing the throughput of Ethereum and driving further innovation on the scalable, sustainable data availability front.
If you were curious about comparisons to zk rollup (an idea originally developed by Barry Whitehat as roll_up, and later improved by Buterin as zk rollup), which I didn’t cover here, check out this excellent post by Alex Gluchowski.