The Quantum Threat to Bitcoin: How a Quantum Computer Can Steal Your Cryptocurrency in Under 10 Minutes

This series explores the intersection of quantum computing and cryptocurrency. The first part delved into the physics behind quantum computers, highlighting their unique capabilities and potential applications. However, understanding the inner workings of a quantum computer doesn't necessarily reveal how it could be used to compromise bitcoin. To grasp this, it's essential to comprehend what a quantum computer is attacking, the security mechanisms of bitcoin, and the specific vulnerabilities involved. This piece begins with an examination of bitcoin's encryption methods, discussing how a quantum algorithm can break them and the significance of Google's recent quantum computing paper, which identified a nine-minute window for such an attack. Bitcoin utilizes elliptic curve cryptography to verify ownership. Each wallet has two keys: a private key, which is a secret 256-digit binary number, and a public key derived from the private key through a mathematical operation on the secp256k1 curve. This process can be thought of as a one-way map, where starting from a known point (the generator point G), taking a certain number of steps defined by the curve's math leads to the public key. Anyone can verify the public key, but determining the private key (the number of steps taken) is virtually impossible for classical computers. Technically, this is represented as K = k × G, where k is the private key, and K is the public key. The 'multiplication' here is a geometric operation that involves repeatedly adding a point to itself along the curve, resulting in a seemingly random spot that corresponds to the private key k. The crucial aspect of this system is that calculating K from k and G is straightforward, but the reverse—finding k from K and G—is effectively impossible for classical computers, known as the elliptic curve discrete logarithm problem. It's estimated that solving this problem for a 256-bit curve using the best-known classical algorithms would take longer than the age of the universe. This one-way function is the core of bitcoin's security model. The private key proves ownership, and the public key can be shared safely because classical computers cannot reverse the math. When sending bitcoin, the wallet uses the private key to create a digital signature, proving knowledge of the secret number without revealing it. However, in 1994, mathematician Peter Shor discovered a quantum algorithm that can break this one-way trapdoor. Shor's algorithm efficiently solves the discrete logarithm problem, something that would take a classical computer an impractically long time. The intuition behind Shor's algorithm relates to the three quantum properties discussed earlier: superposition, entanglement, and interference. The algorithm converts the problem of finding the private key k, given the public key K and the generator point G, into finding the period of a function that maps numbers to points on the elliptic curve. Quantum computers are particularly suited for finding this period because they can apply the function to all possible inputs simultaneously due to superposition, and then use the Fourier transform to reinforce the correct answers while canceling the incorrect ones. Once the period is found, ordinary math can quickly recover the private key k. This attack utilizes all three quantum properties: superposition to evaluate the function on all inputs at once, entanglement to keep the input and output correlated, and interference to filter out noise and retain the answer. 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. Recent estimates have significantly reduced the number of qubits needed, from millions to fewer than 500,000, based on a paper by Google's Quantum AI division. The team designed quantum circuits that implement Shor's algorithm against bitcoin's elliptic curve, requiring approximately 1,200 to 1,450 logical qubits and tens of millions of Toffoli gates. A significant challenge in quantum computing is that qubits constantly lose their quantum state, necessitating hundreds of redundant qubits to maintain a single reliable logical qubit. Most of a quantum computer's infrastructure is dedicated to error correction. Google's paper introduced a practical attack scenario, where parts of Shor's algorithm that depend on the elliptic curve's fixed parameters can be precomputed, allowing the quantum computer to sit in a primed state, ready to finish the calculation once a target public key is identified. The second half of the calculation, which depends on the specific public key, is estimated to take about nine minutes. Given that bitcoin's average block confirmation time is 10 minutes, a quantum attacker has a window of opportunity to derive a private key and submit a competing transaction. The math suggests the attacker has a roughly 41% chance of succeeding 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 6.9 million bitcoin (about one-third of the total supply) in wallets where the public key has been permanently exposed on the blockchain, making them vulnerable to an 'at-rest' attack that doesn't require racing against the clock. A quantum computer running Shor's algorithm can turn a bitcoin public key into the private key that controls the coins, posing a significant threat to the security of the bitcoin network.