Protocol and Genus versioning Redux

[SmithSamuelM]

Versioning for CESR Based Protocols

This replaces discussion item #1016

First a few preliminaries and then a cogent example to illustrate the problem.

Protocol Dependency on Shared CESR Code Table

KERI and ACDC

Currently the KERI and ACDC protocols use CESR to encode primitives, indexed primitives, and groups (nestable compositions of primitives or groups of primitives). These are encoded based on a set of code tables for different types of encodings. More specifically these are primitives codes, indexed codes, and group codes. We can refer to the set of code tables more succinctly as a single master code table. What I mean by "use CESR" is that there is a specific set of code tables that use the CESR approach to composable encodings in the Text and Binary domain that the KERI and ACDC protocols use.

In the reference implementation of CESR, i.e., the keripy library, the primitive codes are managed by the Matter class (and its subclasses), the indexed codes by the Indexer class (and its subclasses), and the group codes by the Counter class. These classes are shared by both the KERI and ACDC protocol implementations in keripy.

A specific set of code tables is indicated by a special universal CESR code called a protocol-genus-version code or genus-version code for short.

Currently both the KERI and ACDC protocols use the same set of code tables as specified by its associated genus-version code.

This means that both the KERI and ACDC protocols are dependent on that shared set of code tables i.e the same master code table.

TSP and SPAC

Currently in development, the TSP protocol also depends on the same CESR master code table as KERI and ACDC. Likewise the contemplated SPAC protocol also depends on the same CESR master code table.

Why Share a Code Table

One reason why implementations of different related protocols might benefit from all using the same CESR master code table is that they can then share sourcecode in their implementations. This becomes more apparent for the TSP and SPAC protocols which are tunneling protocols that tunnel other protocols. If the tunneled protocols use the same CESR master code table then there is more ability to share sourcecode libraries amoungst the protocols. A parser of a CESR stream that includes all the protocols can benefit from that sharing.

One problem that CESR solves is the cryptographically agile encoding of cryptographic primitives for cryptographically heavy protocols. The same set of primitives is largely the same across all cryptographic protocols so there is some simplification via shared familiarity by using the same set of encodings for the same underlying cryptographic primitives across protocols. It is not unreasonable to assume that all cryptographic heavy protocols could all use the same CESR master code table.

Historically the early implementations of CESR did not have support for different master code tables. There was no concept of a universal genus-version code. So all the pre-CESR V2 keripy libraries for KERI and ACDC has no choice but to share the same CESR master code table. Migrating to a versioned master code table or multiple versioned master code tables is one of the heavy lifts in moving from pre-CESR version 2 to CESR version 2.

Indeed, the underlying problem is how to manage the migration from an unversionable shared master code table to a versioned master code table(s).

Why Version

The main reason for versioning is to enhance interoperability between versions, especially when those versions are mutually incompatable. The version sends a signal that indicates whether or not there could be compatiblity problems. One approach to versioning splits the version into a major and minor version with different semantics for major vs. minor version changes. In one approach, a major version change signals both backward-breaking compatibility changes with earlier major versions. A minor version change for the same major version signals new features in the later minor version that do not break backwards compatiblity with features in earlier minor versions for the same major version.

Versioning is a familiar mechanism for managing the evolution of features in a protocol that fosters interoperability over time. It provides a clearer upfront signal of degree of compatibility.

This was required for KERI and ACDC as a result of lessons learned with the earliest implementation of the shared master code table, that we are now calling CESR V1, namely not being consistent in how group codes operate. This forced backwards breaking changes, which by virtue of versioning allows changing at the very least the group code table between CESR V1 and CESR V2.

The versioning scheme for CESR is that the version number is split into a (major, minor) elements. As of yet the CESR protocol does not specify the semantics of what a major versus minor change means. It is assumed that there is some semantic difference that is TBD. One of the reasons for this discussion is to gain some clarity on what those semantics should be so that the specification can be hardened in that respect.

Protocol Governance Given a Shared Master Code Table

Given that four protocols currently share the same unversionable CESR master code table and all are in the process of moving to a shared versioned master code table, the open question is how should the versioning of that shared CESR master code table be governed. Currently the CESR, KERI, and ACDC protocol specifications are governed by the KeriSuite Working Group (KSWG) in the ToIP foundation in the Linux Foundation (JDF) and are on a track to become ISO specifications.

The TSP protocol specification depends on CESR V2 and later. The TSP specification is governed by the Technical Stack Working Group (TSWG) within ToIP. The contemplated SPAC protocol specification does not yet have a governing body.

As mentioned above, a shared versionable master code table comes with advantages. Its primary disadvantage is that the governance of the table must also be shared in someway. When the governing bodies are disparate then there must be a defined coordination mechanism for managing that disparity.

So minimizing shared governance coordination between different governing bodies may be highly desirable.

When the CESR Version 2.0 specification is published it will include a master code table that notionally will be shared by all of the KERI, ACDC, SPAC and TSP protocols. The Specification will define the Genus code for that table. Lets call this the KAST genus for (Keri, Acdc, Spac, Tsp). The KAST genus will have a major version of 2 and a minor version of 0. We can represent this as v2.0. There are 64 possible major versions and for each major version there are 4096 possible minor versions.

Currently as specified in the draft CESR 2.0 specification the unique genus code for the KAST genus master code table is 'AAA'. A CESR genus-version for KAST at v2.0 would be encoded as -_AAACAA.

Each member of the KAST set of protocols has its own protocol specific versioning scheme. As of version 2 for KERI and ACDC, and version 1 for TSP and SPAC, each protocol supports a similar (major, minor) version number with 64 major versions and 4096 minor versions for each major version. It is anticipated that all 4 protocols will simultaneously release major versions of their protocols that depend on the v2.0 of the shared CESR KAST genus code table.

Currently the KERI and ACDC specification do not indicate which CESR v2 genus code table is implied in those specifications. Conceptually, however, there is an implied CESR master code table without specifying what that is. This is primarily because the three specifications CESR, KERI, and ACDC were written largley simultaneously and the specifics of the genus-version code now in the CESR specification had yet to be developed. The CESR specification, however, does indicate that genus 'AAA' (KAST) is reserved as the genus code for the shared master code table for KERI and ACDC. Consequently, the KERI and ACDC specifications still need to be updated to harden that dependency. Moreover, some outstanding issues of version synchronization and goverance still need to be resolved as per this discussion. Once those are addressed we will be in a better place to harden the specified dependency on a given CESR master code table genus for both KERI and ACDC. The working assumption has been that it will be the KAST genus. But that may change as a result of this discussion.

Example

Some messages in the KERI protocol include a key list. The entries in the
key list are CESR encoded public keys from a cryptographic key pair generation algorithm for each entry. The CESR encoding of each public key is specific to the key generation algorithm used to generate that public key. For example, in a given CESR code table, an Ed25519 public key is encoded differently than an ECDSAsecp256k1 public key. Likewise fields in the other protocols could include public keys likewise encoded.

Suppose that on day one, CESR 2.0, KERI 2.0, ACDC 2.0, SPAC 1.0, and TSP 1.0 are simultaneously released. Each of these KAST protocol specifications indicates their dependency of the version 2.0 of the KAST genus CESR master code table that they all share.

Now suppose, that sometime later, codes for public keys for post quantum resistant key pairs are added to the shared KAST genus code table.

These means that a KERI message v2.0 could include in its key list a primitive that uses a new primitive code not included in the KAST v2.0 code table but is included in an later KAST code table.

A receipient of that message could not correctly parse that message unless it supported the updated set of codes.

So the open question is how to manage the version signaling by that message that there is a change in the CESR KAST genus code table used by the contents of that message despite no changes in the message protocol itself..

One way to do this would be to increment the minor version of the KAST genus code table. So when the new post quantum key pair public key codes are addeed the KAST table its version is incremented to v2.1. In this case the minor version change follows a semantic versioning scheme where non-backwards breaking changes to the code table get a minor version increase.

Unfortunately, a KERI message that includes the new CESR v2.1 public key codes does not have any way of explicitly signaling it has those new codes. The version for the KERI protocol was not changed and there is nothing embedded in the message itself that indicates that is uses primitive codes from a later version of the KAST genus table.

So how to handle this? I have listed below numbered alternatives that are possible. There may be others. I ask that any responses, to this post reference the number. Also if someone wants to propose an alternative not listed, in a comment, then give that new alternative a number.

I have limited the example to a minor version change. Major version changes could possibly be handled differently. So I don't want to confuse the simpler problem of minor version signaling with major version signaling. It would be great if we solved both that same way, but one of the options is to NOT solve both the same way. So that is an ancilliary discussion.

Alternatives

1. Do not signal a minor version change in CESR KAST.
   A parser that attempts to parse a KERI or ACDC message will eventually get to the point of parsing the key list and will attempt to parse the entries in the key list as public keys from that parser's supported KAST genus code table version. A minor version change is not backward breaking so the the parser upon encountering an unrecognized primitive code would drop the message and its attachments and potentially flush all or part of the associated CESR stream. A complication is that for non-CESR-native serializations of the message (JSON, CBOR, MGPK) the parsing of the key list primitives happens deep in the bowels of the processEvent method, whereas for a CESR-native serialization of the message the key list is parsed up front in the parser, and so the detection of the unrecognized primitive code happens in a different place. This means that how the parser drops the message, its attachments, and all or part of the associated stream could well be different. One reason to signal a minor version change is so that the decision to drop happens at the same depth in the code. Consequently, signaling has potential security advantages. The biggest advantage of this alternative is that it is the lightest lift. No code changes are required. We just keep operating as is. The only time a version change would ever be signaled would be for a major CESR genus code table change, but minor table version changes are never signaled.

2. Tightly synchronize the protocol version with the shared CESR KAST genus version that a given protocol is dependent on.
   This means that to signal to a parser that a given message is using primitive codes from a later version of the CESR KAST genus, the protocol version needs to be updated to match the CESR KAST genus version. In other words, all Protocols that share the same genus must use the same version for their protocol. This means that when the new post-quantum key pair generating algorithm codes are added to the shared CESR KAST genus table thereby triggering a minor version update to 2.1 then all of KERI, ACDC, SPAC, and TSP MUST update their protocols versions to 2.1 as well. This requires tight coordination between the working groups. It may be entirely impractical given nothing more problematic than different meeting schedules or voting requirements for approving and then publishing minor version updates to each protocol. Technically this is also inelegant because the protocol version itself tracks changes in the protocol. Protocol changes include message types, message field labels for each message type, and the semantics of each message field but not the contents of each field. Whereas the genus table version only tracks changes in the encoding of fields. The two versions track different non-mutually dependent changes. This approach tightly couples changes that otherwise would be loosely coupled, hence relatively inelegant.

3. Include the shared KAST genus version number in the Protocol Version strings of every protocol that shares that KAST genus.
   In general, the genus version number that a protocol is dependent on is added to the version string so that the version string for the protocol includes the protocol code, the protocol version number, and the genus version number. The genus itself is not included since this is a declared dependency in the protocol specification. The inclusion of the genus version number explicitly signals a minor change in the KAST genus without requiring tight coordination with the dependent protocol version governance. A given user of the KERI protocol can send a message that includes the KAST genus version and therefore signal a minor version compatibility change in the contents of the message without triggering any governance actions for the governing body of the KERI protocol. The downside of this approach is that all protocols that share a given CESR genus table must include that table's version number in the version string of any messages sent by that protocol. This adds 3 bytes to the length of each and every message. The protocols are still required to publish their dependency on a given CESR genus table and are dependent on the governance of that table. So for example, this governance determines how and and when new codes are added to that table which then results in a minor version change. Since minor version changes are not backward breaking, it's not likely to cause too much trouble for users since any user can signal which version of the CESR genus they are using for any given message. A complication occurs if and when a given protocol decides to no longer share a genus table with other protocols. In that case, they would have to publish that as of say version 2.2 of their protocol they are using a different genus. Any implementation would have to track that change by maintaining a table of protocol versions mapped to a specific genus. If such a change is unlikely then the burden of such tracking could be minimized. Indeed this could be a case for forcing a Major version change in the associated protocol. To clarify should a protocol that shares a CESR genus with other protocols choose to change that dependency to a different genus then that change is considered backward breaking and the protocol MUST make a major version change. So the change could only occur say with version 3.0 of the ACDC protocol for example. This locks genus dependency to a major version change not a minor version change in the dependent protocol.

4. Include both the genus and version number of the shared genus table in the Protocol Version string.
   This has the advantage that it explicitly signals what genus table and table version are used for any CESR-encoded elements of a given message. Thus a parser can unambiguously know what genus table to use independent of the protocol in order to successfully parse the message. A given user of the protocol can choose, on a message-by-message basis, to switch genus tables and versions. This minimizes the governance dependency between a dependent protocol and a shared CESR genus. Indeed a user can choose to switch a genus without any governance action required. The disadvantage of this approach is that the implementation of all the associated protocols KERI, ACDC, SPAC, and TSP gets more complicated. The lift to migrate to V2.0 of these specifications gets harder and will take much longer. The other disadvantage is that each message in any protocol must carry at least 6 more bytes of overhead (3 for the genus and 3 for the genus version )

5. Not share genus tables between protocols.
   In this approach, each of the KAST protocols KERI, ACDC, SPAC, and TSP MUST use a unique dedicated genus code for that protocol's associated CESR master code table. Essentially the genus code maps one-to-one to the protocol code. Given the genus code a parser knows the protocol or given the protocol code a given parser knows the genus. The version is the same. So changes to the genus code version for that protocol result in a change in the protocol version. They are the same. the main advantage of this approach is that there is no shared governance between protocols other than the initial allocation of the dedicated genus code for a given protocol. A disadvantage of this approach is that it loses the shared source code advantages of a shared CESR genus code table. It's also a bigger lift than 1, 2, or 3 but maybe less than 4.. Another drawback of this approach is that in this example the addition of the post-quantum primitive codes forces a minor version change to the protocol version. Technically this is also inelegant because the protocol version itself tracks changes in the protocol. The tracked protocol changes include message types, message field labels for each message type, and the semantics of each message field but not the contents of each field. Whereas the genus table version only tracks changes in the encoding of fields. They track different things. This approach tightly couples those changes that otherwise would be loosely coupled, hence relatively inelegant.

Comparisons:

1. This is what we do right now with preversioned CESR, KERI, and ACDC. It is the lightest lift. IMHO, however, it starts to become more problematic over time as we add support for native-CESR encoding of messages and may be more problematic with SPAC and TSP which are fully CESR Native. I think NOT signaling version changes, even minor version changes just ends up becoming more problematic over time because things break in different ways, whereas signaling enables things to break the same way every time. This would be my second choice primarily because it is the least work.

2. IMHO this seems to be fatally flawed as the coordination for governance could be too tight across sharing protocols. It does retain the advantage of sharing a single CESR genus code table and is a lighter lift than 3. but not much lighter. I find the one-to-one coupling between the protocol version and genus version tables too inelegant.

3. IMHO this is the best option of the bunch, my first choice. It is in the sweet spot of minimizing the lift while benefiting from signaling and also maximizing the benefit of shared tables with at worst minimal governance coordination issues.

4. IMHO this is worse than 3. Primarily because the lift is much higher and the flexibility of switching CESR Genus code tables seems to be more flexible than is justified given the code maintenance cost of such flexibility. This could be an option down the road for a path that starts with 3 and then migrates to this on a major version change.

5. IMHO this is less problematic than 2. but not as good as 3. Indeed one outgrowth of 3. would be to migrate at some point to non-shared genus tables between protocols but still retain the elegance of the loose coupling that 3. gains from including the genus table version in the protocol version string.

Comments

Appreciate constructive feedback and suggestions as well as clarifying questions.

[pfeairheller]

I also favor #3 as the choice to move forward with assuming my following understanding is correct. What we are now indicating is that a protocol version declares 3 things:

1. The message types
2. The fields per message type
3. The genus (newly included).

So for example, the KERI 2.0 version specifies message types of ‘icp’, ‘rot’, ‘ixn’, etc, the fields (‘v’, ’t’, ’s’, etc) for each message type and (now) that it uses the KAST genus. Each individual KERI 2.0 event will have a version string that includes KERI20 and also a version indicator for the version of the KAST genus that it supports.

We now have the ability to independently version protocols and genus as well as share genus tables (if so desired) across protocols with the freedom to change to a non-shared genus in the future for any given protocol by creating a new version of that protocol. This gives us the best combination of flexibility without assumptions or “version rules” of any of the options.

Therefore #3 has my vote as well.