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

The first part of this series explored the fundamental principles of quantum computing. However, understanding how quantum computers work is only half the story when it comes to the potential theft of bitcoin. To grasp the full scope of the threat, it's essential to comprehend what a quantum computer is attacking and where the vulnerabilities in bitcoin's security lie. This piece will examine bitcoin's encryption, the process by which a quantum algorithm can break it, and the significance of Google's recent quantum computing paper, which has revised the timeline for such an attack. Bitcoin utilizes a system known as elliptic curve cryptography to verify ownership. Each 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. This 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 the public key. While it's straightforward to calculate the public key from the private key, reversing this process is virtually impossible for classical computers due to the elliptic curve discrete logarithm problem. This one-way function is the foundation of bitcoin's security model. The private key serves as proof of ownership, and the public key can be shared safely because classical computers cannot reverse the mathematics. When sending bitcoin, the wallet uses the private key to generate a digital signature, proving knowledge of the secret number without revealing it. 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 in polynomial time, meaning the difficulty increases slowly as numbers get larger. The intuition behind how it works relates to the quantum properties discussed in the first part of this series. The algorithm converts the problem of finding the private key into finding the period of a function related to the elliptic curve. This function takes a number as input and returns a point on the curve, and as sequential numbers are input, the outputs eventually cycle. Knowing the length of this cycle allows for the immediate recovery of the private key. Finding this period is exactly what quantum computers are designed for. They can put their input register into a superposition, representing all possible values simultaneously, apply the function to all of them at once, and then apply a quantum operation called the Fourier transform to reinforce the correct answers while canceling out the wrong ones. Upon measurement, the period appears, from which ordinary mathematics can recover the private key. This attack utilizes all three quantum properties: superposition for evaluating the function on all inputs simultaneously, entanglement to keep inputs and outputs correlated, and interference to filter out noise until only the correct answer remains. Despite Shor's algorithm being known for over 30 years, the reason bitcoin remains secure is that running the algorithm requires a quantum computer with a sufficiently large number of stable qubits to maintain coherence throughout the calculation. Google's recent paper, with contributions from the Ethereum Foundation and Stanford, has significantly reduced the estimated number of qubits needed, from millions to fewer than 500,000, a roughly 20-fold reduction. The team designed 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. Because qubits constantly lose their quantum state, hundreds of redundant qubits are needed to maintain a single reliable logical qubit, explaining the large ratio between physical and logical qubits. Google's paper not only reduced qubit counts but also introduced a practical attack scenario. Parts of Shor's algorithm that depend on the elliptic curve's fixed, publicly known parameters can be precomputed, allowing the quantum computer to sit in a primed state, halfway through the calculation, waiting for a target public key to appear. Once a public key is broadcast or exposed on the blockchain, 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, a quantum 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 6.9 million bitcoin, roughly one-third of the total supply, sitting in wallets where the public key has been permanently exposed on the blockchain. These coins are vulnerable to an 'at-rest' attack that does not require racing against the clock. A quantum computer running Shor's algorithm can turn a bitcoin public key into the controlling private key. For coins transacted since the Taproot upgrade, the public key is already visible, while for coins in older addresses, the public key is hidden until spent, at which point the owner has roughly nine minutes before an attacker could derive the private key.