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 these machines differ fundamentally from classical computers. However, understanding the inner workings of quantum computers doesn't directly reveal how they can be used to steal bitcoin. To grasp this, one must comprehend what quantum computers are attacking, the nature of bitcoin's security, and the specific weaknesses involved. This piece begins by examining bitcoin's encryption, leading to the revelation of a nine-minute window for breaking it, as identified in a recent quantum computing paper by Google. Bitcoin utilizes elliptic curve cryptography to verify ownership, a system where each wallet has two keys: a private key and a public key. The public key is derived from the private key through a mathematical operation on the 'secp256k1' curve, essentially creating a one-way map. Starting from a known point on the curve, taking a certain number of steps defined by the curve's mathematics leads to the public key. This process is easy to perform in one direction but virtually impossible to reverse with classical computers, making it the foundation of bitcoin's security model. The private key serves as proof of ownership, while the public key can be safely shared without compromising security. When sending bitcoin, the wallet uses the private key to create a digital signature, proving knowledge of the secret number without revealing it. However, the discovery of Shor's algorithm by mathematician Peter Shor in 1994 opened up the possibility for quantum computers to break this one-way trapdoor efficiently. Shor's algorithm solves the discrete logarithm problem, which classical computers cannot, by converting it into a problem of finding the period of a function related to the elliptic curve. This is achievable due to the unique properties of quantum computers, including superposition, where a particle can exist in multiple states simultaneously, entanglement, which links particles in a way that their properties are correlated, and interference, which can filter out incorrect answers. The algorithm applies these principles to evaluate a function on all possible inputs at once, find the period of the function, and from this period, derive the private key. The reason bitcoin remains secure today is that running Shor's algorithm requires a quantum computer with a large number of stable qubits, which has been beyond current technological capabilities. Yet, a recent paper by Google's Quantum AI division, in collaboration with researchers from the Ethereum Foundation and Stanford, significantly reduced the estimated number of qubits needed from millions to fewer than 500,000. This reduction comes from designing quantum circuits that implement Shor's algorithm specifically against bitcoin's elliptic curve, requiring approximately 1,200 to 1,450 logical qubits and tens of millions of Toffoli gates. Given that qubits are prone to losing their quantum state, hundreds of redundant qubits are needed to maintain a single reliable logical qubit, explaining the high ratio of physical to logical qubits in quantum computers. The paper also introduced a practical attack scenario, suggesting that parts of Shor's algorithm can be precomputed for bitcoin's elliptic curve, allowing a quantum computer to be 'primed' and ready to finish the calculation once a target public key appears. This leads to a nine-minute window for the attack, which is particularly alarming considering bitcoin's average block confirmation time is 10 minutes. If a user broadcasts a transaction with their public key visible, a quantum attacker has roughly nine minutes to derive the private key and submit a competing transaction. This 'mempool attack' gives the attacker about a 41% chance of succeeding before the original transaction confirms. More concerning is the vulnerability of the 6.9 million bitcoin (about one-third of the total supply) that have had their public keys exposed on the blockchain, making them susceptible to an 'at-rest' attack that doesn't require racing against the clock. A quantum computer can turn a public key into a private key at any time, posing a significant threat to the security of these coins.