The Quantum Threat to Bitcoin: How Your Coins Can 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 does not directly reveal how it can be utilized to steal bitcoin. To grasp this, one must comprehend what a quantum computer attacks and the inherent weaknesses in bitcoin's security framework. This piece begins by examining bitcoin's encryption, tracing the path to the nine-minute window identified by Google's recent quantum computing paper. Bitcoin employs 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 visualized as a one-way map, where starting from a known location, taking a certain number of steps leads to a public key, but reversing this process to find the private key is virtually impossible for classical computers. The security of bitcoin relies on this one-way trapdoor, with the private key serving as proof of ownership and the public key being safe to share. When sending bitcoin, the wallet uses the private key to create a digital signature, a mathematical proof that the sender knows the secret number without revealing it. However, a quantum algorithm known as Shor's algorithm can break this trapdoor. Discovered by mathematician Peter Shor in 1994, this algorithm solves the discrete logarithm problem efficiently, which is the backbone of bitcoin's encryption. The algorithm converts finding the private key into a problem of finding the period of a function, which is a task well-suited for quantum computers. Quantum computers can represent all possible values simultaneously and apply a function to all of them at once, leveraging superposition, entanglement, and interference to find the correct answer. The reason bitcoin remains secure today is that running Shor's algorithm requires a quantum computer with a large number of stable qubits, a feat that has been beyond current technological capabilities. Google's paper significantly reduced the estimated number of qubits needed, from millions to fewer than 500,000, bringing the possibility of a quantum attack closer to reality. The team designed quantum circuits that implement Shor's algorithm against bitcoin's specific elliptic curve, requiring approximately 1,200 to 1,450 logical qubits and millions of Toffoli gates. A Toffoli gate is a type of gate that acts on three qubits, and due to qubits' tendency to lose their quantum state, hundreds of redundant qubits are needed to maintain a single reliable logical qubit. Google's paper introduced a practical attack scenario that changes the perspective on the threat. Parts of Shor's algorithm can be precomputed, allowing the quantum computer to sit in a primed state, waiting for a target public key to appear. Once a public key is visible, the machine only needs to finish the second half of the calculation, which Google estimates takes about nine minutes. This creates a window of opportunity for a quantum attacker to derive a private key and submit a competing transaction, potentially redirecting funds. The average block confirmation time in bitcoin is 10 minutes, giving 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, roughly one-third of the total supply, sitting 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, controlling the coins. For coins transacted since the Taproot upgrade, the public key is already visible, while for coins in older addresses, the public key is hidden until spent, at which point there is a nine-minute window before an attacker can catch up.