The Quantum Threat to Bitcoin: How a Powerful Computer Can Steal Your Cryptocurrency in Under 10 Minutes

The first part of this series delved into the physics behind quantum computing, explaining how these machines differ fundamentally from classical computers. However, understanding the inner workings of a quantum computer doesn't reveal how it can be used to compromise bitcoin security. To grasp this, one must comprehend what bitcoin's encryption entails, why a quantum algorithm can break it, and the significance of Google's recent paper on the timeline of this threat. This piece begins by examining bitcoin's encryption method, known as elliptic curve cryptography, which relies on a one-way function to ensure the security of transactions. Every bitcoin wallet has a private key, a secret number, and a public key derived from the private key through a mathematical operation on a specific curve. This process is akin to a one-way map where starting from a known point, taking a certain number of steps leads to a public key, but reversing the process to find the private key is virtually impossible for classical computers. The security of bitcoin hinges 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, the discovery of Shor's algorithm by mathematician Peter Shor in 1994 introduced a quantum algorithm that can efficiently solve the discrete logarithm problem, effectively breaking the trapdoor. Shor's algorithm works by converting the problem of finding a private key into finding the period of a function, which is a task well-suited for quantum computers due to their ability to exist in multiple states simultaneously, apply functions to all possible inputs at once, and use quantum operations like the Fourier transform to find the correct answer. The algorithm utilizes superposition, entanglement, and interference, making it a powerful tool against bitcoin's encryption. Despite Shor's algorithm being known for over 30 years, the reason bitcoin remains secure is the requirement for a quantum computer with a large number of stable qubits to run the algorithm. Recent estimates by Google, 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, making the threat more tangible. Google's paper also introduced a practical attack scenario where parts of Shor's algorithm can be precomputed, allowing a quantum computer to sit in a primed state, waiting for a target public key to appear. Once a public key is visible, the machine only needs to finish the second half of the calculation, which Google estimates takes about nine minutes. This timeframe is crucial because it means a quantum attacker has roughly nine minutes to derive a private key and submit a competing transaction that redirects funds, given that bitcoin's average block confirmation time is 10 minutes. The attacker has a roughly 41% chance of succeeding before the original transaction confirms. This 'mempool attack' is alarming but requires a quantum computer that does not yet exist. A more significant concern is the approximately 6.9 million bitcoin, 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, including the impact of Taproot, a privacy upgrade on Bitcoin, and how quickly quantum hardware is advancing, will be explored in the next part of this series.