In Part 1 of this series, we explored the fundamentals of quantum computing. Now, we dive into the target: Bitcoin's encryption, why a quantum algorithm can break it, and how Google's recent paper has shifted the timeline.
The One-Way Map of Bitcoin Security
Bitcoin relies on elliptic curve cryptography to secure ownership. Each wallet has two keys: a private key (a secret 256-digit number) and a public key derived from it via a mathematical operation on the curve "secp256k1." Think of this as a one-way map: starting from a known point G, your private key determines a number of steps, ending at your public key K. While calculating K from the private key is easy, reversing this to find the private key from K is the elliptic curve discrete logarithm problem—estimated to take classical computers longer than the age of the universe.
This one-way trapdoor is Bitcoin's security foundation. Your private key proves ownership without being revealed, and your public key is safe to share.
How Shor's Algorithm Breaks the Trapdoor
In 1994, mathematician Peter Shor discovered a quantum algorithm that efficiently solves the discrete logarithm problem. It works by finding the period of a function related to the elliptic curve, using quantum properties like superposition, entanglement, and interference. By evaluating all possible inputs simultaneously and filtering out wrong answers, Shor's algorithm can derive a private key from a public key in polynomial time, making what was once impossible feasible.
Why Bitcoin Remains Secure Today
Despite Shor's algorithm being known for over 30 years, running it requires a quantum computer with enough stable qubits. Previous estimates suggested millions of qubits, but Google's recent paper, with contributions from the Ethereum Foundation and Stanford, reduced this to fewer than 500,000. The paper details circuits using about 1,200-1,450 logical qubits and millions of Toffoli gates, with a high ratio of physical to logical qubits due to error correction needs.
The Nine-Minute Attack Window
Google's paper introduces a practical attack scenario. By precomputing parts of Shor's algorithm based on public curve parameters, a quantum computer can be primed to finish the calculation in about nine minutes once a target public key appears. With Bitcoin's average block time of 10 minutes, this gives an attacker a roughly 41% chance to steal funds from a transaction in the mempool before it confirms.
More concerning is the 6.9 million Bitcoin (about one-third of the supply) in wallets where public keys are already exposed on the blockchain. These are vulnerable to an "at-rest" attack with no time pressure. Since Taproot's privacy upgrade in November 2021, public keys for newer transactions are visible, while older addresses expose them upon spending, triggering the nine-minute race.
What this means for exposed Bitcoin, Taproot's impact, and the hardware progress will be covered in the final part of this series.
Comments
Join Our Community
Sign up to share your thoughts, engage with others, and become part of our growing community.
No comments yet
Be the first to share your thoughts and start the conversation!