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. To grasp how they can be used to steal bitcoin, it's essential to comprehend what they're attacking and where the vulnerabilities lie. This piece begins by examining bitcoin's encryption and the nine-minute window, as identified by Google's recent paper, that it takes to break it. Bitcoin utilizes a system called elliptic curve cryptography to verify ownership. Each wallet has two keys: a private key, which is a secret 256-digit binary number, and a public key derived from the private key through a mathematical operation on the 'secp256k1' curve. This can be thought of as a one-way map, where starting from a known point, taking a certain number of steps leads to a public key, but reversing this process is virtually impossible for classical computers. The security of bitcoin relies on this one-way trapdoor, with the private key serving as proof of ownership and the public key being safe to share because classical computers cannot reverse the math. However, Shor's algorithm, discovered in 1994, breaks this trapdoor by solving the discrete logarithm problem efficiently, using properties of quantum mechanics. The algorithm works by finding the period of a function related to the elliptic curve, which is exactly what quantum computers are designed for. By applying the function to all possible inputs simultaneously and then using the Fourier transform, the algorithm can find the period and from it, the private key. This process utilizes superposition, entanglement, and interference, showcasing the power of quantum computing. Despite Shor's algorithm being known for over 30 years, its application has been hindered by the requirement for a quantum computer with a large number of stable qubits. Recent estimates by Google have significantly reduced the number of qubits needed, from millions to fewer than 500,000, making the threat more realistic. Google's paper also introduced a practical attack scenario, where parts of Shor's algorithm can be precomputed, leaving only the second half to be completed once a target public key appears. This second half is estimated to take about nine minutes, which is crucial because it's just below the average block confirmation time in bitcoin, giving an attacker a window of opportunity. Furthermore, the paper highlighted that approximately 6.9 million bitcoin are already vulnerable to an 'at-rest' attack because their public keys have been exposed on the blockchain. These developments signify a significant step towards making the theoretical threat of quantum computing to bitcoin a practical reality.