Subject: Re: UUID version 6 proposal, initial feedback

From: Brad Peabody <[email-masked]>
Date: Sat, 1 Feb 2020 11:00:24 -0800

>>> 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.

Cool - I will come up with some ideas for different names and send those 
around soon.

> 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. http://gh.peabody.io/uuidv6/
> /dev/urandom is a Linux specific thing.  The better choice is libuuid.

To clarify - the information at http://gh.peabody.io/uuidv6/ is out of 
date, and the new proposal (see 
https://docs.google.com/document/d/1bctTr14CrxzjHUIRAkT8jB46Jomr9aB2JQ9hDCh3cJg 
) includes things like variable amounts of random data and alternate 
text encodings - stuff that will almost certainly never end up in 
libuuid.  The issue being that many applications need something like a 
UUID but can't use an actual UUID for one reason or another (e.g. 
sorting properties, insufficient unguessability, too long, etc.); thus 
the new proposal.

I think it's pretty clear all around though that calling this new thing 
a UUID is just confusing, so yeah I'll think of some other name ideas.

---

From: Keith Moore <[email-masked]>
Date: Sat, 1 Feb 2020 14:49:21 -0500

On 2/1/20 2:00 PM, Brad Peabody wrote:

> )

Another recommendation: publish your proposal as an Internet-Draft, 
rather than expecting people to visit a proprietary site that is known 
to be a serious privacy threat.

Keith

---

From: "Theodore Y. Ts'o" <[email-masked]>
Date: Sat, 1 Feb 2020 16:28:59 -0500

On Sat, Feb 01, 2020 at 11:00:24AM -0800, Brad Peabody wrote:
> The issue being that many applications need something like a UUID but can't use
> an actual UUID for one reason or another (e.g. sorting properties,
> insufficient unguessability, too long, etc.); thus the new proposal.

Again, I'd urge you to consider that you should build on *top* of the
standard UUID spec, since there are already implementations that will
do the right thing as far as time-based and random-based UUID's (the
latter will provide all the unguessability you need) and then just
create a library which *transforms* the UUID into a convenient
encoding form that makes it be convenient for key-indexing, or a more
compact text encoding, etc.

There are already very good implementations for UUID generation, and
if you create something which re-invents the wheel at a spec level, it
will cause people to reinvent the wheel (possibly badly) at the
implementation level.

Cheers,

						- Ted

---

From: Brad Peabody <[email-masked]>
Date: Sat, 1 Feb 2020 13:29:06 -0800

Fair point, will do.

> 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.

Ted, I'll spend some more time looking through the libuuid source code 
(nice work, btw).

I do need to give more thought to the uniqueness property.  One 
observation is that uniqueness guarantees can be somewhat 
application-specific, and specific cases can significantly reduce the 
complexity of implementation.  Examples: Applications deployed on a 
cluster where each machine already has a unique number can simply 
include that number to ensure uniqueness.  Applications only concerned 
about uniqueness in a single process can easily do this using the clock 
and a counter.

Making identifiers globally unique in a distributed fashion with high 
certainty (and still being reasonably short) is a harder problem to 
solve, but again only certain applications actually require this.  But 
some will, so it will need to be accommodated. I've read various 
concerns about using the network interface MAC address and how leaking 
this information can be bad.  My thought is that for many applications 
it may be workable to have an ID with a timestamp and then enough random 
data coming from a CSPRNG that the probability of collision is simply 
low enough to be workable.  I need to do the math on what the collision 
probability is for a nanosecond-precise timestamp followed by 64 bits of 
random data (and for larger amounts of random data also).  A lot of 
engineering already goes into making cryptographically strong random 
numbers available on modern computers.  I could be wrong, but it seems 
to me that simply knowing the collision probability for a given id 
configuration (time and random data bit lengths) one can just use one 
long enough to push the collision probability down below whatever one 
considers acceptable.  E.g. the probability of encountering a duplicate 
MAC address in the wild, or an implementation bug causing a duplicate. 
There is no true absolute guarantee of uniqueness, so mind as well just 
look at the numbers and accept the risk knowingly based on the 
probability. (I'm thinking this probability information could be given 
in the proposal, so it's clear like "use this form of ID if you XYZ 
probability of collision", listed out for each one, etc.) Again, am 
definitely willing to be wrong here, but that's my logic on it. Thoughts?

---

From: "Theodore Y. Ts'o" <[email-masked]>
Date: Sat, 1 Feb 2020 17:03:48 -0500

On Sat, Feb 01, 2020 at 01:29:06PM -0800, Brad Peabody wrote:
> I do need to give more thought to the uniqueness property.  One observation
> is that uniqueness guarantees can be somewhat application-specific, and
> specific cases can significantly reduce the complexity of implementation. 
> Examples: Applications deployed on a cluster where each machine already has
> a unique number can simply include that number to ensure uniqueness. 
> Applications only concerned about uniqueness in a single process can easily
> do this using the clock and a counter.

For very specialized use cases (e.g., where 16 binary bytes is too
long), I'm not sure it makes sense to create a fully general
specification which is so abstract that it becomes hard to use, since
you have to customize it for a particular application.

Past a certain point, you might as well say that you want to
standardize "b-trees" --- and that's something which belongs in an
algorithms book, and not an I-D or an RFC.

I will note that created distributed unique id's for applications
running in a cluster is very common system design interview question.
(Or at least, it used to be, until it got leaked and now there tons
and tons of pages on callicoder, topcoder, describing solutions and
how to approach it in interviews, such that at least at $WORK, it's
been blacklisted as an interview question.  :-)

So I'm not sure I'd consider it a "hard problem"; just as I'm not at
all convinced this is something that needs to be standardized.

    	      	      		     	      - Ted

---

From: Brad Peabody <[email-masked]>
Date: Tue, 4 Feb 2020 02:04:52 -0800

> algorithms book, and not an I-D or an RFC.
In practical terms, the issue I'm concerned about is that there are 
various points where software from different projects needs to 
communicate UUIDs to each other and so it turns from a general thing 
into something very specific. In this link I mentioned earlier 
https://github.com/uuidjs/uuid/issues/303#issuecomment-575992079 it's 
all about how UUIDs work with Postgres as primary keys.

The text encoding is particularly relevant, since hexes with dashes is 
not a particularly practical format (too long) for a many use cases.  So 
if you have a column in a database of type 'UUID' (or some other similar 
ID type) and then issue an update statement - there needs to be known 
text format and it would be great if it were more compact.   And if it 
were standardized then eventually various databases would implement it.  
The sorting is also a thing - see below.

But I do get what you mean on shorter IDs with less uniqueness guarantee 
- a spec isn't need to just generate a random opaque string that you're 
just going to have to check a database for to ensure you don't have a 
duplicate.

> will cause people to reinvent the wheel (possibly badly) at the

I think a part of the issue here is that since there is an existing UUID 
spec people then try to use it for things like database keys, and then 
run into these various rough edges:

- hex text format too long

- sorting is extra work for no benefit, having the raw bytes sort 
naturally in time sequence (for UUIDs with a timestamp) would seem to be 
a better way

- there is no official form of UUID that has a timestamp and then random 
data - the spec says to use the MAC address of the machine (version 1) 
which can be a security issue; and version 4 is not time-ordered.

So that's more info on the motivation and, at least from my perspective, 
the practical concerns that are driving this.

It would certainly be less of a change to just propose an update to the 
UUID spec that puts the date in a sequence that sorts as raw bytes and 
says feel free to use random data from a properly seeded CSPRNG instead 
of a MAC address if you're willing to have X collision probability in 
exchange for not having your MAC address there.  And also says btw hex 
encoding is big, so feel free also to use base32 or base64 according to 
what you want for your app. It would be great if these things had good 
names too so that when someone goes to implement this in a new database 
column type they can be referred to with sane names that match the 
spec.  Those points might be all it would take. And that was more or 
less my original intention with coming up with the original "UUID 
version 6" concept.

At the end of the day I guess the main driving use case is as a database 
primary key (and then also being able to easily use that PK in the same 
human readable form in things like URLs or written in documents), but 
the above sillyness ("rough edges") make this difficult with the current 
specification.

---

From: "Rob Wilton (rwilton)" <[email-masked]>
Date: Tue, 4 Feb 2020 11:36:49 +0000

Hi Brad,

I'm no expert on UUID's but some thoughts (as an individual contributor):

What you describe does sound to me like it could be a new form of UUID (if limited to a 128 bit format), and it could potentially also be useful.  E.g. a 128 bit UUID that has good database locality properties and minimizes the leakage of private information sounds useful if it can be reasonably specified and implemented.

I also note that RFC 4122 is 15 years old, and as Martin previously indicated there are security and privacy considerations that have evolved over time, hence updating RFC 4122 to make readers aware of those considerations also seems like it could potentially be useful.

Writing this up as a draft sounds like a good next step to see if there is enough wider interest.

Regards,
Rob

-----Original Message-----
From: ietf <[email-masked]> On Behalf Of Brad Peabody
Sent: 04 February 2020 10:05
To: Theodore Y. Ts'o <[email-masked]>
Cc: IETF discussion list <[email-masked]>
Subject: Re: UUID version 6 proposal, initial feedback

> algorithms book, and not an I-D or an RFC.
In practical terms, the issue I'm concerned about is that there are various points where software from different projects needs to communicate UUIDs to each other and so it turns from a general thing into something very specific. In this link I mentioned earlier
https://github.com/uuidjs/uuid/issues/303#issuecomment-575992079 it's all about how UUIDs work with Postgres as primary keys.

The text encoding is particularly relevant, since hexes with dashes is not a particularly practical format (too long) for a many use cases.  So if you have a column in a database of type 'UUID' (or some other similar ID type) and then issue an update statement - there needs to be known text format and it would be great if it were more compact.   And if it were standardized then eventually various databases would implement it. The sorting is also a thing - see below.

But I do get what you mean on shorter IDs with less uniqueness guarantee
- a spec isn't need to just generate a random opaque string that you're just going to have to check a database for to ensure you don't have a duplicate.

> will cause people to reinvent the wheel (possibly badly) at the 

I think a part of the issue here is that since there is an existing UUID spec people then try to use it for things like database keys, and then run into these various rough edges:

- sorting is extra work for no benefit, having the raw bytes sort naturally in time sequence (for UUIDs with a timestamp) would seem to be a better way

- there is no official form of UUID that has a timestamp and then random data - the spec says to use the MAC address of the machine (version 1) which can be a security issue; and version 4 is not time-ordered.

So that's more info on the motivation and, at least from my perspective, the practical concerns that are driving this.

It would certainly be less of a change to just propose an update to the UUID spec that puts the date in a sequence that sorts as raw bytes and says feel free to use random data from a properly seeded CSPRNG instead of a MAC address if you're willing to have X collision probability in exchange for not having your MAC address there.  And also says btw hex encoding is big, so feel free also to use base32 or base64 according to what you want for your app. It would be great if these things had good names too so that when someone goes to implement this in a new database column type they can be referred to with sane names that match the spec.  Those points might be all it would take. And that was more or less my original intention with coming up with the original "UUID version 6" concept.

At the end of the day I guess the main driving use case is as a database primary key (and then also being able to easily use that PK in the same human readable form in things like URLs or written in documents), but the above sillyness ("rough edges") make this difficult with the current specification.

---

From: Benjamin Kaduk <[email-masked]>
Date: Fri, 7 Feb 2020 16:16:52 -0800

On Sat, Feb 01, 2020 at 02:41:12AM +0000, 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.

Taking a bit of a tangent, you may find
https://tools.ietf.org/html/draft-gont-numeric-ids-sec-considerations-04 an
interesting read, even if it's not directly related to this work.

-Ben

---

From: Ben Ramsey <[email-masked]>
Date: Mon, 24 Feb 2020 22:09:15 -0600

On 2/4/20 11:36 UTC, Rob Wilton (rwilton) wrote:
> What you describe does sound to me like it could be a new form of
> UUID (if limited to a 128 bit format), and it could potentially also
> be useful.  E.g. a 128 bit UUID that has good database locality
> properties and minimizes the leakage of private information sounds
> useful if it can be reasonably specified and implemented.
> 
> I also note that RFC 4122 is 15 years old, and as Martin previously
> indicated there are security and privacy considerations that have
> evolved over time, hence updating RFC 4122 to make readers aware of
> those considerations also seems like it could potentially be useful.
> 

FYI, Brad has submitted his first draft for review. You can see it here:
https://datatracker.ietf.org/doc/draft-peabody-dispatch-new-uuid-format/

I've been following this for a while, and as the author of a popular
userland UUID library for PHP <https://github.com/ramsey/uuid>, I'd like
to throw my support behind this proposal and describe a few of the pain
points that have led application developers down the path of modifying
the existing UUID structure to better suite their needs.

As a standard, the UUID format is ubiquitous and portable. Despite some
of its shortcomings, and the desire (as some have raised on this list)
to create a new standard other than UUID, it's a desirable format, for
many reasons.

There is one primary shortcoming that results in a frequent need to
modify the format, and this is the shortcoming that Brad's version 6
UUID attempts to overcome. When developers begin storing UUIDs in
relational databases, they inevitably arrive at one or all of these
articles (which I'm surprised haven't yet been mentioned in this thread):

* http://www.informit.com/articles/printerfriendly/25862
* https://blog.codinghorror.com/primary-keys-ids-versus-guids/
* https://www.percona.com/blog/2014/12/19/store-uuid-optimized-way/

As a result, in my PHP library, I have implemented alternate _codecs_ to
encode/decode UUIDs in more optimal ways for database fields, especially
for use as primary keys. Two of these codecs are:

* Timestamp-first COMB
* Ordered Time UUID

The timestamp-first COMB is a version 4 UUID combined with a Unix
timestamp as the first 48 bits, resulting in a monotonically-increasing
UUID. For all intents and purposes, the resulting value always looks
like a version 4 UUID (the version and variant bits remain in the same
places as defined by RFC 4122).

The ordered time UUID is similar but retains the semantics of the
version 1 UUID. That is, the UUID can be deconstructed to produce a node
value, clock sequence value, and timestamp with nanosecond fidelity. The
difference is that the timestamp is rearranged so that the UUID is
monotonically increasing.

The problem with this approach, though, is that the first 2 bytes are
the same as the time_hi_and_version field, which means the UUID version
now occupies the first 4 bits of the UUID. Unless you know how the bits
of this UUID were rearranged, there's no way to reliably tell that it
was originally a version 1 UUID.

Therein lies the problem. The use-case is for a version 1 UUID, from
which an application can retrieve nanosecond timestamp and node values,
while being monotonically increasing so that it does not scatter the
records in my database engine. But, by rearranging the bits to achieve
this, I'm placing a dependency on my application to know how to
deconstruct the bits when retrieving from the database. It's not very
portable, error-prone, and can lead to developer confusion.

Brad's version 6 UUID solves this problem.

There are two primary issues I have with the current draft (I have many
other comments, but I want to start with these two, and I'm also unsure
how IETF discussion on drafts proceeds, so I'm eager to learn from others):

1. The draft doesn't appear to go into detail about the arrangement of
the bits and how the timestamp should be split to accommodate the
version field, while the earlier version (posted here:
<http://gh.peabody.io/uuidv6/>) does go into this detail.

2. IMO, I think the alternate text formats do not belong in this
document. I think this document should focus on the version 6 UUID, and
the alternate text formats can be defined in a separate document. The
ULID spec seems like a good specification to draw inspiration from,
since it's compatible with any 128-bit number and already has a number
of implementations. <https://github.com/ulid/spec>

Cheers,
Ben

P.S. Yes, I am aware of privacy concerns with the use of the node field
in version 1 UUIDs. I'm happy to discuss potential use-cases of the node
field that can be used to track where a UUID was minted without
revealing potentially private information, but I don't think the
mechanism for creating the node field should be part of this draft.

---

From: Laurence Lundblade <[email-masked]>
Date: Wed, 26 Feb 2020 11:09:25 -0800

The UUID format seems somewhat anachronistic going back to a time when good HW RNGs were uncommon. That’s not true today. HW was introduced between 2010 and 2015 for good RNGs, particularly this <https://en.wikipedia.org/wiki/RDRAND>  The better choice today seems just a sequence of cryptographic quality random bytes.  This is already being done for a nonce field in some protocols. They are not UUID format.

Except, as discussed, true RNG IDs don’t work well with databases. 

One option is to say the databases should be fixed to work with true RNG IDs. In some case this is what will have to happen.

Another is to design an ID that is database friendly, which is what this draft is about. Protocols can use that if they like and they can meet the generation requirements. Generation requirements seem to require a clock or stored coordinate state. 

For a new ID, it might be worth breaking free from the UUID format to design a better database-friendly ID. The UUID format doesn’t seem particularly necessary nowadays. It might good to allow for more bits too (UUIDs are fixed at slightly less than 128).

LL

> On Feb 24, 2020, at 8:09 PM, Ben Ramsey <[email-masked]> wrote:
>

---

From: George Michaelson <[email-masked]>
Date: Thu, 27 Feb 2020 08:38:15 +1000

For every example (in some things) there is a counter example. As a
thought experiment I have tried to think what is the counter-example
for a DB aligned UUID. The only one I have in hypothesis is something
around the information leakage that two UUID reside in the same
logical data frame.

So I think there is a likelihood more real/tangible reasons NOT to do
this exist, alongside the proven ones to deliberately do this. (e.g.
sharding, Bloom filters over discrete sets, parallelism...)

Therefore, I hope any work in UUID is additive, not subtractive or
solely re-definitional to *one* form, because well.. for every UUID
structural example, there probably is a counter-example.

-G

On Thu, Feb 27, 2020 at 5:09 AM Laurence Lundblade
<[email-masked]> wrote:
>
> The UUID format seems somewhat anachronistic going back to a time when good HW RNGs were uncommon. That’s not true today. HW was introduced between 2010 and 2015 for good RNGs, particularly this  The better choice today seems just a sequence of cryptographic quality random bytes.  This is already being done for a nonce field in some protocols. They are not UUID format.
>