Key Revocation in Self-Certifying Protocols

In Web3 protocols cryptographic keys are used for encryption and signature verification. Typically a key is split into a public and a private key and because private keys are hard to keep secure, it is considered good practice to change keys over time. This is commonly referred to as key rotation or revocation. Building protocols for doing so securely can be a challenge. In this article you will learn about the nuances of key revocation and how we approach the problem with Ceramic.

Double Spending and Key Rotation

The challenge of safely performing key rotations in Web3 data protocols has similar characteristics as the classical double spending problem. Blockchains solve this problem for financial application using a strong consistency model. Can we loosen these constraints for non-financial applications while maintaining the safety of key rotations?

Double-spending is a potential flaw in a digital cash scheme in which the same single digital token can be spent more than once.

A quite similar problem also arises when you simply want to perform a key rotation. A critical aspect of any protocol that involves cryptographic key material is how to manage the lifecycle of these keys. For HTTPS, which is used to secure the web today, centralized certificate authorities verify if a given key is valid or not.

In Web3, by definition, self-certifying protocols can’t rely on third party centralized authorities since authority comes from the user directly. This presents new challenges when designing the lifecycle of a cryptographic key. How can you know if a key has been revoked and should no longer be considered valid without trusting a third party authority?

In order to understand this more deeply, let’s start with some basic definitions:

Key revocation - a function in the lifecycle of a cryptographic key; the point in time where proofs generated from the key are no longer considered valid.

Key rotation - Changing the key, i.e., replacing it by a new key. Typically this means that the old key would be considered revoked when the new key becomes active.

Based on this we can see that there are two main things we need to consider in the lifecycle of a cryptographic key. When proofs generated by a given key (e.g. a signature) starts being valid and when they stop being valid. Let’s suppose Alice wants to generate a cryptographic identifier that is not tied to a specific cryptographic key. Instead she wants to be able to update the key which is associated with her identifier over time, i.e. she wants to be able to perform key rotations. A simple scheme for this would be to sign the new key with the old key and dispose of the old key. However, this could present a problem if the old key is not properly disposed of. Consider the following diagram:

We know by definition Public key (pk) A is authoritative. Alice rotates from pk A to pk B by signing pk B using key A. Now, if Carol is able to steal key A at some point after the rotation happened, she could establish a rotation to pk C. An outside observer Bob who learns of both pk B and pk C has no way of knowing which key to trust. This is because there is no information about when the rotations happened.

As you can see this is very similar to the double-spending problem: pk A should only be allowed to be spent (i.e. rotated) once. Blockchains solve this problem by introducing a hash linked ledger where all events in the system are notarized in one universal ordering, which is economically infeasible to reverse. This is critical for financial applications. However, it means that all nodes in the network need to process all events in order to uphold invariants on account balances. The Ethereum community has discovered that this problem can be somewhat circumvented by leveraging data availability sampling and rollups, but these systems are still ultimately bottlenecked by the need of logical centralization. If our goal is merely self-certified authority of data and not the security of financial transactions, could we loosen the constraints a bit to get around this bottleneck?

Blockchains as timestamp machines

Because blockchains deal with financial transactions they have to favor strong consistency since rollback of transactions would be detrimental to the system. However, many large scale distributed system today rely on eventual consistency in order to provide timely updates and processing of events. Consider our key rotation example from above. Our main goal is to establish that the key rotation that happened at the earliest point in time should be the valid rotation. If we rely on eventual consistency we could imagine Bob first seeing the rotation to pk C which happened at time N+2, and only later learning about the rotation to pk B which happened at time N+1.

This means that as long as Alice is able to prove that her key rotation happened before Carol’s key rotation, Bob will eventually learn about this (e.g. through some p2p gossip, network architecture is out of scope for this article). An interesting consideration here is that Alice herself could create two key rotations. The first one she keeps secret and the second one she makes public. At some later point in time she could reveal the secret rotation, invalidating all signatures created by the latter key. In a financial type application this would be very problematic since it would enable double spends. However, from the perspective of a self-certifying data protocol Alice would only be revoking her own data that was signed by the second key. In many cases this would only damage herself. For example, if she has built up a strong reputation over time and revokes this data her reputation would be lost. Note that care should be taken if there is a system that produces on-chain decisions based on Alice’s data. Protocols that do this might want to introduce data availability checks at the point of decision and potential cryptoeconomic penalties for cheating.

So how can we timestamp these events without putting them through the expensive logical centralization of a blockchain? First let’s consider why this logical centralization is expensive. In order to solve the double spend problem, a blockchain fulfills two properties to prevent double spends: data ordering and “proof of non-publication”. The latter is very expensive since it requires all nodes to agree on all data (e.g. transactions) included throughout the history of the blockchain. In an eventual consistent system we only need ordering, which is less expensive. It is fairly straight forward to timestamp data leveraging a blockchain without putting all of the data on-chain: (1) gather events (e.g. pieces of data, transactions) off-chain, (2) use these events to build a merkle tree (or any sort of vector commitment), and (3) make a transaction on-chain which includes the root of the tree. If Bob is now presented with an event and a merkle witness of on-chain inclusion he can trustlessly verify the timestamp of this event as long as he is at least running a light client of the given blockchain.

Key revocation in Ceramic

In Ceramic the timestamp proofs described above are called anchors, i.e. an anchor is a merkle witness that proves that a certain event existed at time N. Shown in the diagram below is a simplified example of a data structure on Ceramic where Alice produces data and rotates her key. Here, N+X refers to the wall clock time as observed in the block on which the anchor transaction was included (block number could also be used). If Bob first observes event A, B, E, and F, he would consider all of these valid. When he eventually learns of event C and D he would dismiss event E and F.

These anchors are also useful if a key has temporary authorization to write to some data structure. For example, when granting temporary write access to a session key, its authorization should automatically be revoked at some point in the future. By using an anchor we can prove that a particular event produced by a session key happened before this session keys authorization was expired. A concrete example of this is CACAO which is an example of an Object Capability. CACAO can be used to grant a specific public key temporary access to some specified resources, which is useful if we want to build a granular access control system. Consider the example below, where a CACAO is issued from Alice (the controller) to Bob:

The CACAO has an expiry date equal to N+2. Any outside observer can easily verify that the signature for Event B was produced before time N+2 because the timestamp from the anchor proves this. However, after time N+2 has passed it would be impossible for Bob to produce an anchor of Event C earlier then time N+2. The CACAO has thus been effectively revoked.

This article outlined how the strict ordering of blockchains can be paired with a more flexible approach to data availability, enabling eventually consistent protocols that are self-certifying. Ceramic utilizes this approach to create an ecosystem of composable data.

Thanks to everyone who provided feedback on this post: Christian Lundkvist, Brooklyn Zelenka, Carson Farmer, Irakli Gozalishvili, Oliver Terbu, Robert Drost, Adin Schmahmann, and Mircea Nistor.