Merge #14624: Some simple improvements to the RNG code

e414486d56b9f06af7aeb07ce13e3c3780c2b69b Do not permit copying FastRandomContexts (Pieter Wuille)
022cf47dd7ef8f46e32a184e84f94d1e9f3a495c Simplify testing RNG code (Pieter Wuille)
fd3e7973ffaaa15ed32e5aeadcb02956849b8fc7 Make unit tests use the insecure_rand_ctx exclusively (Pieter Wuille)
8d98d426116f0178612f14d1874d331042c4c4b7 Bugfix: randbytes should seed when needed (non reachable issue) (Pieter Wuille)
273d02580aa736b7ccea8fce51d90541665fdbd1 Use a FastRandomContext in LimitOrphanTxSize (Pieter Wuille)
3db746beb407f7cdd9cd6a605a195bef1254b4c0 Introduce a Shuffle for FastRandomContext and use it in wallet and coinselection (Pieter Wuille)
8098379be5465f598220e1d6174fc57c56f9da42 Use a local FastRandomContext in a few more places in net (Pieter Wuille)
9695f31d7544778853aa373f0aeed629fa68d85e Make addrman use its local RNG exclusively (Pieter Wuille)

Pull request description:

  This improves a few minor issues with the RNG code:
  * Avoid calling `GetRand*()` functions (which currently invoke OpenSSL, later may switch to using our own RNG pool) inside loops in addrman, networking code, `KnapsackSolver`, and `LimitOrphanSize`
  * Fix a currently unreachable bug in `FastRandomContext::randbytes`.
  * Make a number of simplifications to the unit tests' randomness code (some tests unnecessarily used their own RNG or the OpenSSL one, instead of using the unit test specific `insecure_rand_ctx`).
  * As a precaution, make it illegal to copy a `FastRandomContext`.

Tree-SHA512: 084c70b533ea68ca7adc0186c39f0b3e0a5c0ae43a12c37286e5d42086e056a8cd026dde61b12c0a296dc80f87fdc87fe303b9e8e6161b460ac2086cf7615f9d

1 files changed, 46 insertions, 5 deletions

diff --git a/src/test/random_tests.cpp b/src/test/random_tests.cpp
index 679e857ce6..1057d09471 100644
--- a/src/test/random_tests.cpp
+++ b/src/test/random_tests.cpp
@@ -38,11 +38,18 @@ BOOST_AUTO_TEST_CASE(fastrandom_tests)
     BOOST_CHECK(ctx1.randbytes(50) == ctx2.randbytes(50));
 
     // Check that a nondeterministic ones are not
-    FastRandomContext ctx3;
-    FastRandomContext ctx4;
-    BOOST_CHECK(ctx3.rand64() != ctx4.rand64()); // extremely unlikely to be equal
-    BOOST_CHECK(ctx3.rand256() != ctx4.rand256());
-    BOOST_CHECK(ctx3.randbytes(7) != ctx4.randbytes(7));
+    {
+        FastRandomContext ctx3, ctx4;
+        BOOST_CHECK(ctx3.rand64() != ctx4.rand64()); // extremely unlikely to be equal
+    }
+    {
+        FastRandomContext ctx3, ctx4;
+        BOOST_CHECK(ctx3.rand256() != ctx4.rand256());
+    }
+    {
+        FastRandomContext ctx3, ctx4;
+        BOOST_CHECK(ctx3.randbytes(7) != ctx4.randbytes(7));
+    }
 }
 
 BOOST_AUTO_TEST_CASE(fastrandom_randbits)
@@ -75,8 +82,42 @@ BOOST_AUTO_TEST_CASE(stdrandom_test)
         for (int j = 1; j <= 10; ++j) {
             BOOST_CHECK(std::find(test.begin(), test.end(), j) != test.end());
         }
+        Shuffle(test.begin(), test.end(), ctx);
+        for (int j = 1; j <= 10; ++j) {
+            BOOST_CHECK(std::find(test.begin(), test.end(), j) != test.end());
+        }
     }
 
 }
 
+/** Test that Shuffle reaches every permutation with equal probability. */
+BOOST_AUTO_TEST_CASE(shuffle_stat_test)
+{
+    FastRandomContext ctx(true);
+    uint32_t counts[5 * 5 * 5 * 5 * 5] = {0};
+    for (int i = 0; i < 12000; ++i) {
+        int data[5] = {0, 1, 2, 3, 4};
+        Shuffle(std::begin(data), std::end(data), ctx);
+        int pos = data[0] + data[1] * 5 + data[2] * 25 + data[3] * 125 + data[4] * 625;
+        ++counts[pos];
+    }
+    unsigned int sum = 0;
+    double chi_score = 0.0;
+    for (int i = 0; i < 5 * 5 * 5 * 5 * 5; ++i) {
+        int i1 = i % 5, i2 = (i / 5) % 5, i3 = (i / 25) % 5, i4 = (i / 125) % 5, i5 = i / 625;
+        uint32_t count = counts[i];
+        if (i1 == i2 || i1 == i3 || i1 == i4 || i1 == i5 || i2 == i3 || i2 == i4 || i2 == i5 || i3 == i4 || i3 == i5 || i4 == i5) {
+            BOOST_CHECK(count == 0);
+        } else {
+            chi_score += ((count - 100.0) * (count - 100.0)) / 100.0;
+            BOOST_CHECK(count > 50);
+            BOOST_CHECK(count < 150);
+            sum += count;
+        }
+    }
+    BOOST_CHECK(chi_score > 58.1411); // 99.9999% confidence interval
+    BOOST_CHECK(chi_score < 210.275);
+    BOOST_CHECK_EQUAL(sum, 12000);
+}
+
 BOOST_AUTO_TEST_SUITE_END()