4 ms·
Ask HN: What Kind of Threat Does Quantum Computing Pose to Bitcoin?
My understanding of quantum computing and what it can do is popular mechanics level at best. I have heard people dismiss bitcoin as inevitably insecure "because of quantum computing" and, conversely, I've heard people dismiss quantum computing as hype, the reality of which lies too far in the future to worry about.
Is the concern simply, "we don't know how this could change the computing landscape," or is something more like "quantum computing promises to calculate primes in O(1) time, rendering keypairs worthless"?
And how far out are we realistically?
- therealmarv 6y agoNone, unless somebody (China?) surprises us a with a working one specifically on the bitcoin blockchain. Quantum resistance blockchain architecture is in the works or even available in theory and if the danger is real Bitcoin can be forked/modified to be quantum resistant. Because community would most probably be okay with this switch it would be accepted world wide.
- BelenusMordred 6y agoSHA2 hashing which secures the chain itself faces no known threats from quantum-computing. ECDSA wallet signatures can easily be broken with a sufficiently sized QC and now are essentially a billion dollar bounty on whether a country or corp has gotten there. Switching over to post-quantum signatures is a simple matter but the coins will have to be moved to secure them. So, someone with access to such a computer can learn the private key for any wallet on the planet and steal the contents, but they can't magically mine with 100% hashpower or undo history and all prior tx's.
- tromp 6y agoThe hashcash proof-of-work scheme that bitcoin uses is vulnerable to Grover's quantum search algorithm, that can find a solution in the 2^76 search space for the current target difficulty in roughly sqrt(2^76) = 2^38 quantum hashing steps, for a 2^38 factor speedup. Other proof-of-work schemes (e.g. finding cycles in graphs [1]) are not vulnerable to quantum speedup. [1] https://github.com/tromp/cuckoo https://github.com/tromp/cuckoo
- alwillis 6y agoThis means that as long as funds have never been transferred from a p2pkh address, the public key is not known and the private key cannot be derived using a quantum computer. Some address types are already quantum-resistant. Of course the addresses that are just public keys (not hashed public keys) are vulnerable. From https://www2.deloitte.com/nl/nl/pages/innovatie/artikelen/quantum-computers-and-the-bitcoin-blockchain.html https://www2.deloitte.com/nl/nl/pages/innovatie/artikelen/qu...
- jcuenod 6y agoThanks; this looks on point.
- cozzyd 6y agoThat's half of what that article (which is excellent!) says. Presumably those unused addresses are lost and would lead to some devaluation but not that much. The harder to understand half is that if a quantum computer can break the public key before the transaction is verified (which takes some time, by design) then that's also game over, although it's not clear if that's possible or not.