Trust the batch unless somebody objects
An optimistic rollup posts a batch and a root, and the main chain simply believes it. Nobody checks anything unless somebody objects.
That sounds risky. Today you see why one honest checker is enough, and how the main chain settles an argument by re-running a single step.
By the end of this lesson
Note
I can find the first wrong step in a batch by bisection.
Key words
| Word | What it means |
|---|---|
| Optimistic rollup | a rollup whose batches count as right unless challenged |
| Trace | the root before a batch and after every step |
| Fraud proof | evidence that one step of a batch is wrong |
| Bisection | finding a point by halving the range each time |
| Challenge window | the time in which a batch can be disputed |
| Final | no longer open to challenge |
The cells students fill in are left blank in this preview.
A trace shows where two sides part
Every batch has a trace: the root before it and after each transfer. A checker replays the posted data and builds its own trace.
If the last roots differ, the two sides agree at the start and disagree at the end. Somewhere in between is the first step where they part. The main chain only needs to re-run that one step to see who is right.
Bisection finds that step quickly
The two sides compare their roots at the middle step. If they agree there, the fault is in the second half. If not, it is in the first half.
Each question halves what is left. Sixteen steps need four questions, a thousand need ten, and a million need twenty. Real dispute games do this on the main chain, one move at a time.
Catch a lying sequencer
docker exec jupyter python3 steps/dispute.pyShown here, not run. Press Start lab to type it into your own lab’s terminal.
Worked example: what the lab printed
| Question | Step asked | Answer | Wrong step is in |
|---|---|---|---|
| 1 | 8 | agree | steps 9 to 16 |
| 2 | 12 | disagree | steps 9 to 12 |
| 3 | 10 | agree | steps 11 to 12 |
| 4 | 11 | disagree | step 11 |
The cells students fill in are left blank in this preview.
Try it: bisection over 32 steps
first_wrong = 21
def agree(i):
return i < first_wrong
good = 0
bad = 32
questions = 0
while bad - good > 1:
middle = (good + bad) // 2
questions = questions + 1
print("ask about step", middle, "agree:", agree(middle))
if agree(middle):
good = middle
else:
bad = middle
print("first wrong step:", bad, "after", questions, "questions")
# Change first_wrong to 1, then to 32. How many questions now?
A challenge must come in time
A batch cannot stay open for ever, or nobody could rely on it. So each batch has a challenge window, often seven days. After it the batch is final.
In the lab the window is 50400 slots of 12 seconds, which is 7.0 days. A batch posted at slot 1000 could be challenged at slot 51399 and not at 51400.
Watch a challenge window close
docker exec jupyter python3 steps/window.pyShown here, not run. Press Start lab to type it into your own lab’s terminal.
A common mistake
Warning
Many people think an optimistic rollup needs most checkers to be honest. One honest checker who watches in time is enough, because the main chain re-runs the disputed step itself. What it does need is that the data was published and the window is long enough.