The Quantum Threat to Bitcoin: How Your Cryptocurrency Could be Stolen in Under 10 Minutes

The first part of this series delved into the physics behind quantum computing, but understanding how it works is not enough to grasp the potential risks to Bitcoin. To comprehend the threat, it's essential to know how Bitcoin's security is built and where the weaknesses lie. This piece begins by examining Bitcoin's encryption, specifically the elliptic curve cryptography that verifies ownership. Every wallet has a private key, a secret 256-digit binary number, and a public key derived from it using a mathematical operation on the secp256k1 curve. This one-way function allows anyone to verify the public key but makes it virtually impossible for classical computers to reverse-engineer the private key. However, a quantum algorithm known as Shor's algorithm can efficiently break this encryption. Discovered in 1994, Shor's algorithm solves the discrete logarithm problem, which would take a classical computer longer than the universe has existed to solve, in what's known as polynomial time. The algorithm works by converting the problem into finding the period of a function, which is a task that quantum computers are particularly well-suited for. By using superposition, entanglement, and interference, a quantum computer can find the period and, from it, derive the private key. This means that if a quantum computer with a large enough number of stable qubits is built, it could potentially steal Bitcoin by deriving the private key from the public key. The reason Bitcoin remains secure for now is that building such a machine has been beyond current technological capabilities. However, a recent paper by Google's Quantum AI division, in collaboration with researchers from the Ethereum Foundation and Stanford, has significantly reduced the estimated number of qubits needed to run Shor's algorithm against Bitcoin's elliptic curve, from millions to fewer than 500,000. This reduction in required qubits brings the threat of quantum computing to Bitcoin closer to reality. The paper also introduced a practical attack scenario, where parts of Shor's algorithm can be precomputed, allowing a 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 about nine minutes. Given that Bitcoin's average block confirmation time is 10 minutes, this means a quantum attacker has a roughly 41% chance of deriving a private key and submitting a competing transaction before the original transaction confirms. This 'mempool attack' is alarming but requires a quantum computer that does not yet exist. A more significant concern is the approximately 6.9 million Bitcoin (about one-third of the total supply) that are already vulnerable to an 'at-rest' attack because their public keys have been permanently exposed on the blockchain. These coins can be targeted without any time constraint, as the attacker can take as long as needed to derive the private key. The implications of this vulnerability, including which Bitcoin are already exposed and how Taproot, a privacy upgrade implemented in November 2021, affects the situation, will be explored in the next part of this series.