The Quantum Threat to Bitcoin: How Your Coins Can Be Stolen in Under 10 Minutes

The first part of this series delved into the fundamentals of quantum computing, explaining how these machines differ from classical computers by leveraging the unique rules of physics at the atomic and particle level. However, understanding the mechanics of quantum computers doesn't directly reveal how they can be used to steal bitcoin. To grasp this, one must comprehend what quantum computers attack and how the security of bitcoin is structured, including the specific vulnerabilities. This piece begins by examining bitcoin's encryption method, known as elliptic curve cryptography, which is used to verify ownership. Every bitcoin wallet has a pair of 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 curve's math leads to the public key. While anyone can verify the public key, determining the private key (the number of steps taken) 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 universe's age to solve for a 256-bit curve. The security of bitcoin relies on this one-way trapdoor, with private keys proving ownership and public keys being safe to share since classical computers cannot reverse the math. When sending bitcoin, the wallet uses the private key to create a digital signature, proving knowledge of the secret number without revealing it. However, a quantum algorithm discovered by Peter Shor in 1994 can break this trapdoor efficiently. Shor's algorithm solves the discrete logarithm problem in polynomial time, meaning the difficulty increases slowly with larger numbers, unlike the exponential growth seen in classical algorithms. The algorithm works by converting the problem into finding the period of a function related to the elliptic curve, which is a task suited for quantum computers. By putting the input register into a superposition (representing all possible values simultaneously), applying the function, and then using a quantum Fourier transform to filter out incorrect answers, the period can be found. From this period, the private key can be derived, allowing access to the bitcoin. This attack utilizes the three key properties of quantum computing: superposition, entanglement, and interference. Despite Shor's algorithm being known for over 30 years, the reason bitcoin remains secure is the requirement for a quantum computer with a large number of stable qubits to run the algorithm. Recent estimates by Google, 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, a 20-fold reduction. Google designed two quantum circuits implementing Shor's algorithm against bitcoin's elliptic curve, requiring approximately 1,200 and 1,450 logical qubits, respectively, along with millions of Toffoli gates. The practicality of this attack scenario has changed, with parts of the algorithm that can be precomputed, allowing the quantum computer to be in a 'primed' state, ready to finish the calculation once a target public key appears. Google estimates this second phase takes about nine minutes, which is significant because it's close to bitcoin's average block confirmation time of 10 minutes. This means a quantum attacker has a roughly 41% chance of deriving a private key and submitting a competing transaction before the original transaction confirms, known as the 'mempool attack.' Although alarming, this requires a quantum computer that does not yet exist. A more pressing concern is the approximately 6.9 million bitcoin (about one-third of the total supply) in wallets where the public key has been exposed on the blockchain, making them vulnerable to an 'at-rest' attack that doesn't race against the clock. For coins transacted since the Taproot upgrade, the public key is already visible, and for older addresses, the key is hidden until spent, at which point there's a nine-minute window of vulnerability. The implications of these findings, including which 6.9 million bitcoin are exposed, the impact of Taproot, and how quickly hardware is advancing, will be discussed in the final piece of this series.