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

The first part of this series delved into the physics behind quantum computing, explaining how it differs from classical computing. However, understanding the mechanics of quantum computing doesn't necessarily reveal how it can be used to compromise bitcoin security. To grasp this, one must comprehend what quantum computers are attacking and where the weaknesses lie in bitcoin's security framework. This piece begins by examining bitcoin's encryption methodology, which relies on elliptic curve cryptography 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 mathematics 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, which would take longer than the universe's age to solve for a 256-bit curve. This one-way function is the cornerstone of bitcoin's security model, with the private key serving as proof of ownership and the public key being safe to share. However, the discovery of Shor's algorithm by mathematician Peter Shor in 1994 introduced a quantum approach that can efficiently break this encryption. Shor's algorithm converts the problem of finding the private key into finding the period of a function, which quantum computers can solve effectively by representing all possible inputs simultaneously and applying the function to them at once, followed by a Fourier transform that cancels out incorrect answers. The result is that the period, and thus the private key, can be found in polynomial time, significantly faster than any classical method. The reason bitcoin remains secure today is that implementing Shor's algorithm requires a quantum computer with a large number of stable qubits, which has been beyond current technological capabilities. Recent research by Google, in collaboration with Ethereum Foundation and Stanford cryptographers, has reduced the estimated number of qubits needed from millions to fewer than 500,000, a 20-fold reduction. This study designed quantum circuits for Shor's algorithm tailored to bitcoin's elliptic curve, requiring approximately 1,200 to 1,450 logical qubits and tens of millions of Toffoli gates. Because qubits are prone to losing their quantum state, a significant portion of a quantum computer's infrastructure is dedicated to error correction, with a roughly 400-to-1 ratio between physical and logical qubits. Google's research 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, ready to finish the calculation once a target public key is identified. This reduces the time needed to derive a private key to about nine minutes, which is close to bitcoin's average block confirmation time. If a user broadcasts a transaction, a quantum attacker has roughly nine minutes to derive the private key and submit a competing transaction, giving them a 41% chance of succeeding before the original transaction confirms. While this 'mempool attack' is alarming, it requires a quantum computer that does not yet exist. A more significant concern is the approximately 6.9 million bitcoin that have their public keys permanently exposed on the blockchain, making them vulnerable to an 'at-rest' attack that can be executed without time pressure. The implications of these findings, including the impact of Taproot on bitcoin privacy and the pace at which quantum hardware is advancing, will be explored in the next piece of this series.