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

The first part of this series delved into the physics behind quantum computing, explaining how it differs fundamentally from classical computing. However, understanding the mechanics of quantum computing doesn't directly reveal how it can be used to compromise bitcoin's security. To grasp this, one must comprehend what quantum computers attack and where the vulnerabilities in bitcoin's security lie. This piece begins with an examination of bitcoin's encryption method, known as elliptic curve cryptography, and proceeds to explain how a quantum algorithm can break it, focusing on the recent findings by Google that significantly shorten the time required for such an attack. Bitcoin utilizes a system called elliptic curve cryptography to verify ownership. Each wallet has two 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 process can be thought of as a one-way map, where starting from a known point (generator point G), taking a certain number of steps defined by the curve's mathematics leads to the public key. The number of steps is the private key, and while anyone can verify the public key, determining the private key 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, with the 'multiplication' being a geometric operation along the curve. The crucial aspect of this system is that moving forward (from private to public key) is straightforward, but reversing the process (from public to private key) is effectively impossible for classical computers, due to the elliptic curve discrete logarithm problem. It's estimated that solving this problem for a 256-bit curve with the best-known classical algorithms would take longer than the age of the universe. This one-way function is the backbone of bitcoin's security model. The private key proves ownership, and the public key can be safely shared because no classical computer can 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, Peter Shor's quantum algorithm, discovered in 1994, can efficiently solve the discrete logarithm problem, breaking the one-way trapdoor. Shor's algorithm works by converting the problem of finding the private key into finding the period of a function related to the elliptic curve. Quantum computers are ideal for this task because they can represent all possible inputs simultaneously (superposition), apply the function to all inputs at once, and then use the Fourier transform to reinforce correct answers while canceling out incorrect ones. The period, once found, allows for the easy recovery of the private key, thus compromising the security of the bitcoin. This process utilizes the three key properties of quantum computing: 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 the Ethereum Foundation and Stanford cryptographers, have significantly reduced the number of qubits needed, from millions to fewer than 500,000, a 20-fold reduction. Google 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. Given that qubits lose their quantum state constantly, a large number of physical qubits are needed to maintain a single reliable logical qubit, with most of the quantum computer's infrastructure dedicated to error correction. The introduction of a practical attack scenario by Google changes the perspective on the threat. Parts of Shor's algorithm can be precomputed for bitcoin's elliptic curve, allowing the quantum computer to be in a primed state, 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 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, with a 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 greater 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 does not race against the clock. A quantum computer can turn a bitcoin public key into the private key, controlling the coins, with no time constraint for coins that have been exposed since the Taproot upgrade. The practical implications of this vulnerability, the impact of Taproot, and how quickly hardware is closing the gap to make such attacks feasible, will be explored in the next piece of this series.