Quantum computing may kill Bitcoin!

A somewhat ‘advanced’ concern – mainly brought up by people who have already read about Bitcoin and at some point are starting to ‘connect some dots’ – is the concern that Bitcoin’s security could be broken by quantum computers one day.

This is an actual risk, and it would be reckless and ignorant to deny it.

However, the question is: when would such a still theoretical risk (there are no functional and stable quantum computers that could break SHA-256 encryption which is used by Bitcoin) turn into an imminently threatening one?

The risk invoked by quantum computing would be a) that Bitcoin’s SHA-256 hashes could be solved faster than by ordinary computers / ASIC mining devices, or b) to break the public-key encryption that protects users’ Bitcoin balances. So if someone secretly had a quantum computer, he could mine Bitcoin a bit faster, or he could just steal everyone else’s Bitcoins. However, that would only work as long as a) no one knew that such a computer exists and b) no one else would use one for this purpose. Otherwise, Bitcoin’s mining difficulty would be adjusted upwards, and the advantage would be gone. But how to deal with the risk of Bitcoin getting stolen?

For this problem, the Taproot update for Bitcoin may hold a solution. More on that below.

First however, let’s take a look at how Bitcoin handles transactions. When Satoshi developed Bitcoin, public keys were the actual Bitcoin addresses themselves, so a transaction to such an address is accurately called ‘pay to public key’ (p2pk). Most bitcoins Satoshi himself/themselves had mined back in the day are stored in such addresses – a quantum computer running Shor’s algorithm (which is used to find prime numbers) could then be used to derive the private key from such an address. This would allow an adversary who has a quantum computer to spend the coins that the address had. In other words, Satoshi’s stash of ~ 1 million Bitcoin serves as a super-tasty ‘honeypot’ for anyone who were able to develop a functional and stable quantum computer that’s capable to attack the Bitcoin network!

But already at the time when Satoshi was still openly mining, the improved system of ‘pay to public key hashes’ (p2pkh) was introduced, and almost all transactions used p2pkh from then on – with these, it is extremely difficult to derive private keys from the hashes that are publicly visible in the blockchain:

Probabilities & state of science: With research data available in 2019, the estimated time required to break SHA-256 encryption using Grover’s algorithm (the best bet there currently is to utilize a QC in order to break this encryption) was estimated at 18,000 years. According to numerous experts in the field (among them, Bitcoin Core developers who are specialized in the field, like Stepan Snigirev), Quantum computing won’t be a serious threat for SHA-256 encryption for at least 10 more years, even if we were to believe the most optimistic assumptions of corporations, universities etc. that are trying to capitalize on the hype around this new technology to attract funding. Skeptics on the other hand, consider the idea of someone being able to a) create a stable quantum computer that is b) capable of doing the advanced mathematical calculations necessary to break any form of encryption, either as a hoax or as not being realistically possible for at least 30-40 years.

Okay, but what if there’s an unexpected breakthrough?

Only coins in p2pk addresses and reused p2pkh addresses are vulnerable to quantum attacks.

So, only if you have ever used an ancient wallet that was using the p2pk address scheme (which is very unlikely), or if you – against all recommendations – have re-used (!) a Bitcoin address, your coins would be at risk … from the aforementioned 10-50 years onwards. Only once quantum computers have become very efficient and fast, they could calculate the private key of a broadcasted Bitcoin transaction and ‘override’ it in the short timeframe of 10+ minutes until it has been stored in the blockchain to a certain depth.

Consequently, the simplest form to protect your bitcoins right away is to move them to a newly generated address which you don’t share, and not to share your wallet’s xpub keys either. Top-notch safety against the unlikely worst-case scenario that an adversary has a fast, stable quantum computer AND (!) third parties are compromised (i.o.w., gaining access to the keys you have exchanged with them), would also involve avoiding opening Lightning Network channels and using hardware wallets that exchange keys with 3rd parties.

Taproot: light on the horizon.

Taproot keys (when used according to the recommendation in BIP-0341) will have considerably better quantum resistance than legacy outputs. They don’t provide 100% protection yet, but will buy the Bitcoin project more time than other crypto-based technologies have to implement PQC (post quantum cryptography*) techniques. The remaining challenge will then be to allow for a smooth transitioning process of the current system to a new one.

* It is pretty likely that within the next years, smart cryptography experts will find a solution for the inherent problems of quantum computing vulnerabilities of ALL cryptography-using applications (this would go way beyond just Bitcoin, as all entities using cryptography would be at risk: banks, credit cards, the military, nuclear plants, SSL-encryption on the Internet, many fields of science etc.), which will allow to transition to a new type of cryptography called ‘post-quantum cryptography’ (PQC) – one that will be inherently resistant to quantum attacks. These types of algorithms present new challenges to the usability of blockchains and are currently being investigated by cryptographers around the world. The pressure to develop such methods is rising along with the progress in quantum computing itself, so eventually we will see robust and future-proof blockchain applications, most likely with Bitcoin leading the field again considering all the research and money flowing into it.

Conclusion: The most rational estimation in our view is that we won’t see ‘risky’ levels of quantum technology until at least the 2030s – for now, we are still waiting for the quantum version of Moore’s law to take over for quantum clock speeds, gate fidelities, and qubit numbers… Until then, counter-measures for quantum computer attacks will make Bitcoin resilient against such attacks.

Further, more technical reads:
Goodbye, Bitcoin … hello Quantum by Silen Nahin (2019)
Why quantum computing will not break cryptocurrencies by Roger Huang (2020)
Quantum computers and the Bitcoin blockchain by Deloitte Research

Do you have any thoughts about these concerns, the estimated timeframes or the roadmap for PQC outlined here? Please share them in the comment section… this article is subject to regular updates whenever we hear about new aspects or related developments.