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

From: Jos Hickson (jos.hickson_at_[hidden])
Date: 2007-06-05 09:00:36

On 05/06/07, Peter Dimov <pdimov_at_[hidden]> wrote:
> 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".
>

Understood.  However, if the best implementation of uuid::create()
depends on which of two usage patterns is assumed ("batch" or "one per
program") maybe a better approach is to have both uuid_generator (for
batch purposes) and uuid::create() (for the one-per-program usage)
with the generator seeded using the randomness that uuid::create()
uses.

Jos