6

An interesting question was posted recently, discussing the idea of hashed addresses being (not meaningfully) quantum resistant.

As Andrew's answer on that question points out, paying to a hashed address does not 'quantum-proof' your coins, however there is a mention of using a zero-knowledge proof of a BIP32 seed to recover coins safely, against the threat of a quantum computer capable of breaking the elliptic curve discrete logarithm problem (ECDLP).

If this is possible, then clearly there are advantages to more complex constructions for addresses (the BIP32 key-derivation function being apparently more quantum-proof, in this case).

So my question is: what address constructions are known to provide some level of safety from a quantum computer defeating the ECDLP? How is this safety provided? How can a user create addresses today, to allow themselves the best chance of having their Bitcoin-wealth survive a highly capable quantum computer?

Note that this question is meant to explore what a user can do now to mitigate the risk of the 'worst-case-scenario' of ECDLP being broken suddenly and unexpectedly soon; with time to plan there are obviously less scary ways to switch to a quantum-secure algorithm.

EDIT: for the sake of this question, lets assume that users have unanimously agreed to fork the chain from a certain block that was mined before the quantum-computer attack began, and the fork will lock all coins that are easily stolen by the QC (P2PK outputs, reused addresses, etc). Consider the case in which every bitcoin is stored at an address which will allow safe recovery, suddenly the potential damage to the network is lessened greatly. Even if this is unlikely, I think it is academically interesting.

Improve this question
5

We're deep in speculative territory here but, theoretically, if the elliptic curve algorithm were broken the entire Bitcoin system would immediately collapse.

Let's consider the case where you've successfully guarded your own funds somehow. How many public keys would still be out there vulnerable to such an attack?

Even though your "base" survived the attack, every other user out there who had UTXO on reused addresses would've been nuked and Bitcoin would have collapsed. You'd be the exceptional survivor. It'd be all over the news, dollar value would've gone to near zero, miners would stop and cut losses and so on.

So, in my view, there is no way to protect yourself individually against the eventual breakage of the elliptic curve discrete logarithm problem. Even if 90% of Bitcoin users had unspent UTXO's in safe unused addresses, the 10% that were hacked would cause immense damage to Bitcoin in a social sense.

Since Bitcoin obeys Metcalfe's law, network value being number of users squared, if enough users dropped out of the ecosystem, due to this kind of development in cryptanalysis, it'd surely deal a major blow to the community.

Not to mention another possibility: such a quantum computer could try brute forcing astronomic quantities of random numbers into private keys all day. Eventually they'd stumble on valuable wallets which could cause the community upheaval of "having broken Bitcoin" and its consequences. So having a known public key wouldn't necessarily be the only attack vector. I'm sure there are other possible attacks using quantum computing, perhaps unknown unknowns that would add immense risk to the system.

Math is the Bitcoin guardian, if it's somehow found to be vulnerable no man would be left standing in my opinion.

Improve this answer
  • I agree with everything you wrote, but this didn't provide an answer to the actual question: how can a user create an address, such that they will be able to safely recover coins in a post-QC world? For the sake of the question, lets imagine that users have all agreed upon a certain pre-QC block that they will fork from, so vulnerable funds have not been stolen / all network value destroyed. Perhaps this situation is unlikely, but this question is still interesting from an academic perspective. – chytrik Oct 17 '19 at 20:11
  • @chytrik It's a nice theoretical question. I don't think there's a way to do anything after QC has broken the system. In a scenario where QC has already broken ECDLP it'd be catastrophic. Of course Core developers won't let it happen, unless something truly revolutionary happens in the near future. – Jose Fonseca Oct 17 '19 at 20:28
  • If the onset of the attack was obvious (example, at block X we see every single P2PK UTXO consumed to create a single UTXO), then rolling back to a pre-attack block and forking the network to add safeguards against the QC is possible. I'm really just interested in hearing more about what sort of ideas there are to recover coins safely on this forked chain, such as the BIP32 seed ZKP Andrew mentioned. Evidently there is math that holds up against a QC attack, so how can users employ this math to their advantage, today? I do assume an unexpected QC will cause huge damage, in any case. – chytrik Oct 17 '19 at 20:39
  • @chytrik I understand that you want to look at specific cryptographic technologies to be deployed at that scenario. Fine, but what I mean is this scenario would be unsolvable in practice. It's like debating what you'd do about the swimming pool water after a nuclear attack. Let's assume we're at the point where it's been decided to roll back to a pre-attack block, everything else ceter paribus. This is where my answer above kicks in: all those UTXO's pre-fork are vulnerable. Whatever you derive from the keys, to save those keys, is already broken! – Jose Fonseca Oct 17 '19 at 21:38
  • @chytrik So let's say you find a cryptographic solution to convert all those pubkeys to the new system. The attacker also has this data available to him. So post-mortem there is no way to recover this blockchain, it's gone. – Jose Fonseca Oct 17 '19 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.