Papers

Key EVENT RECEIPT INFRASTRUCTURE (KERI) DESIGN = Samuel M. Smith, Ph.D. v2.63 2025/09/14, original 2019/07/03

Abstract—An identity system-based sceure overlay for the Internet is presented. This includes a primary root-of-trust in self-certifying identifiers. It presents a formalism for Autonomic Identi- fiers (AIDs) and Autonomic Namespaces (ANs). They are part of an Autonomic Identity System (AIS). This system uses the design principle of minimally sufficient means to provide a candi- date trust-spanning layer for the internet. Associated with this system is a decentralized key ma- nagement infrastructure (DKMI). The primary root-of-trust are self-certifying identifiers that are strongly bound at issuance to a cryptographic signing (public, private) key-pair(s). These are self-contained untilfunless control needs to be transferred to a new key-pair. In that event, an ap- pend-only chained key-event log of signed transfer statements provides end-verifiable control provenance. This makes intervening operational infrastructure replaceable because the event logs may be served up by any infrastructure, including ambient infrastructure. End-verifisble logs on ambient infrastructure enable ambient verifiability (verifiable by anyone, anywhere, at any time). The primary key management operation is key rotation (transference) via a novel key pre-rota- tion scheme. Two primary trust modalities motivated the design: a direct (one-to-one) mode and an indirect (one-to-any) mode. The direct mode depends on append-only verifiable data struc- tures called key event logs (KELS). The identity controller establishes control via verified signa- tures of the controlling key-pair(s) on each event. The indirect mode depends on witnessed key event receipt logs (KERL) as a secondary root-of-trust for validating events. This gives rise to the acronym KERI for key event receipt infrastructure. The indirect mode extends that trust basis with witnessed key event receipt logs (KERL) for validating events. But for short we call both types of logs key cvent logs or KELs. The security and accountability guarantees of indircct mode are provided by KAWA or KERI’s Algorithm for Witness Agreement (KAWA) among a set of witnesses. The KAWA approach may be much more performant and scalable than more complex approach- es that depend on a total ordering distributed consensus ledger. Nevertheless, KERI may employ a distributed consensus ledger when other considerations make it the best choice. T

he KERI ap- proach to DKMI allows for a more granular composition. Moreover, because KERI is event- streamed, it enables DKMI to operate in stride with data events streaming applications such as Web 3.0, IoT, and others, where performance and scalability are more important. The core KERI engine is identifier-independent. This makes KERI a candidate for a universal portable DKML Index Terms—Secure Overlay, Trust Spanning Layer, Autonomic Identifier (ALD, Autonomic Identity System (AIS), Autonomic Namespace, Decentralized, Key, Vianagement, Infrastructure, Key, Fxent, Receipts, Pe-rotaion, Rotation, Event, Streaming, DKMI, KERI, KERL, KEL, KAWA, KA2CE, KERI’s Agreement Algorithm for Control Esablishment Post Quantum Securiy, Slf-Soversign dentiy. 1 INTRODUCTION

‘The major motivation for this work is to provide a secure, decentralized foundation of trust for the Internet as a frustable spanning layer [7; 24; 42]. A major flaw in the design of the Internet

1. hpssarivorgiab 1907.02143

2 hpserione

12

Protocol was that it had no security layer. There is no built-in mechanism for security. Anyone can forge an IP (Internet Protocol) packet. Specifically, the IP packet header inchudes a source address field to indicate the IP address of the device that sent the packet [81]. Because the source address may be forged, a recipient may not know if the packet was sent by an imposter. This means that seeurity mechanismes for the Internet must be overlaid (bolted-on). 081 Mode! 1P Model Applcation Aoplcaton Presentaton Aubenicaon | Session Transport Tanspot | ToP,UDP Network Nework | p ik ik Physical Figure 1.1. OSI vs IP Protocol Stack. IP stack s missing both the session and preseniation layers that provide sccurity (authentication). Without a built-in security layer, IP security must be provided by bolt- onidentity sysiem sccurily overlays.

A typical Internet sccurity overlay is based on some form of an identity system that leverages the properties of asymmetric public-key cryptography (PKI) [117]. The purpose of the overlay is to establish the authenticity of the message payload in an IP Packet. The following diagram shows the basic concept.

keypair |« ~{ enity systom mapping |« ~{ dontr | Vessage Verfbl Payod

identier | data signature | Figure 1.2, Idenity System Security Overlay. The authenticity of a verifiable packet payload is derived from a mapping between an asymmetric key pair and an identificr. The aached digita] signaturc exclusively (non-repudiably) associates the verifiable payload to the holder of the private key from the key-pair. The overlay's sccurity is contingent on the mapping’s security.

In general, with such a security overlay, the message payload inside an IP packet includes a unique identifier provided by the identity system that is exclusive to the sender of the packet. ‘The payload is signed with a digital signature generated by the private key of a (public, private) key-pair. This signature is atiached to the packet. The identity system provides a directory that links or maps the public key from the (public, private) key pair to the sender identifier. A valid signature verifies that the packet came from the holder of the private key. The mapping between identifier and public key establishes that the message came from the holder. This approach as- sumes that only a valid sender of the packet with payload has access to the private ke, i.c. the sender is the exclusive holder or controller of the private key. As a resul, the recipient

of the packet may use the identity system to look up the corresponding public key given the unique

2142

sender identifier in the packet payload and then, with that public key, cryptographically verify the signature attached to the payload. Only the holder of the private key may generate such a verifiable payload. Without access to the private key, an imposter may not forge a verifiable pay- Toad. Indeed, a more accurate label for this approach would be an identifier system sccurity overlay because identity is inimically bound to verifiable control over the identificr.

‘This sceurity mechanism ostensibly establishes that the payload in the packet came from the correct source. Ostensibly, because the strength of this establishment depends on the strength of the security of the mapping between identifier and key pair. Indeed, the overlay’s security is con- tingent on the mapping’s security.

In addition, when ordering s important, other contents of the payload, such as sequence num- bers, may be used to protect against replay of the same payload in a different packet. Notably, securely establishing the authenticity of the payload via a signature is orthogonal to ensuring that the contents of the payload are confidential via encryption. Encryption is an additional task. Confidentiality alone may be insufficient when the payload is from the wrong source.

1.1 Binding

‘The essential feature of an identity (identifier) system seeurity overlay is that it binds together controllers, identifiers, and key pairs. A sender controller is exclusively bound to the public key of a (public, private) key pair. The public key is exclusively bound to the unique identifier. The sender controller s also exclusively bound to the unique identifier. The strength of such an identifier system-based security overlay is derived from the security supporting these bindings.

controller / idenity system 5030 secury (200G overiay key-pair || binding |+~ identifier denifer ssuance Figure 1.3, Identity system as security overlay. The mechanism provides secure bindings between controlling entities, asymmetric key pairs, and identifiers.

To elaborate, typically, the associated identity systems are administrative in nature. This means the identifiers sourced from such an identity system are ultimately controlled by the associated administrator (administrative organization) of the identity (identifier) system. From a security perspective, the most important function of the administrator is (o authoritatively and usually ex- clusively permit some other entity to use the identifier. We call the p

ermitted use by an entity of an identifier a binding between the entity and the identifier. The permitted entity we call the con- trolfer (or, for short, the user). In this sense, the administrator binds that controller (user) to an identifier. This binding enables the controller to use the identifier to make mappings to resources such as IP addresses. The administrator also binds the public key from a cryptographic (public, private) key pair to this entity-identifier binding. The controller holds the private key and may prove its permitted use of the identifier by signing a statement (packet) with the private key. By virtue of holding the private key, the controller is bound to the key pair.

When the identifiers are sourced from the administrator, then their use is contingent on the ad- ‘ministrator’s continuing permission (usually by paying rent). The exclusivity and security of the

3142

bindings between controller and identifier and the key-pair and identifier are based on trust in the administrator and, by association, trust in the ostensibly secure operation of essential com- puting infrastructure to sustain and manage control over the bindings. By essential, we mean necessary to the security function of the overlay. Thus, a controller of an identifier sourced from such an administrative identity system is merely a renter of the identifier and must also rely on the operational security of the administrator’s essential computing infrastructure. Consequently, any value the controller builds in its identifiers is contingent on both continuing permission from the administrator and trust in the administrators essential operational infrastructure, enopy coiroler | capures T + / identy contoler | | seminstatr stong | 5N [ yga ) f TS F overay % gonrnes s s / \ 4 4 Sy key-pair |« weak <~ identifier keypair |« inding || identier . admin-ertiying ) Admin-Certifying dentifer Issuance (@) ®) Figure 1.4. Administrative identifier issuance and binding. The controller captures entropy to generate a key pair. Administrator issues an identifier and asserts bindings between the key pair and the identifier and the controller and the identifier. (s) The strength of administrative certfied bindings between key- pair and identifier, and controller and identifier, depends on the sccurity of the administrative infrastructure supporting its assertion. (b) Resultant weak (insecure) bindings between controller and identificr, and key-pair and identificr.

In summary, Internet security mechanisms, by and large, use some form of identity system se- curity overlay. The most well-known example is the Internet Domain Name System (DNS) with Certificate Authoritics (CAs) [40; 54]. DNS binds controllers o domain name identificrs. DNS also maps domain names such as “mail.cxample.com’” to IP addresses such as “54.85.132.205" A CA binds controllers with domain names to public keys (certificates) from (public, private) key pairs. A DNS-based URL namespace maps URL identificrs to a resource [148]. Besides DNS-CA, other identifier-based security mechanisms are in wide use. These inchude web plat- form access control systems that use usernames (identifiers) and passwords and OAuth/OpenID Connect [113]. These other identifier-based security mechanisms systems typically leverage DNS/CA.

Because DNS was bolted onto IP and CA was later bolted onto DNS, they are not well inte- grate

d from a security perspective. This has resulted in well-known exploits [69; 74]. In order to better mitigate exploits, various sccurity mechanisms have been further bolted on such as pin- ning, notarics, and DNSSEC [44; 52; 55; 71; 76; 126; 128]. All these require trust in adminisira- tively operated essential computing infrastructure and, as a result, suffer from related sceurity vulnerabilities. More recently, Certificate Transparency (RFC6962) has had some success at mit- igating cxploits of the DNS/CA security overlay [41;57; 70; 95-97]. DNS servers that employ certificate transparency maintain a global, immutable, append-only audit log of certificate au- thority activities (issuance and revocation events). The log may detect inconsistent behavior by a given CA and thereby trigger prophylactic measures by clients of servers using the associated domain names. In spitc of the mitigation potential of certificatc transparency, the DNS-CA secu- ity overlay continues to suffer from scurity cxploits that fall into the class of attacks called

w142

DNS hijacking [4; 69; 140]. A related vulnerability is BGP hijacking using AS path poisoning to spoof the domain verification process by CAs [28-30; 66]. These both enable an attacker to in- duce a CA to issue a bogus but verifiable certificate. At the time of the referenced study, a major- ity of the internet domains were vulnerable to this attack. These sorts of attacks exploit the weak binding between key-pair and identifier from trusted issuers that is inherent to the DNS-CA system.

In general, the principal weakness of current internet security overlays is that establishing the binding between key-pair and identifier via certificates relies on essential computing infrastruc- ture, which is inherently vulnerable to faulty operational administration of that infrastructure The design goal of KERI is a security overlay that does not rely on essential operational infra- structure, thereby removing that weakness.

1.2 Trust Basis and Trust Domain

In sceurity systems design, a root-of-frust is a component or process of the system upon which other components or processes are reliant. The root-of-trust has trustworthy sceurity properties that provide foundation of trust that other components or processes in the system may rely on [119]. A system may have multiple roots-of-trust. Some roots may be considered primary and others sccondary, depending on the degree of reliance on the given root-of-trust. We define pri- mary and secondary roots-of-trust as follows:

A primary root-of-rust is irreplaceable. wy ‘This means that the component that serves as the primary root-of-trust is an essential component in the system. It alone provides trust that is uniquely necessary to the system.

A secondary root-of-trust is replaceable. a2 ‘This means that the component that serves as the secondary root-of-trust is not an essential com- ponent in the system. It provides trust that may also be provided redundantly by another compo- nent. A secondary root-of-trust may serve an essential role, but the component itself is not uniquely necessary to establish trust in the system. In this case, at least one component must serve in the role, but replacement of that component does not remove frust.

Exploitable weaknesses in & primary root-of-trust may destroy the security of the associated system. Thus, good security design starts with selecting the root or roots-of-trust and includes ‘making trade-offs between cost, convenience, and security of different roots-of-trust as integra

t- ed with the rest of the sccurity system. Often, the term root-of-trust is narrowly applied to some hardware device that is sulliciently sceure that it may always be trusted. To be clear, in this work, we generalize the concept of root-of-trust t0 include all the operational elements that may be trusted, even when not very trustworthy. These all contribute to what we call the trust basis In an Internet identity system sccurity overlay, we define the trust basis thusly:

A trust basis binds controllers, identifiers, and key-pairs. 3)

A trust basis may include various roots-of-trust, both primary and secondary, as well as other operational components or processes. When the irust basis includes administratively managed essential operational infrastructure, then the security of the bindings may be dependent on the operational virtue of the administrator to support and maintain those bindings. In that case, the administrator may be considered a root-of-frust for the bindings and hence control of the identi- fier. This includes the policies and procedures that create and establish control over bindings and those that manage or govem the associated infrastructure.

Each trust basis has associated with it what we call a rust domain. A trust domain is the ecosystem of interactions between entities using the intenet that relies on a given trust basis to

s/142

imbue trust in those interactions. The trustworthiness of the trust domain (ecosystem) depends on its trust basis. We define the trust domain thusly: Atrust domain is an ecosystem of interactions that relics on a trust basis. 14 For example, the Facebook ecosystem of social interactions is a trust-domain that relies on

Facebook’s identity system of usernames and passwords as its trust basis. The following diagram illustrates the relationship between trust basis and trust domain in an identifier-based security overlay.

‘Trust Domain (Interactions)

Trust Basis (Infrastructure) Figure 1.5. Relationship between Trust Basis and Domain

The essential role of the frust basis is to enable the trustworthy establishment of control over an identifier. A common misconception is that administrative issuance of identifiers s inherently trustworthy. Careful analysis of the process of bootstrapping from roots-of-trust to trustworthy internet interactions reveals that this process is often exploitable (see, for example, the exposi- tion above for the DNS/CA system). As mentioned previously, the primary weakness of many administrative approaches to establishing or proving control over an identifier depends on a Toot-of-trust in the administrator’s management of its computing infrastructure. To elaborate, the goal of a security overlay is to eventually enable a controller to make digitally cryptographically verifiable statements referencing an identifier using universally unique cryptographic digital signatures based on a key-pair comprised of a public key and a private key (or key pairs when multi-signature) . But this first requires that one trust the binding between that identifier and the cryptographic key-pair. Usually, this binding, especially when the identifier is human-meaning- ful, is self-asserted by the administrator and therefore has a primary root-of-trust in the adminis- frator’s management or governance of its computing infrastructure [142; 155]. Thus, frust in such identifiers issued by the administrator requires trust in the administrator, and when that binding is issued in a digital way, frust in the computing infrastructure that is used to issue that binding. Moreover, the binding may be based on a manual establishment process that may re- quire direct physical interaction with the administrative entity, such as visiting the office of the administrator to obtain some form of hardcopy credential that proves a given key pair is bound 10 an identifier iss

ued by the administrator. Once the binding between an administratively issued identifier and a digital signing key pair is established, then cryptographically secure signed inter- net interactions may occur. Thus, the provenance of trust in an administrative entity is crucial Trustworthy administraive entities must go to great lengths to establish and maintain a credible provenance of trust.

When the mechanisms used to establish control over identifier bindings are not interoperable in any material way between trust bases, then the establishment of secure control over identifier bindings may be trust-basis dependent. This may be especially true of administrative identifiers. In this casc, identifiers are effeetively locked 1o a given trust basis and thereby its associated trust domain by virtue of the dependence on the administrator’s operational infrastructure used to cnsure a trustably secure binding. In other words, the binding and, hence, identifier is not portable to other trust bases. As a result, any value attached to the identifier is not portable to

142

other trust domains. Moreover, different trust bases that rely on widely differing mechanisms for establishing or proving the validity of a binding may place a large burden on any controller (user) that wishes to intcroperate concurrently with others in more than one trust domain be- cause the controller has to support the different establishment mechanisms for each trust basis. ‘This may include redundant resource instances with redundant non-interoperable identifiers on different operational infrastructures, such as both a Facebook and YouTube URL for the same video.

To restate, one of the main problems with the vast majority of identity-based security mecha- nisms arises when the bindings between controller, identifier, and key pair are both administra- tively permissioned and locked to the associated trust basis. A controller’s interactions using that identifier are thereby locked to the associated frust domain. Merely providing interoperability between trust bases (and hence domains) does not fix the administrative permissioning problem. Merely removing the administrative permissioning problem does not fix the trust domain lock- ing problem. Consequently, one goal of this work is o design a system that provides secure in- teroperable bindings (hence identifiers) that are both self-administering and portable between trust bases and their trust domains. The goal is to create bindings and identifiers that are not Tocked to a given trust basis/domain but allow the controller to move identifiers between inter- operable trust bases/domains. We believe this means that interoperable trust bases must share a common mechanism for establishing control over those bindings that thereby span both the sup- porting trust bases and the associated applied trust domains. This mechanism provides the foun- dation for a trust-spanning layer protocol.

1.3 Decentralization

Our definition of decentralization (centralization) is about control, not spatial distribution. In our definition, decentralized is not necessarily the same as distributed. By distributed, we mean that activity happens at more than one site. Thus decentralization is about control and distribu- tion is about place. To elaborate, when we refer to decentralized infrastructure, we mean infra- structure under decentralized (centralized) control, no matter its spatial distribution. Thus, de- centralized infrastructure is infrastructure sourced or controlled by more than one entity. Enities are not limited to

natural persons but may include groups, organizations, software agents, things, and even data items. This control may lic on a scale from highly centralized 10 highly decentral- ized. A centralized administratively managed identity system may be controlled by a single gov- eming organization. A governing organization might also be hierarchical in nature, with multiple subordinate organizations that operate under the auspices of the next higher-level organization. ‘The associated operational infrastructure might itself be highly spatially distributed despite be- ing under highly centralized control or vice-versa. For example, although DN is administered by a single organization, IANA, the operational infrastructure is distributed worldwide [77].

Much of the operation of interet infrastructure is inherently decentralized, but control over the value transported across this infrastructure may be much less so. Centralized value capture systems concentrate value and power and thereby provide strong temptations for malicious ad- ‘ministrators to wield that concentrated power to extract value from participants. We believe that decentralization of value transfer is essential to building trust. Consequently, a key component for a decentralized foundation of trust is an interoperable decentralized identity (identifier) sys- tem [10; 132; 133; 152]

Within a centralized identity/identifier system used as a security overlay, one entity —the ad- ‘ministrator —controls all the identifiers. In contrast, within a decentralized system, disparate entities each control some of the identifiers, but in an interoperable way. Each entity may have a set of identifiers (namespaces) that it controls but are still recognized by the other entities. In

w8

other words, each entity may be sovereign over a set of identifiers. In this case, where an identi-

fier refers to its controlling entity then that entity in that sensc is self-sovereign over its own

identifier and hence the identity associated with that identifier. Ideally, a self-sovereign identifier is one that the user issues and controls without deference to or permission from any other admin- istrative organization. The associated identity system is also, in that sense, self-administering.

This property of decentralized, self-administering identity systems has given rise to the term

self-sovereign identity (SST) [10; 127; 133; 152]. A fully self-sovereign identity system would be

highly decentralized.

To summarize, two disadvantages to participants in a centralized identity-system-based securi- ty overlay are as follows:

• Participants require permission from the administrator, often at some cost. The administrator may censure a participant.

• Participants must trust the operational infrastructure (trust basis) of the administrator. The val- ue produced by the participant may be locked to the infrastructure and/or subject to exploita- tion due to administrative vulnerability.

In either case, the participant is not ultimately in control of the value the participant brings to the associated trust domain, Whereas decentralization of the trust basis enables a more competi- tive eco-system with portability between infrastructure providers, where the choice and means to port identifiers are under participant control [129; 134].

2 SELF-CERTIFYING IDENTIFIERS We believe fully decentralized and trustable control over identifiers is best enabled by a trust

basis with a primary root-of-trust that is based on the properties of a self-certifying identifier [68;

90; 102; 103]. This concept was first described in the 1990 as a way of creating secure identi-

fiers under decentralized control. Applications include file systems and internet URLS that did

not depend on centralized DNS certificate authorities for secure control establishment. However,

the concept never achieved meaningful adoption when it was first introduced. Recent concerns over both the increasing centralization of the internet and its attendant security vulnerabilities now make the self-certifying identifier concept much more attractive. We proposed using self- certifying identifiers, called cryptonyms, for decentralized or self-sovereign identity in early

2015 [132; 133]. More recen

tly, some variations of identifiers that follow the emerging W3C

Decentralized Identifier (DID) standard are self-certifying [151]. Also, more recently, the Trust-

ed Computing Group (TCG) uses the terms “implicit identity” and “embedded certificate author-

ity to describe the process whereby device identifiers are automatically generated by the associ- ated computing device [143]. This mechanism is called the Device Identifier Composition

Engine (DICE). It generates DICE Compound Device Identifiers (DCI). These are compatible

with the IEEE 802.TAR-2018 Secure Device ID (DevID) identifier standard and the IETF RATS

standards [3; 118; 124; 154]. They also provide a type of self-certifying identifier.

2.1 Basic Concept ‘The simplest form of a self-certifying identifier includes either the public key or a unique fin-

gerprint of the public key as a prefix in the identifier. Because the public key is included in the

identifier, the identifier is strongly and securely bound to the (public, private) key pair. This

cryptographic secure binding makes the identifier self-certifying [68; 90; 102; 103].

This self-certifying property is the critical feature needed to establish a secure, decentralized, portable identity system. The holder of the private key is in sole control of the identifier because only that holder can sign statements that may be cryptographically verified with the public key

142

bound to that identifier. The holder of the private key is the controller and, by virtue of that con- trol, is implicitly bound to the identifier. Only the holder of the private key (controller) may suc- cessfully respond to any challenge to prove control over the identifier by signing the challenge response with the private key.

Aself-certifying identifier cryptographically binds an identifier to a key pair. (2.1)

The primary root-of-trust in a self-certifying identifier comes from the properties of asymmet- tic public key cryptography (public-private key pairs)[117]. To claborate, the private key is de- rived from a random seed represented as a very large random number. The degree or strength of randomness determines how difficult it would be for someone else to reproduce the same large random number. This is called collision resistance. Shannon's information theory uses the term entropy 1o describe the degree of unpredictability of a message [78]. Entropy is measured in bits.

entropy ( 4 controlier | - / idenity s (oo system (o contoler | stong | 150 [(svong ) S P owday P / . - ¢ o key-pair |« strong |« identifer key-par |+ ~[ binding |+ +| identfer f— Seff-Ceriying Identfe Issuance seltcertying (@) ®) Figure 2.1. Self-certfying identifier issuance and binding. The controller captures entropy to generate key-pair and derive identifirs. Self-certifying identificrs provide strong cryplographic binding between key-pair and identifier. (2) The strength of self-certfied binding between key-pair and identifier is eryptographic. (b) Resultant strong (secure) bindings between controller and identifier and key-pair and identifier

Likewise, the randomness of a number or message can measured by the number of bits of en- tropy in the number. A cryptographic strength random number may have as many bits of entropy as the number of bits in the number. An A-bit long base-2 random number has 2" different possi- ble values. A random seed with A bits of entropy means that there are 2" possible values of that seed.

The highest level of cryptographic security is called information-theoretic security [79]. A spe- cial case of information-theoretic security is called perfect security. Perfect security means that the cipher text provides no information about the key [79]. A crypto-system with this level of se- curity cannot be broken algorithmically. It must be broken by brute force, if at all. Brute force ‘means that in order to guarantee success, the adversary must sea

rch every combination of the seed/key.

For cryptosystems with perfect security, the fundamental parameter is the number of bits of en- tropy needed to resist any practical brute-force attack. In other words, when a large random ‘number is used as the sced/key that is the input to a crypto-system with perfect sceurity, the question to be answered is how large does the random number need to be to withstand a brute force attack against the output of the crypto-system? Assuming non-quantum computers, the conventional wisdom is that, for systems with perfect security, the seed/key input needs to have

9142

on the order of 128 bits (16 bytes) of entropy to practically withstand any possible brute force at- tack for a given output. For other cryptosystems, the size of the seed/key may need to be much larger. Given that with perfect security, no other information is available to an attacker, the at- tacker may need to try every possible value as an input before finding the correct one that results in the desired output, Thus, with N bits of entropy in an N-bit random number, the number of at- tempts or trials that the attacker would have to make will be on the order of 2", Theoretically, quantum computers, using the asymptotically optimal Grover's Algorithm, may be able to brute force a given output of a black box crypto-system where the input seed/key has N bits of entropy in as little as 2 trials [145]. Thus, once practical quantum computers exist, for algorithms that are vulnerable to Grover's attack, the size of N needed to achieve cryptographic strength would increase from 128 to 256,

Just to understand how hard it would be to brute force attack a system with a cryptographic strength of 128 bits, given available computing power, le's suppose an adversary had access to some multiple of all the world’s supercomputing resources. The aggregate performance of the top 500 supercomputers combined is estimated to be less than 2 exaflops [145]. One cxaflop is on the order of one quadrillion operations per second [63]. A quadrillion is approximately 2 = 1,125,899,906,842,624. Because a single CPU core is limited to about 4 billion operations per second the most powerful supercomputers must run many many cores in parallel. Suppose an adversary could use over a million (2" = 1,048,576) exaflop capable supercomputers. The ad- versary could then try 2 * 2 = 2" values per second (assuming that each try only took one operation). There are about 3600 * 24 * 365 = 313,536,000 = 24255559 = 2451 = 7% seconds in a year. Thus, this set of over one million exascale supercomputers could try about 2% = 2% values per year. With 128 bits of entropy in the input seed/key, the adversary would need on the order of 2% = 2 = 8,589,934,592 years to guess the right value. This also assumes that the value gained by breaking the crypto-system is worth the expense of that much computing power. Consequently, a crypto-system with N = 128 bits of cryptographic strength is practically impossible to break (pre-quantum). The term for this is computationally infeasible. To restate, a cryptographic

strength of 128 bits s strong enough that no adversary may break it by brute force attack with any practically imaginable amount of (current pre-quantum) computational re- sources, ic., it is considered computationally infeasible. Successful attacks must instead exploit some other vulnerability that exposes the private key, such as poor private key management, so- cially engincered disclosure of private keys, or a side-channel weakness in the digital signing compute infrastructure [22; 130; 137]

Cryptographic strength random numbers may be generated in various ways. A common soft- ware-based approach is a cryplographically secure pseudo-random number generator (CSPRNG) [46]. More sophisticated approaches use special-purpose hardware such as trusted platform mod- ules [146]. In any case, inexpensive methods to collect sullicient entropy 1o generate a crypto- ‘graphic strength random number are readily available. This means tha it is entirely practical for any entity to capture sufficient entropy to generate cryplographically strong random seed Morcover, once an entity captures tha entropy in a sced, no other entity may practically re- produce that seed; the likelihood is infinitesimally small. This makes the original capturing cnti- ty the sole holder, possessor, or controller over that random seed. It is thereby the sole sovercign or the sole authority over that seed. The holder of that seed obtained control of that seed by virtue of capturing entropy without deference, permission, or dependence on any other entity or authority. This is frue decentralized control.

2.2 Generating Self-Certifying Identifiers

Given current computing power, cach cryplographic operation in the process of generating the

self-certifying identifier should maintain no less than 128 bits of cryptographic sirength. Each 10142

operation is a type of cryptographic one-way finction [112]. A one-way function is relatively casy to compute going in one direction but extremely hard to reverse (invert) [111]. A one-way function with 128 bits of security would take on the order of 2'** operations to invert.

ECC scalar multiplication is a type of one-way function. Public key generation in elliptic curve cryptography (ECC) uses clliptic curve scalar multiplication as a one-way function to gencrate a public key from a private key. To restate, public key generation is a type of one-way function. Take Ed25519 keys, for example. They are relatively strong for their length and take relatively little computation to generate [1; 26; 49]. The following description uses Ed25519 as an exam- ple, but other ECC keys like ECDSA have similar characteristics [35; 58; 107; 125]. An Ed25519 private key may be represented by a 256-bit long (32-byte) number. of length (not strength) 256 bits (32 bytes). The cryptographic strength of a scalar multiplication compliant with the Ed25519 scheme using a 256-bit long scalar is no less than 128 bits [26; 89]. The rea- son the eryptographic strength with a 256-bit scalar multiplication is sill only 128 bits is that well-known attack algorithms can invert an N-bit ECC scalar multiplication in 2*7 independent trials. This means that the size of the underlying field should be roughly twice the security para- meter. Thus for 128 bits of security, the private key must be at least 256 bits in length [27; 53; 59; 75]. An ECC public key is actually a point on the elliptic curve with both an x and y coor- dinate. Fach coordinate is a 32-byte number, for a total of 64 bytes. Because, however, the curve itself is known, only the x coordinate and a sign bit that indicates which side of the x-axis the y coordinate lies on are needed to recover the y coordinate. Thus, public keys are only 32 bytes when stored (x coordinate and sign bit).

Given a 128-bit random seed, the next step in generating a self-certifying identifier i to create an asymmetric (public, private) key pair. If the required length of the private key is 256 bits (as i the case for Ed25519), then we first need to stretch the random seed from 128 bits (16 bytes) 10 256 bits (32 bytes). This stretched seed then becomes an input to the Ed25519 key generation algorithm [49]. Key stretching is another type of one-way function [92]. A good algorithm for key streiching is Argon2 [15; 114]. Once stretched, this 256-bit s

ced becomes the private key. Using the LibSodium code library, which provides the associated ECC operations, we can create the associated public key. Under the hood, the Ed25519 code hashes the private key/sced before performing the scalar multiplication on the results to compute the public key. But this hashed value is never exposed to the user. The resultant 32-byte public key may then be encoded and used to generate the self-certifying identifier

Cryptographic operations produce large binary numbers. The binary number format s not very useful for identifiers in most applications. Identifiers are better represented as strings of charac- ters. Thus, in order to practically create an identifier from a public key, we first need to convert it to a string of characters. A highly interoperable and relatively compact encoding is RFC-4648 Base-64 (URL safe) [87]. Base-64 encodes every 3 bytes of a binary number into 4 ASCII char- acters. When the N-byte binary number is not an exact multiple of 3 bytes, there will be either 1 or 2 bytes of pad characters added to the end of the Base-64 encoding. A 32-byte public key would encode to 44 Base-64 characters with one trailing pad character inclusive. For example, consider the following 32-byte private key represented as a 64-character hex string: Dcaac8c64711f66e6ed71b3Tdc5e69c5124fed3eel2446elad7ad4b650ddB61d This is encoded as the following 44-character Base-64 string (includes one trailing pad character):

DKrJxkxcRIm5ulxs33F5pxRIP6TThIERhpHErUt1Ddhh0= 11142

22,1 Derivation Code

To properly extract and use the public key embedded in a self-certifying identifier, we need to know the eryptographic signing scheme used by the key pair. In this case, we need to know that the key pair follows Ed25519 and is used for signing. This information would also allow us to infer the length of the public key. This information consists of the cipher suite and operation. In general, this defines the process used to derive the self-certifying identifier. This derivation in- formation must either be assumed or included in the identifier. One way to include this very compactly in the identifier is to replace the pad character with a special character that encodes the derivation process. Let’s call this the derivation code. Because this derivation information is needed to correctly parse the encoded public key and the convention is to parse from lefi to right, we prepend the derivation code to the public key and delete the pad character. The result is stll 44 characters in length. For cxample, suppose that the 44-character Base-64 with trailing pad character for the public key is as follows: FSpxRIPETHrUL1Ddhh07nIEDKrIxkcRIm5ulxs33bhp= IFB s the value of the derivation code then the resultant self-contained string s as follows: BFSpxRIPETHrUL1Ddhh07hJEDKr JxkcRImSul xs33bhp

Now, the derivation code is part of the identifier. This binds both the public key and its deriva- tion process to the identifier. Because the string is valid Base-64, it may be converted to binary before being parsed with binary operations, or it may be parsed before conversion. If parsed be- fore conversion, the derivation code character must be extracted from the front of the string. The first character tells how to parse the remaining characters, including the length. This allows com- pact but parseable concatenation of cryptographic material. One pad character must be re-ap- pended before converting the remaining characters that comprise the encoded public key back to binary. Once converted, the binary version of the public key may be used in cryptographic oper- ations. This approach to compact encoding of cryptographic material given risc to the CESR (Compact Event Streaming Represcntation) protocol. Proposed sets of derivation codes for KERI are provided in Section 14.2. Each is either 1, 2 or 4 characters long to replace 1,2 or 0 pad characters respectively. This ensures that each self-contained identifier siring is compliant with Base-64 specification

which must be multiple of 4 base-64 characters. This allows con- version before parsing, which may be more efficient. This approach to encoding the derivation process is similar to that followed by the multi-codee standard but is more compact because it efliciently exploits pad bytes and only needs to support cryptographic material in KERI events [105]. Furthermore, a KERI design goal is to support cryptographic agility for all the crypto- ‘graphic material in its events. A compact derivation code makes supporting this degree of granu- Tar cryptographic agility much more efficient. The derivation codes are not only used for self- certifying identifier prefixes but also for keys, signatures, and digests. For example, the Base-64 representation of the private key from the end of the Section 2.2 above may be encoded with a derivation code as follows: ADKrJxkcR9m5ulxs33FSpxRIPETThIEChpHrUL1DARhO ‘This enables the use of derivation codes for cfficient representation of cryptographic material throughout the key management infrastructure used to support KERT. 2.2.2 Inception Statement

‘The practical use of a self-certifying identifier may require some initial configuration data. We call this the inception data, and it is formally represented in a signed inception statement, The in- ception data must include the public key and the identifier derivation from that public key and ‘may include other configuration data. The identifier derivation may be simply represented by the

12142

derivation code. A statement that includes the inception data with an attached signature made with the private key comprises a cryptographic commitment to the derivation and configuration of the identifier that may be cryptographically verified by any entity that receives it. It is com- pletely self-contained. No additional infrastructure is needed or, more importantly, must be trust- ed in order to verify the derivation and initial configuration (inception) of the identifier. The ini- tial trust basis for the identifier is simply the signed inception statement. A diagram of a basic inception statement is shown below Incepton Sttement Incepton Dt Dertaton | PublicKey | Confuraton | Signature Figure 2.2, Inception Statement 223 Transferability

Unfortunately, over time, the private key controlling a sclf-crtifying identifier may be cx- posed to potential compromise. In this case, best practices for key management indicate that the (public, private) key pair nceds to be changed. This is called key rolation. Key rotation effective- 1y transfors control of an identifier to a different key pair. The transfer may be performed with a signed transfer statement. This makes a cryptographically verifiable commitment to the transfer. For a sclf-cerifying identificr, however, afler the transfer, the new controlling key pair is no longer uniquely bound to the identifier. Nonctheless, its new binding is still cryptographically verifiable, given one has a copy of the transfer statement. The log of transfer statements is end- verifiable. This means that the log may be verified by any end user that receives a copy. No trust in intervening infrastructure s needed to verify the log and validate the chain of transfers and thereby establish the current control authority. Because any copy of the record or log of transfer statements is sufficient, any infrastructurc providing a copy is replaccable by any other infra- structure that provides & copy. Any infrastructure may do. Therefore, the infrastructure used to maintain a log of transfer stalements is morely a secondary root-of-trust for control establish- ment over the identifier. This cnables the usc of ambient infrastructure to provide a copy of the log. The combination of end verifiable logs scrved by ambient infrastructure cnables ambient verifiability, that is, anyone can verify anywhere at any time. This approach cxhibits some of the features of certificate transparency and key transparency with end-verifiable event logs

but dif- fers in that cach identifier has its own chain of events that is rooted in a self-certifying identifier [93:971.

‘This presents two different fundamental classes of self-certifiable identifiers. They are rans- ferable (rotatable) and non-transferable (non-rotatable). The transferability class of the identifier ‘may be declared in either the derivation code (see Section 14.2) or the inception statement’s con- figuration data. When the private key for a non-transferable identifier becomes exposed to po- tential compromise, then the identifier must be abandoned by the controller as it is no longer se- cure. Whereas when the private key for a transferable identifier becomes exposed to potential compromise, then control over the identifier may be transferred fo & new key pair to maintain se- curity. Many applications of self-certifying identifiers only require temporary use, after which the identifier is abandoned. These are called ephemeral identifiers. Other applications may only attach a limited amount of value to the identifier such that replacing the identifier is not onerous. Because a non-transferable (cphemeral) identifier is not recoverable in the event of compromise, the only recourse is to replace the identifier with another identifier. In some applications, this may be preferable, given the comparable simplicity of maintaining the key state. In either of these cases, a non-transferable self-certifying identifier is sufficient. In other applications, con-

13122

trol over the identifier and its attached value must persist over time. In this case, a transferable self-certifying identifier is required. This persistent control property gives rise 1o a new type of identificr, an unbounded term identifier. In public key cryptography it is common to use bothg short term and long term public keys as identifiers. But even long term public keys must be eventually abandoned due to exposure. This means any value or reputation binding to that public key as an identifier must eventually be lost. Whereas an unbounded term identifier need never abandon its bound value or reputation. It need never be abandoned. This is one of the novel unique properties that KERI provides

‘The carly implementations of self-certifying identifiers, as well as the more recent secure de- vice ID implementations, are, in general, non-transferable. The main innovation of KERI is that it provides a niversal decentralized mechanism that supports both non-transferable and, more importantly, transferable (persistent) self-certifying identifiers.

2.3 Types of Self-Certifying Identifiers 2.3.1 Basic

A basic self-certifying identifier includes a prefix that is composed of a Base-64 (URL safe) derivation code prepended to Base-64 encoding of a public digital signing key. The derivation code indicates that the derivation is basic, as well as the cipher-suite for the signing scheme. Ab- stractly, the prefix may be represented as follows:

Preix Dorvation | Publc Koy Figure 23. Basic Prefix.

Including the derivation code in the prefix binds the derivation process along with the public key to the resultant identifier. An example of the prefix with a one-character derivation code and 32-byte public key encoded into a 44-character Based-64 string follows:

BDKrJxkeROMSU1x833F5pXRIPETThIEDhpHIUL1DARKO

A diagram showing the derivation from a random seed to the public key in the prefix for a ba- sic self-certifying identifier follows:

Dervation |, ) [ P Random Seed |—> Stelch > PrivaleKey ——> Generaon — PublicKey — Figure 2.4, Basic Prefix Derivation.

This derivation process was described in detail in Section 2.2.1 above. The basic type is the simplest to parse. It's asy to extract the derivation and public key directly from the identifier prefix. Moreover, when the derivation code also indicates that the identifier is non-transferable, then the inception configuration data may be empty. This means there must never be any transfer statements, and everything nee

ded to verify the signature on any statement is contained in the identifier prefix. This means that there is no need for an inception statement. This provides a very compact representation and trust basis for ephemeral self-certifying identifiers. Further- more, when non-transferable, a convention may be adopted that allows repurposing of the signing key pair to also be used as an encryption key pair.

For example, an Ed25519 signing key pair may be converted to an X25519 encryption key pair because the two curves are birationally equivalent [56; 149]. The public key from the

1142

X25519 key pair may be used cither for anonymous asymmetric public encryption or exchanged with the public key from another party to create a Diffie-Hellman shared symmetric encryption key. This would allow bootstrapping a secure authenticated (signed) and encrypted communica- tions channel between any two parties with only a non-transferable basic self-certifying identifi- er from each party. No other infrastructure is needed. Once the secure channel is bootstrapped, the two parties may thereby exchange non-transferable identifiers.

232 Self-Addressing

‘When there is a need for incepting configuration data, then the inception statement must not be empty. In some cases, it would be useful to be able to strongly bind the inception statement to the identifier and not merely rely on a cryptographically verifiable inception statement for the associated identifier. This binding between inception data and private key can be created by re- placing the public key in the identifier prefix with a cryptographic strength content digest (hash) of the inception statement (that includes the public key). A type of one-way function produces a content digest (hash). Given that the hashing function has sufficiently strong collision resistance then it uniquely securely cryptographically binds its output digest to the contents of the inception data. Furthermore, given that the inception data includes both the derivation code and the public key, then, the digest output is bound to the public key, which in turn is bound to the private key. ‘This assumes that the full derivation process, including the hashing step, is known by any verifi- er. In gencral, the process of successively chaining sufficiently strong one-way functions may ‘maintain the cryptographic strength of the binding backward along the whole chain from the fi- nal output to the originating private sced/key. With reference to the example in Section 2.2, 32 byte Blake2b, Blake2s, or Blake3 hash fanction has 128 bits of cryptographic strength [31; 33; 121). Blake2b is relatively fast for its length and strength, Blake2s works on limited-resource hardware, and Blake3 s even faster [31; 32]. These functions maintain 128-bit strength with a 32-byte digest.

Using a content digest binds the inception statement to the identifier and makes it casy to use the identifier prefix to retrieve the inception statement from a content addressable database. This requires that the database store the signature with the inception dat

a so that a reader may crypto- graphically verify that the inception data is authoritative. Without the signature, the digest is re- pudiable by the controller. This approach also enables content or document-specific but self-cer- tifying identifiers. This provides a content-addressable database mechanism to enforce non- repudiable unique attribution to the content creator as controller. This binds the content to the creator in the content address. Different creators mean different addresses. This makes confiden- tial (encrypted) content more usable as the content address is bound to the controller from whorm a decryption key must be obtained.

Abstractly, the prefix for a content self-addressing self-certifying identifier may be represented as follows:

Preix Denvaton | Inceplon Digest | Figure 2.5, Self-Addressing Prefix.

An example of the prefix with a one-character derivation code and a 32-byte hash encoded into 44 character Base-64 string follows:

EXq5YgaL6L48pf0fu7IUhL0JRAUZ RXFPOAL43wYnlds.

A diagram showing the derivation from a random seed to a hash of the inception data in the prefix for a self-addressing self-certifying identifier follows:

15142

Outntn : Omian |, + R esd| > Suokn > paey > Goion | Puty | ¢ 1 Pl + s e et Crgn Figure 2.6, Self-Addressing Prefix Derivation. The public key has a derivation distine from the digest's derivation. 2.3.3 Multi-Sig Self-Addressing Adding a content digest at the end of the identifier prefix derivation opens up other derivation possibilitis for a self-certifying identifier. For example, the inception statement need not merely contain one public key but could include a st of public keys and a threshold such that multiple signatures meeting a threshold are required for verification. Muliple signatures may significantly increase the scurity of the establishment of control authority over the identifier derived from the inception content. This assumes that the multiple signature (muli-sig) scheme used in the derivation is known by any verificr. Incepton Statement Inception Data | . Derhation | Public Keys | Canfguraton | Signatures Figure 2.7. Multple Public Key Inception Statement Abstractly, the prefix for a multi-sig content self-addressing self-certfying identifier differs from a single signature in the derivation code specifies a multi-sig scheme with inception data that includes multiple public keys appended together (not just one). The prefix may be represent- ed as follows: ot Dervaton | Incepon Digest Figurc 2.8, Mult-Sig Self-Addressing Prefix A diagram showing the derivation from multiple random sceds to a hash of the inception data in the prefix for a multi-sig self-addressing self-certifying identifier follows: ooain | 4 Formsen | > Smn - Py Goame | Pk | | o i T e Roion |- Smeh oty > oo | Pty : . > o 5 oSt |5 o Pty > oo | Pt | IS o G Figure 2.9, Mult-Sig Self-Addressing Prefix Derivation. The public keys have a derivation distinct from the digests derivation. “The inception configuration data block shown in the figurc could also include the valu and type of threshold of the number of signatures from the mulfi-sig set of public keys that are needed for satisfaction. 16142

2.3.4 Delegated Self-Addressing

An important use case for self-certifying identifiers is delegated identifiers, where a delegating identifier authorizes the delegated identifier to perform some subsct of activitics. A delogated identifier prefix may be created by including, at the very least, the delcgating identificr prefix in the delegated prefix inception configuration data. This may also be generalized to include other essential delegating configuration data. This inclusion of the delegator’s identifier cryptographi- cally binds the delegating prefix to the delegated prefix and other delegating configurations, as well as the delegated prefix’s controlling key pairs and other configuration data. The prefix may be represented as follows:

ot Derivaton | Inception Digest |

Figure 2.10. Delegated Self-Addressing Prefix.

A diagram showing the derivation to a hash of the inception data in the prefix for a delegated self-addrossing self-certifying identifier follows

oo, L s Yl 5o o o res |~ S et - o Py N A~ + o G|+ o || e Crtn

Figure 2.1, Delegated Sel-Addressing Prefix Derivation, The public key has a derivation distinct from the digests derivation.

A delegated prefix may also be made multi-sig by including a set of multi-sig public keys. 2.3.5 Self-Signing

While using a content digest in the prefix of a sclf-addressing self-certifying identifier may bind the identifier prefix to the inception data, it sill requircs an attached signature for vrifica- tion. If instead of a content digest (hash), a signature of the inception data is used in the prefix, then o attached signature is required. Signatures not only provide collision-resistant content hashes, but the signature is non-repudiable. This gives the identifier self-contained verifiability that the controller (holder of the private signing key) created the signature. In other words, this makes the inception data both self-addressing for content addressable storage and self-signing, ‘This approach may be particularly uscful for legal documents or other digital media where the contenis of the document (or a digest) are included in the inception configuration data. This makes the content addressable identificr strongly bound to the verifiable signature on the docu- ‘ment, which establishes control over the document at the time of its entry into the database. The drawback of this approach is that for the same level of cryptographic strength, the signature s typically twice as long as the digest. This is

the case for Ed25519 used in the example in Section 2.2 above, where signatures are 64 bytes long. This may or may not be a net disadvantage, de- pending on the application. Removing the burden of managing attached signatures might simpli- Iy some content-addressable storage systems. Furthermore, including the signature in the identi- fier prefix makes the inception statement more compact overall but may make other statements Longer because the identifier is longer. Some content-addressable document storage applications,

112

however, do not need many statements, so identifier length may not conribute much to tofal storage. Abstractly the prefix for a content self-addressing self-certifying identificr may be represented as follows: Prfx Deivaton | Incepion Sgnature Figure 2.12. Self-Signing Prefix Signatures that are 64 bytes long encode to an 88 character Base-64 string that includes 2 pad characters. This means the derivation code, in this case, is two Base-64 characters long, not one An example of the prefix with a two-character derivation code and a 64-byte signature encoded as an 88-character Base-64 string follows: OBYDLIO1Rx8xh5taCxW-_aCBoPbOLAZIKS5- d1DP40Z9PWn13BpPCel22FVZfF18sM3Pv-2z1jbsInR6AdZzTiESZAW. A diagram showing the erivation from a random sced to a hash of the inception data in the prefix for a self-addressing self-certifying identifier follows: et : Do | B Y 4 e Rankmion | > S Pskey > Coten - Plickey ¥ 45 spen gt Catprsion Figure 2.13. Self-Signing Prefix Derivation. 23.5.1 Generalized Any unique chain of cryptographic one-way functions of sufficient cryptographic strength may be used to securely generate an associated type of self-certifying identifier. The derivation infor- mation must properly indicate the full chain of one-way functions used in the derivation. Given such a derivation and any other content included in the derivation, any recipient of the identifier ‘may verify that the identifier was derived from a given private key(s) and thercby enable the re- cipient of any associated statement with attached signature(s) to verify the statement as authori- tative for the identifier. KERI's sccurity properties and support may apply to these generalized self-certifying identifiers. This enables universal extensibility for future types of self-certifying identifiers. ‘The prefix for a generalized self-certifying identifier may be composed of a derivation and the resulting derivative. This may be abstractly represented as follows: Prefx Derivation Derivative: Figure 2.14. Generalized Prefix, A diagram showing the derivation from a random seed to some number of one-way functions to the final derived self-certifying identifier follows: 18142

f - S, 2] 4| Pt B L L ¥ con Gt L ooy

oy

Figure 2.15. Generalized Prefix Derivation. 2.4 Cryptographic Trust Basis

The design of our portable decentralized identity system security overlay may be best under- stood through three important properties of its trust basis. These are roots-of-trust, sources-of- truth, and loci-of-control.

2.4.1 Roots-of-Trust

A root-of-rust was defined previously. The primary root-of-frust for a self-certifying identifier is cryptographic in that the derivation process at inception makes a unique binding between one or more signing key pairs and the identifier prefix. This unique binding is established with one or more chained one-way functions that bind the entropy captured by the controller to the identi- fer prefix. Only the controller may universally uniquely issue the identifier associated with that entropy. The binding at issuance is cryptographically verifiable and does not depend on any operational infrastructure for its initial establishment. This provides for a totally decentralized root-of-trust for the secure issuance of identifiers.

Acryptographic root-of-trust in the binding between a digital signing key pair and an identifier provides a verifiable trust property. A digitally signed verifiable statement provides two additio- nal verifiable trust properties, these are integrity and non-repudiability [110]. Integrity means the statement has not been tampered with since the signature was created. One can trust the state- ‘ment was made as received. Non-repudiability means that no entity besides the private key hold- er (controller) could have created the signature. This means that the holder may not repudiate the statement while maintaining that they have sole possession of the private key. This means that key possession is crucial to maintaining the root-of-trust

What a digital signature does not provide is a basis for trusting the facts of the signed state- ment or, equivalent the veracity of what was said. Informally, this means that it does not provide trust in what was said but only in who said it or cquivalently the authenticity of what was said. Nonetheless, trust in who said it is useful because non-repudiation enables consistent attribution. Consistent attribution to who said it is a necessary condition for maintaining the possibility of trust (veracity) in what was said when that trust (veracity) is based on the reputation, credibility, or authoritativeness of who said it. With consistent attribution,

one may trust that the controller made a set of statements. If those statements are also consistent in their content, then there is thereby the possibility of trust in the veracity. On the other hand, if the statements are inconsis- tent in their contents, then the non-repudiable source of that statement (the controller) is thereby proven to be inconsistent. Inconsistency is a basis for distrust. Another term for inconsistency is duplicity. Duplicity exhibits itsclf as inconsistent statements about some fact. To summarize, consistent attribution is basis for assessing the veracity of what was said because who said it is not known to be untrustworthy. One may then build on that basis over time a stronger likelihood

197142

of trust by maintaining histories of statements and verifying them for consistency in order to de- tect duplicity. 2.4.2 Sources-of-Truth

A source-of-truth is someone or something that may make authoritative statements. One very useful approach to information systems design is to establish a single or authoritative source-of- truth for any item of information in the system [8; 94; 131]. In the case of an identity (identifier) system security overlay, we wish to establish a cryptographically verifiable source-of-truth about an identifier. Because at issuance, self-certifying identifiers make a universally unique crypto- ‘graphically strong binding between the identifier and a key pair, there may be no other verifiable source-of-truth besides the controller who created the key pair and thereby holds the private key.

To restate, the process of creating a self-certifying identifier means that only the controller may make verifiably authentic control statements about the identifier. The identificr is thereby bound to the controller. This makes the controller the only authoritative o single source-of-truth for the identificr.

To elaborate, at inception, self-certifying identifiers have a single root-of-trust and a single source-of-ruth that are cryptographically bound together. This binding creates what we call the root-authority for the self-certifying identifier. Because root-authority uniquely binds an entity, the controller, to a private key(s) by which that authority is exercised, therefore without loss of ‘generality, we may refer to root-authority as either the power of control and/or the entity that ex- excises that power of control. This resuls in the following definition:

A root-authority has total and exclusive control over a self-certifying identifier. (22)

“This exclusive total control is imbued in the roor-authority at the inception of a self-certifying identifier by virtue of the process of creation from captured entropy. Exercise of this root-author- ity is first exhibited at issuance of the identifier. Root-authority may later be transferred, delegat- ed, or attenuated by the exercise of that root-authority via cryptographically verifiable state- ments to that effect.

In contrast, in an administrative identity system, by virtue of its designation as administrator, the administrator is/holds the root-authority over identifiers it issues and not the holders of the private keys that the administrator binds to those identifiers. Thus, the scc

urity of an administra- tive binding is comparatively weak because it s a function of the security of the administrator’s processes and not cryptography.

2.4.3 Loci-of-Control

In psychology, the term loci-of-control refers to the scope of a person’s life over which they feel they have control. The root meaning of the word loci or locus means place. The term faci-of- control refers to the extent to which control over one’s life either is driven by external forces or arises internally from the exercise of one’s agency [2; 100]. We apply the term loci-of-control to an identifier system to answer the question of “who controls what? . Does the control over bindings between identifiers, controllers, and key-pairs arise externally from an administrator or does it arise internally from the controller itself? One way of analyzing the degree of decentralization in an identity system s to categorize the relative scope of external vs internal locus-of-conirol over the bindings.

With self-certifying identifiers, the singular root-of-trust and source-of-truth, that support the its control-authority enable consistent attribution of verifiable authoritative control statements about an identifier. Given that there is only one source-of-truth, that source of truth may exclu- sively determine the sequence of control statements and any dependencies befween control state- ‘ments. Control over the sequencing means that the type of infrastructure needed to support and

20142

‘maintain the history of control statements may be simplified because any identifier’s history of control statements may be ordered independently of any other identifier's history. Recognition of this property dircetly leads to KERT's approach. Primarily, control statements are used to estab- lish and maintain control over the identifier. This includes the following types of statements: + Control over the creation or issuance of an identificr. This may include designations of sup- ‘port infrastructure or pre-commitments to future transfers of control. + Control over operations on an identifier. Control operation statements may include the following « Transfer of control (non-revocable). This means transfer of control of the identifier to a dif- ferent key-pair or set of key-pairs and different signing schemes such as multi-signature. This is also known as rotation. A transfer/rotation operation revokes the current set of key pairs and replaces them with a new set. This may also include transfer designations of sup- port infrastructure + Delegation of identifier (revocable). This creates a new identifier with its own set of keys and authorizes (revocable) some degree of control authority. Anotional diagram of the composition of these control statements follows: Establish Control Authority Incepion Statement [Prfix[Key Designations Witess Designations | Signatures Transfer (Rotaton) Statement [Pref [crai Hesn ey Designatons Witness Designation [ signatures ‘ Transfer Statement Figure 2.16. Control Establishment Statements Transfer Designations Infrastructure [ Delegations Figure 2.17. Transfer Designation Once current control authority over an identifier has been established, that current control au- thority may make additional statements for purposes unrelated to establishing and/or maintain- ing its control authority. These statements may include authorizations of encryption keys for communication, endpoints for routing communications, service endpoints for other resources, or signed transactions for doing business. These are diagramed below: 21142

( Communication Authorizations Encrypton Keys

\ Routing

Figure 2.18. Communications Authorizations Service Authorizations

‘ Senvice Endpoints. Figure 2.19. Service Authorizations 3 AuTtoNoMmIC IDENTIFIER (AID) Although SSI is becoming recognized as an important new approach to identity, different imple- ‘mentations of SSI vary in the degree of decentralization and security. As a result there is a need to define more precisely a normalized theoretical model that best represents the ideals of self- sovereign identity. To avoid confusion with other variants, we have chosen to use the terms Au- tonomic Identity System (AIS) and Autonomic Identifier (AID) to name this more precise model. ‘The roots of the word autonomic are the same as the word autonomous, which comes from the Greek words auto (self) and nomos (law), which together mean literally, self-rule or when ap- plied as an adjective, sel-ruling, self-governing, or sel -regulating [18; 21]. The word autonomic is most commonly used o refer to the body’s autonomic nervous system that controls the circu- latory, digestive, respiratory, and other systems that act unconsciously, i.e., are self-regulating without conscious oversight [20]. Likewise, the term autonomic computing (AC) means some type of self-managing software capability such as self-configuring, self-securing, or self-scaling [6: 19; 51].

In that vein, we can say that an autonomic identifier is one that has self-managing or self.gov- erning capabilities. This more fully evokes the meaning of self-sovereign but with the addition of self-management. The most important seif-management capability is self-certification which, as we have shown, leads to selfadministration. We defined seif-certification above in Section 2.2 but it bears generalization here. As defined above, self-certifying identifiers include a prefix that uniquely (strongly) binds the identifier to the incepting controlling key pair at issuance. The selfcertifying property is inherently completely decentralized in the broadest sense of the word. ‘This prefix enables that identifier to be part of a namespace governed by that controller of the key pair.

3.1 Autonomic Namespace (AN)

Anamespace groups symbols or identifiers for a set of related objects [108]. In an identity sys- tem, an identifier can be generalized as belonging to a namespace that provides a systematic way of organizing related identifiers with their resources and attributes.

To elaborate, a namespace employs some

scheme for assigning identifiers to the elements of the namespace. A simple name-spacing scheme uses a prefix or prefixes in a hierarchical fashion to compose identifiers. The following is an example of a namespace scheme for addresses within the USA that uses hierarchy of prefixes:

state.county.city.zip.street.number. @ 21142

An example element in this namespace may be identified with the following:

utah.wasatch.heber.84032.main.1508. 32) where each prefix location has been replaced with the actual value of the element of the address. Namespaces provide a systematic way of organizing related elements and are widely used in computing.

We formally define an autonomic namespace (AN) as a namespace with a self-certifying prefix. A self-certifying prefix provides cryptographic verification of root control authority over its ‘namespace [68; 90; 102; 103]. To clarify, cach identifier from an autonomic namespace includes as a prefix an identifier that either is the public key or is uniquely eryptographically derived from the public key of the incepting (public, private) key pair. The associated private key may then be used by the controller to authoritatively (nonrepudiably) sign statements that authenti- cate itself and authorize use of the identifier. These statements include responses to challenges to prove control over the identifier. It is the essential enabling property of identifiers in a fully de- centralized self-sovereign identity system. Thus self-certification enables both self-authentica- tion and self-authorization capabilitics as well as self-management of cryptographic signing key- pairs. Together, these properties make the namespace self-administering

An autonomic namespace is self-certifying and self-administrating. (33) ‘The self-management capabilities of autonomic namespaces best exemplify the touted self: governing property associated with self-sovereign identity systems [10; 45; 127; 132; 133; 136]. ‘All derived autonomic idenifiers (AIDs) in the same autonomic namespace (AN) share the same root-of-trust, source-of-truth, and locus-of-control (RSL). The goverance of the ‘namespace i, therefore, unified into one catity, that s, the controller who is/holds the root authority over the namespace. This unification of control authority simplifies the security system design and analysis. The associated implications lead to the KERI design.

‘The primary purpose of an autonomic identity system (AIS) is to enable any entity to establish control over an identifier namespace in an independent, interoperable, and portable way. This approach builds on the idea of an identity (identifier) meta-system [37; 38; 153] that enables in- teroperability between systems of identity (identifiers) that not only expose a unified interface, but add decentralized control over their ident

ifiers. This best enables portability, not just inter- operability. Given portability in an identity (identifier) meta-system system, transitive frust can occur, that is, the transfer of trust between contexts or domains. Because transifive frust facili- tates the transfer of other types of value, a portable decentralized identity meta-system, e.g., an autonomic identifier system, enables an identity meta-platform for commerce [134].

3.2 Namespace Syntax

‘There are many name-spacing conventions for the syntax of hierarchically organizing the identifiers in the namespace. Of those conventions, the most widely supported is the Uniform Resource Identifier (URI) of which URLs (Uniform Resource Locators) and Uniform Resource Name (URN) are special cases (IETF RFC-3986) standard [147; 148]. Given its almost univer- sal popularity, we adopt its hierarchical path, query, and fragment syntax for name-spacing auto- nomic identifiers (AIDs). In our national definition, the identifier starts with the characters aid to indicate the scheme. This is followed by a colon, and then the Base-64 encoded prefix as defined above. The prefix includes the derivation code and the derived self-certifying identifier. Other colon-delimited prefix options may follow. This is then followed by the URI components. More formally the syntax is as follows:

aid:prefix[:options][/path][?query] [#fragment] (3.4) 237182

Anotional example of an AID using URI components s as follows: aid:BXq5YqaL6L48pf0fu7IUNLOJRAU2 RxFPOALA3wYnl148/path/to/ resource?name=secure$really

‘This is not a complete specification, but it is sufficient to illustrate the concept. The prefix

provides a means of authentication. The other components provide a means of accessing a

resource. Any signed statement referencing an AID may be verified as authoritative and may

serve as authorization.

3.2.1 Properties An AID has several useful propertics.

• Universally Unique Identifier (UUID). By virtue of its prefix, an AID is universally unique thus it can be used instead of a UUID as defined by RFC 4122 [5]. UUIDs enable distributed applications o create unique identifiers without a central identifier server. Prefixed name- spacing allows for sorting and searching properties such as time order, lexical order, nesting, ete.

• Mini language for performing operations on resources (ReST). The URI components are com- patible with the tooling that has been developed for ReST interfaces. This fosters adoption in ‘micro-service and serverless applications but with security built-in not bolted on.

• Hierarchically deterministic derived self-certifying identifier. Using the URI components, one can casily specify hierarchically deterministic derivation paths for identifiers that enable the creation of derived (public, private) key pairs without having to store private keys but merely re-derive them from the identifier and the root private key. This helps with key management An example follows:

aid:selfcertroot:/path/to/data?key-path=parent/child/child/child

‘These features make AIDs a candidate for a universal identifier scheme to be used throughout a

computing system. This body of work will explore in more depth the design of autonomic

namespaces and their associated security and operational features. There is some similarity between the usc of the cryptographic identifier prefix in KERI and public encryption keys in the key transparency project [93]. The similarity is that in KERL a basic sclf-certifying identifier is

a public signing key with a derivation code, whereas key transparency is a verifiable dircctory of

public keys, primarily public encryption keys, although signing keys may be used. There are

several other important differences. In KERI, identifier prefixes may be any of the self-certifying identifier types, not merely public keys. Furthermore, the key events in KERI are separable for cac

h identifier prefix. This enables support for GDPR’s right to be forgotten [67]. KERI uses pre-rotation for key rotation (see later). KERT's key event logs allow anchoring of issuance events. Finally, the identifier derivation code enables self-contained crypto agility. In summary,

KERT is & full-featured DKMI, whereas key transparency is simply a verifiable public key

directory.

3.3 Unified Identifier Model In general, we want to have a theory or model of how to design identifier systems with desir-

able properties. Historically identifier systems has been designed without any unifying theory to

guide the designers. This means that many identifier systems are largely bespoke to a given ap-

plication. This may be problematic especially when the identifier system does not have a well

defined approach to security. More recently, explicitly characterizing identifier properties has

gained some recognition as a prerequisite (o identifier system design. For example, the well

known Zooko's triangle or so called tri-lemma is based on recognizing a conflict between three 24182

different desirable properties for an identifier [155]. The three properties are human meaningful, secure, and decentralized. The tri-lemma states that an identifier may have any two of the three properties by not all three. Some have claimed to have solved the tri-lemma by using a hybrid identifier system where human meaningful but insecure identifiers may be registered on a dis- tributed consensus ledger. The registration process itself uses identifiers that are secure and de- centralized but not human meaningful [142]. The fact that not one identifier but a combination of identifiers is needed to solve the tri-lemma hints that the identifier model therein employed is incomplete.

‘The autonomic identifier (AID) model, however, provides a complete unified model of identi- fiers (digital). This model takes a security first approach. The model is based on the recognition that all other properties of an identifier are of little value if the identifier s not securely con- trolled. In this sense the AID model provides a formal theory of identifiers. Al identifiers maybe classified and described within the framework of this theory. This theory provides a principled approach to identifier system design and may be used to inform and guide the design and devel- opment of any concrete implementation of an identifier system.

‘The function of KERI is to establish control authority over an identifier (AID) in a crypto- ‘graphically secure and verifiable way. Once that control authority has been established, a verifier may then securely verify any associated authorizations issued by the controller of the AID. ‘These authorizations have the form of a signed authoriation statement where the statement typi- cally includes the AID under which the authorization is issued. A verifier may then verify the au- thorization by verifying the atiached signature using the keys that were authoritative at the time the authorization was issued. These authorizations are secure to the extent that the cstablished control authority is secure. The authorizations inherit their security from their associated AID. ‘The trust domain of an AID is the set of statements that may be securely verified as being issued by the controller of that AID (along with any associated transactions or interactions). Authoriza- tions then inhabit and are protected by this trust domain. In other words the authorizations are under the aegis of the AID (or equivalently the controller of the AID) that ssued them.

33.1 Legitimized Human Meaningful Identifiers (LIDs)

Given an AID we may now unify the other desirable property of an identifier, that is human ‘meaningfulness. The cryptographic material in an AID makes it decidedly non-human meaning- ful. In contrast, examples of human meaningfulness might be casily recognized words or names or more relevant some efficiently hierarchically organized composition of characters. Human ‘meaningfulness has two limiting characteristics. The frst is scarcity, this exhibits itself in vari- ous undesirable ways such as name squatting, or race conditions to register or otherwise assert control. More importantly, there is no inherent security property of a human meaningful identifi- er. This makes them insecure by default. Nevertheless, given the trust domain of an AID any ‘human meaningful identifier may be uniquely authorized, sanctioned, or legitimized within that trust domain. Because only the controller of the AID may issue verifiable authorizations associ- ated with that ATD, that controller alone may authorize the use of any human meaningful identi- fier under the acgis of its trust domain, The associated authorization statements legitimize the use of that human meaningful identifier within the trust domain. This gives rise to a new class of identifiers, we call a member of this class a legitimized human meaningful identifier and use the acronym LID, The important property of an LID is its verifiability with respect to a given AID. ‘The pair forms a new identifier couplet that we may represent as follows:

aidlid 35 where | represents that the succeeding /id s authorized within the trust domain of the preceding aid. We can diagram this relationship as follows:

257142