Bitcoin And Quantum A Roadmap

I felt kind of guilty my last post , so I have spent a bit of time thinking post-quantum Bitcoin. This includes:

I have seen a few people construct lists or summaries of (2), and then point to them like “See! Look at all that’s happening! How could you say that there’s not enough going on?!” This is true, there is something going on. Maybe even, dare I say, LOTS going on. But how much is going on is not really the relevant question. (1) and (3) are the most important parts! What is necessary, but not yet completed, to make Bitcoin PQ-safe? What are the tradeoffs of various options and how do we choose between them? We need to know the gap from here to there : What needs to be done before we can declare Bitcoin secure in the presence of a CRQC, and are we making sufficient progress towards that? 1

In this post, I’m going to argue that we should provide a one-shot way for users to make their coins safe in the presence of a CRQC with minimal tradeoffs. We should do this even if we have not yet resolved all the questions of what to do when a CRQC appears, like how to handle coins that are still not PQ-safe.

I do not think we have to have 100% of the answers immediately, nor can we. There are different mitigations that have different tradeoffs. We should make the low-harm, low-risk, high-benefit, safety-critical mitigations NOW, and save the high-harm, high-risk mitigations for LATER, when we know with more certainty a CRQC is close.

So what should we do now, in my opinion?

If this is done, it gives Bitcoin users the ability to move their coins to a safe output type immediately, having confidence their coins are safe even if a powerful CRQC appears, without worrying future softforks.

The best candidate for this I have seen so far is P2MR (BIP 360) in conjunction with a new PQ signature opcode and cryptographic agility (multiple branches with different signature schemes) . This combination gives us the ability to say: Move your coins to this output type, and as long as you do not reveal your non-PQ-safe public key (do not reuse addresses):

This is great. The downsides are the following:

These downsides, for the ability to say that you can go away and not come back for a long time and your coins are safe in the presence of a CRQC, seem reasonable to me. The efficient privacy loss part is annoying, but maybe we can get it back later once we are all using PQ signatures.

This can help you make your coins secure. What this does not help with is making everyone else’s coins secure if they don’t use it, or use it incorrectly. Since Bitcoin is a monetary system you should probably care this. Most of the argument on the bitcoin-dev mailing list to date seems to be this distinction; namely, there is an argument that if too many other people’s coins are insecure , your coins are insecure.

I am not yet sure how to think this. At the very least I’d say it depends on exact numbers – if only 0.0001% of coins are insecure, I think Bitcoin will be fine. If 20% of coins are insecure, I think things would probably get pretty chaotic if a CRQC would appear, but I’m not totally convinced there isn’t a possible path where Bitcoin might make it through. That said, I think it would be horrible, it wouldn’t really be the Bitcoin we know today, people might lose faith in it entirely, and it’s just way too high risk to bank on. 2 Either way, I don’t know how many coins will remain insecure. Let’s call this percentage X. I think it’s safe to say X > 0 (not all coins will move to PQ-safe outputs), and X 2.9 . If you believe all old P2PK is probably not going to move, X > 8.1 . ↩

Before you yell at me for even considering the idea of turning off ECC (which would freeze Satoshi’s coins if they’re not moved in time), please understand that it is not something I want. Among all the horrible things described in this post, it is one of the most horrible. I am not advocating for it. I would only advocate for it if I was convinced Bitcoin as a whole cannot remain secure in a world where a powerful CRQC-adversary exists and Satoshi’s coins are vulnerable on chain (my current thinking is that this might be the case due to miner incentives for reorgs to battle for the coins. I don’t give a crap dumping a bunch of coins on the market, this is not a good reason and I am pretty sure that’s recoverable. For example, Michael Saylor might go bankrupt and sell tomorrow, and no one is going to make an argument to freeze his coins). So if the option is “no Bitcoin” or “disable ECC (which is to be badly broken) on Bitcoin, with years of warning” I would choose the latter. But I don’t know that’s the choice in front of us to make, yet. Others might have more certainty one way or the other. ↩

Neha Narula narula@gmail.com public key fingerprint: 51EB 6533 48A7 4708 454C C5E9 2C11 CF42 A297 44AC btc: bc1q7jepjq95xcffjka8n5yx4yzuac39z6myp4r4qt