This week I was interviewed on the Cryptocast podcast (sorry, it’s in Dutch) and one of the questions during the one hour program was about Quantum Computing and Bitcoin. I only gave a short answer there, but think it’s an important topic so I decided to go a bit deeper in a blog post.
I have been following Quantum Computing (QC) for years because it’s a fascinating technology with huge implications for cryptography. Even though I I only have a basic understanding of how QC works, I at least try to understand what it could be used for. About 5 years ago I for example looked at using quantum computing for Bitcoin mining, but after discussions with scientists from UBC, QC not only seemed too far off, it also turned out that the machines could not be optimized for mining (meaning there would not be a huge advantage for using QC compared to ‘regular’ chips).
Simple quantum computers have been around for years, but ‘real’ RC was always expected to be here around 2025 at the earliest. Real QC meaning computers with enough qubits to do meaningful computations. It’s hard to explain it here (and like I said, I am no expert at all!), but qubits are similar to bits in a normal computer, but instead of being either 1 or 0, they can be in a 1 or 0 quantum state, basically 2 vectors in a 2D space perpendicular to each other (“a coherent superposition of both” is the term used in QC). When measured the result is either 0 or 1, however, just by measuring it the state gets destroyed and the result can change. There is a ton of information on the Internet if you want to better understand how this works, I won’t even try to do that here.
Interestingly, QC is suddenly developing much faster than anybody had expected. Google has shown some out-of-this-world results: Its quantum processor doesn’t just show exponential change (like in Moore’s Law), but double exponential change! What does that mean? Well, suppose you have 5 iterations of improvements, then in classical computers the computer would be 5 times as fast, with exponential change it would be 2^5=32 times as fast, and in the double exponential change it would be 2^2^5=4.2 million times as fast. That is hard to comprehend for human beings.
To quote from the article: “In December 2018 they were able to reproduce the quantum processor’s computation using a regular laptop. Then in January, they ran the same test on an improved version of the quantum chip. This time they had to use a powerful desktop computer to simulate the result. By February, there were no longer any classical computers in the building that could simulate their quantum counterparts. The researchers had to request time on Google’s enormous server network to do that. Somewhere in February they had to make calls to say, ‘Hey, we need more quota.’ They were running jobs comprised of a million processors.”
If this is true the world will see some radical changes in computing power over the next couple of months already. Real quantum computers will be here this year instead of somewhere in the next decade. It’s quite amazing how fast this is going.
Now keep in mind hat QC is fairly limited in what it can do. What it can do, however, is integer factorization, which determines the security of public key cryptographic systems. Ordinary computers can’t do this for large numbers, say products of 2 multi-hundred digit prime numbers. A quantum computer could efficiently solve this problem using Shor’s algorithm to find its factors. This ability would allow a quantum computer to break many of the cryptographic systems in use today, including potentially Bitcoin wallets.
So when I read the article I immediately thought about the implications for Bitcoin. I had done research on that years ago, but at that point I wasn’t that worried about it, simply because QC seemed at least a decade away. Now that that timeline had moved forward significantly it was time to look at it again.
It turns out that Bitcoin in its current state is not QC proof. However, that does not mean that your coins are at risk right away. What it means is that if you follow the recommended practice of only using your Bitcoin addresses one time, you should be fine. In that case your public key is only ever revealed at the one time that you spend bitcoins sent to each address. A quantum computer would need to be able to break your key in the short time between when your transaction is first sent and when it gets into a block (normally less than 10 minutes, depending on the mining fee you are willing to pay).
However, older addresses are still at risk. For example, Satoshi’s coins are all stored on (old) P2PK addresses instead of (new) P2PKH addresses, meaning that they are immediately vulnerable to a quantum computer attack. So you will have proof that real QC exists once Satoshi’s coins start moving!
The good thing is that a new public-key algorithm can be added to Bitcoin as a softfork. For a Bitcoin user this would mean the creation of a new address type, and everyone would need to send their bitcoins to this new address to achieve quantum security.
Am I worried about QC and Bitcoin? Not really. Even though QC seems to be just around the corner, there are solutions to make Bitcoin QC proof, and as long as you do not use addresses more than once you should be safe. Moreover, there are much better targets than the Bitcoin network for anybody controlling a QC network, Bitcoin will certainly not be on top of the list. Once a government has a functioning network it would want nobody to know that they have it, so using it to hack Bitcoin would probably be the last thing they would want to do. So nothing to worry about for now, but it’s certainly something we should pay close attention to.