The Quantum Threat to Bitcoin: How Your Cryptocurrency Could Be Stolen in Under 10 Minutes

The first part of this series explored the fundamentals of quantum computing, introducing the physics that underpin this revolutionary technology. However, understanding how quantum computers work is only half the story; the critical question is how they can be exploited by malicious actors to compromise bitcoin's security. This piece will examine the target of such an attack: the encryption that safeguards bitcoin transactions, why a quantum algorithm can break it, and the significance of Google's recent paper in altering the timeline for potential quantum attacks. The security of bitcoin transactions relies on a system known as elliptic curve cryptography. Each bitcoin 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 visualized 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 mathematics leads to a public key. Anyone can verify that the public key corresponds to the starting point, but reversing the process to find the private key is virtually impossible for classical computers. The elliptic curve discrete logarithm problem, which involves finding the private key given the public key and the generator point, is so computationally intensive that even the fastest classical computers would take longer than the age of the universe to solve it for a 256-bit curve. The breakthrough came with Peter Shor's quantum algorithm in 1994, which can efficiently solve the discrete logarithm problem. This algorithm works by converting the problem into finding the period of a function related to the elliptic curve, a task that quantum computers are particularly suited for due to their ability to evaluate functions on multiple inputs simultaneously (superposition), maintain correlations between inputs and outputs (entanglement), and filter out incorrect answers (interference). Despite Shor's algorithm being known for over 30 years, its application has been hindered by the need for a quantum computer with a sufficiently large number of stable qubits to maintain coherence throughout the calculation. Recent estimates by Google's Quantum AI division, in collaboration with researchers from the Ethereum Foundation and Stanford, have significantly reduced the number of qubits required, from millions to fewer than 500,000. This reduction is crucial because it brings the feasibility of a quantum attack on bitcoin's encryption closer to reality. 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. Given the need for redundant qubits to maintain a single reliable logical qubit due to qubit instability, the actual number of physical qubits needed would be much higher. The introduction of a practical attack scenario by Google's paper changes the perspective on the quantum threat. Parts of Shor's algorithm that depend on fixed, publicly known parameters of the elliptic curve can be precomputed, allowing a quantum computer to sit in a primed state, ready to finish the calculation once a target public key is identified. This could happen in about nine minutes, a timeframe that is alarmingly close to bitcoin's average block confirmation time of 10 minutes. If a user broadcasts a transaction, making their public key visible, a quantum attacker has roughly nine minutes to derive the private key and submit a competing transaction. The odds of success are about 41% in this 'mempool attack' scenario. More concerning, however, is the vulnerability of the 6.9 million bitcoin (about one-third of the total supply) that have had their public keys permanently exposed on the blockchain. These coins are susceptible to an 'at-rest' attack, which does not require racing against the clock. The implications of this vulnerability, the impact of Taproot on bitcoin's privacy, and how the advancing hardware is narrowing the gap to a potential quantum attack are subjects for further exploration.