Die Doppelausgabe-Rechnung im Bitcoin-Whitepaper, nachgerechnet
Abschnitt 11 des Bitcoin-Whitepapers nachgerechnet: Die Tabellen stimmen, das Modell unterschätzt das Risiko. Mit Herleitung, Code und Simulation.
Wer eine Bitcoin-Zahlung annimmt, wartet, bis die Transaktion in einem Block steht und weitere Blöcke darauf folgen. Der Grund ist die Doppelausgabe: Ein Angreifer bezahlt, lässt die Ware liefern und versucht dann, eine alternative Kette zu veröffentlichen, in der dieselben Coins an ihn selbst zurückgehen. Gelingt das, verschwindet die Zahlung aus der Kette, die alle Knoten für gültig halten.
Wie lange man warten sollte, rechnet Abschnitt 11 des Whitepapers von 2008 vor. Das Ergebnis sind Tabellen, die bis heute zitiert werden. Nachprogrammiert lassen sie sich exakt reproduzieren. Das Modell dahinter enthält aber eine Vereinfachung, die das Risiko unterschätzt, und zwar umso stärker, je länger man wartet.
Dieser Beitrag behandelt ein Wahrscheinlichkeitsmodell. Er sagt nichts darüber, ob man Bitcoin benutzen oder kaufen sollte.
Das Modell: ein Wettrennen zweier Ketten
Der Angreifer kontrolliert den Anteil der gesamten Rechenleistung, die ehrlichen Miner den Anteil . Blöcke entstehen durch unabhängige Hash-Versuche, die Zeit bis zum nächsten Block ist daher gedächtnislos, und die Blöcke jeder Seite bilden einen Poisson-Prozess. Daraus folgt eine einfache Beschreibung: Jeder neu gefundene Block, egal auf welcher Seite, stammt mit Wahrscheinlichkeit vom Angreifer und mit Wahrscheinlichkeit von den ehrlichen Minern, unabhängig von allen früheren.
Der Rückstand des Angreifers macht also eine Irrfahrt: Er wächst mit Wahrscheinlichkeit um eins und schrumpft mit Wahrscheinlichkeit um eins. Das Whitepaper nennt das eine binomiale Irrfahrt und zerlegt den Angriff in zwei Phasen:
- Der Händler wartet, bis seine Transaktion in einem Block steht und Blöcke darauf gefolgt sind. Währenddessen arbeitet der Angreifer heimlich an seiner Kette und schafft dabei eine zufällige Zahl von Blöcken.
- Danach muss der Angreifer den verbleibenden Rückstand aufholen.
Phase 2: Aufholen aus z Blöcken Rückstand
Sei die Wahrscheinlichkeit, einen Rückstand von Blöcken jemals aufzuholen. Um Blöcke aufzuholen, muss man zuerst einen aufholen, dann den nächsten, und so weiter. Weil die Irrfahrt kein Gedächtnis hat, sind das unabhängige Teilstrecken mit derselben Erfolgswahrscheinlichkeit, also .
Für betrachtet man den ersten Block. Mit Wahrscheinlichkeit ist er vom Angreifer, und der Rückstand ist weg. Mit Wahrscheinlichkeit ist er ehrlich, und der Rückstand beträgt jetzt zwei:
Diese quadratische Gleichung hat die Lösungen und . Ist , driftet der Rückstand nach dem Gesetz der großen Zahlen gegen unendlich, die Aufholwahrscheinlichkeit kann also nicht 1 sein. Es bleibt und
und für . Das ist das klassische Ruinproblem des Spielers, die Formel steht genau so im Whitepaper. Für gewinnt der Angreifer also mit Sicherheit, egal wie lange der Händler wartet. Das ist der „51-Prozent-Angriff“.
Phase 1: Was der Angreifer in der Wartezeit schafft
Während die ehrlichen Miner Blöcke finden, findet der Angreifer durchschnittlich Blöcke. Das Whitepaper nimmt an, dass die ehrlichen Blöcke genau in der erwarteten Zeit kommen. Dann ist die Zahl der Angreiferblöcke Poisson-verteilt mit Erwartungswert
Für jedes mögliche multipliziert man die Poisson-Wahrscheinlichkeit mit der Wahrscheinlichkeit, den Rest aufzuholen. Hat der Angreifer schon mehr als Blöcke, ist er vorn, und diese Wahrscheinlichkeit ist 1. Das Minimum fasst beide Fälle zusammen:
Weil die Wahrscheinlichkeiten aller zusammen 1 ergeben, lässt sich das ohne unendliche Summe schreiben:
Diese zweite Form übersetzt das Whitepaper in eine kurze C-Funktion.
Nachgerechnet
Dieselbe Rechnung in Python, Zeile für Zeile wie die C-Funktion:
from math import exp
def nakamoto(q: float, z: int) -> float:
p = 1.0 - q
lam = z * (q / p)
total = 1.0
for k in range(z + 1):
poisson = exp(-lam)
for i in range(1, k + 1):
poisson *= lam / i
total -= poisson * (1 - (q / p) ** (z - k))
return total
print(f"{nakamoto(0.1, 6):.7f}") # 0.0002428
Auf sieben Nachkommastellen gerundet stimmen alle 22 Werte der beiden Tabellen im Whitepaper ( für bis und für ) mit dieser Funktion überein. Auch die dritte Tabelle, die für jedes das kleinste mit angibt, ergibt sich genau so: 5, 8, 11, 15, 24, 41, 89 und 340 Bestätigungen für bis .1
An der Arithmetik ist also nichts auszusetzen. Das Problem liegt eine Ebene tiefer.
Wo die Intuition täuscht: Die Wartezeit ist selbst zufällig
Die Annahme, dass die ehrlichen Blöcke genau in der erwarteten Zeit kommen, klingt harmlos, weil sie im Mittel stimmt. Sie stimmt aber nur im Mittel. Brauchen die ehrlichen Miner zufällig länger, hat der Angreifer mehr Zeit. Gehen sie schneller, hat er weniger. Diese Schwankung gleicht sich im Ergebnis nicht aus: Jeder zusätzliche Angreiferblock multipliziert die Aufholwahrscheinlichkeit mit , also bei mit 9. Eine lange Wartezeit hilft dem Angreifer deshalb mehr, als eine kurze ihm schadet. Die Ausnahme ist der Bereich, in dem er ohnehin vorn liegt: Mehr als Gewissheit gibt es nicht, und dort kehrt sich der Effekt um.
Ohne die Annahme ist die Rechnung sogar einfacher. Man zählt in der Blockfolge, in der jeder Block unabhängig mit Wahrscheinlichkeit dem Angreifer gehört, wie viele Angreiferblöcke vor dem -ten ehrlichen Block liegen. Das ist die negative Binomialverteilung:
Man erhält sie auch, wenn man im Poisson-Modell die Wartezeit nicht festhält, sondern als Gamma-verteilte Zufallsgröße einsetzt. Mit dieser Verteilung und derselben Aufholformel ergibt sich für
Diese Formel hat Meni Rosenfeld 2014 veröffentlicht. Cyril Grunspan und Ricardo Pérez-Marco haben 2017 gezeigt, dass sie eine geschlossene Form hat, die regularisierte unvollständige Betafunktion:
Beide Ausdrücke und die direkte Summe über die negative Binomialverteilung stimmen für alle 20 nachgerechneten Kombinationen von und überein, die Summen exakt, die Betafunktion bis auf den Fehler der numerischen Integration.
Der Unterschied in Zahlen
| q | z | Whitepaper | exakt | Faktor |
|---|---|---|---|---|
| 0,1 | 1 | 0,2045873 | 0,2000000 | 0,98 |
| 0,1 | 2 | 0,0509779 | 0,0560000 | 1,10 |
| 0,1 | 6 | 0,0002428 | 0,0005914 | 2,44 |
| 0,1 | 10 | 0,0000012 | 0,0000079 | 6,33 |
| 0,3 | 5 | 0,1773523 | 0,1976173 | 1,11 |
| 0,3 | 10 | 0,0416605 | 0,0651067 | 1,56 |
| 0,3 | 24 | 0,0008106 | 0,0040007 | 4,94 |
Nur bei einer einzigen Bestätigung liegt das Whitepaper über dem exakten Wert, das ist der eben beschriebene Bereich. Ab zwei Bestätigungen unterschätzt es das Risiko, und der Faktor wächst mit . Bei und den 24 Bestätigungen, die das Whitepaper für weniger als 0,1 % empfiehlt, liegt das tatsächliche Risiko bei 0,4 %.
Der Grund für den wachsenden Faktor ist die Abklingrate. Grunspan und Pérez-Marco geben die Asymptotik beider Formeln an: Der exakte Wert fällt wie (bis auf einen Faktor der Größenordnung ), der Whitepaper-Wert wie mit und . Für heißt das: Jede weitere Bestätigung multipliziert das exakte Risiko ungefähr mit 0,36, das Whitepaper-Risiko mit 0,27.
Die Tabelle der nötigen Bestätigungen für verschiebt sich entsprechend:
| q | Whitepaper | exakt |
|---|---|---|
| 0,10 | 5 | 6 |
| 0,15 | 8 | 9 |
| 0,20 | 11 | 13 |
| 0,25 | 15 | 20 |
| 0,30 | 24 | 32 |
| 0,35 | 41 | 58 |
| 0,40 | 89 | 133 |
| 0,45 | 340 | 539 |
Die bekannte Faustregel von sechs Bestätigungen ist keine Protokollregel. Das Bitcoin-Wiki führt sie auf zwei willkürliche Annahmen zurück: höchstens 10 % Rechenleistung beim Angreifer und weniger als 0,1 % Restrisiko. Nach der Formel des Whitepapers würden dafür fünf Bestätigungen reichen, nach der exakten Rechnung sind es genau sechs.
Gegenprobe durch Simulation
Zwei Formeln, die sich widersprechen, kann man durch ein Experiment entscheiden. Die Simulation spielt das Rennen direkt nach: Blöcke ziehen, bis die ehrliche Kette Blöcke hat, dann die Irrfahrt laufen lassen, bis der Angreifer aufgeholt hat oder 80 Blöcke zurückliegt. Bei 80 Blöcken Rückstand ist die Aufholwahrscheinlichkeit für kleiner als , der Abbruch verfälscht also nichts Messbares.
import random
def simulate(q: float, z: int, trials: int, rng: random.Random) -> float:
wins = 0
for _ in range(trials):
honest = attacker = 0
while honest < z: # Phase 1
if rng.random() < q:
attacker += 1
else:
honest += 1
deficit = z - attacker
while 0 < deficit < 80: # Phase 2
deficit += -1 if rng.random() < q else 1
wins += deficit <= 0
return wins / trials
rng = random.Random(20261029)
print(simulate(0.3, 5, 200_000, rng)) # 0.1979
print(simulate(0.1, 6, 1_000_000, rng)) # 0.000606
Für , ergeben 200 000 Rennen 0,1979. Das exakte Modell sagt 0,1976, das Whitepaper 0,1774. Für , ergibt eine Million Rennen 0,000606, gegenüber 0,000591 exakt und 0,000243 im Whitepaper. Die Abweichung vom exakten Wert liegt in beiden Fällen innerhalb der statistischen Schwankung, die vom Whitepaper-Wert weit außerhalb.
Was das Modell nicht abbildet
Auch die korrigierte Formel ist ein Modell mit Annahmen, die man kennen sollte, bevor man aus ihr eine Wartezeit ableitet.
- Kein Vorsprung beim Start. Beide Rechnungen nehmen an, dass der Angreifer erst in dem Moment zu minen beginnt, in dem er bezahlt. Das Whitepaper begründet das damit, dass der Empfänger sein Schlüsselpaar erst kurz vor der Zahlung erzeugt. Kann der Angreifer den Zeitpunkt frei wählen und vorab einen Block Vorsprung sammeln, steigt seine Chance.
- Konstante Anteile. ist als fest angenommen. In der Realität lässt sich Rechenleistung mieten, und niemand kann direkt beobachten. Die Rechnung liefert für ein angenommenes eine Wahrscheinlichkeit, nicht für den tatsächlichen Angreifer.
- Keine Netzwerklaufzeiten. Blöcke verbreiten sich nicht sofort. Verwaiste Blöcke der ehrlichen Seite verschenken Rechenleistung, die im Modell als voll wirksam zählt.
- Ehrliche Miner bleiben ehrlich. Eyal und Sirer haben 2013 gezeigt, dass ein Miner mit genügend Rechenleistung mehr verdienen kann, wenn er Blöcke zurückhält (Selfish Mining). Wer so vorgeht, verhält sich weder wie die ehrliche Seite noch wie der Angreifer in diesem Modell.
- Ein Versuch, keine Kosten. Die Formel gibt die Erfolgswahrscheinlichkeit eines einzelnen Versuchs an. Ob sich ein Angriff lohnt, hängt zusätzlich vom Betrag, von den Kosten der Rechenleistung und von der Zahl der Versuche ab. Rosenfeld behandelt diese Fragen im selben Aufsatz.
Für die eigentliche Frage des Abschnitts heißt das: Die Tabellen des Whitepapers sind korrekt gerechnet, aber zu optimistisch. Wer aus ihnen eine Zahl von Bestätigungen ableitet, sollte die exakte Formel verwenden, sie ist nicht komplizierter.
Weiterführende Quellen
- Satoshi Nakamoto: Bitcoin: A Peer-to-Peer Electronic Cash System, 2008. Abschnitt 11 „Calculations“, S. 6–8.
- Meni Rosenfeld: Analysis of Hashrate-Based Double Spending, 2014. Gleichung (1) und Tabelle 1.
- Cyril Grunspan, Ricardo Pérez-Marco: Double spend races, International Journal of Theoretical and Applied Finance 21(8), 2018. Satz 1 (geschlossene Form), Satz 2 (Asymptotik), Tabelle 1.
- Ittay Eyal, Emin Gün Sirer: Majority is not Enough: Bitcoin Mining is Vulnerable, 2013.
- William Feller: An Introduction to Probability Theory and Its Applications, Band 1, 3. Auflage, Wiley 1968. Kapitel XIV (Irrfahrten und Ruinprobleme).
- Bitcoin-Wiki: Confirmation, zur Herkunft der sechs Bestätigungen.
- Alle Zahlen dieses Beitrags erzeugt
tests/articles/double_spend.pyim Repository dieser Seite, die Grafiktests/articles/double_spend_svg.py.
Fußnoten
-
In Tabelle 1 bei Grunspan und Pérez-Marco steht in der Zeile mit Nakamotos Werten für die Zahl 81. Die Formel des Whitepapers ergibt 89, wie dort gedruckt: Bei liegt sie noch bei 0,18 %. ↩