Re: [boost] [uuid] uuid::create() function

From: Peter Dimov (pdimov_at_[hidden])
Date: 2007-06-05 07:23:54

Jos Hickson wrote:
> On 04/06/07, Andy <atompkins_at_[hidden]> wrote:
>> I am favoring number 4, unless it will not produce good uuids.  Then
>> I favor number 5.
>>
>> I guess I am looking for direction as to how to proceed.
>>
>> Andy.
>
> I prefer number 5.  All you need do then is provide a get_seed()
> method that generates a decent seed; with number 4 it might well take
> a lot more time to implement and test a good source of random numbers
> and then it might add a extra dimension to maintaining the library.
> It seems to me that Boost.Random exists then it should be used by
> default as the source of random number generators unless, of course,
> what it provides is not good enough but I presume that is not the
> case.

Number 5 is a good solution for batch UUID generation, assuming that the RNG 
is seeded well.

That said, I should note that a RNG is not really a source of randomness. 
Sure, it can be used to produce a sequence that appears sufficiently random 
for most computing purposes. For UUID generation, however, and specifically 
in the "one UUID per program" case, a RNG contributes exactly zero random 
bits. If you have a seed that contains K bits of entropy, and you generate 
from that seed an UUID by using a RNG, the UUID will contain exactly K bits 
of entropy. To put it differently, the probability that two seeds collide - 
2^-K - is equal to the probability that two UUIDs collide, because equal 
seeds generate equal UUIDs.

In other words, if you have a "decent" 32 bit seed, you're looking at 2^-32 
probability of collisions, no matter how many RNGs you use as an 
intermediate layer. If you have a decent 128 bit seed, you can use it as an 
UUID as is, and passing it through a RNG will not change anything. And 
conversely, if you don't have a good source of randomness to use as a seed, 
you will not be able to generate a good UUID, so it's not possible to 
eliminate the "extra dimension".