Branch data Line data Source code
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 : : []<class Rep, class Period>(std::type_identity<std::chrono::duration<Rep, Period>>){}(
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 : : RandomNumberGenerator auto& Impl() noexcept { return static_cast<T&>(*this); }
186 : :
187 : : protected:
188 : 728 : constexpr void FlushCache() noexcept
189 : : {
190 : 728 : bitbuf = 0;
191 : 728 : bitbuf_size = 0;
192 : : }
193 : :
194 : : public:
195 : 420219 : 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 : 26263016 : uint64_t randbits(int bits) noexcept
205 : : {
206 : 26263016 : Assume(bits <= 64);
207 : : // Requests for the full 64 bits are passed through.
208 [ + + ]: 26263016 : if (bits == 64) return Impl().rand64();
209 : : uint64_t ret;
210 [ + + ]: 25654539 : if (bits <= bitbuf_size) {
211 : : // If there is enough entropy left in bitbuf, return its bottom bits bits.
212 : 18425797 : ret = bitbuf;
213 : 18425797 : bitbuf >>= bits;
214 : 18425797 : bitbuf_size -= bits;
215 : : } 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 : 7228742 : uint64_t gen = Impl().rand64();
220 : 7228742 : ret = (gen << bitbuf_size) | bitbuf;
221 : 7228742 : bitbuf = gen >> (bits - bitbuf_size);
222 : 7228742 : bitbuf_size = 64 + bitbuf_size - bits;
223 : : }
224 : : // Return the bottom bits bits of ret.
225 : 25654539 : return ret & ((uint64_t{1} << bits) - 1);
226 : : }
227 : :
228 : : /** Same as above, but with compile-time fixed bits count. */
229 : : template<int Bits>
230 : 390886739 : uint64_t randbits() noexcept
231 : : {
232 : : static_assert(Bits >= 0 && Bits <= 64);
233 : : if constexpr (Bits == 64) {
234 : 96477 : return Impl().rand64();
235 : : } else {
236 : : uint64_t ret;
237 [ + + ]: 390790256 : if (Bits <= bitbuf_size) {
238 : 376517289 : ret = bitbuf;
239 : 376420668 : bitbuf >>= Bits;
240 : 376420668 : bitbuf_size -= Bits;
241 : : } else {
242 : 14272967 : uint64_t gen = Impl().rand64();
243 : 14272967 : ret = (gen << bitbuf_size) | bitbuf;
244 : 14272967 : bitbuf = gen >> (Bits - bitbuf_size);
245 : 14272967 : bitbuf_size = 64 + bitbuf_size - Bits;
246 : : }
247 : 390790256 : constexpr uint64_t MASK = (uint64_t{1} << Bits) - 1;
248 : 390790256 : return ret & MASK;
249 : : }
250 : : }
251 : :
252 : : /** Generate a random integer in the range [0..range), with range > 0. */
253 : : template<std::integral I>
254 : 7262526 : I randrange(I range) noexcept
255 : : {
256 : : static_assert(std::numeric_limits<I>::max() <= std::numeric_limits<uint64_t>::max());
257 : 7262526 : Assume(range > 0);
258 [ + + ]: 7262526 : uint64_t maxval = range - 1U;
259 : 7262526 : int bits = std::bit_width(maxval);
260 : : while (true) {
261 : 10851982 : uint64_t ret = Impl().randbits(bits);
262 [ + + ]: 10851982 : if (ret <= maxval) return ret;
263 : : }
264 : : }
265 : :
266 : : /** Fill a Span with random bytes. */
267 : 0 : void fillrand(Span<std::byte> span) noexcept
268 : : {
269 [ # # ]: 0 : while (span.size() >= 8) {
270 : 0 : uint64_t gen = Impl().rand64();
271 : 0 : WriteLE64(UCharCast(span.data()), gen);
272 : 0 : span = span.subspan(8);
273 : : }
274 [ # # ]: 0 : if (span.size() >= 4) {
275 : 0 : uint32_t gen = Impl().rand32();
276 : 0 : WriteLE32(UCharCast(span.data()), gen);
277 : 0 : span = span.subspan(4);
278 : : }
279 [ # # ]: 0 : while (span.size()) {
280 : 0 : span[0] = std::byte(Impl().template randbits<8>());
281 : 0 : span = span.subspan(1);
282 : : }
283 : 0 : }
284 : :
285 : : /** Generate a random integer in its entire (non-negative) range. */
286 : : template<std::integral I>
287 : 189 : I rand() noexcept
288 : : {
289 : : static_assert(std::numeric_limits<I>::max() <= std::numeric_limits<uint64_t>::max());
290 : : static constexpr auto BITS = std::bit_width(uint64_t(std::numeric_limits<I>::max()));
291 : : static_assert(std::numeric_limits<I>::max() == std::numeric_limits<uint64_t>::max() >> (64 - BITS));
292 [ + - + - : 189 : return I(Impl().template randbits<BITS>());
+ - + - +
- + - + -
+ - + - +
- + - +
- ]
293 : : }
294 : :
295 : : /** Generate random bytes. */
296 : : template <BasicByte B = unsigned char>
297 : 50549 : std::vector<B> randbytes(size_t len) noexcept
298 : : {
299 : 50549 : std::vector<B> ret(len);
300 : 50549 : Impl().fillrand(MakeWritableByteSpan(ret));
301 : 50549 : return ret;
302 : : }
303 : :
304 : : /** Generate a random 32-bit integer. */
305 [ + + ][ + + : 16547648 : uint32_t rand32() noexcept { return Impl().template randbits<32>(); }
+ + # # ]
[ + - + -
+ - ]
306 : :
307 : : /** generate a random uint256. */
308 : 1250573 : uint256 rand256() noexcept
309 : : {
310 : 1250573 : uint256 ret;
311 : 1250573 : Impl().fillrand(MakeWritableByteSpan(ret));
312 : 1250573 : return ret;
313 : : }
314 : :
315 : : /** Generate a random boolean. */
316 [ + + ]: 373075464 : bool randbool() noexcept { return Impl().template randbits<1>(); }
[ + - + - ]
[ # # # #
# # # # #
# ]
317 : :
318 : : /** Return the time point advanced by a uniform random duration. */
319 : : template <typename Tp>
320 : 123 : Tp rand_uniform_delay(const Tp& time, typename Tp::duration range) noexcept
321 : : {
322 : 123 : return time + Impl().template rand_uniform_duration<Tp>(range);
323 : : }
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 [ + + ]: 125 : typename Chrono::duration rand_uniform_duration(typename Chrono::duration range) noexcept
328 : : {
329 : : using Dur = typename Chrono::duration;
330 [ + + ]: 125 : return range.count() > 0 ? /* interval [0..range) */ Dur{Impl().randrange(range.count())} :
331 [ + + ]: 3 : range.count() < 0 ? /* interval (range..0] */ -Dur{Impl().randrange(-range.count())} :
332 : 123 : /* interval [0..0] */ Dur{0};
333 : : };
334 : :
335 : : /** Generate a uniform random duration in the range [0..max). Precondition: max.count() > 0 */
336 : : template <StdChronoDuration Dur>
337 : 12 : 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 : : {
343 [ + - + - : 12 : return Dur{Impl().randrange(range.count())};
+ - + - +
- + - + -
+ - + - +
- + - +
- ]
344 : : }
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 : 14 : std::chrono::microseconds rand_exp_duration(std::chrono::microseconds mean) noexcept
357 : : {
358 : : using namespace std::chrono_literals;
359 : 14 : auto unscaled = MakeExponentiallyDistributed(Impl().rand64());
360 : 14 : return std::chrono::duration_cast<std::chrono::microseconds>(unscaled * mean + 0.5us);
361 : : }
362 : :
363 : : // Compatibility with the UniformRandomBitGenerator concept
364 : : typedef uint64_t result_type;
365 : : static constexpr uint64_t min() noexcept { return 0; }
366 : : static constexpr uint64_t max() noexcept { return std::numeric_limits<uint64_t>::max(); }
367 : 497984 : inline uint64_t operator()() noexcept { return Impl().rand64(); }
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 [ + + ][ - + : 419786 : 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 : 29369337 : uint64_t rand64() noexcept
396 : : {
397 [ + + ]: 29369337 : if (requires_seed) RandomSeed();
398 : 29369337 : std::array<std::byte, 8> buf;
399 : 29369337 : rng.Keystream(buf);
400 : 29369337 : return ReadLE64(UCharCast(buf.data()));
401 : : }
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 : 2 : [[nodiscard]] constexpr static uint64_t SplitMix64(uint64_t& seedval) noexcept
421 : : {
422 : 2 : uint64_t z = (seedval += 0x9e3779b97f4a7c15);
423 : 2 : z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
424 : 2 : z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
425 : 2 : return z ^ (z >> 31);
426 : : }
427 : :
428 : : public:
429 : 0 : constexpr explicit InsecureRandomContext(uint64_t seedval) noexcept
430 : 0 : : m_s0(SplitMix64(seedval)), m_s1(SplitMix64(seedval)) {}
431 : :
432 : 1 : constexpr void Reseed(uint64_t seedval) noexcept
433 : : {
434 : 1 : FlushCache();
435 : 1 : m_s0 = SplitMix64(seedval);
436 : 1 : m_s1 = SplitMix64(seedval);
437 : 1 : }
438 : :
439 : 8 : constexpr uint64_t rand64() noexcept
440 : : {
441 : 8 : uint64_t s0 = m_s0, s1 = m_s1;
442 : 8 : const uint64_t result = std::rotl(s0 + s1, 17) + s0;
443 : 8 : s1 ^= s0;
444 : 8 : m_s0 = std::rotl(s0, 49) ^ s1 ^ (s1 << 21);
445 : 8 : m_s1 = std::rotl(s1, 28);
446 : 8 : return result;
447 : : }
448 : : };
449 : :
450 : :
451 : : /* ==================== CONVENIENCE FUNCTIONS FOR COMMONLY USED RANDOMNESS ==================== */
452 : :
453 : : /** Generate a random uint256. */
454 : 378093 : inline uint256 GetRandHash() noexcept
455 : : {
456 : 378093 : uint256 hash;
457 : 378092 : GetRandBytes(hash);
458 [ + - + - ]: 378092 : return hash;
[ + - # # ]
459 : : }
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
|
