Quantum computing and Bitcoin cryptography

[monkeybars]

Bitcoin could surely be overtaken by another, better-designed cryptocurrency. Imo, this is its only genuine threat in the currency world.

But what about breaking its cryptography and comprising the Bitcoin protocol with next-generation computing devices? I have doubts that "faster / next-paradigm computing" could enable the protocol to be cracked.

Even now proto-quantum computers (D-Wave Systems) are coming online and clocking cryptographic computation speeds at 10,000x faster than binary machines. Quantum speeds grow expontentially as bits are added, yet the bits are being added exponentially as well. This would indicate a vastly accelerated speed in the coming years, compared to binary.

Given that Bitcoin mining uses cryptographic techniques, it is probable that quantum computing would be adopted by the mining industry very early on. I think that would preclude the possibility of a quantum early adopter from cracking the Bitcoin protocol and committing fraud directly.

So, even considering the massive cryptographic computation gains to come in the next years and decades, peripheral technologies, and not the Bitcoin protocol itself, will continue to be the weak points in the use chain.

What do you think?

[cakecrumb]

this amazing

[asix_tub]

As far as I gather generating a new block requiers solving the problem

 find x so that H(H(x)) < eps  

where H() is the hashing function, x is the input and eps is a (small) integer.
I think this is solved today by a brute force method. Miners try many variations of x until they stumble upon a solution. Making eps smaller makes the problem harder.

What happens if in 5 years there will be a quantum computer that can solve this problem very quickly with eps = 0 ? Will that be the end of bitcoin?

[monkeybars]

What happens if in 5 years there will be a quantum computer that can solve this problem very quickly with eps = 0 ? Will that be the end of bitcoin?

My contention is: no. "Very quickly" would simply be the new normal as mining operations all upgrade their machinery as soon as it is available. Since there would be a major jump at the paradigm shift, the very earliest adopters would have a massive advantage for a very short time. Then everything would simply even out again at this level (say, millions of times faster than today's block computation).

[monkeybars]

This thread has a lot of relevant information.

https://bitcointalk.org/index.php?topic=133425.0

[mochicoin]

It might so happen that a government is the first to fund and consequently produce a quantum computer. Considering this, it is unlikely an unprivileged individual would have access to such technology unless they developed or funded the research. All sophistry aside, quantum computers will cause all current forms of cryptography to become antiquated. The good/bad news is that building a functional quantum computer has proven to be a great challenge thus far. The better news is that cryptocurrencies are funding technological advances towards higher efficiency machines. It's only a matter of time until some entity realizes that such computing power translates into real world power.

[monkeybars]

It might so happen that a government is the first to fund and consequently produce a quantum computer. Considering this, it is unlikely an unprivileged individual would have access to such technology unless they developed or funded the research. All sophistry aside, quantum computers will cause all current forms of cryptography to become antiquated. The good/bad news is that building a functional quantum computer has proven to be a great challenge thus far. The better news is that cryptocurrencies are funding technological advances towards higher efficiency machines. It's only a matter of time until some entity realizes that such computing power translates into real world power.

The QC revolution/transition will be very rocky indeed as certain forms of computation suddenly jump by orders of magnitude and old forms of security become suddenly crackable (perhaps 2040s?). It's analogous to the shortly coming changes in the economy as we move from fiat national currencies to decentralized cryptocurrencies (next 10 years).

[jickMagger]

This is all assuming that commercial quantum computers (the D-wave in particular) actually behave how they're advertised, and are available for consumer use any time soon. If someone has the money to purchase one, I really hope they use it for something more worthwhile.

[Xanthe]

An interesting discussion here. The good thing is that if necessary, the crypto algorithm used by Bitcoin can be updated without too much work. Provisions are already in place and this has been demonstrated by the Scrypt-based forks of Bitcoin, like Litecoin.

I can already hear the cries of "Quantum computers are ruining Bitcoin!" which will of course follow the current echoes of "ASICs are ruining Bitcoin!" which were preceded by the lamentation "GPUs are ruining Bitcoin!"

[monkeybars]

This is all assuming that commercial quantum computers (the D-wave in particular) actually behave how they're advertised, and are available for consumer use any time soon. If someone has the money to purchase one, I really hope they use it for something more worthwhile.

It doesn't assume any such thing. Even a partial quantum computer like D-Wave's can do certain cryptographic calculations orders of magnitude better than classical processors. General quantum computers don't have to arrive "soon" for them to make a major impact on the world, and on cryptocurrency in particular. And you better believe that cryptocurrency will have a major foothold in the economy decades from now.

[monkeybars]

An interesting discussion here. The good thing is that if necessary, the crypto algorithm used by Bitcoin can be updated without too much work. Provisions are already in place and this has been demonstrated by the Scrypt-based forks of Bitcoin, like Litecoin.

I can already hear the cries of "Quantum computers are ruining Bitcoin!" which will of course follow the current echoes of "ASICs are ruining Bitcoin!" which were preceded by the lamentation "GPUs are ruining Bitcoin!"

Precisely. People are already talking quite a bit about QCs and we're arguably dozens of years from practical general quantum computing. By the time they're on the near horizon, the hooks in Bitcoin and all other widespread forms of electronic cryptography will be undergoing major renovation. Think Y2K -- it's not something that can catch us off guard because we can see it coming as the research advances.

This is not to say other disruptive technologies couldn't severely compromise cybersecurity at any time along the way, as they have in the past.

[jjbliss]

Precisely. People are already talking quite a bit about QCs and we're arguably dozens of years from practical general quantum computing. By the time they're on the near horizon, the hooks in Bitcoin and all other widespread forms of electronic cryptography will be undergoing major renovation. Think Y2K -- it's not something that can catch us off guard because we can see it coming as the research advances.

Definitely.  Any problem bitcoin has will be shared by any other system using cryptography.  If anything, upgrading mining systems to QC would provide a built-in safety advantage to Bitcoin over other electronic payments.