Interactive Fraud Proofs

close button

Part II

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.

  1. The challenger calls challengeStory to propose the search space's middle segment.

  2. The defender calls defendStory to either agree or disagree with the challenger.

  3. Repeating steps 1-2, the challenger and defender will eventually find the earliest step which they disagree on.

  4. 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, ) =""); 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.