New D-Wave Quantum Computer - 51% attack?

[bluemeanie1]

http://www.scientificamerican.com/article.cfm?id=d-waves-quantum-computer-courts-controversy

These new quantum computers change the game in the IT world, and certainly might effect some of the assumptions behind Bitcoin's security.  The question that needs to be asked: how quickly can blocks be 'mined' with such a computer?

But the pain has been real — much of it, critics would argue, brought on by Rose himself. In 2007, his company announced its first working computer with a showy public demonstration at the Computer History Museum in Mountain View, California. By the current standards of quantum computing — which in theory offers huge advances in computing power — the device's performance was astonishing. Here was a prototype searching a database for molecules similar to a given drug and solving a sudoku puzzle, while the best machines built using standard quantum approaches could at most break down the number 21 into its factors.

Butterfly Labs better take notice.

[bluemeanie1]

earlier threads on Bitcoin and quantum computing:

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

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

https://news.ycombinator.com/item?id=2602570

[rizzla]

http://cr.yp.to/hash/collisioncost-20090823.pdf

[moni3z]

The last thing somebody is going to do with a quantum computer is mess with bitcoin. I can think of almost infinite things they should be doing first like bioinformatics and physics calculations for new trillion dollar alternative power methods.

Bruce Schneier has written about QC numerous times on how useless it is for practical cryptography, just look up quantum computing on his blog, go through all the posts, deflate the hype

[ForumAcc]

These quantum computers do not actually do what you think they do. they aren't conventional function computers but probability solvers for formations of solutions. they are very epotomy of asics but not for definitive maths.

they do not do standard mathematics and cannot be switched over. they short cut high difficulty pattern and lowest energy state problems in a noisy quantum way. they are not good at high grade parallel math. they effectively act like little distillery pots for patterns or lowest energy configurations of a problem, like folding or crystal lattice problems.

http://www.scientificamerican.com/article.cfm?id=d-waves-quantum-computer-courts-controversy&page=5

[crazy_rabbit]

I feel like we talk about this every few months.

[bluemeanie1]

http://cr.yp.to/hash/collisioncost-20090823.pdf

initially though, consider that the 'experts' claimed that Quantum Computing had no effect on hashing algorithms.

[Vanderi]

EVERYBODY PANIC

[solex]

There have been loads of threads on this subject.

Bottom line is that there is no need to worry about a QC threat to Bitcoin in this decade or the next (or longer :-)

a) The capabilities of any QC that can be built today with one that can brute force a private key is like comparing Red Baron's bi-plane with a stealth fighter.

b) All fiat transactions in financial systems done over the internet, indeed, internet security itself would also be at risk, not just Bitcoin.

c) Different hashing algorithms can be used to replace SHA-256 that are much more resistant to QC problem solving.

[jetmine]

http://cr.yp.to/hash/collisioncost-20090823.pdf

Interesting paper.

According to it, preimage searches can be faster on quantum computers than on classic computers.  BTC mining can be expressed as preimage search, so the extended Grovers algorithm could be applied.  The paper sais it is not clear what search complexity is required to reach the tip-over point at which a quantum computer is more efficient.  Therefore it isnt clear on which side BTC sits.  It may or may not be more efficient.

If BTC mining was more efficient on quantum computers, it wouldnt necessarily be the end of BTC.  As long as the length of SHA2 hashes permit, quantum mining rigs will be dealt with by difficulty adjustments.  Just like GPU, FPGA, ASIC technology each is so much more efficient than the previous generations.  The network has compensated for all of them and is still running as designed.

There is a maximum possible difficulty though.  Only when the network hashing power gets beyond that point, BTC mining is broken.  Until then: business as usual.

Other areas of BTC (such as the public key crypto) are probably much more vulnerable to quantum computers than the mining process.

[Littleshop]

There have been loads of threads on this subject.

Bottom line is that there is no need to worry about a QC threat to Bitcoin in this decade or the next (or longer :-)

a) The capabilities of any QC that can be built today with one that can brute force a private key is like comparing Red Baron's bi-plane with a stealth fighter.

b) All fiat transactions in financial systems done over the internet, indeed, internet security itself would also be at risk, not just Bitcoin.

c) Different hashing algorithms can be used to replace SHA-256 that are much more resistant to QC problem solving.

And finally, many scientists doubt that the D-wave is actually a quantum computer in the first place.  It may be a quantum computer simulator but does not solve any problems faster then a traditional large computer so far. 

[jag2k2]

To me if there is a computer powerful enough to attack bitcoin then it is powerful enough to attack traditional banking institutions as well.  All monetary systems would be at risk not just bitcoin.

[AquaticBob]

There'd be a lot more things in danger, too.

[domob]

There have been loads of threads on this subject.

Bottom line is that there is no need to worry about a QC threat to Bitcoin in this decade or the next (or longer :-)

a) The capabilities of any QC that can be built today with one that can brute force a private key is like comparing Red Baron's bi-plane with a stealth fighter.

b) All fiat transactions in financial systems done over the internet, indeed, internet security itself would also be at risk, not just Bitcoin.

c) Different hashing algorithms can be used to replace SHA-256 that are much more resistant to QC problem solving.

And finally, many scientists doubt that the D-wave is actually a quantum computer in the first place.  It may be a quantum computer simulator but does not solve any problems faster then a traditional large computer so far. 

Indeed all that I read about the D-wave device was that it can outperform classical computers for certain optimisation problems, but it is not a "general purpose quantum computer" which could either run Grover's algorithm for sqrt(N) searches in unsorted lists, or Shor's algorithm for integer factoring and discrete logarithms.  Note that in my opinion, mining / SHA-2 is not the crucial point if a quantum computer is ever dangerous to bitcoin.  Instead it is the public key cryptography and ECDSA (although I don't know how susceptible ECDSA is to quantum computing).

[esenminer]

If / when quantum computers are available and have enough bits to run algorithms to brute force SHA256, to maintain it's current security level Bitcoin would have to implement SHA512

http://en.wikipedia.org/wiki/Key_size#Effect_of_quantum_computing_attacks_on_key_strength

Bennett, Bernstein, Brassard, and Vazirani proved in 1996 that a brute-force key search on a quantum computer cannot be faster than roughly 2^(n/2) invocations of the underlying cryptographic algorithm, compared with roughly 2^n in the classical case.

So 512 bits of security in a classical computer would give 256 bits of security for a quantum computer.

[leopard2]

The question is, will only the bad guys have quantum computers? What will be the computational power of personal q.c. versus large q.c.? If reasonable quantum computing power is available to everyone, nothing will change - people will use small q.c. for encryption and the NSA will have big ones that take trillions of years to brute force.

Only if normal people are stuck with classical computers, and the bad guys have q.c. then we're fucked.

[Vanderi]

Only if normal people are stuck with classical computers, and the bad guys have q.c. then we're fucked.

Lol, I'm actually tempted to put this statement in my sig. Funny shit.

[Severian]

Prediction: The next Pirateat40 will be advertising a quantum miner. He'll make a fortune and delivery will be pending for years.