The Quantum Threat to Bitcoin: How a Quantum Computer Can Steal Your Crypto in Under 10 Minutes

The first part of this series explored the fundamentals of quantum computing. However, understanding the inner workings of a quantum computer doesn't necessarily reveal how it can be utilized to steal bitcoin. To grasp this, one must comprehend what the quantum computer is targeting, the security framework of bitcoin, and the specific vulnerability it exploits. This piece begins by examining bitcoin's encryption, progressing to the nine-minute window required to breach it, as outlined in Google's recent quantum computing paper. Bitcoin employs a system known as elliptic curve cryptography to verify ownership. Each wallet contains 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 can be thought of as a one-way map, where starting from a known point on the curve and taking a series of steps defined by the curve's mathematics leads to the public key. While moving forward is straightforward, reversing the process to find the private key is virtually impossible for classical computers due to the elliptic curve discrete logarithm problem. The best classical algorithms would take longer than the universe's age to solve this for a 256-bit curve. This one-way function is the cornerstone of bitcoin's security model. Your private key proves ownership, and your public key is safe to share since no classical computer can reverse the math. When sending bitcoin, your wallet uses the private key to create a digital signature, proving knowledge of the secret number without revealing it. However, Shor's algorithm, discovered by mathematician Peter Shor in 1994, breaks this one-way trapdoor using quantum computing. It solves the discrete logarithm problem efficiently, handling in polynomial time what would take a classical computer an impractically long time. The algorithm converts finding the private key into a problem of finding the period of a function related to the elliptic curve. Quantum computers are particularly adept at finding this period due to their ability to represent all possible inputs simultaneously (superposition), apply a function to all these inputs at once, and then use the Fourier transform to reinforce correct answers while canceling out incorrect ones. This process leverages superposition, entanglement, and interference - the three quantum properties highlighted in the first part of this series. Despite Shor's algorithm being known for over 30 years, its application has been hindered by the requirement for a large number of stable qubits to maintain coherence throughout the calculation. Google's recent paper significantly reduced the estimated number of qubits needed, from millions to fewer than 500,000, by designing quantum circuits that implement Shor's algorithm against bitcoin's specific elliptic curve. This reduction, a roughly 20-fold decrease from prior estimates, brings the threat closer to reality. The paper introduced a practical attack scenario where parts of the calculation can be precomputed and stored, waiting for a target public key to appear. Upon detecting a public key, the quantum computer can finish the calculation in about nine minutes, according to Google's estimates. This timeline is critical because it's comparable to bitcoin's average block confirmation time of 10 minutes. An attacker has a window of opportunity to derive a private key and submit a competing transaction that redirects funds, with a roughly 41% chance of succeeding before the original transaction confirms. While this 'mempool attack' is alarming, it requires a quantum computer that does not yet exist. A more pressing concern is the 6.9 million bitcoin (approximately one-third of the total supply) in wallets where the public key has been permanently exposed on the blockchain. These coins are vulnerable to an 'at-rest' attack, where a quantum computer running Shor's algorithm can turn a bitcoin public key into the private key without any time constraint. For coins transacted since the Taproot upgrade, the public key is already visible, making them susceptible. For older addresses, the public key remains hidden until spent, at which point the nine-minute window begins. The practical implications of this, including which 6.9 million bitcoin are exposed and how Taproot affects this vulnerability, will be explored in the next piece of this series.