Cryptographic agilityCryptographic agility

In early February, Ethan Heilman wrote an interesting post on the Bitcoin Mailing List about "cryptographic agility." Heilman describes this concept by quoting from an industry standard:

Protocol designers need to assume that advances in computing power or advances in cryptoanalytic techniques will eventually make any algorithm obsolete. For this reason, protocols need mechanisms to migrate from one algorithm suite to another over time.

Algorithm agility is achieved when a protocol can easily migrate from one algorithm suite to another more desirable one, over time.

When you use bitcoin, you are mostly using two cryptographic algorithms: secp256k1 and SHA-256. If you are not just using taproot addresses, but are using segwit or legacy addresses, you also rely on RIPEMD-160.

Conceivably, there are other algorithms we could use in bitcoin that would work more or less as well as the ones that Satoshi chose. Indeed, Satoshi said in an email to Mike Hearn that "I didn't find anything to recommend a curve type so I just... picked one."

But cryptographic agility refers to the ability of a system like Bitcoin to switch to a different algorithm in the event that we are worried that secp256k1 is going to be compromised -- for example, in the case of advances in quantum computing.

It's hard to change the lock on buried treasureIt's hard to change the lock on buried treasure

Heilman goes on to point out that

Bitcoin should enable a person to self-custody coins for at least one human lifetime, ~75 years. Someone should be able to bury an HD Seed in a coffee can and then dig it up in 75 years and spend those coins.

and that

The main risk I will be considering here is the loss of the ability to authenticate ownership of coins resulting from a break in a digital signature algorithm used by Bitcoin. Such risks are extremely unlikely in the short term (1 to 5 years), but become more likely on 5 to 75 year timescales. Most of the focus in the wider cryptocurrency world has been on mitigating the quantum threat, but I take a less narrow view of the problem. We should consider not just Quantum attacks on Bitcoin’s signature algorithms and also classical breaks that do not require a quantum computer.

If you put your coins in cold storage and the secp256k1 algorithm is broken, your coins aren't in cold storage anymore. So: Bitcoiners need to be thinking about cryptographic agility.

The Nic Carter PhenomenonThe Nic Carter Phenomenon

In a separate thread on the Bitcoin Mailing List, Pieter Wuille took a step back from the very detailed discussion about different cryptographic algorithms in Heilman's thread, and raised a broader issue:

The idea is giving users/wallets the ability to choose the cryptographic primitives used to protect their own coins, from a set of available primitives that may change over time. I think this ignores how important it is what others do with their coins. If others' coins lose value, for example due to fears about them becoming vulnerable to theft with cryptographic breakthroughs, so do your own due to fungibility, regardless of how well protected they are.

Wuille then proposes a thought experiment that tries to get at what he means:

As an extreme thought-experiment, imagine that tomorrow a new cryptographic signature scheme FancySig is published, with all the features that Bitcoin relies on today: small signatures, fast to verify, presumed post-quantum, BIP32-like derivation, taproot-like tweaking, multisignatures, thresholds, ... Further assume that within the next year or two, voices (A) start appearing arguing that such a scheme should be adopted, because it's the silver bullet the ecosystem has been waiting for. At the same time, another camp (B) may appear cautioning against this, because the scheme is new, hasn't stood the test of time, and isn't well-analyzed. These two camps may find themselves in a fundamental disagreement:

• Camp (A), fearing an EC-break (CRQC or otherwise), wouldn't just want FancySig as an option - they would want (feasible or not) that near-everyone migrates to it, because the prospect of millions of BTC in EC-vulnerable coins threatens their own hodling.
• Camp (B), fearing the possibility that FancySig gets broken soon, possibly even classically, don't want to just not use FancySig; they would want near-nobody to migrate to it, because the prospect of a potential break of FancySig threatens their own hodling.

Wuille speculates about the level at which enough users relying on a algorithm you are convinced will soon be vulnerable would cause you to abandon the coin. This may sound dramatic, but imagine that you are Nic Carter and super convinced that a quantum computer that can derive private keys from bitcoin public keys is going to be here next year. If only 2 million bitcoins have moved to quantum safe addresses and everybody else refuses to believe your dire warnings of quantum wolves, would you really feel comfortable holding bitcoin?

In the end, Wuille implies that bitcoin probably works best when everybody relies on the same cryptographic algorithms, but also that this is a pretty hard thing to achieve if it's not what you started with.

Focus on good engineering and let the psychology take care of itselfFocus on good engineering and let the psychology take care of itself

Some of how Wuille worded his initial post is confusing, but my takeaway is this idea that Wuille put in bold:

despite being a currency for enemies, Bitcoin essentially requires users to share trust assumptions in the cryptography, and its technology in general.

He uses the above examples to make the case that if other Bitcoin users rely on weak cryptography, it could harm you even if you only rely on robust cryptography.

waxwing has a very nice reply to Wuille where he says:

The fact that other coins are held in an insecure way is in no way a threat to my security. As you point out with e.g. OP_TRUE there is zero ability to prevent people doing this.

Suppose X% of the supply is held by negligent holders. Over time that X% will move away from those negligent holders to "thieves" (scare quotes because if literally held in outputs for which the unlocking script is publically derivable, it's debatable whether it's theft, even). The thieves will either be negligent themselves or not; in any case, over time, the coins will move to holders who are not negligent.

This feels very much like a code is law argument and in my naievte I am sympathetic to this (I guess this means I come down on the thieves' side of the burn or steal debate). But waxwing goes on to point out that

every honest action of moving to safety looks identical, onchain, to theft.

Waxwing advises that Bitcoiners focus on good engineering and let the concerns about quantum procrastinators sort themselves out:

This is a big mess, but my reason for framing as in the previous paragraph is to try to argue that that mess is 100% unavoidable even with the most prudent behaviour and the most brilliant engineering. I am saying this to argue against the idea that engineering decisions should take this psychological effect, as you put it, into account. I have an intuition that trying to address that will create bad outcomes.

Waxwing ends with this summary, which I found particularly helpful:

The only thing that the system as a whole has to promise is that there exists a safe, practical way to keep possession (and also users should not have to just "guess" which methods are secure!). The system is not required, nor can it, to prevent people choosing insecure storage methods, against the technical advice.

I'm no cryptographer, but I do find this kind of conversation fascinating:

• no cryptographic algorithm will work forever
• it is probably best if all of Bitcoin relies on the same algorithms
• the best system is durable to people using it wrong