random_tests.cpp raw
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()
260