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

The first part of this series explored the fundamental principles of quantum computing, explaining how these machines differ from classical computers by leveraging the unique rules of physics at the atomic and particle level. However, understanding the inner workings of a quantum computer doesn't directly reveal how it can be used to compromise bitcoin's security. To grasp this, one must comprehend the target of such an attack: the encryption that underpins bitcoin, why a quantum algorithm can break it, and the implications of recent research by Google. This piece begins with an examination of bitcoin's encryption, progressing to the nine-minute window identified by Google's quantum computing paper as the time it takes to breach it. Bitcoin employs a system called elliptic curve cryptography to verify ownership. Each wallet contains two keys: a private key, which is a secret 256-digit binary number, and a public key derived from the private key through a mathematical operation on the 'secp256k1' curve. This process can be thought of as a one-way map, where starting from a known point (the generator point G), taking a series of steps defined by the curve's mathematics (the number of steps being the private key) leads to a public key (point K). Anyone can verify the public key, but reversing the process to find the private key is virtually impossible for 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 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. In 1994, mathematician Peter Shor discovered a quantum algorithm that can break this one-way trapdoor. Shor's algorithm efficiently solves the discrete logarithm problem, which classical computers cannot do in a reasonable timeframe. The algorithm works by converting the problem of finding the private key 'k' into finding the period of a function related to the elliptic curve. Quantum computers are particularly suited for this task because they can represent all possible inputs simultaneously (superposition), apply the function to all inputs at once, and then use the Fourier transform to reinforce correct answers while canceling out incorrect ones. The result is the period, from which the private key can be easily derived, thus compromising the security of the bitcoin wallet. This attack utilizes the three key properties of quantum computing: superposition to evaluate the function across all inputs simultaneously, entanglement to correlate inputs and outputs, and interference to filter out incorrect answers. Despite Shor's algorithm being known for over 30 years, the reason bitcoin remains secure is that executing this algorithm requires a quantum computer with a sufficiently large number of stable qubits. Recent research by Google, in collaboration with the Ethereum Foundation and Stanford University, has significantly reduced the estimated number of qubits needed to run Shor's algorithm against bitcoin's elliptic curve from millions to fewer than 500,000. This reduction comes from designing quantum circuits that implement Shor's algorithm more efficiently, requiring approximately 1,200 to 1,450 logical qubits and tens of millions of Toffoli gates. A Toffoli gate is a quantum gate that operates on three qubits, acting as a control mechanism. Due to the fragile nature of qubits, which constantly lose their quantum state, a quantum computer needs hundreds of redundant qubits to maintain a single reliable logical qubit, with most of the machine's infrastructure dedicated to error correction. Google's paper introduced a practical attack scenario where parts of Shor's algorithm depending on the elliptic curve's fixed parameters can be precomputed, allowing the quantum computer to be in a 'primed' state. Upon encountering a target public key, the machine only needs to complete the second half of the calculation, which Google estimates takes about nine minutes. Given that bitcoin's average block confirmation time is 10 minutes, an attacker has roughly nine minutes to derive a private key and submit a competing transaction. This gives the attacker a 41% chance of succeeding before the original transaction is confirmed. While this 'mempool attack' requires a quantum computer that does not yet exist, a more significant concern is the approximately 6.9 million bitcoin (about one-third of the total supply) that are vulnerable to an 'at-rest' attack because their public keys have been permanently exposed on the blockchain. These coins can be compromised without any time constraint, as the attacker can take as long as needed to derive the private key using Shor's algorithm. The implications of this vulnerability, the impact of Taproot on bitcoin privacy, and how the advancement of quantum hardware is narrowing the gap to this capability, will be explored in the next part of this series.