It might be worth me sharing this again, a summary of how QCs can affect bitcoin:
Mining can potentially be much quicker with QCs.The current PoW difficulty system can be exploited by a Quantum Computer using
Grover’s algorithm to drastically reduce the number of computational steps required to solve the problem. The theorised advantage that a quantum computer (or parallelised QCs) have over classical computers is a couple of orders of magnitude, so ~x100 easier to mine. This isn’t necessarily a game-changer, as this QC speed advantage is likely to be some years away, by which time classical computers will surely have increased speed to reduce the QC advantage significantly. It is worth remembering that QCs aren’t going up against run-of-the-mill standard equipment here, but rather against the very fast ASICs that have been set up specifically for mining.
Re-used BTC addresses are 100% vulnerable to QCs.Address Re-Use. Simply, any address that is re-used is 100% vulnerable because a QC can use
Shor’s algorithm to break public-key cryptography. This is a quantum algorithm designed specifically to solve for prime factors. As with Grover’s algorithm, the key is in dramatically reducing the number of computational steps required to solve the problem. The upshot is that for any known public key, a QC can use Shor’s approach to derive the private key. The vulnerability cannot be overstated here.
Any re-used address is utterly insecure.Processed (accepted) transactions are theoretically somewhat vulnerable to QCs.Theoretically possible because the QC can derive private keys from used addresses. In practice however processed transactions are likely to be quite secure as QCs would need to out-hash the network to double spend.
Unprocessed (pending) transactions are extremely vulnerable to QCs.As above, a QC can derive a private key from a public key. So for any unprocessed transaction, a QC attacker can obtain the private key and then create their own transaction whilst offering a much higher fee, so that the attacker’s transaction gets onto the blockchain first, ahead of the genuine transaction. So block interval and QC speed are both crucial here – it all depends on whether or not the a QC can hack the key more quickly than the block is processed.
Possible defences...
Defences using classical computers.- Modify the PoW system such that QCs don’t have any advantage over classical computers. Defending PoW is not as important as defending signatures (as above), because PoW is less vulnerable. However various approaches that can protect PoW against QCs are under development, such as Cuckoo Cycle, Momentum and Equihash.
- Modify the signature system to prevent easy derivation of private keys. Again, various approaches are under development, which use some pretty esoteric maths. There are hash-based approaches such as XMSS and SPHINCS, but more promising (as far as I can tell) are the lattice-based approaches such as Dilithium, which I think is already used by Komodo.
Defences using quantum computers.As I’ve said a few times, I’m more of a bumbling enthusiast than an expert, but exploiting quantum properties to defend against QC attack seems to me a very good idea. In theory properties such as
entanglement and the
uncertainty principle can offer an unbreakable defence. Again, people are busy researching this area. There are some quite astonishing ideas out there, such as
this one.
... but apart from all of this, migrating bitcoin to a quantum-proof system brings its own challenges. Coins will only be safe once they have been moved to new, quantum-proof addresses. What happens to those coins that aren't moved? They would remain vulnerable, and could still be stolen using a QC. Should these be burned to prevent theft, or should the theft be permitted? This is an important question with no obvious consensus on how it should be resolved. Potentially millions of coins would be vulnerable. Theft could tank the price and damage bitcoin irreparably, but burning 'someone else's' coins could do the same thing.
Theymos brought this subject up years ago, and as far as I'm aware it is still a contentious issue.
