Pseudo-random generator statistical tests

[sisyphusSmiling]

Closes: #3

Introduces statistical tests for the xorshift128+ implementation in PseudoRandomGenerator contract, asserting a uniform distribution across a sample of UInt64 random results.

[sisyphusSmiling]

@joshuahannan Agreed, I'll build out tests for the other contracts & their scripts using the Cadence testing framework. The PRG test needs to be done a non-Cadence framework since we need to run an analysis on the statistical distribution of random numbers returned from the PRG. Go is preferable here given the supporting BasicDistributionTest() method in flow-go and was raised by @tarakby in #3

[joshuahannan]

Are we able to use overflow though? that is much better design framework than my tests

[sisyphusSmiling]

I'd imagine so. I'm not familiar with it, but can look into it for the test setup & execution. Better for me to familiarize myself with it since it's been mentioned as a powerful tool.

[sisyphusSmiling]

Quick update: the PRG stat tests now use overflow as suggested by @joshuahannan. Since overflow pulls the contract config from local flow.json, I've moved the test & its helper to the root dir where the project's flow.json is located. And since we're using overflow, we no longer need the contract bindata or templates, so the lib/go/ directory containing both contracts/ and templates/ has been removed.

Once this PR is done and merged, I can move on to building out Cadence unit tests.

[tarakby]

Looking at this PR shortly, apologies for the delay

[sisyphusSmiling]

Quick update - PR should be ready for another round of reviews. Some notes on changes:

• PRG implementation has been updated with changes from #6
• PRG initialization had a bug created during previous refactor and has been corrected after discovery while testing
• Generating sufficient quantity of random numbers for BasicDistributionTest required persisting PRG state across a number of transactions (due to computational limits) and recording generated random numbers. In order to do this, I introduced a simple helper contract for this express purpose - RandomResultStorage. As suggested by @tarakby in this comment, I first generated the numbers, then query the contract to retrieve the generated results - both steps done in batches to prevent reaching computational limits. These results are then passed to BasicDistributionTest to assess uniformity of distribution
• Two additional test cases have been added, covering alternate random results from same seed + different salts and different seeds + same salt

Note that the sample size assignment in the result distribution test had to be hardcoded due to its calculation in BasicDistributionTest. This is not ideal as it creates a fragile test, breaking if/when the sample size constants are updated in crypto/random/rand_utils. Open to suggestions on making this more robust.

[tarakby]

My last comment is about the repo structure and whether developers can be confused about what’s a test, example and production code. For instance /contracts contains 2 production contracts (history + xorshift) and 1 example (cointoss). Same for /transaction where there are also test transactions. I’m wondering if it’s better to have a /test subfolder and /example subfolder under /contracts , /transactions and /scripts , or another way to clear the possible confusion.

[sisyphusSmiling]

Thank you @tarakby!

My last comment is about the repo structure and whether developers can be confused about what’s a test, example and production code. For instance /contracts contains 2 production contracts (history + xorshift) and 1 example (cointoss). Same for /transaction where there are also test transactions. I’m wondering if it’s better to have a /test subfolder and /example subfolder under /contracts , /transactions and /scripts , or another way to clear the possible confusion.

Good point. Just to make sure main is updated ASAP, I'll merge PR as-is and create a fast-follow PR with a directory restructure.