Take the 2-minute tour ×
Bitcoin Stack Exchange is a question and answer site for Bitcoin crypto-currency enthusiasts. It's 100% free, no registration required.

A scalable quantum computer is a quantum computer that is easy to extend - adding more (q)bits of memory is not a fundamentally hard problem, and will happen. Or, alternatively, that it follows Moore's Law - its memory capacity and speed will increase exponentially over the years with technological advancement (the exponent might be relatively low).

Suppose such a Quantum Computer were constructed tomorrow - what would this mean for bitcoin?

share|improve this question
    
wired.com/wiredenterprise/2013/06/d-wave-quantum-computer-usc looks like quantum computers are almost here –  user5795 Jul 2 '13 at 21:29
    
"that it follows Moore's Law - its memory capacity and speed will increase exponentially over the years with technological advancement" This is not what Moore's Law is about. Moore Law is about density of transistors in electronic circuit. –  Maciej Mączko Nov 20 at 21:23

4 Answers 4

up vote 12 down vote accepted

You have a good discussion in:

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

Basically, ECDSA is compromised, hashing isn't. With a quantum computer, you could easily deduce the private key corresponding to a public key. If you only have an address, which is a hashed public key, the private key is safe. Anyway, to spend a transaction, you need to send the public key. At that point you are vulnerable, but the attack is not straightforward.

In general, quantum computers are not exponentially better than classical computers. You cannot access all the states in the superposition, only global properties. You can read http://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf to get a good idea of what they can and cannot do.

share|improve this answer
1  
By the way.. There is no guarantee that classical computers cannot break ECDSA or SHA256. The involved problems are only supposed to be difficult. –  halftimepad Jan 14 '13 at 18:59
    
Are you saying that elliptic curve point multiplication hasn't been proved difficult? –  Janus Troelsen Apr 28 '13 at 11:12
2  
I guess you mean inverting point multiplication ("division" if you want). Point multiplication is easy. It is what you do when you know the key. For the inverse problem, as in most public key cryptography, there is no proof of security. A related problem is P vs NP: en.wikipedia.org/wiki/P_vs_NP which still hasn't been solved. Inverting is only supposed to be hard. A lot of people have tried to find an efficient algorithm and they have failed. The best known ways to invert multiplication are indeed slow, but there could be a better way. –  halftimepad Apr 29 '13 at 17:55

Worst case scenario:

  1. Bitcoin ECDSA algorithm would be broken. Because quantum computers can easily decrypt the private key using the public key, anyone with a quantum computer can extract Bitcoins using the corresponding public key.

  2. Bitcoin hashing would become exponentially difficult. There's already a predicted escalation in mining difficulty due to the advent of ASIC, and quantum computers would create a spike in mining difficulty to which ASIC mining effects pale in comparison. In the short run, this would lead to hyperinflation, but the long run effects aren't known at this point.

  3. The hashing advantage of quantum computer will be curtailed by block mining limitations. To quote from the Bitcoin wiki:

"The difficulty is the measure of how difficult it is to find a new block compared to the easiest it can ever be. It is recalculated every 2016 blocks to a value such that the previous 2016 blocks would have been generated in exactly two weeks had everyone been mining at this difficulty. This will yield, on average, one block every ten minutes. As more miners join, the rate of block creation will go up. As the rate of block generation goes up, the difficulty rises to compensate which will push the rate of block creation back down."

This means that the rate of block creation will not be impacted by quantum computers (the increase in key generation is proportional to the increase in difficulty, resulting in an overall mining rate of 1 bitcoin block every 10 minutes), but it will drastically increase the mining difficulty, exponentially more than ASIC miner already have. This gives miners with quantum computers (presumably corporations, government agencies, or other power organizations) a major advantage, to the point of being considered a monopoly, on the bitcoin market.

Unless quantum computers either:

(a) become publicly available (b) are given their own class for hashing purposes, so as to limit their mining advantage

Then miners with access to quantum computers have an unfair mining advantage, which can (and will be) used to manipulate the value and distribution of bitcoins. Furthermore,

  1. Quantum computer's hashing power can be used as voting power. If a coalition of people with scalable quantum computers could generate enough hashes to comprise over 51% of the total Bitcoin hashes,they could use that power to greatly manipulate the bitcoin network.

As explained in the Bitcoin wiki ("Weaknesses")

"An attacker that controls more than 50% of the network's computing power can, for the time that he is in control, exclude and modify the ordering of transactions. This allows him to:

Reverse transactions that he sends while he's in control. This has the potential to double-spend transactions that previously had already been seen in the block chain. Prevent some or all transactions from gaining any confirmations Prevent some or all other miners from mining any valid blocks

The attacker can't:

Reverse other people's transactions
Prevent transactions from being sent at all (they'll show as 0/unconfirmed)
Change the number of coins generated per block
Create coins out of thin air
Send coins that never belonged to him 

With less than 50%, the same kind of attacks are possible, but with less than 100% rate of success. For example, someone with only 40% of the network computing power can overcome a 6-deep confirmed transaction with a 50% success rate.

It's much more difficult to change historical blocks, and it becomes exponentially more difficult the further back you go. As above, changing historical blocks only allows you to exclude and change the ordering of transactions. It's impossible to change blocks created before the last checkpoint."


However:

"Since this attack doesn't permit all that much power over the network, it is expected that no one will attempt it. A profit-seeking person will always gain more by just following the rules, and even someone trying to destroy the system will probably find other attacks more attractive. However, if this attack is successfully executed, it will be difficult or impossible to "untangle" the mess created -- any changes the attacker makes might become permanent."


All this being said, is it possible for a scalable quantum computer (specially, one that is programmed (like ASIC) to hash blocks) to have an exponential advantage over traditional computers, FPGAs, ASICS, etc.?

That question is better addressed here: http://cs.stackexchange.com/questions/586/could-quantum-computing-eventually-be-used-to-make-modern-day-hashing-trivial-to

There's a lot of mathematics involved, which is a bit above my academic proficiency, but we can derive at least this much:

Most of the algorithms quantum computers are famous for efficiently utilizing (Shor's algorithm, Grover's search algorithm) probably can't be used for hashing Bitcoin blocks. One possible exception noted is the collision attack, which if done using Grover's algorithm, could possibly perform better attacks than conventional computers:

"Can quantum-computers perform better collision attacks? Actually I'm not sure about it. Grover's algorithm can be extended, such that if there are t items (that is, preimages), the time to find one is reduced to O(N/t−−−−√). But this gives no collision - running the algorithm again might return the same preimage. On the other hand, if we choose m1 at random, and then use Grover's Algorithm, it is probable that it will return a different message. I'm not sure if this gives better attacks."

http://cs.stackexchange.com/questions/586/could-quantum-computing-eventually-be-used-to-make-modern-day-hashing-trivial-to

In the event that scalable quantum computers manage to corner the Bitcoin network, new code will be released to patch this vulnerability, so while there would be a long-term breakage of the network in the short term, there's nothing to worry about for Bitcoin users in the long term.

share|improve this answer
1  
"resulting in an overall mining rate of 1 bitcoin every 10 minutes)," 1 BLOCK in ten minutes. –  Maciej Mączko Oct 23 at 17:32
1  
Thanks for noting my typo @Maciej Mączko. I have appended the omission as you suggested :) –  nspyraishn Nov 20 at 18:52

I want to point out a quick possibly important point.

As other answers have mentioned current implementations of Bitcoin could be compromised by a quantum computer.

However, Quantum Computers do not solve all known classically hard problems and so any cryptography that is based on problems that are also difficult for a Quantum Computer to solve should work just as fine as classical crypto which also lives under the existential threat of someone discovering a polynomial time algorithm for factoring and similar problems.

share|improve this answer

The algorithm that compose the bitcoin's address are ECDSA and will be completely broken (you would be able to find one's private key with the public key). So you would be able to spend anyone's bitcoin.

The mining though is sha-256 based and is still "secure", in secure I mean it can't be simply reversed, but it still can be brute force. And since a quantum computer is exponentially more powerful people with QC would begin to mine like hell and the difficulty would rise to unseen levels. Since the difficulty is just merely an exponentionnal limitation the time to mine for an quantum computer will only grow linearly up until the maximum difficulty is reached (the maximum difficulty would require an hash of 0....all zeroes hash).

When this time come maybe it will block the chain (or maybe not) because a 0 hash maybe impossible to get, but in anyway massive damage would have been done to the blockchain.

This would happen if the quantum computer is introduced tomorrow, if we have a more progressive approach we can have time to change our algorithm to quantum ones, bitcoin can change his algorithm.

share|improve this answer
1  
The part about mining is pretty much nonsense. A quantum computer with otherwise the same performance as classical computers would be able to find twice as many leading zeros. For mining to fail that quantum computer would need to be comparable to a classical computer that can run 2^128 operations per 10 minute interval, and that won't happen for a long time. For mining the quantum computer is exponentially more powerful than classical computers, but the problem is still exponential for quantum computers. –  CodesInChaos Jan 12 '13 at 14:48
1  
After re-reading your comment, I finally understood it. In my post I merely faced what would be the worst case senario: having a powerful QC on the network. But I am not sure that (and as for now we cannot really know for sure) that the mining problem would still be exponential (but easier of course), we don't know how will QC react to sha-256. In anyway since the ECDSA algorithm would have been broken mining would be be my last problem. –  Gopoi Jan 13 '13 at 1:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.