The Quantum Threat to Bitcoin: How a 9-Minute Window Can Compromise Your Cryptocurrency

The first part of this series introduced the fundamental principles of quantum computing, distinguishing it from classical computing. However, understanding the inner workings of a quantum computer does not directly reveal how it can be utilized to steal bitcoin. To grasp this, one must comprehend the target of such an attack - the security framework of bitcoin, specifically how its encryption functions, why a quantum algorithm can bypass it, and the significance of Google's recent paper in altering the timeline of potential threats. This piece begins by examining bitcoin's encryption, progressing to the nine-minute window, as identified by Google's research, within which an attack can be successful. Bitcoin employs a system known as elliptic curve cryptography to verify ownership. Each wallet possesses two keys: a private key, which is a secret number approximately 256 digits long in binary, and a public key derived from the private key through a mathematical operation on a specific curve known as 'secp256k1'. This process can be visualized as a one-way map, where starting from a known location on the curve, taking a certain number of steps defined by the curve's mathematics leads to a public key. Anyone can confirm the endpoint but not trace back the steps taken. Technically, this is expressed as K = k × G, where k is the private key, and K is the public key. The 'multiplication' here is a geometric operation, not conventional multiplication, resulting in a seemingly random spot on the curve that only the specific number k could produce. The critical property of this system is that moving forward is straightforward, while reversing the process is virtually impossible for classical computers. If one knows k and G, calculating K takes mere milliseconds, but if one knows K and G and seeks to find k, they are faced with the elliptic curve discrete logarithm problem, which classical algorithms would take longer than the age of the universe to solve for a 256-bit curve. This one-way trapdoor is the backbone of bitcoin's security model. Your private key serves as proof of ownership, and your public key is safe to share because no classical computer can reverse the mathematics. When sending bitcoin, the wallet uses the private key to create a digital signature, a mathematical proof that you know the secret number without revealing it. However, Shor's algorithm, discovered in 1994, breaks this trapdoor by solving the discrete logarithm problem efficiently. This quantum algorithm converts the problem into finding the period of a function, which represents the length of a cycle of outputs when feeding sequential numbers into a function related to the elliptic curve. Finding this period is exactly what quantum computers are designed for, utilizing superposition to represent all possible values simultaneously, applying the function to all of them at once, and then applying a quantum operation called the Fourier transform to reinforce the correct answers while canceling out the wrong ones. The result, upon measurement, yields the period, from which ordinary mathematics can quickly recover k, the private key, and thus control over the coins. The attack leverages all three quantum properties: superposition evaluates the function on every possible input at once, entanglement links the input and output to keep results correlated, and interference filters the noise until only the answer remains. Despite Shor's algorithm being known for over 30 years, the reason bitcoin remains secure is that executing this algorithm requires a quantum computer with a sufficiently large number of stable qubits to maintain coherence throughout the calculation. Previous estimates suggested millions of physical qubits were needed, but Google's paper reduced this requirement to fewer than 500,000, a roughly 20-fold reduction. The team designed quantum circuits implementing Shor's algorithm against bitcoin's specific elliptic curve, one using approximately 1,200 logical qubits and 90 million Toffoli gates, and the other using about 1,450 logical qubits and 70 million Toffoli gates. A Toffoli gate is a type of gate acting on three qubits, where two control qubits affect the state of a third target qubit. Due to qubits constantly losing their quantum state, hundreds of redundant qubits are needed to maintain a single reliable logical qubit, with most of the quantum computer's infrastructure dedicated to error correction. Google's paper introduced a practical attack scenario, where parts of Shor's algorithm depending 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 upon encountering a target public key. This reduces the time needed to derive a private key to about nine minutes, according to Google's estimates. Given bitcoin's average block confirmation time of 10 minutes, a quantum attacker has roughly nine minutes to derive a private key and submit a competing transaction after a user broadcasts a transaction with their public key visible in the mempool. This gives the attacker a roughly 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, or one-third of the total supply, sitting 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 running Shor's algorithm can turn a bitcoin public key into the private key controlling the coins, with no time constraint. For coins transacted since the Taproot upgrade, the public key is already visible, and for coins in older addresses, the public key is hidden until spent, at which point the owner has roughly nine minutes before an attacker can derive the private key.