The Quantum Threat to Bitcoin: How Your Cryptocurrency Could be Stolen in Under 10 Minutes

The first part of this series delved into the principles of quantum computing, explaining how these machines differ fundamentally from classical computers. However, understanding the inner workings of quantum computers doesn't directly reveal how they can be used to compromise bitcoin security. To grasp this, one must comprehend what quantum computers attack and where the weaknesses in bitcoin's security lie. This piece will dissect bitcoin's encryption, the role of elliptic curve cryptography, and the 'nine-minute window' identified by Google's recent quantum computing research. Bitcoin utilizes elliptic curve cryptography, specifically the 'secp256k1' curve, to validate ownership. Each wallet has a private key, a secret 256-bit number, and a public key derived from it through a mathematical operation on the curve. The process can be thought of as a one-way map, where starting from a known point, taking a certain number of steps defined by the curve leads to the public key. While moving forward is straightforward, reversing the process to find the private key from the public key is virtually impossible for classical computers, due to the elliptic curve discrete logarithm problem. This problem is so complex that even the fastest classical computers would take longer than the age of the universe to solve it for a 256-bit key. The security of bitcoin relies on this one-way trapdoor; your private key proves ownership, and your public key can be shared without compromising security. However, in 1994, mathematician Peter Shor discovered an algorithm that can efficiently solve the discrete logarithm problem using a quantum computer. Shor's algorithm converts the problem into finding the period of a function related to the elliptic curve, which quantum computers can solve by representing all possible inputs simultaneously and applying the function to them at once, followed by a Fourier transform to filter out incorrect answers. This process leverages superposition, entanglement, and interference, core properties of quantum mechanics. Despite Shor's algorithm being 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 the Ethereum Foundation and Stanford cryptographers, has significantly reduced the estimated number of qubits needed, from millions to fewer than 500,000. This reduction comes with the design of quantum circuits that implement Shor's algorithm against bitcoin's elliptic curve, utilizing approximately 1,200 to 1,450 logical qubits and tens of millions of Toffoli gates. Given that qubits are highly prone to losing their quantum state, the actual number of physical qubits required is much higher, due to the need for redundancy to maintain a stable logical qubit. Google's research introduced a practical attack scenario, suggesting that parts of Shor's algorithm can be precomputed based on the elliptic curve's fixed parameters, allowing a quantum computer to be 'primed' and ready to attack once a target public key is identified. The second half of the calculation, which depends on the specific public key, can be completed in about nine minutes, according to Google's estimates. This timeframe is critical because it is comparable to bitcoin's average block confirmation time of 10 minutes. If a user broadcasts a transaction with their public key visible, a quantum attacker has roughly nine minutes to derive the private key and submit a competing transaction. The probability of success in this 'mempool attack' is approximately 41%. More alarming is the vulnerability of the 6.9 million bitcoin (about one-third of the total supply) that have had their public keys exposed on the blockchain. These coins are susceptible to an 'at-rest' attack, where a quantum computer can take as long as needed to derive the private key, without racing against the clock. The implications of this vulnerability, the impact of Taproot on bitcoin privacy, and the pace at which hardware is advancing towards making such attacks feasible, will be explored in the next part of this series.