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 */
83void RandomInit();
84
85/**
86 * Gather entropy from various expensive sources, and feed them to the PRNG state.
87 *
88 * Thread-safe.
89 */
90void 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 */
98void 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 */
117void 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 */
129void 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.
142template<typename T>
143class RandomMixin;
144
145/** A concept for RandomMixin-based random number generators. */
146template<typename T>
147concept 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. */
155template<typename T>
156concept 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. */
162double 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 */
173template<typename T>
174class RandomMixin
175{
176private:
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
187protected:
188    constexpr void FlushCache() noexcept
189    {
190        bitbuf = 0;
191        bitbuf_size = 0;
192    }
193
194public:
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    }