Unlocking Bitcoin's Security: How Quantum Computers Can Breach Encryption in Under 10 Minutes

The first part of this series explored the fundamental principles of quantum computing. However, understanding how these computers work does not directly reveal how they can be utilized to compromise bitcoin security. To grasp this, one must comprehend what aspect of bitcoin's security is being targeted and where the vulnerability lies. This piece begins with an examination of bitcoin's encryption methodology and progresses to the approximately nine-minute window required to breach it, as identified in Google's recent quantum computing research. Bitcoin employs a system known as elliptic curve cryptography to verify ownership. Each wallet possesses two keys: a private key, which is a secret number approximately 256 digits long in binary, and a public key derived from the private key through a mathematical operation on the 'secp256k1' curve. This can be thought of 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 a public key. Anyone can verify the endpoint, but determining the number of steps taken to get there is virtually impossible for classical computers. This one-way function is the foundation of bitcoin's security model. The private key serves as proof of ownership, while the public key can be safely shared because classical computers cannot reverse the mathematics. When sending bitcoin, the wallet uses the private key to create a digital signature, 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 trapdoor. Discovered by mathematician Peter Shor in 1994, this algorithm efficiently solves the discrete logarithm problem. While classical computers would take longer than the universe's age to solve this problem, Shor's algorithm can handle it in what is known as 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 adept at finding such periods due to their ability to represent all possible inputs simultaneously and apply functions to them all at once, thanks to superposition. By applying a quantum operation called the Fourier transform, the incorrect answers cancel out, leaving the correct period. From this period, ordinary mathematics can quickly recover the private key, thereby accessing the bitcoin. Shor's algorithm utilizes all three primary quantum mechanics principles: superposition to evaluate functions on all possible inputs at once, entanglement to keep inputs and outputs correlated, and interference to filter out incorrect answers. Despite Shor's algorithm being known for over 30 years, its application to break bitcoin's encryption has been hindered by the requirement for a quantum computer with a large number of stable qubits. Recent research by Google, in collaboration with the Ethereum Foundation and Stanford cryptographers, has significantly reduced the estimated number of qubits needed, from millions to fewer than 500,000. This reduction is crucial because it brings the feasibility of such an attack closer to reality. The team designed quantum circuits that implement Shor's algorithm against bitcoin's specific elliptic curve, requiring approximately 1,200 to 1,450 logical qubits and tens of millions of Toffoli gates. Given that qubits constantly lose their quantum state, hundreds of redundant qubits are needed to maintain a single reliable logical qubit, explaining the vast difference between physical and logical qubit counts. The research introduced a practical attack scenario, where parts of Shor's algorithm that depend on the elliptic curve's fixed parameters can be precomputed, leaving the quantum computer in a primed state, ready to finish the calculation once a target public key appears. Google estimates this second half of the calculation takes about nine minutes, which is alarming considering bitcoin's average block confirmation time is 10 minutes. This creates a narrow window for a quantum attacker to derive a private key and submit a competing transaction. The attacker has a roughly 41% chance of succeeding before the original transaction confirms. While this 'mempool attack' is concerning, it requires a quantum computer that does not yet exist. A more significant concern is the approximately 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 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, the impact of Taproot on bitcoin's privacy, and how quickly hardware is advancing to potentially close the gap are critical considerations for the future of bitcoin security.