Easier to read with cream paper, a tint, more contrast or larger text? Choose your colours and text, once, for every page.

Free lesson

Optimistic rollups and fraud proofs

After this lesson: I can find the first wrong step in a batch by bisection.

70 min lesson2 commandsRollup lab: batches, fraud proofs, data availability and exits in Python

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

WordWhat it means
Optimistic rollupa rollup whose batches count as right unless challenged
Tracethe root before a batch and after every step
Fraud proofevidence that one step of a batch is wrong
Bisectionfinding a point by halving the range each time
Challenge windowthe time in which a batch can be disputed
Finalno 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

Command
docker exec jupyter python3 steps/dispute.py

Shown here, not run. Press Start lab to type it into your own lab’s terminal.

Worked example: what the lab printed

QuestionStep askedAnswerWrong step is in
18agreesteps 9 to 16
212disagreesteps 9 to 12
310agreesteps 11 to 12
411disagreestep 11

The cells students fill in are left blank in this preview.

Try it: bisection over 32 steps

Code: python
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

Command
docker exec jupyter python3 steps/window.py

Shown 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.

About this lab and its source: Rollup lab: batches, fraud proofs, data availability and exits in Python

Teaching a class? Set this module for your students with a teacher guide, marked assignments and a lab for every student.