Analyzing New Unique Identifier Formats (UUIDv6, UUIDv7, and UUIDv8) (2022)(blog.devgenius.io)
blog.devgenius.io
Analyzing New Unique Identifier Formats (UUIDv6, UUIDv7, and UUIDv8) (2022)
https://blog.devgenius.io/analyzing-new-unique-identifier-formats-uuidv6-uuidv7-and-uuidv8-d6cc5cd7391a
10 comments
Commented on this early today, V7 UUIDs are really ideal to use as DB primary keys: https://news.ycombinator.com/item?id=36433481
People definitely rely on the number of bits in v4 for security. I wonder what are some use cases where you can't rely on v7 for security?
When you need to generate IDs that don't reveal when they were generated.
Daniel J. Bernstein addressed this the 1990s:
* Construct a tuple of the current TAI64NA time, the process ID, some other IDs, and a sequence number.
* Encrypt this 384-bit tuple with a 1024-bit secret using SURF.
* The 256-bit result is the ID.
https://github.com/bruceg/ezmlm-idx/blob/master/lib/surf.3
One could adapt this approach to UUIDs.
* Construct a tuple of the current TAI64NA time, the process ID, some other IDs, and a sequence number.
* Encrypt this 384-bit tuple with a 1024-bit secret using SURF.
* The 256-bit result is the ID.
https://github.com/bruceg/ezmlm-idx/blob/master/lib/surf.3
One could adapt this approach to UUIDs.
This eliminates the primary benefit of V7 UUIDs, which is that keys sort temporally, which is almost always the same as the insertion order of a database table (or most collection-like data structures(
But satisfies, as v7 does not satisfy, the actually stated constraint of "IDs that don't reveal when they were generated" whilst still using timestamps, no permanent IDs from hardware, and no centralized ticket-issuing mechanism for sequence numbers. There is more than one feature of v7, and the top of this sub-thread started a discussion of how one would trade them for better security.
For this case just add random(0, 2^128/N) to the previous UUID. N*2 is average number of ascending UUIDs you want to maintain for database performance. If N is low enough (like 1024), database will be happy and UUIDs will be pretty random and won’t reveal much. There won’t be global ordering, but it leaks timing information in one way or another, anyway.
The ascending order of IDs though is a great property that is used in other contexts. I.e. for many of our workflow processes we want queries to return reverse chronological order, and "ORDER BY id DESC" is our most common sort. A v7 UUID as a primary key is still great for that, so you'd usually want to keep that property.
People rely on v4 UUIDs for things like session tokens, where the unguessability of the ID is ensured by the amount of randomness it has. You shouldn't use a v7 UUID here because it has considerably less entropy.
However, for object retrieval (e.g. "show me my accounts with object IDs X, Y and Z"), you shouldn't be just relying on the unguessability of the ID anyway - you should be using appropriate access control permission checks (because for object IDs even if they are unguessable they are frequently not guaranteed to be private, e.g. they show up in log files, they may be in URLs that people share, etc., and they don't expire, unlike a session ID).
A frequent source of severe security vulnerabilities are bugs in these access control checks, which can lead to insecure direct object reference (IDOR) vulnerabilities, where I can say "Show me account with ID X" even though I don't own or have permissions to that account. If you're using incrementing integer IDs for your object IDs here, abusing this bug is trivially easy - just walk up and down the IDs next to yours. I think it was the Parler app that had a particularly egregious case of this - they weren't doing any access control checks on posts at all.
However, if your object ID is a v7 UUID, this bug becomes much more difficult to abuse, because your IDs may not be completely unguessable to a strong adversary, but you should be able to detect the failed access attempts when you see someone trying billions of access attempts and only getting not found errors (of course, you should be rate limiting these attempts in the first place).
However, for object retrieval (e.g. "show me my accounts with object IDs X, Y and Z"), you shouldn't be just relying on the unguessability of the ID anyway - you should be using appropriate access control permission checks (because for object IDs even if they are unguessable they are frequently not guaranteed to be private, e.g. they show up in log files, they may be in URLs that people share, etc., and they don't expire, unlike a session ID).
A frequent source of severe security vulnerabilities are bugs in these access control checks, which can lead to insecure direct object reference (IDOR) vulnerabilities, where I can say "Show me account with ID X" even though I don't own or have permissions to that account. If you're using incrementing integer IDs for your object IDs here, abusing this bug is trivially easy - just walk up and down the IDs next to yours. I think it was the Parler app that had a particularly egregious case of this - they weren't doing any access control checks on posts at all.
However, if your object ID is a v7 UUID, this bug becomes much more difficult to abuse, because your IDs may not be completely unguessable to a strong adversary, but you should be able to detect the failed access attempts when you see someone trying billions of access attempts and only getting not found errors (of course, you should be rate limiting these attempts in the first place).
The Internet Draft link in the article has expired. Here is the current version: https://datatracker.ietf.org/doc/html/draft-ietf-uuidrev-rfc...
I actually invented something that turned out identical to UUIDv7 when I was thinking on this problem. So I approve this particular version. It is good and well thought out (:
The only issue is lack of trusted implementations. But it’s easy enough to implement it.
The only issue is lack of trusted implementations. But it’s easy enough to implement it.
ULIDs, https://github.com/ulid/spec, are also already in widespread use and are essentially the same idea as v7 UUIDs.
"When generating a ULID within the same millisecond, we can provide some guarantees regarding sort order. Namely, if the same millisecond is detected, the random component is incremented by 1 bit in the least significant bit position (with carrying)."
This makes ULIDs easily predictable and defeats one of major reasons to use UUID. 1 millisecond is a lot and thousands records could be generated in one millisecond, especially with some kind of batching.
This algorithm could be improved: either generate new random 80 bits until they're higher than previously issued ULID or select few bits for counter and rest of bits for randomness. But then we'll end up almost with UUIDv7, I guess.
Also their representation idea... Well, I think that UUID representation is a widely used everywhere.
So basically I think that ULID is an amalgamation of questionable ideas and I'd stay away from it.
This makes ULIDs easily predictable and defeats one of major reasons to use UUID. 1 millisecond is a lot and thousands records could be generated in one millisecond, especially with some kind of batching.
This algorithm could be improved: either generate new random 80 bits until they're higher than previously issued ULID or select few bits for counter and rest of bits for randomness. But then we'll end up almost with UUIDv7, I guess.
Also their representation idea... Well, I think that UUID representation is a widely used everywhere.
So basically I think that ULID is an amalgamation of questionable ideas and I'd stay away from it.
The spec as written on that page is confusing on that point, but the incrementing-counter-within-the-same-millisecond-behavior only happens if you explicitly specify a "monotonicFactory", https://github.com/ulid/javascript#monotonic-ulids. The default behavior (just using the ulid() function) doesn't do that, it generates a completely random value regardless of the millisecond value.
If it's random value, then generated UUIDs won't always be ascending which defeats purpose as well.
No, that's not really it either. ULIDs have both a time component (in this case accurate to the millisecond) and a random component. Thus the order is always accurate up to the ms, and for the vast majority of applications anything created in the same millisecond can be considered created "at the same time", so it's usually OK if order is undetermined within the same MS.
Note that the UUID v7 spec is largely modeled after the ULID spec. ULIDs came first, and they traded the "standard" UUID format of 8x-4x-4x-4x-12x hex string for the more compact Crockford base32 format, and there are some other minor differences in number of timestamp bits vs. number of random bits, but they are otherwise functionally equivalent.
Note that the UUID v7 spec is largely modeled after the ULID spec. ULIDs came first, and they traded the "standard" UUID format of 8x-4x-4x-4x-12x hex string for the more compact Crockford base32 format, and there are some other minor differences in number of timestamp bits vs. number of random bits, but they are otherwise functionally equivalent.
See also: https://github.com/vladmihalcea/hypersistence-tsid (shorter than UUID)
That's great, those seem like very practical UIDs for a web application. I didn't see a port to Node yet, that could be a fun project.
I often see uuids stored as strings, which makes me think there are many people who don’t care about length.
Thanks for this. Vlad's articles are always very informative and practical.
ULID seems like a better solution to me: still 128 bits but with a more compact canonical format and sensible timestamp and increment semantics.
I guess it's not far off a v7 UUID though.
https://github.com/ulid/spec
https://github.com/ulid/spec
Alternatively: UUID v7 and v8 seem like the better solution. They're the subject of a more formal standardization process; they're compatible with existing UUIDs because they correctly set the version number and variant fields; v7 has exactly the same 48-bit POSIX timestamp as an ULID; and they already have widespread transformations to and from machine-readable form.
Picking something primarily because of its human-readable form rather than its machine-readable form is probably not the best decision criterion.
Picking something primarily because of its human-readable form rather than its machine-readable form is probably not the best decision criterion.
UUIDv7 is nice because it's just a variant of UUID, which are already supported in very many databases and programming languages. And even if you are writing code for an obscure microprocessor where no implementation is available, the encoding scheme is well known and straightforward.
ULID on the other hand depends on an uncommon encoding scheme. It is more complicated than hex encoding, so it's easy to make mistakes when implementing it.
Finally, the encoding scheme is weird, because it "wastes" a few bits at the end, so if you are not careful enough you could end up in a situation where two ULIDs in text form are different but once you convert them to bits they are the same.
ULID on the other hand depends on an uncommon encoding scheme. It is more complicated than hex encoding, so it's easy to make mistakes when implementing it.
Finally, the encoding scheme is weird, because it "wastes" a few bits at the end, so if you are not careful enough you could end up in a situation where two ULIDs in text form are different but once you convert them to bits they are the same.
The following isn't a serious contribution to the discussion, but somehow this reminds me of the people in Hitchhiker's Guide to the Galaxy unable to invent the wheel because they can't decide what colour to make it. Personally I just generate a reasonable number of random bits, encode them in a reasonably efficient manner, and move on to something more interesting. By ignoring "standards" I make my UUIDs just that little bit more "unique"!
I don't understand this statement.
UUIDs rarely have to be unique compared to every other place in the world where they are used, they just need to be unique within the same context. The reason for using NIC addresses and time is to ensure that the chance of a collision is really small (but not 0). Saying that you are making them a little more unique doesn't sound like good motivation.
The second part is that just using random numbers gives you no real guarantees of uniqueness since without seeding with time and NIC, it would be highly likely that multiple systems around the world would generate the same number.
UUIDs rarely have to be unique compared to every other place in the world where they are used, they just need to be unique within the same context. The reason for using NIC addresses and time is to ensure that the chance of a collision is really small (but not 0). Saying that you are making them a little more unique doesn't sound like good motivation.
The second part is that just using random numbers gives you no real guarantees of uniqueness since without seeding with time and NIC, it would be highly likely that multiple systems around the world would generate the same number.
> it would be highly likely that multiple systems around the world would generate the same number.
"Highly likely"? No. You are ignoring probability. See UUIDv4, which does not use time or NIC/MAC but does use 122 random bits.
"Highly likely"? No. You are ignoring probability. See UUIDv4, which does not use time or NIC/MAC but does use 122 random bits.
In another comment I mentioned I use nanoid in my projects now. It has a default space of 64^21 and has an a page where you can play with key lengths and alphabet sizes and see the probability of collisions :
https://zelark.github.io/nano-id-cc/
At the default 64 character alphabet with a 21 character key length it would take ~41 million years in order to have a 1% probability of at least one collision if you generated 1000 ids per second.
https://zelark.github.io/nano-id-cc/
At the default 64 character alphabet with a 21 character key length it would take ~41 million years in order to have a 1% probability of at least one collision if you generated 1000 ids per second.
I’ve started using nanoid for generated ids. Here is the JavaScript version:
https://github.com/ai/nanoid
Some info from that page:
- Safe. It uses hardware random generator. Can be used in clusters.
- Short IDs. It uses a larger alphabet than UUID (A-Za-z0-9_-). So ID size was reduced from 36 to 21 symbols.
- Portable. Nano ID was ported to 20 programming languages.
https://github.com/ai/nanoid
Some info from that page:
- Safe. It uses hardware random generator. Can be used in clusters.
- Short IDs. It uses a larger alphabet than UUID (A-Za-z0-9_-). So ID size was reduced from 36 to 21 symbols.
- Portable. Nano ID was ported to 20 programming languages.
Sounds like a job for --- blockchain!
Blockchain: the perennial solution in search for a problem.
Actually, blockchain will work for generating guaranteed unique identifiers. After all, each bitcoin is different, right?
Creating unique identifiers while having access to a global db of all previous unique identifiers is not really the problem uuid is trying to solve most of the time.
Each bitcoin is identified by a block assigning it to a key. Keys are not guaranteed to be unique, with enough guesses you can duplicate one (if you have some time before the heat death of the universe or so) and maybe win the lottery (i.e. access to someone else's bitcoins). So in all, things are more "very probably unique".
There are two uses cases that blockchain would solve nicely.
Proof of publication in a fully decentralized academic journal, as an alternative to the current grifting scientific publishing industry.
As a consensus protocol for a distributed graph database, where you ensure consistency through exclusive ownership of nodes by single writers.
But those things don't offer any get rich quick shemes, so we're stuck if crypto bros and pyramid shemes.
Proof of publication in a fully decentralized academic journal, as an alternative to the current grifting scientific publishing industry.
As a consensus protocol for a distributed graph database, where you ensure consistency through exclusive ownership of nodes by single writers.
But those things don't offer any get rich quick shemes, so we're stuck if crypto bros and pyramid shemes.
I don't know if your sarcastic or not, but no, blockchains, even in their most idealistic form, are not a suitable solution to the problem uuid's solve.