How Quantum Computers Pose a Threat to Bitcoin Security in Under 10 Minutes

Quantum computers operate on a fundamentally different principle than classical computers, leveraging the unique properties of quantum mechanics to perform calculations that are exponentially faster and more powerful. The first part of this series explored the physics behind quantum computing, but the critical question remains: how can these machines be utilized to compromise bitcoin's security? The answer lies in understanding the target - the encryption mechanism that safeguards bitcoin transactions. Bitcoin employs elliptic curve cryptography, a system that utilizes 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 on a specific curve known as secp256k1. This relationship between the private and public keys is akin to a one-way map, where it is straightforward to generate the public key from the private key but virtually impossible to reverse the process using classical computers. The security model of bitcoin is based on this one-way function, with the private key serving as proof of ownership and the public key being safe to share without compromising the private key. However, the discovery of Shor's algorithm by mathematician Peter Shor in 1994 introduced a quantum approach that can efficiently break this one-way trapdoor. Shor's algorithm solves the discrete logarithm problem, which is the backbone of bitcoin's encryption, in polynomial time, making it feasible for a sufficiently powerful quantum computer to derive a private key from a public key. The algorithm operates by converting the problem into finding the period of a function related to the elliptic curve, a task that quantum computers are particularly well-suited for due to their ability to exist in a superposition of states and perform calculations on all possible inputs simultaneously. The application of the Fourier transform then allows the correct period to be identified, from which the private key can be easily deduced. The practical implementation of Shor's algorithm against bitcoin's specific elliptic curve has been explored in a paper by Google's Quantum AI division, which significantly reduced the estimated number of qubits required to perform the calculation, from millions to fewer than 500,000. This reduction, coupled with the design of quantum circuits that can implement Shor's algorithm, brings the threat of a quantum attack on bitcoin's security closer to reality. The paper also introduced a practical attack scenario where parts of the calculation can be precomputed, leaving only the final step to be performed once a target public key is identified. This could potentially be completed within nine minutes, a timeframe that is comparable to bitcoin's average block confirmation time, thereby introducing a 'mempool attack' vector. Furthermore, the paper highlights that approximately 6.9 million bitcoin, or roughly one-third of the total supply, are vulnerable to an 'at-rest' attack because their public keys have already been exposed on the blockchain. These findings underscore the evolving landscape of quantum computing and its potential impact on the security of cryptocurrencies like bitcoin, emphasizing the need for vigilance and the exploration of quantum-resistant cryptographic solutions.