How Quantum Computing Can Compromise Bitcoin Security in Under 10 Minutes

The first part of this series provided an overview of quantum computing, highlighting its unique capabilities and differences from classical computing. However, understanding the inner workings of a quantum computer is only half the story; the real concern lies in how it can be utilized to breach bitcoin's security. This piece will examine the target of such an attack: the encryption mechanism that underpins bitcoin, and how a quantum algorithm can potentially break it, with insights from Google's recent paper that has revised the timeline for such an event. Bitcoin's security relies on elliptic curve cryptography, a system that involves 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 the public key. While moving forward in this map is straightforward, reversing the process to find the private key from the public key is virtually impossible for classical computers due to the elliptic curve discrete logarithm problem. The estimated time for classical algorithms to solve this problem for a 256-bit curve exceeds the age of the universe. The security of bitcoin hinges on this one-way trapdoor, where the private key proves ownership, and the public key can be safely shared without risking the private key's secrecy. However, the discovery of Shor's algorithm by mathematician Peter Shor in 1994 introduced a quantum approach that can efficiently solve the discrete logarithm problem. This algorithm leverages the unique properties of quantum computing: superposition, entanglement, and interference. By converting the problem into finding the period of a function related to the elliptic curve, Shor's algorithm can find the private key given the public key and the curve's parameters. The process involves representing all possible inputs simultaneously in a superposition, applying the function to all inputs at once, and then using the Fourier transform to filter out incorrect answers, leaving the correct period and subsequently the private key. Despite Shor's algorithm being known for over 30 years, its application has been hindered by the requirement for a quantum computer with a sufficient number of stable qubits to maintain coherence throughout the calculation. Recent research by Google's Quantum AI division, in collaboration with the Ethereum Foundation and Stanford cryptographer Dan Boneh, has significantly reduced the estimated number of qubits needed, from millions to fewer than 500,000, a reduction of about 20-fold. This research 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. Given that qubits are prone to losing their quantum state, the need for redundancy means that most of a quantum computer's infrastructure is dedicated to error correction, with a roughly 400-to-1 ratio between physical and logical qubits. The introduction of a practical attack scenario by Google's paper has significant implications. 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, ready to finalize the calculation once a target public key is identified. This reduces the time needed to derive a private key from a public key to about nine minutes, according to Google's estimates. Considering bitcoin's average block confirmation time is 10 minutes, this gives a quantum attacker a window of opportunity to derive a private key and submit a competing transaction that could redirect funds, with a roughly 41% chance of succeeding before the original transaction is confirmed. This 'mempool attack' is alarming but requires a quantum computer that does not yet exist. A more pressing concern is the approximately 6.9 million bitcoin (about one-third of the total supply) that are already vulnerable due to their public keys being exposed on the blockchain. For these coins, a quantum computer running Shor's algorithm could derive the private key without any time constraint, posing a significant threat. The practical implications of these findings, including which 6.9 million bitcoin are exposed, the impact of Taproot, and how quickly hardware is advancing, will be explored in the final piece of this series.