Subject: Re: UUID version 6 proposal, initial feedback

From: Brad Peabody <[email-masked]>
Date: Fri, 31 Jan 2020 12:52:18 -0800

I've given this UUID idea a lot more thought and had more discussion on 
it and I wanted to get feedback on these latest ideas.  To summarize:

- Instead of making one single way to generate UUIDs, it should be a set 
of options which indicate a UUID with the features needed.  Properties 
like case-insensitivity, how much random data is included, time ordering 
with a timestamp, and others, can be highly application-specific.   
Trying to specify one set that works for everyone is unrealistic and 
unnecessary.

- There appear to be three main aspects to generating a UUID: timestamp, 
random data and the text encoding of it.  Most of the options are 
centered around these three aspects.  Examples: timestamps can be in 
second-precise ("ts"), millisecond-precise ("tms") and 
nanosecond-precise ("tns") forms.  Random data can be in various lengths 
"r64" for 8 bytes of random data might be okay for many applications, 
some might want "r128" for the additional uniqueness, others might only 
want "r32" where occasional duplication is not dire (example: a unique 
ID for an error message used for debugging) and it's better to have a 
shorter ID.  Various encoding forms like "b32", "b64" (and some alphabet 
variations on this) and "hex" can be used. These are "format options" 
and together they make a "format spec"

- There's also an option for some static bytes to be appended - for 
example a machine ID in a cluster. Useful for fully guaranteeing 
uniqueness in cases where there's a controlled environment.

- In practical terms and as an example, a format spec of "tns r64 b32" 
would result in a nanosecond-precise timestamp (64 bits) followed by 64 
bits of random data, encoded in base32. Alternatively, if you want to 
save on text length a bit and case-insensitivity is not important for 
your application, use "tns r64 b64" instead.

- UUIDs in text form are parseable if one knows the format spec used.  
(This addresses the case of some applications needing to extract the 
timestamp, without over complicating the UUID text format by trying to 
somehow include the format spec in it.) Otherwise it can also of course 
be used as an opaque string.

- The special format option "rfc4122" results in a timestamp in the 
format of that RFC, the number 6 in the version bit field, and the lower 
64 bits filled with random data.   This addresses the backward 
compatibility concern while allowing newer applications to be more 
flexible (using other options instead).

This is the document I've been putting together, it's still very rough, 
but has a fair amount of detail: 
https://docs.google.com/document/d/1bctTr14CrxzjHUIRAkT8jB46Jomr9aB2JQ9hDCh3cJg

Any feedback on this would greatly appreciated.  Overall my plan is to 
complete the document above and then write an implementation in Go and 
in C (and maybe it's time to learn Rust, lol) to make sure it works in 
practice.  And then convert the document into an IETF draft and try for 
moving it toward becoming an RFC.

Best, Brad

On 7/4/18 1:44 AM, Brad Peabody wrote:
> Thanks Martin,
>
> Those are really good points and I agree.
>
> I’m a bit concerned about moving entirely away from the existing 
> format, as I think there are some useful properties - particularly the 
> ability to extract the time stamp. Also by producing newer versions of 
> UUIDs that are the same size and layout a lot of existing software 
> will continue to work (for example, Cassandra understands UUIDs and 
> works with my prototype “version 6” UUIDs without any modification).
>
> But the points you bring up are quite relevant.  I’m not sure how to 
> address the clock skew leakage that might occur, but definitely the 
> counters and MAC address can go the way of the buffalo. Simply reading 
> from /dev/urandom, et al makes so much more sense these days.
>
> I think there is also real potential in the idea of making them 
> variable length.  If you need compatibility with existing UUID schemes 
> you can use the 128 bit length, but you can also go longer if you 
> require more guarantee of uniqueness or un-guess-ability.
>
> The only other thing that has me pondering on this is how important is 
> the property of being able to tell “is this a valid UUID, and if so 
> what type”.  If we don’t care about this, then it might make sense to 
> have two additional formats - a base64 which is as compact as 
> reasonably possible while still being ASCII, and a base32 which is 
> case-insensitive - they both have merit depending on the use case. 
>  But then add the fact that it’s variable length and it becomes 
> impossible to distinguish the format reliably (i.e you might read the 
> base32 value as base64 by accident).  I can think of some ways to work 
> around this in the format using specific characters in one and not the 
> other, but it starts to feel really hacky.  I’m just not sure if this 
> is actually important for real-world applications.  Many applications 
> just use the UUID opaquely, but not all.  And again, extracting the 
> timestamp can be useful - but then is it reasonable to also say “if 
> you want the time, you’ll need to know the format, you won’t be able 
> to automatically tell the difference between a base64 and base32 
> UUID”.  One possible simple solution: put a period after the first 128 
> bits
>
> Still not sure on this, input welcome.
>
> All that said, it seems to me we’re headed for a spec that has the 
> following properties:
>
> - Encodes timestamp
> - Sorts correctly as raw bytes
> - Has the version field in the same place for compatibility
> - Supports the existing 128-bit hex representation 
> (NNNNNNNN-NNNN-NNNN-NNNN-NNNNNNNNNNNN) for compatibility but also...
> - Specifies alternative (url-safe) base64 encoding for compact string 
> representation while still sorting correctly; and also a base32 
> encoding where case-insensitivity is required
> - Instead of existing dangerous bits like counter and MAC address, use 
> secure random data available from OS
> - Can be arbitrarily longer as needed, filled with additional random data.
>
> Does that seem about right?
>
> Also, when things settle in terms of the high level requirements, at 
> what point should I do a rough draft of the spec on this?  (And is 
> there some sort of outline I would follow?)
>
> -Brad
>
>
>> On Jul 3, 2018, at 7:11 PM, Martin Thomson <[email-masked]> 
>> wrote:
>>
>> Nice presentation.
>>
>> I've always been skeptical of the value of UUIDs.  It's very easy to
>> make a unique string.  Formatting it in a particular way, however,
>> serves no real purpose and it might not be necessary for your use
>> case.
>>
>> UUIDs (aside from v4) also have some nasty properties.  For instance,
>> revealing a MAC address is now considered problematic.  As is exposing
>> the output of a clock, which has been used in interesting ways to
>> undermine privacy (clock skew can be used for de-anonymisation, even
>> for determining CPU load).  Counters and timers also allow an observer
>> to correlate the creation of different identifiers.
>>
>> Why not make a string with the properties you desire?  You might need
>> more than 120 bits to achieve all that, but that's just another reason
>> not to use UUIDs.  A library that provided these functions (maybe
>> while addressing the above concerns), would be a valuable addition.
>> On Wed, Jul 4, 2018 at 10:42 AM Brad Peabody <[email-masked]> 
>> wrote:
>>>
>>> I would like to get some initial feedback, and suggested next steps, 
>>> on the idea of making an RFC that covers a version 6 for UUIDs.  It 
>>> would have an embedded timestamp and sorting by its raw bytes 
>>> results in a sequence equivalent to sorting by time.  This is not 
>>> addressed by existing UUID types.  (The closest one is version 1, 
>>> but due to the byte encoding it does not sort correctly.)
>>>
>>> There is also seems to be some ambiguity in the existing RFC on when 
>>> to increment the counter field which I think can be clarified.
>>>
>>> I did a prototype implementation and basic write-up on the details 
>>> here: https://bradleypeabody.github.io/uuidv6/
>>>
>>> I’m also thinking of covering the base64 encoding form which retains 
>>> the sorting properties but makes it human readable and is 
>>> significantly shorter than the long hex encoded form.
>>>
>>> Having these things is very useful when considering UUIDs as 
>>> database primary keys, which is becoming more and more common in 
>>> distributed systems; and indeed this is the main motivation.
>>>
>>> Any help or advice on moving forward with this would be appreciated.
>>>
>>> - Brad
>>>
>

---

From: "Salz, Rich" <[email-masked]>
Date: Fri, 31 Jan 2020 21:45:07 +0000

I don’t understand the purpose of all that mechanism.  UUID’s are supposed to be opaque identifiers; if you intend folks to look inside them, then you should not be using UUID, you should be using something else where the insides are on the outside, as it were.

UUID’s are very old, they were first part of Apollo’s Network Computing Architecture in the 1980’s.  If we were recreating them today, we’d just use a cryptographic nonce.  I suggest that’s what you do as well.

---

From: Brad Peabody <[email-masked]>
Date: Fri, 31 Jan 2020 14:06:58 -0800

I get where you're coming coming.  The issue is there are common use 
cases where just using cryptographic nonce does not work well.

Random UUIDs as primary keys in databases have bad write amplification 
properties.  (example: 
https://github.com/uuidjs/uuid/issues/303#issuecomment-575992079) A 
timestamp provides locality in database indexes as well as a useful 
natural order in the database.

The text format of a UUID is generally not the best way to store it in 
memory.  So after an identifier (timestamp or not) has been created 
there is the issue of how you show it to humans vs its binary form, and 
there are tradeoffs with different formats (size, case-insensitivity, 
backward compatibility).

What I laid out is essentially a collection of options that seem to come 
up time and again dealing with unique identifiers.  I think there is 
benefit in standardizing it.  The list of open source projects that each 
have their own way of creating unique identifiers is quite long and the 
wheel is reinvented often. (Some examples: 
https://github.com/segmentio/ksuid https://github.com/rs/xid 
https://github.com/kjk/betterguid https://github.com/sony/sonyflake 
https://github.com/oklog/ulid https://github.com/chilts/sid )

I agree this is not a terribly complex problem and some applications can 
just read from /dev/urandom and be done with it. But I also believe the 
above concerns are real and affect a lot of real-world applications.

On 1/31/20 1:45 PM, Salz, Rich wrote:
>
> I don’t understand the purpose of all that mechanism.  UUID’s are 
> supposed to be opaque identifiers; if you intend folks to look inside 
> them, then you should not be using UUID, you should be using something 
> else where the insides are on the outside, as it were.
>
> UUID’s are very old, they were first part of Apollo’s Network 
> Computing Architecture in the 1980’s.  If we were recreating them 
> today, we’d just use a cryptographic nonce.  I suggest that’s what you 
> do as well.
>

---

From: "Salz, Rich" <[email-masked]>
Date: Sat, 1 Feb 2020 02:41:12 +0000

*   What I laid out is essentially a collection of options that seem to come up time and again dealing with unique identifiers.  I think there is benefit in standardizing it.

Considerations in designing unique identifiers sounds like it could be a worthwhile RFC. I just don’t think they’re UUID’s.

> some applications can just read from /dev/urandom and be done with it.

That is fraught with danger, not going to get into it on this general public list.

---

From: Keith Moore <[email-masked]>
Date: Fri, 31 Jan 2020 22:03:18 -0500

On 1/31/20 9:41 PM, Salz, Rich wrote:

>   * What I laid out is essentially a collection of options that seem
>     to come up time and again dealing with unique identifiers.  I
>     think there is benefit in standardizing it.
>
> Considerations in designing unique identifiers sounds like it could be 
> a worthwhile RFC. I just don’t think they’re UUID’s.
>
I concur.   I think it would be a better proposal if they were called 
something else.

Keith

---

From: "Theodore Y. Ts'o" <[email-masked]>
Date: Sat, 1 Feb 2020 01:07:33 -0500

On Fri, Jan 31, 2020 at 02:06:58PM -0800, Brad Peabody wrote:
> I get where you're coming coming.  The issue is there are common use cases
> where just using cryptographic nonce does not work well.
> 
> timestamp provides locality in database indexes as well as a useful natural
> order in the database.

As as you point at in [1], it's trivial to covert between your
"version 6" and the V1 UUID --- it's just a matter of swapping the
bytes.

[1] http://gh.peabody.io/uuidv6/

As it happens, I'm aware of at least one large enterprise application
which swaps the bytes before storing a UUID into a database, because
it uses the UUID's for keys in its system.  In fact, it's *because* of
this application that the Linux implementation of libuuid has an
optional-to-run uuidd helper daemon:

    The uuidd daemon is used by the UUID library to generate
    universally unique identifiers (UUIDs), especially time- based
    UUIDs, in a secure and guaranteed-unique fashion, even in the face
    of large numbers of threads running on different CPUs trying to
    grab UUIDs.

This was implemented in 2007 because this particular large enterprise
application (used in many Fortune 100 companies) needs a *huge* number
of UUID when doing its initial database setup.

But the point is they did this as a storage issue --- it's how they
fold, spindle, and mutilate the UUID before they store it into the
database and use it as a key.  There is no need to define a new UUID
version for this hack, since it's so easy to transform a v1 UUID into
a more database-friendly format and back again.  You can just treat it
as an internal implementation detail of how the UUID is stored and
lookups performed in the database.

> above concerns are real and affect a lot of real-world applications.

/dev/urandom is a Linux specific thing.  The better choice is libuuid.

The libuuid library is installed on all Linux systems, so they can
just link with -luuid and use uuid_generate().  It's also installed on
MacOS systems (I changed the license to make it more accepted for
MacOS) and since it is required by GNOME, it's generally available on
all of the *BSD ports.  So for most applications, the best way to go
is to use uuid_generate() and link with -luuid.  That's going to be
more portable and more secure.

						- Ted