Branch data     Line data    Source code

       1                 :            : // Copyright (c) 2009-2010 Satoshi Nakamoto
       2                 :            : // Copyright (c) 2009-2022 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>
      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                 :      58400 : 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                 :      58400 :     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                 :       3777 : 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   [ +  -  +  - ]:       3777 :     assert(max.count() > 0);
      95   [ -  +  -  + ]:       3777 :     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                 :            : /**
     114                 :            :  * Gather entropy from various sources, feed it into the internal PRNG, and
     115                 :            :  * generate random data using it.
     116                 :            :  *
     117                 :            :  * This function will cause failure whenever the OS RNG fails.
     118                 :            :  *
     119                 :            :  * Thread-safe.
     120                 :            :  */
     121                 :            : void GetStrongRandBytes(Span<unsigned char> bytes) noexcept;
     122                 :            : 
     123                 :            : /**
     124                 :            :  * Gather entropy from various expensive sources, and feed them to the PRNG state.
     125                 :            :  *
     126                 :            :  * Thread-safe.
     127                 :            :  */
     128                 :            : void RandAddPeriodic() noexcept;
     129                 :            : 
     130                 :            : /**
     131                 :            :  * Gathers entropy from the low bits of the time at which events occur. Should
     132                 :            :  * be called with a uint32_t describing the event at the time an event occurs.
     133                 :            :  *
     134                 :            :  * Thread-safe.
     135                 :            :  */
     136                 :            : void RandAddEvent(const uint32_t event_info) noexcept;
     137                 :            : 
     138                 :            : /**
     139                 :            :  * Fast randomness source. This is seeded once with secure random data, but
     140                 :            :  * is completely deterministic and does not gather more entropy after that.
     141                 :            :  *
     142                 :            :  * This class is not thread-safe.
     143                 :            :  */
     144                 :            : class FastRandomContext
     145                 :            : {
     146                 :            : private:
     147                 :            :     bool requires_seed;
     148                 :            :     ChaCha20 rng;
     149                 :            : 
     150                 :            :     uint64_t bitbuf;
     151                 :            :     int bitbuf_size;
     152                 :            : 
     153                 :            :     void RandomSeed();
     154                 :            : 
     155                 :      98182 :     void FillBitBuffer()
     156                 :            :     {
     157                 :      98182 :         bitbuf = rand64();
     158                 :      98182 :         bitbuf_size = 64;
     159                 :      98182 :     }
     160                 :            : 
     161                 :            : public:
     162                 :            :     explicit FastRandomContext(bool fDeterministic = false) noexcept;
     163                 :            : 
     164                 :            :     /** Initialize with explicit seed (only for testing) */
     165                 :            :     explicit FastRandomContext(const uint256& seed) noexcept;
     166                 :            : 
     167                 :            :     // Do not permit copying a FastRandomContext (move it, or create a new one to get reseeded).
     168                 :            :     FastRandomContext(const FastRandomContext&) = delete;
     169                 :            :     FastRandomContext(FastRandomContext&&) = delete;
     170                 :            :     FastRandomContext& operator=(const FastRandomContext&) = delete;
     171                 :            : 
     172                 :            :     /** Move a FastRandomContext. If the original one is used again, it will be reseeded. */
     173                 :            :     FastRandomContext& operator=(FastRandomContext&& from) noexcept;
     174                 :            : 
     175                 :            :     /** Generate a random 64-bit integer. */
     176                 :     142493 :     uint64_t rand64() noexcept
     177                 :            :     {
     178   [ +  +  +  - ]:     142493 :         if (requires_seed) RandomSeed();
     179                 :     142493 :         std::array<std::byte, 8> buf;
     180         [ +  - ]:     142493 :         rng.Keystream(buf);
     181   [ +  -  +  - ]:     142493 :         return ReadLE64(UCharCast(buf.data()));
     182                 :     142493 :     }
     183                 :            : 
     184                 :            :     /** Generate a random (bits)-bit integer. */
     185                 :     606691 :     uint64_t randbits(int bits) noexcept
     186                 :            :     {
     187         [ +  + ]:     606691 :         if (bits == 0) {
     188                 :       5347 :             return 0;
     189         [ +  + ]:     601344 :         } else if (bits > 32) {
     190                 :      44311 :             return rand64() >> (64 - bits);
     191                 :            :         } else {
     192   [ +  +  +  - ]:     557033 :             if (bitbuf_size < bits) FillBitBuffer();
     193                 :     557033 :             uint64_t ret = bitbuf & (~uint64_t{0} >> (64 - bits));
     194                 :     557033 :             bitbuf >>= bits;
     195                 :     557033 :             bitbuf_size -= bits;
     196                 :     557033 :             return ret;
     197                 :     557033 :         }
     198                 :     606691 :     }
     199                 :            : 
     200                 :            :     /** Generate a random integer in the range [0..range).
     201                 :            :      * Precondition: range > 0.
     202                 :            :      */
     203                 :     446863 :     uint64_t randrange(uint64_t range) noexcept
     204                 :            :     {
     205         [ +  - ]:     446863 :         assert(range);
     206                 :     446863 :         --range;
     207                 :     446863 :         int bits = std::bit_width(range);
     208                 :     606691 :         while (true) {
     209                 :     606691 :             uint64_t ret = randbits(bits);
     210         [ +  + ]:     606691 :             if (ret <= range) return ret;
     211         [ +  + ]:     606691 :         }
     212                 :     446863 :     }
     213                 :            : 
     214                 :            :     /** Generate random bytes. */
     215                 :            :     template <typename B = unsigned char>
     216                 :            :     std::vector<B> randbytes(size_t len);
     217                 :            : 
     218                 :            :     /** Fill a byte Span with random bytes. */
     219                 :            :     void fillrand(Span<std::byte> output);
     220                 :            : 
     221                 :            :     /** Generate a random 32-bit integer. */
     222                 :          0 :     uint32_t rand32() noexcept { return randbits(32); }
     223                 :            : 
     224                 :            :     /** generate a random uint256. */
     225                 :            :     uint256 rand256() noexcept;
     226                 :            : 
     227                 :            :     /** Generate a random boolean. */
     228                 :          0 :     bool randbool() noexcept { return randbits(1); }
     229                 :            : 
     230                 :            :     /** Return the time point advanced by a uniform random duration. */
     231                 :            :     template <typename Tp>
     232                 :          0 :     Tp rand_uniform_delay(const Tp& time, typename Tp::duration range)
     233                 :            :     {
     234                 :          0 :         return time + rand_uniform_duration<Tp>(range);
     235                 :            :     }
     236                 :            : 
     237                 :            :     /** Generate a uniform random duration in the range from 0 (inclusive) to range (exclusive). */
     238                 :            :     template <typename Chrono>
     239                 :          0 :     typename Chrono::duration rand_uniform_duration(typename Chrono::duration range) noexcept
     240                 :            :     {
     241                 :            :         using Dur = typename Chrono::duration;
     242   [ #  #  #  #  :          0 :         return range.count() > 0 ? /* interval [0..range) */ Dur{randrange(range.count())} :
             #  #  #  # ]
     243   [ #  #  #  #  :          0 :                range.count() < 0 ? /* interval (range..0] */ -Dur{randrange(-range.count())} :
          #  #  #  #  #  
          #  #  #  #  #  
                   #  # ]
     244   [ #  #  #  # ]:          0 :                                    /* interval [0..0] */ Dur{0};
     245                 :            :     };
     246                 :            : 
     247                 :            :     // Compatibility with the UniformRandomBitGenerator concept
     248                 :            :     typedef uint64_t result_type;
     249                 :          0 :     static constexpr uint64_t min() { return 0; }
     250                 :          0 :     static constexpr uint64_t max() { return std::numeric_limits<uint64_t>::max(); }
     251                 :          0 :     inline uint64_t operator()() noexcept { return rand64(); }
     252                 :            : };
     253                 :            : 
     254                 :            : /** More efficient than using std::shuffle on a FastRandomContext.
     255                 :            :  *
     256                 :            :  * This is more efficient as std::shuffle will consume entropy in groups of
     257                 :            :  * 64 bits at the time and throw away most.
     258                 :            :  *
     259                 :            :  * This also works around a bug in libstdc++ std::shuffle that may cause
     260                 :            :  * type::operator=(type&&) to be invoked on itself, which the library's
     261                 :            :  * debug mode detects and panics on. This is a known issue, see
     262                 :            :  * https://stackoverflow.com/questions/22915325/avoiding-self-assignment-in-stdshuffle
     263                 :            :  */
     264                 :            : template <typename I, typename R>
     265                 :       2126 : void Shuffle(I first, I last, R&& rng)
     266                 :            : {
     267   [ +  +  #  #  :      78009 :     while (first != last) {
             #  #  #  # ]
     268                 :      75883 :         size_t j = rng.randrange(last - first);
     269   [ +  +  #  #  :      75883 :         if (j) {
             #  #  #  # ]
     270                 :            :             using std::swap;
     271                 :      70204 :             swap(*first, *(first + j));
     272                 :      70204 :         }
     273                 :      75883 :         ++first;
     274                 :      75883 :     }
     275                 :       2126 : }
     276                 :            : 
     277                 :            : /* Number of random bytes returned by GetOSRand.
     278                 :            :  * When changing this constant make sure to change all call sites, and make
     279                 :            :  * sure that the underlying OS APIs for all platforms support the number.
     280                 :            :  * (many cap out at 256 bytes).
     281                 :            :  */
     282                 :            : static const int NUM_OS_RANDOM_BYTES = 32;
     283                 :            : 
     284                 :            : /** Get 32 bytes of system entropy. Do not use this in application code: use
     285                 :            :  * GetStrongRandBytes instead.
     286                 :            :  */
     287                 :            : void GetOSRand(unsigned char* ent32);
     288                 :            : 
     289                 :            : /** Check that OS randomness is available and returning the requested number
     290                 :            :  * of bytes.
     291                 :            :  */
     292                 :            : bool Random_SanityCheck();
     293                 :            : 
     294                 :            : /**
     295                 :            :  * Initialize global RNG state and log any CPU features that are used.
     296                 :            :  *
     297                 :            :  * Calling this function is optional. RNG state will be initialized when first
     298                 :            :  * needed if it is not called.
     299                 :            :  */
     300                 :            : void RandomInit();
     301                 :            : 
     302                 :            : #endif // BITCOIN_RANDOM_H