The Quantum Threat to Bitcoin: How Your Coins Can Be Stolen in Under 9 Minutes

The first part of this series explored the fundamentals of quantum computing, introducing the physics behind this powerful technology. However, understanding how quantum computers work is only half the story; the other half involves grasping what they can attack and how they can be used to compromise bitcoin's security. This piece begins by examining bitcoin's encryption method, known as elliptic curve cryptography, and then navigates through the process of how a quantum algorithm can break this encryption, highlighting the role of Google's recent quantum computing paper in altering the timeline for a potential attack. Bitcoin's security relies on a complex mathematical system called elliptic curve cryptography, which utilizes a pair of keys: a private key and a public key. The private key is a secret number, while the public key is derived from the private key through a specific mathematical operation on the elliptic curve. This operation is akin to a one-way map, where starting from a known point on the curve, taking a certain number of steps leads to the public key, but reversing this process to find the private key is virtually impossible for classical computers. The security of bitcoin hinges on this one-way function, as the private key serves as proof of ownership, and the public key can be shared without compromising security. However, the advent of quantum computing, particularly through Shor's algorithm, poses a significant threat to this security model. Shor's algorithm is a quantum algorithm that can efficiently solve the discrete logarithm problem, which is the backbone of elliptic curve cryptography. By leveraging the principles of quantum mechanics, such as superposition, entanglement, and interference, Shor's algorithm can find the period of a function related to the elliptic curve, which in turn reveals the private key. The process involves converting the problem into finding the period of a function that repeats in a cycle, which is a task well-suited for quantum computers due to their ability to evaluate functions on multiple inputs simultaneously and filter out incorrect answers. The recent paper by Google's Quantum AI division, in collaboration with researchers from the Ethereum Foundation and Stanford, has significant implications for the timeline of a potential quantum attack on bitcoin. The paper presents a more efficient implementation of Shor's algorithm against bitcoin's specific elliptic curve, requiring fewer qubits than previously estimated. This development brings the threat of a quantum attack closer to reality, as it reduces the number of qubits needed from millions to fewer than 500,000. The study also introduces a practical attack scenario, where parts of the calculation can be precomputed, allowing the quantum computer to sit in a primed state, ready to finish the calculation once a target public key appears. This scenario suggests that if a user broadcasts a transaction, a quantum attacker could derive the private key and submit a competing transaction within approximately nine minutes, which is close to the average block confirmation time of bitcoin. Furthermore, the research estimates that an attacker would have a roughly 41% chance of succeeding before the original transaction confirms. While this 'mempool attack' is alarming, it requires a quantum computer that does not yet exist. A more pressing concern is the vulnerability of the approximately 6.9 million bitcoin that have already exposed their public keys on the blockchain, making them susceptible to an 'at-rest' attack that does not require racing against the clock. In practice, this means that a significant portion of bitcoin is already at risk, and the gap between the current state of quantum hardware and the threshold required for an attack is closing rapidly.