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

The first part of this series explored the fundamental principles of quantum computing. However, understanding the inner workings of a quantum computer is only half the story; the real concern is how it can be utilized to compromise bitcoin's security. To grasp this, we must examine the target: the encryption methods used by bitcoin, why a quantum algorithm can break it, and the significance of Google's recent paper in altering the timeline of this threat. Bitcoin relies on elliptic curve cryptography, which involves a pair of keys: a private key and a public key. The public key is derived from the private key through a mathematical operation on a specific curve known as 'secp256k1'. This process can be visualized as a one-way map, where starting from a known point on the curve, a series of steps defined by the curve's mathematics leads to the public key. The number of steps taken is the private key, and while it's straightforward to verify the endpoint (public key), determining the number of steps (private key) from the public key is practically impossible for classical computers. This one-way function is the cornerstone of bitcoin's security model. Your private key serves as proof of ownership, and your public key can be shared safely because classical computers cannot reverse the mathematical process. When sending bitcoin, your wallet uses the private key to create a digital signature, proving knowledge of the secret number without revealing it. However, the advent of quantum computing, particularly through Shor's algorithm discovered in 1994, poses a significant threat to this security model. Shor's algorithm efficiently solves the discrete logarithm problem, which is the backbone of elliptic curve cryptography's security. By leveraging quantum properties such as superposition, entanglement, and interference, a quantum computer can find the period of a function related to the elliptic curve, which in turn reveals the private key. The intuition behind Shor's algorithm lies in its ability to convert the problem into finding the period of a function that cycles through points on the elliptic curve. Quantum computers are ideally suited for this task, as they can apply the function to all possible inputs simultaneously and then use a quantum operation called the Fourier transform to filter out incorrect answers. The recent paper by Google's Quantum AI division, in collaboration with researchers from the Ethereum Foundation and Stanford, has significantly reduced the estimated number of qubits needed to run Shor's algorithm against bitcoin's elliptic curve from millions to fewer than 500,000. This reduction is substantial, lowering the barrier to a potential quantum attack. The team designed quantum circuits that implement Shor's algorithm, with estimates suggesting the need for approximately 1,200 to 1,450 logical qubits and tens of millions of Toffoli gates. A critical aspect of this attack is the distinction between physical and logical qubits; due to the fragile nature of qubits, hundreds of physical qubits are required to maintain a single reliable logical qubit. The paper introduced a practical attack scenario where parts of Shor's algorithm that depend on publicly known parameters of the elliptic curve can be precomputed, allowing the quantum computer to sit in a primed state, ready to finish the calculation once a target public key appears. This leads to a 'nine-minute window' where, if a user broadcasts a transaction and their public key becomes visible, a quantum attacker has roughly nine minutes to derive the private key and submit a competing transaction. Given that bitcoin's average block confirmation time is 10 minutes, this gives the attacker a roughly 41% chance of succeeding. While this 'mempool attack' is alarming, it's more concerning that approximately 6.9 million bitcoin, or one-third of the total supply, are already vulnerable to an 'at-rest' attack because their public keys have been permanently exposed on the blockchain. These coins can be targeted without any time constraint, as the attacker can take as long as needed to derive the private key. The implications of this vulnerability, especially in light of Taproot's effects on bitcoin transactions and the rapid advancement of quantum hardware, will be explored in the next piece of this series.