How vulnerable is bitcoin to quantum algorithms? [duplicate]

Question

Assuming that quantum computers are implemented some time in the near-ish future, how vulnerable is Bitcoin to decryption via quantum algorithms? For example, Shor's algorithm enables a quantum computer to prime factorize in polynomial time. A variant of it can crack ECDSA.

However, Bitcoin relies on a scripting system, so if quantum computers are created, one probably can just switch to a secure script¹

Is Bitcoin vulnerable to attacks from quantum computers? Are these vulnerabilities fixable²?

^{1. Then again, there are limits to scripting and quantum computing may make it impossible for any script to work.}

^{2. "Fixable" can both be client-side fixable, where everyone just tweaks the script they use and transfers all their money to a clean set of addresses (thus securing all their bitcoins with the new script), or protocol-side fixable, where the protocol is tweaked and everyone downloads a new client. The latter is nor preferable, since the old bitcoins will probably be lost in the process.}

Answer 1

In short, yes, Bitcoin would be vulnerable to some variation of Shor's algorithm and quantum computing, as would basically every kind of crypto we use today. While ECDSA uses the elliptic curve discrete logarithm problem for its security, rather than the prime number factorization problem, you are correct in stating that a variant of Shor's can be used to solve the ECDLP in similar time. I believe there are similar threats with regard to SHA256, which is heavily used in Bitcoin's mining process.

You are also correct in stating that Bitcoin relies on a scripting system and is itself an open-source distributed computing project. Assuming you can arrive at a network consensus it is absolutely possible to change basically any aspect of Bitcoin - you just have to get the whole rest of the network to agree with you. I don't imagine that would be an issue if ECDSA or SHA256 were broken.

It's also entirely possible that the whole project itself could be forked to create an alternate version of Bitcoin similar to others which already exist. There is a variant called Litecoin, for example, which uses scrypt instead of SHA256 for mining - implementing an alternative to ECDSA could be easily done in a similar manner.

This, perhaps, is the true brilliance of Bitcoin: it's a Pandora's box that cannot be un-opened. Bitcoin as it exists today may or may not exist in a decade. Perhaps there is some unforeseen flaw that will soon be discovered, but that flaw will be fixed and the idea will live on. Assuming that there is any reasonable encryption/signing algorithm that is safe from quantum computing, it will be adopted and the cryptocurrency world will move on.

Answer 2

Crypto currencies such as bitcoin will always be a step ahead.

Post-quantum Cryptography is already being researched to combat quantum computers before they have even evolved enough to be considered a threat.