Implausible Output from Xoshiro256**
It's now been a week since David Blackman and Sebastiano Vigna
announced new members of the Xoroshiro family. Although I have been busy with a number of other matters, I recognize that interest in these new PRNGs is likely to be high right now, so I have managed to grab a few stolen moments here and there to take a look at their new work. I plan to write a longer post soon, but my preliminary investigations have turned up enough surprising things that I feel like it's worth sharing some of my discoveries. As with my previous post on these matters, I'll focus in on their best PRNG, xoshiro256**.
Perspective
Before we dive in, let's get a little perspective.
Blackman & Vigna claim that these new PRNGs are better than their prior work, and I think it's reasonable to believe their claim. Many people have used their prior generators successfully for years, even though they failed statistical tests. Vigna has often asserted that these failures were overly technical and esoteric, and rarely a problem in practice.
And in a lot of ways that's true—in practice, the given way most people use random-number generators, even far worse designs that fail many more tests rarely cause problems for their users.
Thus, on the one hand, the flaws we'll see in xoshiro256**, their best PRNG so far, absolutely do not render it unusable in practice—far from it. But if being good means avoiding statistical flaws, then we'll see more evidence that we might want to prefer to use a different PRNG.
Regardless of the quality of xoshiro256**, Blackman & Vigna's paper is very nicely written and shows a genuine attempt to develop a better mathematical understanding of the techniques they applied. In the world of random number generation, we have often discovered that while sophisticated mathematics is often useful, practical testing often reveals aspects that mathematical approaches can't capture. Thus the kind of empiricism I'll apply in this post has merit, too.
The Curious Case of the Duplicates in the Output
It was a dark and stormy night, when there came a knock at the door. A shadowy figure handed me an envelope, saying “Five by five, will it survive? Here be the five seeds to xoshiro256**'s soul”. It seemed quite enigmatic, so of course I had to check them out! (I may have embellished the origin these seeds a little for dramatic effect.)
When I used these seeds, I got random output as I would expect, but after about 128 outputs I noticed something worrying. Take a look for yourself and see if you can see anything strange (to save space, I've skipped the first 120 outputs from each seed).
unix% ./xoshiro256 0x1a3e1765f0739e39 0xf5d7f1bb420e645d 0x16a5269645b3a76f 0xbb126a5fd07a5f1e | od -j 960 -w32 -A x2 -t x8 | head -5
s[4] = { 0x1a3e1765f0739e39, 0xf5d7f1bb420e645d, 0x16a5269645b3a76f, 0xbb126a5fd07a5f1e };
0003c0 c1daba3cc9db5126 9f01294e37dc5ffc 75fcfca7517f335e 80412240796077e4
0003e0 bf18dec850198308 bf18dec850198308 702a3a01c2a02bb9 170c579770939f5b
000400 93bffd6f18a94a36 bf18dec850198308 aacf836720fc2d30 a922cb95b771a67f
000420 bf18dec850198308 bf18dec850198308 d853aa3f2405f8ca a45a79879e4d5551
000440 474e1ce520933ba3 fd251c72f17c8fc7 cb7c5277edd708f8 a8c3126a562de41c
unix% ./xoshiro256 0x2cd27cf254bccc02 0xe32d978237f9e7d8 0x89e65a801e762da3 0xf7b1bcf1bd9f1fec | od -j 960 -w32 -A x2 -t x8 | head -5
s[4] = { 0x2cd27cf254bccc02, 0xe32d978237f9e7d8, 0x89e65a801e762da3, 0xf7b1bcf1bd9f1fec };
0003c0 965e4db3c5acada0 a81236c787799a0b 137929c7a02ce684 c42282933c41de3d
0003e0 3f9c28ac60c45d50 3f9c28ac60c45d50 88f8d900e3f74131 43cbe367e3ae5a92
000400 b90ff20f000eda9b 3f9c28ac60c45d50 835803f769f74170 3f9c28ac60c45d50
000420 3f9c28ac60c45d50 5247843719603ee5 32a7c4eb3945138e 5a4cbe9326459d8f
000440 cd4e2fbcf1b01e81 b7ba05bebd2d38b8 50c81951ce863a3d 5a470ee2dbde75d7
unix% ./xoshiro256 0x6bb8c49b95f9d8d5 0x957355fd426a8e86 0x8c4c14a24fbe215a 0x05a2cf7d898f2ca2 | od -j 960 -w32 -A x2 -t x8 | head -5
s[4] = { 0x6bb8c49b95f9d8d5, 0x957355fd426a8e86, 0x8c4c14a24fbe215a, 0x05a2cf7d898f2ca2 };
0003c0 37c2012a526242ba 7e8642bffd132b88 328b89d55ae0dda8 14aed70596bfb48f
0003e0 3940df181b63839a e2709d36ef5ff440 3630acfada035e57 3630acfada035e57
000400 99fd7f05ff035bd8 442e8c752ccdb2e5 8f19a07c963d072f 3630acfada035e57
000420 3630acfada035e57 3630acfada035e57 3623706d63065f80 0039a361450d513c
000440 f5eec6492b053c10 8c3e2764b56ec3f4 fac83742843867bf 28e8950aa0b33b33
unix% ./xoshiro256 0x0bd1a168fbe67d09 0xf22e4a79c4068f55 0x676fb8772a598833 0x3e1f00f6d50de9c3 | od -j 960 -w32 -A x2 -t x8 | head -5
s[4] = { 0x0bd1a168fbe67d09, 0xf22e4a79c4068f55, 0x676fb8772a598833, 0x3e1f00f6d50de9c3 };
0003c0 52c90a038ef14bca bc88a4014a1036f3 4570286618dbaab1 858c4cfeb305582a
0003e0 b9374f8d19e27768 00442f17f0713b13 c7210eef15157108 b9374f8d19e27768
000400 b9374f8d19e27768 e1aa2b8fa5b0f052 8815699b01da0fe7 b9374f8d19e27768
000420 b9374f8d19e27768 ee8140ff4c3d7123 83bc5a7cde624d0e 501bf1e4fbea9783
000440 0832df4b967c28b1 ec2b11c3aa8dbd06 af5457bfc05b1f38 43f363c7a2acce81
unix% ./xoshiro256 0x216b13fa05d2c01e 0x0165f953d45afc83 0x7557a4909bdae724 0x10718ed2c884dc75 | od -j 960 -w32 -A x2 -t x8 | head -5
s[4] = { 0x216b13fa05d2c01e, 0x0165f953d45afc83, 0x7557a4909bdae724, 0x10718ed2c884dc75 };
0003c0 e49a7c3c6d54f92b 47e5b086300bc9d9 eb034bac186bf4b9 4338b6de0698abb3
0003e0 bd6d5f17f54603b1 7f589ea14c5180ac f1ece002a3004704 f1ece002a3004704
000400 021c000087000360 c21c00008700001b f1ece002a3004704 f1ece002a3004704
000420 f1ece002a3004704 09717dfaa30046e0 f840e14563bf0024 dda57f4c23289df4
000440 1306bcb4072a3318 a1748ac586430e21 54eb736d115bf79d 2ec7fa2d3e2f72eb
What you should see in each of these examples is a repeated number. In each case the number is repeated five times. For example, in the last case it outputs 0xf1ece002a3004704 over the course of seven outputs (and the other two outputs are 0x021c000087000360 and 0xc21c00008700001b, which are disturbingly similar). The other cases are similar; in the first example, we repeat 0xbf18dec850198308 five times over the space of ten outputs.
Repeats certainly seem odd, but they aren't automatically bad. For example, if we saw 0x1234567887654321 repeated four times in a row, that would feel very unlikely, because the chance of seeing that output is 2-256, but in a generator with period 2256, it's perfectly reasonable to see this output once, (or even a few times!).
But what about these examples? For now I'll just leave the question with you to ponder: just how many nearby five-repeats is reasonable to expect over the full period of this generator?
In an upcoming post, I'll elaborate on these themes and show that the structure of xoshiro256** is in fact wildly improbable due to faulty nearby-repeat behavior.
Conclusion
This post reminds me of the adage about finding a needle in a haystack. In this case, it's five improbably sharp needles (these outputs) in a beyond–astronomically-sized haystack (the full period of xoshiro256**).
From a practical standpoint we might be able to say that even if there are flaws, they don't matter—with so much hay, the needles aren't likely to be something you'll typically stumble upon.
As I've argued previously, large state space is often enough to successfully mask structural flaws. After all, even Jon von Neumann's ancient and much derided middle-square algorithm passes stringent statistical tests once the size reaches 128 bits.
So we could argue that once we get to 256-bits, it doesn't matter if xoshiro256**'s state space has problems; it probably won't cause anyone any problems in practice.
But I don't like what I've found. The five examples I chose for this post were just a few of many—in reality, a rather large box of needles has been emptied into this particular haystack.