Bitcoin Stack Exchange is a question and answer site for Bitcoin crypto-currency enthusiasts. It only takes a minute to sign up.
Sign up to join this community
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?
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.
Worst case scenario:
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.
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.
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,
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: https://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."
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.
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.
With the current mining difficulty classical computers need to do 2*10^21 SHA256D invocations in average to find a block nonce. A quantum computer would need to do 4.5*10^10 invocations, which is billions times "faster". This means that the answer is: It would be able to doublespend as many times as the quantum adversary wants.
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.
There is a whitepaper of cryptocurrency based on quantum computer implications. http://arxiv.org/abs/1604.01383
So bitcoin could be obsolete to this solution. Yet it is not possible to build this computer and not all problems are fixed as of now.
Quantum computers can do hashing (cf. Quantum Error Correction).
Quantum teleportation will revolutionize the distribution of the blockchain.
Quantum Computer might revolutionize the Bitcoin mining, since the processing power of Quantum Computer is far more better than Traditional Computers.
The reason behind this speed is because of Photons and the Laws of Quantum Mechanics, which are:
So, accordingly, the more processing power we have, the more it would be easy to mine Bitcoins.
