Branch data Line data Source code
# 1 : : // Copyright (c) 2009-2010 Satoshi Nakamoto
# 2 : : // Copyright (c) 2009-2020 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 <uint256.h>
# 12 : :
# 13 : : #include <chrono> // For std::chrono::microseconds
# 14 : : #include <cstdint>
# 15 : : #include <limits>
# 16 : :
# 17 : : /**
# 18 : : * Overall design of the RNG and entropy sources.
# 19 : : *
# 20 : : * We maintain a single global 256-bit RNG state for all high-quality randomness.
# 21 : : * The following (classes of) functions interact with that state by mixing in new
# 22 : : * entropy, and optionally extracting random output from it:
# 23 : : *
# 24 : : * - The GetRand*() class of functions, as well as construction of FastRandomContext objects,
# 25 : : * perform 'fast' seeding, consisting of mixing in:
# 26 : : * - A stack pointer (indirectly committing to calling thread and call stack)
# 27 : : * - A high-precision timestamp (rdtsc when available, c++ high_resolution_clock otherwise)
# 28 : : * - 64 bits from the hardware RNG (rdrand) when available.
# 29 : : * These entropy sources are very fast, and only designed to protect against situations
# 30 : : * where a VM state restore/copy results in multiple systems with the same randomness.
# 31 : : * FastRandomContext on the other hand does not protect against this once created, but
# 32 : : * is even faster (and acceptable to use inside tight loops).
# 33 : : *
# 34 : : * - The GetStrongRand*() class of function perform 'slow' seeding, including everything
# 35 : : * that fast seeding includes, but additionally:
# 36 : : * - OS entropy (/dev/urandom, getrandom(), ...). The application will terminate if
# 37 : : * this entropy source fails.
# 38 : : * - Another high-precision timestamp (indirectly committing to a benchmark of all the
# 39 : : * previous sources).
# 40 : : * These entropy sources are slower, but designed to make sure the RNG state contains
# 41 : : * fresh data that is unpredictable to attackers.
# 42 : : *
# 43 : : * - RandAddPeriodic() seeds everything that fast seeding includes, but additionally:
# 44 : : * - A high-precision timestamp
# 45 : : * - Dynamic environment data (performance monitoring, ...)
# 46 : : * - Strengthen the entropy for 10 ms using repeated SHA512.
# 47 : : * This is run once every minute.
# 48 : : *
# 49 : : * On first use of the RNG (regardless of what function is called first), all entropy
# 50 : : * sources used in the 'slow' seeder are included, but also:
# 51 : : * - 256 bits from the hardware RNG (rdseed or rdrand) when available.
# 52 : : * - Dynamic environment data (performance monitoring, ...)
# 53 : : * - Static environment data
# 54 : : * - Strengthen the entropy for 100 ms using repeated SHA512.
# 55 : : *
# 56 : : * When mixing in new entropy, H = SHA512(entropy || old_rng_state) is computed, and
# 57 : : * (up to) the first 32 bytes of H are produced as output, while the last 32 bytes
# 58 : : * become the new RNG state.
# 59 : : */
# 60 : :
# 61 : : /**
# 62 : : * Generate random data via the internal PRNG.
# 63 : : *
# 64 : : * These functions are designed to be fast (sub microsecond), but do not necessarily
# 65 : : * meaningfully add entropy to the PRNG state.
# 66 : : *
# 67 : : * Thread-safe.
# 68 : : */
# 69 : : void GetRandBytes(unsigned char* buf, int num) noexcept;
# 70 : : /** Generate a uniform random integer in the range [0..range). Precondition: range > 0 */
# 71 : : uint64_t GetRand(uint64_t nMax) noexcept;
# 72 : : /** Generate a uniform random duration in the range [0..max). Precondition: max.count() > 0 */
# 73 : : template <typename D>
# 74 : : D GetRandomDuration(typename std::common_type<D>::type max) noexcept
# 75 : : // Having the compiler infer the template argument from the function argument
# 76 : : // is dangerous, because the desired return value generally has a different
# 77 : : // type than the function argument. So std::common_type is used to force the
# 78 : : // call site to specify the type of the return value.
# 79 : 2064 : {
# 80 : 2064 : assert(max.count() > 0);
# 81 : 2064 : return D{GetRand(max.count())};
# 82 : 2064 : };
# 83 : : constexpr auto GetRandMicros = GetRandomDuration<std::chrono::microseconds>;
# 84 : : constexpr auto GetRandMillis = GetRandomDuration<std::chrono::milliseconds>;
# 85 : : int GetRandInt(int nMax) noexcept;
# 86 : : uint256 GetRandHash() noexcept;
# 87 : :
# 88 : : /**
# 89 : : * Gather entropy from various sources, feed it into the internal PRNG, and
# 90 : : * generate random data using it.
# 91 : : *
# 92 : : * This function will cause failure whenever the OS RNG fails.
# 93 : : *
# 94 : : * Thread-safe.
# 95 : : */
# 96 : : void GetStrongRandBytes(unsigned char* buf, int num) noexcept;
# 97 : :
# 98 : : /**
# 99 : : * Gather entropy from various expensive sources, and feed them to the PRNG state.
# 100 : : *
# 101 : : * Thread-safe.
# 102 : : */
# 103 : : void RandAddPeriodic() noexcept;
# 104 : :
# 105 : : /**
# 106 : : * Gathers entropy from the low bits of the time at which events occur. Should
# 107 : : * be called with a uint32_t describing the event at the time an event occurs.
# 108 : : *
# 109 : : * Thread-safe.
# 110 : : */
# 111 : : void RandAddEvent(const uint32_t event_info) noexcept;
# 112 : :
# 113 : : /**
# 114 : : * Fast randomness source. This is seeded once with secure random data, but
# 115 : : * is completely deterministic and does not gather more entropy after that.
# 116 : : *
# 117 : : * This class is not thread-safe.
# 118 : : */
# 119 : : class FastRandomContext
# 120 : : {
# 121 : : private:
# 122 : : bool requires_seed;
# 123 : : ChaCha20 rng;
# 124 : :
# 125 : : unsigned char bytebuf[64];
# 126 : : int bytebuf_size;
# 127 : :
# 128 : : uint64_t bitbuf;
# 129 : : int bitbuf_size;
# 130 : :
# 131 : : void RandomSeed();
# 132 : :
# 133 : : void FillByteBuffer()
# 134 : 13871750 : {
# 135 [ + + ]: 13871750 : if (requires_seed) {
# 136 : 1829531 : RandomSeed();
# 137 : 1829531 : }
# 138 : 13871750 : rng.Keystream(bytebuf, sizeof(bytebuf));
# 139 : 13871750 : bytebuf_size = sizeof(bytebuf);
# 140 : 13871750 : }
# 141 : :
# 142 : : void FillBitBuffer()
# 143 : 85303654 : {
# 144 : 85303654 : bitbuf = rand64();
# 145 : 85303654 : bitbuf_size = 64;
# 146 : 85303654 : }
# 147 : :
# 148 : : public:
# 149 : : explicit FastRandomContext(bool fDeterministic = false) noexcept;
# 150 : :
# 151 : : /** Initialize with explicit seed (only for testing) */
# 152 : : explicit FastRandomContext(const uint256& seed) noexcept;
# 153 : :
# 154 : : // Do not permit copying a FastRandomContext (move it, or create a new one to get reseeded).
# 155 : : FastRandomContext(const FastRandomContext&) = delete;
# 156 : : FastRandomContext(FastRandomContext&&) = delete;
# 157 : : FastRandomContext& operator=(const FastRandomContext&) = delete;
# 158 : :
# 159 : : /** Move a FastRandomContext. If the original one is used again, it will be reseeded. */
# 160 : : FastRandomContext& operator=(FastRandomContext&& from) noexcept;
# 161 : :
# 162 : : /** Generate a random 64-bit integer. */
# 163 : : uint64_t rand64() noexcept
# 164 : 88352617 : {
# 165 [ + + ]: 88352617 : if (bytebuf_size < 8) FillByteBuffer();
# 166 : 88352617 : uint64_t ret = ReadLE64(bytebuf + 64 - bytebuf_size);
# 167 : 88352617 : bytebuf_size -= 8;
# 168 : 88352617 : return ret;
# 169 : 88352617 : }
# 170 : :
# 171 : : /** Generate a random (bits)-bit integer. */
# 172 : : uint64_t randbits(int bits) noexcept
# 173 : 934556044 : {
# 174 [ + + ]: 934556044 : if (bits == 0) {
# 175 : 273614 : return 0;
# 176 [ + + ]: 934282430 : } else if (bits > 32) {
# 177 : 3034997 : return rand64() >> (64 - bits);
# 178 : 931247433 : } else {
# 179 [ + + ]: 931247433 : if (bitbuf_size < bits) FillBitBuffer();
# 180 : 931247433 : uint64_t ret = bitbuf & (~(uint64_t)0 >> (64 - bits));
# 181 : 931247433 : bitbuf >>= bits;
# 182 : 931247433 : bitbuf_size -= bits;
# 183 : 931247433 : return ret;
# 184 : 931247433 : }
# 185 : 934556044 : }
# 186 : :
# 187 : : /** Generate a random integer in the range [0..range).
# 188 : : * Precondition: range > 0.
# 189 : : */
# 190 : : uint64_t randrange(uint64_t range) noexcept
# 191 : 33265060 : {
# 192 : 33265060 : assert(range);
# 193 : 33265060 : --range;
# 194 : 33265060 : int bits = CountBits(range);
# 195 : 45816426 : while (true) {
# 196 : 45816426 : uint64_t ret = randbits(bits);
# 197 [ + + ]: 45816426 : if (ret <= range) return ret;
# 198 : 45816426 : }
# 199 : 33265060 : }
# 200 : :
# 201 : : /** Generate random bytes. */
# 202 : : std::vector<unsigned char> randbytes(size_t len);
# 203 : :
# 204 : : /** Generate a random 32-bit integer. */
# 205 : 33075469 : uint32_t rand32() noexcept { return randbits(32); }
# 206 : :
# 207 : : /** generate a random uint256. */
# 208 : : uint256 rand256() noexcept;
# 209 : :
# 210 : : /** Generate a random boolean. */
# 211 : 386971368 : bool randbool() noexcept { return randbits(1); }
# 212 : :
# 213 : : // Compatibility with the C++11 UniformRandomBitGenerator concept
# 214 : : typedef uint64_t result_type;
# 215 : 0 : static constexpr uint64_t min() { return 0; }
# 216 : 0 : static constexpr uint64_t max() { return std::numeric_limits<uint64_t>::max(); }
# 217 : 13894 : inline uint64_t operator()() noexcept { return rand64(); }
# 218 : : };
# 219 : :
# 220 : : /** More efficient than using std::shuffle on a FastRandomContext.
# 221 : : *
# 222 : : * This is more efficient as std::shuffle will consume entropy in groups of
# 223 : : * 64 bits at the time and throw away most.
# 224 : : *
# 225 : : * This also works around a bug in libstdc++ std::shuffle that may cause
# 226 : : * type::operator=(type&&) to be invoked on itself, which the library's
# 227 : : * debug mode detects and panics on. This is a known issue, see
# 228 : : * https://stackoverflow.com/questions/22915325/avoiding-self-assignment-in-stdshuffle
# 229 : : */
# 230 : : template <typename I, typename R>
# 231 : : void Shuffle(I first, I last, R&& rng)
# 232 : 69593 : {
# 233 [ + + ][ + + ]: 3834977 : while (first != last) {
# [ + + ][ + + ]
# [ + + ][ - + ]
# [ + + ][ + + ]
# [ + + ][ + + ]
# 234 : 3765384 : size_t j = rng.randrange(last - first);
# 235 [ + + ][ + + ]: 3765384 : if (j) {
# [ + + ][ + + ]
# [ + + ][ # # ]
# [ + + ][ + + ]
# [ + + ][ + + ]
# 236 : 3530471 : using std::swap;
# 237 : 3530471 : swap(*first, *(first + j));
# 238 : 3530471 : }
# 239 : 3765384 : ++first;
# 240 : 3765384 : }
# 241 : 69593 : }
# 242 : :
# 243 : : /* Number of random bytes returned by GetOSRand.
# 244 : : * When changing this constant make sure to change all call sites, and make
# 245 : : * sure that the underlying OS APIs for all platforms support the number.
# 246 : : * (many cap out at 256 bytes).
# 247 : : */
# 248 : : static const int NUM_OS_RANDOM_BYTES = 32;
# 249 : :
# 250 : : /** Get 32 bytes of system entropy. Do not use this in application code: use
# 251 : : * GetStrongRandBytes instead.
# 252 : : */
# 253 : : void GetOSRand(unsigned char* ent32);
# 254 : :
# 255 : : /** Check that OS randomness is available and returning the requested number
# 256 : : * of bytes.
# 257 : : */
# 258 : : bool Random_SanityCheck();
# 259 : :
# 260 : : /**
# 261 : : * Initialize global RNG state and log any CPU features that are used.
# 262 : : *
# 263 : : * Calling this function is optional. RNG state will be initialized when first
# 264 : : * needed if it is not called.
# 265 : : */
# 266 : : void RandomInit();
# 267 : :
# 268 : : #endif // BITCOIN_RANDOM_H
|
