The Quantum Threat to Bitcoin: How Your Cryptocurrency Could Be Stolen in Under 10 Minutes

The first part of this series delved into the fundamentals of quantum computing, explaining how it differs from classical computing and the underlying physics that drive it. However, understanding the mechanics of quantum computing is only half the story; the other half involves grasping what it can attack and how. This piece focuses on bitcoin, specifically how its encryption works, why a quantum algorithm can break it, and the implications of Google's recent research on the timeline for such an attack. Bitcoin relies on a system called elliptic curve cryptography to verify ownership. Each 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. This relationship is a one-way function, meaning it's easy to generate a public key from a private key but virtually impossible for classical computers to reverse the process. The security of bitcoin hinges on this one-way trapdoor, with private keys proving ownership and public keys being safe to share because they can't be used to derive the private key. However, the discovery of Shor's algorithm by mathematician Peter Shor in 1994 introduced a method by which a quantum computer could efficiently solve the discrete logarithm problem, thus breaking the encryption. Shor's algorithm works by converting the problem of finding a private key into finding the period of a function related to the elliptic curve. Quantum computers can evaluate this function for all possible inputs simultaneously, apply a quantum operation to reinforce the correct answers, and then measure the result to find the period, from which the private key can be easily derived. The algorithm utilizes the principles of superposition, entanglement, and interference to achieve this. Despite Shor's algorithm being known for over 30 years, its implementation has been hindered by the requirement for 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, along with the design of quantum circuits that can implement Shor's algorithm against bitcoin's elliptic curve, brings the threat closer to reality. The research also introduced a practical attack scenario where parts of the calculation can be precomputed, leaving a quantum computer to finish the calculation in about nine minutes once a target public key is identified. This timeframe is particularly concerning given that bitcoin's average block confirmation time is 10 minutes, offering a window of opportunity for a quantum attacker to derive a private key and redirect funds. The situation is more dire for the approximately 6.9 million bitcoin that have public keys already exposed on the blockchain, as these are vulnerable to attack without any time constraint. The implications of these findings and the potential countermeasures will be explored in the next part of this series.