random_tests.cpp
1 // Copyright (c) 2017-present The Bitcoin Core developers 2 // Distributed under the MIT software license, see the accompanying 3 // file COPYING or http://www.opensource.org/licenses/mit-license.php. 4 5 #include <random.h> 6 7 #include <test/util/random.h> 8 #include <test/util/setup_common.h> 9 #include <util/time.h> 10 11 #include <boost/test/unit_test.hpp> 12 13 #include <algorithm> 14 #include <random> 15 16 BOOST_FIXTURE_TEST_SUITE(random_tests, BasicTestingSetup) 17 18 BOOST_AUTO_TEST_CASE(osrandom_tests) 19 { 20 BOOST_CHECK(Random_SanityCheck()); 21 } 22 23 BOOST_AUTO_TEST_CASE(fastrandom_tests_deterministic) 24 { 25 // Check that deterministic FastRandomContexts are deterministic 26 SeedRandomForTest(SeedRand::ZEROS); 27 FastRandomContext ctx1{true}; 28 FastRandomContext ctx2{true}; 29 30 { 31 BOOST_CHECK_EQUAL(FastRandomContext().rand<uint64_t>(), uint64_t{9330418229102544152u}); 32 BOOST_CHECK_EQUAL(FastRandomContext().rand<int>(), int{618925161}); 33 BOOST_CHECK_EQUAL(FastRandomContext().randrange<std::chrono::microseconds>(1h).count(), 1271170921); 34 BOOST_CHECK_EQUAL(FastRandomContext().randrange<std::chrono::milliseconds>(1h).count(), 2803534); 35 36 BOOST_CHECK_EQUAL(FastRandomContext().rand<uint64_t>(), uint64_t{10170981140880778086u}); 37 BOOST_CHECK_EQUAL(FastRandomContext().rand<int>(), int{1689082725}); 38 BOOST_CHECK_EQUAL(FastRandomContext().randrange<std::chrono::microseconds>(1h).count(), 2464643716); 39 BOOST_CHECK_EQUAL(FastRandomContext().randrange<std::chrono::milliseconds>(1h).count(), 2312205); 40 41 BOOST_CHECK_EQUAL(FastRandomContext().rand<uint64_t>(), uint64_t{5689404004456455543u}); 42 BOOST_CHECK_EQUAL(FastRandomContext().rand<int>(), int{785839937}); 43 BOOST_CHECK_EQUAL(FastRandomContext().randrange<std::chrono::microseconds>(1h).count(), 93558804); 44 BOOST_CHECK_EQUAL(FastRandomContext().randrange<std::chrono::milliseconds>(1h).count(), 507022); 45 } 46 47 { 48 constexpr SteadySeconds time_point{1s}; 49 FastRandomContext ctx{true}; 50 BOOST_CHECK_EQUAL(7, ctx.rand_uniform_delay(time_point, 9s).time_since_epoch().count()); 51 BOOST_CHECK_EQUAL(-6, ctx.rand_uniform_delay(time_point, -9s).time_since_epoch().count()); 52 BOOST_CHECK_EQUAL(1, ctx.rand_uniform_delay(time_point, 0s).time_since_epoch().count()); 53 BOOST_CHECK_EQUAL(4652286523065884857, ctx.rand_uniform_delay(time_point, 9223372036854775807s).time_since_epoch().count()); 54 BOOST_CHECK_EQUAL(-8813961240025683129, ctx.rand_uniform_delay(time_point, -9223372036854775807s).time_since_epoch().count()); 55 BOOST_CHECK_EQUAL(26443, ctx.rand_uniform_delay(time_point, 9h).time_since_epoch().count()); 56 } 57 BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32()); 58 BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32()); 59 BOOST_CHECK_EQUAL(ctx1.rand64(), ctx2.rand64()); 60 BOOST_CHECK_EQUAL(ctx1.randbits(3), ctx2.randbits(3)); 61 BOOST_CHECK(std::ranges::equal(ctx1.randbytes<std::byte>(17), ctx2.randbytes<17>())); // check vector/array behavior symmetry 62 BOOST_CHECK(ctx1.rand256() == ctx2.rand256()); 63 BOOST_CHECK_EQUAL(ctx1.randbits(7), ctx2.randbits(7)); 64 BOOST_CHECK(ctx1.randbytes(128) == ctx2.randbytes(128)); 65 BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32()); 66 BOOST_CHECK_EQUAL(ctx1.randbits(3), ctx2.randbits(3)); 67 BOOST_CHECK(ctx1.rand256() == ctx2.rand256()); 68 BOOST_CHECK(ctx1.randbytes(50) == ctx2.randbytes(50)); 69 { 70 struct MicroClock { 71 using duration = std::chrono::microseconds; 72 }; 73 FastRandomContext ctx{true}; 74 // Check with clock type 75 BOOST_CHECK_EQUAL(47222, ctx.rand_uniform_duration<MicroClock>(1s).count()); 76 // Check with time-point type 77 BOOST_CHECK_EQUAL(2782, ctx.rand_uniform_duration<SteadySeconds>(9h).count()); 78 } 79 } 80 81 BOOST_AUTO_TEST_CASE(fastrandom_tests_nondeterministic) 82 { 83 // Check that a nondeterministic ones are not 84 { 85 BOOST_CHECK(FastRandomContext().rand<uint64_t>() != uint64_t{9330418229102544152u}); 86 BOOST_CHECK(FastRandomContext().rand<int>() != int{618925161}); 87 BOOST_CHECK(FastRandomContext().randrange<std::chrono::microseconds>(1h).count() != 1271170921); 88 BOOST_CHECK(FastRandomContext().randrange<std::chrono::milliseconds>(1h).count() != 2803534); 89 90 BOOST_CHECK(FastRandomContext().rand<uint64_t>() != uint64_t{10170981140880778086u}); 91 BOOST_CHECK(FastRandomContext().rand<int>() != int{1689082725}); 92 BOOST_CHECK(FastRandomContext().randrange<std::chrono::microseconds>(1h).count() != 2464643716); 93 BOOST_CHECK(FastRandomContext().randrange<std::chrono::milliseconds>(1h).count() != 2312205); 94 95 BOOST_CHECK(FastRandomContext().rand<uint64_t>() != uint64_t{5689404004456455543u}); 96 BOOST_CHECK(FastRandomContext().rand<int>() != int{785839937}); 97 BOOST_CHECK(FastRandomContext().randrange<std::chrono::microseconds>(1h).count() != 93558804); 98 BOOST_CHECK(FastRandomContext().randrange<std::chrono::milliseconds>(1h).count() != 507022); 99 } 100 101 { 102 FastRandomContext ctx3, ctx4; 103 BOOST_CHECK(ctx3.rand64() != ctx4.rand64()); // extremely unlikely to be equal 104 } 105 { 106 FastRandomContext ctx3, ctx4; 107 BOOST_CHECK(ctx3.rand256() != ctx4.rand256()); 108 } 109 { 110 FastRandomContext ctx3, ctx4; 111 BOOST_CHECK(ctx3.randbytes(7) != ctx4.randbytes(7)); 112 } 113 } 114 115 BOOST_AUTO_TEST_CASE(fastrandom_randbits) 116 { 117 FastRandomContext ctx1; 118 FastRandomContext ctx2; 119 for (int bits = 0; bits < 63; ++bits) { 120 for (int j = 0; j < 1000; ++j) { 121 uint64_t rangebits = ctx1.randbits(bits); 122 BOOST_CHECK_EQUAL(rangebits >> bits, 0U); 123 uint64_t range = (uint64_t{1}) << bits | rangebits; 124 uint64_t rand = ctx2.randrange(range); 125 BOOST_CHECK(rand < range); 126 } 127 } 128 } 129 130 /** Verify that RandomMixin::randbits returns 0 and 1 for every requested bit. */ 131 BOOST_AUTO_TEST_CASE(randbits_test) 132 { 133 FastRandomContext ctx_lens; //!< RNG for producing the lengths requested from ctx_test. 134 FastRandomContext ctx_test1(true), ctx_test2(true); //!< The RNGs being tested. 135 int ctx_test_bitsleft{0}; //!< (Assumed value of) ctx_test::bitbuf_len 136 137 // Run the entire test 5 times. 138 for (int i = 0; i < 5; ++i) { 139 // count (first) how often it has occurred, and (second) how often it was true: 140 // - for every bit position, in every requested bits count (0 + 1 + 2 + ... + 64 = 2080) 141 // - for every value of ctx_test_bitsleft (0..63 = 64) 142 std::vector<std::pair<uint64_t, uint64_t>> seen(2080 * 64); 143 while (true) { 144 // Loop 1000 times, just to not continuously check std::all_of. 145 for (int j = 0; j < 1000; ++j) { 146 // Decide on a number of bits to request (0 through 64, inclusive; don't use randbits/randrange). 147 int bits = ctx_lens.rand64() % 65; 148 // Generate that many bits. 149 uint64_t gen = ctx_test1.randbits(bits); 150 // For certain bits counts, also test randbits<Bits> and compare. 151 uint64_t gen2; 152 if (bits == 0) { 153 gen2 = ctx_test2.randbits<0>(); 154 } else if (bits == 1) { 155 gen2 = ctx_test2.randbits<1>(); 156 } else if (bits == 7) { 157 gen2 = ctx_test2.randbits<7>(); 158 } else if (bits == 32) { 159 gen2 = ctx_test2.randbits<32>(); 160 } else if (bits == 51) { 161 gen2 = ctx_test2.randbits<51>(); 162 } else if (bits == 64) { 163 gen2 = ctx_test2.randbits<64>(); 164 } else { 165 gen2 = ctx_test2.randbits(bits); 166 } 167 BOOST_CHECK_EQUAL(gen, gen2); 168 // Make sure the result is in range. 169 if (bits < 64) BOOST_CHECK_EQUAL(gen >> bits, 0); 170 // Mark all the seen bits in the output. 171 for (int bit = 0; bit < bits; ++bit) { 172 int idx = bit + (bits * (bits - 1)) / 2 + 2080 * ctx_test_bitsleft; 173 seen[idx].first += 1; 174 seen[idx].second += (gen >> bit) & 1; 175 } 176 // Update ctx_test_bitself. 177 if (bits > ctx_test_bitsleft) { 178 ctx_test_bitsleft = ctx_test_bitsleft + 64 - bits; 179 } else { 180 ctx_test_bitsleft -= bits; 181 } 182 } 183 // Loop until every bit position/combination is seen 242 times. 184 if (std::all_of(seen.begin(), seen.end(), [](const auto& x) { return x.first >= 242; })) break; 185 } 186 // Check that each bit appears within 7.78 standard deviations of 50% 187 // (each will fail with P < 1/(2080 * 64 * 10^9)). 188 for (const auto& val : seen) { 189 assert(fabs(val.first * 0.5 - val.second) < sqrt(val.first * 0.25) * 7.78); 190 } 191 } 192 } 193 194 /** Does-it-compile test for compatibility with standard library RNG interface. */ 195 BOOST_AUTO_TEST_CASE(stdrandom_test) 196 { 197 FastRandomContext ctx; 198 std::uniform_int_distribution<int> distribution(3, 9); 199 for (int i = 0; i < 100; ++i) { 200 int x = distribution(ctx); 201 BOOST_CHECK(x >= 3); 202 BOOST_CHECK(x <= 9); 203 204 std::vector<int> test{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 205 std::shuffle(test.begin(), test.end(), ctx); 206 for (int j = 1; j <= 10; ++j) { 207 BOOST_CHECK(std::find(test.begin(), test.end(), j) != test.end()); 208 } 209 } 210 } 211 212 /** Test that Shuffle reaches every permutation with equal probability. */ 213 BOOST_AUTO_TEST_CASE(shuffle_stat_test) 214 { 215 FastRandomContext ctx(true); 216 uint32_t counts[5 * 5 * 5 * 5 * 5] = {0}; 217 for (int i = 0; i < 12000; ++i) { 218 int data[5] = {0, 1, 2, 3, 4}; 219 std::shuffle(std::begin(data), std::end(data), ctx); 220 int pos = data[0] + data[1] * 5 + data[2] * 25 + data[3] * 125 + data[4] * 625; 221 ++counts[pos]; 222 } 223 unsigned int sum = 0; 224 double chi_score = 0.0; 225 for (int i = 0; i < 5 * 5 * 5 * 5 * 5; ++i) { 226 int i1 = i % 5, i2 = (i / 5) % 5, i3 = (i / 25) % 5, i4 = (i / 125) % 5, i5 = i / 625; 227 uint32_t count = counts[i]; 228 if (i1 == i2 || i1 == i3 || i1 == i4 || i1 == i5 || i2 == i3 || i2 == i4 || i2 == i5 || i3 == i4 || i3 == i5 || i4 == i5) { 229 BOOST_CHECK(count == 0); 230 } else { 231 chi_score += ((count - 100.0) * (count - 100.0)) / 100.0; 232 BOOST_CHECK(count > 50); 233 BOOST_CHECK(count < 150); 234 sum += count; 235 } 236 } 237 BOOST_CHECK(chi_score > 58.1411); // 99.9999% confidence interval 238 BOOST_CHECK(chi_score < 210.275); 239 BOOST_CHECK_EQUAL(sum, 12000U); 240 } 241 242 BOOST_AUTO_TEST_CASE(xoroshiro128plusplus_reference_values) 243 { 244 // numbers generated from reference implementation 245 InsecureRandomContext rng(0); 246 BOOST_TEST(0x6f68e1e7e2646ee1 == rng()); 247 BOOST_TEST(0xbf971b7f454094ad == rng()); 248 BOOST_TEST(0x48f2de556f30de38 == rng()); 249 BOOST_TEST(0x6ea7c59f89bbfc75 == rng()); 250 251 // seed with a random number 252 rng.Reseed(0x1a26f3fa8546b47a); 253 BOOST_TEST(0xc8dc5e08d844ac7d == rng()); 254 BOOST_TEST(0x5b5f1f6d499dad1b == rng()); 255 BOOST_TEST(0xbeb0031f93313d6f == rng()); 256 BOOST_TEST(0xbfbcf4f43a264497 == rng()); 257 } 258 259 BOOST_AUTO_TEST_SUITE_END()