Haseeb Qureshi
1 min readNov 7, 2017

--

This is not entirely correct. The two main quantum algorithms that would affect cryptocurrency security are Grover’s algorithm and Shor’s algorithm.

A modified version of Shor’s algorithm could be used to completely break ECDSA, which is the basis of Bitcoin’s (and Ethereum’s) public-key cryptography. This would be catastrophic, as it means any address that has been used more than once could have its private key compromised (addresses that are only used once would be secure—this was designed intentionally, as a mild way of future-proofing against quantum computers).

As for hashing / PoW, Grover’s algorithm could be used to greatly speed up nonce searches, because Grover’s algorithm can be used to perform a search in O(sqrt(N)) time. So effectively, a search over 2²⁵⁶ possible outputs could be reduced to 2¹²⁸ instead. This would make quantum computers much more efficient at mining than classical ASICs, but the difficulty level of Bitcoin would adjust after a sufficient number of blocks.

So you’d get a different distribution of miner centralization (and ASICs would become much less profitable), but the primary risk to cryptocurrencies would be in breaking the public-key cryptography, not in the PoW. Perhaps only nation-states or large corporations would have their hands on the first quantum computers, but the principles of PoW would remain the same.

--

--

Haseeb Qureshi
Haseeb Qureshi

Written by Haseeb Qureshi

Investor at Dragonfly Capital. Formerly Metastable, @Airbnb, @earndotcom. Writer. Effective Altruist. Former poker pro. One always finds one's burden again.