Choosing the right randomness interface

251
252    /** Generate a random integer in the range [0..range), with range > 0. */
253    template<std::integral I>
254    I randrange(I range) noexcept
255    {
256        static_assert(std::numeric_limits<I>::max() <= std::numeric_limits<uint64_t>::max());
257        Assume(range > 0);
258        uint64_t maxval = range - 1U;
259        int bits = std::bit_width(maxval);
260        while (true) {
261            uint64_t ret = Impl().randbits(bits);
262            if (ret <= maxval) return ret;
263        }
264    }
265
266    /** Fill a span with random bytes. */
267    void fillrand(std::span<std::byte> span) noexcept
268    {
269        while (span.size() >= 8) {
270            uint64_t gen = Impl().rand64();
271            WriteLE64(span.data(), gen);
272            span = span.subspan(8);
273        }
274        if (span.size() >= 4) {
275            uint32_t gen = Impl().rand32();
276            WriteLE32(span.data(), gen);
277            span = span.subspan(4);
278        }
279        while (span.size()) {
280            span[0] = std::byte(Impl().template randbits<8>());
281            span = span.subspan(1);
282        }
283    }
284
285    /** Generate a random integer in its entire (non-negative) range. */
286    template<std::integral I>
287    I rand() noexcept
288    {
289        static_assert(std::numeric_limits<I>::max() <= std::numeric_limits<uint64_t>::max());
290        static constexpr auto BITS = std::bit_width(uint64_t(std::numeric_limits<I>::max()));
291        static_assert(std::numeric_limits<I>::max() == std::numeric_limits<uint64_t>::max() >> (64 - BITS));
292        return I(Impl().template randbits<BITS>());
293    }
294
295    /** Generate random bytes. */
296    template <BasicByte B = unsigned char>
297    std::vector<B> randbytes(size_t len) noexcept
298    {
299        std::vector<B> ret(len);
300        Impl().fillrand(MakeWritableByteSpan(ret));
301        return ret;
302    }
303
304    /** Generate fixed-size random bytes. */
305    template <size_t N, BasicByte B = std::byte>
306    std::array<B, N> randbytes() noexcept
307    {
308        std::array<B, N> ret;
309        Impl().fillrand(MakeWritableByteSpan(ret));
310        return ret;
311    }
312
313    /** Generate a random 32-bit integer. */
314    uint32_t rand32() noexcept { return Impl().template randbits<32>(); }
315
316    /** generate a random uint256. */
317    uint256 rand256() noexcept
318    {
319        uint256 ret;
320        Impl().fillrand(MakeWritableByteSpan(ret));
321        return ret;
322    }
323
324    /** Generate a random boolean. */
325    bool randbool() noexcept { return Impl().template randbits<1>(); }
326
327    /** Return the time point advanced by a uniform random duration. */
328    template <typename Tp>
329    Tp rand_uniform_delay(const Tp& time, typename Tp::duration range) noexcept
330    {
331        return time + Impl().template rand_uniform_duration<Tp>(range);
332    }
333
334    /** Generate a uniform random duration in the range from 0 (inclusive) to range (exclusive). */
335    template <typename Chrono> requires StdChronoDuration<typename Chrono::duration>
336    typename Chrono::duration rand_uniform_duration(typename Chrono::duration range) noexcept
337    {
338        using Dur = typename Chrono::duration;
339        return range.count() > 0 ? /* interval [0..range) */ Dur{Impl().randrange(range.count())} :
340               range.count() < 0 ? /* interval (range..0] */ -Dur{Impl().randrange(-range.count())} :
341                                   /* interval [0..0] */ Dur{0};
342    };
343
344    /** Generate a uniform random duration in the range [0..max). Precondition: max.count() > 0 */
345    template <StdChronoDuration Dur>
346    Dur randrange(std::common_type_t<Dur> range) noexcept
347    // Having the compiler infer the template argument from the function argument
348    // is dangerous, because the desired return value generally has a different
349    // type than the function argument. So std::common_type is used to force the
350    // call site to specify the type of the return value.
351    {
352        return Dur{Impl().randrange(range.count())};
353    }
354
355    /**
356     * Return a duration sampled from an exponential distribution
357     * (https://en.wikipedia.org/wiki/Exponential_distribution). Successive events
358     * whose intervals are distributed according to this form a memoryless Poisson
359     * process. This should be used for repeated network events (e.g. sending a
360     * certain type of message) to minimize leaking information to observers.
361     *
362     * The probability of an event occurring before time x is 1 - e^-(x/a) where a
363     * is the average interval between events.
364     * */
365    std::chrono::microseconds rand_exp_duration(std::chrono::microseconds mean) noexcept
366    {
367        using namespace std::chrono_literals;
368        auto unscaled = MakeExponentiallyDistributed(Impl().rand64());
369        return std::chrono::duration_cast<std::chrono::microseconds>(unscaled * mean + 0.5us);
370    }
371
372    // Compatibility with the UniformRandomBitGenerator concept
373    typedef uint64_t result_type;
374    static constexpr uint64_t min() noexcept { return 0; }
375    static constexpr uint64_t max() noexcept { return std::numeric_limits<uint64_t>::max(); }
376    inline uint64_t operator()() noexcept { return Impl().rand64(); }
377};
378
379/**
380 * Fast randomness source. This is seeded once with secure random data, but
381 * is completely deterministic and does not gather more entropy after that.
382 *
383 * This class is not thread-safe.
384 */
385class FastRandomContext : public RandomMixin<FastRandomContext>
386{
387private:
388    bool requires_seed;
389    ChaCha20 rng;
390
391    void RandomSeed() noexcept;
392
393public:
394    /** Construct a FastRandomContext with GetRandHash()-based entropy (or zero key if fDeterministic). */
395    explicit FastRandomContext(bool fDeterministic = false) noexcept;
396
397    /** Initialize with explicit seed (only for testing) */
398    explicit FastRandomContext(const uint256& seed) noexcept;
399
400    /** Reseed with explicit seed (only for testing). */
401    void Reseed(const uint256& seed) noexcept;
402
403    /** Generate a random 64-bit integer. */
404    uint64_t rand64() noexcept
405    {
406        if (requires_seed) RandomSeed();
407        std::array<std::byte, 8> buf;
408        rng.Keystream(buf);
409        return ReadLE64(buf.data());
410    }
411
412    /** Fill a byte span with random bytes. This overrides the RandomMixin version. */
413    void fillrand(std::span<std::byte> output) noexcept;
414};
415
416/** xoroshiro128++ PRNG. Extremely fast, not appropriate for cryptographic purposes.
417 *
418 * Memory footprint is very small, period is 2^128 - 1.
419 * This class is not thread-safe.
420 *
421 * Reference implementation available at https://prng.di.unimi.it/xoroshiro128plusplus.c
422 * See https://prng.di.unimi.it/
423 */
424class InsecureRandomContext : public RandomMixin<InsecureRandomContext>
425{
426    uint64_t m_s0;
427    uint64_t m_s1;
428
429    [[nodiscard]] constexpr static uint64_t SplitMix64(uint64_t& seedval) noexcept
430    {
431        uint64_t z = (seedval += 0x9e3779b97f4a7c15);
432        z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
433        z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
434        return z ^ (z >> 31);
435    }
436
437public:
438    constexpr explicit InsecureRandomContext(uint64_t seedval) noexcept
439        : m_s0(SplitMix64(seedval)), m_s1(SplitMix64(seedval)) {}
440
441    constexpr void Reseed(uint64_t seedval) noexcept
442    {
443        FlushCache();
444        m_s0 = SplitMix64(seedval);
445        m_s1 = SplitMix64(seedval);
446    }
447
448    constexpr uint64_t rand64() noexcept
449    {
450        uint64_t s0 = m_s0, s1 = m_s1;
451        const uint64_t result = std::rotl(s0 + s1, 17) + s0;
452        s1 ^= s0;
453        m_s0 = std::rotl(s0, 49) ^ s1 ^ (s1 << 21);
454        m_s1 = std::rotl(s1, 28);
455        return result;
456    }
457};
458
459
460/* ==================== CONVENIENCE FUNCTIONS FOR COMMONLY USED RANDOMNESS ==================== */
461
462/** Generate a random uint256. */
463inline uint256 GetRandHash() noexcept
464{
465    uint256 hash;
466    GetRandBytes(hash);
467    return hash;
468}
469
470/* ============================= MISCELLANEOUS TEST-ONLY FUNCTIONS ============================= */
471
472/** Check that OS randomness is available and returning the requested number
473 * of bytes.
474 */
475bool Random_SanityCheck();
476
477#endif // BITCOIN_RANDOM_H
478