ID standardisation for all projects and domains

[CMCDragonkai]

Specification

ID generation is used in many places in PK. But the IDs must have different properties depending on the usecase.

The properties we care about are:

• Decentralised vs Centralised - the appending of a "machine ID" makes the IDs decentralised and prevents collisions and is coordination-free
• k-Sortable vs Random - k-sortable IDs are sortable lexically which means it can be used in a ordered key-value database as an index, while random identifiers are intended to have no-order, and is often important to ensure unguessability, note that sortable IDs can also have a random component but there's a tradeoff in how random vs how sortable when there's limited amount of space
• Limited byte size representation - UUIDs use 128 bits, it appears most IDs are 128 bits or 16 bytes, this means all properties have to be encoded within 128 bits, some properties may not fit within that 128 bits, for example decentralised ids may need to use the machine id which itself may be larger than 128 bits, and slicing a smaller amount would actually increase the likelihood of collision, in such cases compound ID formats will be required
• Buffer Representation and Base Encoding - IDs should have a original binary form, and can then be encoded in various formats for display, buffer representation is superior as we can make use of the full bitspace, and it will be shorter compared to the base encoded for textual display, we could support different textual displays for different reasons, but the UUID display is a nice way of displaying the IDs which can help memorisation
• Strict Monotonicity - for sortable IDs, it's essential that IDs generated are monotonic to prevent collisions or ambiguity, these have to be sortable across clock resets, and process restarts of the program

IDs compared to petnames give us the secure and decentralized properties, but not human-meaningful. Human meaningful names can be generated by mapping to a mnemonic. But that is outside the scope of this for now.

There are roughly 4 usecases in PK:

• Decentralised Sortable IDs - claim ID in sigchain should be decentralized, but also sortable, they are public information so they point to a claim at a point in time
• Centralised Sortable IDs - notification ID in PK notifications, these are IDs local to the PK, but should also be sortable, they are public information so they don't have to be cryptographically random
• Decentralised Random IDs - vault ID, these should be random, as they should not leak the order of creation information
• Centralised Random IDs - permission ID, these should be random because order doesn't matter, but leakage isn't really an issue either

To resolve decentralised vs centralised, rather than assuming that the machine id should be embedded in the identifier, we would instead always expect the machine id to be appended as as suffix. Appending is superior to prepending to ensure that sorting is still done.

We can default to using 128 bit sizes, but allow the user to specify higher or smaller sizes.

We can use a default CSPRNG, but also allow users to submit a custom CSPRNG for random number generation.

To ensure monotonicity, we want to allow the external system to save a clock state and give it to us, so we can ensure that ids are always monotonic.

We may expect that our IDs to be later encoded with multibase, we should allow this library to be composed with multibase later.

Note that ID generation is different when it's meant to be backed by a public key. That is out side of the scope of this library. These IDs are not public keys!

There are places in PK where we use https://github.com/substack/lexicographic-integer, in those cases we may keep using that instead of this library. However those are when it is truly that we are trying to store a number like the inode indexes in EFS, in the sigchain, what we really want is IdSortable

Additional context

• https://gitlab.com/MatrixAI/Engineering/Polykey/js-polykey/-/merge_requests/205#note_625776187 - Vaults Refactoring MR
• https://www.npmjs.com/package/flakeid
• Use this for FlakeIds vweevers/monotonic-lexicographic-timestamp#3
• https://github.com/ulid/javascript
• https://github.com/aarondcohen/id128
• https://github.com/perry-mitchell/ulidx
• https://www.ietf.org/id/draft-peabody-dispatch-new-uuid-format-01.html - ideas for v6, v7 and v8 versions of uuid
• https://github.com/uuid6/uuid6-ietf-draft
• Support new IETF UUID formats uuidjs/uuid#580
• https://news.ycombinator.com/item?id=28088213

Tasks

1. - Play around with uuid library
2. - Review uuidv7 and uuidv8 spec
3. - Review https://github.com/kripod/uuidv7 implementation
4. - Integrate multibase
5. - Transform uuidv7 to uuidv8 constructor
6. - Use uuiv8 as a skeleton to build our multi-property ids needed by PK
7. - Integrate performance.now() and performance.timeOrigin APIs (make it browser possible by testing with a dynamic import?)
8. - Consider both synchronous and asynchronous API due to asynchronous crypto CSPRNG
9. - Implement IdRandom
10. - Implement IdDeterministic
11. - Implement IdSortable
12. - Add tests for lexical order for both binary and encoded forms
13. [ ] - Port tests over from https://github.com/uuid6/prototypes/tree/main/python for IdSortable - created our own tests
14. - Add in multibase encoding utilities to allow easy way of encoding and decoding the ids using any base
15. [ ] - Test that it is actually returning ArrayBuffer - can't do this because it doesn't work in jest

[CMCDragonkai]

The above spec doesn't concern itself with deterministic IDs. That is IDs generated by hashing some value. The UUIDv3 and UUIDv5 specs are for deterministic IDs.

Incorporating deterministic IDs can be useful for dealing with MatrixAI/js-db#1. Because we are exposing values to be keys, and they are not encrypted at rest, this means it can be a good idea to hash those values and ensure we have a deterministic ID. This would mean that we get a similar ID representation and base encoding even if the source of the ID is deterministic data.

Note that it also supports the usecase of namespaces. Namespaces sound like the machine ID that we have, and one would imagine the generation of a namespaced random identifier. Note that the UUID specs state that they use MD5 or SHA1. It sounds like UUIDv5 would override any usage of UUIDv3. See this for more info: https://stackoverflow.com/a/28776880/582917

According to https://www.sohamkamani.com/uuid-versions-explained/ it would make sense that UUIDv5 is taken over.

And again, the main reason not to use UUIDv1 is because we want the higher amounts of entropy, which does mean our IDs are alot bigger. Or our compound IDs are used instead.

[CMCDragonkai]

We are probably not going to follow the UUID versions strictly but instead create our IDs for our 4 separate usecases above and additional usecases as we see fit.

One of the things that would be nice is if we can configure whatever ID generated to be a composition of different properties. But somethings will be mutually exclusive.

[CMCDragonkai]

The uuid library supports writing to a given buffer. However the buffer must be a typed array or a Node buffer, not an ArrayBuffer. This makes sense, since ArrayBuffer cannot be written to directly, you must use a typed array. In this case, it's always a Uint8Array which will be more portable than using Node buffers.

[CMCDragonkai]

Instead of expecting a CSPRNG, you can ask the user to supply a random generator:

import * as uuid from 'uuid';

uuid.v4({
  // 16 random bytes (it's actually 16 random numbers)
  // could change to 16 random bytes since we want to be buffer/binary native
  // and that's how most CSPRNGs would work
  rng: () => [  0x10, ... ]
});

[CMCDragonkai]

The API of uuid in some situations makes use of "array of numbers" as a representation of bytes. I think this seems like a vestigial feature from the olden days of lacking proper binary types. Now with typed arrays, we shouldn't need to support this representation. Since we're going to be using this with LevelDB in js-db, and that is always buffers, we can focus entirely on buffer types instead of array of numbers.

The text representation of uuids have dashes, this seems intended to help human readability.

• https://stackoverflow.com/a/3557678/582917

So it seems that even this strict adherence is not necessary, this shows equivalent base encodings.

Ascii:   3F2504E0-4F89-11D3-9A0C-0305E82C3301
Base64:  7QDBkvCA1+B9K/U0vrQx1A
Ascii85: 5:$Hj:Pf\4RLB9%kU\Lj

Seems like we would also be able to support multibase representations in this library too. https://github.com/multiformats/js-multiformats

Our preference I believe is base58btc, which means a bit longer, but easier to double click and copy.

[CMCDragonkai]

Here's an example of using multibase:

const idBuf = new Uint8Array(16);
uuid.v5(
  'abc',
  'c1b00cc0-25a3-11ec-be9b-033334f5bcba',
  idBuf
);
const idEnc = base58btc.encode(idBuf);
const idEnc2 = base64.encode(idBuf);
const ds = Object.values(bases).map((c) => c.decoder).reduce(
  // @ts-ignore
  (d1, d2) => d1.or(d2)
);
const idBuf_ = ds.decode(idEnc);

const b1 = Buffer.from(idBuf);
const b2 = Buffer.from(idBuf_);

console.log(b1.equals(b2));

console.log(idEnc);
console.log(idEnc2);

Note you can see here that we are using UUIDv5 to write a 16 byte UUID. This is then encoded as base58btc using multibase. Then to decode it, we combine all the base codecs together and reduce it into a combined decoder. This has a type error due to: multiformats/js-multiformats#121 but it works fine.

If the base encoded string is not recognised, the exception is:

throw Error(`Unable to decode multibase string ${JSON.stringify(text)}, ${this.name} decoder only supports inputs prefixed with ${this.prefix}`)

Or:

throw Error('Can only multibase decode strings'

So any exception thrown here can be considered a parse error.

The multibase encoded string looks like:

zQMqkjqqpU32Ke7GWFCkTcK

Which has a much more constrained alphabet compared to base64, and we always have the z prefix in front to indicate base58btc as opposed to other base encodings like base64 which would use m.

[CMCDragonkai]

I wonder whether to integrate multibase directly here in ID or leave it out for user to integrate outside in case they are likely to use it elsewhere. This would then ensure that this library focuses on binary representations and leaves the string encoding to the user.

[CMCDragonkai]

One of the issues with using a CSPRNG, is that acquiring data may be an asynchronous operation. This would mean that the ID generation would be asynchronous as well.

Note that sometimes there are synchronous or asynchronous APIs, both are possible: https://nodejs.org/api/crypto.html#crypto_crypto_randombytes_size_callback

However webcrypto API specifies synchronous CSPRNG.

crypto.getRandomValues(typedArray)
crypto.randomUUID()

And our usage of node-forge would mean that we have synchronous and asynchronous forms:

async function getRandomBytes(size: number): Promise<Buffer> {
  return Buffer.from(await random.getBytes(size), 'binary');
}

function getRandomBytesSync(size: number): Buffer {
  return Buffer.from(random.getBytesSync(size), 'binary');
}

So our random IDs should then be both synchronous and asynchronous. That is we may return the raw data or return a promise on the data.

[CMCDragonkai]

Note that CSPRNG and PRNG are all random number generators. CSPRNGs are better than PRNGs. But this is all pluggable, and for PK's purposes we are going to always package with a CSPRNG.

[CMCDragonkai]

I've been investigating the uuidv7 functionality. It is claimed to be lexicographic order. However I'm not sure if this is the case when used as a bytes and without encoding.

When I used lexicographic-integer https://github.com/substack/lexicographic-integer, their byte representation was also in lexicographic order, so I didn't have to hex encode to get the lexicographic order and leveldb supported buffer keys.

// lexi.pack(number) => Array<number> - this converts a number into an array of number byte format
// Buffer.from(Array<number>) => Buffer -> this converts the array of numbers into a binary buffer

Buffer.from(lexi.pack(100))

// the result is usable as a leveldb key

This was proven by several tests that I did in js-db. So I'm going to port over uuidv7 and test if its byte representation is still lexically ordered.

[CMCDragonkai]

Ok I've reviewed the UUIDv7 and UUIDv8 specs. It looks like the UUIDv8 spec would the most suitable to handle all of our usecases, and it would allow us to flexibly define and change the id structure.

The structure is:

     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                          timestamp_32                         |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |           timestamp_48        |  ver  |      time_or_seq      |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |var|  seq_or_node  |          node                             |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                              node                             |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

And it is possible to potentially truncate the public key id to fit entirely in the uuidv8.

What ids are actually are in a shared context? In most cases you're going to always look up the node id before you look up the individual ids like vault id. Unless vault id were to be preserved across keynodes. It doesn't seem like you need to preserve it entirely if the vault remotes are used.

While vault ids may not need to be "shared" anymore.

I reckon claim ids may still be if we want to be able to refer to them.

Anyway we can make this optional to fill in the node part of the UUID or they are just CSPRNG filled random data.