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

The first part of this series explored the fundamental principles of quantum computing. However, understanding the inner workings of a quantum computer is only half the story. To grasp how it can be used to compromise bitcoin, one must also comprehend what it is targeting and where the vulnerabilities lie. This piece will examine bitcoin's encryption, the role of elliptic curve cryptography, and how a quantum algorithm can break it, as well as the implications of Google's recent findings. Bitcoin's security relies on a complex system known as elliptic curve cryptography, which utilizes a pair of keys: a private key and a public key. The public key is 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 it is easy to move forward but virtually impossible to reverse the process using classical computers. The security of this system hinges on the difficulty of solving the elliptic curve discrete logarithm problem, which is estimated to be virtually impossible for classical computers to solve in a reasonable timeframe. However, the discovery of Shor's algorithm by mathematician Peter Shor in 1994 introduced a quantum approach that can efficiently solve this problem. Shor's algorithm exploits the properties of quantum mechanics, including superposition, entanglement, and interference, to find the period of a function related to the elliptic curve. This period is crucial for recovering the private key from the public key, thus breaking the encryption. Despite the existence of Shor's algorithm for over three decades, its application has been hindered by the requirement for a large number of stable qubits to maintain coherence throughout the calculation. Recent research by Google's Quantum AI division, in collaboration with contributors from the Ethereum Foundation and Stanford, has significantly reduced the estimated number of qubits needed, from millions to fewer than 500,000. This reduction has profound implications for the potential threat to bitcoin's security. The team designed 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 critical aspect of this research is the introduction of a practical attack scenario, where parts of the calculation can be precomputed and the quantum computer can be primed to finish the calculation quickly once a target public key is identified. Google estimates that the second half of the calculation, which depends on the target public key, can be completed in about nine minutes. Given that bitcoin's average block confirmation time is 10 minutes, this creates a narrow window for a quantum attacker to derive a private key and submit a competing transaction. The attacker has 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 approximately 6.9 million bitcoin (about one-third of the total supply) that are already vulnerable to an 'at-rest' attack because their public keys have been permanently exposed on the blockchain. These coins can be compromised without racing against the clock, as the attacker can take as long as needed to perform the calculation. The implications of these findings and the steps that can be taken to mitigate the quantum threat to bitcoin will be explored in the next and final piece of this series.