Cryptographic canaries and backups

Cryptography
1

TLDR: We propose a generic approach to safely deploy cryptographic primitives at the protocol-level. We use canary contracts to detect unsafe primitives, and to automatically deploy safer cryptographic backups.

Background

We want the Ethereum protocol to endure on the order of centuries yet cryptographic primitives break down on the order of decades. One generic approach to address this is “abstraction” where cryptographic choices are pushed away from the protocol layer towards users and the application layer.

Unfortunately cryptographic abstraction has its limits. In some cases we may want the protocol to enforce homogeneity across all participants (e.g. it’s useful for all Merklelised data structures to use the same hash function), and in other cases one particular cryptographic construct has a set of features that makes it uniquely appropriate for a given task, and not making use of that construct could be a wasted opportunity.

The “wasted opportunity” aspect resonates with considerations around quantum security. At this point the quantum era does seem inevitable and many primitives (e.g. ECDSA, RSA, BLS signatures, SNARKs) are known to be “pre-quantum”, i.e. not be post-quantum secure. However, the dawn of the post-quantum era may not happen for another decade, and the next decade in cryptoland is particularly critical. This makes totally avoiding pre-quantum crypto at the protocol-level a potential strategic mistake.

Below are four examples of fancy/safe pairs of primitives where the fancy (pre-quantum) version is genuinely more powerful than the safe (post-quantum) alternative:

  1. Signing: ECDSA has significantly shorter signatures versus Lamport signatures.
  2. Voting: Fork-free voting with BLS signatures finalises significantly faster than forkful voting.
  3. Random beacons: Dfinity-style random beacons provide significantly better randomness versus blockhashes or a RANDAO approach.
  4. Verification: SNARK-based verification is significantly faster than execution-based verification.

The construction below uses cryptographic canaries and backups to simultaneously leverage the power of fancy primitives and the safety of safe primitives.

Construction

For every fancy primitive we want to use in-protocol we construct a canary contract with an associated large bounty. My guess is that 50,000 ETH is large enough. Such an amount can be subsidised by the protocol through inflation (0.05% inflation of the total supply is a small price to pay), or could be funded by donations from the community (I’d put 1 ETH :slightly_smiling_face:) and the foundation.

Anyone can redeem the bounty by producing a “proof of cryptographic threat”. The canary can be very specific, e.g. only target BLS signatures. In this case the proof could be a BLS signature matching a nothing-up-my-leave public key (e.g. the binary serialisation of "Come at me, bro"). Alternatively the canary can be more general, e.g. target all pre-quantum crypto, where the proof would be a proof of quantum supremacy. A hash-based hiding commitment scheme is used (SHA3 is thought to be post-quantum secure).

We want the canary to be triggered before any production crypto is at risk. For that the canary puzzle needs to be made easy enough that only the threat of a breakdown is displayed, not an actual complete breakdown. For example the puzzle in a post-quantum canary would be hard enough for no classical computer to stand a chance, but easy enough for a reasonably-low-qbit quantum computer to crack.

We now pair every fancy protocol-layer mechanism with a safe backup. The backup remains dormant until the canary is triggered. At that point all fancy operations are automatically and immediately shut down, and the safe backup takes over. This applies to system contracts (e.g. the VMC and the FFG contract) as well as to clients for offchain protocol rules (e.g. fork choice rules). Even application-layer contracts can listen to the canary and have their own contingency plan.

8 Likes
In favor of forkfulness
A soundness alert function for zk-rollups
2

I totally agree and would like to offer two little tweaks :slight_smile:

  1. make bounties gradual (start with a particular strength say X bits and pay bounty each time the next bit of strength is cracked)

With RSA challenge the problem was that large organizations that had lots of parallel computational power had huge advantage against independent researchers.

  1. Restrict the challenge to a single-threaded algorithm running on a single core that cracks the bounty so that all you need is a PC. The cracked strength will be much smaller but it is does not matter so much. Arguably if you can crack a weaker problem and show the scaling law, you can easily extrapolate to the stronger problem.

What you want to do is to have many independent researchers working on this thing.

The question is how to enforce the single-threaded property … May be you simply create a group of crypto researchers to attest to the fact that the canary was cracked on a single core

3

This is a fun idea :stuck_out_tongue:. It reminds me of this IC3 paper; essentially, create bug bounties that give people incentive to claim the bug bounty rather than exploit it (and hopefully safely recover from this as well).

That being said, I’m not sure this is totally practical. I think the benefit one would get from hiding their quantum computer and then breaking everything is much greater than they would get from any amount of ETH we might put in a bounty (if they’re evil). And if they aren’t hiding their work, then there really isn’t a need to make this happen automatically.

Also, having the “canary […] be triggered before any production crypto is at risk” seems like a hard problem. It requires us to judge how for the canary breaking is from the quantum computer that breaks everything else. We’d probably have to be very conservative here, in which case let’s just be conservative in a manual manner and not pay a bounty.

1 Like
4

I think it is more to stimulate incremental progress in math …

As far a quantum computers go they are totally impractical - I guess the reason why CS people like talking about quantum computers is because they never took quantum mechanics :slight_smile:

The amount of quantum coherence required by a quantum computer raises exponentially with the number of bits. Amazing that government still funds these things :slight_smile:

The real quantum computer is called a semiconductor transistor since electrons in it have a quantum gap. The reason why semiconductors semi-conduct is because of quantum interference. We all already use quantum computers :slight_smile:

1 Like
5

The quantum race is led by established companies (IBM, Intel, Microsoft, Google), startups (Rigetti, IonQ, Quantum Circuits) and possibly governments (NSA, GCHQ). It seems unlikely an established company like IBM would hide their quantum computer for the purpose of breaking everything. As for startups, they are also commercial entities and claiming the “official” Ethereum bounty would be huge PR coup, and a rare “legit” opportunity to claim a significant amount of cash from breaking crypto.

This leaves us with governments… It’s possible that Ethereum will have enough global systemic importance by the time quantum computers are real that they will want to break Ethereum. But then Ethereum seems like a much less likely target than something like, say, military and financial secrets.

1 Like
6

We used this proposal’s main idea to resolve aspects related to (what we call) “quantum procrastinators”: users that would not switch to post-quantum addresses in time, in the context of cryptocurrencies. The eprint is available here: Protecting Quantum Procrastinators with Signature Lifting: A Case Study in Cryptocurrencies .

At this time, the manuscript wasn’t peer-reviewed. Comments are welcome.

1 Like
7

We also learned that Peter Todd implemented roughly this idea specifically to detect a collision for several hash functions in 2013, see here.

1 Like
8

It suggests pairing powerful pre-quantum primitives with safe backups. This approach ensures security while preparing for potential quantum risks. It’s a well-thought-out strategy for navigating cryptographic choices in a changing landscape. Nice

1 Like
9

Eight years later: the canary problem is still an incentive problem

Coming back to this eight years later because I ran into the same wall you and Nate were circling in the 2018 replies, but from a different angle.

I’ve been working on a mechanism, Geminis, where a chain can switch its own ruleset — including its signing primitive — when an on-chain trigger condition is met, without a vote or hard fork.

Structurally, it is close to what you propose here: a canary followed by an automatic switch to a pre-wired backup. But instead of putting a bounty on the deployed primitive, the canary is a deliberately weakened instance from the same primitive family, derived from a public seed. Nobody generates the instance, so nobody can privately hold the exploit. There is also nothing valuable behind that specific instance.

That addresses the specific problem nate raised with the bounty model:

Why would someone who can break the real primitive claim the reward instead of quietly draining accounts?

But I don’t think it closes the underlying problem. It relocates it.

The canary can tell you that the primitive family is weakening. It cannot guarantee that the real deployed instance will break on the same timeline as the deliberately weakened one.

I ended up writing this down formally because I think this distinction is worth being precise about.

A complete break is fundamentally different from a partial break. If an attacker can recover the secret key, their resulting signatures are not distinguishable from legitimate signatures: they are using the same signing relation as the legitimate signer. There is no second observable process that a bounty or penalty can condition on.

In incentive terms, this looks like a hidden-action problem with an unobservable type, in the same general family as moral hazard.

A partial break is different. Statistical biases or progressively cheaper attacks — the kind of pattern we saw with DES, MD5, and SHA-1 — can produce observable evidence before the primitive is completely compromised.

A complete break, by definition, removes much of that observability. And I think this limitation applies to the bounty construction as well, not only to my canary approach.

Where I think both mechanisms can still get useful signal is in how the canary is chosen.

Rather than selecting the most obscure candidate, choose the primitive that has received the most serious public cryptanalysis. Rainbow and SIKE are useful reminders here: both were serious NIST PQC candidates with substantial public scrutiny, yet both were broken completely in 2022 by attacks practical enough to run on a laptop.

Public scrutiny is not proof of security, obviously. But it may be one of the few external signals available for the proposition we’re actually trying to test: has someone already tried seriously to break this?

I also measured a complementary mitigation rather than assuming it was worthwhile: a composite signature combining lattice-based ML-DSA-44 with hash-based SLH-DSA-128s, with no shared cryptographic core.

My preliminary desktop measurement, across three execution engines, puts composite verification at roughly 4.2× the cost of a single verification, rather than the ~10× one might naively expect from adding native benchmark numbers. The reason is that the two primitives favor different execution engines.

I haven’t run the phone measurement yet, and this result alone doesn’t establish that the composite construction is worth adopting. That would depend on a velocity threshold I haven’t measured yet.

Full writeup and measurement code:

I’d be interested in your current view of the original proposal: do you still think the bounty is the right incentive lever, or does this framing of the complete-break case change how you see the problem seven years later?