Tell me more ×
Bitcoin Stack Exchange is a question and answer site for Bitcoin crypto-currency enthusiasts. It's 100% free, no registration required.
up vote 4 down vote favorite
1

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

2 Answers

up vote 3 down vote

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
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 at 18:59
Are you saying that elliptic curve point multiplication hasn't been proved difficult? – Janus Troelsen Apr 28 at 11:12
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 at 17:55
up vote -1 down vote

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
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 at 14:48
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 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.