Bitcoin Selfish Mining und Dyck-Wörter: Ein kombinatorischer Beweis

Inhaltsverzeichnis

1. Einleitung

Selfish Mining (SM) ist eine Block-Vorenthaltungsstrategie in Bitcoin, die einen Fehler im Schwierigkeitsanpassungsmechanismus des Protokolls ausnutzt. Im Gegensatz zu ehrlichen Minern, die stets die öffentlich längste Kette erweitern, hält ein eigennütziger Miner neu geminte Blöcke zurück, um einen geheimen Fork zu erzeugen, und gibt sie strategisch frei, um seinen Ertrag zu maximieren. Die zentrale Kennzahl zur Bewertung solcher Strategien ist die langfristige scheinbare Hashrate $\tilde{q}$, die den Anteil der Blöcke in der offiziellen Blockchain darstellt, die im Laufe der Zeit vom Angreifer beigesteuert werden.

Frühere Analysen stützten sich auf komplexe Markov-Ketten oder Martingal-Techniken. Diese Arbeit präsentiert einen einfachen kombinatorischen Beweis unter Verwendung von Dyck-Wörtern und Catalan-Zahlen, wodurch die Herleitung zugänglicher und eleganter wird.

2. Angriffszyklus und Dyck-Wörter

Ein Angriffszyklus kann als eine Sequenz von Ereignissen modelliert werden, bei der jeder Block entweder vom Selfish Miner (S) oder von den ehrlichen Minern (H) gemint wird.

2.1. Sequenzdarstellung

Beispiel: Die Sequenz SSSHSHH zeigt an, dass der eigennützige Miner drei Blöcke mint, dann die ehrlichen Miner einen, dann der eigennützige einen, dann die ehrlichen zwei. Der Zyklus endet, wenn der Vorsprung des eigennützigen Miners schrumpft, was ihn dazu veranlasst, seinen Fork zu veröffentlichen.

2.2. Verteilung von L

Sei $L$ die Anzahl der Blöcke, die pro Angriffszyklus zur offiziellen Blockchain hinzugefügt werden.

Satz 2.2: $P[L=1] = p$, $P[L=2] = pq + pq^2$, und für $n \geq 3$, $P[L=n] = p q^2 (pq)^{n-2} C_{n-2}$ wobei $C_n = \frac{(2n)!}{n!(n+1)!}$ die $n$-te Catalan-Zahl ist.

Beweisskizze: Für $n \geq 3$ entspricht das Ereignis ${L=n}$ Sequenzen, die mit SS beginnen, mit H enden und bei denen der mittlere Teil, bei der Abbildung S→"(" und H→")", ein Dyck-Wort (eine ausgeglichene Klammerfolge) der Länge $2(n-2)$ bildet. Die Catalan-Zahl $C_{n-2}$ zählt solche Dyck-Wörter.

3. Zentrale mathematische Ergebnisse

3.1. Erwartungswert von L

Korollar 2.3: $E[L] = 1 + \frac{p^2 q}{p - q}$.

Dies folgt aus bekannten erzeugenden Funktionsrelationen für Catalan-Zahlen.

3.2. Formel für die scheinbare Hashrate

Sei $Z$ die Anzahl der Blöcke, die der Angreifer pro Zyklus zur offiziellen Kette hinzufügt. Die langfristige scheinbare Hashrate ist $\tilde{q} = E[Z] / E[L]$.

Satz 2.4: Die scheinbare Hashrate für Bitcoin ist: $$\tilde{q}_B = \frac{[(p-q)(1+pq)+pq]q - (p-q)p^2q(1-\gamma)}{pq^2 + p - q}$$ wobei $p$ die Hashrate der ehrlichen Miner, $q$ die Hashrate des Angreifers ist ($p+q=1$, $q<1/2$) und $\gamma$ der Anteil der ehrlichen Miner ist, die während eines Forks auf dem Block des Angreifers minen.

4. Technische Analyse & Rahmenwerk

4.1. Mathematisches Rahmenwerk

Die zentrale Innovation ist die Abbildung von Angriffssequenzen auf Dyck-Pfade (ausgeglichene Klammerfolgen). Dies verbindet Selfish Mining mit etablierter Kombinatorik und vereinfacht Wahrscheinlichkeitsberechnungen, die zuvor stochastische Prozesse erforderten.

Wichtige Formel: Die Wahrscheinlichkeit $P[L=n]$ für $n\geq3$ ist direkt proportional zur Catalan-Zahl $C_{n-2}$, skaliert mit den Wahrscheinlichkeitsgewichten $p$ und $q$: $P[L=n] = p q^2 (pq)^{n-2} C_{n-2}$.

4.2. Beispiel für das analytische Rahmenwerk

Fallanalyse für L=4:

1. Die Sequenz muss mit SS beginnen und mit H enden.
2. Die mittleren zwei Positionen müssen ein Dyck-Wort der Länge 2 bilden: nur SH oder HS? Überprüfen wir: Für L=4 ist n=4, also n-2=2. Wir brauchen Dyck-Wörter der Länge 2*(2)=4 Zeichen in der Mitte? Vorsicht: Der Satz besagt für n≥3, dass P[L=n] Sequenzen der Form w = SS X1...X_{2(n-2)} H entspricht, wobei die X's ein Dyck-Wort der Länge 2(n-2) bilden. Für n=4 ist die Länge 2*(4-2)=4. Der mittlere Teil hat also 4 Zeichen, die ein Dyck-Wort bilden. Beispiel: SS(SHSH)H? Abbildung S→(, H→). Der mittlere Teil "SHSH" wird zu "()()", was ein Dyck-Wort ist. Das Wahrscheinlichkeitsgewicht ist p^{#S} q^{#H} = p^3 q^3? Zählen wir S und H in w=SS S H S H H: S erscheint 4 Mal? Tatsächlich: SS S H S H H: Positionen: S,S,S,H,S,H,H. Das sind 4 S und 3 H. Also p^4 q^3. Die Formel ergibt p q^2 (pq)^{2} C_2 = p q^2 * p^2 q^2 * 2 = 2 p^3 q^4. Hier gibt es eine Diskrepanz. Das PDF sagt: "Die Anzahl der Buchstaben 'S' (bzw. 'H') in w ist n (bzw. n-1). Also erhalten wir P[L=n] = p^{n-1} q^n C_{n-2}". Für n=4 ist das p^3 q^4 C_2 = p^3 q^4 * 2 = 2 p^3 q^4. Dies stimmt mit der Formel überein. Die Beispielsequenz SS S H S H H hat also 4 S und 3 H, was p^4 q^3 ergibt, nicht p^3 q^4. Daher ist SS S H S H H unter der Dyck-Wort-Bedingung keine gültige Sequenz für L=4? Sie ist möglicherweise nicht ausgeglichen. Abbilden: S→(, H→). SS S H S H H wird zu ((( ) ( ) ). Das ist nicht ausgeglichen (drei öffnende, zwei schließende). Tatsächlich sind die gültigen Sequenzen diejenigen, bei denen die Gesamtanzahl von S gleich n und von H gleich n-1 ist, UND der mittlere Teil ein Dyck-Wort ist. Die Dyck-Bedingung erzwingt die Ausgeglichenheit und führt zur spezifischen Zählung. Das Rahmenwerk erfasst also elegant die gültigen Angriffspfade.

Dieses Rahmenwerk ermöglicht eine systematische Aufzählung und Wahrscheinlichkeitsberechnung ohne Simulation von Markov-Ketten.

5. Ergebnisse & Implikationen

Die abgeleitete Formel für $\tilde{q}_B$ quantifiziert die Profitabilitätsschwelle für Selfish Mining. Zum Beispiel benötigt der Angreifer bei $\gamma=0$ $q > \approx 0.25$, um profitabel zu sein, was niedriger ist als die naive Annahme $q>0.5$. Dies verdeutlicht eine kritische Protokollschwachstelle.

Diagrammbeschreibung: Ein Plot von $\tilde{q}_B$ gegen $q$ für verschiedene $\gamma$-Werte würde zeigen: 1) $\tilde{q}_B > q$ für $q$ oberhalb einer Schwelle, was Profitabilität anzeigt. 2) Höheres $\gamma$ (bessere Konnektivität für den Angreifer) senkt die Profitabilitätsschwelle und erhöht den Gewinn an scheinbarer Hashrate.

6. Perspektive eines Branchenanalysten

Kernaussage: Die Eleganz der Arbeit liegt in der Reduktion eines komplexen, zustandsbehafteten Angriffs auf ein sauberes kombinatorisches Modell. Es zeigt, dass die Profitabilität von Selfish Mining nicht nur von der rohen Hashrate abhängt, sondern von der strukturellen Kopplung zwischen Angriffssequenzen und kanonischen kombinatorischen Objekten (Dyck-Wörtern). Dies ist nicht nur ein mathematischer Trick; es offenbart die Schwachstelle des Bitcoin-Protokolls als ein formales Sprachproblem – seine Sicherheit hängt von der Wahrscheinlichkeitsverteilung bestimmter Zeichenkettenmuster im Blockwettlauf ab.

Logischer Ablauf: Die Autoren beginnen damit, den Angriffszyklus als Zeichenkette (S/H-Sequenz) zu beschreiben. Der entscheidende Schritt ist die Erkenntnis, dass erfolgreiche Angriffe (bei denen alle Blöcke des Angreifers akzeptiert werden) Zeichenketten entsprechen, die im Wesentlichen Dyck-Wörter sind, die von spezifischen Start-/Endzeichen umschlossen sind. Dies ermöglicht es ihnen, direkt auf den umfangreichen Apparat der Catalan-Kombinatorik für Zählung und Wahrscheinlichkeitserzeugung zurückzugreifen und so das Lösen von Gleichgewichtsgleichungen für eine Markov-Kette zu umgehen. Die endgültige Formel wird abgeleitet, indem der Erwartungswert von L (über erzeugende Funktionen für Catalan-Zahlen) und der Erwartungswert von Z (unter Berücksichtigung von Randfällen wie L=1,2) verbunden werden.

Stärken & Schwächen:
Stärken: Der Beweis ist bemerkenswert prägnant und zugänglich. Er entmystifiziert die Ertragsformel für Selfish Mining. Die Verknüpfung mit Dyck-Wörtern könnte neue Analysen anderer Blockchain-Angriffe (z.B. Balancing-Angriffe, Eclipse-Angriffe) mithilfe der formalen Sprachtheorie inspirieren. Sie unterstreicht den Wert interdisziplinärer Ansätze (Krypto + Kombinatorik).
Schwächen: Das Modell geht von einem statischen, beständigen Angreifer mit konstantem q aus. Es erfasst keine dynamische Anpassung, Ein- oder Austritt von Minern oder die Auswirkungen mehrerer eigennütziger Miner (ein potenzielles Oligopol-Problem). Der Parameter $\gamma$ ist vereinfachend; die reale Netzwerktopologie und Propagierungsverzögerungen sind komplexer. Wie in Folgearbeiten wie "Optimal Selfish Mining Strategies in Bitcoin" (Gervais et al., Financial Crypto 2016) festgestellt, ist die ursprüngliche Selfish-Mining-Strategie nicht immer optimal; es gibt adaptivere Strategien. Der Beitrag dieser Arbeit ist grundlegend, nicht erschöpfend.

Umsetzbare Erkenntnisse:

1. Für Protokolldesigner: Die Ursache liegt in der "First-Seen"-Regel und der langsamen Blockverbreitung. Lösungen wie Gervais' "Freshness Preferred" oder Decker und Wattenhofers "Compact Block Relay" (wie in Bitcoin Core implementiert) zielen darauf ab, $\gamma$ und die Propagierungsvarianz zu reduzieren. Die Formel dieser Arbeit liefert eine quantifizierbare Metrik, um solche Korrekturen zu testen.
2. Für Mining-Pools: Die Schwellenwertberechnung ($q$ ~0,25) ist eine rote Linie. Pools, die diese Größe erreichen, sollten genau beobachtet werden. Dezentralisierung ist nicht nur ideologisch; sie ist ein Sicherheitsparameter in der $\tilde{q}$-Formel.
3. Für Analysten: Die Dyck-Wort-Abbildung ist eine leistungsstarke Vorlage. Suchen Sie nach anderen Konsensmechanismen, bei denen die Aktionen der Teilnehmer Sequenzen erzeugen, die durch formale Sprachklassen (regulär, kontextfrei) analysierbar sind. Proof-of-Stake-Systeme mit ihren expliziten Abstimmungssequenzen könnten reif für ähnliche Analysen sein.

Fazit: Blockchain-Sicherheit wird zunehmend ein Feld für angewandte Mathematiker und Linguisten, nicht nur für Kryptographen. Diese Arbeit ist ein Paradebeispiel für diesen Wandel.

7. Zukünftige Anwendungen & Richtungen

1. Erweiterte Angriffsmodelle: Das Dyck-Wort-Rahmenwerk kann angepasst werden, um Varianten wie Stubborn Mining oder Trail Mining zu analysieren, bei denen die Veröffentlichungsstrategie des Angreifers abweicht.

2. Andere Konsensprotokolle: Die Anwendung ähnlicher kombinatorischer Methoden auf Proof-of-Stake (z.B. Ethereums Casper) oder DAG-basierte Protokolle (z.B. IOTA, Avalanche) könnte neue Erkenntnisse über deren Widerstandsfähigkeit gegen Vorenthaltungsangriffe liefern.

3. Automatisierte Sicherheitsverifikation: Es könnten Werkzeuge entwickelt werden, um die Regeln eines Konsensprotokolls automatisch in eine formale Grammatik zu übersetzen und auf die Existenz von "profitablen Angriffsgrammatiken" zu prüfen, analog zur hier gefundenen Dyck-Struktur.

4. Integration von Netzwerkdynamiken: Zukünftige Arbeiten könnten realistischere Netzwerkmodelle (z.B. unter Verwendung von Epidemiemodellen für die Blockverbreitung) in die kombinatorischen Wahrscheinlichkeitsgewichte integrieren und so über den einfachen $\gamma$-Parameter hinausgehen.

8. Referenzen

1. Eyal, I., & Sirer, E. G. (2014). Majority is not enough: Bitcoin mining is vulnerable. In Financial Cryptography and Data Security (pp. 436-454). Springer.
2. Stanley, R. P. (2015). Catalan Numbers. Cambridge University Press.
3. Nakamoto, S. (2008). Bitcoin: A peer-to-peer electronic cash system.
4. Grunspan, C., & Pérez-Marco, R. (2018). On profitability of selfish mining. arXiv preprint arXiv:1805.08281.
5. Gervais, A., Karame, G. O., Wüst, K., Glykantzis, V., Ritzdorf, H., & Capkun, S. (2016). On the security and performance of proof of work blockchains. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (pp. 3-16).
6. Bitcoin Wiki. Difficulty. https://en.bitcoin.it/wiki/Difficulty.
7. Decker, C., & Wattenhofer, R. (2013). Information propagation in the Bitcoin network. In IEEE P2P 2013 Proceedings (pp. 1-10). IEEE.