Query Mode Format

[SmithSamuelM]

Define abstract functionality of Query Replay Modes

Define query message qry
new message type qry or qkl or req Define query string parameters

[SmithSamuelM]

Design Proposal

Preliminary design approach suggestions for query message is to start with Restful API parameters and then back out from the Restful API a compatible query message format.

Restful APIs

A useful set of design guidelines for ReSTful APIs may be found here:

Web API Design A related but more dated book. API Design

The basic design consists of two base URLs per resource. A collection URL and a specific element in the collection URL.

'/dogs?all=true' (collection with query parameters to operate on the collection)

'/dogs/1234' (specific element with path to specify element)

The base URLs are operated on with the HTTP verbs, POST, GET, PUT, PATCH, and DELETE corresponding to the CRUD (create, read, update, delete) methods on a database. Unlike PUT, PATCH allows updating only part of a resource.

Resource	POST create	GET read	PUT/PATCH update	DELETE delete
/dogs	Create a new dog	List dogs	Bulk update dogs	Delete all dogs
/dogs/1234	Error	Show dog 1234 (if exists)	Update dog 1234 (if exists)	Delete dog 1234 (if exists)

Sweep complexity under the '?' Use limit and offset for pagination. /dogs?limit=25&offset=50

Suggested Resources

Clone Replay of KELs in first seen order.

Logs are stored with key of identifier prefix plus monotonic date time.

\logs

\logs\{pre}

\logs\{pre}\{datetime}

{pre} is template for identifier prefix

{datetime} is template for url encoded ISO8601 datetime. (Alternatively the datetime could be encoded as a Unix compatible datetime floating point number, but that is not a format that is universal to all operating systems)

GET \logs\EABDELSEKTH replays first seen log for identifier prefix `EABDELSEKTH' (prefix clone)

GET \logs?all=true replays first seen log for all identifier prefixes in database (full database clone)

GET \logs\EABDELSEKTH\%272020-08-22T17%3A50%3A09.988921%2B00%3A00%27 (get event of prefix at datetime)

GET \logs\EABDELSEKTH?after={datetime}&limit=1 Returns next event for 'EABDELSEKTH' after {datetime} where date time is ISO8601 URL encoded.

GET \logs\EABDELSEKTH?before={datetime} Returns all events for 'EABDELSEKTH' before {datetime} where date time is ISO8601 URL encoded.

GET \logs\EABDELSEKTH?after=%272020-08-22T17%3A50%3A09.988921%2B00%3A00%27

Returns all events for 'EABDELSEKTH' after '2020-08-22T17:50:09.988921+00:00' (url encoded ISO-8601)

GET \logs\EABDELSEKTH?before=%272020-08-22T17%3A50%3A09.988921%2B00%3A00%27

GET \logs?pre=EABDELSEKTH&after=%272020-08-22T17%3A50%3A09.988921%2B00%3A00%27 Equivalent query on the collective base URL

GET \logs?pre=EABDELSEKTH,E123ABDELSE,EzyyABDELSE Get logs for three prefixes

Replay of KELs by Sequence Number

Given recovery forks the KEL indexed by sn will not be the same as the first seen KEL. The key state will be the same but the exact sequence of events in a replay will not. So this is for verifying key state not for cloning the append only event log. But for any verification, the KEL by sn is more appropriate because you can query the key state at any sn and allows a verifier to find a given authoritative event in the log by its location seal.

\events

\events\{pre}

\events\{pre}\{sn}

{pre} is template for identifier prefix {sn} is template for sequence number

\events?all=true (All KELs in database in order by sn)

\events\{pre} (KEL for identifier prefix {pre})

\events\{pre}\{sn} (event at {sn} where {sn} is template for sequence number

\events\{pre}?offset={sn}&limit=1000 (next 1000 events starting at sn = {sn}

\events?pre={pre}&sn={sn} Using collective to get event at sn of pre

Fetch Keys for Event at given sequence number

/keys

/keys/{pre}

/keys/{pre}/{sn}

Fetch latest Key State for KEL at prefix

/states

/states/{pre}

Query Replay Messages

Given the proposed basic restful API framework above, a couple of different approaches come to mind for a non HTTP message format for providing similar query capability but over bare metal protocols like TCP. The first approach is to explode the resource request path template parts from a restful GET request into fields in the message body. One field for each part of the resource path template. This would be evocative of the current event message structure and share some of the similar fields. The second approach is to just tunnel a mimic of the restful verbs with the exact resource path and query strings. This is essentially tunneling the equivalent of the restful request through a bare metal protocol. Examples are provided below:

Restful Path Explosion

This message performs the equivalent of

`GET /logs/{pre}/{datetime}

{
  "v"   : "KERI10JSON00011c_",  
  "t"  : "log", 
  "i"  : "EaU6JR2nmwyZ-i0d8JZAoTNZH3ULvYAfSVPzhzS6b5CM",  
  "dt"  : "2020-08-22T17:50:09.988921+00:00", 
}

The message type field, t, is the resource base, the identifier prefix field, i , is the next part of the template and the datetime field, dt, is the last part of the template. This has the disadvantage that we need a new message type for each base resource. We can fix this by adding a base field, b and then just using one message type.

{
  "v"   : "KERI10JSON00011c_",  
  "t"  : "qry", 
  "b" : "logs",
  "i"  : "EaU6JR2nmwyZ-i0d8JZAoTNZH3ULvYAfSVPzhzS6b5CM",  
  "dt"  : "2020-08-22T17:50:09.988921+00:00", 
}

But this still has the disadvantage that every variation of a URL resource template requires a new field set in the message. This feels like an explosion of message structure variations.

Restful Mimic Tunnel

In this approach the restful verb becomes the value of the message type field, t and the full resource URL path becomes the value of the resource field, r.

{
  "v" : "KERI10JSON00011c_",  
  "t" : "get",  
  "r" : "/logs/EaU6JR2nmwyZ-i0d8JZAoTNZH3ULvYAfSVPzhzS6b5CM/%272020-08-22T17%3A50%3A09.988921%2B00%3A00%27"  

}

This may require up to 5 new message types, if the full semantics of rest are to be mimicked and tunneled. these are: pst, get, put, pch, del. (following the KERI custom of three character message types).

We can fix this by using one message type and adding a verb field, b. (the letter `v' is already taken for version string)

{
  "v" : "KERI10JSON00011c_",  
  "t" : "req",  
  "b" : "get",
  "r" : "/logs/EaU6JR2nmwyZ-i0d8JZAoTNZH3ULvYAfSVPzhzS6b5CM/%272020-08-22T17%3A50%3A09.988921%2B00%3A00%27"  
}

The advantage of the tunneled mimic is that it does not introduce any new structure or dependencies, given an implementation is already tooled to support a restful HTTP interface. In other words libraries for parsing URLs may be used to parse the "r" field and extract the necessary parameters for replaying the databases. The disadvantage is that URL parsing tooling now becomes a requirement even for implementations that do not support HTTP restful interface. But that seems like a small disadvantage given the ubiquity of URL parsing libraries. The principle disadvantage in terms of expressive power is that URL reserved text characters must be URL encoded in the Mimic tunnel whereas in the restful path explosion there is no requirement to URL encode.

It feels like the mimic makes the most sense in general because is minimizes new stuff given that one is going to implement the Restful API anyway.

[pfeairheller]

I agree that the RESTful Mimic Tunnel is the better approach. I wonder if the additional b field is necessary. Though the exercise started out by exploring the RESTful API, I don't believe the resulting messages for querying need to account for all the HTTP verbs. These messages are only analogous to the GET operations and thus the b field can be dropped.

All mutations of a KEL are through the events already defined outside this proposal and with the exception of DELETE I don't believe overlap with the CRUD operations of REST. Adding the others here could cause confusion with the other messages (ROT, DRT, etc) already defined.

So I think we could get away with

{
  "v" : "KERI10JSON00011c_",  
  "t" : "req",  
  "r" : "/logs/EaU6JR2nmwyZ-i0d8JZAoTNZH3ULvYAfSVPzhzS6b5CM/%272020-08-22T17%3A50%3A09.988921%2B00%3A00%27"  
}

As for the value of the t field well... naming is hard and I won't offer an opinion. :-)

[SmithSamuelM]

@pfeairheller I agree that we don't need to support all the verbs (at least at this time if ever) but there is something in me that wants to generalize the mimic to be able to support other verbs should a need for them arise in the future. So i suppose we could drop the 'b' field or make it optional and when not provided assume that its defaults to 'get' and then should it ever come up that we want or need another verb then that other verb must provide the 'b' field. I would prefer that to adding another message type for another HTTP verb.

[pfeairheller]

@SmithSamuelM I like the idea of leaving it off with the understanding of making it default to "get" in the future.

[SmithSamuelM]

After some more thought, there is a third alternative. When one looks at how web frameworks work, the heavy lifting of URL composition encoding and decoding is done by the framework and the endpoints just get a parameters dict and a query string dict to process. These have already been URL decoded and parsed. Likewise instead of sending the URL itself with query string we could just send the elements that are used to compose the URL. Path template elements and query parameters all in one query dict. In the restful interface there are two base urls, a collection URL, and a single element URL. The collection URL depends on query parameters for operations on the collection. But a special case of any collection is a single element. Thus the single element base URL is in this sense redundant. It is useful however because of the clarity that single element URLs provide about intent. However under the hood one can do everything with the collective base URL and an equivalent query string. So the third option is somewhere in between. Its an exploded query string as dict or mapping.

{
  "v" : "KERI10JSON00011c_",  
  "t" : "req",  
  "r" : "logs",
  "q" : 
  {
       "i":  "EaU6JR2nmwyZ-i0d8JZAoTNZH3ULvYAfSVPzhzS6b5CM",
       "dt": "2020-08-22T17:50:09.988921+00:00"
  }
}

the field r, is the base resource the field q is the query parameters exploded into a mapping. And

{
  "v" : "KERI10JSON00011c_",  
  "t" : "req",  
  "r" : "logs",
  "q" : 
  {
       "i":  "EaU6JR2nmwyZ-i0d8JZAoTNZH3ULvYAfSVPzhzS6b5CM",
       "after": "2020-08-22T17:50:09.988921+00:00",
        "before": "2020-08-22T17:50:12.988921+00:00"
  }
}

The advantage of the exploded query string approach is that there is no need for URL parsing but the endpoints map so the dependencies are actually less (because most web frameworks do the URL parsing anyway). The major drawback of the exploded query string is that a JSON object is more verbose than a URL path plus query string (as block delimiters add a few characters over ? = & separators. But if there is any % escaped encoding in the query parameters then the compactness flips to the advantage of the exploded query mapping. And if using CBOR or MGPK then the query map is always more compact than the encoded URL. So I am liking the third alternative a little better than either of the first two.

[pfeairheller]

@SmithSamuelM I like this third approach better as well. Getting rid of URL parsing is a big win, in my opinion. If we wanted to gain some compactness back, allowing the single element case to be represented as a string for the q field or as a different field instead of q. So something like

{
  "v" : "KERI10JSON00011c_",  
  "t" : "req",  
  "r" : "logs",
  "q" :  "EaU6JR2nmwyZ-i0d8JZAoTNZH3ULvYAfSVPzhzS6b5CM"
}

Of course saying this while working on one of the statically typed implementations I realize that could be a pain. So maybe a field other than q would be better.

[sethjback]

While I think the REST design above makes sense for a web base API, I would be hesitant to import any of those design decisions into the core protocol. My main concern is just keeping the division clean between the KERI protocol itself and access patterns that live higher up the stack.

An incidental example - pretty much all the services I work on use gRPC. If I were to take the KERI reference package and deploy it internally I would pass all the data around using protobuf. I could create a message analog the actual KERI protocol message format, then very easily parse the KERI JSON outside messages into it. My point is that all my interfaces to my services would not be REST based - I am really just interested in the defined KERI messages. I would hate to have to have a field that would require parsing twice just so that it could mimic a RESTful API. (Also as an aside, if I was going to stand up a public api I would probably use graphql not a REST based one, so mimicking REST wouldn't help).

I think having the KERI spec define the data it needs, how to format, sign, secure it, etc., is the right level to work at. We could create reference watchers/witnesses with REST APIs, but I would hate the spec to be tried to that specific implementation (or even worse require its implementation to be consistent with the spec even if it will never be used).

All that said - I like the 3rd suggestion: it seems consistent with the current message format and would require less parsing (you could act on the data after parsing the KERI message rather than having to parse the KERI message and a URL field inside it).

[SmithSamuelM]

@seth I agree that the KERI core protocol does not need to be tied too closely to a Restful interface and may suffer for it. But I find the exercise of thinking about what type of queries that a restful interface would have helpful to provide some structure.

So the third option may be informed by the query parameter structure without being strictly tied to it. we can use more compact labels for example that one would usually shy away from in a Restful query string.

[SmithSamuelM]

@pfeairheller

A suggestion to enable the more compactness is for the single element form to just have the "i" field .

{
  "v" : "KERI10JSON00011c_",  
  "t" : "req",  
  "r" : "logs",
  "i" :  "EaU6JR2nmwyZ-i0d8JZAoTNZH3ULvYAfSVPzhzS6b5CM"
}

The problem is the parsing logic gets more complex for each different field configuration which makes one want to differentiate by having a different message type for each field configuration set. This was the problem with the exploded form above. But if we narrowly or linearly constrain the field set, we can have a compromise that only requires at most two message types for the two formats: single element vs collective.

In other words, a compromise would be to have two message types. One for the collective req and one for the single element qry. the single element has a restricted defined set of fields which are optional. The set of optional field is fixed and the appearance of each element in the set is linearly constrained as a traversal so there is no combinatoric explosion. This mimics the single element template URL approach /logs/{pre}/{datetime} (There are good reasons why this approach is so popular. One is because it naturally allows graph or tree traversal of structured data).

Single element

Clone whole database

{
  "v" : "KERI10JSON00011c_",  
  "t" : "qry",  
  "r" : "logs",
}

Clone Log for Prefix

{
  "v" : "KERI10JSON00011c_",  
  "t" : "qry",  
  "r" : "logs",
  "i" :  "EaU6JR2nmwyZ-i0d8JZAoTNZH3ULvYAfSVPzhzS6b5CM"
}

Single element entry in log for prefix

{
  "v" : "KERI10JSON00011c_",  
  "t" : "qry",  
  "r" : "logs",
  "i" :  "EaU6JR2nmwyZ-i0d8JZAoTNZH3ULvYAfSVPzhzS6b5CM",
  "dt": "2020-08-22T17:50:12.988921+00:00"

range of entries in log for prefix

{
  "v" : "KERI10JSON00011c_",  
  "t" : "qry",  
  "r" : "logs",
  "i" :  "EaU6JR2nmwyZ-i0d8JZAoTNZH3ULvYAfSVPzhzS6b5CM",
  "dta": "2020-08-22T17:50:12.988921+00:00"
  "dtb": "2020-08-22T17:50:12.988921+00:00"

Collective

Collective allows flexibility in what in in q that the single element format does not. It becomes a catchall that allows some optionality in the specification for future proofing that the single element message type does not allow.

{
  "v" : "KERI10JSON00011c_",  
  "t" : "req",  
  "r" : "logs",
  "q" : 
  {
       "i":  "EaU6JR2nmwyZ-i0d8JZAoTNZH3ULvYAfSVPzhzS6b5CM",
       "dta": "2020-08-22T17:50:12.988921+00:00",
       "dtb": "2020-08-22T17:50:12.988921+00:00"
  }
}

{
  "v" : "KERI10JSON00011c_",  
  "t" : "req",  
  "r" : "logs",
  "q" : 
  {
       "i":  [
                 "EaU6JR2nmwyZ-i0d8JZAoTNZH3ULvYAfSVPzhzS6b5CM",
                 "EPzhzS6b5CMaU6JR2nmwyZ-i0d8JZAoTNZH3ULvYAfSV"
              ]
  }
}

---

[SmithSamuelM]

Authentication Support

An issue not considered above but that may be timely for this proposal is access restrictions or access control for queries. Unlike the event messages which are cryptographic commitments or disclosures originally initiated by some controller that are verified according to the protocol against signatures by the controller of the associated identifier, or receipt messages which are merely conveying signature and other cryptographic material used to verify signatures on events, a query is asking some host to disclose KELs. As a result it makes sense to include a bare bones authentication mechanism in the query to enable authorization of that disclosure by a layer above KERI. For security reasons its best if the authentication happen sat the query layer. This was discusses today in the dev call. But to summarize. The heavy lifting for authentication is already done by KERI. That heavy lifting is providing the current key state for a given identifier. This means that a request may have attached to it the identifier of the requester and a signature of the request. This essentially authenticates the requester. What this does not protect against is a replay attack of a signed request. Requests need to be timely. The simplest non-interactive mechanism to protect against replay attacks is a date-time stamp in the request message. The server then refuses any signed requests whose datetime stamps are not within a narrow time window around the server's current datetime. An attacker has to replay within that window. Thus stale requests outside that window will be refused. So without compromising private keys an attacker can't request the information. The server can increase the protection by keeping a cache of requests within a window and enforcing monotonically increasing datetime stamps on requests therefore making any replay attacks within a window detectable by the requester. (As the server will only respond to the first, request at a given datetime so a successful replay attack results in no response being returned to the requester thereby exposing the attack).

Non-interactive Authentication Support for Query Messages

Given that addition of a datetime stamp in each request, it seems than that the preferred query message format is now the Collection version. As follows:

{
  "v" : "KERI10JSON00011c_",  
  "dt": "2020-08-22T17:50:12.988921+00:00",
  "t" : "req",  
  "r" : "logs",
  "q" : 
  {
       "i":  "EaU6JR2nmwyZ-i0d8JZAoTNZH3ULvYAfSVPzhzS6b5CM",
       "dt": "2020-08-22T17:00:00.988921+00:00",
  }
}

Attached to the serialized query message body is a count code for a couple, the requesters fully qualified identifier, and the fully qualified signature or signatures (if its multi-sig). The authentication signature(s) is always verified against the latest available keystate known to the server for the requester. This means that the establishment event seal used for the signatures does not need to be attached to indicate which keys were used. It may be assumed to always be the latest keystate. If not that the request is not timely anyway.

The dt field in the request body top level is the datetime of the request, whereas the dt field in the q block is the 'dt' of the log entry. This separates the request body from the query body and avoids confusion without having to define unique field labels.

To regain some of the simplicity of the non-collection query we can take advantage of the fact that in KERI we enforce ordering of the appearance of fields in a mapping. (ordered mapping). This means that the q block could be interpreted as the a non-collection request if all the fields in the q block on non-collections and the ordering and presence or absence of fields mimics a non-collection traversal of the resource path.

Interactive Authentication

Also discussed in the meeting was future support for interactive authentication. The advantage of interactive authentication is that it may makes replay attack even more difficult. In interactive authentication the server responds to any query with a nonce. The requester then re-submits the query with the nonce included and signs the revised message that includes the nonce. The server than only accepts the first nonced and signed query. The nonce can include other information such as IP address information of the requester to make it more difficult for a replay attack to succeed as it ties the request response to a given ip address. The nonce format is TBD as well as the exact request response set of messages.

For example a query with a nonce would look like this:

{
  "v" : "KERI10JSON00011c_",  
  "ot": "ABCDE12345",
  "t" : "req",  
  "r" : "logs",
  "q" : 
  {
       "i":  "EaU6JR2nmwyZ-i0d8JZAoTNZH3ULvYAfSVPzhzS6b5CM",
       "dt": "2020-08-22T17:00:00.988921+00:00",
  }
}

The ot field is the one-time nonce field

It was decided that for now the non-interactive mechanism is sufficient.

One can always layer on or add other multi-factor authentication mechanisms in addition to the non-interactive or interactive query messages. But the strongest proof of authenticity is a signature made with the private keys. It just needs a proof of timeliness do to protect against replay attacks.

T

[sethjback]

@SmithSamuelM could you clarify for me the use of datetime as a query parameter (not in the context of authentication - but the before/after timestamp for log entries). I am struggling to envision a time where I would want to query the log based on a timestamp and not sequence number (e.g. I have sn X, give me anything before/after/at X). Given the async nature of when I may actually receive an event, it seems like I could never rely on my internal "received" timestamp when making a query request. And if I am relying on some context based on received events and the timestamp of trusted controller/witness/watcher, why wouldn't I still just use the sn of the event as my anchoring point in the KEL rather than that timestamp?

[SmithSamuelM]

@sethjback

There are two logs. One is the log where events are listed in order by sequence number (sn). This log can be forked when there is a recovery rotation that disputes or invalidates interaction events that were signed with compromised signing keys. This log, because of the forks, does not preserve the first seen order of events. A fork will have at least one or more duplicate events with the same sn. So simply replaying by sn will not be sufficient.

In case it wasn't clear the resource base /events above is the endpoint for querying the sn based log. Whereas /logs is for querying the first seen ordering. There is only one copy of the actual events stored, we just have two different tables of indexes one for /logs and one for /events.

In order to replay a possibly forked log in first seen order requires tracking the first seen order of events in some other way besides the sn. One way to do this is to have a linear table that is indexed by yet another sequence number (not the sn in the event) but merely a counter that indicates first seen order across recovery forks. But this first seen counter does not map one-to-one to the sequence number. So counter = 4 may not be sn = 4. So querying the first seen log is not the same as querying the sn log for the authoritative event at a given sn (after any recovery rotations). This first seen counter must be monotonically increasing. But this is no different from a monotonically increasing datetime stamp (both are counters) The advantage of using a datetime stamp as the first seen counter is that when later comparing logs from different watchers that one trusts (and hence trust their date time stamp) One can use the datetime stamp to help reconcile duplicity. Furthermore, because there is not a one-to-one correspondence, then there is little advantage to using a counter (other than its may be shorter). One might as well use a datetime stamp because of the datetime stamp's other advantages.

One reason to store duplicates of the same sn instead of merely storing the last seen (recovered version) is it aids in duplicity detection and reconciliation.

The normal use case for replay of the first seen event log is to reproduce it somewhere else (i.e. clone it) in the exact order of first seen, start to finish. For example a new watcher that is bootstrapping will want a first seen replay of a log from some other witness or watcher so that the watcher sees all the events as seen by the the other one. This insures complete fidelity. Most importantly, a replay (clone) of the first seen log in its first seen order into another database will not only reproduce the first seen log in order but will also guarantee to reproduce the exact matching sn log with all forks intact. Whereas a replay of a sn log with only the latest version of the event at any fork included in the replay will not reproduce either the first seen log or the sn log with all forks intact. This means that the sn log is not suitable for future replay or duplicity detection or reconciliation but merely for validation of the key state. Development of KERI so far has focused on validation logic not replay or duplicity detection or reconciliation. As we move into supporting witnesses and watchers we need to support full replay (cloning) in first seen order. The first seen log is indeed therefore the true "append only event log" we use for replay. Given that the normal use case is for using the first seen event log is to replay the whole log (clone), then the main purpose of a query on the first seen log for a given datetime or a range of date times to allow restart of replay in the case that full replay gets interrupted and has to be restarted at the point of interruption. So instead of restarting from the beginning, the query of a given datetime after allows the replay to be resumed with all events after the datetime of the latest event received. Generalizing to other use case means allowing arbitrary ranges including the query of a specific datetime entry..

Alternately, another approach to providing a lossless replay (clone) of first seen events is to store events in a DAG (directed acyclic graph) where a depth first search of the DAG would reproduce the first seen log in exact order with all forks intact. This means using a more complex DAG structure. LMDB trivially allows forking using duplicate entries but does not enable a depth first DAG search without adding the DAG links at each entry. (Well actually one could do a depth first search and construct the DAG on the fly using the LMDB duplicate entires but that would be really expensive). In either case, building a DAG seemed like a big lift when all we needed in order to support first seen replay (cloning) was to just store a reference (i.e. the digest) of each event in linear order as indexed by a monotonic counter (datetime).

Were one to use a DAG instead, then querying a replay of the dag would require a special query that says starting at some sn replay the dag in a depth first search order. Given the normal use case of replay is to clone it did not seem to me to be worth the complexity of building a DAG. However I expect that we could support both as an option. That would mean having another resource base /dags that allows queries of dag entries for replay instead of a linear append only event log. So an implementation could choose to use a DAG instead of a linear index (essentially the linear time stamped index is what you would get by performing a depth first search of the DAG). So from purely performance comparison, given that full replay is the normal use case, (when one wants to validate key state one queries the sn log at /events ) then its a wash on storage to have an index of digests in a linear table vs having the references or pointers for a DAG structure. And the computation cost of storing into a DAG replaying via a depth first traversal of the DAG is much much more than storing into and replying from a linear log .

[SmithSamuelM]

In python the first seen and sn tables are filled when an event is first seen. The Kever object does this with its .logEvent method. The first parameter indicates to the method that this is a first seen condition as opposed to a later async event with additional signatures. The .fse database is the first seen event table and .kes is the key event table in sn order with duplicates. Here is the code:

 def logEvent(self, serder, sigers, first=False):
        """
        Update associated logs for verified event.
        Update is idempotent. Logs will not write dup at key if already exists.

        Parameters:
            serder is Serder instance of current event
            sigers is list of Siger instance for current event
            first is Boolean True means first seen accepted log of event.
                    Otherwise means idempotent log of event to accept additional
                    signatures beyond the threshold provided for first seen
        """
        dgkey = dgKey(self.prefixer.qb64b, self.serder.diger.qb64b)
        dtsb = nowIso8601().encode("utf-8")
        if first:
            self.baser.setDts(dgkey, dtsb)  #  first seen so dts is first seen
        else:
            self.baser.putDts(dgkey, dtsb)  #  do not change dts if already

        self.baser.putSigs(dgkey, [siger.qb64b for siger in sigers])
        self.baser.putEvt(dgkey, serder.raw)
        if first:  # append event dig to first seen database in order
             dtsb = self.baser.appendFse(self.prefixer.qb64b, dtsb, self.serder.diger.qb64b)
             blogger.info("Kever process: First seen at %s\nKEL event = %s\n",
                                     dtsb.decode("utf-8"), serder.ked)
        self.baser.addKe(snKey(self.prefixer.qb64b, self.sn), self.serder.diger.qb64b)
        blogger.info("Kever process: Added valid event to KEL event = %s\n", serder.ked)

[pfeairheller]

I'm just about to push a PR that implements most of this in kerigo. It is using BadgerDB which does not support multiple values per key so I had to implement a Set and OrderedSet on top of Badger. So it took me a bit longer than I had hoped but now that this is in place, we should be able to demo first seen and sequence number replay.

[sethjback]

@SmithSamuelM

Thank you for the clarification! I had a couple follow ups to make sure I understand:

there are two logs

I just want to make sure I parse this correctly: as I understand it there is a single KEL, but it could contain “forks,” arising from duplicitous events, which signal a key compromise or “bad acting” by the controller. The fork is expressed as multiple events for a single sn. Which branch of the “fork” is followed is controlled by which event gets “written” to the log on witnesses and watchers dictated by the “first seen wins” rule. First seen on witnesses means the first event that the witness receives enough signatures to meet the threshold. And for watchers it is the first event that has enough witnesses to meet the threshold. Retaining events that did not get “written” to the KEL is important in many (all?) contexts to attest to duplicity when asked.

For my question regarding the timestamps on queries - it was less about the specific implementation of the above ideas (i.e. how any given implementation is processing, storing and indexing received events to make sure it abides by the first seen wins rule and can provide correct reply mechanics/order for all paths/forks through the log). The question is around the purpose of the query message. From my understanding (again just making sure I am on the right track here), query messages are to allow a third party (defined as NOT the witness/watcher/controller being queried) to ask for details about the witness or watcher’s “view” if you will of the KEL. That encompasses either a full replay, the state of any given event (sn), or even the current KEL state.

In the case of replay, I understand what your were saying about how the timestamps could be used to ask for replay to restart at a given point if it was interrupted. As you pointed out, though, there are potentially multiple ways of storing/indexing/processing events to make sure you follow the first seen wins rule and facilitate correct replay. Monotonic timestamps are perhaps the most efficient/easiest/safest/etc. I guess my contention though is that is an implementation detail, not necessarily a spec detail. Wouldn’t it be almost as easy for a 3rd party to ask for replay starting from a particular sn as it would be for a timestamp? There would be some more implementation logic (e.g. truncate to the last fully received sn and start from there), but unless I’m missing something (entirely probable!) I would argue this is more consistent with separating the spec from implementations.

It seems the spec is asking that certain constraints be met that are dictated by event receipt order. These constraints could be met using timestamps, but do not necessarily have to be. If we add timestamps as a defined field in a spec message type, don’t timestamps on events essentially become a requirement?

[SmithSamuelM]

@sethjback

Well not exactly. Only interaction events may be recovered from (at least for non-delegated identifiers). So when a signing key is compromised the controller may perform a rotation to recover from the compromise. The rotation specifies the prior event. This may not be the most recent interaction event published and first seen by watchers. The rotation by picking an earlier event to be the prior event forks the log. The later in terms of SN interaction events have been first seen, but the rotation supersedes and makes the key state according to the controller to be what the rotation specifies. However because the interaction events were signed and verified and first seen already, the controller may be held liable for them, from the standpoint of the watchers. Signatures are non-repudiate. So those interaction events are part of the log. They count as reconciled duplicity in the narrow sense that the key state is updated to remove the compromised keys. But they are in disputed. The white paper refers to these as disputed events. A controller is always ultimately responsible for LIVE key compromise which these are. The rotation acts to limit the damage of the compromise. But the controller and any validators that have seen and acted on those compromised events must still come to terms about any harm that came to the validator as a result of the LIVE compromise. The governance framework for the ecosystem in which those interaction events participated may help to resolve the dispute.

As mention in the other Issue on replay modes. There are several use cases for replay modes that include a controller backing up its KEL or replaying and reverifying a KEL from a backup.
And include a controller replaying a KEL. To its witnesses or a witness that is being spun up. None of these are third parties per se. So access restriction on replay should consider all parties and relationships and if those are permitted or not based on the policy of the replayer vis a vis the replayee

[SmithSamuelM]

The problem is that SN are not unique on a log with forks. So the logic of replaying from a sequence number has to additionally specify is is th first or last event with that sn etc or always all. It think that given there might be other implementation ways of doing replay that we can have some flexibility and options in the spec but we do need to have at the very least a reference implementation that practiacally works. It’s doesn’t have to be th only way just a practically good way. And given that replay by date time is the most effection easy way it makes sense for us to start there and then we can add other ways as options when or if someone wants to implement that way.

[SmithSamuelM]

Also with forks all the events with the same SN will not be contiguous. So how do you query a non-contiguous set of SN? You certainly can’t use them in any valid replay because they are not continuous. So you can maybe start replay at the first event with a given SN. But if replay is interrupted you can’t simple restart at some SN or the sn of the latest event you received because well they are not contiguous. These issues make any true FSE replay difficult if one is querying by SN. So date time seems the most practical solution. As mentioned above you could create another sequence number counter that is the sequence of first seen which is a different sequence than the SN in the event log. But a mono tonic date time is a counter and has the advantage of providing date time information. But pretty much those are the two practical choices.

[SmithSamuelM]

One could have both a date time stamp and a FSE counter and allow querying both ways. But the date time stamp is valuable for making comparisons between a pool of trusted watchers. A new vacuous watcher added to a pool might be susceptible to a dead attack for any identifiers it does not preload into its log. An attacker could troll new watchers to see if their preload is missing an identifier for which the attacker has compromised old keys. Given they find such a watcher than the attacker would send a compromised duplicitous event log to the new watcher which would accept it has first seen. However the date time stamps of that watcher will be recent. (It’s a watcher under the validator’s control so the validator trusts is date time stamps). So when the validator compares the log for that identifier amongst the other logs in its pool of watchers it will see that the compromised log has more recent date time stamps whereas the other watcher logs will have old date time stamps for their alternate non-compromised logs. This provides a useful metric for reconciling the duplicity. It’s a tool at the disposal of the validator’s confirmation network to aid in resolving or reconciling inconsistency in the first seen versions among the watchers.

There are two forms of duplicity. Duplicity of first seen between watchers and duplicity of alternate but not first seen by a given watcher.

So the SN log keeps all first seen events which may include recovery forks. This allows watchers to hold Controllers accountable for compromised signing keys and likewise allows a controller to detect a compromise has happened by querying its witness logs. A query of the SN log may provide all alternate events with the same SN given duplicates in the database. And the FSE log enables replay cloning of the first seen events in the order they were first seen. Neither of the two logs (index tables) is structured to do both.Even a DAG would require a additional duplicate table to query for duplicate events with the same SN. A pathological SN log could have many many duplicates. If for example a side channel attack against signing infrastructure was not discovered for some time. The controller would see duplicitous signed interaction events in its witness logs, do a rotation recovery and then immediately see new compromised duplicitous interaction events made with the new signing keys in its witness logs, do another recovery, etc. After a few of these the controller might then suspect its signing infrastructure was compromised and do the next rotation using different signing infrastructure. However now its witnessed event log have numerous duplicate interaction events with same SN from multiple branches (forks) all separated in FSE by the number of compromised events made with a given set of compromised signing keys. All which are first seen for those witnesses. Ultimately the controller is able to recover control without abandoning the identifier because the pre-rotated keys were not compromised only the signing keys, but will have to repair any damage done via the compromised interaction events. This means the controller will want to query its own witness event logs to find out the extent of the damage (i.e. get all the duplicates that have been superceded at each SN)

[SmithSamuelM]

Based on feedback and some more thinking, here is a revised proposal that maybe better solves the ordering problem of first seen replay.

We introduce a new ordinal called the first seen ordering number (fson) or on or fn for short to distinguish it from the authoritative event sequence number sn. I was initially reluctant to introduce yet another ordinal besides the sn to avoid confusion but it seems like it may be best to just bite that bullet. So given an fn we have the first seen table of events indexed by fn (or on not sure which one is better) whose values are the event digests. We also already have a table indexed by event digest whose values are datetime stamps of when the event was first seen (also used by escrows before first seen but then updated to be the first seen datetime once first seen). It was this later table that convinced me to make this revised proposal to use the fn. Because we already have the datetime stored we can attach the datetime to the fn replay and get both. Also using an ordinal for indexing replay is more compact that using a datetime.

FN based queries

Replay all events

{
  "v" : "KERI10JSON00011c_",  
  "dt": "2020-08-22T17:50:12.988921+00:00",
  "t" : "req",  
  "r" : "logs",
  "q" : 
  {
       "i":  "EaU6JR2nmwyZ-i0d8JZAoTNZH3ULvYAfSVPzhzS6b5CM"
  }
}

Replay single event

{
  "v" : "KERI10JSON00011c_",  
  "dt": "2020-08-22T17:50:12.988921+00:00",
  "t" : "req",  
  "r" : "logs",
  "q" : 
  {
       "i":  "EaU6JR2nmwyZ-i0d8JZAoTNZH3ULvYAfSVPzhzS6b5CM",
       "fn": "3"
  }
}

Replay starting at offset of fn=3 of up to 100 events

{
  "v" : "KERI10JSON00011c_",  
  "dt": "2020-08-22T17:50:12.988921+00:00",
  "t" : "req",  
  "r" : "logs",
  "q" : 
  {
       "i":  "EaU6JR2nmwyZ-i0d8JZAoTNZH3ULvYAfSVPzhzS6b5CM",
       "fn": "3",
       "limit": "100",
  }
}

Replay all events after fn

{
  "v" : "KERI10JSON00011c_",  
  "dt": "2020-08-22T17:50:12.988921+00:00",
  "t" : "req",  
  "r" : "logs",
  "q" : 
  {
       "i":  "EaU6JR2nmwyZ-i0d8JZAoTNZH3ULvYAfSVPzhzS6b5CM",
       "fn": "3",
       "limit": "all"
  }
}

For compactness we could use f instead of fn and "l" instead of "limit" .

The replay would look like this:

event + cc + fn + dt + cc + sigs + cc + receipts + ... other attachments event + cc + fn + dt + ... ...

where event is the encoded event, cc is the fully qualify attachment type counter code, fn is the fully qualified first seen order number, and dt is a new fully qualified date time.

We need to add a new counter code for this new attachment group of (fn + dt) We already have a counter code for sequence numbers so we can reuse it here (given the context) for the fn We need to define a new attachment type derivation code that of an encoded iso8601 datetime in base64

If a replay is interrupted then it can be resumed using the latest fn received

Please comment on this revised proposal.

[pfeairheller]

Am I understanding correctly that this new attachment group (fn + dt) is only present in the stream replay of logs (first seen mode) in response to a query message? Or is it always present in first seen replay mode (for example a database clone not initiated by a query message)?

[SmithSamuelM]

It could be optionally included in any first seen ordered replay. It provides two features. A way to restart an interrupted replay via the last received fn and a the date time stamp of when that event event was first seen which a given replayee may want to observe. The unique group specific count code for that group means it can be optional since it is its own group.

[sethjback]

I like the updated proposal.

Two thoughts/ideas for comment that play off of each other, then two concerns/questions:

1. Should a query for a single sn return multiple events?

If we specify that a query for a single sn means “I want the even that you have accepted into your version of the KEL” this would simplify the query logic. A watcher would then detect duplicity by noting if there are different versions of the event at that sn being returned from different witnesses.

That would not give the watcher an indication of whether the witness had observed potential duplicitous activity. If the watcher wanted that level of information, they could request a reply query. Which leads to my next thought:

2. What if instead of fn as first seen number, it is simply the digest of event to start with.

Two thoughts here: the first is that this digest is already used as part of the spec for events. The second is this would avoid adding a new ordinal: If I want a full dump, start at the beginning (maybe indicated by an empty fn field). If the replay gets interrupted, I can send the digest of the last seen event, and the replay can start from there. This would allow the witness to decide on their own method for storing and indexing the first seen replay order but still alow external parties with no knowledge of that method a way to start at a specific event. An added benefit is that since the event digesting code is already part of the spec it should be easy to reuse that code to request a replay.

Now I have two questions on the updated proposal:

1. The dt field

Is this going to be marked as an optional parameter? I completely understand the value of a timestamp to a watcher in resolving duplicity. I just keep thinking if we make it non-optional we are effectively adding timestamps as a requirement. And if we make it optional then it seems to add complexity in parsing the reply.

Just to be clear I am not arguing against its value, or against the benefit of any given witness implementation providing it via their query methods. I am simply wanting to confirm that we are adding as part of the defined query message at the spec level.

2. DDOS using forked events

Is there a potential vector here to DDOS a witness/watcher network? Let’s say I compromise your key, either current or past, and my goal is nothing more than to bring your witnesses offline (effectively disrupting any watchers relying on them). I could flood your witnesses with duplicate “valid” events that would not get added to the log, but would be saved as duplicitous for that event sn at a later fn. It would seem possible in these circumstances to very quickly break the entire replay query mechanics.

[SmithSamuelM]

@sethjback

1. Should a query for a single sn return multiple events?

Not sure I understand this

2. What if instead of fn as first seen number, it is simply the digest of event to start with.

In general I think APIs on a database work best if they at least have an option that mimics the underlying table structure. Layering on APIs that hide the table structure is good if there is a use case that benefits from the layer. The question always arises though from a performance perspective, is if there is not a table that makes the query easy, then it must be computed on the fly, and that is usually very costly. So in order to query in First Seen Order by digest we would need to add another table that indexes the first seen fn by the digest. I.e. the key is the digest the value is the fn. So this might be a good addition but under the hood we still need the fn table in order to replay in order. Ie key is fn val is digest. So I don't see this as replacing the fn query but might be a useful additional query which would require an additional table.

[SmithSamuelM]

Here are the proposed new codes to support the revised proposal

fn are 16 bytes (128 bits) and are the same length and code as sn but distinguished by context. fn are encoded using existing Matter Codex entry Salt_128: str = '0A' # 128 bit random seed or 128 bit number

Attached date times have a new crypto material Matter code labeled DateTime. The new entry in the Matter Codex is:

DateTime: str = '1AAG' # Base64 custom encoded 32 char ISO-8601 DateTime

This code represents a specific variant of ISO-8601, that is, time zone aware UTC offset form of an ISO-8601 datetime with microseconds and HH:MM UTC offset to a Base-64 compatible version. This variant of ISO-8601 has this format: 2020-08-22T17:50:09.988921+00:00 for positive UTC offset and this format: 2020-08-22T17:50:09.988921-00:00 for negative UTC offset. The length of this ISO-8601 variant is 32 characters. This UTC format includes 3 non-Base 64 characters. Namely :.+ . The custom Base-64 encoding is to replace these non-Base64 characters with Base64 equivalents. Specifically, every where one of the non-Base-64 characters :.+ appears in the date time, it is replaced with the corresponding Base64 character from the set cdp where c is for colon, d is for dot or decimal, and p is for plus. This keeps the size smaller than converting the raw ascii text directly to Base 64. The fully qualified version includes the 4 char derivation code 1AAG as defined above. The total length of the fully qualified, qb64, Base64 representation is 36 characters. This converts to 27 Base2 bytes, in qb2. The raw bytes in base two is 24 bytes long.

A qb64 encoding of the datetime:

`2020-08-22T17:50:09.988921+00:00' is as follows:

1AAG2020-08-22T17c50c09d988921p00c00

The python code for doing the custom Base64 encoding/decoding from ISO-8601 text is as follows:

>>> toB64 = str.maketrans(":.+", "cdp")

>>> fromB64 = str.maketrans("cdp", ":.+")

>>> a = '2020-08-22T17:50:09.988921+00:00'
>>> b = a.translate(toB64)

'2020-08-22T17c50c09d988921p00c00'

>>> c = b.translate(fromB64)
'2020-08-22T17:50:09.988921+00:00'

>>> c == a
True

The attachments for First Seen Event replay includes a new optional attachment group (besides signatures and receipts) This new group is called a FirstSeenReplayCouple and consists of a couple of fully qualified items, an fn followed by a dt (see the encoding above).

The new Counter Codex table entry for this new attachment group couple is as follows:

FirstSeenReplayCouples: str = '-E' # Composed Base64 Couple, fn + dt.

[stevetodd]

Some comments on this thread:

Requesting in First Seen Order

My first recommendation is that we keep the marker/token/fn/timestamp opaque to maintain flexibility for implementations. It's just a bookmark used by the remote node for knowing where to start. It could be a sequence number fn, monotonic timestamp, or some other mechanism, but its function doesn't need to be and shouldn't be specified. There are plenty of ways to track insertion order and we shouldn't let our specification limit the types of databases used on the backend.

Additionally, the remote node receiving the query can take an isd triple and find the datetime, fn, token etc and know where to start. For example, in keripy, you can take the identifier and the digest and lookup in the dtss the timestamp for the isd triple. There's no need to request by fn or timestamp. I also think that we should avoid timestamps in the request API as well since it basically will break caching capabilities on the HTTP side (I have more feedback to provide on the HTTP API in a bit).

Timestamps

I do agree that validators are interested in knowing when a watcher received an event. We'll want a mechanism to provide that with the events. I think the ISO-8601 format is a little absurd in its complexity when we could just use UTC epoch time and encode it using the existing base64 integer encoding. It doesn't make sense to encode it as ISO-8601 format since we're losing its main benefit of readability when we obfuscate/encode it.

I also wonder whether receipts ought to include signed timestamps, though that kind of blows up a lot of things in the current structure for receipts.

[SmithSamuelM]

First Seen Ordering

@stevetodd While it's true that an isd triple allows one to look up the dts it does not however allow one to resume a replay at any point in the first seen order unless of course one has a table indexed by dts that points back to d. It is therefore not true that the isd triple by itself tells one where to continue for first seen order. Recall that recovery may have created multiple events with the same sn but each from a different sequence that spans multiple sequence numbers. The digest in the isd triple does not indicate the ordering of any set of same is but different d especially since the ordering is interspersed across multiple s. Ie they are not contiguous. This was discussed in some detail above in answer to @sethjback question. Recall that duplicates at any sn do not order themselves with respect to prior or later events. As discussed above, one either needs a DAG so that one can do a depth first search on, or some other mechanism such as an ordinal table to get a first seen ordering.

So I disagree that isd is sufficient.. To restate. the isd triple by itself does not enable a look up into the first seen order. We must add additional tables. Even if we added another table that specifically uses the the isd triple as an index to a table of first seen ordinal, such as dts or fn we would still need then yet another table that maps that ordinal back to d in order to replay in first seen order. The lookups are isd to ordinal, ordinal to d. Given an ordinal indexed table one can then find the next entry in the ordinal table to resume replay. And if we don't have an isd indexed table to ordinal but an is to d table then we have yet another lookup to go from d to ordinal. Thus we add multiple lookups in order that isd be the primary lookup besides the ordinal.

So there is a tradeoff between doing multiple lookups against just exposing the ordinal itself. Its not a bad idea to want to hide the ordinal because its only there to support first seen replay. But requiring that the standard mechanism for first seen replay hide the ordinal comes at a performance and complexity cost. Is it really better to require an implementation to support multiple tables that include an ordinal table in order to hide that ordinal vs requiring they expose their ordinal as 'fn'? No matter what an ordinal is required. For example if an implementation were to use dts as the ordinal, they would merely need to add a table that mapped dts to fn. So given that any ordinal may be exposed as 'fn' by adding a table we are really talking about what tables we want to require. We don't get rid of the ordinal by having only an indirect lookup. We just force implementations to add tables to hide it. I expect that a numeric ordinal will the most common implementation choice for performance reasons. So we may not buy much by hiding it. And if the query supports ranged replay by specifying a numeric limit for the number of replayed events then one is using an effective numeric ordinal anyway.

KERIpy will support direct lookup for performance reasons, it has the 'fn' table anyway so its little cost to expose it. The question is must it also support indirect lookup by adding a table that maps 'd' to 'fn'. Its not a bad idea.
But it would be good to see how others feel about requiring an indirect lookup as a must have versus a direct lookup or should we require both?

While I agree that we want to allow flexibility in how a database stores first seen order, for the sake of interoperability we need at least one common way that is testable. Because no matter what, under the hood, there must be a one-to-one mapping to an 'fn' ordinal, its not unreasonable to require that one-to-one mapping be exposed if for no other reason than to guarantee interoperable higher performance replay. But we should allow other optional mechanisms such as other direct ordinals like 'dt' or indirect resumption using multiple tables indexed from an isd query. The latter, no matter what, will require additional tables to get to whatever direct ordinal is used under the hood. Either way I expect that there will be options.

So the question is: 1) require replay resumption via an indirect lookup using isd for identifier prefix, sequence number, digest of the event to resume replay at. With other mechanisms as options. 2) require a numeric ordinal 'fn' with other mechanism as options. 3) require both 'isdandfn`

DateTime Format

@stevetodd While I agree that it would appear to be simpler to encode datetime using a Unix Epoch time float, there are numerous problems in general with that approach. The most obvious of these problems is that epochs are not universal across operating systems (only Unix) and the unix epoch suffers from rollover in 2038. see https://en.wikipedia.org/wiki/Year_2038_problem. Thus we would merely be both implementing a non universal date time and introducing a near term rollover problem. This is not a satisfactory option IMHO. Finally there is no standard way to increase the time resolution of unix epoch. These three problems alone are reasons why in general the scientific community has moved to iso-8601 for sensor data collection. Indeed much of the machine learning community has moved to Iso-8601 for these reasons not the least of which is support for new variants of iso-8601 with nano or atto second resolution. Higher resolution is not possible with epoch time, unless one uses a non-standard base. At the proposed one-to-one mapping from iso-8601 to a base64 variant preserves the interoperability and non-rollover features of iso-8601. Using a base-64 encoding of ISO-8601 may seem extreme at first glance but its a future proofed solution that we will not have to revisit until 9999. And we can easily add support in the future for higher resolution Iso-8601 variant with another code. And this is only for the form that appears in an attachment not in the request body. The request body is standard ISO-8601.

[SmithSamuelM]

@stevetodd the purpose of the dt in the main query body is to provide a minimal non-interactive end to end authentication mechanism that is transport independent including bare metal TCP queries. As I mentioned above, when using HTTP there are already interactive mechanism that are standard and may be used instead.

I also think that we should avoid timestamps in the request API as well since it basically will break caching capabilities on the HTTP side (I have more feedback to provide on the HTTP API in a bit).

Putting a date time field in the request body of an an HTTP request does not break any HTTP caching mechanism that I know of. HTTP caching is all based on HTTP headers. =) Thus it would be completely opaque to any HTTP caching to include a DTS in the body but enabling transport across protocols that preserves the non interactive end-to-end authentication mechanism. Hop-by-hop authentication is in general a bad idea no matter how standard it has become =( in the HTTP world . Bad security is still bad security. Interactive hop-by-hop authentication is antithetical to KERI's end verifiability and exposes all sorts of security problems. But for the sake of interoperability with HTTP its may be the preferred choice for HTTP only interface. But it must not supplant the proposed choice that is a universal mechanism. To restate, putting the DTS in the body does not obviate or prevent someone from using HTTP header based authentication nor does it interfere with HTTP caching mechanisms, but does enable subsequent hops that may not be using HTTP to still use the DTS in the body for a non-interactive end-to-end authentication. This is an innovation enabled by KERI. We should take advantage of it.

[SmithSamuelM]

Some problem with browser .

[SmithSamuelM]

KERI Request Authentication Mechanism KRAM

Orginally I solved this decentralized end-to-end non-interactive authorization problem as part of a proof-of-concept for a privacy preserving lost and find registry and peer-to-peer messaging service. This proof-of-concept was implemented in python in an open source Apache2 project called Indigo-BluePea which may be found here. Indigo BluePea

Interactive vs. Non-interactive Authentication Design

In general, authentication mechanisms may be grouped into two different approaches, these are: interactive and non-interactive approaches. An interactive mechanism requires a set of requests and reponses or challenge responses with challenge response replies for secure authentication. Non-interactive approaches on the other hand pose unique problems because they do not allow a challenge response reply handshake. A request is submitted that is self-authenticating without additional interaction. The main benefits of non-interactive authentication are scalabilty and path independent end-to-end verifiability. These benefits become more important in decentralized applications that employ zero-trust architectures. (by zero-trust we mean never trust always verify, this means every request is independently authenticated, there are no trusted pre-authenticated communication channels.)

For non-interactive authentication of some request for access, the most accessible core non-interactive mechanism is a non-repudiable digital signature of the request itself made with asymmetric key-pair(s). The hard problem for asymmetric digital signatures is key management. The requester must manage private keys. Indeed this problem of user cryptographic key management, at least historically, was deemed too hard a requirement which meant that only federated, token based, authentication mechanisms were acceptable. But given that users are able to manage private keys, which is a core assumption for KERI in general, then the remaining problem for non-interactive authentication using non-repudiable digital signatures is simply replay attack protection. Indeed with KERI the hardest problem of key management, that is, determining current key state given rotations is already solved.

By way of comparison, the closest authentication mechanism to what KERI enables is the FIDO2/WebAuthn standard FIDO2/WebAuthn. The major difference between FIDO2/WebAuthn and KERI is that FIDO2/WebAuthn has no built-in automated verifiable key rotation mechanism. FIDO2/WebAuthn uses of two ceremonies for authentication, that are: first a registration ceremony followed by one or more authentication ceremonies. Upon creation of a key-pair, the user engages in a registration ceremony to register that user created key pair with a host service to which the user would like access. The registration ceremony usually involves some MFA procedure that associates from the host's perspective, the entity controller of the key pair with its pair's public key. Once registered subsequent access may be authenticated through an authentication ceremony that typically involves signing the access request with the registered private key often as a replay to a challenge response with a nonce. Unfortunately, however, because FIDO2/WebAuthn has no in-stride verifiable key rotation mechanism, should a user ever need to rotate keys, that user must start over with a new registration ceremony to register a new key pair for itself. I sat in on a presentation from a BYU researcher that detailed how FIDO2's re-registration for key rotation exposes attack vulnerabilities. These are similar to how reissuing a certificate from a CA expose attack vulnerabilities in DNS/CA. Whereas with KERI rotation happens automatically with a rotation event using pre-rotated keys that is verified agains the pre-rotated keys. No re-registration is required. Thus given the requestee already has a KERI verified key state for the requestor, using FIDO2/WebAuthn to authenticate a KEL log replay request would be a downgrade.

Any access control or authorization mechanism based on KERI must still have some additional registration mechansim in order to link or associate an actual entity as the controller of a given identifier. However, in this case where we are enabling access for the purpose of replaying key event logs, it may not be necessary to link to any external entity. We merely need authenticate to the controller of the identifier regardless of the actual external entity. Thus authentication can be simply restricted to authenticating as the controller of the identifier via its current key state without requiring a separate registraion step to link to an external controlling entity. With this any implementation of KERI can build a base level private authorization policy for a given identifier using a simple authentication mechanism based only on proof of control over the authorized identifier that is signaled by signing a request or query with the current controlling key pairs of that identifier. This does not preclude an implementation from layering on additional authentication and authorization mechanisms that may include external entity associated registration and/or MFA. But the minimal simple authentication mechanism proposed here is meant to enable this base authentication and authorization or more complex MFA authentication and more sophisticated authorization layering without requiring it.

Replay Attack Protection in Non-interactive Authentication

A digital signature made with an assymmetric key pair(s) on a request provides non-repudiable authentication of the requester as the controller of that key pair(s). This assumes that the receipient of the request (requestee) can securely map the identifier of the requestor to the controlling key pair(s). With KERI derivation codes, we have a simple mechanism for attaching and resolving both the identifier of the requestor and the requestor's signature of that request to that request. Given that the requestee has the current key event log for the requestor, then the requestee may securely verify the mapping from requestor identifier to its associated current key state. Indeed we could view the publication of the key event log of a given potential requestor to a given requestee as an ersatz registration ceremony that then enables later authentication of signed request messages that include both the requestee's identifier and signature as attachments to the request. Another way is describing this approach it to say that the requestor must make an authenticatable presentation of a KEL replay request or query by attaching to the request both its identifier and signature of the request.

The problem is that an attacker may capture the signed request and then resubmit it or replay it from its own host, thereby effectively fooling the requestee into redirecting a copy of the response to the attacker's host in addition to or instead of the original requestor's host. In other words the attacker acts as an imposter. This requires that the attacker intercept the original request and then replay it from a different connection. This is called a replay attack. There are several mechanism one can employ to protect against this form of replay attack. However the practical choices for non-interactive protection are limited. In general replay attack protection imposes both some form of timeliness and some form of uniqueness to any signed request.

We are assuming that only the current keys from the current key state may be used for authentication. This requirement imposes one form of timeliness, in that any requests signed with stale keys are automatically invalid. The requestor can ensure that the requestee has its, (the requestor's) latest key state so that it is protected from replay attacks using old stale key signed requests.

The simplest and most practical non-interactive mechanism for ensuring timeliness and uniqueness is to insert a date-time stamp in the request body. This date time stamp is relative to the date time of the requestee not requestor. There are two protection mechanisms, one loose and one tight. In the loose mechanism the requestee imposes a time window with respect to its date time for any request. The time window is usually some small multiple of network latency of the connection to the requestor. An imposter must intercept and resubmit the replay attack within that window in order to successfully redirect a response to itself. This is loose protection because the requestor is not guaranteed to be able to detect the attack. The requestee may respond to multiple copies of the same signed request but from different source addresses. In addition to timeliness a tight mechanism imposes a uniqueness constraint on the request timestamps. The requestee does this by keeping a cache of all requests from the same requestor identifier (not host address). All requests in the cache must have monotonically increasing timestamps. The requestee only responds once to any request with a given time stamp and any subsequent requests must have later timestamps. This means that a successful replay attack may be detected because the only way that the attacker gets a reply response is if redirects the one and only one response to that request first to itself before possibly forwarding it on to the requestor (if at all). This redirection is detectable because either the requestee does not get the response at all if it is not forwarded or it gets it via a later redirection from some host that is not the originating requestee. Given that the requestor detects the attack it may then take appropriate measures to avoid future interception of its traffic by the attacker.

The monotonic cache even protects against a retrograde attack on the system clock of the requestee. The monotonicity requirements means that even if the system clock if retrograded to an earlier time such that an attacker could replay stale requests, the cache would have later timestamps and therefore prevent response until the system clock was restored to normal time.

The datetime stamp should have fine enough resolution that the monotonicity constraint doesn not limit the rate of requests nor cause it to run past the end of the timeliness window. Microsecond resolution is adequate for most internet connections but may not be for 40 Gbps LAN connections. An ISO-8601 timestamp with microsend resolution is a common variant. Most operating system now also support nano or atto time variants of ISO-8601 timestamps.

Authentication Request Timeliness and Caching

Generally speaking all authentication mechanisms, both interactive and not, depend on some explicit or implicit datetime stamp for timeliness. Interactive mechanisms that use tokens typically embed the datetime stamp or its hash in the token itself. This is because tokens are bearer authentication mechanisms and need to expire quickly to prevent replay. A common non-token based interactive authentication mechanism requires that the requestee send a challenge response with a nonce to the requestor. The requestor then includes the nonce in its signed challenge reply. This ensures uniqueness of the signed request (as challenge reply). But even then its still best practice to have a timeout on the authentication because an attacker that intercepts the traffic can still replay the challenge response. Even if the requestee keeps a cache of challenge responses and only responds once to any nonced signed request, there is no guarantee that a requestor got that response and therefore an attacker might capture a challenge response/reply and replay the reply some time later. To prevent this, the requestee must also impose a timeout even on nonced reply requests that invalates any stale replayed nonced requests. This approach enables the requestor to detect an attack because there is one and only one response to any request. Given a successful attack, either the requestor does not get the response or it sees that the responsehas been redirected from some other host that is not the requestee.

From a replay attack protection perspective, a nonce with a time window in an interactive authentication is functionally equivalent to a monotonic time stamp in a non-interactive authentication but the latter avoids the overhead of the interaction. Both employ a timed cache (timeliness) tied to each requestor and both employ a mechanism that ensures one and only one response is sent for any signed request (uniqueness).

This analysis just reinforces that observation that in general authentication request replay attack protection mechanisms include both timeliness and uniqueness properties.

Because generally replay attack protection mechanisms use timeliness, caching of authentication requests by the requestee or some intermediate load balancer is an anti-pattern. This applies to both interactive and non-interactive authentication requests. Thus, in general request caching of authentication requests must be disabled. Responses, however, may still be cached.

In a zero-trust non-interactive environment where every request is self-contained and self authenticating with an embedded date time stamp and attached identifier and signature couple, request caching would be problematic. This may be viewed as a trade-off where the scalability advantages of non-interactivity and the security advantages of zero-trust exceed the scalability disadvantages of not being able to cache requests.

[SmithSamuelM]

A practical example might help.

1) direct mode KELs confidentiality protection.

A given KEL server has a policy of only sharing a given KEL replay with a client that have both established a secure encrypted channel and have authenticated by signing the request with the current keys for that KEL. Ie is Authentications as the keys's identifier controller. The secure channel could be made with DID-COMM or TLS. The point of the channel is not to authenticate access to the KEL but to establish a confidential communications path. For simplicity lets assume its TLS with server side certificate only. The server knows it has a confidential TLS channel but doesn't know with whom. Assume that the server merely required that the client sign each request with the current keys for the requested identifier's KEL thereby proving that the request came originally from the controller of that identifier. The Server then replays that KEL to the client. No one else may see the log because it went over an encrypted channel.

Suppose as well that an attacker has gained access to the client's computer, and a copy of the signed request is left lying around in a log on the client's compute. Now the attacker can open its own TLS connection to the Server and request the same KEL by replaying the request it just found lying around. This would defeat the original intent to preserve the confidentiality of the KEL. However, if the request included a datetime stamp and the server dropped requests whose datetime stamp were outside an narrow time window with respect to the server's current time then the attacker would be foiled. Merely finding an old copy of a request lying around does not enable it to gain access to the KEL. A datetime with a window is sufficient.

Having uniqueness just adds additional protection for corner cases where the attacker can intercept traffic or is able to see old requests in real time.

2) indirect mode KELS DDOS proection:

Suppose that the KELs are all public so the Server doesn't care who sees them but doesn't want to be burdened with responding to a myriad of requests from any number of clients thereby effectively DDosing it. Suppose the Server has a list of preferred clients that it will replay to and no others. In this case it may not require an encrypted channel for a given client connection but it will only replay to clients that authenticate as controlling an identifier from its preferred list. In this case some attacker monitoring internet traffic could observe a client request for a KEL and then the attacker could stand up any number of hosts than send duplicates of any request to the Server. Thereby overloading the server by inducing huge number of responses. If however each request required a monotonic time stamp thereby guaranteeing uniqueness, then the attacker could not replay any of the observed requests because they are one time only requests. So the server is protected from DDOS.

The attacker would have to actually intercept the original requests and resubmit them from its own host. In this case it doesn't DDOS the server but DDOSs the client whose requests it intercepted. But this is detectable to the client who gets no responses from the Server misses too many response. The client can then send new requests but from a different network perspective to avoid the intercept.

[stevetodd]

Probably need to split this issue into multiple since there are multiple topics clobbering each other.

[SmithSamuelM]

@stevetodd Its all part of the same proposal for what constitutes a replay request. I think there is already broad agreement on the core of the proposal. I see one concrete actionable suggestion from you on the database first seen query and one suggestion that we use Unix epoch time. The first I have asked for feedback on above. And the latter is in IMHO not a viable suggestion. Your comment about HTTP caching is also non actionable and non applicable. Other than the feedback on the first seen query, I think we are good to go.

[stevetodd]

First Seen Ordering

I reiterate my recommendation that we should just use a opaque token so that we don't limit implementations. This is commonly done in APIs that have large datasets. Whether you do a fn, dts or whatever, you're are still going to have to present to the node something that it had previously provided to you. The token could be a node-local ordering integer or a date time stamp, but I would recommend it be opaque. I would also recommend that it be encoded or obfuscated otherwise people will depend on it always being an integer or date (see also: Procotol Ossification).

Using an ordinal has limitations in that it requires coordination among multiple processes processing events, which may or may not be colocated on the same host. A date time stamp also has issues when used among multiple hosts since you really can't guarantee that their clocks will be synchronized to better than millisecond resolution. Even within a single host, when doing greater than millisecond precision you really can only get monotonicity but not accuracy.

The question is then, how much accuracy do we need in first seen ordering? If it is absolute, we limit the performance of a node to the performance of single threaded writes. If we can get by with these all arrived within the same millisecond and provide the first seen ordering as basically "these all arrived in a narrow similar time frame", we allow much better scalability. This latter approach does conflict with the rule that first seen event wins, though if we are in a situation where milliseconds matter, things are going to look highly suspicious anyways. Since we are receiving these across the network where packets can be reordered and delayed 10s of milliseconds, nodes are going to have to take this variability into account when validating events for an identfier.

Date Time Format

Specifying a 64-bit unsigned integer is pretty trivial to both specify and implement and is widely used among all programming languages. We can also easily do 128-bit integers if you're concerned. Heck, we've already got a specification for arbitrarily large integers we use already for the sequence number. It's trivial to convert whatever count of time units into something that is useful in whatever language. It's also future proof by just selecting whatever bit length and precision you want. Everyone has dealt with this type timestamp so the claims of non-standardness are especially specious when considering the proposed ISO-8601 encoding.

HTTP Caching

With regards to caching, I was speaking toward these proposed paths (fixed incorrect slashes):

GET /logs/EABDELSEKTH?after={datetime}&limit=1
GET /logs/EABDELSEKTH/%272020-08-22T17%3A50%3A09.988921%2B00%3A00%27
GET /logs/EABDELSEKTH?before={datetime}
GET /logs/EABDELSEKTH?after=%272020-08-22T17%3A50%3A09.988921%2B00%3A00%27

HTTP caching takes into account the full URL excluding the fragment (text including and after the #) and its headers (but not necessarily all headers). If the datetime appears in the path, query string, or some of the headers, it will affect whether it is a cache hit or miss. When fronting this service with a caching proxy like CloudFlare or others, only exactly matching URL/header combinations will use the cache. If every client is sending different timestamps, then none of the responses will get cached. It should be noted that GETs do not allow request bodies and it doesn't make sense to cache other request methods except HEAD since they are "unsafe".

Ideally, the server would be providing some sort of tag representing a specific point in its log and returning that to clients, which the clients would use in the next request. It's true that each client may be at a different point in its replay, but heavily loaded servers could improve their performance by releasing events only periodically (for example, by grouping events in 10 second increments) and using a common tag for each increment. Of course, a websocket could be used but that raises backpressure issues when clients temporarily may be unable to keep up.

[SmithSamuelM]

Using an ordinal has limitations in that it requires coordination among multiple processes processing events, which may or may not be colocated on the same host. A date time stamp also has issues when used among multiple hosts since you really can't guarantee that their clocks will be synchronized to better than millisecond resolution. Even within a single host, when doing greater than millisecond precision you really can only get monotonicity but not accuracy.

This comment shows a fundamental lack of understanding of what an append only first seen event log means. That you are citing general principles about coordination that have nothing to do with what first seen means or what must happen for first seen ordering to be immutable causes me real despair. It seems like you are commenting purely for the sake of just wasting the communities time rather than actually making a positive contribution. You're continued comments show little understanding at a fundamental level what first seen ordering means for KERI. Since I know you better than that I can only conclude that this is you not engaging sufficiently to make positive contributions. Thus continued discussion feels like a waste of time.

[SmithSamuelM]

With regard the proposal above to provide replay attack protection using monotonic date times it might be interesting to note that non-interactive Replay attack protection using monotonic counters is a well known technique in security. Indeed it is the most common non-interactive technique in wide usage. Using monotonic date times is a well known variant. Some references are included below if some one wants to dig in further.

The proposed approach above is an adaptation of that technique that takes advantage of KERI's unique properties. I have written this up in a whitepaper and decided to call it KRAM for Keri Request Authentication Mechanism instead of K-SQAM

Here are some references:

https://en.wikipedia.org/wiki/Replay_attack https://www.cisco.com/c/en/us/support/docs/ip/internet-key-exchange-ike/116858-problem-replay-00.html https://software.intel.com/content/www/us/en/develop/documentation/dal-developer-guide/top/features/features-monotonic-counters.html https://people.csail.mit.edu/devadas/pubs/ccs-stc07.pdf https://patents.google.com/patent/US20030067921A1/en https://eprint.iacr.org/2017/048.pdf

[chunningham]

While we all agree that datetime stamps in events are not appropriate as there is no way to verify the actual creation time, I agree with @SmithSamuelM that as a replay-prevention mechanism they provide a great non-interactive method without relying on more esoteric/platform specific methods like ledger blocktime (which would bind the protocol to specific ledgers). The only properties required in this case are a commitment to non-repetition/"recency" (clients should not be able to use the same nonce twice) and a monotonic ordering (such that clients and servers do not need to store a history of used nonces), both of which datetime stamps can provide. I'd propose that we discuss this again at the next WG call.