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

This series' first part explored the principles of quantum computing, introducing a new kind of machine that leverages the unique rules of physics at the atomic and particle level. However, understanding how quantum computers work doesn't reveal how they can be used to steal bitcoin. To grasp this, one must comprehend what a quantum computer attacks, how bitcoin's security is established, and where the vulnerability lies. This piece begins with bitcoin's encryption, working through to the nine-minute window, as identified by Google's recent quantum computing paper, that it takes to break it. Bitcoin utilizes elliptic curve cryptography to verify ownership, with each wallet having two keys: a private key, which is a secret 256-digit binary 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 the public key. Anyone can verify the public key, but no classical computer can figure out the number of steps taken, making it effectively impossible to reverse the process. This one-way trapdoor is the foundation of bitcoin's security model, with the private key proving 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, Shor's algorithm, discovered in 1994, breaks this trapdoor by solving the discrete logarithm problem efficiently, using quantum properties to find the period of a function and unravel the math in a single step, recovering the private key. The algorithm utilizes superposition to evaluate a function on all possible inputs simultaneously, entanglement to link inputs and outputs, and interference to filter out wrong answers. While Shor's algorithm has been known for over 30 years, implementing it requires a quantum computer with a large number of stable qubits, which has been beyond reach. Google's paper reduced the estimated number of qubits needed from millions to fewer than 500,000, introducing a practical attack scenario. The team designed two quantum circuits that implement Shor's algorithm against bitcoin's elliptic curve, using approximately 1,200 and 1,450 logical qubits, respectively. Because qubits lose their quantum state constantly, redundant qubits are needed to maintain a single reliable logical qubit, with most of the quantum computer existing to catch its own mistakes. Google's paper introduced a nine-minute window for a quantum attack, where the parts of Shor's algorithm that depend on the elliptic curve's fixed parameters can be precomputed, allowing the quantum computer to sit 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, estimated to take about nine minutes. This creates a 'mempool attack' scenario, where a quantum attacker has roughly nine minutes to derive a private key and submit a competing transaction, with a 41% chance of finishing before the original transaction confirms. The bigger concern, however, is the 6.9 million bitcoin already exposed on the blockchain, 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, with the implications of this vulnerability and the pace of hardware development being explored in the next part of this series.