Quantum Computers and Bitcoin

Google's recent announcement regarding an advancement in quantum computing has sparked concerns within the cryptocurrency community about its potential impact on Bitcoin. While Google's Willow chip is still years, if not decades, away from posing a threat to Bitcoin, it raises a valid question: how will quantum computing affect Bitcoin?

The short answer is that Bitcoin will adapt.

Quantum computing will not arrive overnight; it will take time. Research is already underway to explore methods of addressing quantum computing in Bitcoin.

Signatures

It's important to note that security in Bitcoin operates on two levels: within transactions and between transactions. Within transactions, digital signatures safeguard the locking and unlocking of coins, serving as the first line of defense. Bitcoin's digital signature algorithm mandates a signature for any user to spend their Bitcoins. All nodes on the network can verify that the user has this signature, without knowing what that signature is.

Historically, Bitcoin has utilized ECDSA, but following Taproot (Bitcoin's last major upgrade in 2021), Bitcoin now employs Schnorr signatures, which leverage hash functions and are conceptually simpler and more private than ECDSA.

While Schnorr signatures are not quantum resistant, their rollout demonstrated a path forward for updating signatures. Taproot was implemented as a soft fork, essentially a backward-compatible upgrade. Any Bitcoin user can choose to use a pay-to-Taproot (p2tr) address instead of the older public key hash or SegWit addresses.

If a quantum computer were to eventually succeed in breaking these Schnorr signatures, I believe the Core developers would adopt a quantum-resistant signature scheme and deploy it as a soft fork within Bitcoin Core.

Such quantum-resistant schemes are already feasible. Juan Garay, a cryptographer at Texas A&M and a colleague of mine, is currently exploring the integration of Lamport signatures into Bitcoin. Once this new quantum-resistant signature becomes part of a soft fork, all existing Bitcoin users would simply transfer their bitcoins from their existing address into a new quantum-proof address.

The only potential complication in this plan arises with addresses that are no longer active. The largest such address belongs to Satoshi Nakamoto, whose 1 million bitcoins have remained unmoved since they were mined in the early years of Bitcoin.

Bitcoin Core developers would face a choice in how to handle Satoshi's coins. One option would be to disallow them from the blockchain, although this might trigger a hard fork. Hard forks are highly undesirable, but there are perhaps a handful of instances in Bitcoin's history when they would be necessary. This would be one of them, along with the timestamp issue (which I will discuss separately).

Hash Functions

Another possibility for a quantum computer would be to break SHA-256, the hash algorithm used extensively in Bitcoin. Not only is this used within some Bitcoin addresses, like pay-to-public-key hash (p2pkh), and even within Schnorr signatures, but it also forms the foundation of the blockchain's security.

Breaking SHA-256 would entail finding hash collisions, and in the best case, making the hash function invertible. The quantum computer could then perform a 51% attack on the blockchain, which, in the best case, would allow the double-spending of coins. However, to obtain access to those funds within the Bitcoin addresses, the quantum computer would still need to break the signature algorithm.

Bitcoin Core developers could then integrate this quantum-resistant hash function in place of SHA-256 throughout Bitcoin Core. Subsequently, all new blocks would be mined using this quantum-resistant hash function.

If a quantum computer could indeed break SHA-256, the highest and best use of this technology would be to mine bitcoin, not to perform a double-spend attack. A double-spend attack would be easily detectable and would ultimately diminish the value of the bitcoins that were double-spent. Instead, a quantum miner would simply use this new quantum computer to mine all remaining bitcoin, which it would be able to do if it could tailor the transactions and blocks in a way that would generate a sufficiently small number to win the mining lottery every 10 minutes. This would be possible if the quantum computer could invert the SHA-256 hash operation.

In this scenario, mining would cease to be a globally competitive industry and would instead become an oligopoly, limited to those entities with access to the quantum computer. Assuming that more than one entity had access to this computer, bitcoin mining could continue as an industry, even if it were a duopoly between, say, Nvidia and Google.

To avert this scenario, the simplest solution would be to install a quantum-resistant hash function in place of SHA-256. This is not out of the question, since Schnorr signatures themselves utilize hash functions. Therefore, a quantum-resistant signature scheme would need to be immune to hash functions.

This problem is still a long way off, and with more and more economic value being tied to bitcoin, the