How Quantum Computers Pose a Threat to Bitcoin Security in Under 10 Minutes

The first part of this series explored the fundamental principles of quantum computing. However, understanding the mechanics of quantum computers doesn't directly reveal how they can be used to compromise bitcoin security. To grasp this, one must comprehend what aspect of bitcoin's security is being targeted and where the vulnerabilities lie. This piece begins by examining bitcoin's encryption method, explaining how it works, why a quantum algorithm can break it, and the significance of Google's recent paper on quantum computing, which has altered the perceived timeline of this threat. Bitcoin utilizes a system known as elliptic curve cryptography to verify ownership. Each wallet has a pair of 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 can be visualized as a one-way map, where starting from a known point on the curve, taking a certain number of steps (defined by the private key) leads to the public key. Anyone can confirm the public key without being able to deduce the private key. Technically, this relationship is expressed as K = k * G, where k is the private key and K is the public key. The 'multiplication' here is a geometric operation along the curve, making it easy to calculate K from k and G, but virtually impossible to reverse-engineer k from K and G using classical computers. This one-way function is the backbone of bitcoin's security model. The private key serves as proof of ownership, and the public key can be safely shared since classical computers cannot reverse the mathematical process. When sending bitcoin, the wallet uses the private key to create a digital signature, proving knowledge of the secret number without revealing it. However, 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. The intuition behind Shor's algorithm relates to the properties of quantum mechanics: superposition, entanglement, and interference. By putting the input register into a superposition, representing all possible values simultaneously, and applying a function and then a Fourier transform, the algorithm can find the period of a function, which directly leads to the solution of the discrete logarithm problem and thus to the private key. The reason bitcoin remains secure for now is that implementing Shor's algorithm requires a quantum computer with a sufficiently large number of stable qubits. Recent estimates by Google's Quantum AI division, in collaboration with researchers from the Ethereum Foundation and Stanford, have significantly reduced the number of qubits needed, from millions to fewer than 500,000. This reduction, alongside the design of quantum circuits that can implement Shor's algorithm against bitcoin's elliptic curve, signals a potential threat. The team's design uses approximately 1,200 to 1,450 logical qubits and tens of millions of Toffoli gates, which are quantum gates that act on three qubits. Given that qubits are prone to losing their quantum state, hundreds of redundant qubits are needed to maintain a single reliable logical qubit, explaining the vast difference between physical and logical qubits. Google's paper also introduced a practical attack scenario, suggesting that parts of Shor's algorithm can be precomputed, leaving the quantum computer in a primed state. Once a target public key is identified, the machine only needs to complete the second half of the calculation, which Google estimates takes about nine minutes. This timeline is critical because it coincides with bitcoin's average block confirmation time of 10 minutes. If a user broadcasts a transaction, a quantum attacker has roughly nine minutes to derive the private key and submit a competing transaction. The attacker has a 41% chance of succeeding before the original transaction is confirmed. 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 already vulnerable due to their public keys being exposed on the blockchain. These coins are susceptible to an 'at-rest' attack, where the attacker has unlimited time to derive the private key. The implications of this vulnerability, the impact of Taproot on bitcoin's privacy, and how the development of quantum hardware is narrowing the gap to this threat are critical considerations for the future of bitcoin security.