From Zero to Hero: OP Stack Fault Proof Series 3 [ENG]

Overview of the Fault Dispute Game (FDG) / Bisection Game

Published in

Tokamak Network

18 min readJun 28, 2024

Tokamak Network aims to deliver valuable information for current developers interested in Optimism and the evolution of the Ethereum ecosystem.

This post is the Third installment of the ‘The feature-complete version of OP Stack fault proofs Series,’ comprising 3 planned articles by Tokamak Network. In this article, we explore how Optimism's Fault Proof System resolves Layer 2 state disputes using onchain (MIPS.sol) and offchain (MIPSEVM) components. We cover the roles of proposers and challengers, the PreimageOracle’s data management, and the incentive structures ensuring integrity and security. Additionally, we explain the bisection game, which breaks down disputes into single instructions for precise verification.

💡 Given the interconnected nature of the series, we recommend reading the articles sequentially for a cohesive understanding.

Series 1. Cannon’s Fault Proof System:
In this article, we introduce Optimism’s Fault Proof Program and explain how its Multi-Proof Architecture enhances Layer 2 security and reliability. The program integrates robust fault proof mechanisms to ensure accurate state transitions and efficient dispute resolution. [LINK]
Series 2. Cannon’s Fault Proof System:
In this article, we provides an overview of Cannon(Optimism’s FPVM), which ensures Layer 2 state transition integrity via offchain execution and onchain verification. Key components like MIPS.sol, MIPSEVM, and PreimageOracle work together for efficient dispute resolution. [LINK]

What is a Dispute Game?

A dispute game is a core primitive of the dispute protocol, modeling a simple state machine. It starts with a 32-byte commitment to any piece of information whose validity can be disputed. The resolution function, defined by the implementor, determines whether this commitment is true or false. The OP Stack’s first implementation, the FaultDisputeGame, is permissionless, with its resolution function determined by the outcome of a fault proof program's execution on an emulated VM.

Dispute games rely on two fundamental properties:

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

💡 Different types of dispute games can be created, managed, and upgraded through the DisputeGameFactory, enabling innovative features like aggregate proof systems and the ability to dispute various matters beyond L2 state, such as on-chain binary verification.

The Role of Dispute Games in Optimistic Rollup Security

A dispute game involves multiple parties contesting the validity of a claim, and in optimistic rollups, claims are made about the Layer 2 network state to facilitate Layer 1 withdrawals.
The security of the Layer 2 network depends on the ability to challenge and dispute fraudulent withdrawals. The dispute game interface supports multiple implementations, akin to having multiple protocol clients, ensuring that a bug in one implementation does not compromise the entire consensus process.

Basic Game Specification

Types

Claim: Represents a 32-byte hash or unique identifier for a claim.
Hash: A custom type for a generic hash.
Timestamp: A dedicated timestamp type.
GameType: Represents the type of game being played.
GameId: Represents a packed 4-byte game ID, 8-byte timestamp, and 20-byte address.
[0, 32]: Game Type
[32, 96]: Timestamp
[96, 256]: Address

GameTypes Library

CANNON (ID 0): A dispute game type that utilizes the Cannon VM.
PERMISSIONED_CANNON (ID 1): A permissioned dispute game type that also uses the Cannon VM.
ASTERISC (ID 2): A dispute game type that utilizes the ASTERISC VM.
FAST (ID 254): A dispute game type with a short duration, intended for testing withdrawals and not for production use.
ALPHABET (ID 255): A dispute game type that utilizes the Alphabet VM, also not intended for production use.

GameStatus Enum

Represents the current status of the game:

IN_PROGRESS: Game is ongoing.
CHALLENGER_WINS: Challenger successfully contested the rootClaim.
DEFENDER_WINS: Defender’s rootClaim was not contested.

Key Points of the Dispute Game Factory

1. Claim Submission:

A proposer makes a claim about the state of the layer two network.

2. Set Initialization Bond:

Fig. IDisputeGameFactory.sol (Source: github link)

The factory ensures that the required bond for initializing the dispute game is set. This is done through the setInitBond function, which can be called by the owner to set the bond (in wei) for initializing a game type.
When a bond is updated, the InitBondUpdated event is emitted with the details of the game type and the new bond amount.

💡 setInitBond and InitBondUpdated are part of the administrative setup

3. Dispute Game Initialization:

The dispute game is initiated by the DisputeGameFactory, which creates a new DisputeGame contract. This involves calling the create function on the factory, passing in the _gameType, _rootClaim, and any _extraData.
The factory emits a DisputeGameCreated event with details about the dispute game.

Fig. IDisputeGame.sol (Source: github link)

Bonds ensure that participants (proposers and challengers) have a financial stake in the outcome of a disputed game. This helps to discourage malicious claims and challenges.
This bond is held by the contract to ensure the proposer has a financial stake in the dispute.

4. Dispute Game Configuration:

Fig. DisputeGame.sol (Source: github link)

The new DisputeGame contract is initialized by calling its initialize function. This sets up the game parameters, including the root claim, game creator, L1 block parent hash, and any extra data provided

5. Game Monitoring:

Challengers listen for the DisputeGameCreated event to identify new disputes and participate accordingly.
Challengers may also be required to pay a bond to participate in the dispute.

💡 Challengers have two options: they can use the DisputeGameCreated event to start a new game, or they can participate in already created disputes by monitoring existing DisputeGame contracts and joining the dispute as a challenger.

Dispute Game Occurs…

6. RootClaim Handling(Game Resolution):

_rootClaim is the root claim of the DisputeGame.
The _rootClaim of dispute games can be either agreed upon or disagreed with by the creator.

Handled by the IDisputeGame’s resolve function.
Condition: Can only be called if the game status is IN_PROGRESS.
Purpose: Marks the game status as either CHALLENGER_WINS or DEFENDER_WINS and returns the resolved game status.
Return: The status of the game after resolution.

7. Finalization

Based on the final game status, bonds are awarded to the necessary parties (e.g., the proposer or challenger). The bond is returned to the proposer if they win or forfeited to the challenger if they lose.

💡 The dispute game factory maintains a record of all created dispute games. This includes tracking the game count, game types, timestamps, and implementation details.

‘clones-with-immutable-args’ pattern

The clones-with-immutable-args pattern is used during the Dispute Game Initialization phase. This approach is employed to create lightweight proxy contracts, known as clones, which are tailored with specific immutable arguments.

GameType Implementations:

Each GameType (e.g., CANNON, ASTERISC) has a corresponding implementation contract already deployed within the factory.
When a new game is created, the factory generates a clone of the specific GameType’s implementation contract using the clones-with-immutable-args pattern.

Connection to GameTypes:

Specific Implementations: Each GameType has its own implementation contract.
Dispute Parameters: When a dispute game of a specific GameType is initialized, the factory creates a clone of the corresponding implementation contract with the dispute-specific parameters embedded as immutable arguments.

Creating Clones:

clone(address implementation, bytes memory data): Deploys a clone of the implementation with immutable arguments encoded in data.
clone(uint256 value, address implementation, bytes memory data): Similar to the above, but also deposits value ETH during deployment.

Role and Benefits:

Tailored Clones: Each clone is customized with specific immutable arguments, allowing it to operate according to the parameters of the particular dispute.
Shared Core Logic: The clones share the same core logic from the pre-deployed implementation contract, ensuring consistency.
Efficiency and Cost-Effectiveness: This approach makes the deployment of new game instances more efficient and cost-effective, as it avoids redeploying the entire contract logic each time.

💡 In summary, the clones-with-immutable-args pattern allows for the efficient and tailored deployment of dispute game instances by cloning existing implementation contracts and embedding specific parameters. This ensures that each game operates according to its designated GameType without the need to redeploy the core logic every time.

Bisection Game / Fault Dispute Game (FDG)

Key Concepts:

1. Virtual Machine (VM)

Definition: A Virtual Machine (VM) is a computational model that processes state transitions using the State Transition Function (STF) to compute the post-state from a given pre-state.

Pre-state: The initial state before the transition.

Optional Proof: The proof needed for the transition to occur.

Post-state: The resulting state after the transition.

Mathematical Definition: This means that the VM, given the pre-state and the proof, computes the post-state.
Data Integrity: The pre-state contains a commitment to the proof, ensuring data integrity by verifying the transition process.

2. PreimageOracle

Definition: A PreimageOracle is a pre-image data store used by Virtual Machines (VMs) to access external data during the State Transition Function (STF), requiring preloading with pertinent data and utilizing key-based retrieval methods specific to each VM.

Preloading Data: Necessary to preload the PreimageOracle with pertinent data before executing the STF.
Key-based Retrieval: The method varies according to the specific VM.

3. Execution Trace

Definition: This is a sequence of VM states showing the transition from the initial state to the final state, representing the process through which the VM moves from one state to the next.

This is the starting point of the VM state before any transitions occur

The first transition where the VM processes the initial state.

The second transition where the VM processes state.

The final state after n transitions.

4. Claims

Definition: Asserts an output root or the state of the FPVM at a given instruction.

Claims represent individual steps in the execution trace and each claim corresponds to a single state transition within the execution trace.
Represented as a Hash type (bytes32), which can be either an output root or acommitment to the last VM state in a trace(each of the execution trace).
Execution trace subgames at SPLIT_DEPTH + 1 start with a claim that commits to the entire execution trace between two consecutive output roots (block n -> block n+1).

5. Anchor State and Initialization

Definition: An anchor state (or anchor output root) is a previous output root that is assumed to be valid.

Initialization:

The Fault Dispute Game (FDG) is initialized with an anchor state. Execution occurs between this anchor state and the claimed output root.
The anchor state is retrieved from the Anchor State Registry contract, with the initial anchor state for FDG being the genesis state of L2.

6. Subgame

Definition: A subgame is a Directed Acyclic Graph (DAG) of depth 1, where the root of the DAG is a Claim and the children are Claims that counter the root. This structure represents a fundamental dispute between two parties over a single piece of information.

7. Game Tree

Definition: A binary tree of positions, each claim in the DAG references a position in the Game Tree.

Depth:

Split Depth: The maximum depth at which claims about output roots can occur.
Maximum Depth (MAX_GAME_DEPTH): Preset to an FDG implementation, defining the total depth of the Game Tree.

Structure:

The Game Tree contains 2^{d+1} — 1 positions, where d is the MAX_GAME_DEPTH (unless d=0, in which case there’s only 1 position).

8. Position

Definition: The location of a claim in the Game Tree is represented by a “generalized index” (gindex).

Generalized Index (gindex):

The high-order bit represents the level in the tree.
The remaining bits form a unique bit pattern, creating a unique identifier for each node.

Calculation:

The gindex of a position n is calculated as 2^(d(n))+idx(n), where:
d(n): Function returning the depth of the position in the Game Tree.
idx(n): Function returning the index of the position at its depth (starting from the left).

9. MAX_CLOCK_DURATION

Definition: Keeps track of the total time each team takes to make moves, similar to a chess clock that prevents delays by ensuring timely moves. (An immutable preset to an FDG implementation.)

Functionality:

Making a move resumes the clock for the disputed claim and pauses it for the newly added claim.
If a claim’s clock has less than CLOCK_EXTENSION seconds remaining, it is given exactly CLOCK_EXTENSION seconds. This helps ensure that there is enough time for an honest move. MAX_GAME_DEPTH

💡 The claim's clock is a timer associated with each claim in the Fault Dispute Game, tracking the amount of time a team has to make a move on that particular claim. This clock mechanism ensures that teams make timely moves and prevents delays in the game.

For claims that are the root of an execution trace bisection, if their clams’s clock has less than CLOCK_EXTENSIONseconds remaining, they are given exactly CLOCK_EXTENSION * 2 seconds. This extra time allows for the necessary off-chain calculations to be completed.

Expiration:

A move against a claim is no longer possible once the parent claim’s clock has accumulated MAX_CLOCK_DURATION seconds, causing the claim’s clock to expire.

💡 In recent evaluations of blockchain security mechanisms, specific vulnerabilities were identified in the collaboration between Offchain Labs and Optimism, particularly in the management of timers within their Proof of Fraud systems. These vulnerabilities highlight the challenges in designing systems that require the participation of multiple parties, which can complicate the management of critical elements like timers. More Detail.

Key Game Mechanics

1. Initialization

Root Claim: The FDG starts with a root claim, which is an output root that corresponds to the state of Layer 2 (L2) at a specific L2 block number. This root claim is asserted by the Defender.

2. Actors Involved

Players: There are two main types of players: Challengers and Defenders.

Challengers: Aim to dispute the root claim by proving it invalid.
Defenders: Aim to prove the root claim is valid.

3. Game Tree and Claims

Game Tree: A binary tree structure where each node represents a claim. Each claim commits to a specific state in the execution trace.
Execution Trace: A sequence of VM states representing the transitions from the initial state (ABSOLUTE_PRESTATE) to the disputed state.

4. Making Moves

Moves: Players interact with the game by making moves, which are either attacks or defenses against existing claims. Each move adds new claims to the Game Tree at strictly increasing depth. Once a claim reaches MAX_GAME_DEPTH, the only way to dispute it is through a step.

Attack: A move made to dispute a claim when you disagree with it.

The attack position relative to a node (n) in the Game Tree is calculated by multiplying its gindex by 2.
The new claim at the attack position commits to half of the trace of the original claim’s range.
If a claim is positioned at node 5 in the Game Tree:
- Attacking this claim moves to a new position at node 10.
- This new claim at node 10 disputes the claim at node 5.

Defense: A move made to support a claim when you agree with both the claim and its parent.

Supports a claim by providing an execution trace that defends the previous state.
The defense position relative to a node (n) in the Game Tree commits to the first half of (n+1)’s trace range.
Defending a claim at node 10:
- The defense position is at node 11 (5 + 1).
- Commits to the first half of node 11’s trace range.

5. Bisection

Bisection Process: The game progresses by iteratively bisecting the disputed range of states until the dispute is narrowed down to a single VM instruction step.

Split Depth: Defines the maximum depth at which claims about output roots can occur. Below this depth, the game focuses on bisecting execution traces.
MAX_GAME_DEPTH: When the bisection reaches the maximum game depth, the position of claims corresponds to specific indices in the execution trace. At this point, the game can query the VM to determine the validity of claims.

6. Stepping

Step: Similar to moves, there are two ways to step on a claim: attack or defend. These steps determine the pre-state input to the VM STF and the expected output.

Attack Step: Challenges a claim by providing a pre-state, proving an invalid state transition.

Input: Uses the previous state in the execution trace.
Output: Expects the disputed claim’s state.
Requirement: There must be an existing claim in the DAG that commits to the input state.

Defense Step: Challenges a claim by proving it was an invalid attack, thereby defending the disputed parent’s claim.

Input: Uses the disputed claim’s state.
Output: Expects the next state in the execution trace.
Requirement: There must be an existing claim in the DAG that commits to the expected output state.

FDG Step Mechanics

Handling Inputs: The FDG step manages the inputs to the VM and asserts the expected output.
A step that successfully proves an invalid post-state (when attacking) or pre-state (when defending) is a successful counter against the disputed claim.

7. Interaction with PreimageOracle

In the context of a dispute game, VM state transitions rely on external data provided by the PreimageOracle. Players must supply this data beforehand to ensure successful state transitions during the dispute resolution process.

Fig. IFaultDisputeGame.sol (Source: github link)

Function: addLocalData

Loads local data into the VM’s PreimageOracle.

Parameters:

_ident: The local identifier of the data to post.
_execLeafIdx: The index of the leaf claim in an execution subgame that requires the local data for a step.
_partOffset: The offset of the data to post.

Data Identifiers:
There is specific data required to verify and process VM state transitions during disputes.

1. Parent L1 head hash at the time of the proposal.

This is the hash of the head block of the Layer 1 chain at the moment the proposal was made. It serves as a reference point for the state of the Layer 1 blockchain at that specific time.

2. Starting output root hash (commits to block # n).

This is the root hash of the output state after processing block # n. It represents the state of the Layer 2 network at block number n.

3. Disputed output root hash (commits to block # n + 1).

This is the root hash of the output state that is being disputed, corresponding to block # n + 1. It shows the state of the Layer 2 network after the disputed block.

4. Disputed L2 block number (block # n + 1).

This is the number of the Layer 2 block that is under dispute, which follows block number n.

5. L2 Chain ID.

This is the identifier of the specific Layer 2 chain where the dispute is taking place. It helps in distinguishing between multiple Layer 2 networks if more than one is being used.

Submitting Preimages

Small Preimages: Submitted one by one.
Large Preimages: Submitted via streaming over multiple transactions.

Steps for Large Preimage Proposals

Large preimage proposals allow submitters to stream in a large preimage over multiple transactions with commitments to the intermediate state of the keccak256 function.

Fig. PreimageOracle.sol (Source: github link)

Function: hashLeaf

Returns a leaf hash to add to a preimage proposal merkle tree.

Parameters:

input: A 136-byte chunk of the input.
blockIndex: The index of the block that input corresponds to.
stateCommitment: The hash of the full 5x5 state matrix after absorbing and permuting input.
Requirement: The input must be exactly the size of the keccak256 rate (136 bytes).

8. Finalization

Anchor State Registry: Once the game is resolved, the final state is reported to the Anchor State Registry. The registry updates the anchor state if the game resolves in favor of the defender and the new state is more recent than the current anchor state.

9. Challenge Period

The challenge period begins once the full preimage and all intermediate state commitments are posted. During this time, challengers can verify the integrity of the Merkle Tree constructed on-chain. Here’s a detailed breakdown of the steps and processes involved:

Steps:

1. Create a merkle proof for the agreed-upon prestate leaf.

Generate a Merkle proof that demonstrates the inclusion of the agreed-upon prestate leaf in the Merkle Tree. This proof is used to verify the initial state before any disputed transitions.

2. Create a merkle proof for the disputed post-state leaf.

Generate a Merkle proof for the disputed post-state leaf. This proof is necessary to validate the state after the disputed transition, ensuring that it matches the claimed outcome.

3. Compute the state matrix at the agreed-upon prestate.

Calculate the state matrix at the agreed-upon prestate. This involves computing the intermediate states and transformations leading up to the disputed transition.

Submission: Submit all the generated data, including the Merkle proofs and computed state matrix, to the PreimageOracle. This submission provides the necessary information for on-chain verification.

Validation:

1. SHA3 Permutation Execution:

The submitted data triggers an on-chain execution of the SHA3 permutation. This process involves hashing the state matrix and other relevant data to produce a final hash.

2. Hash Comparison:

The resulting hash from the SHA3 permutation is compared to the proposer’s claimed hash. This comparison determines the validity of the proposal:
Match: If the hash matches the proposer’s claim, the proposal remains valid and can proceed toward finalization.
Mismatch: If the hash does not match, the proposal is marked as challenged.

3. Finalization:

If there are no challenges after the challenge period ends, the proposal may be finalized. The preimage part associated with the finalized proposal is then placed into the authorized mappings for the FPVM (Fraud Proof Virtual Machine) to read and use in future verifications.

Summary

Initial Output Root

The output root is a hash representing the final state of the Layer 2 chain after executing all transactions in a batch.

Intermediate Execution Steps

Execution steps are individual operations or instructions executed by the VM during the processing of transactions. These steps provide a detailed, step-by-step account of how the VM’s state evolves during transaction processing. Each step changes the VM state slightly based on the operation performed.
💡 A Challenger can either attack an instruction by marking it as incorrect or move to the next instruction without taking any action.

Bottom Leaf Node (Below SPLIT_DEPTH)

The bottom leaf node represents the VM’s hashed state at the finest level of granularity within the fault-proof game.
It serves as the most detailed point of contention in a dispute, encapsulating the complete state of the VM (including memory, registers, stack, etc.) at a specific execution point.
It doesn’t focus on individual execution steps but on the VM’s state as a whole at a very specific point in time.

When a challenger reaches the bottom leaf node (below SPLIT_DEPTH) in a dispute, determining whether the hashed state is correct or incorrect involves a specific process:

Reconstruct the State: The challenger needs to reconstruct the VM’s state up to that point using the execution trace. This involves replaying the instructions from a known correct state to the point of the disputed hashed state.
Verify State Transitions: By verifying each state transition step-by-step, the challenger can ensure that the sequence of operations leads to the hashed state in question.
Compare Hashed State: The challenger computes the expected hashed state from the reconstructed state and compares it with the claimed hashed state.
Identify Discrepancies: If there is a mismatch between the expected hashed state and the claimed hashed state, the challenger can prove that the hashed state is incorrect. If they match, the hashed state is considered correct.

Conclusion

Dispute games are a crucial and exciting component of the OP Stack’s Fault Proof System, offering innovative solutions for decentralized fault detection. Their modular design and incentive structures ensure fair and efficient resolution of disputes, paving the way for robust and scalable fault detection in the Superchain ecosystem.