As a Bitcoin enthusiast, people around me frequently throw certain claims at me as a challenge. The classic, of course, is that it’s a scam, a pyramid scheme — usually accompanied by laughter. This claim reveals that they either don’t know what a pyramid scheme is, or they don’t understand Bitcoin (and in some cases, neither). Another very common claim is that “governments will shut it down” because it’s not in their interest. This one isn’t entirely absurd, since it’s true that those in power don’t want to lose part of that power, and so they will try to stop it. However, what the claim reveals is that they haven’t stopped to think about how. The more you think about it, the more difficulties you find.
And among the more technically-minded, there’s the claim that “when quantum computers arrive, it will be possible to break Bitcoin” and therefore it will be worthless.
This is the claim I’m going to analyse in this article.
To analyse whether this is true or not — or more precisely, to what extent it is — let’s first look at how a Bitcoin transaction works. A transaction is a set of bytes of information indicating that an amount of bitcoin moves from one address to another, or more generally, from m source addresses to n destination addresses, such that the total bitcoin at the m source addresses is greater than or equal to the total bitcoin at the n destination addresses.
How is it ensured that only the owner of the bitcoin at an address can move it? This is achieved through public-key cryptography — specifically, in Bitcoin, the system used is ECDSA (Elliptic Curve Digital Signature Algorithm). In a public-key system, each user has a private key known only to them, kpriv, and a public key kpub which, as the name suggests, is public. To move bitcoin from one address to another, it is necessary to “sign” the message (the transaction). And signing it requires the private key — therefore, only the holder of that key can move (spend) the bitcoin. Of course the signature does not reveal the private key, and verifying the signature requires only the public key. (For a detailed explanation, see (I).)
Given the private key, deriving the public key is trivial, but the reverse is not possible. “Not possible”, in this context, means that no algorithm is known that can compute the private key from the public key other than brute force — that is, trying millions of random private keys and checking whether any corresponds to the public key we have. Since there are on the order of 2 to the power of 256 private keys (approximately one billion times the number of atoms in the Milky Way), no computer — nor all the computers in the world working together — could compute it in less time than the age of the universe (approximately 13.8 billion years).
So far so good — but this is for conventional computers, the ones we all know, the ones that work with bits, i.e. with 0s and 1s. But what about quantum computers? They have existed for years, and recently Google announced that it had achieved “quantum supremacy”. Since we now have quantum computers that will make everything much faster, everything stated above is invalid and Bitcoin will be destroyed. Right?
Not so fast!
To begin with, quantum computers are not going to make all tasks faster — they are not simply “faster computers”. They are “different” computers that will perform many tasks more slowly than conventional ones, but that can solve in polynomial time certain problems that conventional computers can only solve in exponential time. These quantum computers do not work with bits but with qubits.
What are qubits? Qubits are units of information more complex than bits — difficult to understand for anyone unfamiliar with quantum mechanics. Since this article does not assume such knowledge on the part of the reader, I will make some simplifications, possibly at the cost of precision or accuracy. The goal of the article is to provide an accessible idea of how real and how imminent the quantum computing threat to Bitcoin actually is — accessible to most people, not only those who know quantum mechanics.
With that said, a qubit is a unit of information that can exist in infinitely many states, unlike a bit which can only exist in 2 states. Like a bit, it has two basic states: |0⟩ and |1⟩. But unlike a bit, it can exist in any state ⍺|0⟩ + β|1⟩, where ⍺ and β are complex numbers whose squares sum to 1. There’s more. If a bit is in state 1 and we “measure” (read) it, we get 1; if it’s in state 0 we get 0 (as anyone would expect). In quantum mechanics, things don’t work that way. In quantum mechanics measurement alters the state. And this isn’t due to using a poor measuring instrument or insufficient care — it is due to the very essence of the quantum phenomenon. So a qubit can exist in infinitely many states, but when we measure or read its value, we get |0⟩ or |1⟩. We cannot read the value ⍺|0⟩ + β|1⟩.
Strange, yes — but that’s nature. At first glance, qubits don’t seem to offer much. They can have an enormous number of states but we can only read two, and moreover we don’t know which one we’ll get because it’s random. What could they be good for? It is random, yes, but not equally probable. It turns out that ⍺ and β are probability amplitudes — in other words, the square of ⍺ is the probability that measuring the qubit yields |0⟩, and the square of β is the probability that it yields |1⟩.
As we can see, qubits are extremely complex information elements. Without going deeper, we can already get an idea that a quantum computer will be radically different from a conventional one, since it must handle such strange information elements. In fact, logical operations, algorithms — everything is different in quantum computing. The usual logic gates — AND, OR, NOT, NAND, XOR — don’t exist for qubits. Instead there exist many other, vastly more numerous (infinitely many, in fact) possible quantum logic gates. Algorithms are also completely different. They must be developed from scratch and have nothing in common with traditional ones — they are algorithms built from these new quantum gates.
If you know nothing about quantum computing, you might think this is very strange (it is) and that it will probably take a very long time to develop algorithms capable of doing anything interesting with these exotic quantum gates — let alone breaking cryptography. Well, that is not the case for public-key cryptography.
In the matter at hand, the threat that Bitcoin will be destroyed by quantum computers arises from the fact that an algorithm already exists for quantum computers capable of “breaking” the discrete logarithm of ECDSA, upon which Bitcoin’s security is based. And it has existed since 1995 — 13 years before Bitcoin was invented! Being able to compute the discrete logarithm of ECDSA means that given the public key, the private key can be derived, which would bring the entire system down. This is the famous Shor’s algorithm. (II)
So quantum computers exist, and the algorithm capable of computing the discrete logarithm of ECDSA that Bitcoin relies on exists too. That’s it then, right?
Again, not so fast. What does Google’s quantum supremacy announcement actually mean? What has it achieved? It solved in a matter of seconds a problem that would take a supercomputer thousands of years. It achieved this with a quantum computer of 54 qubits. According to the latest research (III), a quantum computer with more than 2,300 qubits (and more than 128 billion Toffoli quantum gates) would be needed to break 256-bit ECDSA. And building quantum computers with more and more qubits is far from straightforward. Let’s put this in historical perspective:
The idea of quantum computing (IV) emerged in 1981 when Paul Benioff envisioned a computer operating on some of the principles of quantum mechanics. Also in 1981, Richard P. Feynman gave a talk at MIT entitled “Simulating Physics with Computers” (V), in which, among other ideas, he argued that since the essence of nature is quantum, we will need quantum computers to simulate it. Since 1981, quantum computing has been advancing and developing:
- In 1985, David Deutsch described the first universal quantum computer.
- In 1995, Peter Shor described an algorithm capable of factoring numbers into their prime factors and also solving the discrete logarithm of ECDSA.
- In 1998, the first 2-qubit machine was born, presented at the University of Berkeley, California.
- In 1999, IBM built the first 3-qubit machine.
- In 2001, IBM and Stanford University executed Shor’s algorithm for the first time on the first 7-qubit quantum computer. The experiment computed the prime factors of 15, correctly returning 3 and 5.
From then to the present, advances have continued. At CES 2019, IBM presented the IBM Q System One, the first quantum computer for commercial use — housed in a hermetic glass cube measuring 2.7 metres on each side, with a total of 20 qubits. In November 2019, Google announced “quantum supremacy”, having solved with its 54-qubit computer a problem that would have taken a conventional machine thousands of years.
So how many years remain until quantum computers can break ECDSA?
Predicting the future is enormously complicated, primarily because — as Nassim Nicholas Taleb argues in his book The Black Swan — we are unable to predict the potentially enormous effects of the highly improbable. Applied to our topic, this means we cannot predict whether, for example, a physical discovery of such magnitude might occur that our understanding of quantum mechanics advances to the point where building quantum computers with very many qubits becomes trivial… or perhaps impossible.
Assuming there will be no black swans in quantum computing, we can make predictions based on what we know. Let’s summarise our history of advances in quantum computing.
We know that from 1981 to 2001 — in 20 years — we managed to build the first quantum computer capable of factoring 15 into its two prime factors: 3 and 5. And that in the following 20 years we reached 20 qubits in a 2.7-metre cubic computer and another of 54 qubits that performed the first calculation (with no practical application) that a conventional computer could not perform faster. In nearly 40 years we have managed to build a 54-qubit quantum computer. Building computers with many qubits is not straightforward.
To harness the full computing power of quantum computers and enable them to execute the algorithms that give them that exponential advantage over conventional computers, it is essential for the qubit system to be in a state of entanglement. Quantum entanglement is one of the most counterintuitive physical phenomena in quantum mechanics — a phenomenon that Einstein himself could not accept, yet which has been verified experimentally. We won’t go into what quantum entanglement is, but for our purposes it is enough to know that entanglement is fundamental to the functioning of quantum computers. Currently, we can maintain qubits in this state for around 100 ms. This is the time window we have in which to perform our calculation. When entanglement is lost (quantum decoherence), it’s over — calculation cannot continue.
There are different techniques for building a qubit system capable of sustaining entanglement, but the most promising one (based on superconductors) requires qubits to be maintained at a temperature of… 15 millikelvin! To get a sense of what temperature this is: it is very likely that the coldest place in the universe right now is a qubit inside one of the existing supercomputers. Even the outer space most distant from any star is at a higher temperature — 2.7 Kelvin.
To summarise: we have quantum computers and we have the necessary algorithm (Shor), but breaking the discrete logarithm for 256-bit keys (such as those used in Bitcoin) requires a computer with more than 2,300 qubits. As we have seen, building computers with more and more qubits is far from simple, and in 40 years we currently have computers of 54 qubits. Technological progress need not be linear, of course, but a priori it does not seem likely that we will build a computer with more than 2,300 qubits within the next 10 years. If we ever achieve it (and that’s a big “if”), it will likely take far longer — 20, 50 years or more.
Conclusion: should we be worried? In my opinion, quantum computing does not pose a relevant threat to Bitcoin at the present time, since we are very far from being able to build a quantum computer with a sufficient number of qubits to break ECDSA. However, this is solely my personal opinion after considering the facts set out above.
In any case, if a day were to come when the threat was more imminent, Bitcoin could be updated and ECDSA replaced by a quantum-cryptography digital signature scheme — something that could be implemented without any disruption to the network via a Soft Fork (VI).
References
(I) Anatomy of a Bitcoin transaction https://privatekeys.org/2018/04/17/anatomy-of-a-bitcoin-transaction/ (II) Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer https://arxiv.org/abs/quant-ph/9508027 (III) Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms https://arxiv.org/pdf/1706.06752.pdf (IV) Quantum Computing https://en.wikipedia.org/wiki/Quantum_computing (V) Simulating Physics with Computers. Richard P. Feynman http://www.wisdom.weizmann.ac.il/~naor/COURSE/feynman-simulating.pdf (VI) Soft Fork https://en.bitcoin.it/wiki/Softfork