How Quantum Computing Can Compromise Bitcoin Security in Under 10 Minutes

The first part of this series delved into the physics behind quantum computing, explaining how it differs from traditional computers. However, understanding the mechanics of quantum computing doesn't necessarily reveal how it can be used to steal bitcoin. To grasp this, one must comprehend the target of the attack: the encryption used by bitcoin and how a quantum algorithm can break it. This piece will examine the encryption method used by bitcoin, why a quantum algorithm poses a threat, and the significance of Google's recent paper on the timeline. Bitcoin utilizes a system called elliptic curve cryptography to verify ownership. Each wallet has two keys: a private key, which is a secret number, and a public key derived from the private key through a mathematical operation. The process can be thought of as a one-way map, where the private key is used to generate the public key, but it's virtually impossible for a classical computer to reverse the process. The security of bitcoin relies on this one-way trapdoor. A quantum algorithm, known as Shor's algorithm, can break this trapdoor. Discovered by mathematician Peter Shor in 1994, the algorithm solves the discrete logarithm problem efficiently, which would take a classical computer an impractically long time to solve. The algorithm works by converting the problem into finding the period of a function, which is a task well-suited for quantum computers. Quantum computers can represent all possible values simultaneously and apply a function to them at once, allowing for the efficient solution of the discrete logarithm problem. The recent paper by Google's Quantum AI division, in collaboration with Ethereum Foundation researcher Justin Drake and Stanford cryptographer Dan Boneh, has reduced the estimated number of qubits required to run Shor's algorithm against bitcoin's elliptic curve from millions to fewer than 500,000. The team designed two quantum circuits that implement Shor's algorithm, one using approximately 1,200 logical qubits and the other using approximately 1,450 logical qubits. The paper also introduced a practical attack scenario, where parts of the algorithm can be precomputed, allowing the quantum computer to sit in a primed state, waiting for a target public key to appear. Once the public key is visible, the machine only needs to finish the second half of the calculation, which Google estimates takes about nine minutes. This creates a window of opportunity for a quantum attacker to derive a private key and submit a competing transaction. The average block confirmation time for bitcoin is 10 minutes, giving the attacker a roughly 41% chance of succeeding. However, the bigger concern is the 6.9 million bitcoin sitting in wallets where the public key has already been exposed on the blockchain, making them vulnerable to an 'at-rest' attack. A quantum computer running Shor's algorithm can turn a bitcoin public key into the private key that controls the coins, posing a significant threat to the security of these coins.