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(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 constexpr void FlushCache() noexcept
189 {
190 bitbuf = 0;
191 bitbuf_size = 0;
192 }
193 194 public:
195 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 {
206 Assume(bits <= 64);
207 // Requests for the full 64 bits are passed through.
208 if (bits == 64) return Impl().rand64();
209 uint64_t ret;
210 if (bits <= bitbuf_size) {
211 // If there is enough entropy left in bitbuf, return its bottom bits bits.
212 ret = bitbuf;
213 bitbuf >>= bits;
214 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 uint64_t gen = Impl().rand64();
220 ret = (gen << bitbuf_size) | bitbuf;
221 bitbuf = gen >> (bits - bitbuf_size);
222 bitbuf_size = 64 + bitbuf_size - bits;
223 }
224 // Return the bottom bits bits of ret.
225 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 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 if (Bits <= bitbuf_size) {
238 ret = bitbuf;
239 bitbuf >>= Bits;
240 bitbuf_size -= Bits;
241 } else {
242 uint64_t gen = Impl().rand64();
243 ret = (gen << bitbuf_size) | bitbuf;
244 bitbuf = gen >> (Bits - bitbuf_size);
245 bitbuf_size = 64 + bitbuf_size - Bits;
246 }
247 constexpr uint64_t MASK = (uint64_t{1} << Bits) - 1;
248 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 I randrange(I range) noexcept
255 {
256 static_assert(std::numeric_limits<I>::max() <= std::numeric_limits<uint64_t>::max());
257 Assume(range > 0);
258 uint64_t maxval = range - 1U;
259 int bits = std::bit_width(maxval);
260 while (true) {
261 uint64_t ret = Impl().randbits(bits);
262 if (ret <= maxval) return ret;
263 }
264 }
265 266 /** Fill a span with random bytes. */
267 void fillrand(std::span<std::byte> span) noexcept
268 {
269 while (span.size() >= 8) {
270 uint64_t gen = Impl().rand64();
271 WriteLE64(span.data(), gen);
272 span = span.subspan(8);
273 }
274 if (span.size() >= 4) {
275 uint32_t gen = Impl().rand32();
276 WriteLE32(span.data(), gen);
277 span = span.subspan(4);
278 }
279 while (span.size()) {
280 span[0] = std::byte(Impl().template randbits<8>());
281 span = span.subspan(1);
282 }
283 }
284 285 /** Generate a random integer in its entire (non-negative) range. */
286 template<std::integral I>
287 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 return I(Impl().template randbits<BITS>());
293 }
294 295 /** Generate random bytes. */
296 template <BasicByte B = unsigned char>
297 std::vector<B> randbytes(size_t len) noexcept
298 {
299 std::vector<B> ret(len);
300 Impl().fillrand(MakeWritableByteSpan(ret));
301 return ret;
302 }
303 304 /** Generate fixed-size random bytes. */
305 template <size_t N, BasicByte B = std::byte>
306 std::array<B, N> randbytes() noexcept
307 {
308 std::array<B, N> ret;
309 Impl().fillrand(MakeWritableByteSpan(ret));
310 return ret;
311 }
312 313 /** Generate a random 32-bit integer. */
314 uint32_t rand32() noexcept { return Impl().template randbits<32>(); }
315 316 /** generate a random uint256. */
317 uint256 rand256() noexcept
318 {
319 uint256 ret;
320 Impl().fillrand(MakeWritableByteSpan(ret));
321 return ret;
322 }
323 324 /** Generate a random boolean. */
325 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 Tp rand_uniform_delay(const Tp& time, typename Tp::duration range) noexcept
330 {
331 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 typename Chrono::duration rand_uniform_duration(typename Chrono::duration range) noexcept
337 {
338 using Dur = typename Chrono::duration;
339 return range.count() > 0 ? /* interval [0..range) */ Dur{Impl().randrange(range.count())} :
340 range.count() < 0 ? /* interval (range..0] */ -Dur{Impl().randrange(-range.count())} :
341 /* 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 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 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 std::chrono::microseconds rand_exp_duration(std::chrono::microseconds mean) noexcept
366 {
367 using namespace std::chrono_literals;
368 auto unscaled = MakeExponentiallyDistributed(Impl().rand64());
369 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 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 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 uint64_t rand64() noexcept
405 {
406 if (requires_seed) RandomSeed();
407 std::array<std::byte, 8> buf;
408 rng.Keystream(buf);
409 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 [[nodiscard]] constexpr static uint64_t SplitMix64(uint64_t& seedval) noexcept
430 {
431 uint64_t z = (seedval += 0x9e3779b97f4a7c15);
432 z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
433 z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
434 return z ^ (z >> 31);
435 }
436 437 public:
438 constexpr explicit InsecureRandomContext(uint64_t seedval) noexcept
439 : 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 constexpr uint64_t rand64() noexcept
449 {
450 uint64_t s0 = m_s0, s1 = m_s1;
451 const uint64_t result = std::rotl(s0 + s1, 17) + s0;
452 s1 ^= s0;
453 m_s0 = std::rotl(s0, 49) ^ s1 ^ (s1 << 21);
454 m_s1 = std::rotl(s1, 28);
455 return result;
456 }
457 };
458 459 460 /* ==================== CONVENIENCE FUNCTIONS FOR COMMONLY USED RANDOMNESS ==================== */
461 462 /** Generate a random uint256. */
463 inline uint256 GetRandHash() noexcept
464 {
465 uint256 hash;
466 GetRandBytes(hash);
467 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
478