The Quantum Threat to Bitcoin: How Your Coins Can Be Stolen in Under 10 Minutes

The first part of this series delved into the physics behind quantum computing, explaining how it differs from classical computing. However, understanding the mechanics of quantum computing doesn't necessarily reveal how it can be used to steal bitcoin. To grasp this, one must comprehend what quantum computers are attacking and where the weakness lies in bitcoin's security. This piece begins by examining bitcoin's encryption method, known as elliptic curve cryptography, which is used to verify ownership. Every bitcoin wallet has a private key, a secret number, and a public key derived from the private key through a mathematical operation on the 'secp256k1' curve. This process is akin to a one-way map, where starting from a known point, taking a certain number of steps leads to a public key, but reversing the 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 because classical computers cannot reverse the math. However, in 1994, mathematician Peter Shor discovered a quantum algorithm that can break this trapdoor efficiently. Shor's algorithm solves the discrete logarithm problem, which would take a classical computer longer than the universe's existence to solve, in what is known as polynomial time. The algorithm works by converting the problem into finding the period of a function, which quantum computers can solve efficiently using superposition, entanglement, and interference. Despite Shor's algorithm being known for over 30 years, the reason bitcoin remains secure is that running the algorithm requires a quantum computer with a large number of stable qubits. A recent paper by Google, in collaboration with Ethereum Foundation researcher Justin Drake and Stanford cryptographer Dan Boneh, significantly reduced the estimated number of qubits needed from millions to fewer than 500,000. The team designed quantum circuits that implement Shor's algorithm against bitcoin's elliptic curve, with one circuit using approximately 1,200 logical qubits and another using about 1,450 logical qubits. Because qubits lose their quantum state constantly, hundreds of redundant qubits are needed to maintain a single reliable logical qubit, with most of a quantum computer's infrastructure dedicated to error correction. The paper introduced a practical attack scenario where 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 'mempool attack' scenario where an attacker has roughly nine minutes to derive a private key and submit a competing transaction, giving them a 41% chance of succeeding before the original transaction confirms. More alarming is the vulnerability of the 6.9 million bitcoin (about one-third of the total supply) that have public keys already exposed on the blockchain, making them susceptible to an 'at-rest' attack that doesn't require racing against the clock. 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 bitcoin's security.