Can Quantum Computers Break Bitcoin?
There has always been a lot of discussion around whether or not quantum computers could realistically break bitcoin’s SHA-256 algorithm. If that was done in secret, thousands of medium value addresses could slowly be stolen without anyone noticing. If it was realized that the algorithm was being broken, a hard fork could take place, but it would be a complete mess and massive amounts of damage would have likely been done. There is no doubt that at some point in the future computers will be able to break the SHA-256 algorithm, but how far off are we talking about ?
The largest quantum computers right now are owned by big companies such as IBM,Intel,Google and a handful of government/academic institutions. This may IBM unveiled their 16 quibit, or quantum bit, computer which is considered at this point the most powerful quantum computer that is actually available in the near future. I say “available”, but realistically very few people actually have access to it and the machine is worth hundreds of millions of dollars. Previously, their past largest was 5 quibits, so there definitely is growth on the technology behind the processors that power the machines.
What amount of quibits would potentially we dangerous to breaking bitcoin’s algorithm? This we really don’t know because specific applications would have to be made to try and brute force the sha 256 algorithm. As far as we know IBM isn’t currently working on this function, so we really don’t know how far they can get. In the past they have made statements that at 50 quibits, mathematical problems and algorithms thought unbreakable, would essentially be able to be brute forced, but again it is only speculation. I would say if we got to that point, which probably wont happen for another handful of years, we would possibly want to think about changing the algorithm just to be safe. However with the massive mining industry based off SHA 256, there would have to most likely be some sort of compromise between developers and miners. Which raises a whole other problem.
In terms of regular computers, botnets, ect, breaking the SHA 256 algorithm is near impossible. It would take thousands of years to break a private key. With the amount of possible characters, brute forcing would be a great waste of power and time. There have been a few groups who have claimed to be able to brute force a few private keys, specifically a group that claims to have done it multiple times, which would be like winning the lottery, or more than likely they have found a bug within a website that generates private keys. We are pretty sure that the algorithm itself is safe, but websites generating keys might use some sort of generator that limits them to certain keys, making the keys generated there, much more vulnerable to being brute forced. There is actually going to be a talk at the next Defcon about brute forcing private keys, so I expect that to be very interesting.
Overall, while quantum computers can and at some point will have the ability to crack sha 256 and brute force private keys on many of the coins of today. I don’t think it is something we have to worry about in the immediate future. Upgrading the protocol and adding user friendliness is a much better use of our time. Even if we reached a point where brute forcing became possible, it would still be very expensive and the algorithm would be upgraded to a stronger and uncrackable substitute. For the most part, quantum computing breaking bitcoin isn’t something we really have to worry about at this point in time.
Thanks to @Elyaque for the badges
Because SHA-256 is a bit-mixing algorithm, I don't think quantum computing would lend itself to cracking it any easier than traditional means. I haven't seen any algorithm suggested that would help to solve any hashing algorithm. IOW, QC isn't magic that spits out results for any given problem.
I think QC will even have a problem solving the Discrete Logarithm Problem for Elliptic Curve, because each point in the field is random compared the the adjacent scalar values in the underlying group.
EC is like having a huge stack of papers that are all in the wrong order. For example, the first page may be labeled 1,323, the second page is labeled 75, the third page is 7,888... etc. You can easily count through the stack to find the 75th piece of paper, and tell somebody that it is page number 999. Given that page number, they will have a hard time telling you that it's the 75th piece of paper in the stack. This is the EC DLP.
Now take that stack of papers and extend it so that it goes to the Andromeda galaxy that is 2.537 million light years away. That's only about an 85-bit number of pages. Double that distance (5 million light years), and that's an 86-bit number. We use 256 bits for Bitcoin and most other cryptocurrencies.
Where QC shines is for solving the DLP or factoring of RSA because each value is the value (no weird translation to another coordinate space, like EC requires). This is what the famous Shor algorithm helps to solve.
(Writing this comment inspired me to also create a blog post using the stack of papers metaphor: Introducing the Elliptic Curve Discrete Log Problem)
Thanks for the detailed comment - learned a lot just digging in based on your jumping off points. Followed and upvoted.
These metaphors are useful for understanding
Thanks a lot for clarifying this - based on what you are saying, the risks of quantum computing aren't nearly as bad as if it's some kind of linear computing power issue.
I think there's a lot of misunderstood hype about what quantum computing can actually do.
Don't get me wrong - for certain problems, it will be orders of magnitude more efficient than traditional computing, and this is very cool stuff! But, it's not magic - that's my bigger point.
Maybe somebody will come up with an algorithm in the future for some of the problems that I mentioned, and maybe QC will only be used to solve a small piece of that algorithm (that's its role even in the Shor algorithm - you still need a classical computer for a lot of the factoring work).
But, given the information that I've been able to find today, I don't fear that SHA-256 or EC DLP will be broken by QC any time soon. Time will tell!
Thanks for commenting on this. Your explanation is clear and helpful.
It'll happen sooner than we think. The defense? If you own a ton of bitcoin, don't put it all in one wallet!
@calaber24p all these theories and possibilities makes me worry a bit due to all our investments and time on Blockchain technology including steem. Hopefully all these corporations won´t find a way to compromise the blockchian technology and thus make crypto´s worthless. Good post indeed, thanks
I watched something on steemit about IOTA, it is a new technology that is suppose to be quantum proof. The tech is call tangle and the smart token is IOTA. I found it quite interesting, and hope to be able to invest in it when it comes available. Thank you very informative article.
Great post! it is necessary to erase all these myths, upvoted!
I would be very interested in an article that describes solution to the quantum computing problem. The danger is many years ahead from actually threatening btc, but btc is a small thing compared to atomic weapons that could be hacked with quantum computers.
Brute force can't make the private key visible to anybody but their might be some other Currency which can overtake Bitcoin by rumors of their future, these type of things might be harmful but bitcoin can't be broken.
I have same thought few years back. Basically is possible but difficult at this moment.
Yea quantum computing is pretty far off as a concern. D-Wave has usable models but they are used for very specific types of calculations.
I also think that IF quantum computing becomes widely available, we will have some kind of fork that addresses security issues.
This is an informative article, although I reached the opposite conclusion as you by the end!! Based on all the info you give about Quantum Computing going from 5 -> 16 quibit systems, and that 50 quibits is enough to basically destroy Bitcoin's security... AND it could happen in secret, theoretically.. no good!
Seems to me like something the bitcoin community would want to address sooner than later. "Quantum-proofing" the system may be one of the top 5 "Black Swan" issues to be considered, in my humble opinion.