How Quantum Computing Can Compromise Bitcoin Security in Under 10 Minutes

The first part of this series explored the fundamental principles of quantum computing, distinguishing it from classical 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 enables the verification of ownership without revealing the private key. Essentially, each wallet has a private key and a public key, with the latter being derived from the former through a mathematical operation on the 'secp256k1' curve. This process is akin to 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 due to the elliptic curve discrete logarithm problem. It's estimated that solving this problem for a 256-bit curve with the best-known classical algorithms would take longer than the universe's age. The security of bitcoin hinges on this one-way trapdoor, where the private key serves as proof of ownership, and the public key can be safely shared. When a bitcoin transaction is made, the wallet uses the private key to create a digital signature, proving knowledge of the secret number without disclosing it. However, the advent of quantum algorithms, notably Shor's algorithm discovered in 1994, poses a significant threat. Shor's algorithm efficiently solves the discrete logarithm problem, potentially breaking the trapdoor. It works by converting the problem into finding the period of a function related to the elliptic curve and then using quantum properties to evaluate this function for all possible inputs simultaneously. The algorithm applies a quantum operation called the Fourier transform to reinforce correct answers while canceling out incorrect ones. The result is the period, from which the private key can be deduced, thus compromising the security. The attack leverages superposition to evaluate the function on all inputs at once, entanglement to correlate inputs and outputs, and interference to filter out noise. Despite Shor's algorithm being known for over 30 years, its implementation has been hindered by the requirement for a quantum computer with a sufficient number of stable qubits. Recent estimates suggest that fewer than 500,000 qubits might be needed, a significant reduction from previous estimates. Google's Quantum AI division, in collaboration with researchers, designed quantum circuits that implement Shor's algorithm against bitcoin's elliptic curve, requiring approximately 1,200 to 1,450 logical qubits and millions of Toffoli gates. The introduction of a practical attack scenario changes the threat landscape, particularly with the possibility of precomputing parts of the algorithm that depend on publicly known parameters. This means a quantum computer could be primed, waiting for a target public key to appear, and then finish the calculation within about nine minutes. Given bitcoin's average block confirmation time of 10 minutes, an attacker has a roughly 41% chance of deriving a private key and submitting a competing transaction before the original transaction confirms. This 'mempool attack' is alarming but 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) in wallets with publicly exposed keys, vulnerable to an 'at-rest' attack that does not race against the clock. For coins transacted since the Taproot upgrade, the public key is already visible, making them susceptible. The practical implications of these findings, including the impact of Taproot and the pace at which hardware is narrowing the gap, will be explored in the next piece.