Tensegrity

Identity is, of course, an extremely complicated subject that has been endlessly blogged, white papered, carved and assigned to the appropriate magic quadrants. I won’t add much to those previous dissertations and discussions; Apollo and thus Sky uses an existing specification called KERI: the Key Event Receipt Infrastructure for Identifiers and Key Management.

Frankly, I always loathe talking about these types of things because they are completely and utterly embroiled in massive standardization efforts. Decentralized Identity is extremely hot with the crypto and web3 crowd as it’s – frankly – one of the few viable applications one can make the case for wrt the underlying technology of blockchains n’ such. Of course, there’s literally no requirement to use any kind of distributed ledger nor any requirement use any of the other attendant technologies that are so near and dear to the hearts of the proponents of these same technologies.

However, it still remains that in order to perform the functions that I’ve been laying out for Sky/Apollo, a strong notion of identity must be defined. It’s literally a foundational abstraction and it requires being firmly dealt with up front with no excuses nor hand waving allowed.

I had investigated a lot of identity schemes in this space, and have a lot of familiarity with the issues surrounding identity via my day jobs. I finally came to settle on the KERI design for Apollo/Sky identity. I believe it is an excellent choice, even though it’s not part of any decentralized identity standard efforts any more. Sky and Apollo don’t need that kind of interoperation requirements, imo.

The KERI specification is extremely dense and quite long, weighing in at 140 pages. So you will be unsurprised to learn that I am not going to dive into an in depth explanation and discussion on KERI and its associated technology. It is an extremely well written document is very good at laying out the KERI design; I strongly recommend reading it – at least skimming – if you want seem more of the details of the technology.

Identifiers

Identifiers are fundamental to identity and provide the “handle” we use for identity. Identifiers may be opaque, transparent, human readable… endless varieties of such. In Sky/Apollo, there is also an architectural need for strongly binding of Identifiers to a cryptographic key pair(s). This basic Identifier -> Public/Private key pair association is used throughout Apollo, primarily for signing and validation, but there are some encryption use cases as well. And the fundamental problem with the Identifier -> Key Pair binding is that it must be a strong binding, not a weak binding.

Strongly Bound

The diagram above demonstrates what we’ll refer to as a weak binding between the identifier and the key pair that is associated What we mean by this is illustrated on the left. We have two “personas” in this diagram: the Controller of the Key Pair and the Administrator that maintains the binding between the Key Pair and the Identifier. The Controller generates and uses the Key Pair for signing. This binding is strong between the Controller and the Key Pair because only the controller of the private key can sign using that key, providing proof of control.

The same cannot be said for the binding between the same Key Pair and the Identifier. In this binding, the Administrator is the trusted persona that maintains an association where one can look up the public key associated with an identifier (and vice versa). Because the identifier is not strongly bound to the key pair, the strength of the binding relies on the Administrator that maintains the database that provides the mapping between key pairs and Identifiers. This is far weaker because this association is in no way traceable from the key pair back to the identifier; only the Administrator updating the key/identifier association validates the association.

The right side of the diagram above shows the three bindings we are concerned with in Apollo:

1. Controller <-> Key Pair : Strong
2. Key Pair <-> Identifier : Weak
3. Identifier <-> Controller : Weak

The problem Apollo faces is that only one of these bindings associations is strong. The other two bindings are inherently weak and pose a significant architectural risk. If we cannot strongly bind these associations as we have strongly bound the Controller and Key Pair, then we must over engineer and compensate for the lack of the two strong bindings.

This is where many problems wedge themselves in. If it’s just a database update to change the association, then the DB system that maintains the association is a single point of failure for these bindings – and it’s a failure independent of the Controller and Key Pair used. The Administrator, the database service, et al. – they all provide unnecessary attack surfaces that must be compensated for.

The diagram above illustrates the bindings in the KERI design. Like the previous diagram, the left side above demonstrates that the two personas we had – i.e. the Controller and the Administrator – are now replaced with the single entity: the Controller of the Key Pair. This is accomplished by creating a cryptographic binding between the Identifier and the Key Pair it represents. This means that we now have a strong binding between these two as we can now cryptographically verify the Identifier and the Key Pair; That is, the controller of the Identifier is the controller of Key Pair and we can verify that from the Key Pair and Identifier alone.

This strategy results in the strong bindings illustrated on the right side of the diagram above. In contrast with administratively maintained associations, the binding between the Identifier and Key Pair is cryptographically maintained – i.e. it is not merely a database association that provides this binding. This results in a Self Certifying Identifier. This means that we can verify that the Identifier and the Key Pair are bound using only the public key and the Identifier itself. In the administrative model this is a binding guaranteed only by trustworthy and correct administrators of the bindings database.

A Key Event Ledger For Every Identifier

The diagram above illustrates the central part of the KERI design, which is the Key Event Receipt Ledger – the KERL. Again, I would refer you to the most excellent KERI specification for details, but the main thing to know about the KERL is that it is simply a ledger that can only have a single writer, and the single writer is the Controller of the Identifier that defines the ledger. All “blocks” in this ledger represent Key Events for the Identifier. These events represent lifecycle events of the logical Key Pair that the Identifier is strongly bound to (through the events of the ledger).

The Inception Event of the Identifier represents the creation of the logical key for this Identifier. Note that I’m referring to a Logical Key Pair. This is because KERI deals with the nasty aspects of Key Rotation front and center. Strong bindings between the Identifier and this logical key pair is performed by creating two key pairs when we create the Identifier. One key pair is the “current” key pair, represented by the Inception Key Event. The second key pair is not yet revealed and kept hidden. However, what the Inception Key Event does is encode a commitment to this hidden key that can be revealed at a later time to prove that one has control over this hidden key and that it is the same key committed to in the Inception event.

The Rotation Event is that aptly named Key Event that represents the rotation – the revealing – of the previously hidden key and the establishment of that key as the “current” key of the Identifier. Like in the Inception event, the Controller also generates a new next key pair which is kept hidden. And like Inception, the Rotation event provides the commitment to this next hidden key to be revealed upon the next Rotation Key Event.

The extremely useful thing to note is that the value of the Identifier – which in Apollo is, by default, a 32 byte value (256 bits) – remains fixed. It’s what identifies the Key Event ledger. This gives us a cryptographically strong binding to all the keys that a Key Event Ledger records. We know that things signed by these keys are bound to the 32 byte value of the Identifier. This means controllers can rotate keys on their own, whenever they wish, for whatever reason. Issues such as control of keys, rotation policies, etc, etc, are well defined and implemented in designs conforming to the KERI specification.

Key Delegation and Hierarchical Key Control

KERI also defines how key delegation and hierarchical control is achieved. This provides Sky/Apollo with a rich design patterns to provide extremely secure solutions to rather tricky key control and authentication/verification problems.

The way that KERI provides this functionality is by a set of Delegated Key Events. These events are a clever form of two phase commit that provides the mechanism for cryptographically verifiable control of one Identifier by another Identifier; that is to say, a strongly bound hierarchical Identifier structure is provided by this functionality. Sky leverages key delegation to provide the decentralization of Identity on a permissioned, distributed system infrastructure as well as hierarchical identifier control within a Controller’s domain.

Distributed Key Event Receipt Ledgers

Recall that these KERLs are single writer. That is, only the Controller of the Identifier’s logical Key Pair can append Key Events to the Identifier’s KERL. This means that there’s no consensus to be performed – it’s a single writer. This makes it the easiest distributed ledger in the world to distribute. Apollo leverages this fact to provide a Unified KERL in the form of a Byzantine Fault Tolerant Distributed Hash Table (DHT). By “Unified KERL” what I mean is that we store and manage the KERLs of a whole lot of Identifiers in this DHT.

Apollo’s BFT Distributed Hash Table is, in itself, some pretty cool technology imo. Peer To Peer systems like DHTs are by conventional, chorded design, extremely hard to make secure (for some value of secure). For some use cases, such as content addressable DHTs, where the key of the value is the hash of the value, some of the concerns regarding validation of key to value are implicit. Other use cases where content addressable design is not available have much harder issues to overcome and the multiple hops in these chorded DHTs provide challenging security, validation and availability environments.

Apollo leverages the ring based model from Fireflies to provide a single hop DHT – rather than a chorded, multi hop DHT as is the fashion with kids these days.

As it turns out, this BFT communication pattern used for the single hop KerlDHT is also a communications motif used throughout Apollo and thus Sky. In this pattern, the members of a group are mapped to a set of rings. These rings form a set of consistent hash rings where the position of the members on each of the rings is based on a different hash function. This means that while every member in the group is present in each ring, they appear in a different order due to each ring having a different hashing function for the member’s identifiers.

This ingenious structure forms an expander graph and the way we construct them gives us a byzantine fault tolerant subset of members in the group when taken as a set of successors from some supplied identifier. This is an incredibly interesting subject I can really only gloss over in this post, but you can of course check out the Fireflies module and Context model in Apollo that implement this functionality. Subsystems like the KerlDHT are built upon a Ring Communications idiom that leverages these BFT ring structures, and they are also leveraged in Apollo’s SQL State Machine replication module, CHOAM, to provide a verifiable random function for selecting committee members.

The core KERI implementation module in Apollo is the Stereotomy module. The Apollo Stereotomy model deviates somewhat from the KERI specification in that Apollo uses Protobufs to define the various serialization structures used throughout KERI, rather than JSON. This provides a vast simplification in the implementation while providing an extremely compact interchange serialization. The Stereotomy interface defines the KERI “Controller” that provides the API for a Controlled Identifier. A set of services are also defined in the KERI specification and Apollo provides these in the aptly named Stereotomy services module.

The Key Take Away

Okay, that pun probably fell on deaf groans but the important take away from this post is that the fundamental Identifier model in Sky/Apollo is based on the KERI specification. Sky uses the KERI Identifier model for Identity purposes and the Identifier used by Sky/Apollo provides a strong binding between the Identifier and the logical key pair of a Controller. This provides key rotation, delegation and a host of other useful services and solutions that Apollo uses to provide solutions to rather tricky and nasty security and authentication problems. And while a complex and highly capable specification, KERI provides a fundamentally simple and straightforward model for Identifier and the logical keys associated with them. Sky/Apollo leverages this to the hilt throughout all the Apollo architecture to provide the foundation level Identifier model.