Strategies for quantum-enabled Bitcoin miners

Technical Summary: Strategies for Quantum-Enabled Bitcoin Miners

Problem Statement
The security of the Bitcoin network relies on the assumption that executing a "51% attack"—where a consortium controls the majority of the network's computational power to double-spend or reverse transactions—is prohibitively expensive. While prior works have theoretically suggested that Grover's algorithm could reduce the cost of such an attack by providing a quadratic speedup in solving the Proof-of-Work (PoW) problem, these studies often relied on narrow adversarial models. Specifically, previous models restricted quantum miners to a single quantum measurement per mining race and a "peaceful" strategy (discarding the search upon a new block broadcast). This paper addresses the gap by studying the impact of two non-colluding, aggressive quantum miners on the 51% attack threshold within a more realistic adversarial model. The core problem is to determine the optimal quantum mining strategies for two competing miners who can perform multiple quantum measurements and utilize Sattath's aggressive quantum mining strategy (AQMS), and to quantify the resulting effect on the network's stale rate ($p_{stale}$) and the effective 51% attack threshold.

Methodology
The authors extend the Symmetric Two-Player Quantum Races (S2QR) game-theoretic framework to model the competition between two quantum miners, Alice and Bob, within an otherwise classical Bitcoin network.

1. Model Extensions:

   • Multiple Measurements: Unlike prior models assuming a single measurement, this model allows miners to perform $c$ quantum measurements between successive blocks.
   • Aggressive Strategy: The model incorporates Sattath's AQMS, where miners halt their search and measure immediately upon receiving a broadcast of a new block, rather than discarding their computational effort. This strategy increases the correlation between measurement times and block discovery, potentially increasing the stale rate.
   • Resource Constraints: Miners operate under a cumulative Grover iteration budget $\kappa$, distributed across $c$ measurements. The strategy space involves allocating these iterations to maximize the probability of being the first to find a valid block.

2. Game-Theoretic Formulation:

   • The competition is modeled as a strategic game where Alice and Bob choose pure strategies (vectors of Grover iterations for each of their $c$ measurements).
   • Payoff Matrices: The authors derive closed-form expressions for the payoff matrices ($A$ and $B$) for both players. These matrices account for:
     • The probability of success for the Finite-Budget Quantum Search (FQS) algorithm based on the number of Grover iterations.
     • The additive structure of payoffs across multiple measurements.
     • The terms introduced by AQMS, which modify payoffs when a miner measures after an opponent has already found a solution (or when measurements occur simultaneously).
   • Equilibrium Computation: Optimal strategies are identified as Nash equilibria. Due to the combinatorial explosion of the strategy space (growing with $c$), the authors employ a heuristic to sample the pure strategy space and use the Lemke-Howson algorithm to compute exact Nash equilibria.

3. Simulation:

   • To evaluate the security impact, the authors perform Monte Carlo simulations (1,000,000 days) using the computed Nash equilibria.
   • The simulations track the stale rate ($p_{stale}$), defined as the ratio of blocks outside the longest chain to the total blocks.
   • The study assesses whether $p_{stale}$ exceeds the critical threshold of $1/3$, which would lower the effective 51% attack threshold to 40% or below.
   • Simulations are conducted across three network difficulty regimes: Low ($D \le 2^{32}$), High ($D > 2^{32}$, reflecting current and projected difficulties), and Ideal (where the quantum oracle encodes the entire block header).

Key Contributions

• Novel Strategy Inclusion: The paper introduces the "Aggressive Quantum Mining Strategy" (AQMS) into a game-theoretic framework, analyzing its impact alongside multiple quantum measurements.
• Generalized Payoff Matrices: The authors derive the mathematical structure of payoff matrices for $c$ quantum measurements, extending the S2QR model to handle the cumulative nature of multiple attempts and the specific timing correlations induced by AQMS.
• Optimal Strategy Computation: The study computes optimal quantum mining strategies (Nash equilibria) for $c \in \{1, 2, 3, 4\}$ across different difficulty regimes, revealing how miners should allocate their Grover iteration budgets.
• Security Quantification: The paper provides a quantitative assessment of the 51% attack threshold under these optimal strategies, moving beyond theoretical possibilities to simulated outcomes.

Results

• Optimal Strategies:
  • In the High-Difficulty Regime (current and projected), the optimal strategy for both miners is to allocate all resources to the final measurement. The expected payoff is extremely low ($\approx 8.9 \times 10^{-5}$), and the miners are statistically indistinguishable from classical miners.
  • In Low-Difficulty and Ideal Regimes, miners distribute resources across multiple measurements. For $c=2$, resources are split to balance success probability against temporal advantage. For $c \ge 3$, miners often concentrate resources into fewer measurements or perform zero iterations on some attempts to maximize the quadratic success probability of others.
• Stale Rate and 51% Attack Threshold:
  • High-Difficulty: The impact on the stale rate is negligible. The 95th and 99th percentiles of $p_{stale}$ are effectively zero. The probability of $p_{stale}$ exceeding the $1/3$ threshold is zero. The network produces the expected 144 blocks per day, and the presence of quantum miners is undetectable.
  • Low-Difficulty/Ideal: These regimes show a significant increase in $p_{stale}$, with some simulated days approaching the $1/3$ benchmark. However, the empirical probability of $p_{stale} > 1/3$ is vanishingly small ($10^{-6}$ to $10^{-8}$).
  • Detection: In the Low-Difficulty and Ideal regimes, the presence of quantum miners is statistically certain to be detected ($P_{det} = 1$) due to the anomalous fork rate, whereas in the High-Difficulty regime, detection is negligible.

Significance and Claims
The paper concludes that the threat posed by two non-colluding quantum miners racing each other to the Bitcoin network is negligible for the foreseeable future.

• Security Preservation: Even under the most aggressive assumptions (multiple measurements, AQMS, and optimal play), the resulting stale rate does not sustainably exceed the threshold required to make a 51% attack feasible. The Bitcoin network remains secure against this specific adversarial model.
• Realism: The authors emphasize that the regimes where $p_{stale}$ increases significantly (Low-Difficulty and Ideal) are unlikely to occur in practice. The Low-Difficulty regime requires a network difficulty not seen since Bitcoin's inception, and the Ideal regime requires a quantum oracle capable of encoding the entire 640-bit block header, which is currently technologically infeasible.
• Detection: In scenarios where the stale rate does increase, the network would statistically detect the quantum miners immediately, allowing for potential countermeasures.
• Modest Scope: The authors note that their model represents a "best-case scenario" for quantum miners, as it ignores overheads associated with state preparation and oracle construction. Consequently, the actual impact on the stale rate would likely be even lower than predicted. The work establishes a foundation for studying larger numbers of miners or colluding strategies but asserts that, for two miners, the 51% attack threshold remains robust.