How Quantum Computing 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 classical computing. However, understanding the inner workings of a quantum computer does not directly reveal how it can be utilized to steal bitcoin. To grasp this, one must comprehend the target of the attack - the security structure of bitcoin - and where its vulnerabilities lie. This piece commences with an examination of bitcoin's encryption methodology, progressing to the recently identified nine-minute window required to breach it, as outlined in Google's quantum computing paper. Bitcoin employs a system known as elliptic curve cryptography to verify ownership. Each wallet possesses 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 can be visualized as a one-way map, where starting from a known point on the curve, taking a certain number of steps (defined by the private key) leads to a public key. While moving forward in this map is straightforward, reversing the process is virtually impossible for classical computers. This one-way function is the backbone of bitcoin's security model, allowing users to prove ownership without revealing their private keys. The introduction of Shor's algorithm by mathematician Peter Shor in 1994 marked a significant turning point. This quantum algorithm efficiently solves the discrete logarithm problem, which classical computers cannot. The algorithm works by converting the problem into finding the period of a function related to the elliptic curve, a task that quantum computers are well-suited for due to their ability to represent multiple values simultaneously and perform operations on them in parallel. By applying the function to all possible inputs at once and then using a Fourier transform to filter out incorrect answers, the period - and thus the private key - can be determined. This process leverages the principles of superposition, entanglement, and interference, showcasing the unique capabilities of quantum computing. Despite Shor's algorithm being known for over 30 years, its application has been hindered by the requirement for a quantum computer with a sufficiently large number of stable qubits to maintain coherence throughout the calculation. Google's recent paper reduced the estimated number of qubits needed from millions to fewer than 500,000, significantly narrowing the gap. The paper proposed two quantum circuits that implement Shor's algorithm against bitcoin's elliptic curve, each requiring approximately 1,200 to 1,450 logical qubits and tens of millions of Toffoli gates. Given the constant loss of quantum state in qubits, the actual number of physical qubits required is much higher, due to the need for redundancy to maintain a single reliable logical qubit. The paper also introduced a practical attack scenario, suggesting that parts of Shor's algorithm can be precomputed, allowing the quantum computer to be in a primed state, ready to complete the calculation once a target public key is identified. This leads to a nine-minute window for the attack, which is particularly concerning given bitcoin's average block confirmation time of 10 minutes. If a user broadcasts a transaction with an exposed public key, an attacker has roughly nine minutes to derive the private key and submit a competing transaction. For the approximately 6.9 million bitcoin with public keys already exposed on the blockchain, the threat is even more pressing, as these coins are vulnerable to attack without any time constraint.