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 of quantum computing, explaining how these machines differ fundamentally from regular computers. However, understanding the inner workings of a quantum computer doesn't reveal how it can be used to steal bitcoin. To grasp this, one must comprehend what a quantum computer attacks and how the security of bitcoin is structured, including its weaknesses. This piece begins with an examination of bitcoin's encryption, leading to the crucial nine-minute window identified by Google's recent quantum computing paper. Bitcoin utilizes 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 process can be thought of as a one-way map, where starting from a known point (the generator point G), taking a certain number of steps defined by the curve's math (the private key) leads to a public key (point K). Anyone can verify the public key, but figuring out 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 hinges 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 math. When sending bitcoin, the wallet uses the private key to create a digital signature without revealing it. However, Peter Shor's algorithm, discovered in 1994, breaks this trapdoor using quantum computing. Shor's algorithm efficiently solves the discrete logarithm problem, handling the math in polynomial time, which means the difficulty grows slowly as numbers increase. The algorithm converts finding the private key into a problem of finding the period of a function related to the elliptic curve. Quantum computers are ideal for this task because they can put their input register into a superposition, representing all possible values simultaneously, apply the function to all of them at once, and then use a quantum operation called the Fourier transform to find the period. From this period, ordinary math can recover the private key, thus accessing the coins. This process utilizes superposition, entanglement, and interference - the three quantum properties discussed in the first piece. Despite Shor's algorithm being known for over 30 years, running it requires a quantum computer with a large number of stable qubits, which has been out of reach. Google's recent paper reduced the estimated number of qubits needed from millions to fewer than 500,000, a 20-fold reduction. The team designed quantum circuits that implement Shor's algorithm against bitcoin's elliptic curve, using approximately 1,200 to 1,450 logical qubits and millions of Toffoli gates. 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 quantum computing. Google's paper introduced a practical attack scenario, where parts of Shor's algorithm can be precomputed, leaving the quantum computer in a primed state, ready to finish the calculation once a target public key appears. This could take about nine minutes, which is close to bitcoin's average block confirmation time of 10 minutes. If a user broadcasts a transaction with their public key visible, a quantum attacker has roughly nine minutes to derive the private key and submit a competing transaction. The attacker has a 41% chance of succeeding before the original transaction confirms. This 'mempool attack' is alarming but requires a quantum computer that does not yet exist. A more significant concern is the 6.9 million bitcoin (about 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 that does not require racing against the clock. A quantum computer running Shor's algorithm can turn a bitcoin public key into the controlling private key. For coins transacted since the Taproot upgrade, the public key is already visible, while for coins in older addresses, the public key is hidden until spent, leaving a nine-minute window before an attacker can catch up.