The Quantum Threat to Bitcoin: How a Quantum Computer Can Steal Your Cryptocurrency 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 utilized to steal bitcoin. To grasp this, one must comprehend what a quantum computer is attacking, the security mechanisms of bitcoin, and where the vulnerabilities lie. This piece begins by examining bitcoin's encryption, leading up to the nine-minute window identified by Google's recent quantum computing paper, in which a quantum computer can potentially break bitcoin's encryption. Bitcoin employs elliptic curve cryptography to verify ownership. Each wallet has a private key, a secret number, and a public key derived from the private key through a mathematical operation on the 'secp256k1' curve. This process can be thought of as a one-way map, where starting from a known location, taking a certain number of steps defined by the curve's math leads to a public key. Anyone can verify the public key, but no classical computer can reverse the process to find the private key. The security of bitcoin relies on this one-way trapdoor. Your private key proves ownership, and your public key is safe to share 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, Shor's algorithm, discovered in 1994, breaks this trapdoor using quantum computing. It solves the discrete logarithm problem efficiently, which would take a classical computer longer than the universe's age to solve. The algorithm works by converting the problem into finding the period of a function, which quantum computers can solve using superposition, entanglement, and interference. Despite Shor's algorithm being known for over 30 years, running it requires a quantum computer with a large number of stable qubits, which has been beyond reach. Google's recent paper reduced the estimated number of qubits needed from millions to fewer than 500,000, a 20-fold reduction. The team designed quantum circuits that implement Shor's algorithm against bitcoin's elliptic curve, using approximately 1,200 to 1,450 logical qubits. Because qubits lose their quantum state, hundreds of redundant qubits are needed to maintain a single reliable logical qubit. Google's paper introduced a practical attack scenario where parts of Shor's algorithm can be precomputed, leaving the quantum computer in a primed state. Once a target public key appears, the machine only needs to finish the second half of the calculation, which Google estimates takes about nine minutes. This creates a 'mempool attack' scenario where an attacker has roughly nine minutes to derive a private key and submit a competing transaction, with a 41% chance of succeeding before the original transaction confirms. Moreover, 6.9 million bitcoin, or roughly one-third of the total supply, are vulnerable to an 'at-rest' attack since their public keys have been exposed on the blockchain. A quantum computer running Shor's algorithm can turn these public keys into private keys, controlling the coins. The implications of this and how the hardware gap is closing will be discussed in the next piece.