The Threat of Quantum Computing to Bitcoin Security: A 9-Minute Window to Steal

The first part of this series delved into the physics of quantum computing, explaining how it differs from classical computing. However, understanding the mechanics of quantum computing is only half the story. To grasp how it can be used to steal bitcoin, one must comprehend what it is attacking - the security framework of bitcoin, and where its weaknesses lie. This piece begins by examining bitcoin's encryption method, elliptic curve cryptography, and how a quantum algorithm can break it, as outlined in Google's recent paper. The process involves a one-way map, where a private key is used to derive a public key through a mathematical operation on a specific curve, known as secp256k1. The public key can be shared safely because classical computers cannot reverse the math to obtain the private key. However, a quantum algorithm, known as Shor's algorithm, can efficiently solve the discrete logarithm problem, thereby breaking the encryption. This algorithm exploits the properties of quantum computing, including superposition, entanglement, and interference, to find the period of a function, which is crucial for deriving the private key. The recent paper by Google's Quantum AI division, in collaboration with researchers from the Ethereum Foundation and Stanford, has reduced the estimated number of qubits required to run Shor's algorithm against bitcoin's elliptic curve from millions to fewer than 500,000. The team designed quantum circuits that can implement Shor's algorithm, one of which uses approximately 1,200 logical qubits and 90 million Toffoli gates. The introduction of a practical attack scenario has significant implications for the security of bitcoin. The parts of Shor's algorithm that depend 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 public key is visible, the machine only needs to finish the second half of the calculation, which Google estimates takes about nine minutes. This creates a narrow window for a quantum attacker to derive a private key and submit a competing transaction. The average block confirmation time for bitcoin is 10 minutes, giving the attacker a roughly 41% chance of succeeding. Furthermore, approximately 6.9 million bitcoin, or one-third of the total supply, are vulnerable to an 'at-rest' attack, as their public keys have already been exposed on the blockchain. These coins can be targeted without any time constraint, making them particularly susceptible to quantum attacks. The implications of these findings and the potential consequences for bitcoin security will be explored in the next part of this series.