The Quantum Threat to Bitcoin: How a Quantum Computer Can Steal Your Coins 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 steal bitcoin. To grasp this, one must comprehend what a quantum computer attacks and how the security of bitcoin is constructed, including the specific vulnerabilities it exploits. This piece begins by examining bitcoin's encryption method, known as elliptic curve cryptography, which is used to verify ownership. Each wallet has a private key, a secret 256-digit binary number, and a public key derived from the private key through a mathematical operation on the 'secp256k1' curve. The 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 a public key. Anyone can confirm the endpoint, but reversing the process to find the number of steps (the private key) is virtually impossible for classical computers. This is known as the elliptic curve discrete logarithm problem, which classical algorithms would take longer than the age of the universe to solve for a 256-bit curve. The security of bitcoin relies on this one-way trapdoor; your private key proves ownership, and your public key can be shared safely because classical computers cannot reverse the math. When sending bitcoin, the wallet uses the private key to create a digital signature, proving knowledge of the secret number without revealing it. However, in 1994, mathematician Peter Shor discovered a quantum algorithm that can break this trapdoor efficiently. Shor's algorithm solves the discrete logarithm problem in polynomial time, making it feasible for a quantum computer to handle. The algorithm works by converting the problem into finding the period of a function related to the elliptic curve. Quantum computers are ideal for this task because they can represent all possible inputs simultaneously (superposition), apply the function to all inputs at once, and then use the Fourier transform to reinforce correct answers while canceling out wrong ones. This process utilizes the three key quantum properties: superposition, entanglement, and interference. Although Shor's algorithm has been known for over 30 years, its implementation has been hindered by the requirement for a quantum computer with a large number of stable qubits. Recent estimates by Google's Quantum AI division, 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. This reduction is crucial because it brings the threat of quantum attacks on bitcoin's encryption closer to reality. 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, ready to finish the calculation once a target public key appears. This could potentially give an attacker a nine-minute window to derive a private key and submit a competing transaction. For the 6.9 million bitcoin whose public keys have already been exposed on the blockchain, the situation is even more dire, as they are vulnerable to an 'at-rest' attack that does not require racing against the clock. The implications of this quantum threat and how the community is responding will be explored in the next part of this series.