The Quantum Threat to Bitcoin: How a 9-Minute Window Can Compromise Your Funds

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 could be exploited to steal bitcoin. To grasp this, one must comprehend what quantum computers are capable of attacking, specifically how bitcoin's security is structured, and where the weaknesses lie. This piece begins with an examination of bitcoin's encryption method, known as elliptic curve cryptography, which is crucial for verifying ownership. Every bitcoin 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. The relationship between the private and public keys can be thought of as a one-way map, where starting from a known point on the curve (the generator point G), taking a certain number of steps defined by the curve's mathematics leads to the public key. This process, while easy to perform in one direction, is virtually impossible to reverse with 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. The security of bitcoin relies on this one-way trapdoor, with the private key serving as proof of ownership and the public key being safe to share. When sending bitcoin, the wallet uses the private key to create a digital signature, proving knowledge of the secret number without revealing it. The discovery of Shor's algorithm by mathematician Peter Shor in 1994 introduced a quantum approach that can efficiently break this trapdoor. Shor's algorithm solves the discrete logarithm problem in polynomial time, leveraging the unique properties of quantum mechanics. It works by converting the problem into finding the period of a function related to the elliptic curve, which, once known, allows for the immediate derivation of the private key. This process exploits the principles of superposition, where a quantum computer can represent all possible values simultaneously, and interference, which filters out incorrect answers. The algorithm's efficiency is rooted in its ability to apply a function to all possible inputs at once and then use a quantum operation, the Fourier transform, to reinforce the correct answers while canceling out the incorrect ones. The practical application of Shor's algorithm against bitcoin's encryption has been limited by the requirement for a quantum computer with a large number of stable qubits. Recent estimates by Google, in collaboration with researchers from the Ethereum Foundation and Stanford, have significantly reduced the number of qubits needed, from millions to fewer than 500,000. This reduction is based on designing quantum circuits that implement Shor's algorithm against bitcoin's specific elliptic curve, requiring approximately 1,200 to 1,450 logical qubits and tens of millions of Toffoli gates. A key aspect of this breakthrough is the introduction of a practical attack scenario, where parts of the calculation can be precomputed, allowing the quantum computer to be 'primed' and ready to finish the calculation once a target public key is identified. Google estimates that this second part of the calculation could take approximately nine minutes, which is close to bitcoin's average block confirmation time of 10 minutes. This creates a narrow window for a quantum attacker to derive a private key and submit a competing transaction, posing a significant threat, especially to the 6.9 million bitcoin that have their public keys exposed on the blockchain, making them vulnerable to an 'at-rest' attack without any time constraint.