The Quantum Threat to Bitcoin: How Cryptography Can Be Broken in Under 10 Minutes

The first part of this series explored the fundamentals of quantum computing, but understanding how it can be used to compromise bitcoin requires knowledge of what it's attacking and where the vulnerability lies. This article begins with an examination of bitcoin's encryption, which utilizes elliptic curve cryptography, a system that relies on a one-way map to prove ownership. Every bitcoin wallet has a private key, a secret number, and a public key derived from it through a mathematical operation on a specific curve known as secp256k1. This process can be thought of as a one-way function where it's easy to generate a public key from a private key but virtually impossible to reverse the process with classical computers. The security of bitcoin is based on this one-way trapdoor, with the private key serving as proof of ownership and the public key being safe to share because reversing the math is impractical for classical computers. However, the discovery of Shor's algorithm by mathematician Peter Shor in 1994 introduced a quantum algorithm that can efficiently solve the discrete logarithm problem, thereby breaking the trapdoor. Shor's algorithm works by converting the problem of finding a private key into a problem of finding the period of a function, which quantum computers are particularly adept at solving due to their ability to exist in a superposition, apply functions to all inputs simultaneously, and use quantum operations like the Fourier transform to filter out incorrect answers. The practical application of Shor's algorithm against bitcoin's encryption has been limited by the requirement for a quantum computer with a sufficiently large number of stable qubits. Recent research by Google, in collaboration with the Ethereum Foundation and Stanford cryptographers, 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. This reduction in required qubits, along with the introduction of a practical attack scenario, changes the perspective on the quantum threat to bitcoin. The scenario involves precomputing parts of Shor's algorithm that depend on the elliptic curve's fixed parameters, allowing a quantum computer to sit in a primed state, ready to finish the calculation once a target public key appears. Google estimates that finishing the second half of the calculation takes approximately nine minutes, which is close to bitcoin's average block confirmation time of 10 minutes. This creates a window of opportunity for a quantum attacker to derive a private key and submit a competing transaction that redirects funds, with a roughly 41% chance of succeeding before the original transaction confirms. Moreover, the research highlights that approximately 6.9 million bitcoin, or roughly one-third of the total supply, are 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 derive the private key once a quantum computer capable of running Shor's algorithm is available.