How Quantum Computing Threatens Bitcoin Security in Under 10 Minutes

The first installment of this series explored the fundamental principles of quantum computing. However, understanding the inner workings of a quantum computer does not necessarily reveal how it can be utilized to compromise bitcoin security. To grasp this, one must comprehend the target of the attack - namely, how bitcoin's encryption functions, why a quantum algorithm can break it, and the significance of Google's recent paper in altering the timeline of this threat. This piece commences with an examination of bitcoin's encryption, proceeding to the nine-minute window identified by Google's research, during which a quantum computer can potentially breach bitcoin's security. Bitcoin employs a system known as elliptic curve cryptography to validate ownership. Each wallet possesses two keys: a private key, which is a secret number, and a public key derived from the private key through a mathematical operation on the 'secp256k1' curve. This relationship can be thought of as a one-way map, where starting from a known point on the curve, taking a certain number of steps defined by the curve's mathematics leads to a public key. While anyone can verify the public key, determining the exact number of steps taken (the private key) is virtually impossible for classical computers. This one-way function is the cornerstone of bitcoin's security model, with the private key serving as proof of ownership and the public key being safe to share. The security relies on the difficulty of reversing the mathematical operation to find the private key from the public key, a problem known as the elliptic curve discrete logarithm problem. Classical algorithms are estimated to take longer than the age of the universe to solve this problem for a 256-bit curve. However, in 1994, mathematician Peter Shor discovered a quantum algorithm that can efficiently solve this problem. Shor's algorithm exploits the properties of quantum mechanics, such as superposition, entanglement, and interference, to find the period of a function related to the elliptic curve. This period is crucial for unraveling the discrete logarithm problem and obtaining the private key. The algorithm works by putting the input register into a superposition to represent all possible values simultaneously, applying the function to all of them at once, and then using a quantum operation called the Fourier transform to reinforce the correct answers while canceling out the wrong ones. The result is the period of the function, from which the private key can be deduced. Despite Shor's algorithm being known for over 30 years, the reason bitcoin remains secure is the requirement for a large number of stable qubits to maintain coherence throughout the calculation. Recent research by Google, in collaboration with Ethereum Foundation researcher Justin Drake and Stanford cryptographer Dan Boneh, has significantly reduced the estimated number of qubits needed, from millions to fewer than 500,000. This reduction is based on designing quantum circuits that implement Shor's algorithm against bitcoin's specific elliptic curve, using approximately 1,200 to 1,450 logical qubits and tens of millions of Toffoli gates. Given that qubits lose their quantum state constantly, hundreds of redundant qubits are needed to maintain a single reliable logical qubit, reflecting the extensive self-babysitting infrastructure within a quantum computer. The research introduced a practical attack scenario, where parts of Shor's algorithm depending on the elliptic curve's fixed parameters can be precomputed, allowing the quantum computer to sit in a primed state. Upon encountering a target public key, the machine only needs to finish the second half of the calculation, estimated to take about nine minutes. This timeline is alarming because bitcoin's average block confirmation time is 10 minutes, giving a quantum attacker a roughly 41% chance of deriving a private key and submitting a competing transaction before the original transaction confirms. The bigger concern is the 6.9 million bitcoin already exposed on the blockchain, vulnerable to an 'at-rest' attack that does not require racing against the clock. A quantum computer running Shor's algorithm can turn a bitcoin public key into the private key controlling the coins, posing a significant threat to bitcoin security.