Re: UUID version 6 proposal, initial feedback

[Brad Peabody <[e-mail]>]

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 <[e-mail]> 
>> 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 <[e-mail]> 
>> 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
>>>
>