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

The first part of this series explored the fundamental principles of quantum computing, highlighting its distinction from classical computing. However, understanding the inner workings of a quantum computer is only half the story; the real concern lies in its potential application in stealing bitcoin. To grasp this threat, it's essential to comprehend what quantum computers are attacking and the inherent weaknesses in bitcoin's security. This piece begins by examining bitcoin's encryption method, which relies on elliptic curve cryptography to verify ownership. Each wallet possesses two keys: 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 relationship between these keys can be thought of as a one-way map, where starting from a known point (generator point G), taking a certain number of steps defined by the curve's math leads to a public key (point K). While anyone can verify the public key, determining the private key (the number of steps taken) is virtually impossible for classical computers due to the elliptic curve discrete logarithm problem. This problem is so complex that solving it is estimated to take longer than the age of the universe with current classical algorithms. 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. When a bitcoin transaction is made, the wallet uses the private key to create a digital signature, proving knowledge of the secret number without revealing it. However, the discovery of Shor's algorithm by mathematician Peter Shor in 1994 introduced a quantum method that can efficiently solve the discrete logarithm problem, thereby breaking the trapdoor. This algorithm works by converting the problem into finding the period of a function related to the elliptic curve, a task that quantum computers are particularly suited for due to their ability to apply functions to multiple inputs simultaneously (superposition), maintain correlated outputs (entanglement), and filter out incorrect answers (interference). 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 Ethereum Foundation and Stanford cryptographer Dan Boneh, has significantly reduced the estimated number of qubits needed, from millions to fewer than 500,000, making the threat more tangible. The study designed 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 lose their quantum state constantly, a large number of physical qubits are needed to maintain a single logical qubit, with most of the quantum computer's infrastructure dedicated to error correction. The introduction of a practical attack scenario by Google's paper changes the perspective on the threat. 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 could happen when a transaction is broadcast, giving the attacker roughly nine minutes to derive the private key and submit a competing transaction, a timeframe that aligns closely with bitcoin's average block confirmation time of 10 minutes. The attacker has about a 41% chance of succeeding before the original transaction is confirmed. 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 (about one-third of the total supply) in wallets where the public key has been exposed on the blockchain, making them vulnerable to an 'at-rest' attack with no time constraint. For coins transacted since the Taproot upgrade, the public key is already visible, while for older addresses, the public key is hidden until spent, leaving a nine-minute window of vulnerability. The practical implications of these findings, including which 6.9 million bitcoin are exposed and how Taproot affects security, will be explored in the final piece of this series.