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 it differs from traditional computing. However, understanding the mechanics of quantum computers doesn't directly reveal how they can be used to steal bitcoin. To grasp this, it's essential to comprehend what quantum computers are attacking and where the vulnerabilities lie in bitcoin's security. This piece begins by examining bitcoin's encryption, leading up to the nine-minute window identified by Google's recent quantum computing paper, during which a quantum computer could potentially break bitcoin's encryption. 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, taking a certain number of steps defined by the curve's math leads to the public key. Anyone can verify the public key, but determining the number of steps taken (the private key) is virtually impossible for classical computers. The security model of bitcoin relies 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, proving knowledge of the secret number without revealing it. However, Shor's algorithm, discovered in 1994, breaks this trapdoor by solving the discrete logarithm problem efficiently using quantum properties. The algorithm converts finding the private key into a problem of finding the period of a function related to the elliptic curve. By representing all possible inputs simultaneously through superposition, applying the function, and then using the Fourier transform to filter out incorrect answers, the period is found, from which the private key can be derived. This process utilizes the three quantum properties of 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. Google's recent paper reduced the estimated number of qubits needed from millions to fewer than 500,000, introducing a practical attack scenario. The paper designed quantum circuits that implement Shor's algorithm against bitcoin's elliptic curve, requiring approximately 1,200 to 1,450 logical qubits and millions of Toffoli gates. Because qubits constantly lose their quantum state, hundreds of redundant qubits are needed to maintain a single reliable logical qubit. Google's paper also introduced the concept of precomputing parts of Shor's algorithm that depend on the elliptic curve's fixed parameters, allowing the quantum computer to sit in a primed state. Upon encountering a target public key, the machine only needs to finish the second half of the calculation, which Google estimates takes about nine minutes. This creates a window of opportunity for a quantum attacker to derive a private key and submit a competing transaction. The average block confirmation time for bitcoin is 10 minutes, giving the attacker a roughly 41% chance of succeeding before the original transaction confirms. This attack 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. For coins transacted since the Taproot upgrade, the public key is already visible, while for older addresses, the public key is hidden until spent, leaving a nine-minute window before an attacker can catch up. The practical implications of these findings and how the hardware gap is closing will be discussed in the next piece.