Post
Topic
Board Development & Technical Discussion
Re: Can quantum computers kill Bitcoin?
by
achow101
on 15/10/2016, 14:21:32 UTC
Quantum Computers are not any faster at hashing than classical computers.

You are very wrong.

From Section 4.3 of https://www.iotatoken.com/IOTA_Whitepaper.pdf:
Quote
It is known that a (today still hypothetical) sufficiently large quantum computer can
be very efficient for handling problems where only way to solve it is to guess answers
repeatedly and check them. The process of finding a nonce in order to generate a
Bitcoin block is a good example of such a problem. As of today, in average one must
check around 2^68 nonces to find a suitable hash that allows to generate a block. It
is known (see e.g. [Gilles Brassard, Peter Hyer, Alain Tapp (1998) Quantum cryptanalysis
of hash and claw-free functions. Lecture Notes in Computer Science 1380, 163–
169.]) that a quantum computer would need Θ(√N) operations to
solve a problem of the above sort that needs Θ(N) operations on a classical computer.
Therefore, a quantum computer would be around √2^68 = 2^34 ≈ 17 billion times more
efficient in Bitcoin mining than a classical one. Also, it is worth noting that if
blockchain does not increase its difficulty in response to increased hashing power,
that would lead to increased rate of orphaned blocks.
Interesting, did not know that.

Even so, QCs cannot do preimage attacks on hashes, they can only brute force them faster. For mining, that just means that the difficulty will increase and blocks will stay the same. For addresses, that means that they still cannot find the associated public key because they still can't find the preimage.