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  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      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  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      assert(max.count() > 0);
 95      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      void FillBitBuffer()
156      {
157          bitbuf = rand64();
158          bitbuf_size = 64;
159      }
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      uint64_t rand64() noexcept
177      {
178          if (requires_seed) RandomSeed();
179          std::array<std::byte, 8> buf;
180          rng.Keystream(buf);
181          return ReadLE64(UCharCast(buf.data()));
182      }
183  
184      /** Generate a random (bits)-bit integer. */
185      uint64_t randbits(int bits) noexcept
186      {
187          if (bits == 0) {
188              return 0;
189          } else if (bits > 32) {
190              return rand64() >> (64 - bits);
191          } else {
192              if (bitbuf_size < bits) FillBitBuffer();
193              uint64_t ret = bitbuf & (~uint64_t{0} >> (64 - bits));
194              bitbuf >>= bits;
195              bitbuf_size -= bits;
196              return ret;
197          }
198      }
199  
200      /** Generate a random integer in the range [0..range).
201       * Precondition: range > 0.
202       */
203      uint64_t randrange(uint64_t range) noexcept
204      {
205          assert(range);
206          --range;
207          int bits = std::bit_width(range);
208          while (true) {
209              uint64_t ret = randbits(bits);
210              if (ret <= range) return ret;
211          }
212      }
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      uint32_t rand32() noexcept { return randbits(32); }
223  
224      /** generate a random uint256. */
225      uint256 rand256() noexcept;
226  
227      /** Generate a random boolean. */
228      bool randbool() noexcept { return randbits(1); }
229  
230      /** Return the time point advanced by a uniform random duration. */
231      template <typename Tp>
232      Tp rand_uniform_delay(const Tp& time, typename Tp::duration range)
233      {
234          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      typename Chrono::duration rand_uniform_duration(typename Chrono::duration range) noexcept
240      {
241          using Dur = typename Chrono::duration;
242          return range.count() > 0 ? /* interval [0..range) */ Dur{randrange(range.count())} :
243                 range.count() < 0 ? /* interval (range..0] */ -Dur{randrange(-range.count())} :
244                                     /* interval [0..0] */ Dur{0};
245      };
246  
247      // Compatibility with the UniformRandomBitGenerator concept
248      typedef uint64_t result_type;
249      static constexpr uint64_t min() { return 0; }
250      static constexpr uint64_t max() { return std::numeric_limits<uint64_t>::max(); }
251      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  void Shuffle(I first, I last, R&& rng)
266  {
267      while (first != last) {
268          size_t j = rng.randrange(last - first);
269          if (j) {
270              using std::swap;
271              swap(*first, *(first + j));
272          }
273          ++first;
274      }
275  }
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