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

The first part of this series explored the fundamental principles of quantum computing. However, understanding the inner workings of a quantum computer is only half the story; the other half involves grasping how it can be utilized to compromise bitcoin's security. This entails comprehending the target of the attack – the encryption mechanism that underpins bitcoin – and recognizing why a quantum algorithm can dismantle it. Furthermore, a recent paper by Google has significantly altered our understanding of the timeline associated with this threat. To begin with, it is crucial to understand how bitcoin's encryption functions. Bitcoin employs a system known as elliptic curve cryptography to verify ownership. Each wallet possesses two keys: a private key, which is a secret number comprising 256 binary digits, and a public key, which is derived from the private key through a mathematical operation on a specific curve known as 'secp256k1'. This process can be visualized as a one-way map, where starting from a known location on the curve, one can take a series of steps defined by the curve's mathematics to arrive at a public key. While anyone can verify that the public key corresponds to a specific private key, determining the exact number of steps taken to reach the public key from the starting point is virtually impossible for classical computers. This one-way function is the backbone of bitcoin's security model. The private key serves as proof of ownership, and the public key can be safely shared without compromising security since classical computers cannot reverse the mathematical operation. When a bitcoin transaction is initiated, the wallet utilizes the private key to create a digital signature, which is a mathematical proof that the sender knows the secret number without actually revealing it. However, the discovery of Shor's algorithm by mathematician Peter Shor in 1994 introduced a method by which a quantum computer can efficiently solve the discrete logarithm problem, thereby breaking the one-way function. This algorithm works by converting the problem of finding a private key into a problem of finding the period of a function related to the elliptic curve. Quantum computers are particularly adept at solving such problems due to their ability to exist in a state of superposition, allowing them to evaluate a function for all possible inputs simultaneously, and then use quantum operations like the Fourier transform to reinforce correct answers while canceling out incorrect ones. The application of Shor's algorithm in the context of bitcoin means that if a quantum computer with a sufficient number of stable qubits can be built, it could potentially derive a private key from a public key, thereby allowing an attacker to access and transfer the associated bitcoins. The security of bitcoin has not been compromised thus far because constructing such a quantum computer has been beyond current technological capabilities. A recent paper by Google's Quantum AI division, in collaboration with researchers from the Ethereum Foundation and Stanford, has provided new insights into the feasibility of this threat. By designing quantum circuits that implement Shor's algorithm against bitcoin's specific elliptic curve, the team has significantly reduced the estimated number of qubits required to launch a successful attack. The paper introduces a practical attack scenario where parts of the calculation can be precomputed, leaving the quantum computer in a primed state, ready to finalize the calculation once a target public key is identified. This development introduces a 'nine-minute window' during which an attacker could potentially derive a private key and submit a competing transaction to redirect funds, given that bitcoin's average block confirmation time is 10 minutes. While this 'mempool attack' is alarming, it requires a quantum computer that does not yet exist. A more pressing concern is the approximately 6.9 million bitcoins that are already vulnerable to an 'at-rest' attack because their public keys have been exposed on the blockchain. The implications of these findings and the evolving landscape of quantum computing as it pertains to bitcoin's security will be explored in the final piece of this series.