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

The first part of this series delved into the physics behind quantum computing, explaining how these machines differ from traditional computers and harness the unique properties of matter at an atomic scale. However, understanding the mechanics of quantum computing doesn't directly reveal how it can be utilized to compromise bitcoin security. To grasp this, one must comprehend what quantum computers are attacking - the encryption methods securing bitcoin - and pinpoint the vulnerabilities. This piece begins with an examination of bitcoin's encryption system, specifically elliptic curve cryptography, which is used to verify ownership. Each wallet possesses two 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 relationship between these keys can be thought of as a one-way map, where starting from a known point on the curve and taking a series of steps defined by the curve's mathematics leads to the public key. While it's straightforward to go from the private key to the public key, reversing this process is virtually impossible for classical computers due to the elliptic curve discrete logarithm problem. This problem is so complex that solving it with the best-known classical algorithms would take longer than the age of the universe for a 256-bit curve. The security of bitcoin relies on this one-way function, allowing users to safely share their public keys without risking the exposure of their private keys. When a bitcoin transaction is made, the wallet uses the private key to create a digital signature, proving ownership without revealing the private key. However, the discovery of Shor's algorithm by mathematician Peter Shor in 1994 introduced a method by which a quantum computer can efficiently solve the discrete logarithm problem, thereby breaking the encryption. Shor's algorithm works by converting the problem of finding the private key into finding the period of a function related to the elliptic curve. Quantum computers are particularly adept at this task due to their ability to apply functions to multiple inputs simultaneously (thanks to superposition), correlate inputs and outputs (through entanglement), and filter out incorrect answers (via interference). Despite Shor's algorithm being known for over 30 years, implementing it has been beyond current technological capabilities due to the requirement for a large number of stable qubits. Recent research by Google, in collaboration with Ethereum Foundation and Stanford cryptographers, has significantly reduced the estimated number of qubits needed, from millions to fewer than 500,000. This reduction is based on designing quantum circuits that can efficiently run Shor's algorithm against bitcoin's specific elliptic curve, with estimates suggesting the need for approximately 1,200 to 1,450 logical qubits. Given that qubits are prone to losing their quantum state, a significant portion of a quantum computer's infrastructure is dedicated to error correction, with hundreds of physical qubits required to maintain a single reliable logical qubit. The research not only lowered the qubit count but also introduced a practical attack scenario. Parts of Shor's algorithm that depend on publicly known parameters of the elliptic curve can be precomputed, allowing the quantum computer to sit in a 'primed' state, ready to finish the calculation once a target public key is identified. Google estimates that completing the second half of the calculation takes about nine minutes, which is close to bitcoin's average block confirmation time of 10 minutes. This creates a 'mempool attack' scenario where an attacker has a roughly 41% chance of deriving a private key and submitting a competing transaction before the original transaction confirms. Although this attack requires a quantum computer that does not yet exist, the more pressing concern is the approximately 6.9 million bitcoin (about one-third of the total supply) that are already vulnerable due to their public keys being exposed on the blockchain. These coins are at risk of an 'at-rest' attack, where an attacker can take as long as needed to derive the private key. The implications of this vulnerability, the impact of Taproot on bitcoin privacy, and how quickly quantum hardware is advancing towards making such attacks feasible are critical considerations for the future security of bitcoin.