PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum attacks on Bitcoin, and how to protect against them

Divesh Aggarwal, Gavin K. Brennen, Troy Lee, Miklos Santha, Marco Tomamichel

arXiv:1710.10377v1quant-phq-fin.GN

TL;DR

The paper investigates how quantum computers could threaten Bitcoin and other cryptocurrencies, whose cryptographic security supports a market worth over 150 billion USD. It analyzes Bitcoin’s proof-of-work and signature scheme, evaluates alternative defenses, and finds that proof-of-work is relatively resistant near term while elliptic-curve signatures could be broken as early as 2027 under optimistic estimates.

  • Problem

    Quantum computers threaten cryptographic protocols securing internet, financial transactions, and cryptocurrencies, motivating an analysis of Bitcoin’s vulnerability.

  • Method

    The paper analyzes Bitcoin’s proof-of-work and elliptic-curve signatures, evaluates Momentum, and reviews post-quantum signature schemes for blockchain requirements.

  • Results

    Bitcoin’s proof-of-work is relatively resistant to substantial near-term quantum speedup, but its elliptic-curve signatures could be cracked in 30 minutes at 10GHz using 485550 qubits.

  • Takeaways & Limitations

    Momentum offers a proof-of-work with even less quantum speedup, while post-quantum signature schemes provide candidate defenses for blockchain applications.

Abstract

from arXiv · show

The key cryptographic protocols used to secure the internet and financial transactions of today are all susceptible to attack by the development of a sufficiently large quantum computer. One particular area at risk are cryptocurrencies, a market currently worth over 150 billion USD. We investigate the risk of Bitcoin, and other cryptocurrencies, to attacks by quantum computers. We find that the proof-of-work used by Bitcoin is relatively resistant to substantial speedup by quantum computers in the next 10 years, mainly because specialized ASIC miners are extremely fast compared to the estimated clock speed of near-term quantum computers. On the other hand, the elliptic curve signature scheme used by Bitcoin is much more at risk, and could be completely broken by a quantum computer as early as 2027, by the most optimistic estimates. We analyze an alternative proof-of-work called Momentum, based on finding collisions in a hash function, that is even more resistant to speedup by a quantum computer. We also review the available post-quantum signature schemes to see which one would best meet the security and efficiency requirements of blockchain applications.

I. INTRODUCTION

The paper examines Bitcoin’s exposure to quantum attacks, finding that proof-of-work remains relatively resistant in the near term while elliptic-curve signatures face a potentially earlier and more severe threat. It proposes countermeasures including an alternative proof-of-work and quantum-safe signature schemes.

  • Bitcoin’s security relies on proof-of-work for ledger protection and elliptic-curve signatures for transaction authorization.
  • Near-term quantum computers are expected to provide little substantial speedup against Bitcoin’s proof-of-work because specialized ASIC miners are much faster than projected quantum computers.
  • Once transactions are on the blockchain, they would remain relatively protected even in the presence of a quantum computer.
  • As early as 2027, a quantum computer could potentially break Bitcoin’s elliptic-curve signature scheme in less than 10 minutes under the most optimistic estimates.
  • The paper analyzes Momentum, a collision-based proof-of-work, and reviews post-quantum signature schemes against blockchain security and efficiency requirements.

II. BLOCKCHAIN BASICS

Bitcoin organizes transactions in a public, hash-linked blockchain and adds blocks through Hashcash proof-of-work. Miners search for valid headers, while transaction ownership is demonstrated with public keys and corresponding private-key signatures.

  • Blockchain structure: Bitcoin stores transactions in a public ledger whose blocks are linked by hashes of preceding block headers.
  • Proof-of-work: Hashcash requires miners to find a block header satisfying h(header) ≤ t, with difficulty adjusted every 2016 blocks to target roughly 10-minute solution times.
  • Proof-of-work: Bitcoin’s proof-of-work uses h(·) = SHA256(SHA256(·)); its expected trial count is 2^256/t, while difficulty is defined as D = 2^224/t.
  • Mining: Miners can choose block contents, receive a mining reward, and search disjoint header spaces because each block includes its own generation transaction.
  • Chain security: A valid proof-of-work is easy for the network to verify with one hash evaluation, while rewriting a block requires winning a competing race from behind.
  • Transactions: To send bitcoin, Bob identifies earlier payments to addresses he controls and signs the transfer using the corresponding private keys.

A. Attacks on the Bitcoin proof-of-work

Bitcoin’s hashcash proof-of-work offers Grover’s algorithm a quadratic reduction in hash queries, but quantum error-correction and clock-speed overheads largely erase that advantage against specialized ASIC miners. Under optimistic future assumptions, quantum mining may eventually gain speed, yet a single quantum computer is not expected to obtain majority hashing power.

  • Quantum search: Grover’s algorithm reduces the hash queries needed for Bitcoin’s proof-of-work quadratically compared with classical search.The analysis models the task in the random-oracle setting and uses Grover search over candidate block headers.
  • Scaling with difficulty: The effective quantum hash rate scales as the square root of mining difficulty, reflecting the quadratic quantum advantage when time overhead is bounded.Parallel quantum processors further increase the effective rate according to the modeled search strategy.
  • Future and strategic implications: At D = 10^13 and s = 50GHz, twenty quantum machines would provide 0.1% of total hashing power and could reduce pool revenue by 10% through a pool-mining attack.The example assumes the optimistic effective-hash-rate scaling used in the analysis.
  • Future and strategic implications: Before 2028 in the optimistic estimate, no quantum computer has enough qubits to implement Grover’s algorithm, and later quantum machines are not expected to achieve majority hashing power.The projections compare quantum hashing power with the Bitcoin network and a current ASIC device.

B. Attacks on signatures

Bitcoin’s elliptic-curve signatures are vulnerable to Shor’s algorithm, with the most serious risk occurring before broadcast transactions are confirmed. Resource estimates indicate that a sufficiently capable quantum computer could make this attack practical as early as 2027.

  • Shor’s algorithm can efficiently derive Bitcoin’s private key from a published public key by solving the elliptic-curve discrete-log problem.Bitcoin uses signatures based on the secp256k1 curve; the attack applies once the public key is revealed.
  • Processed transactions with several confirming blocks are reasonably secure because double spending would still require out-hashing the network.The paper states that such a double-spending attack is unlikely even with a quantum computer.
  • Unprocessed transactions are vulnerable because an attacker could replace a broadcast payment and confirm the fraudulent transaction first.The attack window lasts from broadcast until the transaction is placed on the blockchain.
  • 1.28 × 10^11 Toffoli gates are required for Bitcoin’s 256-bit signature instance, with a parallelized depth of 1.16 × 10^11.The estimate uses 256-bit signatures and accounts for quantum-resource requirements for solving the ECDLP.
  • 30 minutes at 10GHz and 10^-5 physical gate error would require 485550 qubits, making the signature attack potentially practical.At 66.6MHz and a 5 × 10^-4 error rate, the estimated attack takes 6.49 days using 1.7 × 10^6 physical qubits.
  • The most optimistic estimate places the time to break the signature below 600 seconds as early as 2027.Figure 4 compares more and less optimistic projections over the following 25 years.

C. Future enhancements of quantum attacks

The paper identifies several ways future quantum-computing improvements could make its attack estimates more favorable, including better error correction, lower circuit costs, and parallelized algorithms.

  • C. Future enhancements of quantum attacks: The paper cautions that its estimates may be optimistic, although several avenues for improved quantum performance remain possible.This qualification applies to the assumed quantum-computing speed and scaling.
  • C. Future enhancements of quantum attacks: Alternative quantum error-correction codes could reduce or remove some of the surface code’s classical processing overhead, potentially improving overall speed.The paper specifically discusses state distillation, syndrome extraction, and measurement-free protocols.
  • C. Future enhancements of quantum attacks: More efficient quantum-computation techniques could reduce the logical gate counts used in attack circuits.The paper cites a prior comparison showing several orders of magnitude improvement for a different large-size example problem, while expecting less dramatic gains for Shor and Grover algorithms.
  • C. Future enhancements of quantum attacks: Different quantum algorithms could provide relative speedups by distributing discrete-logarithm computations across multiple quantum processors.The discussed approach solves different bits separately and may also reduce quantum error-correction overhead in parts of the circuit.

A. Alternative proofs-of-work

The paper evaluates alternative proof-of-work designs that could reduce quantum advantages over Bitcoin’s hashcash, focusing on Momentum’s collision-finding structure and its classical and quantum running times.

  • A. Alternative proofs-of-work: The alternative-proof-of-work discussion seeks a design that preserves adjustable difficulty and verification asymmetry while reducing quantum advantage.Bitcoin’s proof-of-work already satisfies difficulty and asymmetry, but the paper seeks improvement on the no-quantum-advantage property.
  • A. Alternative proofs-of-work: Momentum is based on finding collisions in a memory-intensive hash function, alongside a threshold condition on a second hash.Its proof requires H, a, and b to satisfy both a hash-threshold condition and a collision condition.
  • A. Alternative proofs-of-work: The Momentum analysis searches subsets for hash collisions, then tests those collisions against the proof-of-work threshold.The classical procedure varies H and uses collisions among h2(H ∥ a) values before checking h1(H ∥ a ∥ b) ≤ t.
  • A. Alternative proofs-of-work: For Momentum, quantum collision-finding and Grover search combine to produce a running-time lower bound that exceeds the classical square-root speedup pattern.Testing whether H is good requires at least |S|^2/3 time, while finding a good H requires at least √m tests.
  • A. Alternative proofs-of-work: A quantum computer cannot achieve a quadratic advantage over the current Bitcoin proof-of-work with Momentum once the subset size exceeds a constant.The paper presents this as an improvement over Bitcoin’s current proof-of-work, whose Grover-based attack has a quadratic hash-count reduction.

B. Review of post-quantum signature schemes

The paper reviews post-quantum signature families for blockchain use, emphasizing stored key and signature lengths, verification time, quantum security, and implementation risks.

  • B. Review of post-quantum signature schemes: Post-quantum signature candidates include hash-based, code-based, multivariate, and lattice-based schemes.The listed examples include XMSS, SPHINCS, QUARTZ, RAINBOW, BLISS, and DILITHIUM.
  • B. Review of post-quantum signature schemes: Blockchain applications prioritize public-key length, signature length, and verification time because transaction verification requires storing relevant signature data.Considering the combined key and signature lengths, the paper identifies hash- and lattice-based schemes as the only reasonable options in its comparison.
  • B. Review of post-quantum signature schemes: Hash-based schemes such as XMSS offer provable security under a random-oracle assumption but lose half their classical security level under Grover’s generic attack.The paper contrasts this with DILITHIUM’s stated quantum-attack cost at a 138-bit classical security level.
  • B. Review of post-quantum signature schemes: At the same quantum security level, lattice-based schemes have an advantage in combined signature and public-key length.The comparison concerns the sum of signature and public-key lengths rather than verification time alone.
  • B. Review of post-quantum signature schemes: BLISS has the shortest combined signature and public-key length in the table but is discouraged by security assumptions, prior NTRU-based attacks, and side-channel vulnerability.A production implementation reportedly allowed signing-key recovery after about 6000 observed signature generations.

Appendix A: Estimating error correction resource overheads for quantum attacks

The appendix estimates quantum error-correction overhead by counting circuit resources under stated future hardware and coding assumptions. Under optimistic assumptions, superconducting circuits could yield a substantially faster effective hashing rate.

  • Resource-overhead method: The overhead calculation begins by determining the numbers of T gates and Clifford gates required by the attack.The method follows prior analyses and uses pseudocode to compute the resulting overhead.
  • Resource-overhead method: The blockchain attack is modeled with nL = 2402 qubits, while the digital-signature attack uses nL = 2334 qubits.
  • Circuit assumptions: The oracle circuit depth is 2142094, computed from four SHA256 hash depths and two multi-controlled phase-gate depths.The stated decomposition is 4 × 528768 + 2 × 13511 = 2142094.
  • Result: 2.0 × 10^3 TH/s is the estimated effective hash rate at difficulty D = 10^12 under optimistic superconducting-circuit assumptions.The estimate uses ultrafast geometric phase gates operating at approximately 50 GHz.

Appendix B: Modeling the development of bitcoin network hash rates and difficulty

The appendix extrapolates Bitcoin’s network hash rate under optimistic and less optimistic growth scenarios, then derives hashing difficulty from the projected rate. The resulting difficulty estimates are compared with historical blockchain.info values.

  • Hash-rate extrapolation: Bitcoin network hash-rate data use observations from January 2012–2015 and January and July 2016–2017.The data are taken from blockchain.info.
  • Hash-rate extrapolation: The optimistic scenario extends exponential growth for five years before switching to linear growth as the market saturates with optimized ASIC miners.
  • Hash-rate extrapolation: The less optimistic scenario assumes linear hash-rate growth at the present rate.
  • Difficulty calculation: D(t) = rate(t) · 600 · 2^-32 derives Bitcoin’s hashing difficulty from the projected total hash rate.The factor 600 represents the 600 seconds in the ten-minute target block interval.
  • Difficulty calculation: The predicted difficulty curves are compared with blockchain.info values for January 2015–2017.

Appendix C: Modeling the development of quantum computers

The appendix models future quantum-computer capabilities using optimistic and less optimistic assumptions for qubit growth, gate frequency, gate infidelity, and algorithmic overhead. Because few early data points exist, the resulting projections are explicitly rough and uncertain.

  • Modeling uncertainty: The projections use two development scenarios because only a few data points are available for emerging quantum technologies.The authors describe the estimates as very rough and subject to future adaptation.
  • Qubit growth: The optimistic qubit-growth assumption doubles available qubits every 10 months, versus every 20 months in the less optimistic scenario.
  • Gate frequency: The quantum-gate-frequency model assumes exponential growth initially, capped at 50 GHz optimistically or 5 GHz less optimistically.Further acceleration is assumed to require sufficiently fast classical control circuits.
  • Gate frequency: Historical gate-time data include 420 ns in 2013, 433 ns in 2015, 160 ns in 2016, 42 ns in 2017, and a projected 25 ns in 2018.
  • Gate fidelity: Gate infidelity is modeled to decline exponentially before stalling at 5 · 10^-6 optimistically or 5 · 10^-5 less optimistically.The optimistic case follows a reduction by a factor of 2 per year.
  • Algorithmic overhead: Algorithmic overhead is assumed to decrease over time because of improving gate fidelity and theoretical advances that reduce required qubits and gates.The model uses overhead(t) = β^(t−2017), with β ∈ {0.75, 0.85} for the two scenarios.
Loading 1710.10377v1…