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

The first part of this series delved into the physics of quantum computing, explaining how these machines differ fundamentally from regular computers. However, understanding the inner workings of a quantum computer doesn't reveal how it can be exploited to steal bitcoin. To grasp this, one must comprehend what a quantum computer attacks and how the security of bitcoin is structured, including its vulnerabilities. This piece begins with an examination of bitcoin's encryption, leading to the nine-minute window, as identified by Google's recent quantum computing paper, that it takes to break it. Bitcoin utilizes a system known as elliptic curve cryptography to verify ownership. Each wallet possesses two keys: a private key, which is a secret number, and a public key derived from the private key through a mathematical operation on the 'secp256k1' curve. This 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 a public key. Anyone can verify the public key, but determining the number of steps (the private key) is, for classical computers, effectively impossible. This one-way function is the backbone of bitcoin's security model. Your private key proves ownership, and your public key is safe to share because classical computers cannot reverse the math. When sending bitcoin, the wallet uses the private key to create a digital signature, proving knowledge of the secret number without revealing it. However, a quantum algorithm known as Shor's algorithm, discovered by mathematician Peter Shor in 1994, can break this one-way trapdoor. Shor's algorithm solves the discrete logarithm problem efficiently, which classical computers cannot do in a reasonable timeframe. The algorithm works by converting the problem into finding the period of a function related to the elliptic curve and then using quantum properties to find this period. Once the period is known, the private key can be found almost immediately. This process utilizes the three quantum properties of superposition, entanglement, and interference. Despite Shor's algorithm being known for over 30 years, running it requires a quantum computer with a large number of stable qubits, which has been out of reach. Google's paper reduced the estimated number of qubits needed from millions to fewer than 500,000, or a roughly 20-fold reduction. The paper introduced two quantum circuits that implement Shor's algorithm against bitcoin's specific elliptic curve, one using approximately 1,200 logical qubits and the other 1,450 logical qubits. Because qubits lose their quantum state, hundreds of redundant qubits are needed to maintain a single reliable logical qubit, reflecting the significant infrastructure required for a quantum computer to function accurately. Google's paper also introduced a practical attack scenario, suggesting that parts of Shor's algorithm can be precomputed, leaving the quantum computer in a primed state, waiting for a target public key to appear. Once a target key is identified, the machine only needs to finish the second half of the calculation, which Google estimates takes about nine minutes. Given bitcoin's average block confirmation time of 10 minutes, an attacker has roughly nine minutes to derive a private key and submit a competing transaction. This gives the attacker 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 6.9 million bitcoin (about one-third of the total supply) in wallets where the public key has already been exposed on the blockchain, making these coins vulnerable to an 'at-rest' attack that does not race against the clock. A quantum computer running Shor's algorithm can turn a bitcoin public key into the private key that controls the coins, with implications for both coins transacted since the Taproot upgrade and those in older addresses.