Who Will Steal Satoshi’s Bitcoins?

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.

body[data-twttr-rendered="true"] {background-color: transparent;}.twitter-tweet {margin: auto !important;}

I'm not an expert in quantum computing. Why do most people aim for 128-bit security in post-quantum crypto? Just be on the safe side? My wild guess is that even with QCs with enough qbits, it will be much costlier to perform, say 2^80 quantum iterations, than 2^80 classical iter.

— @real_or_random

@real_or_random I think that no one really knows what quantum computers will look like, at what clock rate they will operate at, whether they will even exists and what their exact location and momentum is at a given time. But re 80bit security the Bitcoin miners do 2^80 hashes every 12 hours.

— @benediktbuenz

@benediktbuenz Yes, that's my take, too. If anything, we know that 128 is fine, and that is all we need to know to design systems. But this seems to be just folklore. It would be interesting to read an opinion of someone who works on building quantum computers.

— @real_or_random

Tim is one of the inventor of CoinShuffle[1]/ValueShuffle[2] and Benedikt is a contributor to the Bulletproofs[3] paper (BP). In a nutshell, BP is a system that makes half the content I created in this Medium blog over the years immediately obsolete and useless, so I am extremely motivated to see it succeed and get it into Bitcoin. There is just one problem.

Confidential Transactions/Bulletproofs: The Elephant In The Room

BP is based on the discrete logarithm assumption, which is considered to be unsafe against quantum computers. But wait, Benedikt said the only thing we know about quantum computers is that we know nothing about it. Our quantum crypto standards against them are just guess work. “Ok, I can work with that, let’s do some research.” Let’s ask why isn’t the discrete logarithm assumption 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 + 2dlog2 (n)e + 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’s 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.

Google Announces a 72 Qubit Superconducting Quantum Chip | Quantum Computing Report

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, but 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. (Physical curve) It is also poised to predict the quantum supremacy breakthrough (Classical Limit.)

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 even be broken sooner. Never mind, my quest on poking holes on the assumption that it’s quantum computer vulnerable utterly failed. Not only that, it also did not help me get back to sleep. It’s 4:00 AM already.

I could finish here, but my brain is already working on another closely related issue. BP is a nice to have quantum vulnerable feature, but 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 that’s the ones I understand, 4–5 years doesn’t make a difference in such volatile predictions and anyway “I don’t have the brain space” to understand their graphs at 5:00 AM.

But why is it important? This means this relationship can be broken:

Now, if I would write this article to a mainstream media outlet, I would launch the biggest FUD campaign you’ve ever seen. “It’s 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 don’t expose your public key, you don’t need to worry about quantum computers and the only way to expose your public key is to make a Bitcoin transaction. If you don’t reuse addresses you are quantum safe.

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 us to propose a hard fork that invalidates P2PK outputs so he’ll 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 don’t feel like startups stand a chance. There are also the D-Wave computers, but they are working on the quantum annealing machines, along the adiabatic curve, which doesn’t cross the Shor line.What do you think, who will pull off the biggest theft in the history of mankind?

Supporting ZeroLink/HiddenWallet:

bc1q32xe73texphk3cgu33cyw7dajky9u76qltcv6m (Accountability)

Publication date

03/09/2018 - 08:09

Author

nopara73

Article source

Disclaimer

The views and opinions expressed in this article are solely those of the authors and do not reflect the views of Bitcoin Insider. Every investment and trading move involves risk - this is especially true for cryptocurrencies given their volatility. We strongly advise our readers to conduct their own research when making a decision.