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

The first part of this series explored the principles of quantum computing. However, understanding how a quantum computer works is only half the story. To grasp how it can be used to steal bitcoin, one must comprehend what it is attacking and where the vulnerabilities lie. This piece begins by examining bitcoin's encryption and the nine-minute window, as identified by Google's recent quantum computing research, that it takes to break it. Bitcoin utilizes elliptic curve cryptography to verify ownership. Each 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 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 math leads to a public key. Anyone can verify the public key, but no classical computer can deduce the private key due to the elliptic curve discrete logarithm problem. This problem is so complex that even the best classical algorithms would take longer than the age of the universe to solve for a 256-bit curve. The security of bitcoin relies on this one-way trapdoor. When sending bitcoin, the wallet uses the private key to create a digital signature, proving ownership without revealing the secret number. However, Shor's algorithm, discovered in 1994, can break this trapdoor using a quantum computer. It solves the discrete logarithm problem efficiently by converting it into finding the period of a function, which is a task well-suited for quantum computers. The algorithm uses superposition to evaluate the function on all possible inputs simultaneously, entanglement to keep inputs and outputs correlated, and interference to filter out wrong answers. Despite being known for over 30 years, Shor's algorithm has not been a practical threat due to the requirement for a large number of stable qubits to maintain coherence throughout the calculation. Google's recent paper reduced the estimated number of qubits needed from millions to fewer than 500,000, a 20-fold reduction. The team designed quantum circuits that implement Shor's algorithm against bitcoin's elliptic curve, using approximately 1,200 to 1,450 logical qubits and tens of millions of Toffoli gates. A significant portion of a quantum computer's infrastructure is dedicated to maintaining the quantum state of qubits, as they constantly lose coherence. Google's research introduced a practical attack scenario, where parts of Shor's algorithm can be precomputed, allowing the quantum computer to be in a primed state, ready to finish the calculation when a target public key appears. This reduces the time needed to derive a private key to about nine minutes, which is close to bitcoin's average block confirmation time of 10 minutes. If a user broadcasts a transaction with their public key visible, a quantum attacker has roughly nine minutes to derive the private key and submit a competing transaction. This 'mempool attack' gives the attacker about a 41% chance of succeeding before the original transaction confirms. More concerning is the 6.9 million bitcoin, roughly one-third of the total supply, that are already vulnerable to an 'at-rest' attack because their public keys have been permanently exposed on the blockchain. These coins can be compromised without racing against the clock, as the attacker can take as long as needed to derive the private key using Shor's algorithm.