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

The first part of this series delved into the fundamental principles of quantum computing, explaining how these machines differ from classical computers. However, understanding the mechanics of quantum computers doesn't reveal how they can be used to steal bitcoin. To grasp this, it's essential to comprehend what a quantum computer attacks and how bitcoin's security is structured. This piece begins by examining bitcoin's encryption method, known as elliptic curve cryptography, and progresses to the recently identified nine-minute window, as outlined in Google's quantum computing paper. Bitcoin employs a system called elliptic curve cryptography to verify ownership. Each wallet has two keys: a private key, which is a secret number, and a public key derived from the private key through a mathematical operation on a specific curve called 'secp256k1'. This process can be thought of as a one-way map, where starting from a known location on the curve, taking a certain number of steps leads to a public key. Anyone can verify the public key, but figuring out the number of steps taken (the private key) is virtually impossible for classical computers. The security of bitcoin relies on this one-way trapdoor, where the private key proves ownership, and the 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, in 1994, mathematician Peter Shor discovered a quantum algorithm that can break this trapdoor. Shor's algorithm efficiently solves the discrete logarithm problem, which would take a classical computer longer than the age of the universe to solve. The algorithm converts the problem into finding the period of a function, which can be solved using quantum properties. Finding this period is what quantum computers are designed for, and once the period is known, the private key can be easily recovered. The attack utilizes all three quantum properties: 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. Google's recent paper reduced the estimated number of qubits needed from millions to fewer than 500,000. The team designed two quantum circuits that implement Shor's algorithm against bitcoin's specific elliptic curve, with one using approximately 1,200 logical qubits and the other using 1,450 logical qubits. The paper introduced a practical attack scenario, where 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 the public key is visible, the machine only needs to finish the second half of the calculation, which Google estimates takes around nine minutes. This creates a nine-minute window for a quantum attacker to derive a private key and submit a competing transaction. The math gives the attacker a roughly 41% chance of succeeding before the original transaction confirms. This mempool attack is alarming but requires a quantum computer that does not yet exist. A more significant concern is the 6.9 million bitcoin (approximately one-third of the total supply) in wallets where the public key has already been exposed on the blockchain, making them vulnerable to an 'at-rest' attack that requires no time constraint. A quantum computer running Shor's algorithm can turn a bitcoin public key into the private key that controls the coins, posing a significant threat to the security of the cryptocurrency.