The Quantum Threat to Bitcoin: How Your Cryptocurrency Could be Stolen in Under 10 Minutes

The first part of this series explored the principles of quantum computing. However, understanding how quantum computers work doesn't necessarily reveal how they can be used to steal bitcoin. To grasp this, it's essential to comprehend what quantum computers are attacking and where the vulnerabilities in bitcoin's security lie. This piece begins by examining bitcoin's encryption and proceeds to discuss the nine-minute window, as identified by Google's recent quantum computing paper, that it takes to break it. Bitcoin utilizes a system called elliptic curve cryptography to verify ownership. Each wallet has two keys: a private key, which is a secret 256-digit binary number, and a public key derived from the private key through a mathematical operation on the 'secp256k1' curve. This can be thought of as a one-way map, where starting from a known location on the curve, taking a certain number of steps defined by the curve's math leads to a public key. Anyone can verify the endpoint, but figuring out the number of steps taken is virtually impossible for classical computers. This one-way function is the foundation of bitcoin's security model, with the private key serving as proof of ownership and the public key being safe to share since 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 by mathematician Peter Shor in 1994, breaks this one-way trapdoor. It efficiently solves the discrete logarithm problem, which would take a classical computer longer than the age of the universe to solve. Shor's algorithm works by converting the problem into finding the period of a function, which is then solved using quantum properties such as 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 out of 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 specific elliptic curve, using approximately 1,200 to 1,450 logical qubits and millions of Toffoli gates. Because qubits lose their quantum state constantly, 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, waiting for a target public key to appear. Once it does, 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. The attacker has 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, as their public keys have already been exposed on the blockchain. A quantum computer running Shor's algorithm can turn these public keys into private keys, controlling the coins. This vulnerability and the implications of Taproot, a privacy upgrade on Bitcoin, will be discussed in the next piece.