Fault Proofs

Deep dive into the fault proof game - bisection depth 73, absolute prestate, and challenge mechanics

Fault Proofs

Nexis Appchain’s security model relies on fault proofs, a mechanism that allows anyone to challenge invalid state transitions. This document explains the technical details of how the fault proof game works.

Overview

Optimistic Security

State roots are assumed valid unless proven wrong

Bisection Game

Binary search to narrow disputes to a single instruction

73-Step Depth

Maximum game depth allows 2^73 instruction traces

Economic Bonds

Both parties stake ETH, winner takes all

How Fault Proofs Work

The Problem

Traditional blockchains validate every transaction on every node. This is secure but expensive. Rollups optimize by executing transactions off-chain and only posting commitments on-chain. But how do we ensure these commitments are correct?

Fault Proofs: Instead of validating everything, we optimistically assume correctness and allow anyone to prove incorrectness.

The Solution

The Fault Proof Game

Game Structure

The fault proof game is a turn-based bisection protocol that narrows a disagreement over an entire execution trace to a dispute over a single instruction.

Players:

• Proposer: Claims state root X is correct at block N
• Challenger: Claims state root Y is correct at block N

Goal:

• Identify the exact instruction where they disagree
• Execute that instruction on-chain to determine who’s right

Game Tree

Round 0: Dispute over entire trace (2^73 instructions)
  Proposer: "State at step 2^73 is X"
  Challenger: "State at step 2^73 is Y"

Round 1: Bisect at 2^72
  Proposer: "State at step 2^72 is A"
  Challenger: "State at step 2^72 is B"
  → Disagreement is in first half

Round 2: Bisect at 2^71
  Proposer: "State at step 2^71 is C"
  Challenger: "State at step 2^71 is C" (agree!)
  → Disagreement is in second quarter

... 73 rounds ...

Round 73: Single instruction at step S
  Proposer: "Executing instruction S produces state X"
  Challenger: "Executing instruction S produces state Y"
  → Execute instruction on-chain to determine truth

Bisection Depth

Why 73 levels?

// Maximum instructions in a single block
const MAX_GAS = 30_000_000;
const MIN_GAS_PER_INSTRUCTION = 3; // Simplest opcodes
const MAX_INSTRUCTIONS = MAX_GAS / MIN_GAS_PER_INSTRUCTION; // ~10 million

// For an entire batch (30 blocks @ 2s = 60s)
const BLOCKS_PER_BATCH = 30;
const MAX_INSTRUCTIONS_PER_BATCH = MAX_INSTRUCTIONS * BLOCKS_PER_BATCH;
// ~300 million instructions

// Need enough depth to bisect this many steps
const DEPTH = Math.ceil(Math.log2(MAX_INSTRUCTIONS_PER_BATCH));
// log2(300,000,000) ≈ 28 bits per block
// For safety, use 73 total depth

console.log('Max instructions:', Math.pow(2, 73)); // 9.44 * 10^21

The 73-level tree can accommodate up to 2^73 ≈ 9.44 quintillion instructions - far more than any realistic execution trace.

Implementation

Dispute Game Contract

// DisputeGameFactory.sol - Creates new games
contract DisputeGameFactory {
    enum GameType {
        CANNON,      // MIPS VM for actual execution
        PERMISSIONED // Governance override
    }

    struct GameParams {
        GameType gameType;
        bytes32 rootClaim;
        bytes extraData;
    }

    mapping(bytes32 => IDisputeGame) public games;

    event DisputeGameCreated(
        address indexed game,
        GameType indexed gameType,
        bytes32 indexed rootClaim
    );

    function create(
        GameType gameType,
        bytes32 rootClaim,
        bytes calldata extraData
    ) external payable returns (IDisputeGame game) {
        // Create new game instance
        game = _createGame(gameType, rootClaim, extraData);

        // Require bond from creator
        require(msg.value == BOND_AMOUNT, "Incorrect bond");

        // Initialize game
        game.initialize{value: msg.value}(msg.sender);

        emit DisputeGameCreated(address(game), gameType, rootClaim);
    }
}

Fault Dispute Game

// FaultDisputeGame.sol - The actual bisection game
contract FaultDisputeGame is IDisputeGame {
    uint256 public constant MAX_GAME_DEPTH = 73;
    uint256 public constant BOND_AMOUNT = 1 ether;

    struct ClaimData {
        uint32 parentIndex;
        bool countered;
        bytes32 claim;
        Position position;
        Clock clock;
    }

    struct Position {
        uint128 depth;     // Current depth in game tree
        uint128 indexAtDepth; // Index at this depth
    }

    ClaimData[] public claims;
    mapping(uint256 => uint256) public credit; // Bonds held

    // Root claim (proposer's initial claim)
    bytes32 public immutable rootClaim;

    // Absolute prestate (starting state)
    bytes32 public immutable absolutePrestate;

    // L2 block number being disputed
    uint256 public immutable l2BlockNumber;

    constructor(
        bytes32 _rootClaim,
        uint256 _l2BlockNumber,
        bytes32 _absolutePrestate
    ) {
        rootClaim = _rootClaim;
        l2BlockNumber = _l2BlockNumber;
        absolutePrestate = _absolutePrestate;

        // Initialize with root claim at depth 0
        claims.push(ClaimData({
            parentIndex: 0,
            countered: false,
            claim: _rootClaim,
            position: Position(0, 0),
            clock: Clock.wrap(0)
        }));
    }

    // Challenge a claim
    function attack(
        uint256 parentIndex,
        bytes32 claim
    ) external payable {
        require(msg.value == BOND_AMOUNT, "Incorrect bond");

        ClaimData memory parent = claims[parentIndex];
        require(!parent.countered, "Already countered");

        // New claim is one level deeper
        Position memory position = Position({
            depth: parent.position.depth + 1,
            indexAtDepth: parent.position.indexAtDepth * 2 // Left child
        });

        require(position.depth <= MAX_GAME_DEPTH, "Max depth reached");

        // Add claim
        claims.push(ClaimData({
            parentIndex: uint32(parentIndex),
            countered: false,
            claim: claim,
            position: position,
            clock: Clock.wrap(uint64(block.timestamp))
        }));

        // Mark parent as countered
        claims[parentIndex].countered = true;

        // Hold bond
        credit[msg.sender] += msg.value;

        emit Attack(parentIndex, claims.length - 1, claim);

        // Check if game can be resolved
        if (position.depth == MAX_GAME_DEPTH) {
            _resolve();
        }
    }

    // Defend a claim
    function defend(
        uint256 parentIndex,
        bytes32 claim
    ) external payable {
        require(msg.value == BOND_AMOUNT, "Incorrect bond");

        ClaimData memory parent = claims[parentIndex];

        // New claim is at same level, right sibling
        Position memory position = Position({
            depth: parent.position.depth + 1,
            indexAtDepth: parent.position.indexAtDepth * 2 + 1 // Right child
        });

        require(position.depth <= MAX_GAME_DEPTH, "Max depth reached");

        claims.push(ClaimData({
            parentIndex: uint32(parentIndex),
            countered: false,
            claim: claim,
            position: position,
            clock: Clock.wrap(uint64(block.timestamp))
        }));

        credit[msg.sender] += msg.value;

        emit Defend(parentIndex, claims.length - 1, claim);

        if (position.depth == MAX_GAME_DEPTH) {
            _resolve();
        }
    }

    // Execute single step to resolve leaf claim
    function step(
        uint256 claimIndex,
        bool isAttack,
        bytes calldata stateData,
        bytes calldata proof
    ) external {
        ClaimData memory claim = claims[claimIndex];
        require(claim.position.depth == MAX_GAME_DEPTH, "Not at max depth");

        // Load pre-state from the claim
        bytes32 preState = isAttack ? claim.claim : claims[claim.parentIndex].claim;

        // Execute single instruction using MIPS VM
        bytes32 postState = MIPS_VM.step(stateData, proof);

        // Determine winner
        address winner;
        if (isAttack && postState == claim.claim) {
            // Attacker was correct
            winner = _getCoinbase(claimIndex);
        } else if (!isAttack && postState == claims[claim.parentIndex].claim) {
            // Defender was correct
            winner = _getCoinbase(claim.parentIndex);
        } else {
            revert("Step verification failed");
        }

        // Resolve game in winner's favor
        _distributeBonds(winner);
    }

    function _resolve() internal {
        // Traverse tree to find winning claim
        uint256 rightmostLeaf = _findRightmostLeaf();

        // Winner is whoever posted the rightmost leaf
        address winner = _getCoinbase(rightmostLeaf);

        _distributeBonds(winner);
    }

    function _distributeBonds(address winner) internal {
        // Calculate total bonds in the game
        uint256 totalBonds = claims.length * BOND_AMOUNT;

        // Pay winner
        (bool success, ) = winner.call{value: totalBonds}("");
        require(success, "Transfer failed");

        // Update output oracle if challenger won
        if (winner != _getCoinbase(0)) { // 0 is root claim (proposer)
            IOutputOracle(OUTPUT_ORACLE).deleteProposal(l2BlockNumber);
        }

        emit GameResolved(winner);
    }
}

Position Encoding

The position in the game tree is encoded as (depth, indexAtDepth):

library Position {
    type Position is uint256;

    // Extract depth (left 128 bits)
    function depth(Position _position) internal pure returns (uint128) {
        return uint128(Position.unwrap(_position) >> 128);
    }

    // Extract index at depth (right 128 bits)
    function indexAtDepth(Position _position) internal pure returns (uint128) {
        return uint128(Position.unwrap(_position));
    }

    // Create position
    function pack(uint128 _depth, uint128 _index) internal pure returns (Position) {
        return Position.wrap((uint256(_depth) << 128) | uint256(_index));
    }

    // Move to left child
    function moveLeft(Position _position) internal pure returns (Position) {
        uint128 d = depth(_position);
        uint128 i = indexAtDepth(_position);
        return pack(d + 1, i * 2);
    }

    // Move to right child
    function moveRight(Position _position) internal pure returns (Position) {
        uint128 d = depth(_position);
        uint128 i = indexAtDepth(_position);
        return pack(d + 1, i * 2 + 1);
    }
}

MIPS VM

At the deepest level of the game, a single instruction must be executed on-chain. Nexis uses a MIPS emulator for this:

Why MIPS?

• Simple ISA: Easy to implement on-chain
• Deterministic: No undefined behavior
• Well-supported: Go, Rust, C all compile to MIPS
• Small: Minimal on-chain execution cost

On-Chain Execution

// MIPS.sol - On-chain MIPS emulator
contract MIPS {
    // VM state
    struct State {
        bytes32 memRoot;      // Merkle root of memory
        bytes32 preimageKey;  // Key for oracle lookups
        uint32 preimageOffset;
        uint32 pc;            // Program counter
        uint32 nextPC;
        uint32 lo;            // Multiplication/division results
        uint32 hi;
        uint32 heap;
        uint8 exitCode;
        bool exited;
        uint64 step;
        uint32[32] registers; // 32 MIPS registers
    }

    function step(
        bytes calldata stateData,
        bytes calldata proof
    ) external returns (bytes32) {
        // Decode state
        State memory state = abi.decode(stateData, (State));

        // Fetch instruction at PC
        uint32 instruction = _fetchInstruction(state, proof);

        // Decode and execute
        _execute(state, instruction);

        // Increment step counter
        state.step++;

        // Return new state hash
        return keccak256(abi.encode(state));
    }

    function _execute(State memory state, uint32 instruction) internal {
        uint32 opcode = instruction >> 26;

        if (opcode == 0x00) { // R-type instructions
            uint32 funct = instruction & 0x3F;

            if (funct == 0x20) { // ADD
                uint32 rs = (instruction >> 21) & 0x1F;
                uint32 rt = (instruction >> 16) & 0x1F;
                uint32 rd = (instruction >> 11) & 0x1F;
                state.registers[rd] = state.registers[rs] + state.registers[rt];
            }
            // ... more R-type instructions
        } else if (opcode == 0x08) { // ADDI
            uint32 rs = (instruction >> 21) & 0x1F;
            uint32 rt = (instruction >> 16) & 0x1F;
            int32 imm = int16(instruction & 0xFFFF);
            state.registers[rt] = state.registers[rs] + uint32(imm);
        }
        // ... more opcodes

        // Update PC
        state.pc = state.nextPC;
        state.nextPC = state.pc + 4;
    }
}

Example: Dispute Resolution

// Dispute resolution workflow
class DisputeResolver {
  async resolveDispute(proposalIndex: number) {
    // 1. Create dispute game
    const game = await this.factory.create(
      GameType.CANNON,
      proposedRoot,
      encodedBlockData
    );

    console.log('Dispute game created:', game.address);

    // 2. Derive correct state
    const correctState = await this.deriveState(proposalIndex);

    // 3. Play the bisection game
    let claimIndex = 0; // Start at root

    for (let depth = 0; depth < MAX_DEPTH; depth++) {
      const claim = await game.claims(claimIndex);

      // Check if we agree at this point
      const ourClaim = this.getClaimAtPosition(
        correctState,
        claim.position
      );

      if (ourClaim !== claim.claim) {
        // We disagree - attack this claim
        console.log(`Attacking claim ${claimIndex} at depth ${depth}`);

        const tx = await game.attack(claimIndex, ourClaim, {
          value: ethers.parseEther('1')
        });

        await tx.wait();

        // Move to our new claim
        claimIndex = (await game.claims()).length - 1;
      } else {
        // We agree - wait for opponent's move
        console.log(`Agree at depth ${depth}, waiting...`);
        await this.waitForCounterClaim(game, claimIndex);
        claimIndex = claim.childIndex; // Move to child
      }
    }

    // 4. At max depth, execute single step
    console.log('Max depth reached, executing single step...');

    const preState = await this.getPreState(claimIndex);
    const proof = await this.generateProof(preState);

    const tx = await game.step(
      claimIndex,
      true, // isAttack
      preState,
      proof
    );

    await tx.wait();
    console.log('Dispute resolved!');
  }
}

Economic Security

The fault proof system is secured by economic incentives:

Bond Mechanics

contract BondManager {
    uint256 public constant BOND_AMOUNT = 1 ether;

    mapping(address => uint256) public lockedBonds;
    mapping(uint256 => uint256) public gameBonds;

    function lockBond(uint256 gameId, address player) external payable {
        require(msg.value == BOND_AMOUNT, "Incorrect bond");
        lockedBonds[player] += msg.value;
        gameBonds[gameId] += msg.value;
    }

    function slashLoser(uint256 gameId, address loser, address winner) external {
        uint256 loserBond = lockedBonds[loser];
        lockedBonds[loser] = 0;

        // Winner gets both bonds
        lockedBonds[winner] += loserBond;

        emit Slashed(loser, loserBond);
    }

    function claimBond(address player) external {
        uint256 amount = lockedBonds[player];
        require(amount > 0, "No bond to claim");

        lockedBonds[player] = 0;
        payable(player).transfer(amount);
    }
}

Attack Cost Analysis

To successfully attack the network with an invalid state:

Attacker Costs:

1. Proposer bond: 1 ETH
2. Must defeat all challengers in bisection games
3. Each honest challenger requires defeating: +1 ETH
4. With N honest challengers: N+1 ETH total

Defender Costs:

1. Single honest validator: 1 ETH bond
2. If correct, receives attacker’s bond: +1 ETH profit

Equilibrium:

• As long as one honest party exists with 1 ETH, attacks fail
• Attacker loses all bonds
• Network remains secure

Griefing Resistance

// Prevent frivolous challenges
contract GriefingProtection {
    uint256 public constant MOVE_TIMEOUT = 3 days;
    mapping(uint256 => uint256) public lastMove;

    function checkTimeout(uint256 gameId) external {
        require(
            block.timestamp > lastMove[gameId] + MOVE_TIMEOUT,
            "Not timed out"
        );

        // Player who didn't respond loses
        address defaulter = getCurrentPlayer(gameId);
        slashPlayer(gameId, defaulter);
    }

    // Exponentially increasing bonds for multiple claims
    function requiredBond(address player) public view returns (uint256) {
        uint256 activeGames = getActiveGames(player).length;
        return BOND_AMOUNT * (2 ** activeGames); // 1, 2, 4, 8 ETH...
    }
}

Learn More

Block Validation

How blocks are validated and finalized

Consensus Mechanism

Understand the consensus architecture

Run a Validator

Help secure the network

Infrastructure Overview

Complete architecture documentation

---

Want to deep dive into MIPS VM? Check out the Optimism Cannon documentation which Nexis builds upon.