A recent announcement from Google's Quantum AI team has sparked concern in the cryptocurrency community, stating that a future quantum computer could potentially derive a bitcoin private key from its corresponding public key in approximately nine minutes. This revelation has sent shockwaves across social media and has had a significant impact on the markets. But what does this actually mean in practical terms?
To understand the implications, it's essential to delve into the mechanics of bitcoin transactions. When a bitcoin transaction is made, the wallet uses a private key to sign the transaction, which is then linked to a public key. This public key is shared with the network and is stored in the mempool until it's included in a block by a miner, a process that typically takes around 10 minutes.
The connection between the private and public keys is based on a complex mathematical problem known as the elliptic curve discrete logarithm problem. While classical computers are unable to reverse this math in a useful timeframe, a sufficiently powerful quantum computer running the Shor's algorithm could potentially do so. The nine-minute timeline comes into play when a quantum computer is 'primed' in advance by pre-computing parts of the attack that don't depend on a specific public key. Once a public key appears in the mempool, the quantum computer would only need about nine minutes to derive the private key.
Given that bitcoin's average confirmation time is 10 minutes, this gives the attacker a roughly 41% chance of succeeding in redirecting funds before the original transaction is confirmed. This scenario can be likened to a thief creating a universal safe-cracking machine that, once built, only requires minor adjustments to crack any safe, with these adjustments taking about nine minutes. However, this 'mempool attack' is dependent on the existence of a quantum computer that does not yet exist, with estimates suggesting it would require fewer than 500,000 physical qubits, far beyond the capabilities of today's largest quantum processors. A more pressing concern is the approximately 6.9 million bitcoin that are already vulnerable due to exposed public keys.
This includes early bitcoin addresses that used pay-to-public-key formats and wallets that have reused addresses, thereby revealing the public key for all remaining funds. These coins are at risk of being cracked by a sufficiently powerful quantum computer without any time pressure. The 2021 Taproot upgrade inadvertently expanded the pool of vulnerable wallets by making public keys visible on-chain by default.
While the bitcoin network itself would continue to function, as mining uses a different algorithm that quantum computers cannot significantly speed up, the ability to derive private keys from public keys would undermine the ownership guarantees that make bitcoin valuable. The solution to this vulnerability lies in post-quantum cryptography, which involves replacing the current math with algorithms that are resistant to quantum computer attacks. Ethereum has been working towards this migration for eight years, while bitcoin has yet to initiate this process.