In The previous chapter, we were able to determine that quantum computers posed a risk to modern cryptography. We also discovered that this risk was not imminent. According to experts in the sector, it will gradually happen in several years, even several decades.
In this second chapter, we are going to study Bitcoin more specifically. Will the risks that the quantum computer poses to modern cryptography have consequences for Satoshi Nakamoto's invention?
Will quantum computers break the Bitcoin protocol?
Looking through my posts on the Bitstack blog, you may have seen that I “generally” say that bitcoin security is based on cryptographic keys. This term is no accident. Indeed, even if the vast majority of Bitcoin users use standard electronic signature systems such as ECDSA or Schnorr to secure their funds, this is by no means an obligation in terms of consensus.
In this case, it was a reward for anyone who found a collision on an old hash function called SHA1. To unlock these bitcoins and send them to an address, all you had to do was provide the locking script a valid collision for SHA1, not a signature.
What I want to make you understand with this example is that the Bitcoin protocol is indifferent to how you protect your UTXOs. It is your sole responsibility. In other words, a possible flaw in the signature algorithms (ECDSA or Schnorr) does not mean that the protocol itself has been hacked. Just because you lose your cryptocurrencies doesn't mean there won't be a block every 10 minutes.
In the end, the Bitcoin protocol itself uses very little cryptography. The only primitive used is the famous SHA256 hash function, used in building blocks and for proof of work (mining).
So we have to ask ourselves: is the SHA256 function threatened by quantum computers?
According to current knowledge, no. In general, hash functions should be little affected by the arrival of powerful quantum computers. Even though the Grover algorithm can sometimes speed up the search for collisions, it is not much more efficient than conventional SHA256 algorithms.
Don't worry, the Bitcoin protocol itself should therefore not be broken by quantum computers.
Will quantum computers break electronic signatures?
On the other hand, it is necessary to be much more careful about electronic signature methods. On Bitcoin, two of them are used: ECDSA and the Schnorr protocol. These algorithms allow the generation of a public key from a private key. On the other hand, it is now impossible to find a private key without knowing the associated public key. This is called a one-way function.
The public key is used to block bitcoins, and the private key is used to produce an electronic signature in order to spend the associated bitcoins.
The ECDSA and Schnorr algorithms belong to the same category of cryptographic methods, referred to as “elliptic curve cryptography” (ECC). Both are based on the difficulty in solving the discrete logarithm problem.
However, the Shor quantum algorithm, which I told you about in the previous chapter, can be modified to also calculate a discrete logarithm. It is capable of doing this in polynomial time, that is, the time required increases relatively little with the increase in the size of the keys.
Yes, when fairly powerful quantum computers are produced, it will theoretically be possible to calculate a Bitcoin private key from a public key in a reasonable amount of time. Concretely, this means that the simple knowledge of a public key will be sufficient to spend the associated bitcoins.
The cryptographer Pieter Wuille estimated in 2019 that 37% of the units in circulation on Bitcoin were at risk. This represents all UTXOs secured with a P2PK or P2MS script, which reveal the public keys upon receipt. He also added to his calculation all UTXOs secured with a key (address) or script hash, for which the public key or script is already known. This can happen, for example, when the same receiving address is used twice and only part of that address is spent.
Beyond this estimate, depending on the practical efficiency of Shor, it may be possible to preempt pending transactions in the mempool. Since you must reveal your public key when spending Bitcoin, a quantum computer capable of calculating the associated private key may steal your funds while they are in a transaction still awaiting confirmation.
Is this an urgent problem for Bitcoin?
No, it is not an urgent problem. It is important to understand that the quantum machines required to use the Shor algorithm are far from being available. All of this is still very hypothetical. It is not even known whether it is physically possible to create such machines. Moreover, the Shor algorithm has never been tested in real conditions. It works in theory, but we can't know if it will work in practice and if it will actually be effective.
All of this gives us time to look for solutions. And that is precisely the objective of the research carried out in the field of post-quantum cryptography.
In 2016, the National Institute of Standards and Technology (NIST) has launched a call for proposals for cryptographic algorithms that are resistant to quantum attacks. Multiple post-quantum cryptographic methods have emerged, including in the field of electronic signatures.
However, these new methods have the disadvantage of being still very young and not very tested. Compared to the Schnorr protocol and ECDSA, which have existed since 1991 and 1992 respectively, post-quantum algorithms have not yet passed the test of time. In addition, they often require keys that are considerably larger in size than those of traditional algorithms, making their use more cumbersome.
Thus, it seems premature to implement post-quantum electronic signature technology within Bitcoin today. Such a modification would increase the operational load of network nodes, while greatly increasing the risks of vulnerability, all in order to respond to a threat that, according to specialists, remains remote and hypothetical.
The two main threats to modern cryptography as a result of the advent of quantum computing are Shor's and Grover's algorithms. However, their effectiveness is still very hypothetical.
Considering the current state of knowledge, quantum computing does not seem to be a threat to SHA256, the hash function used within the Bitcoin protocol. On the other hand, ECDSA and Schnorr electronic signatures could well be affected. It is then conceivable that in the medium or long term, we will have to integrate a signature algorithm that is more robust in the face of the threat of quantum computers on Bitcoin.
To conclude, note that these risks associated with quantum computing are not limited to Bitcoin. Cryptography is absolutely everywhere right now. If 2,048-bit RSA keys and 256-bit ECDSA keys can be broken in a reasonable amount of time by a quantum computer, the entire classical banking system is at risk.
Beyond the financial field, many other much larger sectors will be affected. We can obviously think of the security of medical data, military and space communications, air traffic control or even the security of critical infrastructures such as hydroelectric dams or nuclear power plants.
If, in the future, this threat of quantum computing is confirmed, appropriate cryptography solutions will have to be found. It will then suffice to implement these algorithms on Bitcoin, in order to evolve its UTXoS security model.
