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. However, understanding how quantum computers work is only half the story; the other half involves grasping what they can attack and how. Bitcoin's security relies on a complex system known as elliptic curve cryptography, which essentially acts as a one-way map. Every bitcoin wallet has a private key, a secret number, and a public key derived from this private key through a mathematical operation on a specific curve known as 'secp256k1'. The process can be thought of as taking a certain number of steps on this curve, with the private key determining the number of steps and the public key being the endpoint. Anyone can verify the endpoint, but figuring out the number of steps taken (the private key) is virtually impossible for classical computers due to the elliptic curve discrete logarithm problem. This problem is so complex that even the best classical algorithms would take longer than the age of the universe to solve for a 256-bit curve. The security of bitcoin hinges on this one-way trapdoor, with the private key serving as proof of ownership and the public key being safe to share because it cannot be reversed to find the private key. However, the discovery of Shor's algorithm by mathematician Peter Shor in 1994 introduced a quantum approach that can efficiently solve the discrete logarithm problem, thus breaking the trapdoor. Shor's algorithm works by converting the problem into finding the period of a function related to the elliptic curve, which is achievable through quantum computing due to its ability to handle superposition, entanglement, and interference. This process allows a quantum computer to evaluate a function for all possible inputs simultaneously, apply a quantum operation to filter out incorrect answers, and then measure the result to find the period, from which the private key can be derived. The practical application of Shor's algorithm against bitcoin's elliptic curve has been limited by the requirement for a large number of stable qubits to maintain coherence throughout the calculation. Recent research by Google, in collaboration with the Ethereum Foundation and Stanford University, 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 parts of Shor's algorithm that depend on the elliptic curve's fixed parameters can be precomputed, allowing a quantum computer to be 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 critical because 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 attack, known as the mempool attack, gives the attacker about a 41% chance of succeeding before the original transaction confirms. Moreover, approximately 6.9 million bitcoin, or 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 targeted without any time constraint, as the attacker can take as long as needed to derive the private key. The implications of these findings, including the impact of Taproot, a privacy upgrade on Bitcoin, and the rapid advancement of quantum hardware, will be explored in the next piece of this series.