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