The Quantum Threat to Bitcoin: How a Powerful Computer Can Steal Your Cryptocurrency in Under 10 Minutes

The first part of this series delved into the fundamentals of quantum computing, explaining how it differs from classical computing. However, understanding the inner workings of a quantum computer is only half the story. To comprehend how it can be used to steal bitcoin, one must also grasp what it is attacking and where the vulnerabilities lie. This piece begins by examining bitcoin's encryption, shedding light on the process and the weaknesses that a quantum algorithm can exploit. Bitcoin relies on elliptic curve cryptography, a system that 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 the private key through a mathematical operation on a specific curve known as 'secp256k1'. This operation can be thought of as a one-way map, where starting from a known point, taking a certain number of steps defined by the curve's math leads to the public key. The crucial aspect of this system is that moving forward is straightforward, but reversing the process is virtually impossible for classical computers. The security of bitcoin is based on this one-way trapdoor, with the private key serving as proof of ownership and the public key being safe to share since no classical computer can reverse the math. 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 introduced a quantum algorithm that can break this trapdoor. Shor's algorithm efficiently solves the discrete logarithm problem, which would take a classical computer an impractically long time 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. By representing all possible values simultaneously and applying a quantum operation known as the Fourier transform, the algorithm can find the period and, from it, derive the private key. This process utilizes the principles of superposition, entanglement, and interference, making it a powerful tool for breaking bitcoin's encryption. Despite Shor's algorithm being known for over 30 years, the reason bitcoin remains secure is that running the algorithm requires a quantum computer with a large number of stable qubits. However, a recent paper by Google's Quantum AI division, in collaboration with researchers from the Ethereum Foundation and Stanford, has significantly reduced the estimated number of qubits needed, from millions to fewer than 500,000. 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 about 1,450 logical qubits. The introduction of a practical attack scenario by Google's paper changes the perspective on the threat. 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, ready to finish the calculation once a target public key appears. Google estimates that finishing the second half of the calculation takes about nine minutes, which is close to bitcoin's average block confirmation time of 10 minutes. This means a quantum attacker has a roughly 41% chance of deriving a private key and submitting a competing transaction before the original transaction confirms. While this 'mempool attack' is alarming, it requires a quantum computer that does not yet exist. A more significant concern is the 6.9 million bitcoin, roughly one-third of the total supply, that are already vulnerable to an 'at-rest' attack because their public keys have been permanently exposed on the blockchain. These coins can be targeted without a race against the clock, as the attacker can take as long as needed to derive the private key. The implications of this vulnerability and the pace at which quantum hardware is advancing will be explored in the next part of this series.