The Quantum Threat to Bitcoin: How Your Cryptocurrency Could be Stolen in Under 10 Minutes

The first part of this series explored the fundamental principles of quantum computing, distinguishing it from classical computing. However, understanding the inner workings of a quantum computer is only half the story; it's equally important to comprehend how it can be utilized to compromise bitcoin's security. This involves grasping the cryptographic mechanisms that underpin bitcoin and identifying the vulnerabilities that a quantum computer can exploit. Bitcoin relies on elliptic curve cryptography, a system that utilizes a pair of keys: a private key, which is a secret number, and a public key, which is derived from the private key through a mathematical operation on the elliptic curve known as 'secp256k1'. The relationship between these keys can be visualized 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 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 even the most advanced classical algorithms would take longer than the age of the universe to solve for a 256-bit curve. The security of bitcoin is founded on this one-way trapdoor, where the private key serves as proof of ownership, and the public key can be shared without compromising security. However, the discovery of Shor's algorithm by mathematician Peter Shor in 1994 introduced a quantum approach that can efficiently solve the discrete logarithm problem. Shor's algorithm operates by converting the problem of finding the private key into a problem of finding the period of a function related to the elliptic curve. This is achieved by leveraging the principles of quantum mechanics, including superposition, entanglement, and interference, allowing the algorithm to evaluate the function for all possible inputs simultaneously and find the period. Once the period is determined, the private key can be easily recovered, thereby compromising the security of the bitcoin. The practical implementation of Shor's algorithm has been hindered by the requirement for a 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 significantly reduced the number of qubits needed, from millions to fewer than 500,000. This reduction is based on the design of two quantum circuits that implement Shor's algorithm against bitcoin's specific elliptic curve, requiring approximately 1,200 to 1,450 logical qubits and tens of millions of Toffoli gates. The introduction of a practical attack scenario by Google's paper has also changed the perspective on the quantum threat. By precomputing parts of Shor's algorithm that depend on the elliptic curve's fixed parameters, a quantum computer can be primed to finish the calculation quickly once a target public key is identified. Google estimates that the second half of the calculation, which depends on the specific public key, can be completed in about nine minutes. This timeline is critical because it coincides with 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 approximately 41% chance of succeeding before the original transaction is confirmed. Furthermore, there are about 6.9 million bitcoins, roughly one-third of the total supply, that are vulnerable to an 'at-rest' attack because their public keys have already been exposed on the blockchain. These coins can be compromised without racing against the clock, as the attacker can take as long as needed to derive the private key. The implications of this vulnerability and the ongoing development of quantum computing hardware will be explored in the next part of this series.