How Quantum Computing Can Be Utilized to Steal Your Bitcoin in Under 10 Minutes

This series' first installment explained the fundamental principles of quantum computing. However, understanding how quantum computers function doesn't directly reveal how they can be used to compromise bitcoin security. To grasp this, it's essential to comprehend what quantum computers are attacking, the nature of bitcoin's security, and the specific vulnerabilities involved. This piece begins with an examination of bitcoin's encryption, exploring how it works and the potential weaknesses that can be exploited by a quantum algorithm, as identified in a recent paper by Google. Bitcoin employs a system known as elliptic curve cryptography to verify ownership. Each wallet contains two keys: a private key, which is a secret number consisting of 256 binary digits, and a public key derived from the private key through a mathematical operation on the 'secp256k1' curve. The relationship between the private and public keys can be thought of as a one-way map. Starting from a known point on the curve, the private key determines the number of steps taken in a pattern defined by the curve's mathematics, leading to the public key. While anyone can verify the public key, deducing the private key from it is computationally infeasible for classical computers. This one-way function is the cornerstone of bitcoin's security model. The private key serves as proof of ownership, and the public key can be safely shared without compromising security. When sending bitcoin, the wallet uses the private key to generate a digital signature, proving knowledge of the secret number without revealing it. The advent of Shor's algorithm in 1994 introduced a quantum approach that can efficiently break this one-way trapdoor. By leveraging the principles of quantum mechanics, Shor's algorithm solves the discrete logarithm problem in polynomial time, which would be impractically long for classical computers. The algorithm works by converting the problem of finding the private key into finding the period of a function related to the elliptic curve. Quantum computers are particularly suited for this task due to their ability to represent all possible inputs simultaneously and apply the function to them in parallel, followed by a Fourier transform that isolates the correct period. From this period, the private key can be quickly deduced, compromising the security of the bitcoin. The attack utilizes the core quantum properties of superposition, entanglement, and interference to filter out incorrect answers and reinforce the correct one. Despite the theoretical capability of Shor's algorithm to break bitcoin's encryption, its practical implementation has been hindered by the requirement for a large number of stable qubits to maintain coherence throughout the calculation. Recent research by Google, in collaboration with the Ethereum Foundation and Stanford University, has significantly reduced the estimated number of qubits needed, from millions to fewer than 500,000. This advancement introduces a more feasible scenario for a quantum attack, particularly with the design of quantum circuits that can implement Shor's algorithm against bitcoin's specific elliptic curve using approximately 1,200 to 1,450 logical qubits. The introduction of a practical attack scenario changes the perspective on the quantum threat to bitcoin. Parts of Shor's algorithm that depend on the elliptic curve's fixed parameters can be precomputed, allowing the quantum computer to be in a primed state, ready to finish the calculation once a target public key is identified. Google estimates that completing the second half of the calculation takes about nine minutes, which is close to bitcoin's average block confirmation time of 10 minutes. This creates a narrow window for a quantum attacker to derive a private key and submit a competing transaction. The attack, known as the mempool attack, gives the attacker a roughly 41% chance of succeeding before the original transaction confirms. Moreover, approximately 6.9 million bitcoin, or one-third of the total supply, are in wallets where the public key has been permanently exposed on the blockchain, making them vulnerable to an 'at-rest' attack that doesn't require racing against the clock. The implications of these findings and the ongoing development of quantum hardware will be explored in the next installment of this series.