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

The first part of this series delved into the physics behind quantum computing, explaining how these machines differ fundamentally from classical computers. However, understanding the inner workings of a quantum computer doesn't reveal how it can be used to steal bitcoin. To grasp this, one must comprehend what a quantum computer attacks and how the security of bitcoin is structured, including the specific vulnerabilities it exploits. This piece begins by examining bitcoin's encryption method, known as elliptic curve cryptography, which is used to verify ownership. Each bitcoin wallet has two 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. The process 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 private key) leads to a public key. While anyone can verify the public key, determining the private key (the number of steps) is virtually impossible for classical computers due to the elliptic curve discrete logarithm problem. This problem is so complex that even the best classical algorithms would take longer than the age of the universe to solve for a 256-bit curve. The security of bitcoin relies on this one-way trapdoor, where the private key proves ownership, and the public key can be safely shared without compromising the private key. However, in 1994, mathematician Peter Shor discovered a quantum algorithm that can efficiently break this trapdoor by solving the discrete logarithm problem in polynomial time. Shor's algorithm converts the problem into finding the period of a function related to the elliptic curve, which quantum computers can solve efficiently by leveraging superposition, entanglement, and interference. The algorithm represents all possible inputs simultaneously, applies the function to them, and then uses the Fourier transform to filter out incorrect answers, leaving the correct period, from which the private key can be derived. Despite Shor's algorithm being known for over 30 years, running it has been beyond reach due to the requirement for a quantum computer with a large number of stable qubits. Recent estimates by Google's Quantum AI division, along with contributions from other researchers, have significantly reduced the number of qubits needed, from millions to fewer than 500,000. This reduction introduces a practical attack scenario where parts of Shor's algorithm can be precomputed, waiting for a target public key to appear. Once a public key is visible, the quantum computer only needs to finish the second half of the calculation, which Google estimates takes about nine minutes. Given that bitcoin's average block confirmation time is 10 minutes, an attacker has a roughly 41% chance of deriving a private key and submitting a competing transaction before the original transaction confirms. This 'mempool attack' is alarming but requires a quantum computer that does not yet exist. A more significant concern is the 6.9 million bitcoin (about one-third of the total supply) in wallets where the public key has already been exposed on the blockchain, making them vulnerable to an 'at-rest' attack without any time constraint. The implications of these findings and the developments in quantum computing hardware will be discussed in the final piece of this series.