random.h
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