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

The first part of this series explored the fundamentals of quantum computing, but understanding how it works is only half the story. To grasp how a quantum computer can be used to steal bitcoin, one must comprehend what it is attacking - the security framework of bitcoin. This piece begins with an examination of bitcoin's encryption, shedding light on the process and the weakness that a quantum algorithm can exploit, as highlighted in Google's recent quantum computing paper. Bitcoin's security is rooted in a system called elliptic curve cryptography, which involves a pair of keys for each wallet: a private key, kept secret, and a public key, derived from the private key through a mathematical operation on a specific curve known as 'secp256k1'. This process can be thought of as a one-way map, where starting from a known point on the curve, applying a series of steps defined by the curve's mathematics leads to the public key, but reversing this process to find the private key is virtually impossible for classical computers. The crucial aspect of this system is that while moving forward (from private to public key) is straightforward, moving backward is extremely difficult due to what is known as the elliptic curve discrete logarithm problem. It's estimated that solving this problem for a 256-bit curve using the best-known classical algorithms would take longer than the age of the universe. However, in 1994, mathematician Peter Shor discovered a quantum algorithm that can efficiently solve the discrete logarithm problem, thereby breaking the one-way trapdoor that secures bitcoin. Shor's algorithm exploits the properties of quantum computing - superposition, entanglement, and interference - to 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 represent all possible inputs simultaneously, apply a function to them, and then use the Fourier transform to filter out incorrect answers, leaving the correct period and thus the private key. Despite Shor's algorithm being known for over 30 years, the main obstacle to its application has been the requirement for a quantum computer with a sufficiently large number of stable qubits to perform the calculation without error. Recent research by Google, in collaboration with the Ethereum Foundation and Stanford cryptographer Dan Boneh, has 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 more efficiently. This reduction is crucial because it brings the possibility of a quantum attack on bitcoin's encryption closer to reality. The team's designs for quantum circuits that can run Shor's algorithm with approximately 1,200 to 1,450 logical qubits highlight the potential for a practical attack scenario. Furthermore, the research introduces a concept where parts of the calculation can be precomputed, allowing a quantum computer to be in a 'primed' state, ready to finish the calculation once a target public key is identified. This leads to what is known as the 'nine-minute window', where if a user broadcasts a transaction and their public key becomes visible, an attacker has roughly nine minutes to derive the private key and submit a competing transaction, given that bitcoin's average block confirmation time is about 10 minutes. The implications are alarming, with approximately 6.9 million bitcoin (about one-third of the total supply) sitting in wallets where the public key has already been exposed on the blockchain, making them vulnerable to an 'at-rest' attack that does not require racing against the clock. The race to develop a quantum computer capable of running Shor's algorithm efficiently has significant implications for the security of bitcoin and the broader cryptocurrency landscape.