A Practical Example: Optimistic Ballads

Let us reinforce our understanding of interactive fraud proofs by studying an optimistic system and playing a real challenge game.

Stories, Steps & Paths

First, we need to invent some fictitious computation we want our optimistic system to emulate.

A story is represented by a bytes32 value. It can be advanced by hashing it with 1 of 5 possible steps: None, Up, Down, Left, Right.

enum Step {
    None,
    Up,
    Down,
    Left,
    Right
}

/// @notice Advance a story by taking a step
function takeStep(bytes32 story, Step step) returns (bytes32) {
    return keccak256(abi.encode(story, step));
}

A Path is a sequence of steps (e.g., [Up, Up, Left, ..., Down]). When a story progresses along a path, it is repeatedly hashed with each step in the path.

/// @notice Advance a story by taking a path
function takePath(
    bytes32 story, 
    Step[] memory path
) returns (bytes32) {
    for (uint i = 0; i < path.length; i++) {
        story = takeStep(story, path[i]);
    }
    return story;
}

Given a story's beginning and a path, computing the story's ending on-chain can be expensive, especially if the path is too long.

Optimistic Stories

BanditBallad wishes to tell a story. But instead of computing the entire story on-chain, BanditBallad will let an off-chain entity propose the story's ending. Then, any individual is free to dispute the proposed story's ending by initiating a challenge. After 7 days, if no one has successfully disputed the proposed value, the story's ending is assumed to be correct.

The path for the story is given by the following array.

[
    Up, Up, Down, Down, Left, Right, Left, Right,
    Up, Up, Down, Down, Left, Right, Left, Right,
    Up, Up, Down, Down, Left, Right, Left, Right,
    Up, Up, Down, Down, Left, Right, Left, Right,
    Up, Up, Down, Down, Left, Right, Left, Right,
    Up, Up, Down, Down, Left, Right, Left, Right
]

Challenge Game

A Challenge contract is deployed when a challenge is initiated on BanditBallad. Challenge is an implementation of the multi-round challenge game we have detailed before, where the challenger and defender agree on a single step to verify on-chain.

The challenger calls challengeStory to propose the search space's middle segment.
The defender calls defendStory to either agree or disagree with the challenger.
Repeating steps 1-2, the challenger and defender will eventually find the earliest step which they disagree on.
At this point, anyone can call resolve to compute the single step result on-chain, and decide which player is correct.

Your Task

Study BanditBallad, Challenge, and Path. Try to understand how a successful Challenge can prove that a proposed story's ending is incorrect.

Then, deploy BanditBallad and initiate a successful challenge!

When BanditBallad is deployed, it is initialized with an incorrectly proposed ending.

Contract Code

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.19;

import "./Challenge.sol";
import "./Path.sol";

contract BanditBallad {

    Path public immutable path;
    bytes32 public immutable beginning;
    bytes32 public ending;

    address public proposer;
    Challenge public challenge;
    uint256 public challengeWindowEnd;

    event ChallengeCreated(address challengeAddress);
    event ChallengerLoses();
    event ChallengerWins();

    /**
     * @notice Create a new ballad.
     * @param _path The path the story should follow.
     * @param _proposedEnding The proposed ending of the story.
     */
    constructor(Path _path, bytes32 _proposedEnding) {
        proposer = msg.sender;

        path = _path;
        beginning = keccak256("ballad.start");
        ending = _proposedEnding;

        // Everyone is given 7 days to challenge the proposed ending
        challengeWindowEnd = block.timestamp + 7 days;
    }

    /**
     * @notice Initiate a new challenge
     * @param _challengerEnding The challenger's ending
     */
    function initiateChallenge(bytes32 _challengerEnding) external {
        require(block.timestamp < challengeWindowEnd, "Challenge window over");
        require(ending != bytes32(0), "No ending proposed");

        // Deploy a challenge contract
        challenge = new Challenge(
            msg.sender,
            proposer,
            beginning,
            ending,
            _challengerEnding,
            path
        );

        emit ChallengeCreated(address(challenge));
    }

    /**
     * @notice Resolve an existing challenge.
     * The challenge must be resolveable.
     */
    function resolveChallenge() external {
        require(address(challenge) != address(0), "No challenge initiated");

        Challenge.Result result = challenge.resolve();
        if (result == Challenge.Result.DefenderWon) {
            // If the challenger loses, do nothing
            emit ChallengerLoses();
        } else {
            // If the challenger wins, the proposed ending is rejected
            delete ending;
            emit ChallengerWins();
        }
    }

}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.19;

import "./Path.sol";

contract Challenge {

    enum Result {
        ChallengerWon,
        DefenderWon
    }

    bytes32 constant NULL = bytes32(0);
    uint256 constant TIMEOUT_WINDOW = 12 hours;

    address public immutable challenger;
    address public immutable defender;

    // The stories asserted by the challenger and defender
    mapping(uint256 => bytes32) public challengerStory;
    mapping(uint256 => bytes32) public defenderStory;
    
    // The path the story should follow
    Path public path;

    // Binary search boundaries
    uint256 L;
    uint256 R;

    // Latest timestamp before an action time out
    uint256 timeout;

    /**
     * @notice Create a new challenge.
     */
    constructor(
        address _challenger, 
        address _defender,
        bytes32 _beginning,
        bytes32 _challengerEnding,
        bytes32 _defenderEnding,
        Path _path
    ) {
        require(
            _challengerEnding != _defenderEnding, 
            "Challenger must disagree with defender"
        );
        uint256 numSteps = _path.getNumSteps();
        
        (challenger, defender) = (_challenger, _defender);
        (L, R) = (0, numSteps); // The initial search space is [0, numSteps]

        // Both parties agree on the story's beginninng
        challengerStory[0] = _beginning;
        defenderStory[0] = _beginning;
        
        // But disagree on the story's ending
        challengerStory[numSteps] = _challengerEnding;
        defenderStory[numSteps] = _defenderEnding;
        path = _path;
    }

    /**
     * @notice The challenger proposes what a segment of the story should be.
     * The segment to challenge is in the middle of the search space. 
     * (i.e., between L and R)
     */
    function challengeStory(bytes32 story) external {
        require(msg.sender == challenger, "msg.sender != challenger");
        require(isSearching(), "Binary search finished");
        uint256 bisectionStep = getBisectionStep();

        require(challengerStory[bisectionStep] == NULL, "Story already challenged");
        
        challengerStory[bisectionStep] = story;
        timeout = block.timestamp + TIMEOUT_WINDOW;

        // In the real world, the defender is an off-chain entity.
        // For this quest, the defender is simulated by an on-chain contract.
        _simulateDefender();
    }

    /**
     * @notice The defender responds to the challenger.
     * Either agreeing with the challenger, and moving the search right,
     * Or disagreeing with the challenger, and moving the search left.
     */
    function defendStory(bytes32 story) external {
        require(msg.sender == defender, "msg.sender != defender");
        require(isSearching(), "Binary search finished");

        uint256 bisectionStep = getBisectionStep();

        require(challengerStory[bisectionStep] != NULL, "Story not challenged");
        require(defenderStory[bisectionStep] == NULL, "Story already defended");

        defenderStory[bisectionStep] = story;
        timeout = block.timestamp + TIMEOUT_WINDOW;

        // Update binary search bounds
        if (challengerStory[bisectionStep] == defenderStory[bisectionStep]) {
            L = bisectionStep; // Agree
        } else {
            R = bisectionStep; // Disagree
        }
    }

    /**
     * @notice Returns the result of the challenge.
     * The challenge must be resolveable, either by timeout or verification.
     */
    function resolve() external view returns (Result) {
        // If binary search not finished, check for timeout
        if (isSearching()) {
            require(block.timestamp > timeout, "Binary search still ongoing");

            uint256 bisectionStep = getBisectionStep();
            if (challengerStory[bisectionStep] == NULL) {
                // Challenger timed out, Defender won
                return Result.DefenderWon;
            } else {
                // Defender timed out, Challenger won
                return Result.ChallengerWon;
            }
        }

        // Else, binary search finished, verify single step
        bytes32 nextStory = path.step(defenderStory[L], L);

        if (nextStory == defenderStory[R]) {
            return Result.DefenderWon;
        } else {
            return Result.ChallengerWon;
        }
    }

    /**
     * @notice Returns true if binary search is still ongoing.
     * Returns false otherwise.
     */
    function isSearching() public view returns (bool) {
        return L + 1 != R;
    }

    /**
     * @notice Returns the middle index in the search space.
     * (i.e., between L and R)
     */
    function getBisectionStep() public view returns (uint256) {
        return (L + R) / 2;
    }

    /**
     * @notice Triggers the defender to respond to the challenger.
     * In the real world, the defender is an off-chain entity.
     * But for this quest, we automate the defender as an on-chain contract.
     */
    function _simulateDefender() private {
        (bool success, ) = defender.call("");
        require(success, "defender failed");
    }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.19;

contract Path {

    enum Step {
        None,
        Up,
        Down,
        Left,
        Right
    }

    Step[] public steps;

    constructor(Step[] memory _steps) {
        steps = _steps;
    }

    /// @notice Advances a story forward by one step.
    function step(bytes32 _story, uint256 _stepNumber) 
        external 
        view 
        returns (bytes32 nextStory) 
    {
        return keccak256(abi.encode(_story, steps[_stepNumber]));
    }

    /// @notice Return the length of the path (i.e., number of steps).
    function getNumSteps() external view returns (uint256) {
        return steps.length;
    }

}

In truth, the Bandit King was an honorable hero, not keeping a single penny he stole. So poor that he could not save his sick wife.