Papers

KEey EVENT RECEIPT INFRASTRUCTURE (KERT) DESIGN AND BuiLp Samuel M. Smith Ph.D." 2019/07/03 version 1.6 Abstract—A decentralized key management infrastructure (DKMI) that uses the design principle of minimally sufficient means is presented. The primary key management operation is key rota- tion via a novel key pre-rotation scheme. Two trust modes are presented, the online or pair-wise ‘mode and the offline or any-wise mode. The offline mode depends on witnessed key event re- ceipt logs (KERL) as an additional trust basis for validating events. This gives rise to the acronym KERI for key event receipt infrastructure. The KERI approach may be much more per- formant and scalable than more complex approaches that depend on a total ordered distributed consensus ledger. KERI may be augmented with distributed consensus ledgers but does not re- quire them. The KERI approach allows more granular architecture in a DKMI. Moreover, be- cause KERI is event streamed it enables DKMI that operates in-stride with data events streaming applications such as web 3.0, IoT, and others where performance and scalability are more impor- tant. KERI is designed to support DIDs but its core services are identifier independent (this in- cludes DID method independence). This makes KERI a candidate for a universal portable DKM, Inden Torms—Decentrlized, Koy, Mansgement, Infrstructor, Key, Event, Recsipts, Pro-rotation, Rotation, Event, Streaming, DKMI, KERI, KERL, KEL, 1 INTRODUCTION

Herein we define an identity for an entity simply as an identifier and attributes that may be used to describe the entity. Entities are not limited to natural persons but may include groups, organizations, software agents, things, and even data items. With a centralized identity system one entity controls all the identifiers. With a decentralized identity system, in contrast, disparate entities each control some of the identifiers but in an interoperable way. To restate, each entity may have a set of identifiers that it controls but are still recognized by the other entities. Each entity may control or be sovereign over a set of identifiers. In the case where an identifier refers 10 its controlling entity then that entity is self-sovereign over its own identifier and hence the identity associated with that identifier. This property of decentralized identity systems has given rise o the term self-sovereign identity (SSI) [1; 19; 20; 27].

‘The typical approach to establishing or proving control over an iden

tifier is to use a universally unique cryptographic digital signature based a key pair comprised of a public key and a private key. The identifier includes the public key or a unique fingerprint of the public key. The private key is used to digitally sign attestations that may be cryptographically verified using the public key. The holder of the private key is in control of the identifier because only that holder can sign attestations that may be cryptographically verified with the public key bound to that identifier. This makes the identifier self-certifying [14-16].

1. ConsenSys e Seor Mermber IEEE, sanisamuelanit g

150

1.1 Source of Truth

The fundamental assumption is that the (public, private) key pair is universally unique and may be established using a random seed of sufficient size such that the likelihood of duplication (collision) is negligible. A typical method for generating the random seed is to use a crypto- graphic strength pseudo-random number generator with sufficient entropy. Currently 128 bits of entropy is considered sufficient. Other self-certifying identifier systems may use different means to generate and prove control over a universally unique identifier but this work is limited to sys- tems where control is proven via cryptographic (public, private) key pair based digital signa- tures. In this sense there is one primary source of truth for the identifier and hence any key man- agement operations applied to the associated (public, private) key pair. This source of truth is the set of signed attestations made with the private key and verifiable with the public key.

Although this work may be generally applicd to any decentralized identity system that uses self-certifying identifiers, its primary focus is on decentralized identity systems that are inter- operable with the emerging DID (Decentralized 1D) standard [7; 22; 25; 26].

1.2 Minimally Sufficient Means

For decentralized identity systems based on self-certifying identifiers, management of the as- sociated private keys is essential. Because the controlling entity holds their own private key(s) the primary burden of management falls on that entity or its assigns. The sccurity of the identity is a function of the security of the management infrastructure. As mentioned above, unlike a cen- tralized or administrative identity system where a central administrative entity controls all the identifiers, a decentralized identity system may have a multitude of controlling entities each con- trolling one or more identifiers. Some of these entities may not have the resources or the exper- tise to design, build, and maintain secure key management infrastructure. Consequently there is aneed for open interoperable decentralized key management infrastructure (DKMI). Morcover, some applications of decentralized identity may benefit from DKMI that is scalable and perfor- ‘mant. Example applications include data streaming, supply chain, IoT (interet of things), and other applications where data provenance among multiple controlling entities is important and data processing is demanding. One design approach to comp

osing scalable and performant infra- structure is to find minimally sufficient means for each of the key management tasks. This is a primary motivation for this work, that is, to identify the minimally sufficient means for essential key management tasks. This does not imply that other means might not be beneficial or best for a given application but that by first understanding minimally sufficient means an implementor ‘might have at hand more design options that might be customized to better fit a broader class of applications.

1.3 Distributed Ledgers

‘The primary alternative for decentralized key management infrastructure is a distributed ledger based on a distributed consensus algorithm that provides an additional source of truth for key ‘management operations. There are many types of distributed consensus algorithms with various properties. One useful property of many distributed consensus algorithms is a total (global) or- dering of events from multiple sources. This allows all transactions on the associated ledger to have a unique ordering with respect to one another. In the case of key management, for example, the total ordering property makes it casy to establish the ordering of key inception and rotation events. In addition to the aforementioned signed attestations with the private key, a distributed consensus ledger may be used as a source of truth in a DKML This may be as a primary (cssen- tial) source of truth this coupled to signed atestations or may be merely a secondary (non-essen- tial) source of truth that provides complementary sceurity. A distributed consensus ledger, how- ever, may require a significant amount of infrastructure that must be setup, operated, and

280

‘maintained. Typically infrastructure that depends on distributed consensus ledgers must tradeoff cost, throughput, and latency and as a result may not be as scalable or performant as infrastruc- ture that does not depend on a distributed consensus ledger or that minimizes that dependency such as minimizing the number of operations that must be performed on the distributed consen- sus ledger.

‘This work explores more scalable and performant DKMI that cither minimizes the number of primary operations required on a distributed consensus ledger or merely uses a distributed con- sensus ledger as a secondary source of truth if at all. One way to avoid or minimize the use of a distributed consensus ledger is to leverage the fact that only the holder of the private key may create events that produce verifiable operations to the keys including the ordering of associated events. Thus a secondary source of truth merely needs to witness events and their ordering not provide the ordering,

1.4 Key Management

The three main key management tasks are key reproduction, key recovery, and key rotation. ‘We call these the three Rs of key management [22]. The focus of this work is key rotation which may be the most difficult.

1.4.1 Reproduction

Key reproduction includes the creation and derivation of (public, private) key pairs and the as- sociated tracking and storage of the private keys. A discussion of key reproduction is provided elsewhere. But in summary one method that simplifies key reproduction tasks is the use of hier- archically deterministic key derivation algorithms that produce ((HD keys) or keychains. An HD key pair is usually derived from a root private key and some deterministic key path. The key path may be public. This means that there is no need to store the derived HD private key which is a security risk because the private key may be rederived on demand from the root key and the public derivation path.

1.4.2 Recovery

Key recovery involves methods for sccurcly backing up or distributing private keys such that they may be recovered in the event that the device holding the private key is lost or damaged. Key recovery approaches are also discussed elsewhere,

1.43 Rotation

Key rofation involves methods for securely revoking a key pair and replacing it with a new key pair. Revoke without replace may be accomplished by merely rotating to a null key. Thus ro- tation may be implemented as a primary operation and revocation (without replace) may be im- plem

ented as a special case of rotation. The primary motivation for key rotation is to prevent, ‘mitigate, or recover from an exploit of the private key due to exposure. The primary risk of ex- posure comes from use of the private key to sign attestations. Creating a signature typically re- quires loading the private onto a computing device in order to create the signature. Should an at- tacker exploit or capture the computing device they may gain access to the private key. In addition continued use of the private key to sign atestations may over time reduce the effort to cryptographically break the key. Finally over time cryptographic exploits of a given (public, pri- vate) key crypto-system may be discovered thereby rendering the key insecure. Best practice, therefore, is to enable the rotation of a given (public, private) key pair to a new (public, private) key pair cither to the same crypto-system or to a stronger crypto-system. In decentralized identi- ty ‘systems, key rotation is useful when the controller of a self-certifying identifier needs to ‘maintain persistent control over that identifier indefinitely despite exploits of the private key(s).

30

Otherwise in the event of exploit, the controller could just abandon the exploited identifier and create a new identifier with a new (public, private) key pair.

Periodically rotating the key bounds the risk of compromise resulting from exposure over time. This can be used proactively to upgrade the digital signature crypto-system to keep up with advances in computing, The more difficult problem to solve is rotation after a specific exploit may have already occurred. In this case, the exploiter may create a valid signed rotation opera- tion to a key pair under the exploiter’s control prior to the original controller detecting the ex- ploit and they rotating to a new key pair under its own control. The exploiter could thereby ei- ther “capture” the identifier or create a conflict or race condition where two inconsistent but verifiable rotation events have been created. This work provides a scalable performant protocol using pre-rotation or equivalently one-time rotation keys that solves the problem of secure rota- tion after an exploit may have occurred.

‘With self-certifying identificrs special semantics are applied to rotation. The public key associ- ated with the identifier is not changed merely the private key that is authoritative for signing at- testations. Otherwise the identifier loses its value as an identificr. Consequently in order to verify an attestation belonging to a self-certifying identifier the verifier must know the key rotation his- tory for that identifier. To clarify, the original public key from the initial (public, private) key pair is used to create the identifier. The identifier includes a reference to the public key. The original private key is used to cryptographically sign attestations that prove control over the identifier. The original public key is used to cryptographically verify the signatures. Each rota- tion operation creates a new (public, private) key pair. A valid rotation operation must be signed at the very least with the original private key. Rotation does not change the identifier. It still ref- erences the original public key. After rotation, however, atrestations are now signed with the new private key and verified with the new public key. The original private key has been revoked and replaced with the new private key specified in the rotation operation. The new public key is in- cluded in the identifier’s key rotation history. Validation of an attestation first requires lookup and validation of the key rotation

history. The final rotation entry provides the current key pair used to sign and verify attestations.

The key rotation history of digital signing keys used to control an identifier, provides the basis for managing any other data affiliated with the identifier. In general, changes to the value of attributes associated with or under the control of a digital signing key pair may be managed by verifiable signed assertions using the signing key. Thus management of the signing key pair en- ables management of affiliated data including other keys such as encryption keys.

‘This work describes a protocol that provides sccure verifiable rotation that solves the problem of successful exploit of a given private key due to exposure when that exploit happens sometime after creation and use of the key. It is assumed, however, that the private key remains private for some meaningful time after its creation. This protocol does not address the cryptographic securi- ty a private key in the face of side channel attacks that capture the private key at the time of cre- ation and/or first use nor brute force or other attacks that may break a private key given only the public key and signed attestations. Side channel attacks, however, may be prevented or mitigated in other ways.

2 NOMENCLATURE 2.1 Definitions

A digital signature is a string of characters that is produced by a cryptographic operation on a given siring of characters (signed text) using the private or signing key from a (public, private) key pair. The public or verifying key may be used in 2 related cryptographic operation on the

w0

given signed text to verify the validity of the signature. A digital signature has two important properties. The signature is unique to the key pair for the given signed text and the signature is non-repudiable by the signer, that is, only the holder of the private key can create the signature.

A digest is a string of characters that is the output of eryptographic hash function on another (usually much longer) string of characters. The important property of a cryptographic hash func- tion s that the digest is highly unique to the longer string of characters on which it was comput- ed. This is called collision resistance. A digest is a space efficient but unique fingerprint of the content of some message. A signed digest is a commitment to the content. Because digital signa- tures schemes include hash functions, a signature is also a type of digest

A self-certifying identifier is bound to at least one cryptographic digital signature (public, pri- vate) key pair. This protocol description uses that the simpler term identifier to mean self-certify- ing identifier unless that shorter expression would be ambiguous.

A controller is a controlling entity of an identifier. An identifier has at least one but may have ‘more than one controller. Let L be the number of controllers. All proper key management events on the identifier must include a signature from the controller when there is only one or a signa- ture from at least one of the controllers when there is more than one. Typically, when there is more than one controller, control is established via L signatures, one from each coniroller. Al- tematively, with a K of L threshold control scheme, where K < L, control is established via any set of at least K signatures each one from a subset of at least size K of the L controllers. A more sophisticated scheme is a fractional weighted multi-signature.

A message as used by the protocol includes a serialized data structure. The data structure must be serialized in order to be digitally signed. Typically, a message includes a serialized data struc- ture and one or more appended digital signatures

An event may be conveyed by a message. The protocol is primarily concemed with creating, transmitting, validating, and logging events as conveyed by messages.

A key management event or key event for short is a special type of event that represents a key ‘management operation on the key(s) associated with an identifier. These operations are typically related to key rotatio

n. A proper key management event includes a signature(s) by the con- troller(s) of the associated identfier.

An inception event is a key event that represents the creation operation of an identifier and its initial set of controlling keys. There may be one and only one inception operation performed on an identifier.

A rotation event is a key event that represents a rotation operation on an identifier that rotates the set of controlling keys to new set. There may be any number of rotation operations in a unique ordered sequence. Any and all rofation operations may only occur after an inception operation.

A key event log (KEL) is an ordered record of all the key event messages created by the con- troller(s) of an identifier.

Avalidator is an entity that must determine which set of keys are the current controlling set for an identifier that has been subject to rotation operations subject to key operation events by the controller. A validator may do this by replaying the events in a valid KEL.

A witness is & somewhat trusted entity that may receive, verify, and store a key management event on an identifier for which the witness is not a controller. In addition cach witness controls its own self-referential identifier via an associated (public, private) key pair or pairs. A witness may thercby create digital signatures on key event messages it has received but are associated with other identifiers not under its control. Any entity that controls its own self-referential identi-

s30

fier may act as a witness by signing with its own identifier key(s) a copy of a key event message for an identifier not under its control. Depending on the circumstances of the protocol a set of entitics may be designated as trusted or authoritative witnesses. The primary role of a witness is to verify controller signatures attached to an event as well as the event’s integrity. In this sense a witness is an event verifier. The witness also establishes priority to the first version of an event it recives (first seen). The witness signifies this by only signing the first successfully verified ver- sion of an event it receives. To restate a witness will never sign any other conflicting version of the same event in a key event sequence.

A receipt is a special type of event conveyed by a message and may include of a copy of a key management event message or else a reference to the message with one or more attached signa- wres. This may be referred to as key event receipt. A valid key event receipt must inchude a signature of the associated key event message. Typically each signature comes from one or more witnesses o entities acting as witnesses. Indeed the primary purposc of a witness is to generate, store, and disseminate an event receipt for the first verified version of an event the withess re- ceives. A simple witness key event receipt message might inelude the identifier of the witness, a label for the event that that it is receipting, and signature by the witness of the receipted event.

Akey event receipt log (KERL) is an ordered record of all the key event receipt messages for a given identifier created by a given set of witnesses. Typically witnesses keep a KERL for all the identifiers for which they create receipts.

Because a proper key event message includes the signature(s) of the controller(s) it may be thought of as a special type of self-signed receipt. In this same way a KEL may be thought of as a special type of KERL.

A judge is an entity that examines the entries in a KEL or KERL for a given identifier to deter- mine if the associated events are valid and ultimately to determine which st of keys are the cur- rent controlling set given the rotation operations on that given identifier as represented by the events in the log. The primary role of a judge s to validate that a given event sequence has been sufficiently witmessed such that it may be trusted. In this sense a judge is a validator of wit- nessed events. Each judge controls its own

self-referential identifier via an associated (public, private) key-pair or pairs. A judge may thereby create digital signatures on attestations about validations it has performed on KELs or KERLS to determine the authoritative key-pair(s) of an identity. A judge may be a second party involved in a transaction with a first party controller or a judge may be a trusted third party in a multi-party transaction that includes a controller and other parties.

A given entity may act in the roles of both witness and judge. A validator might perform its fanction by serving as both a witness and judge or by trusting other witnesses and judges.

‘This terminology gives rise to the acronym KERI for Key Event Receipt Infrastructure that de- scribes the associated infrastructure consisting of controliers, witnesses, judges, validators and key event (receipt) logs [21].

2.2 Pre-rotation

A described above, one use of key rotation it to recover from a successful exploit of private key. Given that the private key may be compromised the rotation operation must be authorized using a different private key. One common approach it to use another key-pair just for rotation operations. This has the disadvantage that the rotation key-pair will over time also become ex- posed due to use and may therefore eventually be at risk of exploit and likewise need to be rotat- ed. To mitigate this yet another key-pair may be used to authorize the rotation of the rotation key-pair and so on. This comprises a more complex hierarchical key management infrastructure

80

In contrast, the approach presented here, called pre-rotation, is much simpler [22]. In its simplest form, whenever an identifier is created two key-pairs are created. The first i the original key- pair bound to the identifier and the second is a pre-rotated key-pair that will be activated as a result of the first rotation or the original key-pair. This pre-rotation is declared at initialization, The associated key event is called an inception event. Each later rofation operation in furn cre- ates and activates a new pre-rotated key-pair. In essence pre-rotation creates and uses one-time rotation keys. Thus later exploit may not capture the key rotation authority. A rofation operation must be signed by pre-rotated key-pair as declared in the previous rotation or inception opera- tion. Furthermare for enhanced protection against forged key rotation histories each rotation operation must also be signed by the current signing key-pair at the time of rotation. Each rofa- tion operation provides a signed commitment to the next pre-rotated key-pair but using the cur- rent controlling key-pair and the previous (erstwhile) controlling key-pair . Because each pre-ro- tated key is not used to sign anything at the time of its creation nor anything clse prior to the next rotation event, it is not thereby exposed to exploit from usage. A subsequent exploit of the current key-pair cannot change that prior commitment o the specific pre-rotated key-pair. This prevents the exploiter from capturing control of the identifier by using the exploited key to rotate to some other key under s control. In order to verify the provenance of the current valid key- pair a validator needs to be able to replay the history of rotation operations.

‘The pre-rotation approach has some useful features. For many exploits, the likelihood of suc- cess is a function of exposure to continued monitoring or probing. Narrowly restricting the op- portunity for exploit in terms of time, place, and method, especially if the time and place happen only once, makes exploit extremely difficult. The exploiter has to either predict the one time and place of the event or has to have contimuous universal monitoring of all events. By declaring the very first pre-rofation at the inception event of the associated identifier and controlling key-pair, the window for exploit is as narrow as possible. Likewise, each subsequent rofation is a one time and place event as well a one-time usage of the (pre-rotated) rotati

on key. Pre-rotation does not require any additional key infrastructure for rotation. This makes the approach self-contained. Because each rotation-operation event requires two signatures, one using the current key and the other using the pre-rotated key, an exploiter would have to exploit both keys. This is extremely difficult because the only prior times where the private side of the pre-rotated key-pair s used are (1) at its creation in order to make the associated public key, and (2) at the later signing of the rotation operation event. This minimizes the times and places to a very constrained set.

The caveat with pre-rotation is that the validating party be able to replay the rotation cvents to ensure that it did not miss a rotation. This replay allows the validator to verify the provenance of the chain of rotations. Requiring both the current and previous signing keys in the rotation oper- ation means that a forger must exploit both keys or sets of keys (when multi-sig).

There are two use cases for providing this replay capability. The first is online one-to-one or pair-wise interactions and the other is offline one-fo-one (pair-wise) or equivalently offline one- to-many (any-wise) interactions,

2.2.1 Online One-to-One Replay

In the online one-to-one (pair-wise) case, the first parly is controller of a given identifier and wishes to interact with a second party, the validator, using that given identifier. The second party must validate that the given identifier is in the control of the first party. To restate, with respect to the given identifier the first party is the controlfer and the second party is the validator. Be- cause the identifier is bound to the public key of a key-pair the controller may establish control by sending an inception operation event message signed with the corresponding private key. This inception event establishes the controller’s control over the identifier from the perspective

7150

of the validator. The inception event also includes a commitment to a future pre-rotated key pair. ‘This forward chains the inception event to the next event albeit not to the content but to a future verifiable signature made with the pre-rotated key. Likewise the first rotation operation event sent by the controller after the inception event includes a commitment to the next pre-rotated key-pair. Fach subsequent rotation operation inchudes a commitment to the next pre-rotated key. This establishes a forward chain of future commitments to unexposed key-pairs. The private key in a pre-rotated key-pair is not used until a subsequent rotation operation. This prevents an ex- ploiter from capturing control of a future rotation operation with an exposure based attack.

‘The controller must also establish a commitment to the order of events. Because only the con- troller can create verifiable events, the controller may uniquely establish the order of events. No other source of truth with respect to ordering is needed. As long as the validator maintains a copy of the original event sequence it will be able to deteet a later exploit that attempts to change any of the events in that sequence

‘There are two ways a controller may establish an event sequence. The first s o use a monoto- nically increasing sequence number such as an integer counter. The second is to include a back- ward cryplographic commitment in each event to the contents of the previous event (excepting the inception event). The inclusion of a commitment to the content of the previous event content effectively backward chains the events together in an immutable sequence (a self contained backward event chain). Although a sequence number is simpler and results in smaller messages. the backward chain may be more robust because with backward chaining, possession of only the Latest event allows the detection of tampering of any carlier event that is later presented to the validator without it having to keep an original copy of all the events. This prevents an exploit where an altenative sequence of events are created but that terminate with the same key-pair(s) as the original final event. This means the validator does not have to maintain strict custody over its copy of the events but merely the final event in order to detect tampering in any other copy of the cvent sequence. This relaxes the requirement from maintaining secure custody of the com- plete key event sequence to merely maintaining secure c

ustody of the last message. Backward chaining comes at the cost of making cach event message bigger to include a backward commit- ‘ment to the previous message.

A backward commitment is usually a collision resistant digest of the serialized content of the previous event. The output of a hash function or & digital signature may be used as a collision re- sistant digest. Because each event s already signed, using a hash requires extra computation to create. Verification of a hash, however, may take somewhat less time than the verification of a signature. Furthermore, a signature may be longer than a comparable hash. The choice of signa- ture or hash function is a computation space tradeoff [6]. In this work the output of a crypto- graphic hash function s used for the digest [5].

‘The validator needs to maintain a log of the key event messages to verify the provenance of the current controlling key-pair for the identifier. This is a key event log (KEL). As long as the validator maintains a copy of this log, an exploiter may not establish control of the identifier due to an exposure exploit. For example, a later exploit of the original key-pair could be used to forge a different inception event. As long as the validator has a copy of the original inception event it could detect the forged inception event and ignore it. Likewise later exploits of any of the keys except the last pre-rotated key could be used to forge different rotation events. As iong as the validator has a copy of the original chained key rofation event sequence starting with the original inception event it could detect the exploited rotation events and ignore them. Because the last pre-rotated key is never used until a new rotation event is created, the risk of exploit is ‘minimized (exploit must come from via a side-channel attack not exposure). When the key event sequence is backward chained the validator need merely keep a secure copy of the latest event in

80

order to detect tampering of any copy of the event log. The validator still needs to be provided a copy of all the events to validate the event sequence but should the validator lose custody of the full event long and only maintain custody of the final event it may re-csiablish the validity of some other copy by backwards validation from its preserved final event.

Absent any other infrastructure, in order that the validator obtain a complete event log, the controller must ensure that the validator has received each and every rotation event in sequence. ‘This requires an acknowledged transfer of cach new rofation event. In order to ensure that this occurs the controller and validator must both be online (hence the online case) at the time of the transfer. If cither party becomes unavailable the interaction pauses and the other party must wait until both parties are online to resume the interaction. Consequently this case is only useful for interactions where pausing and resuming is acceptable behavior.

The acknowledgment message includes a signature by the validator of the associated key event message, in other words, an cvent receipt. The controller now has a signed receipt that atrests that the validator received and verified the key event message. The validator is thereby in this narrow sense also a witness of the event. The controller can keep the reccipt in a key event re- ceipt log (KERL). This provides a trust basis for transactions with the validator. The validator may not later repudiate its signed receipts nor use a different key event history in interactions with the controller without detection by the controller.

Each party could establish its own identifier for use with the other in the pair-wise interaction. Each party would thereby in tum be the controller for its own identifier and the validator and witness for the other’s identifier. Each could maintain a log of the key events for the other’s identifier and key event receipts from the other for its own identifier thereby allowing each to be invulnerable to subsequent exploit of the associated keys with respeet to the pair-wise interac- tion. A log that includes both the signed key events (sigaed by the controller) and signed key event receipts (signed by the validator) is a log of doubly signed receipts of key events. Any transactions conducted with the associated keys within the time-frame maintained by the logged key event histories may thercby be verified with respect to the keys with

out the need for other infrastructure such as a distributed consensus ledger. A discussion of how to verify associated transaction events is provided later.

Of particular concern with this approach is the original exchange of the inception event. In a pair-wise interaction, however, the controller may create a unique identifier for use with the as- sociated validator and thereby a unique inception event for that identifier. This inception cvent is therefore a one time, place, and use event. Consequently, as long as the validator retains a copy of the original inception event, (or when backward chained a copy of any later event), the incep- tion event itself is not subject to later exploit due to exposure from subsequent usage of the orig- inating key-pair. Another way of looking at this approach is that each pair-wise relationship gets aunique set of identifiers and associated key-pairs for cach party.

The exchange of the inception cvent message must also be made invulnerable o man-in-the- middle attacks (for example by using multi-factor authentication) otherwise an imposter (man- in-the-middle) could create a different identifier under its control and confuse the validator about the correct identifier to use in interactions with the genuine controller. A diagram of the pair- wise infrastructure is shown below.

9150

Enty Entty A B Contrlle o denifir A AgventSisam Valdator of dentfer A 0 e _— L V e v & TR Koy Evat Lo Koy EvrtLag Koy Event o Log KeyEvrt R Log Figure 2.1. Online Pair-wise Ato B Entty Entty A B Valdator of dentfir B Beientean Contrller ofdentfir B Event Gonerator | Event Valdtor J7 SR Seeam v KELIKERL of A e & KELKERLofA Yoy v g ey EvrtLog Koy Evnt RcoiLog Koy Evnt R Log Figure 22. Online Pair-wise Bto A 2.2.2 Offline One-to-One or Offline One-to-Many Replay

In the offline case a validator may not be available at the time of creation to receive and ac- knowledge an inception event. Consequently a later exploit of the originating key-pair might al- low an exploiter to establish an altenative inception event and provide that instead to a validator thereby preempting the original unexploited inception event. The exploiter could thereby capture control of the identifier from the perspective of the validator. Likewise in the offline case a val- idator might not be available at the time to receive and acknowledge a rotation event. Conse- quently a later exploit of the associated key-pairs might allow an exploiter to establish an al- tenative rotation event and provide that instead to a validator thereby preempting the original unexploited rotation event. The exploiter could thereby capture subsequent control of the identi- fier from the perspective of the validator. The offline one-to-one case generalizes to the one-to- ‘many case where one controller uses the same identifier for interactions with a set of validators. this might occur when the controller is using a public identifier.

In the offline one-to-one (pair-wise) or one-to-many (any-wise) case, the key rotation history for a given identifier is maintained by a trustworthy service. While a decentralized distributed consensus ledger could provide this scrvice it may not be the minimally sufficient means. This work deseribes an alternative approach that uses a redundant immutable event log of inception and rotation key event receipts to provide a minimally sufficient means. The service is provided by a set of N designated witnesses and one or more judges. A validator may act as cither a wit-

10680

ness or a judge but in this case a validator is not one of the N designated witnesses that provide the service. The validator may cither be its own judge or rely on some other judge or judges The objective of the service is to provide at a copy of a correct or at least a complete key event receipt log to any validator that needs it (correct and complete are defined below). A redundant immutable (deletion proof) event log may be parallelizable and hence highly scalable.

In this approach, the controller of a given identifier creates and disseminates associated key operation event messages to the set of N witnesses. Each witness verifics the signatures and con- tent of each key event it reccives. When a verified key event is also the first version of that event the witness has received then it signs the event message and creates a receipt with its signature ‘The witness then stores the event receipt in its log. The witness sends its receipt as an acknowl- edgement to the controller. Depending on the dissemination protocol a witness may also send its receipt to other witnesses.

By event version it is meant the contents of the event at a given location in the key event se- quence. I the event contents are different but at the same location in the sequence then it is a conflicting version of the event. The policy is that the first one wins (event version) and is stored in the log all other versions are discarded. Later messages or receipts may not change an existing entry in the log. Each witness adds 10 its log any verified signatures attached to receipls it re- ceives from any other witness for the same version of the event in its log. Receipts for conflict- ing event versions are also discarded (not kept in the log) but may be used to proof duplicitous behavior by a witness. A witness® event receipt log is therefore by construction an immutable log. This log includes the events with attached verificd signatures; from the controller, the wit- ness itself, and other witnesses, that are the receipts.

Distribution of receipts to the N witnesses may be implemented extremely efficiently with re- spect to network bandwidih by the controller by acting in round-robin fashion. Each time the controller connects to witness to send new events it also sends the receipts it has received so far from other witnesses. The controller must wait for a receipt from each witness before it can complete the dissemination which may require a second pass around the witnesses. This

means, however, that at most 2N two-way exchanges are needed for each event in order to create a fully witnessed key event receipt log at each and every witness and the controller.

When network bandwidth is not too constrained then a gossip protocol might be a faster but still efficient mechanism for disseminating the events and receipts. A directed acyclic graph or other data structure can be used to determine what needs to be gossiped.

The purpose of having N designated witnesses is to better ensure trustworthiness of the service in the event of faults. In addition to faults such as unresponsiveness and network interruptions, allowed faults include what are commonly known as Byzantine faults such as malicious or du- plicitous behavior (dishonesty) by the witnesses. Dishonest witnesses may neglect to forward or store event receipts. Nonetheless, as long as the controller is honest and at any time any M of the N witnesses are non-faulty then for any given event the controller will eventually have a signed receipt with at least M+1 signatures in its event log (one from cach of M witnesses plus one from itself). Likewise given the same conditions, for any given event, eventually each of the non- faulty witnesses will have a signed receipt with at least M+1 signatures in its cvent log. The ser- vice is trustworthy because access by any validator or judge to a receipt from a witness on a giv- en event enables the detection of later collusion or duplicitous behavior by that witness in an ex- ploit on that same event. Events from an altered key event history produced by an exploiter will not be accepted by any witness who had previously logged a different version of an event. Con- sequently a successful exploit must exploit not merely one or more of the controller’s keys but must also exploit M witnesses. This significantly increases the difficulty of exploit. To minimize

11730

the risk of exploit a controller should take care to select N witnesses that are independent and have a small likelihood of colluding to defraud.

We define a complete key event receipt log as one where each key event receipt in the se- quence has at least M-+ signatures (one from each of M witnesses plus one from the controller). ‘With an honest controller where M of the N witnesses are non-faulty at any time, a judge or val- idator is guarantced to be able to eventually obtain from the service a complete key event receipt fog from any one of the non-faulty witnesses. A complete key event receipt log is also im- mutable by construction.

The important result s that at any time the service with provide access by a validator via one of the non-faulty witnesses to a complete key event receipt log that will enable it to validate the controlling keys of the associated identifier over the time-frame of the events in the complete log. A complete key cvent receipt log may also be provided by any entity that has retained a copy of it not merely the witnesses. Subsequent exploit of the keys or exploit of any or all of the witnesses or the controller may not exploit any of the events in the complete key event receipt log. The following diagram shows the offline key event infrastructure.

1280

; [ T EenVeder i CEREALaTA . Offine Any-wise H : ofamgn || % { : . i | i 61 T e | EntiyA E VELIER! oA ety vl fnfr i it eor et Cortr [} | et | i T ReeRLaA i 3 KERL oA iy B[ veemwe [ ey o v i i HERI l H oo 13 i L e L et Tl e [ v { T ) Winess 3 H oy Emileg | | £ oo : | T | e L e e, Figure 2.3. Offline Any-wise A to Whoever To summarize, in order to fool a validator or judge into accepting an crroneous or cxploited key cvent history, a successful exploiter must forge a complete key event receipt log but with a different sequence of key events. To do this the cxploiter must not only exploit one or more of the controller’s signing keys (assuming an honest controller) but also exploit M of the N des- ignated witnesses. Typically a successful exploit of a witness would involve gaining access to the witness” signing key. In rare cases, a simpler exploit could succeed if the exploit of the con- trollers key(s) happened before a witness received a verified copy of the true event. Then even an unexploited (honest) witness would assume the exploited event was valid and unwittingly collude with a st of dishonest witnesses. In order to create a complete event receipt log the ex- ploiter would still need to induce another M-1 witnesses into supplying receipts of the exploited cvent. This exploit requires a race condition where some witnesses are unresponsive long cnough for the key exploit duc to exposure to occur. This may take some time. This race condi- 1380

tion would be easy for the controller to prevent by replacing unresponsive witnesses. This miti- gation is discussed later.

‘The assumption of an honest controller means the the validator must trust the controller. This is a reasonable assumption in many cases. It it usually in the best interests of the controller to act in a trustworthy manner with respect to its own identifiers. Furthermore because cach key event must be signed by the controller any inconsistent key events would be detectable by any valida- tor that eventually had access to both events. This would destroy both the trustworthiness of the controller with respect to that identifier and any value it may have built up in the identifier. Be- cause the main purpose of key rotation is to allow a controller to maintain persistent control over an identifier, detectably inconsistent behavior removes any benefit of persistent control of a giv- en identifier.

Nevertheless in cases where duplicity provides some temporary benefit, a controller might be tempted to act dishonestly (or equivalently an exploited might be tempted to fully exploit a con- troller). One way to mitigate the risk to & validator of a dishonest controller is for the validator to require that the witness pool include witnesses that the validator itself trusts. A validator might provide to the controller the identifiers of the set of trusted witnesses. The validator would then only aceept an identificr from the controller if the controller designates one or more of the val- idator’s trusted witnesses as witnesses to the key event receipt history of the controller’s identifier.

Nevertheless, when M is less than a majority of N, a dishonest controller or fully exploited controller might be able to induce different disjoint subsets of 4 witnesses into each eventually producing a divergent (inconsistent) but complete (and immutable) key event receipt log for the same identifier. This might be used to temporarily create a race condition that the dishonest con- troller may be able to exploit. Any validator, judge, or witess, however, merely needs to anony- ‘mously query more than M witesses to detect the inconsistency. This limits the exploit potential of a dishonest controller albeit at some cost to the participants.

Requiring that the number of non-faulty witnesses M be a majority of N at any time adds an additional property that will prevent a dishonest controller from ever inducing the creation of more than one version of a comple

te key event receipt log for a given identifier. When M is a ‘majority of N'then in order for two inconsistent key event receipt logs (different sequence of key events) to be created an honest witness would have to create a receipt for two conflicting ver- sions of the same event which an honest witness would never do. Consequently, no other com- plete log may be created with a different sequence of events despite a dishonest or fully exploit- ed controller because at least one of the M witnesses must be honest. To see how this is so, consider that if M is a majority of N and M witnesses are non-faulty then the number of faulty witnesses ¥ must be less than A4, that s,

F=N-M<M @

A complete event log will also be correct whenever there may not be any other complete event log with a different sequence of key events. This will be true when M is a majority of N. To re- state, & complete event receipt log is also a correct event receipt log when completeness requires that cach event receipt s signed by a majority of the witnesses.

When M is a majority of N then even despite a dishonest or fully exploited controller, the ser- vice may either only produce a correct event receipt log or only produce incomplete event re- ceipts logs but may not produce multiple complete but divergent event receipt logs. In other words, should the service ever produce a complete event receipt log then that event receipt log will also be correet. In the case of an honest controller then the service will produce at least one correct event receipt log which may be provided to a validator by any of the latest set of M non-

1430

faulty witesses. When the controller is responsive it will also produce a correct event receipt log which it may provide to a validator.

‘The most important result is that when 3 is a majority of N where M witnesses are non-faulty at any time, then the service will either provide to a validator or judge a correct and complete key event receipt log (when the controller is honest) or it may not provide a complete log at all (much less correct). This protects the validator from a dishonest controller. A correct log enables validation of the controlling keys of the associated identifier over the time-frame of the events in the log. Once produced a correct key event receipt log may be provided by any entity that has re- tained a copy of it not merely the witnesses. Subsequent exploit of the controller’s keys and/or exploit of less than M of witnesses may not invalidate any of the events in a correct key event re- ceipt log. Moreover, even in the extreme case that a full exploit of the controller and all the wit- nesses has occurred and given that they produce a correct but divergent event receipt log, a prior copy of a correct key event receipt log will enable detection and proof that an exploit has oc- curred. In this extreme case some other mechanism may be used to resolve the production of more than one complete but divergent event receipt log. This might be through an anchor trans- action to the event log on a distributed consensus ledger to establish priority of the original event sequence. This approach minimizes the use of a distributed consensus ledger to only that of re- solving the most extreme and unlikely cases.

Moreover, distributed consensus algorithms employed by blockehain ledgers, typically, require ‘multiple rounds of exchanges between replicants (members of the consensus pool) in order to come to consensus. In some protocols cach round requires a mumber of exchanges that scales with M. In contrast, the witnessed key event receipt log algorithm presented here is much more scalable because the algorithm only needs two rounds of receipt exchanges between the con- troller and witnesses for cach new event. The total mumber of exchanges scale with as little 2. Using a gossip protocol and/of DAG for this algorithm may allow very efficient tradeoffs be- tween throughput and network bandwidth. In gencral the requirements for this witnessed proto- ol are much less than that of a distributed consensus ledger and hence a much more minimally sufficient

means for decentralized key management infrastructure (KERI for DKMI) even in cases of extreme exploit 223 Judge

Validation by a judge of an event receipt log adds additional security. Like a witness, the judge first verifies the controller signatures and event content for each event. The judge also verifies all the witness signatures for cach cvent and validates that there are at least M verified witness signatures. The operation associated with the event is now in force or active until it is superseded by a later event. The result of the operation is now applied when verifying subsequent events in the log, If an event is not complete (i.¢. does not have at least M verified witness signatures then the validation stops and the associated key event receipt log is deemed invalid by the judge. A given implementation of a judge may apply additional rules to resolve the rare case of full ex- ploit of the controller and 3 wilnesses (hat may thereby produce multiple valid complete but di- vergent key event receipt logs. The judge may use the first received or resort to some other trust source including other judges. This could include a median time stamp of the astronomical time at the time of reception of the inception event or some other consensus algorithm with respect to other judges such a distributed consensus ledger

1580

2.3 Representations 23.1 Key-pair

Each entity uses its own identifier when participating in the protocol. That identifier is repre- seated with an upper case letter symbol such as 4, B, C ete. Each identifier has a a controlling (public, private) key pair. Without loss of generality that key pair is represented with the same letter symbol as the entity’s identifier but where the public key is uppercase and the private key is lower case. For example, entity A has a key pair (4, a) where A denotes the public key and & denotes the private key. Successive controlling key pairs are indicated with a superscript. For example (4, a") for the initial key pair and (4", a') for the next pair. When it is not important to distinguish which key pair is used but merely to indicate that the latest valid or authoritative key pair is 10 be used whichever index it may be then the superscripts are lefl off. The key pair then becomes (4, a). Usually the context determines which member of the key pai, the public key for verification or private key for signing, is to be used. In those cascs, without loss of clarity only the uppercase may be used to represent the appropriate member of the key pair. 23.2 Entity

Individual entities that are members of a class of similar entities may be represented by a sub- scripted uppercase letter symbol where the letter symbol denotes the class and the subscript de- notes the member. Suppose for example that C denotes the class of controllers. Then Cy and C; denote two different controllers. This convention may be combined with superseripts to denote successive controlling key pairs for cach controller, such as, (CJ,c}) and (C;,¢;) for the first two key pairs of C,, and (CY,c!) and (C!,c) for the first two key pairs of C, . Likewise (Ca»y) for the latest key pair of Cyand (C, ,¢; ) for the latest key pair of C, 23.3 Serialized Data

A data structure with ordered fields may is represented by a tuple where the tuple is denoted with parentheses about a comma separated list of ficld names, such as, (¢,4,C). A serialized version of that data structure is denoted with angle brackets about comma separated list of the field names, such as, {1, A,C). In general a tuple may be converted to a data structure with la- beled key value pairs. Ordering is important when serializing. 23.4 Signature

A digital signature operation is represented with the lowercase greek sigma, @ where the sym- bol of the signing key pair is provided as a subscript to the sigma

and the serialized data or text is provided as the argument to the signing operation. For example, the digital signature for cntity 4 may be denoted as follows:

as({nAC)), @2) where the signing key is the private key from the key pair, (4°,a") controlled by 4 and the signed text is the serialized data structure, {t,A,C}). When appropriatc an alternative form would use the lowercase symbol for the private key instead, as follows; o, ((n.4.C)). @3 1680

But as stated above when there is no doubt as to the context, the uppercase symbol may be used to represent the appropriate member from the key pair. A message that includes both a serialized data structure and an attached signature may be denoted as follows:

(1.4,C)0,.({1.A.C)) @4 A message with two attached signatures, one each from entities 4 and B may be denoted as Follows:

{1,4,C)o . ((1.A4.C))a((1.4,0)), @5) where the signing key for B s the private key from the key pair, (B",5°) and the other parts are as above. Without confusion, in the expression above the arguments to the signing operations ‘may be redundant. Therefore a more compact form of the preceding expression may be denoted as follows:

(1.A.C)o .0, 2.6) Expressions eq. 2.5 and eq. 2.6 are equivalent. When the attached signatures use the latest key pair from both 4 and and B then an even more compact form of cq. 2.6 may be denoted as Tollows: (1.A,C}0,0, @7 235 Event When the message is a key event message for an identifier then the greek epsilon, £ may be used to label the event with a subscript representing s position in the event sequence, such as, &, When the particular identifier the event belongs t0o is not provided by the context then the &, is used as a subscript on the symbol representing the identifier, such as, A, . For example a key event message for identifier 4 might be labeled as follows: {t.AA" Ao =, =&, @38) 23.6 Receipt Areceipt of a key event message consists of that key event message together with an attached signature made by a witness of that event message. A key event receipt may include other infor- ‘mation such as the identiffer of the witness and/or the witnesses public key needed to verify its signature. In general a witness may use a specific identifier for a given KERL (key event receipt log). Should the keys for the identifier become compromised the witness may recover from the compromise by cither rotating the compromised key and resuming operation as a witness under the same identifier or cease acting &s a witness using that identificr. An exploiter may not change previously created receipts and inconsistent receipts from the same witness will invalidate the witness. In the later approach the witness may resume acting as a witness but under a new identi- fier and must therefore recreate all its receipts using the new identifier. Although cither approach may be made to work, the later approach avoids recursive rotation validation of KERL entries (where the

KERL entries of witnesses to a controller are validated and then the KERL entries of witnesses the witnesses arc validated and so on). Recursive validation complicates the imple- ‘mentation. Consequently, without loss of generality, in this work witnesses may not rotate keys associated with their identifiers but must create a new identifier when exploited. Let W, repre- sent a witness that uses its only signing key pair. A minimal receipt created by W, of event A, may be denoted in long form as follows 1780

U 0 4ty U 041y ({14,478 ((1,4,4% 4 o (1. 4.4, 4') o ({1,8,47,47) @9 where G, ({1, 4,4, ') ({1, 4, A", 4"))) s the the digtal signature created by W, using its key-pair (W,, ,) of the key event {1, 4,4",4")o . ({1, 4, A", A'}). The second set of enclosing brackets in expression eq. 2.9 indicates what text is signed by G, . The equivalent short form of this receipt may be expressed as follows:

{(1.4,4,4"0 )0y, @.10) where the second set of enclosing brackets once again indicates what text is signed by o1, . An even shorter form would use the event label A, =€, (when 4 is given by context) as follows:

(4, )ou, = (&), @1 Areceipt of the same event signed by two witnesscs, W, and W, may be represented in short form as follows: ({44, 4%0 10,0, =(4, }0,,0, = (&, }0,.0, @212) Areceipt may be labeled with the lowercase greek rho, p with subscripts representing the wit- nesses who created the attached signatures and the argument of the receipt being cither the asso- ciated key event or ts label. This gives the compact receipt label form as follows: o (14 4%, 80, )= ((1,4,4°, 4')0 )01, 0,, @13) or the extremely compact receipt and event label form as follows: Puw (4,)=(A, )on0n = ({1,440, 4')0 )0y, 00, @14 or when the context gives us 4 then

Pr (&) ={E0 )00 @.15) 2.3.7 Receipt Message

Akey event receipt message conveys information about the receipt. Typically the recipient of a key event receipt message already has a copy of the associated key event message. Consequently there is no need to retransmit a copy of original key event in the receipt message. Likewise the recipient of the receipt may know the identity of the sending witness and thereby its public key. ‘The only required element is the witness’ signature of the key event. Nonetheless, in addition o the signature it may be convenient to include in the receipt message the identifier and/or public key of the witness and a label of the event. This makes the message bigger but may be casier to track and manage especially with an asynchronous communications channel. For a witness identifier W, that is bound to (W;',w}) its key cvent reccipt message may be cxpressed as follows:

{1, Wo0,,) (2.16) wheret, is the label of the associated key event, W is the witess’ identifier, and o, is the signature of the associated key event, The message itself does not need to be signed by the witness because the only important information the message conveys is that the witness

13730

“witnessed” the associated key event, The witness” signature is non-repudiable so a verified copy of the signature is sufficient to convey that information. In order to verify the signature the recipient of the message needs to have a copy of the original key event message and know the signature’s verification (public) key. The event label and witness identificr and in the receipt message enable convenicnt lookup of that information.

23.8 Digest

The digest of a key event message is string of characters produced by a cryptographic hash function that is a space efficient but unique fingerprint of the content of the message. A signed digest is a commitment to the message content. The serialized data or text is provided as the ar- gument to the hash function. A digest may be labeled with the lowercase greck eta, 17. A digest of serialized data structure {t, 4, A°, A') may be denoted as:

n((r.4 4%, 4%). @17

A digest of a full event message comprised of a serialized data structure and an attached signa- ture may be denoted as follows:

((r.4.4% 40, )=n(4,)=n(e,), @18) where ({1, 4,A°,A'}o, = A, =&, are various denotations of the event message. 23.9 Single and Multiple Signature

‘The descriptions so far have assumed that the current control authority over the identifier at any point in time is based on a single key-pair. One way to increase security is to use a multi- signature approval schemes where mulfiple simultancous key-pairs jointly control the identifier. ‘This would require multiple signers to authorize or approve key management events and verifi- able attestations associated with the identifier. Multi-signature approval may add an extra layer of security thereby making exploit more difficult. They may also lessen the risk of loss of a sin- gle private key and make key recovery more robust. Multiple signature rotation, however, can be somewhat complex. To simplify and clarify the descriptions of both the single and multiple signature versions of the protocols some terminology is introduced i this section.

The sequence of key-pairs used to control an identifier may be denoted with integer index / , such as, (C7,c’). The zeroth index, where j=0, indexes the originating key-pair,(C",c"), whose public key, C" is bound to the identifier C and controlled by private key ¢”. A sequence of indexed public keys may be used to represent the sequence of key-pairs as follows:

XN @19 where Cis the j* public key in the sequence for a controller labeled C.

‘The

sequence of rotation operations may be denoted with integer index /. Each rotation opera- tion changes the controlling key-pair(s) for the identifier. When the controlling key-pair is singu- lar, then each rotation consumes one new key-pair from the sequence. In this case, the indices of the key-pair sequence and rotation sequence will have the same value, that is, j=/. In this nota- tion the key-pair (C',¢') is also the I* key-pair in the sequence of key-pairs controlled by C. When the controlling key-pair is not singular, however, (i.e. multi-signature) then each rotation operation may consume more than one key-pair from the sequence of controlling key-pairs. In this case then the indices j and / may not always be equal, i.c. j#1. Let the number of control-

1980

ling key-pairs for the £rotation be denoted Z,. The I rotation thereby consumes L, key-pairs from the sequence of controlling key-pairs. The key-pairs consumed by the /* rotation form a subsequence of length Z,. The subsequence of indices j for the subsequence of key-pairs for the rotation / of length Z, may be denoted as follows. [ror+Lr+2, . n+L-1] (220 where , is the value of index j for the first key-pair in the subsequence. This means that ha=nt. @21) The originating key-pair (C”, ") is declared by an inception operation that creates the identi- fier C. The inception operation may be thought of as a special case of rotation that s the zeroth rotation operation, that s, =0 . Also let r, =0 be the value of the first index from the inception o zeroth rotation. Given that 7, =0 then the value of the index , for />0 may be computed by summing the lengths, Z,, of subsequences of key-pairs consumed by all the prior rotations. This may be expressed as follows: (B @) where 1, =0. ‘The subsequence of public keys for the I* rotation may be denoted as follows: [crem], (223) with [c*],=[c"] (224 Suppose for example that the inception uses one key-pair, that is, Z,=1and the following three rotations use three, three, and four key-pairs respectively, that is, L, =3, L, =3, and L,=4. The resultant starting indices for cach rotation subsequence are as follows: =0 YA ,l:Zfl,}:lfiL =4 . (2.25) - :2"(‘1_‘:1“1_‘”1:7 =Y L=L+L+L+L=11 Furthermore the resultant subsequences of public-keys for cach rotation in order are as follows: (] =[] [cr.cc] =[c.c’.c"] o 226) [crem o] =[chcf.cf] [er.cm e, o] <[, e8¢0, 0] 2080

With the nomenclature presented above we can now more efficiently describe the protocol 2.4 Miscellaneous 2.4.1 Sufficient Majority

Some parts of KERI are dependent on what is called a sufficient majority. Given an allowed ‘number of faulty members F, the number of sufficient majority of members M less than the total N may be pre-determined. The smallest possible majority is called a simple majority. The simple majority M For N members is given by,

M:ml[%]fl, @27 where the value of the int() function is the nearest integer less than or equal to its argument. In some cases a sufficient majority is a super majority that is greater than a simple majority.

‘The set of entities that form a sufficient majority is called a quorum. If N is the number of entities and A is the number of a sufficient majority of N then the number of possible quorums is given by the number of distinct combinations of N taken M at a time. This is represented as, | cavmy=—2__ 228 MN-M)

Typically at each stage of processing of any given event, an algorithm may require that a quo- rum of members participate in making a decision. The members of the quorum at one stage may be different from the members of the quorum at another stage. Quorum membership at any stage, however, may be a universally verifiable item of knowledge. Changes in quorum member- ship are provided by rotation events that also change quorum membership. These are therefore quorum membership evenis.

2.4.2 Sequence Numbers

Each event has a unique monotonically increasing sequence number. This may be used to or- der sort, index, and organize events. In the following messages the field label 1 is used to repre- sent the sequence number with a numeric subscript to indicate the order of sequence number such s f,,1,....,1,. A simple format for ¢ is a counter with integer values starting at 0 that incre- ment by 1 for each new event. When the sequence number is a counter then the subseript value of £ will equal the value of the sequence number, that is,

1=, (2.29) and 4=0,6=1t,=n (230 243 Date-time Stamps

It may be convenient to include absolute (real, astronomical) date-time stamps in messages or log entries. One well known date-time format is the ISO-8601 standard [11; 12]. An ISO-8601 time zone aware UTC date time stamp with up to nanosecond resolution has the following form:

YYYY-MM-DDTHH:MM:SS. mmmmmmmmm+00:00 @31

An example is

2000-01-01T00:00:00.000000000+00: 00 @32) 2180

2.4.4 Cypher Suite

Best practices cryptography limits the options that user may choose from for the various cryp- tographic operations, such as signing, encrypting, and hashing to a suite of balanced and tuned set of protocols, one for cach operation. Each member of the set should be the one and only one best suited to that operation. This prevents the user from making bad choices. Many key-repre- sentation schemes allow the user the freedom to specify the features of the operation indepen- dently. This is usually a very bad idea [4; 23; 24]. Users should not be custom combining differ- ent features that are not part of a best practices cypher suite. Each custom configuration may be vulnerable to potential attack vectors. The suggested approach i o narrowly specify a single cypher suite family and version for each operation. If an exploit is discovered for a member of a suite and then fixed, the suite is updated wholly to a new version. The number of allowed cypher suites should be minimized to those essential for compatibility but no more. This approach in- creases expressive power because only one syntactic clement is needed to specify a suite instead of a different clement per feature.

In the following event expressions a particular cryptographic system or cypher suit for creating the signatures is cither assumed known or else is explicitly specified. A suggested specification format is that described in the W3C DID (Decentralized Identifier) report for the fype field in the authentication section of a DID Document [25]. This is single string that includes a cypher suite family, operation, and version. For example the family = Ed25519, operation ~ verification, and version = 2018 may be expressed as follows:

Ed25519VerificationKey2018 (233)

One way to specify the cypher suite is to include an additional kind field in cach message with a value (cypher suite type) as given above. The problem with that approach is that all the public keys must use the same kind. This does not allow support for rotations that change or upgrade the cypher suite nor does it support a mixture of cypher suites for multi-signature schemes. In ‘general, the approach used herein is to treat each occurrence of a public key field in a message as a data structure that may optionally include the cypher suite type in a kind field when not us- ing the default cypher suite kind if any. An example data structure in JSON follows: (

key: "Xq5YqaL6L48pf0fu7TUNLOJRAU2_RxFPOALA3wYn148=",

kind: Ed25519VerificationKey2018 } 2.4.5 Encoding

Public keys, signatures, and digests are large integers. They must be encoded in order to be consistently represented when stored, transmitted over networks, or included in serialized data structures that are signed or hashed. A suggested approach is to use the RFC-4648 Base64 URL- File Safe encoding standard. as per RFC-4648 [13] to encode these items. The contents of the ‘messages in this work are intended to be processed by computer algorithms and not transcribed by humans. Consequently Base64 is more appropriate and more compact than other representa- tions such as Base58-check. The main advantage of Basc58-check is that i i less prone 1o error when manually transcribing. Because this behavior should be discouraged in general Base38- check is more cumbersome, Base6d is preferred.

2.4.6 Serialization

A suggested approach for serializing data structures or tuples is to use the JSON standard. One

of the limitations of JSON is that the field order of a serialized JavaSeript object is not norma- 2280

tive, that is, a valid JSON serialization does not guarantee the order of appearance of the fields within a JavaScript object (or Python dict) that results from the deserialization. Likewise white- space in a JSON serialization is not normative. Consequently round trip serializations and dese- rializations may not be identical and therefore would not verify against the same cryptographic signature. This is the so called canonicalization problem. One simple solution to this problem when using JSON is that the data associated with a signature may only be serialized once by the signer. Users of the data may deserialize but never re-serialize unless they also re-sign. Any compliant JSON deserialization will produce an equivalent Javascript object (same field names and values but order and whitespace are ignored).

2.4.7 Signatures

In many protocols the signatures are attached to the serialized data in one data string. This en- counters another limitation of JSON, that is, many JSON implementations raise an error if a de- serialization attempt on a string does not consume al the characters in the siring. Thus a hybrid data sring that consists of a serialized JSON object followed by a signature siring might be diffi- cult to deserialize with some JSON implementations. A portable approach, however, is to con- catenate the signature but separate it from the JSON serialization with a unique string of charac- ters that will not be produced by a JSON serializer. A parser first scarches for the separator string and then separately extracts both the JSON serialization and the signature. One such human riendly separator string is the 4 character sequence of whitespace characters, CR LF CR LF (in ascil notation), where CR represents the CarriageReturn character (ASCII 13) and LF represents the LineFeed character (ASCII 10). In escaped notation this string is "win'rin'. If these separator characters were to appear within a quoted string they would be doubled escaped by the JSON se- rializer. Furthermore, this separator string does not appear in a Base64 serialization. Consequent- ly this same separator can be used to attach multiple signatures. This approach makes it easy for a parser o separate, extract, and verify the serialized data with the attached signature(s) without deserializing the JSON. In this work serializations consist of the JSON followed by one or more sets of the separator "\in'rin' and a JSON string delimited (double quoted) Base64 scrialization of a si

gnature. An example follows:

[ "id": "Xq5YqaL6L48pfOfu7IUhLOJRAU2_RxFPOALA3wYnl48=", "sat: 1, "kind": “ek”, "signer”: "Xq5YgaL6L4BpfOfu?TUNLOJRAU2_RxFPOALA3wYnldg=", "ensuer™: "Qt27fThWoNZsaB8VrTkep6H-4HABtr54sHONLVWLEFE=" } Ar\nyrn "AeYbsHoLOpmAWACGTo55D8 1 AUSQA L nH5U6W] TGPVNIQQOYKBY rPPxA0TC1 i 5SHT IDSBKFFg£81i0tDg8XGizaCg=="

When using HTTP as the transport it may be more convenient to attach the signatures in an HTTP Header. One way to do this is with a custom header. The format of the custom Signature header follows the conventions of RFC7230 [10]. The header format is as follows: Signature: headervalue Headervalue:

tag = "signature" 2380

or

tag = "signature"; tag = "signature" ... where the name of each tag is given a unique string to identify each signature. Each signature tag value is a doubly quoted string " that contains the actual signature in Base64 url safe format. An optional tag named type may be present of the form:

kind = "kind" where the value of the kind tag is a string that specifies the cypher suit type used to create the signature(s) within that header. All signatures within a header must be of the same cypher suite type. Multiple Signature headers may be present and the set of signatures are the union of all the signatures from the Signature headers. If the same signature tag appears multiple times then only the last occurrence is used.

An example is shown below with a kind tag, one signature tag named “signer” and the other signature tag named “ensuer”.

Signature: kind="Ed25519VerificationKey2018";signer="Y5xTb0_jTzZYrf5SSEK2f3 LSLwIWhOX7GE]6YfRWNGViKAesa0BUkNWukUkPGuKuu-EAESU- sdFPPboBAsiRBw=="; ensuer="Xhh6WRGIGgjUSV- ©57g74HcIB87LLONQr2Sqg5VIoTSg- SI1W3AB1gISxOjATSpa2gnonyz3tpGuC2ems 1VTpBg=="

‘The convention is that cach signature tag name must equal a field name in the JSON body. The associated JSON field value is the public key used to verify the signature provided in the corre- sponding header value.

2.4.8 Event Ilk

It may be convenient to include in_ key events a key event lk field that specifies what type of event the message contains. This may aid in parsing the event message. The suggested field name is ilk. Suggested ilk values and events are as follows: icp for inception event, ot for ro- tation event, zct for event receipt message, itc for generic interaction event, dip for dele- gated inception event, drt for delegated rotation event, dwd for domestic witness designation event, and £wd for foreign witness designation event. Specific applications may use other event ilks.

3 ONLINE ONE-TO-ONE PROTOCOL

In this version of the protocol there are no declared witnesses. The defined events reference entities with identifiers that are bound to key-pairs. A controller has an identifier labeled C that is bound to a key-pair (C°, ¢"). Likewise a validator has an identificr labeled ¥ that is bound to a key-pair (V*,+"). Because the likelihood of collision of public keys generated with crypto- ‘graphic strength digital key systems is remote, therefore, with loss of generality, in the event de-

2450

scriptions below, the identifier bound to a key-pair may be equal to the public key. For example, C=C® and V=V". Using only the public key enables the core parts of a KERI implementation to be independent of the syntax for specific types of self-certifying identifiers. In the case of DIDs this means that the KERI core may be DID method independent. Indeed the KERI core may be made independent of any identifier syntax other than that the identifier be uniquely bound to a cryptographic strength signing (public, private) key-pair. The universally unique identifier for the core may be set cqual to the public key and identifier specific syntax for other sections of the identifier may be handled by an identifier specific client.

It is also assumed that the cypher suitc fype used to generatc signatures is cither known or cls cach appearance of a public key (when not the basc identificr) in the cvents is actually a data structure that includes the public key and an optional cypher suite fype when it is not the default type (sce the discussion in Section 2.4). This caveat applies to the public keys referenced in the events below.

In the following event descriptions, the index & indexes all events of any ilk and index / index- es only rotation events. In general the k" event may not be the same as the (" rotation event, Only when the all events are rotation events will &=/ . The inception event is special it always has k=[=0. The inception event is considered a special case of a rotation event. Other events may be interspersed between the inception event and the first rotation event as well as between subsequent rotation events.

There are two types of events, these are chained and unchained. Chained events include a di- gest of the previous event (except the inception event). To avoid redundancy, because, the only difference between chained and unchained events is the inclusion of the digest field in chained events, the event definitions will provide a full description of the chained version but only pro- vide the denotation of the unchained version. The inception event has no digest because it is the first or zeroth event in the sequence. The digest backward chains the events and reinforces the sequence ordering provided by the sequence number (see Section 2.8). Some applications where economy of expression is more important than security may choose to use the non-chained ver- sions of the protocols. To restate, when chained the order of events is provided by a

sequence number but reinforced with a backward chained digest. The sequence of digests and the se- quence number must correspond.

3.1 Single Signature

In this scheme only a single key-pair controls the identifier at any time. A multi-signature scheme is provided later. 3.1.1 Inception Event

Given a controller with identifier labeled C the serialized key inception event message labeled C,, is denoted as follows:

£,=C, ={C,t,.icp,C",C")o., 3.1

where the identifier C is uniquely bound to the key-pair (C",c"), £, =0 is the unique monotoni-

cally increasing sequence number for this event, icp is the event ifk representing an inception

event, the controlling signing key-pair is indicated by C”, which is the public key from the key-

pair (C°, ") that is controlled by the private key, ¢’ the ensuing pre-rotated key-pair is indicat-

edbyC' which is the public key from the key-pair (C',c')that is controlled by the private key, 2580