/workdir/bitcoin/src/random.h
Line | Count | Source (jump to first uncovered line) |
1 | | // Copyright (c) 2009-2010 Satoshi Nakamoto |
2 | | // Copyright (c) 2009-2022 The Bitcoin Core developers |
3 | | // Distributed under the MIT software license, see the accompanying |
4 | | // file COPYING or http://www.opensource.org/licenses/mit-license.php. |
5 | | |
6 | | #ifndef BITCOIN_RANDOM_H |
7 | | #define BITCOIN_RANDOM_H |
8 | | |
9 | | #include <crypto/chacha20.h> |
10 | | #include <crypto/common.h> |
11 | | #include <span.h> |
12 | | #include <uint256.h> |
13 | | #include <util/check.h> |
14 | | |
15 | | #include <bit> |
16 | | #include <cassert> |
17 | | #include <chrono> |
18 | | #include <concepts> |
19 | | #include <cstdint> |
20 | | #include <limits> |
21 | | #include <type_traits> |
22 | | #include <vector> |
23 | | |
24 | | /** |
25 | | * Overall design of the RNG and entropy sources. |
26 | | * |
27 | | * We maintain a single global 256-bit RNG state for all high-quality randomness. |
28 | | * The following (classes of) functions interact with that state by mixing in new |
29 | | * entropy, and optionally extracting random output from it: |
30 | | * |
31 | | * - GetRandBytes, GetRandHash, GetRandDur, as well as construction of FastRandomContext |
32 | | * objects, perform 'fast' seeding, consisting of mixing in: |
33 | | * - A stack pointer (indirectly committing to calling thread and call stack) |
34 | | * - A high-precision timestamp (rdtsc when available, c++ high_resolution_clock otherwise) |
35 | | * - 64 bits from the hardware RNG (rdrand) when available. |
36 | | * These entropy sources are very fast, and only designed to protect against situations |
37 | | * where a VM state restore/copy results in multiple systems with the same randomness. |
38 | | * FastRandomContext on the other hand does not protect against this once created, but |
39 | | * is even faster (and acceptable to use inside tight loops). |
40 | | * |
41 | | * - The GetStrongRandBytes() function performs 'slow' seeding, including everything |
42 | | * that fast seeding includes, but additionally: |
43 | | * - OS entropy (/dev/urandom, getrandom(), ...). The application will terminate if |
44 | | * this entropy source fails. |
45 | | * - Another high-precision timestamp (indirectly committing to a benchmark of all the |
46 | | * previous sources). |
47 | | * These entropy sources are slower, but designed to make sure the RNG state contains |
48 | | * fresh data that is unpredictable to attackers. |
49 | | * |
50 | | * - RandAddPeriodic() seeds everything that fast seeding includes, but additionally: |
51 | | * - A high-precision timestamp |
52 | | * - Dynamic environment data (performance monitoring, ...) |
53 | | * - Strengthen the entropy for 10 ms using repeated SHA512. |
54 | | * This is run once every minute. |
55 | | * |
56 | | * - On first use of the RNG (regardless of what function is called first), all entropy |
57 | | * sources used in the 'slow' seeder are included, but also: |
58 | | * - 256 bits from the hardware RNG (rdseed or rdrand) when available. |
59 | | * - Dynamic environment data (performance monitoring, ...) |
60 | | * - Static environment data |
61 | | * - Strengthen the entropy for 100 ms using repeated SHA512. |
62 | | * |
63 | | * When mixing in new entropy, H = SHA512(entropy || old_rng_state) is computed, and |
64 | | * (up to) the first 32 bytes of H are produced as output, while the last 32 bytes |
65 | | * become the new RNG state. |
66 | | * |
67 | | * During tests, the RNG can be put into a special deterministic mode, in which the output |
68 | | * of all RNG functions, with the exception of GetStrongRandBytes(), is replaced with the |
69 | | * output of a deterministic RNG. This deterministic RNG does not gather entropy, and is |
70 | | * unaffected by RandAddPeriodic() or RandAddEvent(). It produces pseudorandom data that |
71 | | * only depends on the seed it was initialized with, possibly until it is reinitialized. |
72 | | */ |
73 | | |
74 | | |
75 | | /* ============================= INITIALIZATION AND ADDING ENTROPY ============================= */ |
76 | | |
77 | | /** |
78 | | * Initialize global RNG state and log any CPU features that are used. |
79 | | * |
80 | | * Calling this function is optional. RNG state will be initialized when first |
81 | | * needed if it is not called. |
82 | | */ |
83 | | void RandomInit(); |
84 | | |
85 | | /** |
86 | | * Gather entropy from various expensive sources, and feed them to the PRNG state. |
87 | | * |
88 | | * Thread-safe. |
89 | | */ |
90 | | void RandAddPeriodic() noexcept; |
91 | | |
92 | | /** |
93 | | * Gathers entropy from the low bits of the time at which events occur. Should |
94 | | * be called with a uint32_t describing the event at the time an event occurs. |
95 | | * |
96 | | * Thread-safe. |
97 | | */ |
98 | | void RandAddEvent(const uint32_t event_info) noexcept; |
99 | | |
100 | | |
101 | | /* =========================== BASE RANDOMNESS GENERATION FUNCTIONS =========================== |
102 | | * |
103 | | * All produced randomness is eventually generated by one of these functions. |
104 | | */ |
105 | | |
106 | | /** |
107 | | * Generate random data via the internal PRNG. |
108 | | * |
109 | | * These functions are designed to be fast (sub microsecond), but do not necessarily |
110 | | * meaningfully add entropy to the PRNG state. |
111 | | * |
112 | | * In test mode (see SeedRandomForTest in src/test/util/random.h), the normal PRNG state is |
113 | | * bypassed, and a deterministic, seeded, PRNG is used instead. |
114 | | * |
115 | | * Thread-safe. |
116 | | */ |
117 | | void GetRandBytes(Span<unsigned char> bytes) noexcept; |
118 | | |
119 | | /** |
120 | | * Gather entropy from various sources, feed it into the internal PRNG, and |
121 | | * generate random data using it. |
122 | | * |
123 | | * This function will cause failure whenever the OS RNG fails. |
124 | | * |
125 | | * The normal PRNG is never bypassed here, even in test mode. |
126 | | * |
127 | | * Thread-safe. |
128 | | */ |
129 | | void GetStrongRandBytes(Span<unsigned char> bytes) noexcept; |
130 | | |
131 | | |
132 | | /* ============================= RANDOM NUMBER GENERATION CLASSES ============================= |
133 | | * |
134 | | * In this section, 3 classes are defined: |
135 | | * - RandomMixin: a base class that adds functionality to all RNG classes. |
136 | | * - FastRandomContext: a cryptographic RNG (seeded through GetRandBytes in its default |
137 | | * constructor). |
138 | | * - InsecureRandomContext: a non-cryptographic, very fast, RNG. |
139 | | */ |
140 | | |
141 | | // Forward declaration of RandomMixin, used in RandomNumberGenerator concept. |
142 | | template<typename T> |
143 | | class RandomMixin; |
144 | | |
145 | | /** A concept for RandomMixin-based random number generators. */ |
146 | | template<typename T> |
147 | | concept RandomNumberGenerator = requires(T& rng, Span<std::byte> s) { |
148 | | // A random number generator must provide rand64(). |
149 | | { rng.rand64() } noexcept -> std::same_as<uint64_t>; |
150 | | // A random number generator must derive from RandomMixin, which adds other rand* functions. |
151 | | requires std::derived_from<std::remove_reference_t<T>, RandomMixin<std::remove_reference_t<T>>>; |
152 | | }; |
153 | | |
154 | | /** A concept for C++ std::chrono durations. */ |
155 | | template<typename T> |
156 | | concept StdChronoDuration = requires { |
157 | 0 | []<class Rep, class Period>(std::type_identity<std::chrono::duration<Rep, Period>>){}( Unexecuted instantiation: net.cpp:_ZZN11RandomMixinI17FastRandomContextE21rand_uniform_durationINSt6chrono3_V212steady_clockEQ17StdChronoDurationINTL0__8durationEEEENT_8durationES9_ENKUlTyTySt13type_identityINS3_8durationIS8_T0_EEEE_clIlSt5ratioILl1ELl1000000000EEEEDaSE_ Unexecuted instantiation: net.cpp:_ZZN11RandomMixinI17FastRandomContextE9randrangeITk17StdChronoDurationNSt6chrono8durationIlSt5ratioILl1ELl1000000EEEEEET_NSt11common_typeIJS8_EE4typeEENKUlTyTySt13type_identityINS4_IS8_T0_EEEE_clIlS6_EEDaSF_ Unexecuted instantiation: net.cpp:_ZZN11RandomMixinI17FastRandomContextE21rand_uniform_durationINSt6chrono10time_pointI9NodeClockNS3_8durationIlSt5ratioILl1ELl1EEEEEEQ17StdChronoDurationINTL0__8durationEEEENT_8durationESE_ENKUlTyTySt13type_identityINS6_ISD_T0_EEEE_clIlS8_EEDaSI_ Unexecuted instantiation: net_processing.cpp:_ZZN11RandomMixinI17FastRandomContextE9randrangeITk17StdChronoDurationNSt6chrono8durationIlSt5ratioILl1ELl1000EEEEEET_NSt11common_typeIJS8_EE4typeEENKUlTyTySt13type_identityINS4_IS8_T0_EEEE_clIlS6_EEDaSF_ Unexecuted instantiation: net_processing.cpp:_ZZN11RandomMixinI17FastRandomContextE9randrangeITk17StdChronoDurationNSt6chrono8durationIlSt5ratioILl1ELl1000000EEEEEET_NSt11common_typeIJS8_EE4typeEENKUlTyTySt13type_identityINS4_IS8_T0_EEEE_clIlS6_EEDaSF_ Unexecuted instantiation: wallet.cpp:_ZZN11RandomMixinI17FastRandomContextE21rand_uniform_durationINSt6chrono10time_pointI9NodeClockNS3_8durationIlSt5ratioILl1ELl1000000000EEEEEEQ17StdChronoDurationINTL0__8durationEEEENT_8durationESE_ENKUlTyTySt13type_identityINS6_ISD_T0_EEEE_clIlS8_EEDaSI_ |
158 | | std::type_identity<T>()); |
159 | | }; |
160 | | |
161 | | /** Given a uniformly random uint64_t, return an exponentially distributed double with mean 1. */ |
162 | | double MakeExponentiallyDistributed(uint64_t uniform) noexcept; |
163 | | |
164 | | /** Mixin class that provides helper randomness functions. |
165 | | * |
166 | | * Intended to be used through CRTP: https://en.cppreference.com/w/cpp/language/crtp. |
167 | | * An RNG class FunkyRNG would derive publicly from RandomMixin<FunkyRNG>. This permits |
168 | | * RandomMixin from accessing the derived class's rand64() function, while also allowing |
169 | | * the derived class to provide more. |
170 | | * |
171 | | * The derived class must satisfy the RandomNumberGenerator concept. |
172 | | */ |
173 | | template<typename T> |
174 | | class RandomMixin |
175 | | { |
176 | | private: |
177 | | uint64_t bitbuf{0}; |
178 | | int bitbuf_size{0}; |
179 | | |
180 | | /** Access the underlying generator. |
181 | | * |
182 | | * This also enforces the RandomNumberGenerator concept. We cannot declare that in the template |
183 | | * (no template<RandomNumberGenerator T>) because the type isn't fully instantiated yet there. |
184 | | */ |
185 | 11.3k | RandomNumberGenerator auto& Impl() noexcept { return static_cast<T&>(*this); } RandomMixin<FastRandomContext>::Impl() Line | Count | Source | 185 | 11.3k | RandomNumberGenerator auto& Impl() noexcept { return static_cast<T&>(*this); } |
Unexecuted instantiation: RandomMixin<InsecureRandomContext>::Impl() |
186 | | |
187 | | protected: |
188 | | constexpr void FlushCache() noexcept |
189 | 0 | { |
190 | 0 | bitbuf = 0; |
191 | 0 | bitbuf_size = 0; |
192 | 0 | } Unexecuted instantiation: RandomMixin<InsecureRandomContext>::FlushCache() Unexecuted instantiation: RandomMixin<FastRandomContext>::FlushCache() |
193 | | |
194 | | public: |
195 | 9.17k | constexpr RandomMixin() noexcept = default; Unexecuted instantiation: RandomMixin<InsecureRandomContext>::RandomMixin() RandomMixin<FastRandomContext>::RandomMixin() Line | Count | Source | 195 | 9.17k | constexpr RandomMixin() noexcept = default; |
|
196 | | |
197 | | // Do not permit copying or moving an RNG. |
198 | | RandomMixin(const RandomMixin&) = delete; |
199 | | RandomMixin& operator=(const RandomMixin&) = delete; |
200 | | RandomMixin(RandomMixin&&) = delete; |
201 | | RandomMixin& operator=(RandomMixin&&) = delete; |
202 | | |
203 | | /** Generate a random (bits)-bit integer. */ |
204 | | uint64_t randbits(int bits) noexcept |
205 | 7.69k | { |
206 | 7.69k | Assume(bits <= 64); |
207 | | // Requests for the full 64 bits are passed through. |
208 | 7.69k | if (bits == 64) return Impl().rand64(); Branch (208:13): [True: 0, False: 7.69k]
Branch (208:13): [True: 0, False: 0]
|
209 | 7.69k | uint64_t ret; |
210 | 7.69k | if (bits <= bitbuf_size) { Branch (210:13): [True: 7.25k, False: 431]
Branch (210:13): [True: 0, False: 0]
|
211 | | // If there is enough entropy left in bitbuf, return its bottom bits bits. |
212 | 7.25k | ret = bitbuf; |
213 | 7.25k | bitbuf >>= bits; |
214 | 7.25k | bitbuf_size -= bits; |
215 | 7.25k | } else { |
216 | | // If not, return all of bitbuf, supplemented with the (bits - bitbuf_size) bottom |
217 | | // bits of a newly generated 64-bit number on top. The remainder of that generated |
218 | | // number becomes the new bitbuf. |
219 | 431 | uint64_t gen = Impl().rand64(); |
220 | 431 | ret = (gen << bitbuf_size) | bitbuf; |
221 | 431 | bitbuf = gen >> (bits - bitbuf_size); |
222 | 431 | bitbuf_size = 64 + bitbuf_size - bits; |
223 | 431 | } |
224 | | // Return the bottom bits bits of ret. |
225 | 7.69k | return ret & ((uint64_t{1} << bits) - 1); |
226 | 7.69k | } RandomMixin<FastRandomContext>::randbits(int) Line | Count | Source | 205 | 7.69k | { | 206 | 7.69k | Assume(bits <= 64); | 207 | | // Requests for the full 64 bits are passed through. | 208 | 7.69k | if (bits == 64) return Impl().rand64(); Branch (208:13): [True: 0, False: 7.69k]
| 209 | 7.69k | uint64_t ret; | 210 | 7.69k | if (bits <= bitbuf_size) { Branch (210:13): [True: 7.25k, False: 431]
| 211 | | // If there is enough entropy left in bitbuf, return its bottom bits bits. | 212 | 7.25k | ret = bitbuf; | 213 | 7.25k | bitbuf >>= bits; | 214 | 7.25k | bitbuf_size -= bits; | 215 | 7.25k | } else { | 216 | | // If not, return all of bitbuf, supplemented with the (bits - bitbuf_size) bottom | 217 | | // bits of a newly generated 64-bit number on top. The remainder of that generated | 218 | | // number becomes the new bitbuf. | 219 | 431 | uint64_t gen = Impl().rand64(); | 220 | 431 | ret = (gen << bitbuf_size) | bitbuf; | 221 | 431 | bitbuf = gen >> (bits - bitbuf_size); | 222 | 431 | bitbuf_size = 64 + bitbuf_size - bits; | 223 | 431 | } | 224 | | // Return the bottom bits bits of ret. | 225 | 7.69k | return ret & ((uint64_t{1} << bits) - 1); | 226 | 7.69k | } |
Unexecuted instantiation: RandomMixin<InsecureRandomContext>::randbits(int) |
227 | | |
228 | | /** Same as above, but with compile-time fixed bits count. */ |
229 | | template<int Bits> |
230 | | uint64_t randbits() noexcept |
231 | 870 | { |
232 | 870 | static_assert(Bits >= 0 && Bits <= 64); |
233 | | if constexpr (Bits == 64) { |
234 | | return Impl().rand64(); |
235 | 870 | } else { |
236 | 870 | uint64_t ret; |
237 | 870 | if (Bits <= bitbuf_size) { Branch (237:17): [True: 0, False: 0]
Branch (237:17): [True: 0, False: 0]
Branch (237:17): [True: 0, False: 0]
Branch (237:17): [True: 0, False: 0]
Branch (237:17): [True: 0, False: 870]
Branch (237:17): [True: 0, False: 0]
Branch (237:17): [True: 0, False: 0]
|
238 | 0 | ret = bitbuf; |
239 | 0 | bitbuf >>= Bits; |
240 | 0 | bitbuf_size -= Bits; |
241 | 870 | } else { |
242 | 870 | uint64_t gen = Impl().rand64(); |
243 | 870 | ret = (gen << bitbuf_size) | bitbuf; |
244 | 870 | bitbuf = gen >> (Bits - bitbuf_size); |
245 | 870 | bitbuf_size = 64 + bitbuf_size - Bits; |
246 | 870 | } |
247 | 870 | constexpr uint64_t MASK = (uint64_t{1} << Bits) - 1; |
248 | 870 | return ret & MASK; |
249 | 870 | } |
250 | 870 | } Unexecuted instantiation: unsigned long RandomMixin<InsecureRandomContext>::randbits<32>() Unexecuted instantiation: unsigned long RandomMixin<InsecureRandomContext>::randbits<8>() Unexecuted instantiation: unsigned long RandomMixin<FastRandomContext>::randbits<1>() Unexecuted instantiation: unsigned long RandomMixin<InsecureRandomContext>::randbits<1>() unsigned long RandomMixin<FastRandomContext>::randbits<32>() Line | Count | Source | 231 | 870 | { | 232 | 870 | static_assert(Bits >= 0 && Bits <= 64); | 233 | | if constexpr (Bits == 64) { | 234 | | return Impl().rand64(); | 235 | 870 | } else { | 236 | 870 | uint64_t ret; | 237 | 870 | if (Bits <= bitbuf_size) { Branch (237:17): [True: 0, False: 870]
| 238 | 0 | ret = bitbuf; | 239 | 0 | bitbuf >>= Bits; | 240 | 0 | bitbuf_size -= Bits; | 241 | 870 | } else { | 242 | 870 | uint64_t gen = Impl().rand64(); | 243 | 870 | ret = (gen << bitbuf_size) | bitbuf; | 244 | 870 | bitbuf = gen >> (Bits - bitbuf_size); | 245 | 870 | bitbuf_size = 64 + bitbuf_size - Bits; | 246 | 870 | } | 247 | 870 | constexpr uint64_t MASK = (uint64_t{1} << Bits) - 1; | 248 | 870 | return ret & MASK; | 249 | 870 | } | 250 | 870 | } |
Unexecuted instantiation: unsigned long RandomMixin<FastRandomContext>::randbits<16>() Unexecuted instantiation: unsigned long RandomMixin<FastRandomContext>::randbits<30>() |
251 | | |
252 | | /** Generate a random integer in the range [0..range), with range > 0. */ |
253 | | template<std::integral I> |
254 | | I randrange(I range) noexcept |
255 | 7.33k | { |
256 | 7.33k | static_assert(std::numeric_limits<I>::max() <= std::numeric_limits<uint64_t>::max()); |
257 | 7.33k | Assume(range > 0); |
258 | 7.33k | uint64_t maxval = range - 1U; |
259 | 7.33k | int bits = std::bit_width(maxval); |
260 | 7.69k | while (true) { Branch (260:16): [Folded - Ignored]
Branch (260:16): [Folded - Ignored]
Branch (260:16): [Folded - Ignored]
Branch (260:16): [Folded - Ignored]
Branch (260:16): [Folded - Ignored]
|
261 | 7.69k | uint64_t ret = Impl().randbits(bits); |
262 | 7.69k | if (ret <= maxval) return ret; Branch (262:17): [True: 6.84k, False: 0]
Branch (262:17): [True: 0, False: 0]
Branch (262:17): [True: 0, False: 0]
Branch (262:17): [True: 198, False: 133]
Branch (262:17): [True: 289, False: 225]
|
263 | 7.69k | } |
264 | 7.33k | } _ZN11RandomMixinI17FastRandomContextE9randrangeITkSt8integraliEET_S3_ Line | Count | Source | 255 | 6.84k | { | 256 | 6.84k | static_assert(std::numeric_limits<I>::max() <= std::numeric_limits<uint64_t>::max()); | 257 | 6.84k | Assume(range > 0); | 258 | 6.84k | uint64_t maxval = range - 1U; | 259 | 6.84k | int bits = std::bit_width(maxval); | 260 | 6.84k | while (true) { Branch (260:16): [Folded - Ignored]
| 261 | 6.84k | uint64_t ret = Impl().randbits(bits); | 262 | 6.84k | if (ret <= maxval) return ret; Branch (262:17): [True: 6.84k, False: 0]
| 263 | 6.84k | } | 264 | 6.84k | } |
Unexecuted instantiation: _ZN11RandomMixinI21InsecureRandomContextE9randrangeITkSt8integraljEET_S3_ Unexecuted instantiation: _ZN11RandomMixinI17FastRandomContextE9randrangeITkSt8integralmEET_S3_ _ZN11RandomMixinI17FastRandomContextE9randrangeITkSt8integraljEET_S3_ Line | Count | Source | 255 | 198 | { | 256 | 198 | static_assert(std::numeric_limits<I>::max() <= std::numeric_limits<uint64_t>::max()); | 257 | 198 | Assume(range > 0); | 258 | 198 | uint64_t maxval = range - 1U; | 259 | 198 | int bits = std::bit_width(maxval); | 260 | 331 | while (true) { Branch (260:16): [Folded - Ignored]
| 261 | 331 | uint64_t ret = Impl().randbits(bits); | 262 | 331 | if (ret <= maxval) return ret; Branch (262:17): [True: 198, False: 133]
| 263 | 331 | } | 264 | 198 | } |
_ZN11RandomMixinI17FastRandomContextE9randrangeITkSt8integrallEET_S3_ Line | Count | Source | 255 | 289 | { | 256 | 289 | static_assert(std::numeric_limits<I>::max() <= std::numeric_limits<uint64_t>::max()); | 257 | 289 | Assume(range > 0); | 258 | 289 | uint64_t maxval = range - 1U; | 259 | 289 | int bits = std::bit_width(maxval); | 260 | 514 | while (true) { Branch (260:16): [Folded - Ignored]
| 261 | 514 | uint64_t ret = Impl().randbits(bits); | 262 | 514 | if (ret <= maxval) return ret; Branch (262:17): [True: 289, False: 225]
| 263 | 514 | } | 264 | 289 | } |
|
265 | | |
266 | | /** Fill a Span with random bytes. */ |
267 | | void fillrand(Span<std::byte> span) noexcept |
268 | 0 | { |
269 | 0 | while (span.size() >= 8) { Branch (269:16): [True: 0, False: 0]
|
270 | 0 | uint64_t gen = Impl().rand64(); |
271 | 0 | WriteLE64(UCharCast(span.data()), gen); |
272 | 0 | span = span.subspan(8); |
273 | 0 | } |
274 | 0 | if (span.size() >= 4) { Branch (274:13): [True: 0, False: 0]
|
275 | 0 | uint32_t gen = Impl().rand32(); |
276 | 0 | WriteLE32(UCharCast(span.data()), gen); |
277 | 0 | span = span.subspan(4); |
278 | 0 | } |
279 | 0 | while (span.size()) { Branch (279:16): [True: 0, False: 0]
|
280 | 0 | span[0] = std::byte(Impl().template randbits<8>()); |
281 | 0 | span = span.subspan(1); |
282 | 0 | } |
283 | 0 | } |
284 | | |
285 | | /** Generate a random integer in its entire (non-negative) range. */ |
286 | | template<std::integral I> |
287 | | I rand() noexcept |
288 | 870 | { |
289 | 870 | static_assert(std::numeric_limits<I>::max() <= std::numeric_limits<uint64_t>::max()); |
290 | 870 | static constexpr auto BITS = std::bit_width(uint64_t(std::numeric_limits<I>::max())); |
291 | 870 | static_assert(std::numeric_limits<I>::max() == std::numeric_limits<uint64_t>::max() >> (64 - BITS)); |
292 | 870 | return I(Impl().template randbits<BITS>()); |
293 | 870 | } Unexecuted instantiation: _ZN11RandomMixinI17FastRandomContextE4randITkSt8integraltEET_v _ZN11RandomMixinI17FastRandomContextE4randITkSt8integraljEET_v Line | Count | Source | 288 | 870 | { | 289 | 870 | static_assert(std::numeric_limits<I>::max() <= std::numeric_limits<uint64_t>::max()); | 290 | 870 | static constexpr auto BITS = std::bit_width(uint64_t(std::numeric_limits<I>::max())); | 291 | 870 | static_assert(std::numeric_limits<I>::max() == std::numeric_limits<uint64_t>::max() >> (64 - BITS)); | 292 | 870 | return I(Impl().template randbits<BITS>()); | 293 | 870 | } |
|
294 | | |
295 | | /** Generate random bytes. */ |
296 | | template <BasicByte B = unsigned char> |
297 | | std::vector<B> randbytes(size_t len) noexcept |
298 | 0 | { |
299 | 0 | std::vector<B> ret(len); |
300 | 0 | Impl().fillrand(MakeWritableByteSpan(ret)); |
301 | 0 | return ret; |
302 | 0 | } Unexecuted instantiation: _ZN11RandomMixinI21InsecureRandomContextE9randbytesITk9BasicByteSt4byteEESt6vectorIT_SaIS5_EEm Unexecuted instantiation: _ZN11RandomMixinI21InsecureRandomContextE9randbytesITk9BasicBytehEESt6vectorIT_SaIS4_EEm Unexecuted instantiation: _ZN11RandomMixinI17FastRandomContextE9randbytesITk9BasicBytehEESt6vectorIT_SaIS4_EEm |
303 | | |
304 | | /** Generate a random 32-bit integer. */ |
305 | 0 | uint32_t rand32() noexcept { return Impl().template randbits<32>(); } Unexecuted instantiation: RandomMixin<InsecureRandomContext>::rand32() Unexecuted instantiation: RandomMixin<FastRandomContext>::rand32() |
306 | | |
307 | | /** generate a random uint256. */ |
308 | | uint256 rand256() noexcept |
309 | 0 | { |
310 | 0 | uint256 ret; |
311 | 0 | Impl().fillrand(MakeWritableByteSpan(ret)); |
312 | 0 | return ret; |
313 | 0 | } |
314 | | |
315 | | /** Generate a random boolean. */ |
316 | 0 | bool randbool() noexcept { return Impl().template randbits<1>(); } Unexecuted instantiation: RandomMixin<FastRandomContext>::randbool() Unexecuted instantiation: RandomMixin<InsecureRandomContext>::randbool() |
317 | | |
318 | | /** Return the time point advanced by a uniform random duration. */ |
319 | | template <typename Tp> |
320 | | Tp rand_uniform_delay(const Tp& time, typename Tp::duration range) noexcept |
321 | 0 | { |
322 | 0 | return time + Impl().template rand_uniform_duration<Tp>(range); |
323 | 0 | } Unexecuted instantiation: std::chrono::time_point<NodeClock, std::chrono::duration<long, std::ratio<1l, 1l> > > RandomMixin<FastRandomContext>::rand_uniform_delay<std::chrono::time_point<NodeClock, std::chrono::duration<long, std::ratio<1l, 1l> > > >(std::chrono::time_point<NodeClock, std::chrono::duration<long, std::ratio<1l, 1l> > > const&, std::chrono::time_point<NodeClock, std::chrono::duration<long, std::ratio<1l, 1l> > >::duration) Unexecuted instantiation: std::chrono::time_point<NodeClock, std::chrono::duration<long, std::ratio<1l, 1000000000l> > > RandomMixin<FastRandomContext>::rand_uniform_delay<std::chrono::time_point<NodeClock, std::chrono::duration<long, std::ratio<1l, 1000000000l> > > >(std::chrono::time_point<NodeClock, std::chrono::duration<long, std::ratio<1l, 1000000000l> > > const&, std::chrono::time_point<NodeClock, std::chrono::duration<long, std::ratio<1l, 1000000000l> > >::duration) |
324 | | |
325 | | /** Generate a uniform random duration in the range from 0 (inclusive) to range (exclusive). */ |
326 | | template <typename Chrono> requires StdChronoDuration<typename Chrono::duration> |
327 | | typename Chrono::duration rand_uniform_duration(typename Chrono::duration range) noexcept |
328 | 0 | { |
329 | 0 | using Dur = typename Chrono::duration; |
330 | 0 | return range.count() > 0 ? /* interval [0..range) */ Dur{Impl().randrange(range.count())} : Branch (330:16): [True: 0, False: 0]
Branch (330:16): [True: 0, False: 0]
Branch (330:16): [True: 0, False: 0]
|
331 | 0 | range.count() < 0 ? /* interval (range..0] */ -Dur{Impl().randrange(-range.count())} : Branch (331:16): [True: 0, False: 0]
Branch (331:16): [True: 0, False: 0]
Branch (331:16): [True: 0, False: 0]
|
332 | 0 | /* interval [0..0] */ Dur{0}; |
333 | 0 | }; Unexecuted instantiation: _ZN11RandomMixinI17FastRandomContextE21rand_uniform_durationINSt6chrono10time_pointI9NodeClockNS3_8durationIlSt5ratioILl1ELl1EEEEEEQ17StdChronoDurationINTL0__8durationEEEENT_8durationESE_ Unexecuted instantiation: _ZN11RandomMixinI17FastRandomContextE21rand_uniform_durationINSt6chrono3_V212steady_clockEQ17StdChronoDurationINTL0__8durationEEEENT_8durationES9_ Unexecuted instantiation: _ZN11RandomMixinI17FastRandomContextE21rand_uniform_durationINSt6chrono10time_pointI9NodeClockNS3_8durationIlSt5ratioILl1ELl1000000000EEEEEEQ17StdChronoDurationINTL0__8durationEEEENT_8durationESE_ |
334 | | |
335 | | /** Generate a uniform random duration in the range [0..max). Precondition: max.count() > 0 */ |
336 | | template <StdChronoDuration Dur> |
337 | | Dur randrange(typename std::common_type_t<Dur> range) noexcept |
338 | | // Having the compiler infer the template argument from the function argument |
339 | | // is dangerous, because the desired return value generally has a different |
340 | | // type than the function argument. So std::common_type is used to force the |
341 | | // call site to specify the type of the return value. |
342 | 289 | { |
343 | 289 | return Dur{Impl().randrange(range.count())}; |
344 | 289 | } _ZN11RandomMixinI17FastRandomContextE9randrangeITk17StdChronoDurationNSt6chrono8durationIlSt5ratioILl1ELl1000000EEEEEET_NSt11common_typeIJS8_EE4typeE Line | Count | Source | 342 | 289 | { | 343 | 289 | return Dur{Impl().randrange(range.count())}; | 344 | 289 | } |
Unexecuted instantiation: _ZN11RandomMixinI17FastRandomContextE9randrangeITk17StdChronoDurationNSt6chrono8durationIlSt5ratioILl1ELl1000EEEEEET_NSt11common_typeIJS8_EE4typeE |
345 | | |
346 | | /** |
347 | | * Return a duration sampled from an exponential distribution |
348 | | * (https://en.wikipedia.org/wiki/Exponential_distribution). Successive events |
349 | | * whose intervals are distributed according to this form a memoryless Poisson |
350 | | * process. This should be used for repeated network events (e.g. sending a |
351 | | * certain type of message) to minimize leaking information to observers. |
352 | | * |
353 | | * The probability of an event occurring before time x is 1 - e^-(x/a) where a |
354 | | * is the average interval between events. |
355 | | * */ |
356 | | std::chrono::microseconds rand_exp_duration(std::chrono::microseconds mean) noexcept |
357 | 1.16k | { |
358 | 1.16k | using namespace std::chrono_literals; |
359 | 1.16k | auto unscaled = MakeExponentiallyDistributed(Impl().rand64()); |
360 | 1.16k | return std::chrono::duration_cast<std::chrono::microseconds>(unscaled * mean + 0.5us); |
361 | 1.16k | } |
362 | | |
363 | | // Compatibility with the UniformRandomBitGenerator concept |
364 | | typedef uint64_t result_type; |
365 | 0 | static constexpr uint64_t min() noexcept { return 0; } |
366 | 0 | static constexpr uint64_t max() noexcept { return std::numeric_limits<uint64_t>::max(); } |
367 | 0 | inline uint64_t operator()() noexcept { return Impl().rand64(); } Unexecuted instantiation: RandomMixin<FastRandomContext>::operator()() Unexecuted instantiation: RandomMixin<InsecureRandomContext>::operator()() |
368 | | }; |
369 | | |
370 | | /** |
371 | | * Fast randomness source. This is seeded once with secure random data, but |
372 | | * is completely deterministic and does not gather more entropy after that. |
373 | | * |
374 | | * This class is not thread-safe. |
375 | | */ |
376 | | class FastRandomContext : public RandomMixin<FastRandomContext> |
377 | | { |
378 | | private: |
379 | | bool requires_seed; |
380 | | ChaCha20 rng; |
381 | | |
382 | | void RandomSeed() noexcept; |
383 | | |
384 | | public: |
385 | | /** Construct a FastRandomContext with GetRandHash()-based entropy (or zero key if fDeterministic). */ |
386 | | explicit FastRandomContext(bool fDeterministic = false) noexcept; |
387 | | |
388 | | /** Initialize with explicit seed (only for testing) */ |
389 | | explicit FastRandomContext(const uint256& seed) noexcept; |
390 | | |
391 | | /** Reseed with explicit seed (only for testing). */ |
392 | | void Reseed(const uint256& seed) noexcept; |
393 | | |
394 | | /** Generate a random 64-bit integer. */ |
395 | | uint64_t rand64() noexcept |
396 | 3.72k | { |
397 | 3.72k | if (requires_seed) RandomSeed(); Branch (397:13): [True: 2.33k, False: 1.39k]
|
398 | 3.72k | std::array<std::byte, 8> buf; |
399 | 3.72k | rng.Keystream(buf); |
400 | 3.72k | return ReadLE64(UCharCast(buf.data())); |
401 | 3.72k | } |
402 | | |
403 | | /** Fill a byte Span with random bytes. This overrides the RandomMixin version. */ |
404 | | void fillrand(Span<std::byte> output) noexcept; |
405 | | }; |
406 | | |
407 | | /** xoroshiro128++ PRNG. Extremely fast, not appropriate for cryptographic purposes. |
408 | | * |
409 | | * Memory footprint is very small, period is 2^128 - 1. |
410 | | * This class is not thread-safe. |
411 | | * |
412 | | * Reference implementation available at https://prng.di.unimi.it/xoroshiro128plusplus.c |
413 | | * See https://prng.di.unimi.it/ |
414 | | */ |
415 | | class InsecureRandomContext : public RandomMixin<InsecureRandomContext> |
416 | | { |
417 | | uint64_t m_s0; |
418 | | uint64_t m_s1; |
419 | | |
420 | | [[nodiscard]] constexpr static uint64_t SplitMix64(uint64_t& seedval) noexcept |
421 | 0 | { |
422 | 0 | uint64_t z = (seedval += 0x9e3779b97f4a7c15); |
423 | 0 | z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9; |
424 | 0 | z = (z ^ (z >> 27)) * 0x94d049bb133111eb; |
425 | 0 | return z ^ (z >> 31); |
426 | 0 | } |
427 | | |
428 | | public: |
429 | | constexpr explicit InsecureRandomContext(uint64_t seedval) noexcept |
430 | 0 | : m_s0(SplitMix64(seedval)), m_s1(SplitMix64(seedval)) {} |
431 | | |
432 | | constexpr void Reseed(uint64_t seedval) noexcept |
433 | 0 | { |
434 | 0 | FlushCache(); |
435 | 0 | m_s0 = SplitMix64(seedval); |
436 | 0 | m_s1 = SplitMix64(seedval); |
437 | 0 | } |
438 | | |
439 | | constexpr uint64_t rand64() noexcept |
440 | 0 | { |
441 | 0 | uint64_t s0 = m_s0, s1 = m_s1; |
442 | 0 | const uint64_t result = std::rotl(s0 + s1, 17) + s0; |
443 | 0 | s1 ^= s0; |
444 | 0 | m_s0 = std::rotl(s0, 49) ^ s1 ^ (s1 << 21); |
445 | 0 | m_s1 = std::rotl(s1, 28); |
446 | 0 | return result; |
447 | 0 | } |
448 | | }; |
449 | | |
450 | | |
451 | | /* ==================== CONVENIENCE FUNCTIONS FOR COMMONLY USED RANDOMNESS ==================== */ |
452 | | |
453 | | /** Generate a random uint256. */ |
454 | | inline uint256 GetRandHash() noexcept |
455 | 2.33k | { |
456 | 2.33k | uint256 hash; |
457 | 2.33k | GetRandBytes(hash); |
458 | 2.33k | return hash; |
459 | 2.33k | } |
460 | | |
461 | | /* ============================= MISCELLANEOUS TEST-ONLY FUNCTIONS ============================= */ |
462 | | |
463 | | /** Check that OS randomness is available and returning the requested number |
464 | | * of bytes. |
465 | | */ |
466 | | bool Random_SanityCheck(); |
467 | | |
468 | | #endif // BITCOIN_RANDOM_H |