The Quantum Threat to Bitcoin: How a 9-Minute Window Can Compromise Your Cryptocurrency

The first part of this series delved into the principles of quantum computing, but understanding how it works is only half the story. To grasp the threat it poses to bitcoin, it's essential to comprehend what it's attacking and where the vulnerabilities lie. This piece begins with an examination of bitcoin's encryption, shedding light on how a quantum algorithm can break it and the significance of Google's recent paper in altering the timeline. Bitcoin relies on elliptic curve cryptography to verify ownership. Each wallet has a private key, a secret 256-bit number, and a public key derived from it using the 'secp256k1' curve. This process can be thought of as a one-way map, where starting from a known point, taking a certain number of steps defined by the curve's mathematics leads to the public key. While moving forward is straightforward, reversing the process is virtually impossible for classical computers due to the elliptic curve discrete logarithm problem. However, in 1994, mathematician Peter Shor discovered a quantum algorithm that can efficiently solve this problem, thereby breaking the security model. Shor's algorithm works by finding the period of a function related to the elliptic curve, which is achievable due to quantum computing's ability to handle superposition, entanglement, and interference. Despite the algorithm being known for over 30 years, its implementation has been hindered by the need for a large number of stable qubits. A recent paper by Google significantly reduced the estimated number of qubits required, from millions to fewer than 500,000, by designing specific quantum circuits for implementing Shor's algorithm against bitcoin's elliptic curve. This reduction, along with the introduction of a practical attack scenario, changes the perspective on the quantum threat. The scenario involves precomputing parts of the algorithm that depend on the elliptic curve's fixed parameters, allowing the quantum computer to sit in a primed state. When a target public key appears, the machine only needs to finish the second half of the calculation, which Google estimates takes about nine minutes. This timeline is alarming because it's close to bitcoin's average block confirmation time, giving an attacker a roughly 41% chance of deriving a private key and submitting a competing transaction before the original transaction confirms. Moreover, about 6.9 million bitcoin are vulnerable to an 'at-rest' attack since their public keys have been exposed on the blockchain. These coins can be compromised without any time constraint, posing a significant concern. The practical implications of these findings and the race between quantum computing advancements and cryptographic security upgrades will be explored in the next part of this series.