Quantum Securing Bitcoin Really Isn’t That Hard

With the recent news from Chinese scientists claiming to have made material strides towards breaking certain classes of encryption, and Google’s announcement of further progress on quantum chips, I consider it timely to reiterate some principles of Bitcoin and how they relate to the looming threat of quantum computers.

Let’s begin by making sure that we are clear about the fact that any practical quantum threat to Bitcoin is still far away, but still, this is a topic I think a lot of people will find interesting. I will use this piece to lay out, in as simple terms as possible, how Bitcoin uses cryptography, and to what extent quantum computers threaten its components.

Then I will explain, again as simply as possible, what countermeasures can be taken, and what process would be necessary to take them. If you read no further, the summary is that the threat as it is currently understood can be mitigated quite easily, and all that would be required is a soft fork.

I will spend the rest of this paper explaining why that is in as brief and simple terms as I believe is possible given the underlying complexity of the matter.

Bitcoin Makes Use of Two Classes of Cryptographic Tools

Most people know that Bitcoin uses cryptography for security, but very few people know much about how. That is perhaps not too surprising given that cryptography seems impenetrably difficult for most people. In reality though, the principles of cryptography are quite simple: It largely relies on certain functions that can easily be computed in one direction, but not the other. We call these trapdoor functions.

Bitcoin uses two different types of trapdoor functions, and it uses them for quite different tasks. First it uses the fairly well known class of cryptographic key pairs, consisting of a private key and a public key. Secondly, it uses the less well known class of hash functions.

Let’s briefly go over what they do.

Cryptographic Key Pairs are Used to Send and Receive Transactions

At the crux of Bitcoin’s security model lies its utilisation of cryptographic key pairs for transactions. In short, transactions can be thought of as being sent to a public key, and sent from a private key. The more complete way of thinking about it is that the unlocking script of an Unspent Transaction Output (UTXO) is locked to a public key, and unlocked by a digital signature produced by its corresponding private key.

There are currently two signature algorithms used in Bitcoin, the Elliptic Curve Digital Signature Algorithm (ECDSA) and Schnorr Signatures, and they both use the same public key structure (elliptic curve multiplication on the secp256k1 curve). This method is vulnerable to quantum computers using Shor’s algorithm, putting coins sent to both these address types at potential risk.

Hash Functions are Used for Truncation and Validation, Settlement, and Address Obfuscation

The other main class of cryptographic tools — the hash functions — have a few different roles. But it is very important to note here that the hash functions are not used to authorise transactions. There are two hash functions used in Bitcoin SHA-256 and RIPEMD-160, with SHA-256 being used for several different things.

The three main roles of the hash functions are truncation and validation, settlement, and address obfuscation. I will skip over the truncation and validation roles as they are irrelevant for this discussion.

Settlement

When used for settlement, SHA-256 is used by a network of miners to arrive at a decentralised time-ordering of transactions. The regularity of transaction settlement is regulated by the difficulty adjustment such that no matter how many miners participate in the settlement process, new tranches of transactions (blocks) are entered on average every 10 minutes. 

Since it is known that SHA-256 cannot be reverse-calculated, only guessed, the network can impose a certain difficulty on finding new blocks, such that the process cannot happen faster than intended. In this way, Bitcoin’s emission curve is fixed in time and cannot be sped up or slowed down. 

This process also incurs a large cost on the participants, and the magnitude of this cost acts as a deterrent for malicious actors seeking to reverse transactions they’ve made, or to prevent others from transacting. Here it is important to note that no miner, no matter if they controlled 100% of the mining network, could redirect other people’s transactions after they’ve taken place — only their own — because they can not produce digital signatures from other people’s public keys.

Address Obfuscation

Another key role of hash functions is in obfuscating Bitcoin addresses. Sending bitcoin effectively means sending them to a public key. However, it is also possible to send bitcoin to the hash of a public key. This type of transaction is called p2pkh or, Pay to Public Key Hash. We refer to p2pkh as a bitcoin address type. Another address type is p2pk, or Pay to Public Key. Yet another is p2sh, or Pay to Script Hash.

The key thing to note here, is that when bitcoin is sent to the hash of a public key, the public key is not revealed to the network, only an obfuscated form of a public key is visible throughout the network. That means that the operator of a malicious quantum computer trying to calculate private keys from public keys has nothing to work with and can therefore do nothing.

Quantum Computers Reduces the Security of Cryptography, It Doesn’t Necessarily Eliminate It

When analysing the vulnerability of Bitcoin to quantum computers we have to be precise about a few things: First, what exactly quantum computers can do, and second, what the exact effect on that would be for Bitcoin. So let’s address both of those questions.

Cryptography generally relies on the inability of computers to calculate certain things within a practical amount of time. For example, using regular computers, finding a hash collision in SHA-256 is so difficult that even if you had a computer the size of the Earth using all the energy of our sun it would take trillions of times longer than the age of the Universe. 

And the time it takes to ‘reverse’ the trapdoor functions relates to the key sizes or digest lengths. Larger keys require longer times to reverse, so for example, a 256-bit key, while only twice as long as a 128-bit key, would take 2^128, or ~10^39 times longer to reverse [1].

Meanwhile, larger computers will lower the time to reverse them only in proportion to their size, such that a computer that’s twice as fast, only reduces the reversal time by half.

What quantum computers do is that they reduce the time it takes to reverse these functions based on the size of the computer you’re using. That means that a quantum computer that has twice as many qubits as another, can reverse certain trapdoor functions for example four times as fast. This means that the fundamental assumptions of the types of cryptography that are vulnerable to quantum computers are broken, it doesn’t mean that they immediately stop working.

Let me use SHA-256 as an example. According to The University of Illinois, a quantum computer using Grover’s algorithm would reduce the security of SHA-256 from 256-bit to 128-bit. In other words, whereas a normal computer looking to find the input to SHA-256 from an output would have to try 2^256 times [2] to guarantee finding an output, a quantum computer would “only” need 2^128 tries.

To put that in perspective, even if you had a quantum computer that was one trillion times faster than the fastest current quantum computer, it would still take a million years (and an absurd amount of energy) to find a collision. That’s not practical, but it sure is a lot faster than the 367 billion trillion trillion trillion trillion years it would take a regular computer.

In other words, addresses hidden behind SHA-256 hashes are likely to remain secure even if practical mega-scale quantum computers become viable. And in terms of mining, all that a quantum computer would amount to is a faster miner, and given its cost and complexity (assuming it is even possible to make one of interesting scale) it is not obvious that it would be a cost-effective one. 

Bitcoin’s Vulnerabilities are Limited, and Practically Exploiting them Requires Major Technological Advancement

Now that we have some sense for the numbers we’re dealing with and the scales still required to reverse for example SHA-256, let’s think a little more closely about what the quantum vulnerabilities are in Bitcoin.

Let’s start with ECDSA-secured addresses which are theoretically vulnerable to quantum computers using Shor’s algorithm [3]. Remember, it is possible to send bitcoin directly to public keys, so all coins sitting in addresses that reveal the public key would be vulnerable to theft if someone could calculate the private key from the public key. For reference, we are talking about approximately 1.9m bitcoin, or 9% of supply.

Transactions in Schnorr addresses — such as Taproot UTXOs — are also vulnerable since their public keys are also visible, but that address format holds only about 0.1% of coins so we’ll leave that out of this analysis.

According to researchers, in order to reverse a public key within one day, an attacker would require a quantum computer with fault tolerance and error limitation performance that has currently not been achieved, and 13 million physical qubits — about 100,000 times more than the largest current quantum computer [4]. In order to break it within an hour [5], it would have to be 3 million times better than current quantum computers.

Estimating the current annual growth rate in physical qubits is not straightforward. Partly because there are a lot of different types of qubits, but also because we don’t have a lot of data points. According to data compiled by Quantum Zeitgeist, growth in functional physical cubits is similar to that of regular computer chips as described by Moore’s Law — with numbers doubling every two years or so. At this rate, it would take more than 15 years to get to 13 million qubits.

And that assumes that it is even possible to scale qubits to that scale while simultaneously achieving error rates that are lower than have been achieved — and we haven’t even discussed cost.

Fixing the Primary Vulnerability Only Requires a New Address Format via Soft Fork

But if we assume that at some point this quantum supremacy will happen, there are still many mitigations that can be taken to secure coins. These range from simple trust-based ones that require no changes to Bitcoin, to proper replacement of cryptographic tooling.  

The simplest mitigation is to only use address formats that are hidden behind hashes, and then send outbound transactions directly to miners or pools, with the assumption that they won’t be running these types of quantum computers and trying to steal from you (for which they’d of course also be criminally liable). Another method is to send transactions that are small enough that running an ultra-advanced (and probably huge and expensive) quantum computer for an hour would cost more than the value of the transaction. 

But those types of mitigation is unlikely to satisfy the famously paranoid Bitcoin community, and so a new address type using quantum resistant cryptography will likely be necessary. In fact, a draft Bitcoin Improvement Proposal (BIP) for a new quantum secure address format has already been proposed and is being discussed right now. Introduction of a new address format, while obviously not a light change, would only require a soft fork, making it unlikely to stir up much controversy. 

The main issues reducing appetite for urgent action at this point is that most or all of the proposed quantum secure alternatives have signature sizes that are much larger than the current Bitcoin signatures. This is slightly problematic since Bitcoin has a hard limit on its block size, so making transactions require more data effectively reduces the number of transactions that can fit in a block. This too can be solved by increasing the witness part of Bitcoin blocks — which are technically not subject to the blocksize — but this discussion would likely warrant its own separate article to properly cover.

Once implemented, coins that are currently sitting in vulnerable addresses would have to be moved to new secure addresses. The onus of this would be on the owner of each address. Interestingly, the majority of the most vulnerable coins are those that are widely theorised to belong to Satoshi Nakamoto. This means that either those coins will have to move, proving that Satoshi is still alive, or they will effectively act as a honey pot reward for builders of quantum computers.

In Summary: Quantum Computers Present a Threat, But neither a Current nor Particularly Problematic One

Problematic quantum computers, if we assume they will be possible to create, are still quite some time away meaning that necessary changes have plenty of time to be discussed and implemented. But even if they do at some point arrive, Bitcoin can be relatively easily modified to mitigate the risk they present.

The primary risk to Bitcoin is coin theft from addresses with visible public keys. These addresses make up a little less than 10% of all coins. In order to remain secure after the advent of large enough practical quantum computers, coins in such addresses would have to be moved to a new quantum-secure address format.

Then, given a large and capable enough quantum computer, all addresses using ECDSA or Schnorr — even those obfuscated by a hash — would be vulnerable since their keys could conceivably be reversed in the small time during which their signed transactions sit waiting in the mempool. At that point, all coins would have to move to quantum secure addresses.

A quantum secure address format can be added to Bitcoin via soft fork meaning that it can be implemented voluntarily by those who want it, and ignored by those who don’t. That means the change would be relatively easy to implement, and unlikely to be seen as problematic enough to delay deployment.

[1] That’s 340,282,366,920,938,463,463,374,607,431,768,211,456 times.
[2] That’s ~10^78, or 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936 times.
[3] Which to recap, is because the elliptic curve multiplication they use on the secp256k1 curve is vulnerable.
[4] The estimation of ‘physical cubits’ is a bit of a tricky thing since there are many different types of cubits, and they do not have the same performance or characteristics. Given the knowledge level of our audience, we have therefore opted for readability, simplification and generalisability over pure accuracy in this paper.
[5] This is considered a key vulnerability timeframe because even public keys hidden behind SHA-256 are visible to the network for a short period of time when they are in the process of being spent but are still waiting to be added to a block by a miner.