Live data from Hacker News

Ask HN: We just had an actual UUID v4 collision...

news.ycombinator.com

251–260 of 369 posts

Re: Ask HN: We just had an actual UUID v4 collision...

#251
post #153

Are your UUIDs generated client side or server side? If it's client side, it could be due to a crawling bot. Googlebot for example executes Javascript using deterministic "randomness".

Yeah, the answer almost certainly has to be this, or that they were using an old version of the package which didn't use the system RNG correctly (the current version appears to do it correctly, but I didn't dive into older versions), or their project has loaded an old broken polyfill re-implementing the JS crypto API, or they were running this on a hosting setup that does something jank like resuming the same VM snapshot with its RNG state on multiple servers. This category of explanation is many orders of magnitude more likely than a true random collision.

Re: Ask HN: We just had an actual UUID v4 collision...

#252
post #173

Earlier quoted context omitted.

You're heavily leaning on "collision like this" to relate to the exact time stamps for your statement to be true. It's equality possible to interpret the "like this" to the collision itself, without a focus on the 1 year distance between the creation dates. So I guess both views are valid.

The inclusion of a timestamp in v7 makes collisions impossible unless the generating systems think that the time is the same down to the millisecond, which makes the temporal distance quite relevant.

Plenty of systems end up generating multiple UUID's in a single millisecond.

The issue with UUIDv7 is that you also have significantly less entropy since you only have a 62 bits (sometimes less, depending on implementation) of "random" data. So while the time aspect of format lowers the chances of collisions, generating two UUIDv7's in the same millisecond (depending on implementation) have a significantly higher chance of collision than two UUIDv4's.

It's still incredibly unlikely, but it's also incredibly unlikely you generate two matching UUIDv4's, but it does happen.

TLDR; It's possible to generate matching UUIDv7's, don't assume otherwise.

Re: Ask HN: We just had an actual UUID v4 collision...

#253
post #121

Some discussion here: https://github.com/uuidjs/uuid/issues/546 Eg: > FWIW, I just tested crypto.getRandomValues() behavior on googlebot and it is also deterministic(!)

That makes sense. I'm not sure why anybody would generate UUIDs in browsers though, it seems to defeat the purpose.

Re: Ask HN: We just had an actual UUID v4 collision...

#254

Earlier quoted context omitted.

It's still possible in most implementations of UUIDv7. UUIDv7 assigns the first 48 bits for the timestamp in milliseconds. You can generate a lot of UUID's in a millisecond though! Then you have another 12 bits that you can use as you wish; "rand_a". The spec has a few methods they suggest on how to use these bits including 12 bits of random data, using it for sub-millisecond timestamps, or creating a monotonic count…

I think by the time you're building a system that needs to generate (and persist!) billions of identifiers per millisecond, you're solidly past the point where all your design decisions need to be vetted for whether they make sense on your extremely exotic setup.

But 12 bits is not "billions of identifiers" -- it's 4096. Once you exhaust that counter in the same millisecond, you are still relying on a gamble that your random source will not generate the exact same bit sequence for the previous same counter value. And this thread started out with the OP explaining that random collisions are much more common than we'd like them to be, for various reasons.

Re: Ask HN: We just had an actual UUID v4 collision...

#255
post #186

This reminds me of a passage from the book "Pro Git". https://git-scm.com/book/en/v2 > "Here’s an example to give you an idea of what it would take to get a SHA-1 collision. If all 6.5 billion humans on Earth were programming, and every second, each one was producing code that was the equivalent of the entire Linux kernel history (6.5 million Git objects) and pushing it into one enormous Git repository, it would take…

Reminds me of this page with an example for understanding how many permutations there are for a shuffled deck of cards: https://czep.net/weblog/52cards.html

> So, just how large is it? Let's try to wrap our puny human brains around the magnitude of this number with a fun little theoretical exercise. Start a timer that will count down the number of seconds from 52! to 0. We're going to see how much fun we can have before the timer counts down all the way. Shall we play a game?

> Start by picking your favorite spot on the equator. You're going to walk around the world along the equator, but take a very leisurely pace of one step every billion years. The equatorial circumference of the Earth is 40,075,017 meters. Make sure to pack a deck of playing cards, so you can get in a few trillion hands of solitaire between steps. After you complete your round the world trip, remove one drop of water from the Pacific Ocean. Now do the same thing again: walk around the world at one billion years per step, removing one drop of water from the Pacific Ocean each time you circle the globe. The Pacific Ocean contains 707.6 million cubic kilometers of water. Continue until the ocean is empty. When it is, take one sheet of paper and place it flat on the ground. Now, fill the ocean back up and start the entire process all over again, adding a sheet of paper to the stack each time you’ve emptied the ocean. Do this until the stack of paper reaches from the Earth to the Sun. Take a glance at the timer, you will see that the three left-most digits haven’t even changed. You still have 8.063e67 more seconds to go. 1 Astronomical Unit, the distance from the Earth to the Sun, is defined as 149,597,870.691 kilometers. So, take the stack of papers down and do it all over again. One thousand times more. Unfortunately, that still won’t do it. There are still more than 5.385e67 seconds remaining. You’re just about a third of the way done.

Re: Ask HN: We just had an actual UUID v4 collision...

#256

Earlier quoted context omitted.

You must have missed the “at scale” part. There is nothing inexpensive about extra network hops, cache misses, and page faults implied by your solution. Indexing at scale is almost always lossy for performance reasons. The location where you insert a new record is frequently not the same location as where you have to search for an existing record. It is resource amplification all the way down. In a lot of systems tha…

No I didn't miss it. DynamoDb works fine, using CQRS if necessary.

literally the whole point of randomly generating UUIDs is that you don't need to check for collision. that's what the "U"s are for. that is the abstraction that is supposedly being provided. "using " is not in any way a "scalable solution" for that with no other context. nor is just throwing out . the whole point is that it is a global (well, per name, "universal") abstraction that can, in practice, have holes that make it so you can't use it "universal"-ly.

Re: Ask HN: We just had an actual UUID v4 collision...

#257
post #244

Earlier quoted context omitted.

Only expensive if you have unsorted keys or lack an index. Neither of which are unscalable.

AKA centralising a decentralised identifier generator?

exactly lmao. that is exactly what is being presented as "scalable ". sigh.

Re: Ask HN: We just had an actual UUID v4 collision...

#258

Earlier quoted context omitted.

Yes, because UUIDv7 gives up some random bits in order to include the timestamp, which is done in a way that makes UUIDv7s quick to sort by timestamp.

How does including the timestamp expose me to adversarial exploitation?

It reveals the time you created the UUID, for one. That can lead to a bunch of problems.

Re: Ask HN: We just had an actual UUID v4 collision...

#259

This is usually caused by an insufficently seeded PRNG. Are you generating the UUID in the backend, or the frontend? Frontend is fundamentally unreliable for many reasons, including deliberate collisions. So if that case you'll need to handle collisions somehow. Though you can still engineer around common sources of collisions, the specifics depend on the environment. On the other hand making a backend reliable is fe…

I remember hearing about Segment (analytics company) had their entire product based around UUIDs generated in web browsers. There were collisions all over the place, the product was seemingly incapable of producing useful data at a fundamental level because of it. Hopefully they've fixed that now.

Re: Ask HN: We just had an actual UUID v4 collision...

#260
post #121

Some discussion here: https://github.com/uuidjs/uuid/issues/546 Eg: > FWIW, I just tested crypto.getRandomValues() behavior on googlebot and it is also deterministic(!)

That makes sense. I'm not sure why anybody would generate UUIDs in browsers though, it seems to defeat the purpose.

Tell that to Segment. Hopefully they've fixed that, but they didn't seem to think it was a problem years ago (spoiler: it was a big problem).
Post reply on HN