I woke up in the middle of the night so I fired up Twitter and I encountered two well-known cryptographers’ conversation about quantum computing.
Tim is one of the inventor of CoinShuffle[1]/ValueShuffle[2] and Benedikt is a contributor to the Bulletproofs[3] paper. Bulletproofs is a great addition to Confidential Transactions which is transaction amount masking. It is important, because known amounts are the root of all evil in most Bitcoin privacy techniques. Or, in other words, Bulletproofs is a system that obsoletes half of the content I created in this Medium blog. Thus, I am immensely motivated to see it succeed and get it into Bitcoin. There is just one problem.
Bulletproofs is based on the discrete logarithm assumption, which is considered to be unsafe against quantum computers. Wait a second, Benedikt said the only thing we know about quantum computers is that we know nothing about it. Our quantum crypto standards are just speculations. “Ok, I can work with that, let us do some research.” Let us ask why the discrete logarithm assumption is not safe.
It turns out there is an algorithm that can break it: Shor’s discrete logarithm quantum algorithm for elliptic curves.[4] This algorithm is referenced in every paper and article that discusses the topic.
“Ok, this looks legit, how practical is it?” I found recent paper from Microsoft that publishes precise estimates: Quantum resource estimates for computing elliptic curve discrete logarithms.[5]
We conclude that elliptic curve discrete logarithms on an elliptic curve defined over an n-bit prime field can be computed on a quantum computer with at most 9n + 2 [log2 (n)] + 10 qubits using a quantum circuit of at most 448n^3 log2 (n) + 4090n^3 Toffoli gates.
We all know qubit is the biggest bottleneck of quantum computing so that is the number we most care about. I started researching on what qubit count today’s quantum computers can achieve. I encountered the numbers 3 and 4 a lot, I noticed 2017 posts were talking about 17-ish numbers so I limited the time frame of the search and found that Google came up with Bristlecone, a 72 qubit processor a few days ago.
This processor is said to demonstrate quantum supremacy the first time, which means it can run a special algorithm faster than a classical computer would. Luckily this is far from an imminent threat, however this rapid increase of the number of qubits reminded me of Moore’s law. Is it applicable to quantum computing, I asked? Internet says maybe.[6]
The article was written by the Quantum Computing Report in 2016 and based on Moore’s law, it successfully predicted the 17 qubit machines in the beginning of 2017 and Google’s 72 qubits now, which is visible on the Physical curve. Moreover it is poised to predict the quantum supremacy.
For Bulletproofs, what matters is the Shor RSA2048 line, which is predicted to be broken in 2022–23. In fact, ECC is more vulnerable than RSA in a post-quantum world, so our discrete logarithm assumption may be broken even sooner. Never mind, my quest on poking holes on the assumption that Bulletproofs are quantum computer vulnerable utterly failed. Furthermore, it did not help me get back to sleep either. It is 4:00 AM already.
I could finish here, however my brain is already working on another closely related issue. Bulletproofs is a nice to have quantum vulnerable feature, although we do have other quantum vulnerable features in Bitcoin: Quantum attacks on Bitcoin, and how to protect against them.[7]
The elliptic curve signature scheme used by Bitcoin is much more at risk and could be completely broken by a quantum computer as early as 2027, by the most optimistic estimates.
The paper estimates the breakthrough to 2027 with a completely different method. I tend to think 2022–23 are the right numbers, since those are the ones I understand, 4–5 years do not make a difference in such volatile predictions and anyway “I do not have the brain space” to understand their graphs at 5:00 AM.
Why is it important? This means that the following relationship can be broken:
Now, if I would write this article to a mainstream media outlet, I would launch the biggest FUD campaign you have ever seen. “It is a disaster, everyone’s bitcoins are in danger!” Luckily, I am writing this in my blog, so I can tell you that no one actually knows anyone’s public key. What we know about others is something else. The hash of the public key:
Thus, as long as you do not expose your public key, you do not need to worry about quantum computers and, not mentioning some edge cases here, like when you are a miner, the only way to expose your public key is to make a Bitcoin transaction. If you do not reuse addresses you are quantum safe.
Update: RBF can be used to conduct attack on RBF-enabled transactions:
Or are you? It depends on how long you are in Bitcoin:
[Source] Bitcoin 0.1 supported Bitcoin addresses just like today, but it also had a “pay to IP address” feature. When you used this, you’d connect to the IP and get the sender’s full public key, and then send to that. […] Pay-to-IP was removed around 0.5, I think.
Satoshi accumulated about 1 million bitcoins, 1/21 of the total coin supply, many of them are sitting on public keys due to this early feature. This one million Bitcoin is poised to be stolen within 5 to 15 years. Or even sooner, depending on, if secret government projects are still a thing.
Does Satoshi still have access to these coins or was he playing with them the same way as we are playing with our testnet coins? Is he just waiting for dangerous qubit breakthrough or for us to propose a hard fork that invalidates P2PK outputs so he will move them before that would happen? How did exactly this P2IP work anyway? Can it tell us more about Satoshi somehow?
Finally, let me answer the question in the title: Who will steal Satoshi’s bitcoins?
Today Google seems to be winning the race, Microsoft and IBM are not far behind. The US government, the Chinese Communist Party and a few other governments can be wild cards. I do not feel like startups stand a chance. Additionally, there are the D-Wave computers, although they are working on the quantum annealing machines, along the adiabatic curve, which does not cross the Shor line.
What do you think, who will pull off the biggest theft in the history of mankind?
