The Quantum Threat to Bitcoin: How a Powerful Computer Can Steal Your Cryptocurrency in Under 10 Minutes

The first part of this series explored the fundamental principles of quantum computing, explaining how these machines differ from classical computers by leveraging the unique rules of physics at the atomic and particle level. However, understanding the inner workings of a quantum computer does not directly reveal how it could be used by malicious actors to compromise bitcoin security. To grasp this, one must comprehend the target - the encryption mechanism of bitcoin, why a quantum algorithm poses a threat, and the implications of Google's recent research on the timeline of such an attack. This piece begins with an examination of bitcoin's encryption system, known as elliptic curve cryptography, which is used to verify ownership. Each wallet possesses two keys: a private key, which is a secret number, and a public key, derived from the private key through a mathematical operation on the elliptic curve secp256k1. The relationship between these keys can be thought of as a one-way map, where starting from a known point (the generator point G) 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 to find the private key from the public key is virtually impossible for classical computers, due to the elliptic curve discrete logarithm problem. This problem is so complex that the best-known classical algorithms would require more time than the age of the universe to solve for a 256-bit curve. The security of bitcoin relies on this one-way trapdoor, where the private key proves ownership, and the public key can be shared safely because no classical computer can reverse the math to find the private key. When sending bitcoin, the wallet uses the private key to create a digital signature, a mathematical proof that the sender knows the secret number without revealing it. However, the discovery of Shor's algorithm by mathematician Peter Shor in 1994 introduced a quantum algorithm that can efficiently solve the discrete logarithm problem, thus breaking the trapdoor. Shor's algorithm works by converting the problem of finding the private key into finding the period of a function related to the elliptic curve. Quantum computers are particularly suited for this task because they can represent all possible inputs simultaneously in a superposition, apply the function to all inputs at once, and then use a quantum operation called the Fourier transform to reinforce the correct answers while canceling out the wrong ones. The result is the period of the function, from which the private key can be easily derived. This process utilizes the three main properties of quantum computing: superposition to evaluate the function on all possible inputs at once, entanglement to correlate the inputs and outputs, and interference to filter out the noise and leave only the correct answer. Despite Shor's algorithm being known for over 30 years, the reason bitcoin remains secure is that implementing this algorithm requires a quantum computer with a sufficiently large number of stable qubits to maintain coherence throughout the calculation. Recent estimates by Google's Quantum AI division, in collaboration with researchers from the Ethereum Foundation and Stanford, have reduced the required number of qubits from millions to fewer than 500,000, a reduction of about 20-fold from previous estimates. The team designed quantum circuits that can implement Shor's algorithm against bitcoin's elliptic curve, using approximately 1,200 to 1,450 logical qubits and tens of millions of Toffoli gates. A significant aspect of this research is not just the reduction in qubit count but the introduction of a practical attack scenario. Parts of Shor's algorithm that depend on fixed parameters of the elliptic curve can be precomputed, allowing the quantum computer to be in a primed state, ready to finish the calculation once a target public key is identified. Google estimates that finishing the second half of the calculation takes about nine minutes. Given that bitcoin's average block confirmation time is 10 minutes, a quantum attacker has a narrow window to derive a private key and submit a competing transaction. This scenario presents a 41% chance of success for the attacker. The more alarming concern, however, is for the approximately 6.9 million bitcoin (about one-third of the total supply) that are in wallets where the public key has already been exposed on the blockchain. These coins are vulnerable to an 'at-rest' attack, which does not require racing against the clock. A quantum computer running Shor's algorithm can derive the private key from the public key, giving access to the coins. 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, at which point the owner has roughly nine minutes before the attacker can catch up.