Bitcoin Core  24.99.0
P2P Digital Currency
random_tests.cpp
Go to the documentation of this file.
1 // Copyright (c) 2017-2020 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 
8 
9 #include <boost/test/unit_test.hpp>
10 
11 #include <algorithm>
12 #include <random>
13 
14 BOOST_FIXTURE_TEST_SUITE(random_tests, BasicTestingSetup)
15 
16 BOOST_AUTO_TEST_CASE(osrandom_tests)
17 {
19 }
20 
21 BOOST_AUTO_TEST_CASE(fastrandom_tests)
22 {
23  // Check that deterministic FastRandomContexts are deterministic
25  FastRandomContext ctx1(true);
26  FastRandomContext ctx2(true);
27 
28  for (int i = 10; i > 0; --i) {
29  BOOST_CHECK_EQUAL(GetRand<uint64_t>(), uint64_t{10393729187455219830U});
30  BOOST_CHECK_EQUAL(GetRand<int>(), int{769702006});
31  BOOST_CHECK_EQUAL(GetRandMicros(std::chrono::hours{1}).count(), 2917185654);
32  BOOST_CHECK_EQUAL(GetRandMillis(std::chrono::hours{1}).count(), 2144374);
33  }
34  {
35  constexpr SteadySeconds time_point{1s};
36  FastRandomContext ctx{true};
37  BOOST_CHECK_EQUAL(7, ctx.rand_uniform_delay(time_point, 9s).time_since_epoch().count());
38  BOOST_CHECK_EQUAL(-6, ctx.rand_uniform_delay(time_point, -9s).time_since_epoch().count());
39  BOOST_CHECK_EQUAL(1, ctx.rand_uniform_delay(time_point, 0s).time_since_epoch().count());
40  BOOST_CHECK_EQUAL(1467825113502396065, ctx.rand_uniform_delay(time_point, 9223372036854775807s).time_since_epoch().count());
41  BOOST_CHECK_EQUAL(-970181367944767837, ctx.rand_uniform_delay(time_point, -9223372036854775807s).time_since_epoch().count());
42  BOOST_CHECK_EQUAL(24761, ctx.rand_uniform_delay(time_point, 9h).time_since_epoch().count());
43  }
44  BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32());
45  BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32());
46  BOOST_CHECK_EQUAL(ctx1.rand64(), ctx2.rand64());
47  BOOST_CHECK_EQUAL(ctx1.randbits(3), ctx2.randbits(3));
48  BOOST_CHECK(ctx1.randbytes(17) == ctx2.randbytes(17));
49  BOOST_CHECK(ctx1.rand256() == ctx2.rand256());
50  BOOST_CHECK_EQUAL(ctx1.randbits(7), ctx2.randbits(7));
51  BOOST_CHECK(ctx1.randbytes(128) == ctx2.randbytes(128));
52  BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32());
53  BOOST_CHECK_EQUAL(ctx1.randbits(3), ctx2.randbits(3));
54  BOOST_CHECK(ctx1.rand256() == ctx2.rand256());
55  BOOST_CHECK(ctx1.randbytes(50) == ctx2.randbytes(50));
56  {
57  struct MicroClock {
58  using duration = std::chrono::microseconds;
59  };
60  FastRandomContext ctx{true};
61  // Check with clock type
62  BOOST_CHECK_EQUAL(47222, ctx.rand_uniform_duration<MicroClock>(1s).count());
63  // Check with time-point type
64  BOOST_CHECK_EQUAL(2782, ctx.rand_uniform_duration<SteadySeconds>(9h).count());
65  }
66 
67  // Check that a nondeterministic ones are not
69  for (int i = 10; i > 0; --i) {
70  BOOST_CHECK(GetRand<uint64_t>() != uint64_t{10393729187455219830U});
71  BOOST_CHECK(GetRand<int>() != int{769702006});
72  BOOST_CHECK(GetRandMicros(std::chrono::hours{1}) != std::chrono::microseconds{2917185654});
73  BOOST_CHECK(GetRandMillis(std::chrono::hours{1}) != std::chrono::milliseconds{2144374});
74  }
75  {
76  FastRandomContext ctx3, ctx4;
77  BOOST_CHECK(ctx3.rand64() != ctx4.rand64()); // extremely unlikely to be equal
78  }
79  {
80  FastRandomContext ctx3, ctx4;
81  BOOST_CHECK(ctx3.rand256() != ctx4.rand256());
82  }
83  {
84  FastRandomContext ctx3, ctx4;
85  BOOST_CHECK(ctx3.randbytes(7) != ctx4.randbytes(7));
86  }
87 }
88 
89 BOOST_AUTO_TEST_CASE(fastrandom_randbits)
90 {
91  FastRandomContext ctx1;
92  FastRandomContext ctx2;
93  for (int bits = 0; bits < 63; ++bits) {
94  for (int j = 0; j < 1000; ++j) {
95  uint64_t rangebits = ctx1.randbits(bits);
96  BOOST_CHECK_EQUAL(rangebits >> bits, 0U);
97  uint64_t range = ((uint64_t)1) << bits | rangebits;
98  uint64_t rand = ctx2.randrange(range);
99  BOOST_CHECK(rand < range);
100  }
101  }
102 }
103 
105 BOOST_AUTO_TEST_CASE(stdrandom_test)
106 {
108  std::uniform_int_distribution<int> distribution(3, 9);
109  for (int i = 0; i < 100; ++i) {
110  int x = distribution(ctx);
111  BOOST_CHECK(x >= 3);
112  BOOST_CHECK(x <= 9);
113 
114  std::vector<int> test{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
115  std::shuffle(test.begin(), test.end(), ctx);
116  for (int j = 1; j <= 10; ++j) {
117  BOOST_CHECK(std::find(test.begin(), test.end(), j) != test.end());
118  }
119  Shuffle(test.begin(), test.end(), ctx);
120  for (int j = 1; j <= 10; ++j) {
121  BOOST_CHECK(std::find(test.begin(), test.end(), j) != test.end());
122  }
123  }
124 }
125 
127 BOOST_AUTO_TEST_CASE(shuffle_stat_test)
128 {
129  FastRandomContext ctx(true);
130  uint32_t counts[5 * 5 * 5 * 5 * 5] = {0};
131  for (int i = 0; i < 12000; ++i) {
132  int data[5] = {0, 1, 2, 3, 4};
133  Shuffle(std::begin(data), std::end(data), ctx);
134  int pos = data[0] + data[1] * 5 + data[2] * 25 + data[3] * 125 + data[4] * 625;
135  ++counts[pos];
136  }
137  unsigned int sum = 0;
138  double chi_score = 0.0;
139  for (int i = 0; i < 5 * 5 * 5 * 5 * 5; ++i) {
140  int i1 = i % 5, i2 = (i / 5) % 5, i3 = (i / 25) % 5, i4 = (i / 125) % 5, i5 = i / 625;
141  uint32_t count = counts[i];
142  if (i1 == i2 || i1 == i3 || i1 == i4 || i1 == i5 || i2 == i3 || i2 == i4 || i2 == i5 || i3 == i4 || i3 == i5 || i4 == i5) {
143  BOOST_CHECK(count == 0);
144  } else {
145  chi_score += ((count - 100.0) * (count - 100.0)) / 100.0;
146  BOOST_CHECK(count > 50);
147  BOOST_CHECK(count < 150);
148  sum += count;
149  }
150  }
151  BOOST_CHECK(chi_score > 58.1411); // 99.9999% confidence interval
152  BOOST_CHECK(chi_score < 210.275);
153  BOOST_CHECK_EQUAL(sum, 12000U);
154 }
155 
Fast randomness source.
Definition: random.h:143
uint32_t rand32() noexcept
Generate a random 32-bit integer.
Definition: random.h:228
uint64_t rand64() noexcept
Generate a random 64-bit integer.
Definition: random.h:186
uint256 rand256() noexcept
generate a random uint256.
Definition: random.cpp:606
std::vector< unsigned char > randbytes(size_t len)
Generate random bytes.
Definition: random.cpp:617
uint64_t randbits(int bits) noexcept
Generate a random (bits)-bit integer.
Definition: random.h:195
uint64_t randrange(uint64_t range) noexcept
Generate a random integer in the range [0..range).
Definition: random.h:213
BOOST_AUTO_TEST_SUITE_END()
volatile double sum
Definition: examples.cpp:10
#define BOOST_CHECK_EQUAL(v1, v2)
Definition: object.cpp:17
#define BOOST_CHECK(expr)
Definition: object.cpp:16
bool g_mock_deterministic_tests
Flag to make GetRand in random.h return the same number.
Definition: random.cpp:585
bool Random_SanityCheck()
Check that OS randomness is available and returning the requested number of bytes.
Definition: random.cpp:632
constexpr auto GetRandMicros
Definition: random.h:95
constexpr auto GetRandMillis
Definition: random.h:96
void Shuffle(I first, I last, R &&rng)
More efficient than using std::shuffle on a FastRandomContext.
Definition: random.h:271
BOOST_AUTO_TEST_CASE(osrandom_tests)
Basic testing setup.
Definition: setup_common.h:83
static secp256k1_context * ctx
Definition: tests.c:34
static int count
Definition: tests.c:33
std::chrono::time_point< std::chrono::steady_clock, std::chrono::seconds > SteadySeconds
Definition: time.h:28