Branch data Line data Source code
1 : : // Copyright (c) 2009-2010 Satoshi Nakamoto
2 : : // Copyright (c) 2009-present 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 (clocks, resource usage, ...)
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(std::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(std::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, std::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 : 9401 : constexpr void FlushCache() noexcept
189 : : {
190 : 9401 : bitbuf = 0;
191 : 9401 : bitbuf_size = 0;
192 : : }
193 : :
194 : : public:
195 : 28793132 : 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 : 66332972 : uint64_t randbits(int bits) noexcept
205 : : {
206 : 66332972 : Assume(bits <= 64);
207 : : // Requests for the full 64 bits are passed through.
208 [ + + ]: 66332972 : if (bits == 64) return Impl().rand64();
209 : : uint64_t ret;
210 [ + + ]: 66332348 : if (bits <= bitbuf_size) {
211 : : // If there is enough entropy left in bitbuf, return its bottom bits bits.
212 : 55816550 : ret = bitbuf;
213 : 55816550 : bitbuf >>= bits;
214 : 55816550 : 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 : 10515798 : uint64_t gen = Impl().rand64();
220 : 10515798 : ret = (gen << bitbuf_size) | bitbuf;
221 : 10515798 : bitbuf = gen >> (bits - bitbuf_size);
222 : 10515798 : bitbuf_size = 64 + bitbuf_size - bits;
223 : : }
224 : : // Return the bottom bits bits of ret.
225 : 66332348 : 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 : 664804232 : uint64_t randbits() noexcept
231 : : {
232 : : static_assert(Bits >= 0 && Bits <= 64);
233 : : if constexpr (Bits == 64) {
234 : : return Impl().rand64();
235 : : } else {
236 : : uint64_t ret;
237 [ + + ]: 664804232 : if (Bits <= bitbuf_size) {
238 : 653356361 : ret = bitbuf;
239 : 653356361 : bitbuf >>= Bits;
240 : 653356361 : bitbuf_size -= Bits;
241 : : } else {
242 : 11447871 : uint64_t gen = Impl().rand64();
243 : 11447871 : ret = (gen << bitbuf_size) | bitbuf;
244 : 11447871 : bitbuf = gen >> (Bits - bitbuf_size);
245 : 11447871 : bitbuf_size = 64 + bitbuf_size - Bits;
246 : : }
247 : 664804232 : constexpr uint64_t MASK = (uint64_t{1} << Bits) - 1;
248 : 664804232 : 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 : 49557595 : I randrange(I range) noexcept
255 : : {
256 : : static_assert(std::numeric_limits<I>::max() <= std::numeric_limits<uint64_t>::max());
257 : 49557595 : Assume(range > 0);
258 [ + + ]: 49557595 : uint64_t maxval = range - 1U;
259 : 49557595 : int bits = std::bit_width(maxval);
260 : : while (true) {
261 : 66272963 : uint64_t ret = Impl().randbits(bits);
262 [ + + ]: 66272963 : if (ret <= maxval) return ret;
263 : : }
264 : : }
265 : :
266 : : /** Fill a span with random bytes. */
267 : 1762100 : void fillrand(std::span<std::byte> span) noexcept
268 : : {
269 [ + + ]: 749938420 : while (span.size() >= 8) {
270 : 748176320 : uint64_t gen = Impl().rand64();
271 : 748176320 : WriteLE64(span.data(), gen);
272 : 748176320 : span = span.subspan(8);
273 : : }
274 [ + + ]: 1762100 : if (span.size() >= 4) {
275 : 289654 : uint32_t gen = Impl().rand32();
276 : 144827 : WriteLE32(span.data(), gen);
277 : 144827 : span = span.subspan(4);
278 : : }
279 [ + + ]: 2989161 : while (span.size()) {
280 : 1227061 : span[0] = std::byte(Impl().template randbits<8>());
281 : 1227061 : span = span.subspan(1);
282 : : }
283 : 1762100 : }
284 : :
285 : : /** Generate a random integer in its entire (non-negative) range. */
286 : : template<std::integral I>
287 : 146471 : 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 : 146471 : return I(Impl().template randbits<BITS>());
293 : : }
294 : :
295 : : /** Generate random bytes. */
296 : : template <BasicByte B = unsigned char>
297 : 10694524 : std::vector<B> randbytes(size_t len) noexcept
298 : : {
299 : 10694524 : std::vector<B> ret(len);
300 : 10694524 : Impl().fillrand(MakeWritableByteSpan(ret));
301 : 10694524 : return ret;
302 : : }
303 : :
304 : : /** Generate fixed-size random bytes. */
305 : : template <size_t N, BasicByte B = std::byte>
306 : 136 : std::array<B, N> randbytes() noexcept
307 : : {
308 : : std::array<B, N> ret;
309 : 136 : Impl().fillrand(MakeWritableByteSpan(ret));
310 : 136 : return ret;
311 : : }
312 : :
313 : : /** Generate a random 32-bit integer. */
314 [ + - ]: 373744 : uint32_t rand32() noexcept { return Impl().template randbits<32>(); }
315 : :
316 : : /** generate a random uint256. */
317 : 10105 : uint256 rand256() noexcept
318 : : {
319 : 10105 : uint256 ret;
320 : 10105 : Impl().fillrand(MakeWritableByteSpan(ret));
321 : 10105 : return ret;
322 : : }
323 : :
324 : : /** Generate a random boolean. */
325 [ + - + + : 662966122 : bool randbool() noexcept { return Impl().template randbits<1>(); }
+ + + + +
- ][ + + ]
326 : :
327 : : /** Return the time point advanced by a uniform random duration. */
328 : : template <typename Tp>
329 : 132584 : Tp rand_uniform_delay(const Tp& time, typename Tp::duration range) noexcept
330 : : {
331 : 132584 : return time + Impl().template rand_uniform_duration<Tp>(range);
332 : : }
333 : :
334 : : /** Generate a uniform random duration in the range from 0 (inclusive) to range (exclusive). */
335 : : template <typename Chrono> requires StdChronoDuration<typename Chrono::duration>
336 [ + - ]: 132584 : typename Chrono::duration rand_uniform_duration(typename Chrono::duration range) noexcept
337 : : {
338 : : using Dur = typename Chrono::duration;
339 [ + - ]: 132584 : return range.count() > 0 ? /* interval [0..range) */ Dur{Impl().randrange(range.count())} :
340 [ # # ]: 0 : range.count() < 0 ? /* interval (range..0] */ -Dur{Impl().randrange(-range.count())} :
341 : 132584 : /* interval [0..0] */ Dur{0};
342 : : };
343 : :
344 : : /** Generate a uniform random duration in the range [0..max). Precondition: max.count() > 0 */
345 : : template <StdChronoDuration Dur>
346 : 7700 : Dur randrange(std::common_type_t<Dur> range) noexcept
347 : : // Having the compiler infer the template argument from the function argument
348 : : // is dangerous, because the desired return value generally has a different
349 : : // type than the function argument. So std::common_type is used to force the
350 : : // call site to specify the type of the return value.
351 : : {
352 : 7700 : return Dur{Impl().randrange(range.count())};
353 : : }
354 : :
355 : : /**
356 : : * Return a duration sampled from an exponential distribution
357 : : * (https://en.wikipedia.org/wiki/Exponential_distribution). Successive events
358 : : * whose intervals are distributed according to this form a memoryless Poisson
359 : : * process. This should be used for repeated network events (e.g. sending a
360 : : * certain type of message) to minimize leaking information to observers.
361 : : *
362 : : * The probability of an event occurring before time x is 1 - e^-(x/a) where a
363 : : * is the average interval between events.
364 : : * */
365 : 31243 : std::chrono::microseconds rand_exp_duration(std::chrono::microseconds mean) noexcept
366 : : {
367 : : using namespace std::chrono_literals;
368 : 31243 : auto unscaled = MakeExponentiallyDistributed(Impl().rand64());
369 : 31243 : return std::chrono::duration_cast<std::chrono::microseconds>(unscaled * mean + 0.5us);
370 : : }
371 : :
372 : : // Compatibility with the UniformRandomBitGenerator concept
373 : : typedef uint64_t result_type;
374 : : static constexpr uint64_t min() noexcept { return 0; }
375 : : static constexpr uint64_t max() noexcept { return std::numeric_limits<uint64_t>::max(); }
376 : 755754 : inline uint64_t operator()() noexcept { return Impl().rand64(); }
377 : : };
378 : :
379 : : /**
380 : : * Fast randomness source. This is seeded once with secure random data, but
381 : : * is completely deterministic and does not gather more entropy after that.
382 : : *
383 : : * This class is not thread-safe.
384 : : */
385 [ + + ][ - + : 27411121 : class FastRandomContext : public RandomMixin<FastRandomContext>
- - - - -
- ]
386 : : {
387 : : private:
388 : : bool requires_seed;
389 : : ChaCha20 rng;
390 : :
391 : : void RandomSeed() noexcept;
392 : :
393 : : public:
394 : : /** Construct a FastRandomContext with GetRandHash()-based entropy (or zero key if fDeterministic). */
395 : : explicit FastRandomContext(bool fDeterministic = false) noexcept;
396 : :
397 : : /** Initialize with explicit seed (only for testing) */
398 : : explicit FastRandomContext(const uint256& seed) noexcept;
399 : :
400 : : /** Reseed with explicit seed (only for testing). */
401 : : void Reseed(const uint256& seed) noexcept;
402 : :
403 : : /** Generate a random 64-bit integer. */
404 : 48011967 : uint64_t rand64() noexcept
405 : : {
406 [ + + ]: 48011967 : if (requires_seed) RandomSeed();
407 : 48011967 : std::array<std::byte, 8> buf;
408 : 48011967 : rng.Keystream(buf);
409 : 48011967 : return ReadLE64(buf.data());
410 : : }
411 : :
412 : : /** Fill a byte span with random bytes. This overrides the RandomMixin version. */
413 : : void fillrand(std::span<std::byte> output) noexcept;
414 : : };
415 : :
416 : : /** xoroshiro128++ PRNG. Extremely fast, not appropriate for cryptographic purposes.
417 : : *
418 : : * Memory footprint is very small, period is 2^128 - 1.
419 : : * This class is not thread-safe.
420 : : *
421 : : * Reference implementation available at https://prng.di.unimi.it/xoroshiro128plusplus.c
422 : : * See https://prng.di.unimi.it/
423 : : */
424 : : class InsecureRandomContext : public RandomMixin<InsecureRandomContext>
425 : : {
426 : : uint64_t m_s0;
427 : : uint64_t m_s1;
428 : :
429 : 2760836 : [[nodiscard]] constexpr static uint64_t SplitMix64(uint64_t& seedval) noexcept
430 : : {
431 : 2760836 : uint64_t z = (seedval += 0x9e3779b97f4a7c15);
432 : 2760836 : z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
433 : 2760836 : z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
434 : 2760836 : return z ^ (z >> 31);
435 : : }
436 : :
437 : : public:
438 : 1380418 : constexpr explicit InsecureRandomContext(uint64_t seedval) noexcept
439 : 1380418 : : m_s0(SplitMix64(seedval)), m_s1(SplitMix64(seedval)) {}
440 : :
441 : : constexpr void Reseed(uint64_t seedval) noexcept
442 : : {
443 : : FlushCache();
444 : : m_s0 = SplitMix64(seedval);
445 : : m_s1 = SplitMix64(seedval);
446 : : }
447 : :
448 : 749875461 : constexpr uint64_t rand64() noexcept
449 : : {
450 : 749875461 : uint64_t s0 = m_s0, s1 = m_s1;
451 : 749875461 : const uint64_t result = std::rotl(s0 + s1, 17) + s0;
452 : 749875461 : s1 ^= s0;
453 : 749875461 : m_s0 = std::rotl(s0, 49) ^ s1 ^ (s1 << 21);
454 : 749875461 : m_s1 = std::rotl(s1, 28);
455 : 749875461 : return result;
456 : : }
457 : : };
458 : :
459 : :
460 : : /* ==================== CONVENIENCE FUNCTIONS FOR COMMONLY USED RANDOMNESS ==================== */
461 : :
462 : : /** Generate a random uint256. */
463 : 26751152 : inline uint256 GetRandHash() noexcept
464 : : {
465 : 26751152 : uint256 hash;
466 : 26751152 : GetRandBytes(hash);
467 [ + - # # ]: 26751152 : return hash;
[ - - + - ]
468 : : }
469 : :
470 : : /* ============================= MISCELLANEOUS TEST-ONLY FUNCTIONS ============================= */
471 : :
472 : : /** Check that OS randomness is available and returning the requested number
473 : : * of bytes.
474 : : */
475 : : bool Random_SanityCheck();
476 : :
477 : : #endif // BITCOIN_RANDOM_H
|
