Dem Batch glauben, solange niemand widerspricht
Ein optimistisches Rollup veröffentlicht einen Batch und eine Wurzel, und die Hauptkette glaubt ihm einfach. Geprüft wird nur, wenn jemand widerspricht.
Das klingt riskant. Heute sehen Sie, warum eine einzige ehrliche Prüferin genügt und wie die Hauptkette einen Streit entscheidet, indem sie einen einzigen Schritt neu ausführt.
Am Ende dieser Lektion
Notiz
Ich kann den ersten falschen Schritt in einem Batch per Bisektion finden.
Schlüsselwörter
| Begriff | Was er bedeutet |
|---|---|
| Optimistisches Rollup | ein Rollup, dessen Batches als richtig gelten, solange niemand sie anficht |
| Trace | die Wurzel vor einem Batch und nach jedem Schritt |
| Betrugsbeweis | der Nachweis, dass ein Schritt eines Batches falsch ist |
| Bisektion | eine Stelle finden, indem man den Bereich jedes Mal halbiert |
| Anfechtungsfenster | die Zeit, in der ein Batch angefochten werden kann |
| Endgültig | nicht mehr anfechtbar |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein Trace zeigt, wo sich zwei Seiten trennen
Jeder Batch hat einen Trace: die Wurzel vor dem Batch und nach jeder Überweisung. Wer prüft, spielt die veröffentlichten Daten nach und baut einen eigenen Trace.
Unterscheiden sich die letzten Wurzeln, sind sich beide Seiten am Anfang einig und am Ende uneinig. Irgendwo dazwischen liegt der erste Schritt, an dem sie sich trennen. Die Hauptkette muss nur diesen einen Schritt neu ausführen, um zu sehen, wer recht hat.
Bisektion findet diesen Schritt schnell
Beide Seiten vergleichen ihre Wurzeln beim mittleren Schritt. Sind sie sich dort einig, liegt der Fehler in der zweiten Hälfte. Wenn nicht, liegt er in der ersten.
Jede Frage halbiert, was übrig ist. Sechzehn Schritte brauchen vier Fragen, tausend brauchen zehn und eine Million zwanzig. Echte Streitverfahren machen das auf der Hauptkette, Zug um Zug.
Einen lügenden Sequencer erwischen
docker exec jupyter python3 steps/dispute.pyHier angezeigt, nicht ausgeführt. Mit „Lab starten“ geben Sie ihn im Terminal Ihres eigenen Labs ein.
Beispiel: was das Lab gedruckt hat
| Frage | Gefragter Schritt | Antwort | Der falsche Schritt liegt in |
|---|---|---|---|
| 1 | 8 | einig | Schritt 9 bis 16 |
| 2 | 12 | uneinig | Schritt 9 bis 12 |
| 3 | 10 | einig | Schritt 11 bis 12 |
| 4 | 11 | uneinig | Schritt 11 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Probieren Sie es: Bisektion über 32 Schritte
erster_falscher = 21
def einig(i):
return i < erster_falscher
gut = 0
schlecht = 32
fragen = 0
while schlecht - gut > 1:
mitte = (gut + schlecht) // 2
fragen = fragen + 1
print("Frage zu Schritt", mitte, "einig:", einig(mitte))
if einig(mitte):
gut = mitte
else:
schlecht = mitte
print("erster falscher Schritt:", schlecht, "nach", fragen, "Fragen")
# Setzen Sie erster_falscher auf 1, dann auf 32. Wie viele Fragen sind es jetzt?
Eine Anfechtung muss rechtzeitig kommen
Ein Batch kann nicht ewig offen bleiben, sonst könnte sich niemand auf ihn verlassen. Darum hat jeder Batch ein Anfechtungsfenster, oft sieben Tage. Danach ist er endgültig.
Im Lab ist das Fenster 50400 Slots zu je 12 Sekunden lang, also 7.0 Tage. Einen Batch aus Slot 1000 konnte man in Slot 51399 noch anfechten, in Slot 51400 nicht mehr.
Zusehen, wie ein Anfechtungsfenster schließt
docker exec jupyter python3 steps/window.pyHier angezeigt, nicht ausgeführt. Mit „Lab starten“ geben Sie ihn im Terminal Ihres eigenen Labs ein.
Ein häufiger Fehler
Warnung
Viele glauben, ein optimistisches Rollup brauche eine ehrliche Mehrheit unter den Prüfenden. Eine einzige ehrliche Person, die rechtzeitig hinsieht, genügt, denn die Hauptkette führt den strittigen Schritt selbst aus. Nötig ist aber, dass die Daten veröffentlicht sind und das Fenster lang genug ist.