1
$\begingroup$

I want to use a PRNG to generate random patterns. I would provide the PRNG with a hash value as a seed. Ideally, the seed size would be 64-bit or 128-bit and I would expect no collisions if the seeds are unique.

Do PRNGs encounter 'collisions', where two different seeds produce the exact same sequence of random numbers?

For example, if one initializes a PRNG with all possible 32-bit, 64-bit or 128-bit numbers, one would expect zero collisions since all seeds would be different.

When considering a Linear congruential generator, the seed gets divided into a multiplier. Since a Lehmer LCG uses a multiplier of 231-1, supplying a random 32-bit hash would cause collisions, since it is dividing all possible 32-bit numbers into 231-1 numbers. Thus, a seed of 1, 232-1 and 231 are equivalent and produce the same sequence of numbers. This is a problem since I am expecting the collision resistance of 64 or 128-bit hashes in the PRNG.

For more complicated algorithms, it's not as simple to determine these cases. My language of choice is JavaScript, which has no built-in seeded PRNG. There are of course many options to remedy this in the sense of libraries or standalone functions.

The best/fastest available PRNG for JavaScript seems to be Alea. It has a JS and C implementation and is based on Marsaglia's MWC algorithm. The JS implementation takes a variable string seed, so it is not clear how many unique seeds are possible. Alea is described as having a period length of 2116, which if I understand correctly, would mean it utilizes up to 116 bits of a supplied seed (e.g. a 128-bit hash).

Basically what I am asking is, how would I determine if seeds collide in a PRNG? Is it based on the described period length?

A good illustration of the issue is to compare Jenkin's small PRNG (2007) with xoshiro128+ (2018). They are quite similar. They both use 32-bit arithmetic, store the state in a 128-bit array composed of four uint32's and return one uint32 as the result. The main difference is that Jenkins only uses a 32-bit seed that is repeated in b,c,d. While in xoshiro128+ the entire initial state is the seed. Thus I can supply a 128-bit hash to the latter as the seed and still benefit from the quality of the generator (without modifying the algorithm). That is essentially what I mean - being able to provide a very large seed.

As a workaround to this potential issue, I thought about simply using the hash function itself, and running further iterations of the mixing function to obtain new pseudo-random bits (in the same way as obtaining a new number in a PRNG). It is deterministic and appears random enough, but it seems unlikely that hash function outputs pass "statistical randomness tests" such as Diehard or BigCrush since it was not designed as a PRNG.

Also, there are no cryptographic requirements here. The hash function I would use would be MurmurHash3 or similar--anything good enough to pass SMHasher suite of tests and produces 64-bit or 128-bit hashes.

$\endgroup$
1
$\begingroup$

I think I understood your concern. So, the period length cannot be larger than the number of internal states. I.e. if internal state is 128 bits, then period cannot be larger than 2^128. Moreover, good PRNG try to implement longest possible period for given state size, f.e. 2^128-1 for 128-bit state.

Next point is that you can seed PRNG by directly assigning values to the internal state, except that you need to fulfill some requirements. In particular, http://xoshiro.di.unimi.it/ PRNGs can be initialized with any non-zero state. It's guaranteed that state will go through all other non-zero values before repeating the initial state (because each their PRNG with N-bit state has period of 2^N-1).

If last statement isn't clear enough, imagine PRNG with N bits of state and period of 2^N. Since there are exactly 2^N possible internal states, on order to have such large period, the PRNG has to ensure that state will go through all possible values before repeating the initial state.

All http://xoshiro.di.unimi.it/ PRNGs maps zero state to itself. So, in order to provide 2^N-1 period, they have to go through all non-zero states before repeating the state.

Now, if you have a PRNG with period of 2^116, it doesn't necessarily mean that it has only 116 bits of internal state. It may have f.e. 128 state bits, but all possible states are split into 2^12 groups, each containing 2^116 members. Inside each group, values are cycled, so we have a cycle (PRNG period) of 2^116 items. And remaining 12 bits essentially choose one of these groups. It's not strictly necessary, but what we can expect from a reasonable PRNG. Alternatively, bad PRNG may have just a single cycle of 2^116 values, and all other values converged to this cycle after a few steps.

Now, concrete answer to your question is that the seed collision probability is AT LEAST equal to MINIMUM of seed space and PRNG period, or in more strict math terms:

P <= 1/min(2^seed_bits, PRNG_period)

(at least if each seed value maps to different internal state). But as you see, larger period means less independent cycle groups. Ans if period is (almost) equal to the internal state space, then each state is just a point in the one and only cycle.

So, yeah, in particular all own http://xoshiro.di.unimi.it/ PRNGs produce exact the same sequence of numbers and seed/state choose only the initial point in this sequence.

How you can live with it? If you plan to start less than 2^32 sequences, and request less than 2^32 numbers in each one, there are very good chances that you will never encounter overlap. If you need more - just choose PRNG with 256-bit (or longer) state.

$\endgroup$
  • $\begingroup$ That helps a bit, but I am still confused, so let me get to the point: Will all 2^128-1 unique(nonzero) initial states of xoshiro128 return a 100% unique sequence (full period)? That is, unless the seed collides, the PRNG output cannot collide? I suppose what I am truly asking is: "How many total unique sequences can a PNRG produce given a seed", rather than a probability of collision. $\endgroup$ – bryc Aug 20 '18 at 0:06
  • $\begingroup$ xoshiro128 seems potentially good for my purpose as it is short, 32-bit and takes 128-bit seed (entire state) so I can use 128bit hash. if you look at Jenkins smallprng, it has 128-bit state but only 32-bit seed. $\endgroup$ – bryc Aug 20 '18 at 0:07
  • $\begingroup$ I think you can't get the last detail. Let's see - there exactly 2^128 variants of 128-bit state. Since zero state maps to itself, we exclude it and left with 2^128-1 non-zero states. When this PRNG claims 2^128-1 period, this means that starting from any (non-zero) state, you will go through ALL the other states before you will return to the initial one!!! So, there is only one and only one sequence, but it has maximum length possible for PRNG with 128-bit state (minus one). Your seed just puts you on some randomly-chosen point in the sequence, but the sequence is only one. $\endgroup$ – Bulat Aug 20 '18 at 8:22
  • $\begingroup$ May be the point that you are missing is that current state fully determines remainder of PRNG sequence. So if PRNG with 128-bit state has period of 2^128, this means that starting from any state, it goes through all the remaining ones before going to the initial state, and this means that ANY state is just different starting point on the same sequence. So, seeds in XO(RO)SHIRO family doesn't choose sequences, they only select starting points in one sequence determined to this particular PRNG. But since periods are so large, your probably have very low chances of overlaps. $\endgroup$ – Bulat Aug 20 '18 at 8:30
  • $\begingroup$ I don't recommend to use smallprng because it was developed by practical programmer rather than scientist, and it doesn't make strong guarantees (only "there is no guaranteed minimum cycle length, the average cycle length is expected to be about 2^126 results"), and because it's a bit outdated. Today DieHard is pretty weak PRNG test, alrhough it still should suffice for most real usecases. Anyway, PRNGs constructed by scientists look for me much more robust approach. Look into any member of en.wikipedia.org/wiki/Xorshift family, or into pcg-random.org family $\endgroup$ – Bulat Aug 20 '18 at 10:08
1
$\begingroup$

It depends on the PRNG. But it doesn't matter in practice. As long as the probability of collisions is low enough, who cares? These are pseudorandom numbers, so no one ever claimed they are perfect (exactly uniformly distributed); at best they are indistinguishable from random by any procedure that uses a limited amount of computing power.

$\endgroup$
  • $\begingroup$ It does matter. I can use a PRNG to generate 256 bits of random data but if the PRNG's seed is 31 bits (such as in an Lehmer LCG) only a small fraction of the possible outcomes can be accessed. If I generate a 128-bit random seed, I want all those bits incorporated in the PRNG and that collisions only occur when the seed itself collides! $\endgroup$ – bryc Aug 18 '18 at 1:42
  • $\begingroup$ The issue is, collision probabilities grow exponentially the more times you run the random generation (birthday problem). 128-bit hashes for example have "low enough" probabilities, but this can be a problem when a PRNG only uses 32/31 bits in a seed such as LCG, or if for some reason two different seeds produce the same sequence. $\endgroup$ – bryc Aug 18 '18 at 2:09
  • $\begingroup$ @bryc, right, but (1) in that case the collision probability is not low enough, and (2) in any case the real problem is not the possibility of collisions; the problem is a much more fundamental one (e.g., that the set of possible outputs is too small). Focusing on collisions is focusing on just one thing that can go wrong, but on the list of things that are likely to go wrong, it's pretty far down the list, compared to a lot of other possibilities. $\endgroup$ – D.W. Aug 18 '18 at 4:52
  • $\begingroup$ The second comment does not appear to be a correct summary of the relevance of the birthday paradox here. $\endgroup$ – D.W. Aug 18 '18 at 4:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.