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

The first part of this series delved into the principles of quantum computing, a technology that leverages the unique properties of matter at the atomic and subatomic level to perform calculations that are exponentially faster and more powerful than those of classical computers. However, understanding the mechanics of quantum computing does not provide insight into how it can be utilized to steal bitcoin. To comprehend this, it is essential to grasp the security measures that protect bitcoin and identify the vulnerabilities that a quantum computer can exploit. This article will explore how bitcoin's encryption works, why a quantum algorithm can break it, and the implications of Google's recent paper on the timeline for this threat. Bitcoin's security relies on a system called elliptic curve cryptography, which involves 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 the private key through a mathematical operation. This process can be thought of as a one-way map, where it is easy to move forward but virtually impossible to go backward using classical computers. The security of bitcoin hinges on this one-way function, with the private key serving as proof of ownership and the public key being safe to share. When a bitcoin transaction is made, the wallet uses the private key to create a digital signature, which is a mathematical proof that the sender knows the secret number without revealing it. However, a quantum algorithm known as Shor's algorithm can break this one-way function. Discovered by mathematician Peter Shor in 1994, this algorithm solves the discrete logarithm problem efficiently, which is the core of bitcoin's encryption. The algorithm works by converting the problem into finding the period of a function, which is a task that quantum computers are particularly well-suited for. Quantum computers can put their input register into a superposition, representing all possible values simultaneously, and then apply a function to all of them at once. By applying a quantum operation called the Fourier transform, the correct answers are reinforced while the incorrect ones cancel out. The result is the period of the function, from which the private key can be easily derived. This means that a quantum computer running Shor's algorithm can turn a bitcoin public key into the private key that controls the coins. The reason bitcoin remains secure for now is that running Shor's algorithm requires a quantum computer with a large enough number of stable qubits to maintain coherence throughout the calculation. Recent estimates suggested that millions of physical qubits would be needed, but Google's paper reduced this number to fewer than 500,000, a roughly 20-fold reduction. The team designed two quantum circuits that implement Shor's algorithm against bitcoin's specific elliptic curve, one using approximately 1,200 logical qubits and the other using approximately 1,450 logical qubits. Google's paper also introduced a practical attack scenario that changes how to think about the threat. The parts of Shor's algorithm that depend only 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, 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 that redirects funds. The average block confirmation time for bitcoin is 10 minutes, which means the attacker has roughly nine minutes to succeed. The math gives the attacker a roughly 41% chance of finishing before the original transaction confirms. This attack is alarming but requires a quantum computer that does not yet exist. A more significant concern is the 6.9 million bitcoin sitting in wallets where the public key has already been permanently exposed on the blockchain. These coins are vulnerable to an 'at-rest' attack that requires no race against the clock. A quantum computer running Shor's algorithm can turn a bitcoin public key into the private key that controls the coins, allowing the attacker to take as long as needed to steal the funds.