The Quantum Threat to Bitcoin: How Your Cryptocurrency Could Be Stolen 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 is only half the story; the real concern is how it can be utilized to compromise bitcoin's security. To grasp this, one must comprehend the target - the encryption mechanism that safeguards bitcoin and how a quantum algorithm can potentially breach it. This piece will dissect bitcoin's encryption, tracing the path from its foundation to the recently identified nine-minute window of vulnerability, as indicated by Google's quantum computing paper. Bitcoin employs elliptic curve cryptography, a system that verifies ownership through a pair of 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 process can be visualized as a one-way map, where starting from a known point (the generator point G), taking a certain number of steps defined by the curve's mathematics leads to a public key. While moving forward in this map is straightforward, reversing the process is virtually impossible for classical computers. 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 since classical computers cannot reverse the math. However, the introduction of Shor's algorithm, a quantum algorithm discovered by Peter Shor in 1994, changes this landscape. Shor's algorithm efficiently solves the discrete logarithm problem, which is the backbone of bitcoin's encryption, by converting it into a problem of finding the period of a function. This is achieved by leveraging the properties of quantum computing, including superposition, entanglement, and interference. The algorithm puts its input into a superposition, applies a function to all possible inputs simultaneously, and then uses the Fourier transform to reinforce the correct answers while canceling out the incorrect ones. Despite Shor's algorithm being known for over 30 years, its application has been hindered by the requirement for a large number of stable qubits to maintain coherence throughout the calculation. Recent estimates by Google's Quantum AI division, 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, coupled with the design of quantum circuits that implement Shor's algorithm against bitcoin's specific elliptic curve, brings the threat of quantum computing to bitcoin's security closer to reality. The introduction of a practical attack scenario, where parts of Shor's algorithm can be precomputed and the quantum computer can sit in a primed state waiting for a target public key, changes the dynamics of the threat. If a user broadcasts a transaction and their public key becomes visible, a quantum attacker has approximately nine minutes to derive the private key and submit a competing transaction, given that the second half of the calculation takes about nine minutes according to Google's estimates. This creates a 'mempool attack' scenario with a roughly 41% chance of success before the original transaction confirms, assuming the attacker can act within the nine-minute window. Moreover, approximately 6.9 million bitcoin, or one-third of the total supply, are vulnerable to an 'at-rest' attack since their public keys have already been exposed on the blockchain. These coins can be compromised without any time constraint, posing a significant concern. The implications of these findings, including the impact of Taproot on bitcoin's privacy and the pace at which quantum hardware is advancing, will be explored in the next piece of this series.