Fabulous Adventures In Coding
Eric Lippert is a principal developer on the C# compiler team. Learn more about Eric.
Let's recap: a GUID is a 128 bit integer that is used as a globally unique identifier. GUIDs are not a security system; they do not guarantee uniqueness in a world where hostile parties are deliberately attempting to cause collisions; rather, they provide a cheap and easy way for mutually benign parties to generate identifiers without collisions. One mechanism for ensuring global uniqueness is to generate the GUID so that its bits describe a unique position in spacetime: a machine with a specific network card at a specific time. The downside of this mechanism is that code artifacts with GUIDs embedded in them contain easily-decoded information about the machine used to generate the GUID. This naturally raises a privacy concern.
To address this concern, there is a second common method for generating GUIDs, and that is to choose the bits at random. Such GUIDs have a 4 as the first hex digit of the third section.
First off, what bits are we talking about when we say "the bits"? We already know that in a "random" GUID the first hex digit of the third section is always 4. Something I did not mention in the last episode was that there is additional version information stored in the GUID in the bits in the fourth section as well; you'll note that a GUID almost always has 8, 9, a or b as the first hex digit of the fourth section. So in total we have six bits reserved for version information, leaving 122 bits that can be chosen at random.
Second, why should we suppose that choosing a number at random produces uniqueness? Flipping a coin is random, but it certain does not produce a unique result! What we rely on here is probabilistic uniqueness. Flipping a single coin does not produce a unique result, but flipping the same coin 122 times in a row almost certainly produces a sequence of heads and tails that has never been seen before and will never be seen again.
Let's talk a bit about those probabilities. Suppose you have a particular randomly-generated GUID in hand. What is the probability that a specific time that you randomly generate another GUID will produce a collision with your particular GUID? If the bits are chosen randomly and uniformly, clearly the probability of collision is one in 2122. Now, what is the probability that over n generations of GUIDs, you produce a collision with your particular GUID? Those are independent rare events, so the probabilities add (*); the probability of a collision is n in 2122. This 2122 is an astonishingly large number.
There are on the order 230 personal computers in the world (and of course lots of hand-held devices or non-PC computing devices that have more or less the same levels of computing power, but lets ignore those). Let's assume that we put all those PCs in the world to the task of generating GUIDs; if each one can generate, say, 220 GUIDs per second then after only about 272 seconds -- one hundred and fifty trillion years -- you'll have a very high chance of generating a collision with your specific GUID. And the odds of collision get pretty good after only thirty trillion years.
But that's looking for a collision with a specific GUID. Clearly the chances are a lot better of generating a collision somewhere else along the way. Recall that a couple of years ago I analyzed how often you get any collision when generating random 32 bit numbers; it turns out that the probability of getting any collision gets extremely high when you get to around 216 numbers generated. This generalizes; as a rule of thumb, the probability of getting a collision when generating a random n bit number gets large when you've generated around 2n/2 numbers. So if we put those billion PCs to work generating 122-bits-of-randomness GUIDs, the probability that two of them somewhere in there would collide gets really high after about 261 GUIDs are generated. Since we're assuming that about 230 machines are doing 220 GUIDs per second, we'd expect a collision after about 211 seconds, which is about an hour.
So clearly this system is not utterly foolproof; if we really, really wanted to, we could with high probability generate a GUID collision in only an hour, provided that we got every PC on the planet to dedicate an hour of time to doing so.
But of course we are not going to do that. The number of GUIDs generated per second worldwide is not anywhere even close to 250! I would be surprised if it were more than 220 GUIDs generated per second, worldwide, and therefore we could expect to wait about 241 seconds, for there to be a reasonable chance of collision, which is about seventy thousand years. And if we are looking for a collision with a specific GUID, then again, it will take about a billion times longer than our initial estimate if we assume that a relatively small number of GUIDs are being generated worldwide per second.
So, in short: you should expect that any particular random GUID will have a collision some time in the next thirty billion trillion years, and that there should be a collision between any two GUIDs some time in the next seventy thousand years.
Those are pretty good odds.
Now, this is assuming that the GUIDs are chosen by a perfectly uniform random process. They are not. GUIDs are in practice generated by a high-quality pseudo-random number generator, not by a crypto-strength random number generator. Here are some questions that I do not know the answers to:
I do not know the answers to any of these questions, and therefore it is wise for me to assume that the answers to the bottom four questions is "yes". Clearly it is far, far more difficult for someone to work out where and when a version-four GUID was create than a version-one GUID, which has that information directly in the GUID itself. But I do not know that it is impossible.
There are yet other techniques for generating GUIDs. If there is a 2 in the first hex digit of the third section then it is a version 1 GUID with some of the timestamp bits have slightly different meanings. If there is a 3 or 5 then the bits are created by running a cryptographic hash function over a unique string; the uniqueness of the string is then derived from the fact that it is typically a URL. But rather than go into the details of those more exotic GUIDs, I think I will leave off here.
(*) As the comments point out, this is an approximation that only holds if the probability is small and n is relatively small compared to the total number of possible outcomes.
Apologies if this is duplicated; I'm not sure whether my previous comment has been lost due to non-posting or moderation.
"Now, what is the probability that over n generations of GUIDs, you produce a collision with your particular GUID? Those are independent events, so the probabilities add; the probability of a collision is n in 2122."
Probabilities of independent events do not add. The probability of getting a head on either of two independent coin tosses is not (1/2 + 1/2 = 1).
You are correct; I should have called out that I was making an approximation that holds for rare events. I'll update the text. -- Eric
I'm curious what is probability of a GUID collision if you run two and more separate threads that generates guid sequences? Is algorithms use thread Id or anything like that?
And is there any way to choose what algorithm will be used when I call Guid.NewGuid() ?
Yes, I noticed the same as Dan T, but unfortunately the spam filter ate my calculations. :) The point is that independent probabilities can be multiplied and in this case the easier way is to multiply the possibilities of not having a collision. So it involve a lot of substraction from 1, but i'm afraid to write it down, because of the spam filter. :)
You're technically right. But for realistic sizes of n, it is a *very* good approximation. The error only becomes significant if you create more that 2^100 GUIDs, and that just doesn't happen.
It should be: 1 - n*(2^122 - 1)/2^122
The conclusion of the article is of course not ruined by this mistake, but i think the addition of independent probabilities is misleading to others who will read this post later.
@Brett: Nope, that'll be negative for n > 1. It should be 1 - ((2^122 - 1)/2^122)^n
@CodesInChaos: It _is_ a very good approximation, and I thank you for prompting me to think for a minute to work out why. Still, as Zsolt says, just saying "independent probabilities add" without qualification is not good.
A PRNG with insufficient internal state is a common problem. Consider that wherever you start with a PRNG will determine the entire sequence--the seed selects a starting point in the PRNG sequence which is limited in length by its internal state. If the PNRG has only 32 bits of state, then there are only about 4 billion GUIDs that it would ever generate.
Consider all those casual card games like Solitaire and Freecell. They typically can only shuffle the deck into one of only 2^32 arrangements. A true random shuffle yields something like 8 x 10^67 possible arrangements.
If one needs GUIDs that are securely random, one could implement an alternative to `NewGuid()` based on `RNGCryptoServiceProvider`. That's not very hard, and `RNGCryptoServiceProvider` produces good secure numbers, and you're guaranteed to get a V4 GUID. If high performance is required, you'll need to buffer the output of `RNGCryptoServiceProvider`, since it has a huge per-call overhead, whereas per-byte performance is actually pretty decent.
PRNGs with such a small internal state typically have horrible biases anyways. Luckily *that* mistake is falling a bit out of favor nowadays.
Unfortunately low quality *seeds* are still very common. .net's `System.Random` is one example of that. It has 2 billion different seeds at best. But in practice the situation is even worse than that, since `GetTickCount()` is biased towards small numbers on computers that don't run for weeks, and also only increments every few milliseconds. MS considers this flaw "by-design".