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

The first part of this series delved into the physics underlying quantum computing, explaining how these machines differ fundamentally from classical computers. However, understanding the mechanics of quantum computing does not necessarily reveal how it can be exploited to steal bitcoin. To grasp this, one must comprehend what quantum computers attack and how the security of bitcoin is structured, including the specific weaknesses they can exploit. This piece begins by examining bitcoin's encryption method, known as elliptic curve cryptography, and proceeds to explain how a quantum algorithm can break this encryption within a nine-minute window, as recently outlined in a paper by Google. The security of bitcoin relies on a one-way function, where a private key, where a private key is used to generate a public key, but it's virtually impossible for a classical computer to reverse this process and deduce the private key from the public key. This one-way function is based on the elliptic curve discrete logarithm problem, which is virtually unsolvable for classical computers due to its complexity, with estimates suggesting it would take longer than the age of the universe to solve for a 256-bit key. However, a quantum algorithm known as Shor's algorithm can solve this problem efficiently, leveraging the principles of superposition, entanglement, and interference to find the period of a function related to the elliptic curve. This allows a quantum computer to derive the private key from the public key, effectively breaking the encryption. The significance of Shor's algorithm is that it reduces the time required to solve the discrete logarithm problem from an impractically long period to a manageable timeframe, potentially allowing for the theft of bitcoin. Despite Shor's algorithm being known for over 30 years, its application has been hindered by the requirement for a large number of stable qubits to maintain coherence throughout the calculation. Recent research by Google, in collaboration with the Ethereum Foundation and Stanford University, has significantly reduced the estimated number of qubits needed, from millions to fewer than 500,000, making the threat more plausible. The study designed 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 practical implication of this research is the introduction of a 'nine-minute window' during which a quantum computer could potentially derive a private key and submit a competing transaction to steal bitcoin, given that the parts of the algorithm depending on the elliptic curve's fixed parameters can be precomputed, allowing the quantum computer to sit in a primed state, ready to finish the calculation once a target public key appears. This poses a significant risk, particularly for the approximately 6.9 million bitcoin that have already had their public keys exposed on the blockchain, making them vulnerable to an 'at-rest' attack that does not require racing against the clock.