How KERI tackles the problem of trust

The problem of trust over a network is longstanding. It has been addressed in a variety of ways since the internet blossomed, but never as yet solved.

Take, for example, Certificate Authorities (CAs), the organizations with the power to issue certificates to websites so browsers will recognize them as legitimate. These certificates function as a primitive identification for websites, where the CA is attesting to the identity of the website and the website can use this certificate to identify itself to browsers – because all browsers trust the CAs.

The flaw here though is obvious: what if a CA is compromised and begins issuing false certificates? No set of keys can be considered absolutely immune to compromise, no matter how powerful the controller.

The central problem here is that of trustless key distribution and attribution (more specifically, the implementation of a Distributed Key Management System (DKMS). That is, how do we know that a key is truly controlled by an identifier and, given an identifier, how can we know which keys it controls? (It’s important to note here that CAs are not trustless mechanisms, but that browsers rely entirely on trusting that a CA has not been compromised.)

Decentralized digital identity using the technology of Decentralized Identifiers (DIDs) appears to remedy the issue. However, this collection of related specifications only defines a consistent interface for different DID methods to implement a DKMS in any way they see fit, as well as associated semantics to make them very flexible and useful.

The exact way that key distribution and attribution is addressed is different between DID methods. Distributed ledger technologies (DLTs) and blockchains have proven effective for the purposes of designing decentralized DID methods and even centralized trust-requiring systems, such as GitHub or Twitter, have been used.

Most DID methods are still fairly young, but they often share certain characteristics:

• Central registry-based: the infrastructure might be decentralized (e.g. a blockchain or other DLT), however the DID method is informationally centralized, i.e. registration and resolution involve the updating or reading of the shared state of a single network or infrastructure.
• Canonicity: the central registry is considered to be the single trustworthy source of truth.
• Availability provision: the central registry’s entire state can be queried at any time from anywhere (with a network connection).

The logical centralization of these kinds of methods provides an important, arguably more fundamental property: conflict resolution. The underlying consensus mechanism of these DID method implementations (e.g. the Bitcoin blockchain for did:btcr or the Ethereum blockchain for did:ethr) prevents any conflicting states from being propagated on the network. And if this sounds similar to a cryptocurrency, that’s because it is.

Blockchain consensus mechanisms were and are designed to maintain some kind of invariant about the current state of the chain. In Bitcoin and other currency chains, this invariant is the amount of existing coins: the mechanism is designed to solve the double-spend problem. It seemingly makes sense, then, to use this property of blockchains for identity. Or does it?

Interestingly, it actually does not. The invariant of single-spend leads to slow consensus time because it must be applied to the globally-shared state of the chain. In identity, however, we do not have a double-spend problem.

The invariant we care about in identity is different. It is only that an update to the state of the keys and other metadata associated with an identifier be valid. The crux here is that the state of accounts (i.e. identifiers) never overlap or depend upon each other.

So, where does KERI fit into this?

KERI stands for Key Event Receipt Infrastructure. It was initially conceived by Dr. Samuel Smith, distributed systems pioneer and founder of ProSapien, and is now being worked on and implemented under the Decentralized Identity Foundation (DIF). In a nutshell, KERI is a flexible, secure, minimal and privacy-preserving trustless DKMS.

In contrast to blockchain or central registry-based trust systems, KERI is based on a hash-chain data structure called a ‘key event receipt log’ (KERL). Conceptually, it’s similar in some ways to the Peer DID Method specification, except that its data model is a KERL rather than a DID document. And while KERI can be used as a DID method, it is fundamentally not reliant on any of the DID specifications and can be used in many other contexts as well. In particular, it is also useful for Internet of Things (IoT) networks and other security-conscious, low-resource use cases.

Exploring events

A KERL is composed of a list of key events and witness receipts – more on these later. A key event, however, is a transaction signed by the controller of the identifier and indicates an update in the state of the identifier’s keys or other semantics. There are a few basic kinds of key events.

• Inception: this event signals the creation of an identifier, and it cryptographically binds some information to the identifier. The result of an inception event is an identifier with two sets of keys: one for signing, another for controlling. The signing key set can be used to authenticate as the identifier, while the control key set (which is hashed and not visible in the event) can be used to create rotation events.
• Rotation: this event signals the change of signing and control keys for the identifier. KERI relies upon a rule called pre-rotation for post-quantum security. Rotation events maintain this rule. Upon rotation, the control keys (used to sign the rotation event) become the new signing keys, while a new set of control keys is added. This ensures that no attacker can ever compromise the control keys because they are never used (or perhaps never even existed in the first place) until they sign the transaction which makes them no longer the control keys. A rotation event which has an empty set for the control keys is equivalent to abandoning the identifier (as no new control events are possible).
• Interaction: these events simply contain a commitment to a piece of data. Within KERI they can be used by a delegator to commit to – and thus finalize – a delegated inception or rotation event.
• Delegated inception: this event signals adding a new set of delegated keys to the identifier. Similar to the inception event, this new key set has an identifier created by cryptographically binding its inception data, and as such can be referenced by a “path” from the main identifier, e.g. identifier#delegated_identifier.
• Delegated rotation: this event signals the rotation of a delegated key set, similarly to the rotation event. Much like the main identifier, the delegated identifier does not change when the underlying key set is rotated.

State update rules

Along with these event types, there is a set of rules for validating a list of these events. The result of applying these rules is an identifier and a set of keys which are proven to be controlled by the identifier. In simple terms, these rules are:

• There can only be one inception event, and it must come first.
• Each rotation event must be signed by the control keys established by the previous events and must set the new signing keys to be the previous set of control keys.
• Each delegated inception or rotation event must be signed by the signing keys established by the previous events.
• All events must have a monotonically-increasing counter.
• All events must contain the hash of the previous event.

These rules, when applied to the key events, provide the conflict resolution mechanism which enables KERI to work independently of a central registry. A key event log or KEL (i.e. a log containing only events with no receipts) which is being updated will reject an incorrect event. By appending the first valid event, all other valid events for that place in the KEL are rendered invalid (i.e. the counter or backhash or some other semantic detail will be deemed incorrect).

The key event log validation rules provide a way to know the correct key state for an identifier, just as the consensus rules of the Bitcoin blockchain provide a way to know the correct balance of an account. In this sense, a KEL can be thought of as a “single-account blockchain” or micro-ledger. This is perfect for knowing a KEL is valid — but when presented with multiple different KELs for a single Identifier, how can one know which is the “true” KEL?

Witnesses

The witness system is the conflict resolution mechanism for KERLs (remember, a KERL is a KEL plus witness receipts), the same way that the validation rules serve as the conflict resolution mechanism for key events. In an inception event, the creator of the event can list several “witness” identifiers. Upon creation of a key event (every kind, not just inception), the entity must present the event to its witnesses and in return the witness gives a signature of that event. These signatures are compiled into a witness receipt for each event in the KEL. In the case of divergent conflicting KELs being detected, a validator can collect the KEL and the witness receipts into a KERL and prove which is correct via an algorithm called KAACE (KERI’s Agreement Algorithm for Control Establishment, see section 11 of the KERI white paper for more details).

The security mechanism here is subtle but very effective:

1. The witnesses are cryptographically bound to the identifier in the inception event.
2. The witnesses are assumed to be trusted (or at least not known to be malicious) by the creator of the identifier and give signatures which cannot be repudiated.
3. Any attacker must compromise both the control keys of the identifier (very difficult already because of pre-rotation) and all of the signing keys used by the witnesses. If there is more than one event, they will have to compromise the entire key history of each current and previous witness and the identifier. This is much more difficult than, say, compromising the single key pair used to secure a Bitcoin account.

With these security properties, a KERI-based identifier is at least as hard to compromise as most blockchain accounts, equivalent to compromising a single private key. What’s more, a KERI-based identifier is more difficult to attack, being equivalent to reversing several hash functions and compromising an arbitrary number of private keys held by different parties.

This makes KERI an incredibly flexible and powerful way of managing identifiers and keys without recourse to, reliance on, or vulnerability through any centralized or decentralized service or infrastructure.

KERI can even act as a bridging account, whereby key pairs for different ledger networks can be managed and linked under a single Identifier, due to its cryptographic flexibility. This is because KERI currently supports five signature schemes and can be extended to add more.

Ultimately KERI’s core value propositions are:

• Enforced pre-rotation: ensures that the recovery keys are never exposed prior to use, so that even an attacker with a quantum computer can not crack the recovery key set.
• Ambient verifiability: events being verifiable without reliance on a global state which must be kept synchronised allows for KERI to be effective on any scale and in any deployment environment, networked or not.
• Flexible trust structures: the two-layer multisig combined with the rotatable witness set provides support for any imaginable arrangement of trust, or none at all.

‧ ‧ ‧

KERI is currently being worked on in the Decentralized Identity Foundation’s Identifier and Discovery Working Group, co-chaired by Dr Sam Smith who originated KERI and contributed to this article via his ideas and feedback.