How Quantum Computing Threatens Bitcoin Security in Under 10 Minutes

The first part of this series explored the principles of quantum computing, introducing the concept of a fundamentally different kind of machine that leverages the unique rules of physics at the atomic and particle level. However, understanding how quantum computers work does not directly reveal how they can be used to compromise bitcoin security. To grasp this, one must comprehend what quantum computers are attacking, how bitcoin's security is structured, and where the vulnerabilities lie. This piece begins by examining bitcoin's encryption, leading up to the nine-minute window identified by Google's recent quantum computing research, within which a quantum algorithm can potentially break bitcoin's security. Bitcoin utilizes elliptic curve cryptography to verify ownership, with each wallet possessing a private key (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 thought of as a one-way map, where starting from a known point (generator point G), taking a specific number of steps defined by the curve's mathematics leads to a public key. While it's easy to go forward (from private to public key), reversing the process (from public to private key) is effectively impossible for classical computers due to the elliptic curve discrete logarithm problem, which would take longer than the universe's age to solve with current algorithms. In 1994, mathematician Peter Shor discovered a quantum algorithm that efficiently solves the discrete logarithm problem, leveraging quantum properties such as superposition, entanglement, and interference. Shor's algorithm converts finding the private key into a problem of determining the period of a function related to the elliptic curve, which quantum computers can solve efficiently. The intuition behind this process involves representing all possible inputs simultaneously, applying the function, and then using a quantum operation (Fourier transform) to reinforce correct answers while canceling out wrong ones. Although Shor's algorithm has been 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 research by Google, in collaboration with Ethereum Foundation and Stanford cryptographers, 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 elliptic curve. This reduction, along with the introduction of a practical attack scenario, changes the perspective on the quantum threat to bitcoin. The parts of Shor's algorithm that depend on fixed, publicly known parameters of the elliptic curve can be precomputed, allowing a quantum computer to sit in a primed state, ready to finish the calculation once a target public key appears. Google estimates this second half of the calculation takes about nine minutes, which is close to bitcoin's average block confirmation time of 10 minutes. This creates a 'mempool attack' scenario where an attacker has roughly nine minutes to derive a private key and submit a competing transaction. The attacker has a 41% chance of succeeding before the original transaction confirms. More concerning is the vulnerability of the 6.9 million bitcoin (about one-third of the total supply) in wallets where the public key has already been exposed on the blockchain, as these are susceptible to an 'at-rest' attack that does not race against the clock. The implications of this vulnerability, the impact of Taproot, and the pace at which hardware is closing the gap are critical considerations for bitcoin's security in the face of quantum computing advancements.