How Quantum Computers Can Compromise Bitcoin Security in Under 10 Minutes

This series' first part delved into the fundamentals of quantum computing, exploring its underlying physics and how it differs from classical computing. However, understanding the mechanics of quantum computers doesn't directly reveal how they can be exploited to steal bitcoin. To grasp this, one must comprehend what quantum computers are attacking, the nature of bitcoin's security, and where its weaknesses lie. This piece begins by dissecting bitcoin's encryption, tracing the process to the critical nine-minute window identified by Google's recent quantum computing paper. Bitcoin utilizes elliptic curve cryptography to verify ownership, a system based on a one-way function. Each wallet contains 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 derivation can be thought of as a one-way map where, starting from a known point (generator point G), taking a certain number of steps (defined by the private key) leads to a public key (point K). While it's straightforward to verify that the public key corresponds to the private key, reversing this process (finding the private key from the public key) is virtually impossible for classical computers due to the elliptic curve discrete logarithm problem. It's estimated that solving this problem for a 256-bit curve with the best-known classical algorithms would take longer than the age of the universe. This one-way trapdoor is the cornerstone of bitcoin's security model. The private key serves as proof of ownership, and the public key can be safely shared because classical computers cannot reverse the mathematical operation. When sending bitcoin, the wallet uses the private key to create a digital signature, proving knowledge of the secret number without revealing it. However, Peter Shor's 1994 discovery of a quantum algorithm capable of breaking this trapdoor changes the landscape. Shor's algorithm efficiently solves the discrete logarithm problem, leveraging quantum properties to find the private key from the public key and generator point. The algorithm involves converting the problem into finding the period of a function related to the elliptic curve and applies quantum operations like superposition and the Fourier transform to solve it efficiently. This process utilizes the principles of superposition (evaluating a function on all possible inputs simultaneously), entanglement (linking input and output), and interference (filtering out incorrect answers) to find the period and, subsequently, the private key. Despite Shor's algorithm being known for over 30 years, its implementation 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 in required qubits brings the threat of quantum attacks closer to reality. The paper also introduced a practical attack scenario, where parts of Shor's algorithm depending on fixed, publicly known parameters can be precomputed, allowing a quantum computer to be 'primed' and ready to derive a private key once a target public key appears. Google estimates this second phase takes about nine minutes, which is alarmingly close to bitcoin's average block confirmation time of 10 minutes. This creates a 'mempool attack' scenario where an attacker has a roughly 41% chance of deriving a private key and submitting a competing transaction before the original transaction confirms. More concerning is the vulnerability of the 6.9 million bitcoin (about one-third of the total supply) with public keys already exposed on the blockchain, which are susceptible to an 'at-rest' attack without any time constraint. The implications of these findings, the current state of quantum hardware, and the potential impacts on bitcoin security are critical considerations moving forward.