5 ms·

Analyzing New Unique Identifier Formats (UUIDv6, UUIDv7, and UUIDv8) (2022)

107 points by BerislavLopac 3y ago

skissane 3y ago
The Internet Draft link in the article has expired. Here is the current version: https://datatracker.ietf.org/doc/html/draft-ietf-uuidrev-rfc4122bis https://datatracker.ietf.org/doc/html/draft-ietf-uuidrev-rfc...
hn_throwaway_99 3y ago
Commented on this early today, V7 UUIDs are really ideal to use as DB primary keys: https://news.ycombinator.com/item?id=36433481 https://news.ycombinator.com/item?id=36433481
- rubatuga 3y ago
  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?
  - vore 3y ago
    When you need to generate IDs that don't reveal when they were generated.
    - vbezhenar 3y ago
      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.
      - hn_throwaway_99 3y ago
        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.
    - JdeBP 3y ago
      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 https://github.com/bruceg/ezmlm-idx/blob/master/lib/surf.3 One could adapt this approach to UUIDs.
      - tadfisher 3y ago
        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(
        JdeBP 3y ago
        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.
  - hn_throwaway_99 3y ago
    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).
zarzavat 3y ago
https://archive.is/ZoArF https://archive.is/ZoArF
WalterBright 3y ago
Sounds like a job for --- blockchain!
- rewmie 3y ago
  Blockchain: the perennial solution in search for a problem.
  - j-pb 3y ago
    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.
  - WalterBright 3y ago
    Actually, blockchain will work for generating guaranteed unique identifiers. After all, each bitcoin is different, right?
    - c00lio 3y ago
      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".
    - bawolff 3y ago
      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.
- bawolff 3y ago
  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.
Robin_Message 3y ago
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
- JdeBP 3y ago
  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.
- newaccount74 3y ago
  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.
vbezhenar 3y ago
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.
- hn_throwaway_99 3y ago
  ULIDs, https://github.com/ulid/spec https://github.com/ulid/spec, are also already in widespread use and are essentially the same idea as v7 UUIDs.
  - vbezhenar 3y ago
    "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.
    - hn_throwaway_99 3y ago
      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 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.
bloak 3y ago
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"!
- lbriner 3y ago
  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.
  - ademarre 3y ago
    > 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.
  - dugmartin 3y ago
    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/ 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.
wiradikusuma 3y ago
See also: https://github.com/vladmihalcea/hypersistence-tsid https://github.com/vladmihalcea/hypersistence-tsid (shorter than UUID)
- victor106 3y ago
  Thanks for this. Vlad's articles are always very informative and practical.
- rcme 3y ago
  I often see uuids stored as strings, which makes me think there are many people who don’t care about length.
- accrual 3y ago
  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.
mikojan 3y ago
https://archive.is/ZoArF https://archive.is/ZoArF
dugmartin 3y ago
I’ve started using nanoid for generated ids. Here is the JavaScript version: https://github.com/ai/nanoid 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.

107 points by BerislavLopac 3y ago

The Internet Draft link in the article has expired. Here is the current version: https://datatracker.ietf.org/doc/html/draft-ietf-uuidrev-rfc4122bis https://datatracker.ietf.org/doc/html/draft-ietf-uuidrev-rfc...

hn_throwaway_99 3y ago

Commented on this early today, V7 UUIDs are really ideal to use as DB primary keys: https://news.ycombinator.com/item?id=36433481 https://news.ycombinator.com/item?id=36433481

rubatuga 3y ago
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?
- vore 3y ago
  When you need to generate IDs that don't reveal when they were generated.
  - vbezhenar 3y ago
    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.
    - hn_throwaway_99 3y ago
      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.
  - JdeBP 3y ago
    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 https://github.com/bruceg/ezmlm-idx/blob/master/lib/surf.3 One could adapt this approach to UUIDs.
    - tadfisher 3y ago
      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(
      - JdeBP 3y ago
        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.
- hn_throwaway_99 3y ago
  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).

zarzavat 3y ago

https://archive.is/ZoArF https://archive.is/ZoArF

WalterBright 3y ago

Sounds like a job for --- blockchain!

rewmie 3y ago
Blockchain: the perennial solution in search for a problem.
- j-pb 3y ago
  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.
- WalterBright 3y ago
  Actually, blockchain will work for generating guaranteed unique identifiers. After all, each bitcoin is different, right?
  - c00lio 3y ago
    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".
  - bawolff 3y ago
    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.
bawolff 3y ago
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.

Robin_Message 3y ago

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

JdeBP 3y ago
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.
newaccount74 3y ago
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.

vbezhenar 3y ago

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.

hn_throwaway_99 3y ago
ULIDs, https://github.com/ulid/spec https://github.com/ulid/spec, are also already in widespread use and are essentially the same idea as v7 UUIDs.
- vbezhenar 3y ago
  "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.
  - hn_throwaway_99 3y ago
    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 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.

bloak 3y ago

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"!

lbriner 3y ago
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.
- ademarre 3y ago
  > 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.
- dugmartin 3y ago
  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/ 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.

wiradikusuma 3y ago

See also: https://github.com/vladmihalcea/hypersistence-tsid https://github.com/vladmihalcea/hypersistence-tsid (shorter than UUID)

victor106 3y ago
Thanks for this. Vlad's articles are always very informative and practical.
rcme 3y ago
I often see uuids stored as strings, which makes me think there are many people who don’t care about length.
accrual 3y ago
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.

mikojan 3y ago

https://archive.is/ZoArF https://archive.is/ZoArF

dugmartin 3y ago

I’ve started using nanoid for generated ids. Here is the JavaScript version: https://github.com/ai/nanoid 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.