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 mechanics of quantum computers doesn't reveal how they can be used to steal bitcoin. To grasp this, one must comprehend what quantum computers are attacking - the security framework of bitcoin - and where its weaknesses lie. This piece begins by examining bitcoin's encryption method, known as elliptic curve cryptography, which is used 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 a specific curve called 'secp256k1'. 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 a public key. Anyone can verify the public key, but classical computers cannot reverse-engineer the private key due to the complexity of the elliptic curve discrete logarithm problem. In fact, it's estimated that solving this problem for a 256-bit curve using the best-known classical algorithms would take longer than the age of the universe. The security of bitcoin relies on this one-way trapdoor, with private keys proving ownership and public keys being safe to share. When sending bitcoin, the wallet uses the private key to create a digital signature without revealing the key itself. However, a quantum algorithm known as Shor's algorithm, discovered by mathematician Peter Shor in 1994, can break this trapdoor. Shor's algorithm solves the discrete logarithm problem efficiently, handling the math in what's known as polynomial time. The algorithm works by converting the problem of finding the private key into finding the period of a function related to the elliptic curve. This is achieved by putting the input register into a superposition, allowing the function to be applied to all possible values simultaneously, and then using a quantum operation called the Fourier transform to filter out incorrect answers. The result is the period of the function, from which the private key can be derived. This process utilizes the three quantum properties discussed in the first part of the series: superposition, entanglement, and interference. Despite Shor's algorithm being known for over 30 years, running it has been beyond reach due to the requirement for a large number of stable qubits to maintain coherence throughout the calculation. Recent research by Google, in collaboration with Ethereum Foundation and Stanford cryptographer Dan Boneh, has reduced the estimated number of qubits needed from millions to fewer than 500,000. The team designed quantum circuits that implement Shor's algorithm against bitcoin's specific elliptic curve, with one circuit using approximately 1,200 logical qubits and another using about 1,450 logical qubits. Because qubits lose their quantum state constantly, hundreds of redundant qubits are needed to maintain a single reliable logical qubit, reflecting the significant infrastructure required for a quantum computer to function accurately. Google's paper also introduced a practical attack scenario that changes the perspective on the threat. Parts of Shor's algorithm that depend on the elliptic curve's fixed parameters can be precomputed, allowing the quantum computer to sit in a primed state, waiting for a target public key to appear. Once a public key is broadcast or exposed on the blockchain, 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, a quantum attacker has roughly nine minutes to derive a private key and submit a competing transaction. This 'mempool attack' gives the attacker a 41% chance of succeeding before the original transaction confirms. More alarmingly, approximately 6.9 million bitcoin, or one-third of the total supply, are sitting in wallets where the public key has already been exposed on the blockchain, making them vulnerable to an 'at-rest' attack that doesn't require racing against the clock. A quantum computer running Shor's algorithm can turn a bitcoin public key into the private key that controls the coins, posing a significant threat to the security of the bitcoin network.