Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

news.ycombinator.com

Post reply on HN
Print view View original

281–290 of 369 posts

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

#281

Post by pinkmuffinere »

kuratkull wrote: post #116
wongarsu wrote: post #68

Earlier quoted context omitted.

At some point someone optimizes the system to a global company-wide incrementing 128 bit counter. Instead of needing a costly database lookup against a growing database the microservice just fetches the current counter, increments it by one and hands out the new value. Easy, fast O(1) operation. This even allows you to shard the service to provide high availability and distribute the service globally to reduce latenc…

Define a random 128 bit key that you will never change. Use that key to encrypt 128 bit integers in sequence using AES-128, each one comes out as a, for all practical purposes, unique unpredictable ID.

> each one comes out as a, for all practical purposes, unique unpredictable ID

I don't have much cryptography experience, but this seems _suuuuper_ suspicious. I think the "for all practical purposes" is doing a lot of lifting here? If it was this easy, surely this is what we'd use, and there wouldn't be UUID v4 to begin with.

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

#282

Post by kristjansson »

pinkmuffinere wrote: post #281
kuratkull wrote: post #116

Earlier quoted context omitted.

Define a random 128 bit key that you will never change. Use that key to encrypt 128 bit integers in sequence using AES-128, each one comes out as a, for all practical purposes, unique unpredictable ID.

> each one comes out as a, for all practical purposes, unique unpredictable ID I don't have much cryptography experience, but this seems _suuuuper_ suspicious. I think the "for all practical purposes" is doing a lot of lifting here? If it was this easy, surely this is what we'd use, and there wouldn't be UUID v4 to begin with.

The value of uuid is the lack of coordination. “…integers in sequence…” requires quite a bit of coordination if you have more than one computer ;)

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

#283

Post by kristjansson »

throw0101c wrote: post #96
wongarsu wrote: post #68

Earlier quoted context omitted.

At some point someone optimizes the system to a global company-wide incrementing 128 bit counter. Instead of needing a costly database lookup against a growing database the microservice just fetches the current counter, increments it by one and hands out the new value. Easy, fast O(1) operation. This even allows you to shard the service to provide high availability and distribute the service globally to reduce latenc…

> At some point someone optimizes the system to a global company-wide incrementing 128 bit counter. Some UUID versions include time, so there's a bit of a counter in that.

What is the arrow of time if not a single global monotonically increasing sequence?

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

#284

Post by ms_menardi »

greiskul wrote: post #233
LocalH wrote: post #141

Earlier quoted context omitted.

This is why CloudFlare has done what they did with the lava lamp wall. Not that the wall is such a great source of entropy on its own - I'm sure it's not their only source, but you can never have too many sources of entropy - but it makes it visible in a way that can grab those who don't fully understand the concepts of RNGs and how entropy plays into that. The more sources of entropy, the more closely you approach "…

> you can never have too many sources of entropy This is so true. And the beauty is that with algorithms, we don't even need to know much about the entropy to be able to extract it. There is the Von Neumann method of generating an unbiased coin from a biased coin. Of throwing it twice, and checking if you got HT or TH. And completely discarding all HH or TT results. It doesn't matter if the coin you are using is 20%…

> There is the Von Neumann method of generating an unbiased coin from a biased coin. Of throwing it twice, and checking if you got HT or TH. And completely discarding all HH or TT results. It doesn't matter if the coin you are using is 20% or 80%, the result will be a true 50/50.

This blew my mind. Thank you!

I had to think about it a bit, so for anyone scratching their head right now trying to figure it out, consider it this way:

what matters is the ordering, of heads-then-tails, or tails-then-heads.

It doesn't matter that it's biased one way or the other, if you keep flipping pairs until you get a result with two different values, it's a 50/50 chance whether the less-likely result comes first, or second.

You might only have a 20% chance of any particular pair having a tails (for example), but in the cases where you do have a tails, it's a 50/50 chance that it comes first or second.

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

#286

Post by throwaway89865 »

ms_menardi wrote: post #284
greiskul wrote: post #233

Earlier quoted context omitted.

> you can never have too many sources of entropy This is so true. And the beauty is that with algorithms, we don't even need to know much about the entropy to be able to extract it. There is the Von Neumann method of generating an unbiased coin from a biased coin. Of throwing it twice, and checking if you got HT or TH. And completely discarding all HH or TT results. It doesn't matter if the coin you are using is 20%…

> There is the Von Neumann method of generating an unbiased coin from a biased coin. Of throwing it twice, and checking if you got HT or TH. And completely discarding all HH or TT results. It doesn't matter if the coin you are using is 20% or 80%, the result will be a true 50/50. This blew my mind. Thank you! I had to think about it a bit, so for anyone scratching their head right now trying to figure it out, conside…

Not very random if it's only TH or HT. Trivial to brute force with no more than two tries!

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

#287

Post by xyzzy123 »

I had dup uuids causing soak test failures in a Linux based distributed system. After long investigation it turned out there was a kernel bug (race condition) that meant two processes on MP system reading from /dev/random at the same could (very rarely, like 1 in a million) get the same bytes when reading the device.

I'd look at rng initialisation first.

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

#288

Post by other_herbert »

ssalka wrote: post #168
throwaway_19sz wrote: post #50

Funny story no one will believe, but it’s true. A good friend of mine joined a startup as CTO 10 years ago, high growth phase, maybe 200 devs… In his first week he discovered the company had a microservice for generating new UUIDs. One endpoint with its own dedicated team of 3 engineers …including a database guy (the plot thickens). Other teams were instructed to call this service every time they needed a new ‘safe’…

At one of my previous jobs, there was a function `createEntityWithRandomUUID` which would basically do the same thing as a light wrapper around database inserts. If a conflict occurred, it would generate a new ID and try again, up to 5 times I think. No logging to indicate whether any conflict actually ever happened.

No that kind of critical data would be sent to pendo so it could be reported on or shown in a dashboard!

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

#289

Post by susam »

ms_menardi wrote: post #284
greiskul wrote: post #233

Earlier quoted context omitted.

> you can never have too many sources of entropy This is so true. And the beauty is that with algorithms, we don't even need to know much about the entropy to be able to extract it. There is the Von Neumann method of generating an unbiased coin from a biased coin. Of throwing it twice, and checking if you got HT or TH. And completely discarding all HH or TT results. It doesn't matter if the coin you are using is 20%…

> There is the Von Neumann method of generating an unbiased coin from a biased coin. Of throwing it twice, and checking if you got HT or TH. And completely discarding all HH or TT results. It doesn't matter if the coin you are using is 20% or 80%, the result will be a true 50/50. This blew my mind. Thank you! I had to think about it a bit, so for anyone scratching their head right now trying to figure it out, conside…

And for people who like equations, here is my attempt at explaining it.

Assume each flip is independent and the bias remains same in each flip.

Let

  P(H) = p,
  P(T) = 1 - p.
Then

  P(HH) = p^2,
  P(HT) = p(1 - p),
  P(TH) = (1 - p)p,
  P(TT) = (1 - p)^2.
Therefore

  P(HT or TH) = 2p(1 - p).
Now calculate

  P(HT | HT or TH) = p(1 - p) / (2p(1 - p)) = 1/2,
  P(TH | HT or TH) = (1 - p)p / (2p(1 - p)) = 1/2.

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

#290

Post by taegee »

ms_menardi wrote: post #284
greiskul wrote: post #233

Earlier quoted context omitted.

> you can never have too many sources of entropy This is so true. And the beauty is that with algorithms, we don't even need to know much about the entropy to be able to extract it. There is the Von Neumann method of generating an unbiased coin from a biased coin. Of throwing it twice, and checking if you got HT or TH. And completely discarding all HH or TT results. It doesn't matter if the coin you are using is 20%…

> There is the Von Neumann method of generating an unbiased coin from a biased coin. Of throwing it twice, and checking if you got HT or TH. And completely discarding all HH or TT results. It doesn't matter if the coin you are using is 20% or 80%, the result will be a true 50/50. This blew my mind. Thank you! I had to think about it a bit, so for anyone scratching their head right now trying to figure it out, conside…

Afaics it's just basic commutativity – p(H)p(T) = p(T)p(H) – since instances are independent.

Same, of course, holds for flipping it multiple times. But there you get more than Head or Tail (binomnk(n, k)).

Post reply on HN