The Quantum Threat to Bitcoin: How a Quantum Computer Can Steal Your Cryptocurrency in Under 10 Minutes

This series previously explored the physics of quantum computing. However, understanding how a quantum computer works is not the same as knowing how it can be used to steal bitcoin. To grasp the latter, one must comprehend what a quantum computer is attacking, how bitcoin's security is established, and where the vulnerability lies. This piece delves into bitcoin's encryption, the role of elliptic curve cryptography, and the nine-minute window identified by Google's recent quantum computing paper. Bitcoin utilizes a system called elliptic curve cryptography to verify ownership. Each wallet has two keys: a private key, which is a secret number, and a public key derived from the private key through a mathematical operation on the 'secp256k1' curve. This process can be thought of as a one-way map, where starting from a known location, taking a private number of steps leads to a public key that can be verified by anyone but cannot be reversed to find the private key. The security of bitcoin relies on this one-way trapdoor, with the private key proving ownership and the public key being safe to share because classical computers cannot reverse the math. However, a quantum algorithm known as Shor's algorithm can break this trapdoor efficiently. Discovered by mathematician Peter Shor in 1994, this algorithm solves the discrete logarithm problem in polynomial time, making it significantly faster than classical algorithms for large numbers. The intuition behind Shor's algorithm involves converting the problem into finding the period of a function, which is a task well-suited for quantum computers due to their ability to represent all possible values simultaneously and apply functions to them at once. Quantum computers can put their input register into a superposition, apply a function to all possible inputs simultaneously, and then use a quantum operation called the Fourier transform to reinforce correct answers and cancel out wrong ones. Although Shor's algorithm has been known for over 30 years, its implementation has been hindered by the requirement for a quantum computer with a large enough number of stable qubits to maintain coherence throughout the calculation. 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, coupled with the design of quantum circuits that implement Shor's algorithm against bitcoin's specific elliptic curve, brings the threat of a quantum attack closer to reality. Google's paper introduced a practical attack scenario where parts of Shor's algorithm 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 timeline introduces a 'mempool attack' scenario where an attacker has roughly nine minutes to derive a private key and submit a competing transaction that redirects funds, posing a significant threat to bitcoin transactions. Furthermore, approximately 6.9 million bitcoin, or one-third of the total supply, are sitting in wallets where the public key has already been exposed, making them vulnerable to an 'at-rest' attack that does not require racing against the clock.