How Quantum Computing Can Compromise Bitcoin Security in Under 10 Minutes

The first part of this series delved into the physics underlying quantum computing, revealing it as a distinct type of machine that leverages the unique rules of physics at the atomic and particle level. However, understanding how quantum computers work doesn't directly explain how they can be used to steal bitcoin. To grasp this, one must comprehend what quantum computers are attacking - specifically, how bitcoin's security is structured and where its vulnerabilities lie. This piece begins by examining bitcoin's encryption, leading to the nine-minute window, as identified by Google's recent quantum computing paper, within which it can be broken. Bitcoin utilizes elliptic curve cryptography to verify ownership, with each wallet possessing a private key (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 (the generator point G), taking a certain number of steps defined by the curve's math (the private key) leads to a public key (point K). Anyone can verify the public key, but determining the private key from it is virtually impossible for classical computers due to the elliptic curve discrete logarithm problem, which would take longer than the age of the universe to solve with current algorithms. However, Peter Shor's quantum algorithm, discovered in 1994, efficiently solves this problem by exploiting quantum properties. It converts the problem into finding a function's period, which, once known, allows for the immediate derivation of the private key. This is feasible for quantum computers due to their ability to evaluate functions on all possible inputs simultaneously (superposition), maintain correlated results (entanglement), and filter out incorrect answers (interference). 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. A recent Google paper, in collaboration with the Ethereum Foundation and Stanford, significantly reduced the estimated number of qubits needed from millions to fewer than 500,000, introducing a practical attack scenario. The paper designed quantum circuits that implement Shor's algorithm against bitcoin's elliptic curve, with one circuit requiring approximately 1,200 logical qubits and the other 1,450. Given that qubits are highly error-prone and require redundancy for reliable operation, the actual number of physical qubits needed is much higher. The paper also introduced the concept of precomputing parts of the algorithm that depend on fixed, publicly known parameters of the elliptic curve, 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, which is close to bitcoin's average block confirmation time. This creates a 'mempool attack' scenario where an attacker has a roughly 41% chance of redirecting funds before the original transaction confirms. More concerning is the vulnerability of the 6.9 million bitcoin (about one-third of the total supply) in wallets where the public key has been exposed on the blockchain, which can be attacked without time pressure. The implications of this vulnerability and the rapid advancement of quantum computing hardware will be explored in the next part of this series.