How Quantum Computers Can Compromise Bitcoin Security in Under 10 Minutes

The first part of this series explored the fundamental principles of quantum computing, highlighting its distinction from regular computing. However, understanding the operational mechanics of quantum computers does not directly reveal how they can be exploited to steal bitcoin. To grasp this, it's essential to comprehend what quantum computers attack and the inherent vulnerabilities in bitcoin's security framework. This piece begins by dissecting bitcoin's encryption system, which relies on elliptic curve cryptography to verify ownership. Each wallet possesses a pair of keys: a private key, kept secret, and a public key, derived from the private key through a specific mathematical operation on the 'secp256k1' curve. This process can be visualized as a one-way map, where starting from a known point (generator point G), a series of steps defined by the curve's mathematics leads to a public key (point K). While anyone can confirm the endpoint, determining the exact number of steps taken (the private key) is virtually impossible for classical computers. This one-way function is the backbone of bitcoin's security model, with private keys serving as proof of ownership and public keys being safe to share due to the impracticality of reversing the math for classical computers. When a bitcoin transaction is made, the wallet uses the private key to create a digital signature, proving knowledge of the secret number without revealing it. However, the discovery of Shor's algorithm by mathematician Peter Shor in 1994 introduced a quantum approach that can efficiently break this one-way trapdoor. Shor's algorithm solves the discrete logarithm problem in polynomial time, unlike classical algorithms which would take longer than the universe's age for a 256-bit curve. The algorithm works by converting the problem of finding a private key into finding the period of a function related to the elliptic curve. This is achieved by leveraging quantum properties: superposition allows the function to be evaluated on all possible inputs simultaneously, entanglement correlates inputs and outputs, and interference filters out incorrect answers. The period, once found, allows for the straightforward calculation of the private key. Despite Shor's algorithm being known for over 30 years, its implementation has been hindered by the requirement for a quantum computer with a sufficient 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, making the threat more tangible. The paper introduced two quantum circuits for Shor's algorithm against bitcoin's elliptic curve, requiring approximately 1,200 and 1,450 logical qubits, respectively. The practical attack scenario presented involves precomputing parts of the algorithm that depend on the elliptic curve's fixed parameters, allowing the quantum computer to sit in a primed state. Upon encountering a target public key, the machine only needs to complete the second half of the calculation, which Google estimates takes about nine minutes. This timeline introduces a 'mempool attack' scenario, where an attacker has roughly nine minutes to derive a private key and submit a competing transaction before the original transaction confirms, given that bitcoin's average block confirmation time is 10 minutes. The attacker has a 41% chance of succeeding in this timeframe. 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, as these are susceptible to an 'at-rest' attack that doesn't race against the clock. The implications of these findings, including the impact of Taproot and the rapid advancement of quantum hardware, will be explored in the next piece.