Strategies for quantum-enabled Bitcoin miners

Technische Zusammenfassung: Strategien für quantengestützte Bitcoin-Miner

Problemstellung
Die Sicherheit des Bitcoin-Netzwerks beruht auf der Annahme, dass die Ausführung eines „51 %-Angriffs“ – bei dem ein Konsortium die Mehrheit der Rechenleistung des Netzwerks kontrolliert, um Double-Spending zu betreiben oder Transaktionen rückgängig zu machen – prohibitiv teuer ist. Während frühere Arbeiten theoretisch nahelegten, dass der Grover-Algorithmus die Kosten eines solchen Angriffs senken könnte, indem er eine quadratische Beschleunigung bei der Lösung des Proof-of-Work (PoW)-Problems bietet, stützten sich diese Studien oft auf enge Adversarial-Modelle. Speziell beschränkten vorangegangene Modelle Quanten-Miner auf eine einzige Quantenmessung pro Mining-Rennen und eine „friedliche“ Strategie (Verwerfen der Suche bei Bekanntgabe eines neuen Blocks). Diese Arbeit adressiert die Lücke, indem sie die Auswirkungen von zwei nicht kolludierenden, aggressiven Quanten-Minern auf die 51 %-Angriffsschwelle innerhalb eines realistischeren Adversarial-Modells untersucht. Der Kern der Problemstellung besteht darin, die optimalen Quanten-Mining-Strategien für zwei konkurrierende Miner zu bestimmen, die mehrere Quantenmessungen durchführen können und Sattaths aggressive Quanten-Mining-Strategie (AQMS) nutzen können, sowie die resultierende Auswirkung auf die Stale-Rate ($p_{stale}$) und die effektive 51 %-Angriffsschwelle zu quantifizieren.

Methodik
Die Autoren erweitern das spieltheoretische Framework der Symmetric Two-Player Quantum Races (S2QR), um den Wettbewerb zwischen zwei Quanten-Minern, Alice und Bob, innerhalb eines ansonsten klassischen Bitcoin-Netzwerks zu modellieren.

1. Modellerweiterungen:

   • Multiple Messungen: Im Gegensatz zu früheren Modellen, die eine einzige Messung voraussetzen, erlaubt dieses Modell den Minern, $c$ Quantenmessungen zwischen aufeinanderfolgenden Blöcken durchzuführen.
   • Aggressive Strategie: Das Modell integriert Sattaths AQMS, bei der Miner ihre Suche abbrechen und sofort messen, sobald die Broadcast-Meldung eines neuen Blocks eingeht, anstatt ihre Rechenleistung zu verwerfen. Diese Strategie erhöht die Korrelation zwischen Messzeitpunkten und Blockfindung, was potenziell die Stale-Rate erhöht.
   • Ressourcenbeschränkungen: Miner operieren unter einem kumulativen Grover-Iteration-Budget $\kappa$, das auf $c$ Messungen verteilt ist. Der Strategieraum umfasst die Allokation dieser Iterationen, um die Wahrscheinlichkeit zu maximieren, der Erste zu sein, der einen gültigen Block findet.

2. Spieltheoretische Formulierung:

   • Der Wettbewerb wird als strategisches Spiel modelliert, in dem Alice und Bob reine Strategien wählen (Vektoren von Grover-Iterationen für jede ihrer $c$ Messungen).
   • Payoff-Matrizen: Die Autoren leiten geschlossene Ausdrücke für die Payoff-Matrizen ($A$ und $B$) für beide Spieler ab. Diese Matrizen berücksichtigen:
     • Die Erfolgswahrscheinlichkeit des Finite-Budget Quantum Search (FQS) Algorithmus basierend auf der Anzahl der Grover-Iterationen.
     • Die additive Struktur der Payoffs über mehrere Messungen hinweg.
     • Die durch AQMS eingeführten Terme, welche die Payoffs modifizieren, wenn ein Miner misst, nachdem ein Gegner bereits eine Lösung gefunden hat (oder wenn Messungen gleichzeitig erfolgen).
   • Berechnung des Gleichgewichts: Optimale Strategien werden als Nash-Gleichgewichte identifiziert. Aufgrund der kombinatorischen Explosion des Strategieraums (mit wachsendem $c$) verwenden die Autoren eine Heuristik, um den reinen Strategieraum zu sampeln, und nutzen den Lemke-Howson-Algorithmus, um exakte Nash-Gleichgewichte zu berechnen.

3. Simulation:

   • Um die Sicherheitsauswirkungen zu evaluieren, führen die Autoren Monte-Carlo-Simulationen (1.000.000 Tage) unter Verwendung der berechneten Nash-Gleichgewichte durch.
   • Die Simulationen verfolgen die Stale-Rate ($p_{stale}$), definiert als das Verhältnis von Blöcken außerhalb der längsten Kette zur Gesamtzahl der Blöcke.
   • Die Studie bewertet, ob $p_{stale}$ den kritischen Schwellenwert von $1/3$ überschreitet, was die effektive 51 %-Angriffsschwelle auf 40 % oder darunter senken würde.
   • Simulationen werden über drei Netzwerk-Difficulty-Regime durchgeführt: Niedrig ($D \le 2^{32}$), Hoch ($D > 2^{32}$, reflektierend aktuelle und projizierte Schwierigkeiten) und Ideal (wo der Quanten-Oracle den gesamten Block-Header kodiert).

Wesentliche Beiträge

• Einbeziehung neuartiger Strategien: Die Arbeit führt die „Aggressive Quantum Mining Strategy“ (AQMS) in ein spieltheoretisches Framework ein und analysiert deren Auswirkungen neben multiplen Quantenmessungen.
• Generalisierte Payoff-Matrizen: Die Autoren leiten die mathematische Struktur der Payoff-Matrizen für $c$ Quantenmessungen ab und erweitern das S2QR-Modell, um die kumulative Natur mehrerer Versuche und die durch AQMS induzierten spezifischen Zeitkorrelationen zu handhaben.
• Berechnung optimaler Strategien: Die Studie berechnet optimale Quanten-Mining-Strategien (Nash-Gleichgewichte) für $c \in \{1, 2, 3, 4\}$ über verschiedene Difficulty-Regime hinweg und zeigt auf, wie Miner ihre Grover-Iteration-Budgets allokieren sollten.
• Quantifizierung der Sicherheit: Die Arbeit liefert eine quantitative Bewertung der 5-1 %-Angriffsschwelle unter diesen optimalen Strategien und geht über rein theoretische Möglichkeiten hinaus zu simulierten Ergebnissen.

Ergebnisse

• Optimale Strategien:
  • Im High-Difficulty-Regime (aktuell und projiziert) besteht die optimale Strategie für beide Miner darin, alle Ressourcen auf die letzte Messung zu konzentrieren. Der erwartete Payoff ist extrem niedrig ($\approx 8,9 \times 10^{-5}$), und die Miner sind statistisch nicht von klassischen Minern zu unterscheiden.
  • Im Low-Difficulty- und Ideal-Regime verteilen die Miner Ressourcen über mehrere Messungen. Für $c=2$ werden die Ressourcen aufgeteilt, um die Erfolgswahrscheinlichkeit gegen den zeitlichen Vorteil abzuwägen. Für $c \ge 3$ konzentrieren Miner die Ressourcen oft auf weniger Messungen oder führen bei einigen Versuchen null Iterationen durch, um die quadratische Erfolgswahrscheinlichkeit anderer Versuche zu maximieren.
• Stale-Rate und 51 %-Angriffsschwelle:
  • High-Difficulty: Der Einfluss auf die Stale-Rate ist vernachlässigbar. Die 95. und 99. Perzentile von $p_{stale}$ liegen effektiv bei Null. Die Wahrscheinlichkeit, dass $p_{stale}$ den Schwellenwert von $1/3$ überschreitet, ist Null. Das Netzwerk produziert die erwarteten 144 Blöcke pro Tag, und die Anwesenheit von Quanten-Minern ist nicht nachweisbar.
  • Low-Difficulty/Ideal: Diese Regime zeigen eine signifikante Erhöhung von $p_{stale}$, wobei einige simulierte Tage den $1/3$-Benchmark erreichen. Jedoch ist die empirische Wahrscheinlichkeit für $p_{stale} > 1/3$ verschwindend gering ($10^{-6}$ bis $10^{-8}$).
  • Detektion: In den Low-Difficulty- und Ideal-Regimen ist die Anwesenheit von Quanten-Minern statistisch sicher nachweisbar ($P_{det} = 1$) aufgrund der anomalen Fork-Rate, wohingegen im High-Difficulty-Regime die Detektion vernachlässigbar ist.

Bedeutung und Behauptungen
Die Arbeit kommt zu dem Schluss, dass die Bedrohung durch zwei nicht kolludierende Quanten-Miner, die gegeneinander um das Bitcoin-Netzwerk konkurrieren, für absehbarer Zeit vernachlässigbar ist.

• Sicherung der Sicherheit: Selbst unter den aggressivsten Annahmen (multiple Messungen, AQMS und optimales Spiel) führt die resultierende Stale-Rate nicht nachhaltig über den Schwellenwert, der einen 51 %-Angriff machbar machen würde. Das Bitcoin-Netzwerk bleibt gegen dieses spezifische Adversarial-Modell sicher.
• Realismus: Die Autoren betonen, dass die Regime, in denen $p_{stale}$ signifikant ansteigt (Low-Difficulty und Ideal), in der Praxis unwahrscheinlich sind. Das Low-Difficulty-Regime erfordert eine Netzwerk-Difficulty, wie sie seit der Geburtsstunde von Bitcoin nicht mehr gesehen wurde, und das Ideal-Regime erfordert einen Quanten-Oracle, der in der Lage ist, den gesamten 640-Bit-Block-Header zu kodieren, was technologisch derzeit nicht realisierbar ist.
• Detektion: In Szenarien, in denen die Stale-Rate tatsächlich ansteigt, würde das Netzwerk die Quanten-Miner statistisch sofort detektieren, was potenzielle Gegenmaßnahmen ermöglicht.
• Begrenzter Umfang: Die Autoren merken an, dass ihr Modell ein „Best-Case-Szenario“ für Quanten-Miner darstellt, da es Overheads im Zusammenhang mit der Zustandspräparation und der Konstruktion des Oracles ignoriert. Folglich wäre der tatsächliche Einfluss auf die Stale-Rate wahrscheinlich sogar noch geringer als vorhergesagt. Die Arbeit schafft eine Grundlage für die Untersuchung einer größeren Anzahl von Minern oder kolludierender Strategien, stellt jedoch fest, dass für zwei Miner die 51 %-Angriffsschwelle robust bleibt.