The statechannels team’s work has contributed to the wider community of “layer 2” solutions, which are all trying to solve the common goal of scaling Ethereum by building on top of it. This post looks at some work we did which relates to optimistic rollups.

Channels and rollups

In order to scale a blockchain application with state channels, developers have to reimplement their application logic using a state channels framework. This can be totally worth the effort, if (for example) very low latency is a requirement. If you want to play trustless decentralized games or make point-of-sale crypto payments, you’re golden. But there is quite a large class of blockchain applications which don’t lend themselves well to reimagining as state channel applications. When the set of application users is dynamic or where interactions can’t easily be broken down into pairwise connections between peers, the advantages of state channels would likely be outweighted be the increase in complexity. Examples include ENS, NFT marketplaces or Uniswap.

The Optimistic rollup is an alternative scaling technique whose development has certainly been influenced by state channel research and is now central to Ethereum’s roadmap.

The central idea of rollups is to only store transactions T and state commitments C(S) to Ethereum itself, and have the full “layer 2 state” S maintained entirely off chain. In validity rollups (sometimes known as zk rollups), transactions are posted to Ethereum along with a concise cryptographic proof that a given state commitment is correct. In the case of optimistic rollups no such proof is given; instead, there is a dispute protocol to enable onlookers to flag up state commitments that appear incorrect. In either caes Ethereum nodes do not usually need to compute any state transitions, which brings great potential for scalability.

One major benefit of modern rollups is that they allow developers to reuse L1 smart contracts with few or zero changes. Users who migrate from Ethereum then get to enjoy lower costs and increased throughput with minimal changes to their trust assumptions.

Taking this broad view of the “layer 2” landscape and the various complementary approaches, our team was excited to see how we could speed up the development of rollups. We were particularly excited about optimistic rollups since Optimism and Arbitrum were gaining significant traction.

We concentrated on the aforementioend dispute resolution mechanism. Often overlooked in the early stages of protocol development, the security of an optimistic rollup protocol stands or falls on the soundness of the mechanism design and implementation. Since state channels have a similar need for robust disputes to be supported, we realized this problem was at least partially in our wheelhouse.

Disputes

A dispute arises when two actors disagree about the correct sequence of state commitments C. Let’s say one actor believes the sequence should be [0,1,2,3,4] (where each number stands for e.g. a 32 byte hash), but another actor believes it to be [0,1,2',3',4']:

It’s a bit like a blockchain fork: in proof-of-work blockchains, disputes are eventually settled by the rule that the chain with the most work wins. In optimistic rollups, it’s the chain which is generated by the transactions T[] stored on Ethereum.

This is an interesting challenge because the most naive approach to settling the dispute (recomputing all of the transitions on chain) is prohibitively expensive, and may be costly as to not “fit” into a single Ethereum block.

Design

We designed a dispute mechanism as an interactive “game.” during which two peers contest the validity sequence of state commitments by first narrowing down to the smallest possible disagreement that they have. In the picture above, they only need to dispute the transition from C=1 to either C=2 or C=2'.

The generality of our approach means the same protocol can be executed:

• First to find a single disputed transaction T in a list of transactions T[] mapping an agreed upon initial state root C[0] to a disputed output state root C[end], and then
• to find a single, disputed offchain-virtual-machine state transition implied by the disputed transaction. We haven’t explained here exactly how these intra-transaction states come about — but that isn’t actually important to understand our contribution. Suffice to say that a transaction T is itself composed of individual instructions which progress the state of a virtual machine (such as the Ethereum Virtual Machine) through dozens or hundreds of intermediate states between any given input C[i] and C[j].

With this single, indivisible transition in hand, it is simple to validate or invalidate it through a module we might call the SingleStepVerifier. We weren’t so interested in implementing that part of the story, and nor did we want to tie our implementation to any particular SingleStepVerifier. So instead we left it as an external depenency / interface and concentrated solely on reaching that single step as efficiently as possible.

The main mechanism by which the protocol achieves efficiency is through the well-known tehcnique of “bisection”. The protocol participants progressively halve the list of transitions which they are disputing, so that they can narrow down to a single transition in logarithmic time. Advanced users of the git version control tool may have experience of using git bisect to quickly find a code change which introduced a bug. Ever heard the claim that blockchains are just like git? Well, it’s the same magic here, although we prefer the term “dissection” since we aren’t opinionated about whether we split into halves, thirds or some other fraction. Bisection is also a a part of Arbitrum’s dispute logic.

Many more details are in the design document.

Implementation

Back in 2021, we came up with a detailed design for a dispute game, as well as prototype implementations in Solidity and Typescript. Please check out the code or reach out to our team if you’re interested to learn more!

You can read more about the latest developments in dispute games from OP labs here.

Written by Mike Kerzhner and George Knee with input from Alex Gap.