How Quantum Computers Can Compromise Bitcoin Security in Under 10 Minutes

The first part of this series delved into the fundamental principles of quantum computing, distinguishing it from classical computing. However, understanding the inner workings of a quantum computer is merely the first step; the real concern lies in how it can be utilized to breach bitcoin's security. This necessitates a comprehension of the cryptographic mechanisms that underpin bitcoin and the specific weaknesses that a quantum computer can exploit. This piece commences with an examination of bitcoin's encryption methodology, known as elliptic curve cryptography, and progresses to elucidate how a quantum algorithm can potentially undermine this security, with particular reference to the recent findings outlined in Google's quantum computing paper. The cryptographic system employed by bitcoin is based on a 'one-way map' concept, where a private key, a secret number, is used to derive a public key through a mathematical operation on a specific curve, known as 'secp256k1'. This process can be envisioned as taking a certain number of steps on the curve, starting from a universally acknowledged point, with the number of steps being the private key and the endpoint being the public key. While it is relatively straightforward to calculate the public key from the private key, the reverse operation is virtually impossible for classical computers due to the nature of the elliptic curve discrete logarithm problem. It is estimated that even the most efficient classical algorithms would require more time than the universe has existed to solve this problem for a 256-bit curve. The security of bitcoin hinges on this one-way trapdoor, where the private key serves as proof of ownership, and the public key can be safely shared 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 solve the discrete logarithm problem, thereby breaking the trapdoor. Shor's algorithm operates by converting the problem into finding the period of a function related to the elliptic curve, which is a task that quantum computers are particularly suited for due to their ability to handle superposition, entanglement, and interference. By applying these quantum properties, the algorithm can evaluate a function for all possible inputs simultaneously, apply a quantum operation known as the Fourier transform to filter out incorrect answers, and then measure the result to find the period, from which the private key can be deduced. The practical application of Shor's algorithm to break bitcoin's encryption has been hindered by the requirement for a large number of stable qubits to maintain coherence throughout the calculation. A recent paper by Google's Quantum AI division, in collaboration with researchers from the Ethereum Foundation and Stanford, has significantly reduced the estimated number of qubits needed, from millions to fewer than 500,000, marking a roughly 20-fold reduction. This advancement introduces a more feasible attack scenario, where parts of Shor's algorithm can be precomputed for bitcoin's elliptic curve, allowing a quantum computer to be 'primed' and ready to complete the calculation once a target public key is identified. Google's estimates suggest that the completion of the second half of the calculation could take approximately nine minutes, which is alarmingly close to bitcoin's average block confirmation time of 10 minutes. This timeline introduces a 'mempool attack' scenario, where an attacker has a window of opportunity to derive a private key and submit a competing transaction before the original transaction is confirmed, with a calculated 41% chance of success. 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 due to their public keys being permanently exposed on the blockchain, with no time constraint for the attacker. The implications of these findings and the evolving landscape of quantum computing's threat to bitcoin security will be explored in the next piece of this series.