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

In the first part of this series, we explored the fundamentals of quantum computing. However, understanding how quantum computers work is only half the story - to comprehend the threat they pose to bitcoin, we need to delve into the specifics of bitcoin's security and where its weaknesses lie. This piece will examine bitcoin's encryption, the role of elliptic curve cryptography, and how a quantum algorithm can break it. We'll also discuss Google's recent paper and its findings on the feasibility of a quantum attack. Bitcoin's security relies on a system called elliptic curve cryptography, which utilizes a pair of keys: a private key and a public key. The private key is a secret number, while the public key is derived from it through a mathematical operation on a specific curve. This process is akin to a one-way map, where it's easy to move forward but virtually impossible to reverse. The security model is based on this one-way trapdoor, where the private key proves ownership of coins, and the public key can be shared without compromising security. However, a quantum algorithm known as Shor's algorithm can break this trapdoor. Discovered by mathematician Peter Shor in 1994, the algorithm solves the discrete logarithm problem efficiently, which would take a classical computer an impractically long time to solve. The intuition behind Shor's algorithm lies in its ability to find the period of a function, which is essential for breaking the discrete logarithm problem. Quantum computers are well-suited for this task, as they can represent multiple values simultaneously and apply functions to them all at once. The algorithm uses superposition, entanglement, and interference to filter out incorrect answers and reinforce the correct ones. Although Shor's algorithm has been known for over 30 years, its implementation has been hindered by the need for a large number of stable qubits. Recent research by Google's Quantum AI division has reduced the estimated number of qubits required, making the prospect of a quantum attack more feasible. The team designed two quantum circuits that implement Shor's algorithm against bitcoin's specific elliptic curve, with one using approximately 1,200 logical qubits and the other using around 1,450 logical qubits. The introduction of a practical attack scenario has significant implications for the threat posed by quantum computers. 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 a public key is visible, the machine only needs to finish the second half of the calculation, which Google estimates takes around 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. While this 'mempool attack' is alarming, it requires a quantum computer that does not yet exist. A more pressing concern is the 6.9 million bitcoin already exposed on the blockchain, which are vulnerable to an 'at-rest' attack that can be carried out at any time.