The Threat of Quantum Computing to Bitcoin Security: A 9-Minute Window to Steal

The first part of this series delved into the basics of quantum computing, but understanding how it works is not enough to grasp its potential impact on bitcoin security. To comprehend the threat, it's essential to know how bitcoin's encryption functions, why quantum algorithms can break it, and the significance of Google's recent paper on the subject. This piece will examine bitcoin's encryption, the role of elliptic curve cryptography, and the nine-minute window that a quantum computer needs to break it, as identified by Google's research. Bitcoin's security relies on a one-way map, where a private key is used to generate a public key through a mathematical operation on the secp256k1 curve. This process is easy to perform in one direction but virtually impossible to reverse using classical computers. However, quantum computers can exploit this using Shor's algorithm, which solves the discrete logarithm problem efficiently. The algorithm works by finding the period of a function, which is a task that quantum computers are well-suited for. By applying the function to all possible inputs simultaneously and using the Fourier transform, the correct period can be found, allowing for the recovery of the private key. The recent paper by Google's Quantum AI division has reduced the estimated number of qubits required to run Shor's algorithm against bitcoin's elliptic curve from millions to fewer than 500,000. This reduction in qubit count, combined with the introduction of a practical attack scenario, changes the way we think about the threat to bitcoin security. The parts of Shor's algorithm that depend on the elliptic curve's fixed parameters can be precomputed, allowing the quantum computer to sit in a primed state, waiting for a target public key to appear. Once a public key is visible, the machine only needs to finish the second half of the calculation, which Google estimates takes around nine minutes. This creates a narrow window of opportunity for a quantum attacker to derive a private key and submit a competing transaction. The math gives the attacker a roughly 41% chance of succeeding before the original transaction confirms. While this 'mempool attack' is alarming, it requires a quantum computer that does not yet exist. A more significant concern is the 6.9 million bitcoin that are already vulnerable to an 'at-rest' attack, where the public key has been permanently exposed on the blockchain. These coins can be targeted without any time constraint, making them highly susceptible to quantum attacks.