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

This series' first part explored the principles of quantum computing. However, understanding how quantum computers work doesn't directly explain how they can be used to steal bitcoin. To grasp this, one must comprehend what a quantum computer attacks, how bitcoin's security is structured, and where its weaknesses lie. This piece begins with an examination of bitcoin's encryption, leading to the nine-minute window identified by Google's recent quantum computing paper. Bitcoin utilizes elliptic curve cryptography, a system that involves two keys: a private key, which is a secret number, and a public key derived from the private key through a mathematical operation. The relationship between these keys can be thought of as a one-way map, where starting from a known point and taking a specific number of steps leads to the public key, but reversing this process is virtually impossible for classical computers. This one-way function is the foundation of bitcoin's security model. Your private key proves ownership, and your public key is safe to share because classical computers cannot reverse the mathematics. When sending bitcoin, the wallet uses the private key to create a digital signature, proving knowledge of the secret number without revealing it. However, a quantum algorithm discovered by Peter Shor in 1994, known as Shor's algorithm, can efficiently break this one-way trapdoor. Shor's algorithm solves the discrete logarithm problem, which would take a classical computer longer than the universe's age to solve, in polynomial time. The algorithm works by converting the problem of finding the private key into finding the period of a function related to the elliptic curve. Quantum computers are particularly suited for this task due to their ability to represent all possible inputs simultaneously and apply the function to them all at once, then use the Fourier transform to find the period. From this period, the private key can be easily recovered, thus compromising the security of the bitcoin. This attack utilizes the three primary quantum properties: superposition, which allows the evaluation of the function on all possible inputs at once; entanglement, which links the input and output; and interference, which filters out incorrect answers. Despite Shor's algorithm being known for over 30 years, the reason bitcoin remains secure is that implementing this algorithm requires a quantum computer with a large number of stable qubits. Recent estimates have reduced the number of qubits needed from millions to fewer than 500,000, significantly narrowing the gap. Google's Quantum AI division, along with contributions from other researchers, designed quantum circuits that implement Shor's algorithm against bitcoin's specific elliptic curve, using approximately 1,200 to 1,450 logical qubits. The introduction of a practical attack scenario changes the perspective on the threat. Parts of Shor's algorithm can be precomputed, allowing the quantum computer to be 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 about nine minutes. This timeline is critical because it intersects with bitcoin's average block confirmation time of 10 minutes, giving a quantum attacker a roughly 41% chance of deriving a private key and submitting a competing transaction before the original transaction confirms. The more significant concern is the 6.9 million bitcoin already vulnerable due to their public keys being exposed on the blockchain. These coins are at risk of an 'at-rest' attack, which does not require racing against the clock. The implications of this vulnerability, the impact of Taproot on bitcoin privacy, and how quickly hardware is closing the gap to make such an attack possible, will be explored in the next piece.