The Quantum Threat to Bitcoin: How Your Coins Can Be Stolen in Under 10 Minutes

The first part of this series delved into the fundamentals of quantum computing, explaining how these machines differ from classical computers and the unique properties that make them powerful. However, understanding the basics of quantum computing doesn't reveal how it can be used to compromise bitcoin security. To grasp this, one must understand what bitcoin's security is based on and where its weaknesses lie. This article will delve into bitcoin's encryption, how a quantum algorithm can break it, and the implications of a recent paper by Google on the timeline of this threat. 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 specific mathematical operation on the elliptic curve. 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 your private key) leads you to your public key. While it's easy to go forward (from private to public key), reversing the process (from public to private key) 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 age of the universe to solve for a 256-bit curve. The security of bitcoin relies on this one-way trapdoor, with your private key serving as proof of ownership and your public key being safe to share since no classical computer can reverse the math. When sending bitcoin, your wallet uses the private key to create a digital signature, proving you know the secret number without revealing it. However, a quantum algorithm known as Shor's algorithm, discovered by mathematician Peter Shor in 1994, can efficiently break this trapdoor. Shor's algorithm solves the discrete logarithm problem in polynomial time, meaning the difficulty increases slowly as numbers get bigger. The algorithm works by converting the problem of finding the private key into finding the period of a function related to the elliptic curve. This is where quantum computers excel, as 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 use a quantum operation called the Fourier transform to find the period. From this period, the private key can be recovered, allowing access to the bitcoin. This attack utilizes the three key properties of quantum mechanics: superposition, entanglement, and interference. 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. Recent estimates by Google, in collaboration with researchers from the Ethereum Foundation and Stanford, have significantly reduced the 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 practical implication of this research is not just the reduction in qubit count but the introduction of a realistic attack scenario. Parts of Shor's algorithm that depend on the elliptic curve's fixed parameters can be precomputed, allowing the quantum computer to be in a primed state, waiting for a target public key to appear. Once a public key is visible, whether in a transaction waiting to be confirmed or already 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 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 compromised without any time constraint, as the attacker can take as long as needed to derive the private key. The implications of this vulnerability, the impact of Taproot on bitcoin privacy, and how quickly hardware is advancing to pose a real threat will be explored in the final piece of this series.