Breaking ECDLP with a Quantum Computer: Resource Estimates from Google's Latest Research

Ok so, first of all, I read through this entire white paper manually. Didn't use any AI. No, I don't want a cookie for that, but I did want to make sure I really understood what was being stated here and not just gloss over it. Also, I didn't want to risk any hallucinations. So anyway, here it is. Here's what I took from the paper.

Google feels like the threat is so real that it's got to the point where it would be irresponsible for them to publish details of the attack vectors. So they decided to publish what they call a ZK proof (Zero Knowledge) which allows trustless third parties to verify the cryptographic claims without knowing the attack details. The ZK proof that they've published demonstrates two quantum circuits that they've compiled for solving the 256-bit ECDLP (Elliptic Curve Discrete Logarithmic Problem). This is actually one of the first times a ZK proof has even been used in practice. They've been discussed a lot before in the security community but only really theoretically.

What their analysis shows is that Quantum Computers can be used to execute a variety of attacks by cracking public keys, which I'll explain more below. Because of this, existing cryptocurrencies need to be upgraded to using Post Quantum Cryptography (PQC) to mitigate the possibility of these keys being broken.

PQC Blockchains actually already exist. A few are Qunatum Resistant Ledger (QRL), Mochimo, and Abelian. Algorand, XRP, and Solana are actively experimenting with PQC protocols.

PQC protocols would only fix the problem of active crypto wallets though. But dormant assets, for example BTC locked in P2PK (Pay to Public Key locking scripts - estimated to be around 1.7 million BTC) will inevitably be vulnerably to attackers with Quantum Computers. This means the BTC community will face the choice of adhering to the immutability principle of the network or throwing that idea out in order to save the locked assets. The other crazy thing about this is that some of these funds are are 'permantly' locked away due to people just losing their keys. I'm sure we've all heard the story of the guy who's been searching landfills looking for that lost hard drive. James Howells says his ex-girlfriend mistakenly threw away a hard drive that he says has 8,000 BTC on it, back in 2013. Considering the all time high value of $116,523 per bitcoin, that's about $932,184,000. Almost a billion dollars. And that's not the only bitcoin that's been lost. It's easy to imagine attackers going after that if they have the capability to, which the Google Researchers say will be a reality sooner than we think. The researchers propose that maybe there should be some type of legal framework around recovering lost digital assets similarly to how there is for recovering sunken treasure. All of these funds are suseptible to what are known as "At-Rest" attacks.

• On-Spend Attacks

  AKA "short-range" or "just-in-time" attacks. These attacks require a quantum computer that's fast enough to derive a private key from the public one within the window of time between when a transaction is initially broadcasted to the network and when it is recorded onto the blockchain.

• At-Rest Attacks

  AKA "long-range" or "long-exposure" attacks. These attacks go after public keys that have been sitting out in the open for a while, such as dormant wallets like discussed above. The attacker has days or longer to execute these types of attacks.

• On-Setup Attacks

  A back-door is created off-line using a quantum computer. Bitcoin is immune to these but some scaling solutions like Ethereum's Data Availability Sampling Mechanism, or other privacy protocols like Tornado Cash are also vulnerable.

The researchers bring up a good point that quantum computing is still in such an early stage that there still hasn't been the establishment of a 'dominant design'. The leading methods are, superconducting qubit architecture, photonics, spin qubit devices, ion trap, and neutral atom devices, but no one is sure yet which one of these will win out. Because of this, we're not really able to understand which metrics of which methods to watch in order to forcast at which point it will be possible to execute certain attacks. However, they do say that progress is moving so fast in the space that by the time any organization publishes a paper demonstrating that successful attacks on a 32-bit elliptic curve have been made, it'll most likely already be possible to also break for 256-bit, which means it's already too late to implement Post Quantum Cryptography to protect any current networks. They basically say that there probably won't even be any announcements that the technology exists when it does because of how powerful and dangerous it is. It might be the case that the public will just find out when blockchain's are hacked.

So How Is BTC Vulnerable to Being Attacked?

Essentially to be able to spend BTC that's in a wallet, all you need to know is the private key. What quantum computers could do is use the public key of a wallet to derive the private key by using Shor's algorithm to break ECDLP (the Elliptic Curve Discrete Logarthmic Problem). BTC locked away using P2PK (Pay-To-Public-Key) is vulnerable to both at-rest and on-spend attacks because the public key is recorded directly onto the blockchain. P2PKH (Pay-To-Public-Key-Hash) uses a hash of the public key, so it's only vulnerable to on-spend attacks since it's only visible during the window of time while a transaction is taking place (around 10 mins for the BTC network).

BTC is more susceptible to on-spend attacks because of the average time it takes to complete a transaction, about 10 mins. Other cryptocurrencies that optimized for faster transaction times are less vulnerable to these types of attacks. For example Litecoin (2.5 mins), Zcash (75 secs), and Dogecoin (1 min). One other factor in vulnerability is re-using public keys. Even if a locking script like P2PKH is used and the public key is re-used from a previous transaction, it can be susceptible to an at-rest attack if the attacker gets it from one of those previous transactions on the chain. Stopping the re-use of public keys could greatly mitigate the attack surface of quantum adversaries, but re-using them has kinda become necessary for BTC to be practical for it's business use cases. For that reason, the researchers recommend migrating to PQC as the only real solution.

Is it Feasible to Execute Quantum Attacks on the Proof of Work Algorithm?

In short, not for the foreseeable future. This is due to 2 reasons. First, the consensus of the most likely method to use quantum computers for mining BTC would be Grover's algorithm and it just doesn't get much benefit from parralellization. Second, quantum computing still needs a lot of error correction and the speed gained from Grover's algorithm would be kind of 'eaten up' by the overhead of error correction. So it could be used, but it would actually be about 10 orders of magnitude slower than something like an S19 ASIC miner today. However, quantum computers still pose a threat to proof of work because the other types of attacks mentioned above could cause the price of BTC to drop so low that mining could become unprofitable, which would destabilize the network and make transaction times longer. This would increase the attack surface for on-spend attacks.

How About Ethereum? Is it Safe?

Ethereum is actually less susceptible to on-spend attacks than Bitcoin because the transaction window is a lot shorter, averaging at around 1 minute. But there are 3 main features that differentiate it from Bitcoin which actually make it more susceptible to at-rest attacks. Those are, it's Account Model, Smart Contracts, and Validators. Because a public key is tied to an account, the keys can't be rotated. Because Smart Contracts have their own keys which are publicly viewable and have elevated priveleges over a large number of accounts, they're extremely vulnerable to at-rest attacks. This is referred to as the Admin Vulnerability. In addition to the Admin Vulnerability, there's also the Code Vulnerability, which is due to the fact that Ethereum Smart Contracts have pre-compiled cryptographic algorithms in them for the applications built on them to use. The problem is, these algorithms are not PQC. Because of the way the Ethereum network validates transactions, Proof-of-Stake vs Bitcoin's Proof-of-Work, it uses Validator nodes that need to have their public keys exposed in order to validate. This also increases it's attack surface for at-rest attacks. Cracking these keys would allow attackers to wreak all kinds of havoc on the network because they could create fraudulent validations. However because of the number of validator nodes, this would still be fairly expensive for the attackers to carry out. Ethereum is also vulnerable to what are called 'on-setup' attacks because of the relationship of the L2 and L1 networks.

The researchers' main conclusion of Ethereum's vulnerability is that it is a lot higher than Bitcoin's, but the advantage it has is it's leadership and community. Because its slightly less decentralized than Bitcoin, it should have an easier time adopting the necessary changes to implement Post Quantum Cryptography. Bitcoin can still do it, but there could be more disagreements within the community on how things should be handled leading to slower action or forked networks.

To sum up their findings, it is inevitable that cryptocurrencies will be soon vulnerable to quantume computers. The only way forward is really to implement Post Quantum Cryptography for new transactions and to have governments step in to create a framework on how to handle legacy funds that would be recovered by bad actors. But their main message is that all cryptocurrencies should be working on getting PQC implemented YESTERDAY, if they want to survive.

Here's a link to the White Paper if you'd like to also read through it yourself! Securing Elliptic Curve Cryptocurrencies against Quantum Vulnerabilities: Resource Estimates and Mitigations