The Quantum Threat to Bitcoin: How a Powerful Computer Can Steal Your Cryptocurrency in Under 10 Minutes

The first part of this series delved into the physics behind quantum computing, explaining how it differs from traditional computing. However, understanding the mechanics of quantum computers is only half the story; the other half involves grasping what they can attack and how they can compromise bitcoin's security. This piece begins by examining bitcoin's encryption method, known as elliptic curve cryptography, which is used to verify ownership. Each wallet has a pair of keys: a private key, which is 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 it's easy to go forward, 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, which would take longer than the age of the universe to solve with current algorithms. However, a quantum algorithm discovered by Peter Shor in 1994, known as Shor's algorithm, can efficiently solve this problem by exploiting quantum properties such as superposition, entanglement, and interference. The algorithm works by converting the problem into finding the period of a function related to the elliptic curve, which a quantum computer can solve quickly by evaluating the function on all possible inputs simultaneously and then applying a quantum Fourier transform to find the period. Knowing this period allows for the easy recovery of the private key, thus compromising the bitcoin. 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 estimates by Google, in collaboration with the Ethereum Foundation and Stanford cryptographers, have significantly reduced the number of qubits needed, from millions to fewer than 500,000, by designing efficient quantum circuits for implementing Shor's algorithm against bitcoin's elliptic curve. This reduction is crucial because it brings the threat of quantum computers to bitcoin closer to reality. Google's paper also introduced a practical attack scenario where parts of Shor's algorithm can be precomputed, allowing a quantum computer to sit in a primed state, waiting for a target public key to appear. Once a public key is visible, the machine only needs to finish the second half of the calculation, which Google estimates takes about nine minutes. This timeline is alarming because it is comparable to bitcoin's average block confirmation time of 10 minutes, giving an attacker a window of opportunity to derive a private key and submit a competing transaction. The attack, known as the 'mempool attack,' gives the attacker a roughly 41% chance of succeeding before the original transaction confirms. Moreover, about 6.9 million bitcoin, or roughly one-third of the total supply, are vulnerable to an 'at-rest' attack because their public keys have already been exposed on the blockchain. These coins can be targeted without a race against time, as the attacker can take as long as needed to derive the private key. The implications of these findings and how they affect the security of bitcoin, especially considering recent upgrades like Taproot, will be discussed in the final piece of this series.