How Quantum Computers Can Compromise Bitcoin Security in Under 10 Minutes

The first part of this series explored the foundational physics of quantum computing, revealing it as a fundamentally distinct type of machine that leverages the unique rules of physics at the atomic and particle level. However, understanding the operation of a quantum computer does not directly inform us on how it could be utilized by malicious actors to steal bitcoin. This necessitates a comprehension of the target - how bitcoin's security is structured, the nature of its encryption, why a quantum algorithm can break it, and the significance of Google's recent paper in altering the timeline of potential threats. This piece commences with an examination of bitcoin's encryption, traversing through to the nine-minute window identified by Google's quantum computing paper, within which the encryption can be broken. Bitcoin employs a system known as elliptic curve cryptography to authenticate 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 specific curve 'secp256k1'. This can be conceptualized as a one-way map, where starting from a known location on the curve, taking a private number of steps leads to a public key. Anyone can verify the endpoint, but determining the number of steps taken is practically impossible for classical computers. Technically, this is expressed as K = k × G, where k is the private key and K is the public key, with the 'multiplication' being a geometric operation along the curve. The critical property is that moving forward is straightforward, while reversing is virtually impossible for classical computers. If one knows k and G, calculating K is instantaneous, but if one knows K and G and seeks to find k, they are confronted with the elliptic curve discrete logarithm problem, which is estimated to take longer than the age of the universe for the best-known classical algorithms. This one-way trapdoor underpins bitcoin's entire security model, with the private key serving as proof of ownership and the public key being safe to share since no classical computer can reverse the math. When sending bitcoin, the wallet uses the private key to create a digital signature, a mathematical proof of knowing the secret number without revealing it. Shor's algorithm, discovered in 1994, breaks this trapdoor by solving the discrete logarithm problem efficiently, handling it in polynomial time. The intuition behind its operation stems from the three quantum properties: superposition, entanglement, and interference. The algorithm converts finding the private key k into a problem of finding the period of a function, which is exactly what quantum computers are designed for. By putting the input register into a superposition, representing all possible values simultaneously, and applying the function to all of them at once, followed by a quantum operation called the Fourier transform, the period appears, from which the private key can be recovered. This attack utilizes all three quantum tricks: superposition evaluates the function on every possible input at once, entanglement links the input and output, and interference filters the noise until only the answer remains. Despite Shor's algorithm being known for over 30 years, running it requires a quantum computer with a large enough number of stable qubits to maintain coherence throughout the calculation, a feat that has been beyond reach. Google's paper reduced the required number of qubits from millions to fewer than 500,000, a roughly 20-fold reduction. The team designed two quantum circuits implementing Shor's algorithm against bitcoin's specific elliptic curve, one using approximately 1,200 logical qubits and 90 million Toffoli gates, and the other using approximately 1,450 logical qubits and 70 million Toffoli gates. A Toffoli gate acts on three qubits, with two control qubits affecting the state of a third target qubit. Due to qubits constantly losing their quantum state, hundreds of redundant qubits are needed to maintain a single reliable logical qubit, reflecting the extensive self-babysitting infrastructure within a quantum computer. 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 sit in a primed state, waiting for a target public key to appear. Once a target public key is broadcast or exposed on the blockchain, the machine only needs to finish the second half of the calculation, estimated to take about nine minutes. Given bitcoin's average block confirmation time of 10 minutes, an attacker has roughly nine minutes to derive a private key and submit a competing transaction, with a 41% chance of succeeding before the original transaction confirms. This mempool attack, while alarming, requires a quantum computer that does not yet exist. A more significant concern is the 6.9 million bitcoin already vulnerable to an 'at-rest' attack, where the public key has been permanently exposed on the blockchain, allowing an attacker to take as long as needed to derive the private key. For coins transacted since Taproot, the public key is already visible, while for older addresses, the public key is hidden until spent, at which point the owner has roughly nine minutes before the attacker can catch up. The practical implications of these findings, including which 6.9 million bitcoin are exposed, the impact of Taproot, and how quickly the hardware is closing the gap, will be explored in the next piece of this series.