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

In the first part of this series, we explored the basics of quantum computing, a fundamentally different kind of machine that exploits the unique rules of physics at the atomic and particle level. However, understanding how a quantum computer works is not the same as knowing how it can be used to steal bitcoin. To grasp the latter, one must comprehend what the quantum computer is attacking, how bitcoin's security is structured, and where the vulnerabilities lie. This piece begins with an explanation of bitcoin's encryption, working its way through to the nine-minute window identified by Google's recent quantum computing paper, during which a quantum algorithm can potentially break bitcoin's security. Bitcoin relies on elliptic curve cryptography, a system that uses 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 a specific curve known as 'secp256k1'. This 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 the curve's mathematics leads to a public key. Anyone can verify the public key, but figuring out the number of steps (the private key) is virtually impossible for classical computers. This one-way function is the backbone of bitcoin's security model, with the private key serving as proof of ownership and the public key being safe to share. However, in 1994, mathematician Peter Shor discovered a quantum algorithm that can efficiently break this one-way trapdoor. Shor's algorithm solves the discrete logarithm problem, which is the mathematical challenge of finding the private key given the public key and the curve's parameters. This is done by converting the problem into finding the period of a function, which quantum computers can solve efficiently by exploiting superposition, entanglement, and interference. The algorithm puts its input into a superposition, applies the function to all possible inputs simultaneously, and then uses a Fourier transform to filter out incorrect answers, leaving only the correct period. From this period, the private key can be easily derived, thereby breaking the encryption. The reason bitcoin remains secure today is that running Shor's algorithm requires a quantum computer with a sufficiently large number of stable qubits. However, a recent paper by Google's Quantum AI division, in collaboration with researchers from the Ethereum Foundation and Stanford, significantly reduced the estimated number of qubits needed, from millions to fewer than 500,000. This reduction comes from designing quantum circuits that implement Shor's algorithm against bitcoin's specific elliptic curve, requiring approximately 1,200 to 1,450 logical qubits and tens of millions of Toffoli gates. The introduction of a practical attack scenario changes the perspective on the threat. Parts of Shor's algorithm can be precomputed, allowing the quantum computer to be in a primed state, waiting for a target public key to appear. Once it does, 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, an attacker has roughly nine minutes to derive a private key and submit a competing transaction. This gives the attacker a 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 approximately 6.9 million bitcoin (about one-third of the total supply) in wallets where the public key has already been exposed on the blockchain, making them vulnerable to an 'at-rest' attack that does not race against the clock. For these coins, a quantum computer running Shor's algorithm can turn the public key into the private key at any time, without the urgency of the nine-minute window.