How Quantum Computing Can Compromise Bitcoin Security in Under 10 Minutes

The first part of this series explored the fundamental principles of quantum computing, distinguishing it from classical computing. However, understanding the inner workings of quantum computers doesn't directly explain how they can be utilized to steal bitcoin. To grasp this, it's essential to comprehend what quantum computers are attacking and the inherent weaknesses in bitcoin's security framework. This piece begins by examining bitcoin's encryption methodology, leading up to the critical nine-minute window, as identified by Google's recent quantum computing research, within which bitcoin's security can be compromised. Bitcoin employs a system known as 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 envisioned as a one-way map, where starting from a known point on the curve, taking a certain number of steps defined by the curve's mathematics leads to the public key. While it's straightforward to calculate the public key from the private key, reversing this process is virtually impossible for classical computers due to the elliptic curve discrete logarithm problem. It's estimated that solving this problem for a 256-bit curve with the best-known classical algorithms would take longer than the age of the universe. This one-way function is the cornerstone of bitcoin's security model, allowing for the safe sharing of public keys without compromising private keys. When sending bitcoin, the wallet uses the private key to create a digital signature, proving knowledge of the secret number without revealing it. The discovery of Shor's algorithm by mathematician Peter Shor in 1994 introduced a quantum method to efficiently solve the discrete logarithm problem, thereby breaking the security trapdoor. This 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 adept at this task due to their ability to represent all possible inputs simultaneously (superposition), apply functions 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 of the function, from which the private key can be easily derived. Shor's algorithm leverages the three key properties of quantum mechanics: superposition, entanglement, and interference, making it a formidable tool against bitcoin's encryption. Despite Shor's algorithm being known for over 30 years, its application has been hindered by the requirement for 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 from millions to fewer than 500,000, a reduction of roughly 20-fold. This breakthrough involved designing quantum circuits that implement Shor's algorithm against bitcoin's specific elliptic curve, with requirements of approximately 1,200 to 1,450 logical qubits and tens of millions of Toffoli gates. Given that qubits are highly prone to losing their quantum state, hundreds of physical qubits are needed to maintain a single reliable logical qubit, explaining the vast difference between physical and logical qubit counts. The introduction of a practical attack scenario by Google's research changes the perspective on the quantum threat to bitcoin. Parts of Shor's algorithm that depend on the elliptic curve's fixed, publicly known parameters can be precomputed, allowing a quantum computer to be in a 'primed' state, ready to complete the calculation once a target public key is identified. Google estimates that completing the second half of the calculation takes about nine minutes, which is critically close to bitcoin's average block confirmation time of 10 minutes. This creates a narrow window for a quantum attacker to derive a private key and submit a competing transaction, with a roughly 41% chance of succeeding before the original transaction is confirmed. The primary concern, however, 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. The implications of this vulnerability, including the impact of Taproot and the rapid advancement of quantum hardware, will be explored in the next part of this series.