The Quantum Threat to Bitcoin: How a Powerful Computer Can Steal Your Cryptocurrency 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 they can be used by malicious actors to steal bitcoin. This piece begins with an explanation of bitcoin's encryption system, which relies on elliptic curve cryptography to verify ownership. Each wallet has 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. The process can be thought of as a one-way map, where starting from a known point on the curve, taking a certain number of steps defined by the curve's math leads to the 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. 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 classical computers cannot reverse the math. When sending bitcoin, the wallet uses the private key to create a digital signature, proving knowledge of the secret number without revealing it. The discovery of Shor's algorithm by mathematician Peter Shor in 1994 introduced a quantum approach that can efficiently solve the discrete logarithm problem. This algorithm works by converting the problem into finding the period of a function, which can be achieved using quantum properties such as superposition, entanglement, and interference. By representing all possible values simultaneously and applying the function to them at once, followed by a quantum operation like the Fourier transform, the period can be found, and from it, the private key can be recovered. This effectively breaks the one-way trapdoor, allowing for the theft of bitcoin. Despite Shor's algorithm being known for over 30 years, its implementation has been hindered by the need for a quantum computer with a large number of stable qubits. However, a recent paper by Google's Quantum AI division, in collaboration with researchers from the Ethereum Foundation and Stanford, has significantly reduced the estimated number of qubits required, from millions to fewer than 500,000. This reduction is based on designing quantum circuits that implement Shor's algorithm against bitcoin's specific elliptic curve, requiring approximately 1,200 to 1,450 logical qubits and tens of millions of Toffoli gates. Given that qubits are prone to losing their quantum state, a large number of physical qubits are needed to maintain a smaller number of reliable logical qubits, with a ratio of about 400 to 1. The paper also introduced a practical attack scenario, where parts of Shor's algorithm can be precomputed, allowing the quantum computer to be in a primed state, waiting for a target public key to appear. Once a public key is broadcast or exposed on the blockchain, the machine only needs to finish the second half of the calculation, which Google estimates can take about nine minutes. This timeline is alarming because bitcoin's average block confirmation time is 10 minutes, giving a quantum attacker a roughly 41% chance of deriving a private key and submitting a competing transaction before the original transaction confirms. The bigger concern is the approximately 6.9 million bitcoin that are already vulnerable due to their public keys being permanently exposed on the blockchain, making them susceptible to an 'at-rest' attack that does not require racing against the clock. The implications of this vulnerability, including the impact of Taproot and the pace at which hardware is advancing, will be explored in the next part of this series.