The game’s afoot: designing modular dispute games for the OP Stack’s Fault Proof System

It’s not a coincidence that one of the most fun components in the OP Stack’s Fault Proof System (FPS) are its dispute games. Previous posts about the FPS have outlined how the OP Stack’s modularity made it possible to decouple the Fault Proof Program (FPP) from the Fault Proof Virtual Machine (FPVM) to enable next-level composability and efficient parallelized upgrades to both components. The same is true, to an almost exponential degree, for dispute games.

This post explores the role dispute games will play in decentralized fault detection within the Superchain ecosystem, how the fault proof dispute game was built on top of the dispute protocol, and the possibilities that emerge thanks to the extensibility of the dispute protocol.

If you’re looking to nerd out on more granular details about dispute games, I shared a much longer version of this post on my personal blog a few weeks ago.

What is a dispute game?

A dispute game is a core primitive to the dispute protocol. It models a simple state machine, and it is initialized with a 32 byte commitment to any piece of information of which the validity can be disputed. They contain a function to resolve this commitment to be true or false, which is left for the implementor of the primitive to define. The OP Stack’s first implementation of the dispute game, the FaultDisputeGame, is permissionless due to its resolution function being determined by the outcome of a fault proof program’s execution on top of an emulated VM.

Dispute games themselves rely on two fundamental properties:

1. Incentive Compatibility: The system penalizes false claims and rewards truthful ones to ensure fair participation.
2. Resolution: Each game has a mechanism to definitively validate or invalidate the root claim.

In the Dispute protocol, different types of dispute games can be created, managed, and upgraded through the DisputeGameFactory. This opens the door to innovative features, like aggregate proof systems and the ability to expand the protocol to allow for disputing things apart from the state of L2, such as a FaultDisputeGame geared towards on-chain binary verification.

Bisection Game

This is a specific type of dispute game, and the first game built in the OP Stack’s dispute protocol. In this game, players go back and forth, dividing an execution trace until reaching individual steps. After bisection has reached commitments to the state at individual trace instructions, the FaultDisputeGame executes a single instruction step on chain using a generic VM. The VM’s state transition function, which we’ll call T, can be anything, so long as it adheres to the form T(s, i) -> s', where s = the agreed upon prestate, i = the state transition inputs, and s' = the post state.

For our first full implementation of the VM generic in the bisection game, we’ve implemented a single MIPS thread context on top of the EVM to execute single instructions within an execution trace generated by Cannon and the op-program.

Claims

Claims represent a commitment to the state of the backend VM at a given instruction. These can be true or false, with truthfulness determined after the resolution phase. If not countered, claims are assumed true.

Positions

Claims exist at positions in a binary tree. The position represents which instruction the claim is related to. Positions are generalized indices, which can be defined as 2^{depth} + index_at_depth.

Chess Clocks

Players have a time limit to make moves. The game is permissionless, allowing anyone to join. Each side starts with 3.5 days on their clock, totalling a 7-day game time. In the case that a new path is made or a claim is made at a position that has already received a claim, the grandparent’s clock is inherited.

Moves

Players bisect until claims commit to the state of just one VM instruction. Then they execute that instruction on-chain to verify or falsify claims. Moves can either be attacks (which challenge a parent claim) or defenses (agreements with a parent claim). A defense is made whenever a player agrees with the claim hash they’re observing (meaning the two parties’ state is the same at the given instruction), but disagrees with the final outcome they’re trying to push based on the observed claim’s relative agreement with the root claim.

Instruction Step

At the leaf nodes of the position tree, each claim commits to the state at just one VM instruction. The only move left is to execute that VM instruction to prove or disprove parent claims.

If the instruction step confirms the expected post state, the claim stands uncountered. If there is an unexpected post state or exit code, the parent claim is countered.

Resolution

The game may be resolved after chess clocks for all claims have run out, with a low-end of 3.5 days. Each claim within the game is the root of it’s own Sub Game. Sub games are DAGs with a depth of 1. All children (which are sub-game roots themselves) pointing to the root are counters to it, and the subgame may only be resolved if all of its child-subgames have been resolved as well. A subgame root can only be considered countered if one or more of its children are resolved and uncountered, and this property percolates upwards all the way to the root claim of the game.

An honest player’s presence, assuming all of its moves have been exhausted, will always result in the game resolving favorably for its view of the trace, whether the root claim is honest or dishonest. Dishonest claims can always be countered by any party, though there is always only one correct claim to be made as duplicates claim hashes at the same position in the same subgame are not allowed.

Play the Alphabet Bisection Game

For anyone who is curious, there is also a visualization tool for a FaultDisputeGame over a mock execution trace that is only 16 instructions long. This simulation uses a separate VM than the MIPS thread context, the AlphabetVM, which simply returns the next letter of the alphabet when given a letter as input.

If you’re interested in exploring the rules of the game with a lighter backend, here’s how to play:

Clone the Optimism monorepo, install dependencies, and make the devnet allocations / cannon / op-program binaries.

Required Dependencies:

1. foundry
2. Golang toolchain
3. Docker

git clone [email protected]:ethereum-optimism/optimism.git && \\
	cd optimism && \\
  pnpm i && \\
  (cd packages/contracts-bedrock && forge install) && \\
  make cannon-prestate && \\
  make devnet-allocs

Run the alphabet game:

cd op-challenger && make alphabet

1. Navigate to https://disputify.optimism.io/ or run the visualization front-end locally by cloning https://github.com/clabby/dispute-viz and input the address of the FaultDisputeGame proxy deployed to your local devnet above.

Help secure the OP Stack’s dispute protocol

In a bisection game, all of the mechanisms described above work together to create a system that rewards honest behavior and counters dishonest claims effectively.

There are many, many ways to build dispute games that accomplish the same goal. We hope that when the OP Stack’s FPS is deployed on OP Goerli, builders in our ecosystem will have fun and get creative in constructing their own dispute games. Each dispute game created can play a role in the social decentralization of the OP Stack, and provide ecosystem participants with options when it comes to how disputes are resolved for any given claim about a piece of information.