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. However, understanding how quantum computers work is not sufficient to comprehend how they can be used to steal bitcoin. To grasp this, it's essential to know what a quantum computer is attacking, how bitcoin's security is constructed, and where the vulnerability lies. This piece begins by examining bitcoin's encryption and then proceeds to explain the nine-minute window required to break it, as identified by Google's recent quantum computing research. Bitcoin utilizes 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 the secp256k1 curve. This can be thought of as a one-way map, where starting from a known location on the curve, taking a certain number of steps defined by the curve's mathematics leads to a public key. Anyone can verify the public key, but determining the private key is virtually impossible for classical computers. The security model relies on this one-way trapdoor, with the private key proving ownership and the public key being safe to share. 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 works by converting the problem into finding the period of a function, which is a task well-suited for quantum computers. They can represent all possible values simultaneously, apply a function to them, and then use a quantum operation called the Fourier transform to find the correct answer. The attack utilizes all three quantum properties: superposition, entanglement, and interference. While Shor's algorithm has been known for over 30 years, its implementation 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, a 20-fold reduction. The team designed quantum circuits that implement Shor's algorithm against bitcoin's elliptic curve, using approximately 1,200 to 1,450 logical qubits. Because qubits lose their quantum state constantly, hundreds of redundant qubits are needed to maintain a single reliable logical qubit. Google's 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 it does, 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. The math gives the attacker a roughly 41% chance of succeeding before the original transaction confirms. This is alarming, but it requires a quantum computer that does not yet exist. A more significant concern is the 6.9 million bitcoin already exposed on the blockchain, which are 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 bitcoin network.