Interactive Fraud Proofs: Arbitrum’s Secret Sauce

Now that Arbitrum One is open on mainnet, we’re going to put up a bunch of posts on the internals that make Arbitrum go. This post is an excerpt from Inside Arbitrum, our deep-dive description of how Arbitrum works.

Among optimistic rollups, the most important design decision is how to resolve disputes. Suppose Alice claims that the chain will produce a certain result, and Bob disagrees. How will the protocol decide which version to accept?

There are basically two choices: interactive proving, or re-executing transactions. Arbitrum uses interactive proving, which we believe is more efficient and more flexible. Much of the design of Arbitrum follows from this fact.

We have been working on interactive fraud proofs (and Arbitrum) since 2014. The basic mechanism was described in our 2018 academic paper, though we have improved it a great deal since then.

Interactive proving

The idea of interactive proving is that Alice and Bob will engage in a back-and-forth protocol, refereed by an L1 contract, to resolve their dispute with minimal work required from any L1 contract.

Arbitrum’s approach is based on dissection of the dispute. If Alice’s claim covers N steps of execution, she posts two claims of size N/2 which combine to yield her initial N-step claim, then Bob picks one of Alice’s N/2-step claims to challenge. Now the size of the dispute has been cut in half. This process continues, cutting the dispute in half at each stage, until they are disagreeing about a single step of execution. Note that so far the L1 referee hasn’t had to think about execution “on the merits”. It is only once the dispute is narrowed down to a single step that the L1 referee needs to resolve the dispute by looking at what the instruction actually does and whether Alice’s claim about it is correct.

The key principle behind interactive proving is that if Alice and Bob are in a dispute, Alice and Bob should do as much off-chain work as possible needed to resolve their dispute, rather than putting that work onto an L1 contract.

Re-executing transactions

The alternative to interactive proving would be to have a rollup block contain a claimed machine state hash after every individual transaction. Then in case of a dispute, the L1 referee would emulate the execution of an entire transaction, to see whether the outcome matches Alice’s claim.

Why interactive proving is better

We believe strongly that interactive proving is the superior approach, for the following reasons.

More efficient in the optimistic case: Because interactive proving can resolve disputes that are larger than one transaction, it can allow a rollup block to contain only a single claim about the end state of the chain after all of the execution covered by the block. By contrast, reexecution requires posting a state claim for each transaction within the rollup block. With hundred or thousands of transactions per rollup block, this is a substantial difference in L1 footprint — and L1 footprint is the main component of cost.

More efficient in the pessimistic case: In case of a dispute, interactive proving requires the L1 referee contract only to check that Alice and Bob’s actions “have the right shape”, for example, that Alice has divided her N-step claim into two claims half as large. (The referee doesn’t need to evaluate the correctness of Alice’s claims — Bob does that, off-chain.) Only one instruction needs to be reexecuted. By contrast, reexecution requires the L1 referee to emulate the execution of an entire transaction.

Much higher per-tx gas limit: Interactive proving can escape from Ethereum’s tight per-transaction gas limit; a transaction that requries so much gas it couldn’t even fit into an Ethereum block is possible on Arbitrum. The gas limit isn’t infinite, for obvious reasons, but it can be much larger than on Ethereum. As far as Ethereum is concerned, the only downside of a gas-heavy Arbitrum transaction is that it may require an interacrtive fraud proof with slightly more steps (and only if indeed it is fraudulent). By contrast, reexecution must impose a lower gas limit than Ethereum, because it must be possible to emulate execution of the transaction (which is more expensive than executing it directly) within a single Ethereum transaction.

No limit on contract size: Interactive proving does not need to create an Ethereum contract for each L2 contract, so it does not need contracts to fit within Ethereum’s contract size limit. As far as Arbitrum’s dispute contracts are concerned, deploying a contract on L2 is just another bit of computation like any other. By contrast, reexecution approaches must impose a lower contract size limit than Ethereum, because they need to be able to instrument a contract in order to emulate its execution, and the resulting instrumented code must fit into a single Ethereum contract.

More implementation flexibility: Interactive proving allows more flexibility in implementation, for example the ability to add instructions that don’t exist in EVM. All that is necessary is the ability to verify a one-step proof on Ethereum. By contrast, reexecution approaches are tethered to limitations of the EVM.

Interactive proving drives the design of Arbitrum

Much of the design of Arbitrum is driven by the opportunities opened up by interactive proving. If you’re reading about some feature of Arbitrum, and you’re wondering why it exists, two good questions to ask are: “How does this support interactive proving?” and “How does this take advantage of interactive proving?” The answers to most “why questions” about Arbitrum relate to interactive proving.

Want to learn more? Check out Inside Arbitrum.