Das Double-Spending-Problem und die byzantinischen Generäle

Neugier

1. Wenn sich eine digitale Datei perfekt und sofort kopieren lässt, was verhindert dann, dass sie zweimal ausgegeben wird?
2. Wie kann sich eine Gruppe von Fremden ohne gemeinsame Identität auf eine einzige Historie einigen, ohne einen Anführer, der Streitigkeiten schlichtet?
3. Was macht eine Abstimmung in einem offenen Netzwerk wertvoller als das Wort einer anderen Person?

Erkunden

1. Ein digitales Token ist lediglich eine Datei. Anders als physisches Bargeld lässt es sich kostenlos und verlustfrei Bit für Bit duplizieren. Sendet Alice zehn Einheiten an Bob, behält sie die Originaldatei und kann dieselben zehn Einheiten gleichzeitig an Charlie senden. Bis 2008 war jedes funktionierende digitale Bargeldsystem auf einen vertrauenswürdigen Emittenten angewiesen: Online-Systeme prüften jede Zahlung zentral, Offline-Systeme konnten Double Spender erst im Nachhinein identifizieren.
2. Bei David Chaums DigiCash zahlte jeder Zahlungsempfänger die Münzen bei der Bank ein, die jede Seriennummer mit ihrer Liste bereits ausgegebener Münzen abglich. Hal Finneys Reusable Proofs of Work stützte sich auf einen einzigen Server, der Open-Source-Code auf sicherer Hardware ausführte, um ausgegebene Token zu erfassen. Wei Dais b-money sah Server vor, die Sicherheiten hinterlegten und bei Betrug bestraft werden konnten, wurde aber nie gebaut. Jeder dieser Entwürfe hatte eine vertrauenswürdige Partei oder eine bekannte Gruppe im Zentrum.
3. 1982 formalisierten Leslie Lamport, Robert Shostak und Marshall Pease das Problem der byzantinischen Generäle in den ACM Transactions on Programming Languages and Systems. Generäle, die eine Stadt umstellt haben, müssen sich auf Angriff oder Rückzug einigen, doch einige von ihnen sind Verräter, die widersprüchliche Nachrichten senden; die Boten selbst sind zuverlässig. Mit unsignierten Nachrichten ist eine Einigung nur möglich, wenn weniger als ein Drittel der Generäle Verräter sind (n ≥ 3f+1); bei einem Drittel oder mehr kann kein Protokoll sie garantieren.
4. Klassische fehlertolerante Protokolle wie PBFT erfordern eine bekannte, feste Menge von Teilnehmern. Das funktioniert bei internen Ledgern von Banken, scheitert aber in offenen Netzwerken, denen jeder beitreten kann. John Douceur beschrieb 2002 den Sybil-Angriff: Ein Angreifer kann unbegrenzt viele falsche Identitäten erzeugen, um ehrliche Stimmen zu verwässern oder Quoren zu kontrollieren. In einem offenen Peer-to-Peer-Netzwerk sind Identitäten billig und unbegrenzt verfügbar, sodass jedes Verfahren, das Identitäten zählt, von einem einzigen Akteur übernommen werden kann.
5. Satoshi Nakamotos Whitepaper ging genau dieses Problem an. Sein Abstract stellt Bitcoin als Lösung für Double Spending ohne vertrauenswürdige dritte Partei vor. Statt auf Identität oder institutionelles Vertrauen zu setzen, bindet das System jeden Block an einen kumulierten Proof of Work. Stimmen werden nach Rechenaufwand gewichtet, der sich nicht durch das Erfinden von Identitäten vervielfachen lässt; ein Angreifer muss das ehrliche Netzwerk an Rechenleistung übertreffen, um die Historie umzuschreiben.
6. Das Ergebnis ist probabilistische Finalität. Eine Transaktion ist im mathematischen Sinne nie endgültig, wird aber mit jedem neuen Block, der die Chain verlängert, sicherer. Solange ein Angreifer weniger als die Hälfte der Hashrate kontrolliert, sinkt die Wahrscheinlichkeit einer Rückabwicklung mit jeder Bestätigung exponentiell. Dieser Kompromiss nimmt die theoretische Möglichkeit einer Rückabwicklung in Kauf, um ohne zentrale Kontrolle praktische Unveränderlichkeit zu erreichen. Öffnen Sie einen Block-Explorer und beobachten Sie, wie die kumulierte Arbeit mit jeder Blockhöhe wächst; diese sich aufsummierenden Kosten verankern das Ledger in der physischen Realität.

Kernfakten

Übung neun, sechs, drei, eins

Faktcheck

Datumsangaben, Zahlen und Behauptungen wurden mit den unten aufgeführten veröffentlichten Quellen abgeglichen.

• L. Lamport, R. Shostak, M. Pease, 'The Byzantine Generals Problem', ACM TOPLAS (1982)
• J. Douceur, 'The Sybil Attack', Peer-to-Peer Systems (2002)
• S. Nakamoto, 'Bitcoin: A Peer-to-Peer Electronic Cash System' (2008)
• M. Castro & B. Liskov, 'Practical Byzantine Fault Tolerance', OSDI (1999)