How Quantum Computing Can Compromise Bitcoin Security in Under 10 Minutes

The first part of this series explored the fundamental principles of quantum computing. However, understanding how quantum computers work is only half the story; the other half involves grasping what they can attack and how they can be used to compromise bitcoin's security. This piece will examine the encryption used by bitcoin, why quantum algorithms can break it, and the implications of a recent paper by Google on the timeline for such an attack. Bitcoin utilizes elliptic curve cryptography, a system that relies on a pair of keys: a private key, which is a secret number, and a public key, derived from the private key through a mathematical operation. The relationship between the two keys can be thought of as a one-way map, where it's easy to generate the public key from the private key but virtually impossible to reverse the process using classical computers. This one-way function is the backbone of bitcoin's security model, allowing users to prove ownership without revealing their private key. The security of this system is based on the difficulty of solving the elliptic curve discrete logarithm problem, which is estimated to take longer than the age of the universe for classical computers. However, the advent of quantum computing and the discovery of Shor's algorithm have introduced a new variable into this equation. Shor's algorithm is a quantum algorithm that can efficiently solve the discrete logarithm problem, thereby breaking the encryption used by bitcoin. The algorithm works by converting the problem into finding the period of a function, which is a task that quantum computers are particularly well-suited for. By leveraging the principles of superposition, entanglement, and interference, a quantum computer can evaluate the function for all possible inputs simultaneously, apply a quantum operation to reinforce the correct answers, and measure the result to find the period. Knowing the period allows for the easy calculation of the private key, effectively breaking the encryption. Despite the potential of Shor's algorithm, its implementation has been hindered by the requirement for a large number of stable qubits. Recent estimates suggest that the number of qubits needed might be lower than previously thought, with Google's paper proposing that fewer than 500,000 qubits could be sufficient. This reduction in the estimated number of qubits, combined with advancements in quantum computing hardware, brings the possibility of a quantum attack on bitcoin's encryption closer to reality. The introduction of a practical attack scenario, where parts of the calculation can be precomputed and the quantum computer can be primed to finish the calculation once a target public key appears, has significant implications. It suggests that once a public key is visible, an attacker has a limited window, approximately nine minutes, to derive the private key and submit a competing transaction. For the 6.9 million bitcoin with public keys already exposed on the blockchain, the risk is even more pronounced, as an attacker can take as long as needed to derive the private key. The race to develop quantum-resistant cryptography and the potential consequences of a quantum attack on bitcoin's security are topics that will be explored further in the next part of this series.