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

The first part of this series delved into the physics of quantum computing, explaining how these machines differ fundamentally from classical computers. However, understanding the mechanics of quantum computing doesn't reveal how it can be exploited to steal bitcoin. To grasp this, one must comprehend what a quantum computer attacks and how the security of bitcoin is structured, including the specific vulnerabilities it presents. This piece begins by examining bitcoin's encryption method, known as elliptic curve cryptography, which is used to verify ownership. Every bitcoin wallet has a pair of keys: a private key, which is a secret number, and a public key, derived from the private key through a mathematical operation on the 'secp256k1' curve. The process can be thought of as a one-way map, where starting from a known point on the curve, taking a certain number of steps (defined by your private key) leads to a public key. While it's straightforward to go from the private key to the public key, reversing this process is virtually impossible for classical computers due to the elliptic curve discrete logarithm problem. This problem is so complex that even the best classical algorithms would take longer than the universe's age to solve for a 256-bit curve. The security of bitcoin relies on this one-way trapdoor, where knowing the public key does not allow one to deduce the private key. However, in 1994, mathematician Peter Shor discovered a quantum algorithm that can efficiently break this trapdoor by solving the discrete logarithm problem in polynomial time. Shor's algorithm converts the problem of finding the private key into finding the period of a function related to the elliptic curve. Quantum computers are particularly adept at this task due to their ability to represent all possible values simultaneously (superposition), apply functions to all these values at once, and then use interference to filter out incorrect answers, leaving the correct period. From this period, the private key can be easily derived, thereby compromising the bitcoin's security. The reason bitcoin remains secure for now is that running Shor's algorithm requires a quantum computer with a sufficiently large number of stable qubits. Recent research by Google, in collaboration with the Ethereum Foundation and Stanford, has significantly reduced the estimated number of qubits needed, from millions to fewer than 500,000. This reduction comes from designing quantum circuits specifically for attacking bitcoin's elliptic curve, which can be achieved with approximately 1,200 to 1,450 logical qubits. However, due to the fragile nature of qubits, which constantly lose their quantum state, hundreds of physical qubits are needed to maintain a single logical qubit, making the actual number of qubits required much higher. Google's research also introduced a practical attack scenario, where parts of Shor's algorithm can be precomputed for bitcoin's elliptic curve, allowing the quantum computer to sit in a primed state. Once a target public key is broadcast, the machine only needs to finish the second half of the calculation, which Google estimates takes about nine minutes. Given that bitcoin's average block confirmation time is 10 minutes, this presents a narrow window for an attacker to derive a private key and submit a competing transaction. For bitcoin already exposed on the blockchain, particularly those transacted since the Taproot upgrade, the risk is even higher as there's no race against the clock for an attacker. The implications of this quantum threat and the practical steps to mitigate it will be explored in the next piece of this series.