Concepts

The challenge game

How two runs that differ are narrowed, turn by turn, to one step.

A challenge says: I ran this model on this input and got different bits. The game turns that disagreement about a whole run into a disagreement about one step, which the program then executes. Nobody votes and nobody is asked who is right.

The two sides

SideWho
DefenderThe answerer whose output stands on the receipt when the challenge opens. Usually the operator. After an operator has lost a dispute it is the challenger whose answer took its place.
ChallengerAnyone else, with a run that gives a different output.

Each side has posted an output and a trace root, and each has a bond equal to the model's in the vault.

Opening a challenge

challenge is sent inside the receipt's window with the dispute's index (below) and three things: the challenger's output, the challenger's trace root and the challenger's first points (below). The program:

  • takes the challenger's bond into the vault,
  • creates the Dispute account at seeds ["dispute", receipt, index], where index is the receipt's count of earlier challenges as a u16 in little-endian bytes,
  • sets the disputed interval to every step of the model, [0, step_count],
  • pauses the receipt's window and sets its state to challenged.
Refused withWhen
WindowClosedThe window has ended.
SameOutputThe challenger's output equals the answer.
SelfChallengeThe answerer challenges its own answer.
InvalidOutputThe challenger's output is not the model's output_len tokens long.
WrongStateThe receipt is not answered, or the index argument is not the receipt's current count of challenges.
PointCountThe number of points is wrong for the interval.

The interval and its points

Both runs start from the same state, so they agree on the root before step lo = 0: the model's init_root. The root at hi = step_count is the hash of the output, and the two outputs differ, so they disagree there. Somewhere between is the first step where they part. The dispute tracks one interval [lo, hi] with the invariant that the sides agree at lo and disagree at hi.

A side commits points: its own state roots at fixed positions inside the interval. An interval is split into 8 parts by at most 7 points:

Text
point i  =  lo + floor((hi - lo) * i / 8)      for i = 1 … 7

When hi - lo is 8 or less, the points are every interior step instead, so the next selection leaves exactly one step. A turn whose selection is one step wide commits no points.

A turn

The challenger's first points arrive with challenge, so the defender takes the first turn. From then on the sides alternate, and every turn is one bisect instruction with two arguments:

  1. select: the index of the first sub-interval of the other side's points where the mover's own run disagrees. The mover agrees with the root at the start of that sub-interval and disagrees with the root at its end. A mover that agrees with every point selects the last sub-interval, which ends at hi.
  2. points: the mover's own state roots splitting the selected sub-interval, by the same rule.

The selected sub-interval becomes the new [lo, hi]. Each turn divides the interval by 8, so a model of n steps reaches a single step in about log8(n) turns: 6 for the judge's 134,491 steps, 7 for the market model's 1,318,668.

turn 1 · watcher splitssteps 0 to 4,096
turn 2 · operator splitssteps 2,560 to 3,072
turn 3 · watcher splitssteps 2,688 to 2,752
turn 4 · operator splitssteps 2,728 to 2,736
one stepstep 2,731
prove_step: the program executes this step and compares
Each turn keeps one part in eight, down to a single step.
Refused withWhen
NotYourTurnThe sender is not the side on turn.
TurnExpiredThe turn's deadline has passed.
SelectOutOfRangeselect is beyond the sub-intervals.
PointCountThe number of points is wrong for the selected sub-interval.

One step left

When the interval is one step wide the dispute's state changes from open to proving. Both sides agree on the state before the step, lo_root. One side has claimed the state after it, hi_root; that side is recorded as hi_owner and is on turn.

prove_step carries the step's inputs with Merkle proofs. The program executes the step from the agreed state and compares its result with hi_root:

  • the result equals hi_root: the hi_owner was right and wins,
  • the result differs: the hi_owner was wrong and loses.

Anyone can send prove_step, and the result is the program's whoever sends it. The network's keeper sends it for every game that reaches this point, within seconds, so neither side has to sign anything for the last step. One step on chain describes what the transaction carries.

Deadlines

Every turn has a deadline: turn_deadline_secs from Config after the previous turn landed, read from Clock.unix_timestamp. The defender's first deadline counts from the challenge. If the side on turn has not moved by then, anyone can send claim_timeout and that side loses exactly as if a step had proven it wrong. In proving the side on turn is the hi_owner, and a proof has to land before its deadline; the keeper's lands within seconds. claim_timeout before the deadline fails with TurnOpen.

How it ends

The dispute's state becomes resolved and the loser's bond is split between the winner and the protocol, as Bonds and windows describes. Then the receipt:

ResultThe receipt
The challenger lostReturns to answered with the same output. Its window resumes with the time it had left.
The defender lostReturns to answered with the challenger's output and trace root, the challenger's bond locked behind them, and a fresh window. The requester's fee will be paid to the challenger at finalize.

Because every step is deterministic and the program executes the disputed step itself, a run that is correct cannot lose the game to one that is not, whichever side it is on and whichever sub-intervals the other side picks.

Following and playing a dispute

FromWith
The app/disputes/[address] shows the interval narrowing turn by turn, and a side plays its turn there with one signature. The last step needs none.
HTTPGET /v1/disputes/:address returns DisputeDetail; GET /v1/events?dispute= streams each turn as it lands.
TypeScriptlaplace.challenge(receipt, run), laplace.playTurn(dispute, run), laplace.claimTimeout(dispute), and laplace.proveStep(dispute) for a server key.
CLIlaplace watch opens challenges and plays every turn unattended.

Playing the game is the guide for a side in a dispute.