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

The first part of this series delved into the fundamental principles of quantum computing, explaining how these machines differ from classical computers and harness the unique properties of quantum mechanics. However, understanding the inner workings of a quantum computer is only half the story; to comprehend how it could be used to steal bitcoin, one must also grasp what it is that the quantum computer is attacking - namely, the encryption that underpins bitcoin's security. This article will delve into the specifics of bitcoin's encryption, why a quantum algorithm can break it, and the implications of a recent paper by Google on the timeline for such an attack. Bitcoin's security relies on a system known as elliptic curve cryptography, which enables the proof of ownership. Each wallet has a pair of keys: a private key, which is a secret number, and a public key, which is derived from the private key through a mathematical operation on a specific curve known as 'secp256k1'. This 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 mathematics leads to the public key. While moving forward in this map is straightforward, reversing the process - determining the private key from the public 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. However, the advent of quantum computing, particularly with the development of Shor's algorithm, changes this landscape. Shor's algorithm is a quantum algorithm that can efficiently solve the discrete logarithm problem, thereby breaking the encryption that secures bitcoin. The algorithm works by converting the problem of finding the private key into a problem of finding the period of a function related to the elliptic curve. Quantum computers are particularly adept at this task due to their ability to exist in a superposition, allowing them to evaluate the function for all possible inputs simultaneously, and then use quantum operations like the Fourier transform to find the period. Once the period is known, the private key can be easily determined, allowing an attacker to access the bitcoin. The attack utilizes all three primary properties of quantum computing: superposition, entanglement, and interference, to efficiently solve the discrete logarithm problem. Despite Shor's algorithm being known for over 30 years, its application has been hindered by the requirement for a large number of stable qubits to maintain coherence throughout the calculation. Recent estimates, including a paper by Google, suggest that the number of qubits required might be significantly lower than previously thought, potentially fewer than 500,000. This reduction, coupled with advancements in quantum computing hardware, brings the threat of a quantum attack on bitcoin closer to reality. The Google paper introduced a practical attack scenario where parts of Shor's algorithm that depend on fixed, publicly known parameters of the elliptic curve can be precomputed, allowing the quantum computer to be in a 'primed' state, ready to complete the calculation once a target public key is identified. For public keys that have already been exposed on the blockchain, the attack can be executed without time pressure, posing a significant risk to approximately 6.9 million bitcoin. For others, the window of vulnerability is roughly nine minutes - the time it takes for a quantum computer to derive the private key after a public key is broadcast in a transaction, which is just shorter than bitcoin's average block confirmation time of 10 minutes. This creates a race against time, where an attacker has about a 41% chance of succeeding in redirecting funds before the original transaction is confirmed. While the quantum computer capable of executing such an attack does not yet exist, the rapidly advancing field of quantum computing and the decreasing estimates of required qubits make this a pressing concern for bitcoin's security.