Quantum Computers and Bitcoin
Google’s news about a technological advance in quantum computing created a lot of FUD about its impact on Bitcoin. While Google’s new Willow chip is still years, if not decades, away from impacting Bitcoin, it raises a legitimate question: What will quantum computing do to Bitcoin?
Short answer: Bitcoin will adapt.
Quantum computing will not arrive tomorrow. It will take time. Research is already investigating ways to address quantum computing in Bitcoin.
Signatures
Recall that security in Bitcoin happens on two levels: within transactions and between transactions. Inside transactions, digital signatures protect the locking and unlocking of coins. They are the foremost line of defense within Bitcoin. Bitcoin’s digital signature algorithm requires a signature for any user to spend her Bitcoins. All nodes on the network can verify that the user has this signature, without knowing what that signature is. Historically, Bitcoin has used ECDSA, but since Taproot (Bitcoin’s last major upgrade in 2021), Bitcoin has used Schnorr signatures, which use hash functions and are conceptually simpler and more private than ECDSA.
Schnorr signatures are not quantum resistant, but its rollout showed a path forward for a signature update. Taproot was a soft fork, so it was a backward-compatible upgrade. Any user of Bitcoin can elect to use a pay-to-Taproot (p2tr) address rather than the older public key hash or SegWit addresses. If a quantum computer can one day break these Schnorr signatures, then 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 possible. Juan Garay, a cryptographer at Texas A&M and a colleague of mine, is currently researching the use of Lamport signatures within 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 wrinkle in this plan is for addresses that are no longer active. The largest such address belongs to Satoshi Nakamoto, whose 1 million bitcoins have not moved since they were mined in the very early years of Bitcoin. Bitcoin Core developers will have a choice to make about how to handle Satoshi’s coins. One option would be to disallow them from the blockchain, though that might cause a hard fork. Hard forks are extremely unpalatable, but there are possibly a handful of cases in Bitcoin’s history when they would be necessary. This would be one of them, along with the timestamp issue (which I will discuss at a different point).
Hash Functions
The other opportunity 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 lies in the foundation of the security of the blockchain itself. Breaking SHA-256 would mean 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. Getting access to those funds inside the Bitcoin addresses would still require the quantum computer to break the signature algorithm.
Bitcoin Core developers could then use this quantum-resistant hash function in place of SHA-256 throughout Bitcoin Core. All new blocks would be mined using this quantum-resistant hash function.
If a quantum computer could, in fact, 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 easy to detect and would disrupt the value of the bitcoins that were double-spent. Instead, a quantum miner should just 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.
Mining would cease to be a globally competitive industry and would simply be an oligopoly accruing to those with access to the quantum computer. Provided that more than one entity had access to this computer, bitcoin mining could continue as an industry, even if it is a duopoly between, say, Nvidia and Google. To avoid this scenario, the easiest fix 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 away, and with more and more economic value accruing to bitcoin, the incentives will grow year by year for researchers and developers to address it.
