How Quantum Computers Can Compromise Bitcoin Security in Under 10 Minutes

The first part of this series provided an overview of quantum computing's underlying physics. However, understanding how quantum computers work doesn't directly explain how they can be used to steal bitcoin. To grasp this, it's essential to understand what quantum computers are attacking - the security mechanism of bitcoin - and where the vulnerability lies. This piece begins by examining bitcoin's encryption method, which utilizes elliptic curve cryptography to verify ownership. Each wallet has a private key, a secret 256-digit binary 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 point on the curve (generator point G), taking a certain number of steps defined by the curve's mathematics leads to a public key. Anyone can verify the public key, but figuring out the number of steps (the private key) is virtually impossible for classical computers due to the elliptic curve discrete logarithm problem. It's estimated that solving this problem for a 256-bit curve with the best-known classical algorithms would take longer than the age of the universe. The security of bitcoin relies on this one-way trapdoor, where the private key proves ownership, and the public key is safe to share because classical computers cannot reverse the mathematics. When sending bitcoin, the wallet uses the private key to create a digital signature, proving knowledge of the secret number without revealing it. However, Shor's algorithm, discovered in 1994, can break this trapdoor using quantum computing. It efficiently solves the discrete logarithm problem by converting it into finding the period of a function related to the elliptic curve. This is achieved by representing all possible inputs simultaneously (superposition), applying the function to all inputs at once, and then using a quantum operation (Fourier transform) to cancel out wrong answers and reinforce the correct ones. The result is the period, from which the private key can be derived, thus potentially allowing access to the bitcoin. This algorithm utilizes the three quantum properties: superposition, entanglement, and interference. Despite Shor's algorithm being known for over 30 years, executing it has been beyond reach due to the requirement for a quantum computer with a large number of stable qubits. Recent research by Google, in collaboration with the Ethereum Foundation and Stanford University, has significantly reduced the estimated number of qubits needed, from millions to fewer than 500,000. This reduction comes from designing quantum circuits that implement Shor's algorithm against bitcoin's specific elliptic curve, requiring approximately 1,200 to 1,450 logical qubits and tens of millions of Toffoli gates. Because qubits constantly lose their quantum state, a large number of physical qubits are needed to maintain a smaller number of reliable logical qubits, with most of the quantum computer's infrastructure dedicated to error correction. The research also introduced a practical attack scenario where parts of Shor's algorithm can be precomputed, leaving the quantum computer in a primed state. When a target public key appears, the machine 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 window to derive a private key and submit a competing transaction, with a roughly 41% chance of succeeding before the original transaction confirms. This 'mempool attack' is concerning but requires a quantum computer that does not yet exist. A more significant concern is the approximately 6.9 million bitcoin (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. Quantum computers can turn a bitcoin public key into the private key controlling the coins, posing a significant threat to the security of these exposed coins, especially considering the advancements in quantum computing hardware.