The Quantum Threat to Bitcoin: How Your Coins Can Be Stolen in Under 10 Minutes

The first part of this series delved into the physics of quantum computing, explaining how it differs from classical computing. However, understanding the inner workings of a quantum computer is not enough to comprehend how it can be used to steal bitcoin. To grasp this, one must understand the target - how bitcoin's security is built, where the weaknesses lie, and the role of quantum algorithms in exploiting these vulnerabilities. This piece begins with an examination of bitcoin's encryption, specifically the elliptic curve cryptography that underpins it, and progresses to the 'nine-minute window' identified by Google's recent quantum computing paper. 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 location, taking a certain number of steps defined by the curve's math leads to a public key. Anyone can verify the public key, but no classical computer can reverse the process to find the private key. The security of bitcoin relies on this one-way trapdoor, with the private key serving as proof of ownership and the public key being safe to share. However, a quantum algorithm known as Shor's algorithm can break this trapdoor. Discovered by mathematician Peter Shor in 1994, this algorithm efficiently solves the discrete logarithm problem, which is the backbone of bitcoin's encryption. The algorithm works by converting the problem of finding a private key into a problem of finding the period of a function. Quantum computers are particularly adept at finding such periods due to their ability to exist in multiple states simultaneously (superposition), perform operations on all states at once, and then filter out incorrect answers through interference. The process involves representing all possible values simultaneously, applying a function to all of them, and then using a quantum operation called the Fourier transform to cancel out wrong answers. The result is the period, from which the private key can be easily derived. This capability is precisely what threatens bitcoin's security. Although Shor's algorithm has been known for over 30 years, its application has been hindered by the requirement for a quantum computer with a large number of stable qubits. Recent advancements, including a paper by Google's Quantum AI division, have significantly reduced the estimated number of qubits needed, from millions to fewer than 500,000. The paper introduced two quantum circuits that implement Shor's algorithm against bitcoin's specific elliptic curve, requiring approximately 1,200 to 1,450 logical qubits. Because qubits are prone to losing their quantum state, a significant portion of a quantum computer is dedicated to error correction, with hundreds of physical qubits needed to maintain a single logical qubit. The introduction of a practical attack scenario by Google's paper changes the perspective on the threat. Parts of Shor's algorithm can be precomputed, allowing the quantum computer to be in a 'primed' state, ready to finish the calculation once a target public key appears. Google estimates that finishing the second half of the calculation takes about nine minutes. Given that 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. This 'mempool attack' gives the attacker a 41% chance of succeeding before the original transaction confirms. More concerning is the vulnerability of the 6.9 million bitcoin (about one-third of the total supply) that have had their public keys exposed on the blockchain. These coins are susceptible to an 'at-rest' attack, where the attacker can take as long as needed to derive the private key without racing against the clock. The implications of this vulnerability and the rapid advancement of quantum computing hardware will be explored in the next piece of this series.