PRG implementation testing

[sisyphusSmiling]

Description

Proper PRG implementation tests should validate uniform distributions for a large number of random results. This means Cadence test framework will not be sufficient.

Two often recommended PRG tests are chi-square and Kolmogorov-Smirnov, both of which have implementations in scipy.

• scipy.stats.chisquare
• scipy.stats.ktest

While not prescriptive, these are two starting points for the development of statistical analysis tests that can be leveraged in validating PRG implementation.

References

• Testing Random Number Generators - Dr. John Mellor-Crummey

[sisyphusSmiling]

@tarakby do you think this level of PRG testing is necessary and/or sufficient?

[tarakby]

Thanks @sisyphusSmiling for looking up the tests!

These are good tests indeed. There are other known battery of tests that are applied to evaluate a source of randomness. For instance NIST's test suite and TestU01 that includes Big Crush test. They take some time to implement and also take time to run, making them not suitable for CI tests.

These tests are necessary for a TRNG (like a hardware one) that claim to provide good quality randomness, or for new PRNG designs. For existing and known PRNG designs (like our contract case), tests are not meant to evaluate the statistical quality of the design. Other studies have already looked at the PRG and we pick a design that is known to provide acceptable quality. The tests in our case should rather make sure that our implementation matches the design and doesn't have obvious bugs. Some designs provide test vectors that implementations can check. For Xorshift128+, I didn't find a test vector in the original paper or other "official" source. But since the algorithm looks simple enough, we could implement simple sanity checks of a uniform distribution (instead of deep statistical tests).

In flow-go, I used a simple standard deviation test. Feel free to re-use the tools there (they are used in several parts of the repo). Chi-Square is a also simple enough to be implemented for a sanity check, so feel free to extend the tools if you prefer Chi-square over standard deviation.