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

The first part of this series explored the fundamental principles of quantum computing, distinguishing it from classical computing. However, understanding the inner workings of a quantum computer is only half the story; the other half involves comprehending what it can attack and how. This piece focuses on bitcoin's security architecture, the weakness a quantum algorithm can exploit, and the implications of Google's recent quantum computing paper, which significantly reduces the estimated time and resources needed to break bitcoin's encryption. Bitcoin relies on elliptic curve cryptography, a system that utilizes a pair of keys: a private key, kept secret, and a public key, derived from the private key through a complex mathematical operation on the 'secp256k1' curve. This process is akin to a one-way map, where starting from a known point (generator point G), taking a certain number of steps defined by your private key leads you to your public key (point K). While moving forward in this map is straightforward, reversing the process to find the private key from the public key is virtually impossible for classical computers due to the elliptic curve discrete logarithm problem. The best classical algorithms would take an impractically long time, longer than the age of the universe, to solve this problem for a 256-bit curve. The security of bitcoin hinges on this one-way trapdoor, with the private key serving as proof of ownership and the public key being safe to share. However, the advent of quantum computing, specifically through Shor's algorithm discovered in 1994, poses a significant threat. Shor's algorithm can efficiently solve the discrete logarithm problem, breaking the trapdoor that classical computers cannot. It achieves this by converting the problem into finding the period of a function related to the elliptic curve, a task well-suited to quantum computers. Quantum computers can represent all possible inputs simultaneously in a superposition, apply the function to all of them at once, and then use the Fourier transform to find the period, from which the private key can be derived. This process exploits the principles of superposition, entanglement, and interference, making it a powerful tool against bitcoin's encryption. Despite Shor's algorithm being known for over 30 years, its application has been hindered by the requirement for a quantum computer with a sufficiently large number of stable qubits. Recent research by Google, in collaboration with the Ethereum Foundation and Stanford cryptographers, has significantly reduced the estimated number of qubits needed, from millions to fewer than 500,000, a reduction of roughly 20-fold. This advancement introduces a practical attack scenario, where parts of Shor's algorithm can be precomputed, allowing a quantum computer to be in a 'primed' state, ready to finish the calculation once a target public key is identified. The second half of the calculation, which depends on the specific target, can be completed in approximately nine minutes, according to Google's estimates. This timeframe is critical because it coincides with bitcoin's average block confirmation time of 10 minutes. An attacker has a window of opportunity to derive a private key and submit a competing transaction that could redirect funds, with about a 41% chance of succeeding before the original transaction is confirmed. The more pressing concern, however, is the approximately 6.9 million bitcoin (about one-third of the total supply) that are already vulnerable due to their public keys being exposed on the blockchain. These coins are at risk of an 'at-rest' attack, which does not require racing against the clock. The implications of these findings, including the impact of Taproot and the pace at which quantum hardware is advancing, will be explored in the final piece of this series.