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 principles of quantum computing, explaining how it differs fundamentally from classical computing. However, understanding the inner workings of a quantum computer does not directly reveal how it can be utilized to compromise bitcoin security. To grasp this, one must comprehend what aspect of bitcoin's security is being targeted and where the vulnerability lies. This piece begins by examining bitcoin's encryption method and progresses to discuss the nine-minute window, as identified by Google's recent quantum computing research, within which an attack can occur. Bitcoin employs elliptic curve cryptography to verify ownership, utilizing a system where each wallet has two keys: a private key and a public key. The public key is derived from the private key through a mathematical operation on a specific curve known as 'secp256k1'. This process 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 the public key. While moving forward in this map is straightforward, reversing the process to find the private key from the public key is virtually impossible for classical computers due to the elliptic curve discrete logarithm problem. It's estimated that solving this problem for a 256-bit curve with the best-known classical algorithms would take longer than the age of the universe. This one-way function is the cornerstone of bitcoin's security model, allowing the private key to prove ownership without being revealed. When sending bitcoin, the wallet uses the private key to create a digital signature, proving knowledge of the secret number without disclosing it. However, Peter Shor's quantum algorithm, discovered in 1994, can efficiently solve the discrete logarithm problem, thus breaking the security model. This algorithm works by converting the problem into finding the period of a function related to the elliptic curve, which is a task well-suited for quantum computers due to their ability to exist in multiple states simultaneously and perform operations on all possible inputs at once. The algorithm uses superposition to evaluate the function on every possible input, entanglement to correlate inputs and outputs, and interference to filter out incorrect answers, leaving only the correct period. From this period, the private key can be easily derived, compromising the security of the bitcoin. Although Shor's algorithm has been known for over 30 years, its application has been hindered by the requirement for a large number of stable qubits to maintain coherence throughout the calculation. Recent research by Google's Quantum AI division, in collaboration with other experts, has significantly reduced the estimated number of qubits needed, from millions to fewer than 500,000, and introduced a practical attack scenario. The study designed quantum circuits implementing Shor's algorithm against bitcoin's elliptic curve, requiring approximately 1,200 to 1,450 logical qubits and millions of Toffoli gates. Given the constant loss of quantum state by qubits, hundreds of redundant qubits are needed to maintain a single reliable logical qubit, explaining the high ratio of physical to logical qubits. The research also introduced the concept of precomputing parts of the algorithm that depend on the elliptic curve's fixed parameters, allowing the quantum computer to be in a primed state, ready to finish the calculation once a target public key appears. This reduces the time needed to derive a private key to about nine minutes, which is close to bitcoin's average block confirmation time. An attacker thus has a window of opportunity to derive a private key and submit a competing transaction. For the 6.9 million bitcoin with public keys already exposed on the blockchain, the attack can be conducted without time pressure. The implications of this vulnerability and the pace at which quantum computing is advancing will be discussed in the next part of this series.