12
\$\begingroup\$

I devised a tiny pseudo-random engine and I wondered if it would be considered decent or even good.

It is based on a SHA256 implementation and uses a single 32-bytes state variable.

On seeding, the seed is hashed and that's the initial state of the engine. Then, for each new pseudo-random number, the state is hashed, its first byte is popped and the first byte of the hash is pushed at the end of the state (...as in "shifting left").

The requested pseudo-random number is extracted directly from the state hashed state (e.g. a 64-bits integer can be served from the first 4 bytes of the state variable hashed state).

All this is based on the assumption that SHA256 produces "uniform" distribution (i.e. for an infinite number of distinct inputs, the occurence of 1 or 0 for every bit of the hash is very close to 50%).

Here is my C++ implementation (please ignore the util:: namespace; the SHA256 implementation I use can be found here):

random_engine.h

#pragma once

#include <SHA256/SHA256.h>
#include <array>

namespace util {

    class random_engine_t {
    private:

        std::array<uint8_t, 32>
            m_state;

    public:

        random_engine_t(const uint8_t* seed, size_t slen);

        random_engine_t(const char* seed);

        random_engine_t(const time_t seed);

        template<typename T>
        T next() {
            static_assert(sizeof(T) <= 32);

            SHA256 sha; sha.update(m_state.data(), m_state.size());
            uint8_t* digest = sha.digest();
            T t = *reinterpret_cast<T*>(digest);
            //update seed
            {
                //shuffle back
                for (size_t s = 1; s < m_state.size(); s++) {
                    m_state[s - 1] = m_state[s];
                }
                //set last byte from digest
                m_state[m_state.size() - 1] = digest[0];
            }
            delete[] digest;
            return t;
        }
    };
}

random_engine.cpp

#include <util/random_engine_t.h>

namespace util {

    random_engine_t::random_engine_t(const uint8_t* seed, size_t slen) {
        SHA256 sha; sha.update(seed, slen);
        uint8_t* digest = sha.digest();//initial state
        {
            std::copy(digest, digest + 32, m_state.data());
        }
        delete[] digest;
    }

    random_engine_t::random_engine_t(const char* seed) :
        random_engine_t(reinterpret_cast<const uint8_t*>(seed), strlen(seed)) {}

    random_engine_t::random_engine_t(const time_t seed) :
        random_engine_t(reinterpret_cast<const uint8_t*>(&seed), sizeof(time_t)) {}
}

The next() function is templated but is meant only for integer types.

Is there any obvious flaw with this design that I'm not seeing ?

\$\endgroup\$
13
  • 24
    \$\begingroup\$ Calling into an entire SHA256 is not particularly "tiny" \$\endgroup\$
    – Reinderien
    Commented Oct 16, 2022 at 12:51
  • 12
    \$\begingroup\$ Nor is allocating memory from the global allocator every time you want a random number. \$\endgroup\$
    – indi
    Commented Oct 16, 2022 at 13:12
  • 12
    \$\begingroup\$ @G.Sliepen Complexity is relative. Quality aside, libc typically implements rand() in about two lines of code. \$\endgroup\$
    – Reinderien
    Commented Oct 16, 2022 at 13:27
  • 6
    \$\begingroup\$ @Reinderien True, rand() is laughably tiny and laughably bad :) \$\endgroup\$
    – G. Sliepen
    Commented Oct 16, 2022 at 13:31
  • 4
    \$\begingroup\$ @Reinderien: If you want short and simple, and also still fairly good, xoroshiro256++ or ** has the same state size, and is cheaper to compute. Just a couple 64-bit rotates and shifts, a few XORs, and a couple additions. prng.di.unimi.it / prng.di.unimi.it/xoshiro256plusplus.c \$\endgroup\$ Commented Oct 17, 2022 at 4:47

2 Answers 2

17
\$\begingroup\$

Possibility of short cycles

SHA256 is a cryptographically secure hash function, which indeed means the output is very uncorrelated to the input. However, given exactly the same input, it will always give the same output. That implies that if, after a while, the state will return to an earlier value, you will have entered a cycle. If this cycle is short, then the quality of your random number generator has also dropped significantly.

Note that the probability that you enter a cycle is 100%, the only question is how long it will take given the initial seed, and how long the cycle will be.

One way prevent short cycles from happening is to ensure the state is not updated based on the hash function itself. If you would just treat the state as a 256 bit counter, and increment the counter by 1 each time next() is called, you are guaranteed to have the longest possible cycle (\$2^{256}\$). See also this Cryptography question.

Unsafe use of reinterpret_cast<>()

You should not use reinterpret_cast<>() to create a T from m_state. Consider that T might have different alignment restrictions than m_state, for example T might be a 64-bit integer or floating point number. Instead, create a default-constructed T and std::copy() the memory from m_state into t. Also note that all of this is only legal if T is a trivial type, so you might want to add a static_assert() or restrict the template parameter to verify that.

Make more use of STL algorithms

You are already using std::copy() in the constructor, you can also use it to shift the state by one byte.

\$\endgroup\$
6
  • 3
    \$\begingroup\$ Falling into a cycle short enough to be recognizable as a cycle is fantastically unlikely. From a practical perspective, repeated SHA256 does not cycle. \$\endgroup\$
    – Sneftel
    Commented Oct 18, 2022 at 8:23
  • 1
    \$\begingroup\$ "and std::copy() the memory" - "std::memcpy" probably \$\endgroup\$
    – panik
    Commented Oct 23, 2022 at 15:25
  • \$\begingroup\$ @Sneftel It's not the same as repeated SHA256, it shifts one new byte in at a time. Probably it is still fantastically unlikely, but why risk it when it can be avoided entirely? \$\endgroup\$
    – G. Sliepen
    Commented Nov 4, 2022 at 20:47
  • \$\begingroup\$ @G.Sliepen why would you expect that to have a significantly different expected cycle length than repeated SHA256? That would only be the case if SHA256 is broken. \$\endgroup\$
    – Sneftel
    Commented Nov 4, 2022 at 21:56
  • \$\begingroup\$ @Sneftel It is extremely dangerous to assume that some construct built on top of SHA256 is safe just because SHA256 is safe. I've learned that lesson in the past. While what OP did looks safe to me as well, I don't want to spend effort proving that when it can avoided altogether. \$\endgroup\$
    – G. Sliepen
    Commented Nov 5, 2022 at 10:59
24
\$\begingroup\$

Your question has two parts:

  1. Is the algorithm good?
  2. Is the implementation good?

The first part is not really the purview of code review, because it is not only a mathematical question, it is an extremely complex mathematical question.

Designing a new pseudo-random number generator (PRNG) algorithm is not a simple thing. One cannot simply look at the code of a PRNG and determine whether it is good or bad. To evaluate a PRNG, you need a room full of PhD’s, all using advanced statistical techniques, running weeks of tests on supercomputers. And then you need to publish those results in scholarly journals for peer review. There’s a reason PRNGs are named after their inventors; it’s a big deal when you actually invent a good one.

So there is no possible way I can even begin to evaluate whether your idea is good or not. I know nothing about the PRNG’s characteristics—what is it’s period, for example? I’d need to run weeks of tests to even figure out if it actually generates anything even approximating randomness at all.

So no one here can possibly review the quality of the design. What we can do is review this particular implementation. That won’t help much if the algorithm is hot garbage; even a perfect implementation of a garbage algorithm is still garbage.

I can note this much though: While a 32-byte state is relatively small… it’s hardly “tiny”. Both std::minstd_rand and std::minstd_rand0 have only something like a single std::uint_fast32_t of state (which is 4 or 8 bytes, usually). And among non-standard PRNGs, the excellent taus88 PRNG—available in Boost, for example—has only 12 bytes of state, is super-fast, and has a decent period considering its tiny size.

I would also point out that you’re misrepresenting the size of the state when you say it’s only 32 bytes… because you’re not counting the size of the state of the SHA256 implementation. Granted, that’s ephemeral, but it’s not zero. And it’s not trivial.

Design review

My biggest objection to the design is that it doesn’t conform to the standard PRNG interface… making it practically useless in general. I can’t use it in shuffle(), for example, and I can’t use it with any distributions (what if I want a normal distribution, for example).

It isn’t hard to make a standard-conforming PRNG. The concept only requires:

  1. a result_type
  2. a static min() function
  3. a static max() function; and
  4. operator().

Aside from that, most of the problems with the design here stem from the SHA256 implementation. In other words, wherever the code here is bad, it’s usually due to the crappy SHA256 interface. I mean, seriously… returning a raw owning pointer? What is this, 1985?

Also, the fact that the SHA256 implementation allocates memory is pretty much going to kill any performance dreams you might have.

Using a better SHA256 implementation would fix most of the problems, but even if using hardware SHA256 support (via intrinsics) I suspect it will still be fairly slow.

Code review

        std::array<uint8_t, 32>
            m_state;

That should be std::uint8_t. And you should include the appropriate header: <cstdint>.

        random_engine_t(const uint8_t* seed, size_t slen);

You don’t specify what version of C++ you’re targeting, so I’ll assume the current version: C++20.

Taking a pointer and a size is old school. In modern C++, you should prefer iterators or ranges… preferably the latter.

Theoretically, you only need an input range… but because of the SHA256 interface, you’re forced to require a contiguous range. (Or you could take an input range, and if it’s not contiguous, copy it into a vector, and then that use that with the SHA256 interface. Yeah, that’s ugly, but… as I said, it’s a crappy interface.)

So if you’re forced to use a contiguous range, you could take it, wrap it in a span, and then use as_bytes() to get a view of the raw bytes, and pass that to the SHA256 interface.

That alone would be the only constructor you should need.

        random_engine_t(const char* seed);

First, this should definitely be explicit.

Second, I don’t see the point of taking a C-string rather than a string_view, which would not only handle any kind of string, it would even be significantly faster in most cases, because you wouldn’t need to get the size.

But of course, a string_view is also a contiguous range, so it could be handled by a generic contiguous range constructor.

        random_engine_t(const time_t seed);

Again, should be explicit.

Also, should be std::time_t, and you need the proper header.

But from a design standpoint, this constructor seems like a bad idea, because it is generally advised not to seed PRNGs with the time. It’s bad for security, and it’s bad if the program may be run several times in quick succession (std::time_t often only has a precision of one second… which pretty huge in computer time). With the standard random library, the common practice is to seed using std::random_device, which is (hopefully) a non-deterministic hardware entropy source.

If someone doesn’t care and really wants to seed the time, fine… but that doesn’t mean you should make it easy.

        template<typename T>
        T next() {
            static_assert(sizeof(T) <= 32);

You mentioned that T should be an integral type, but you do nothing to enforce it. If you have static_assert(), you have std::is_integral… and if you have static_assert() without a message, then you have std::is_integral_v. You could easily add static_assert(std::is_integral_v<T>).

As of C++20, though, a better option would be to use the std::integral concept.

            SHA256 sha; sha.update(m_state.data(), m_state.size());

Don’t jam multiple statements together. One statement per line, please.

            uint8_t* digest = sha.digest();

Alright, so you’re stuck using an API that actually returns an owning raw pointer. That’s terrible, but you shouldn’t make the situation worse. You should immediately put that owning raw pointer into a smart pointer. delete is a code smell.

So this line should be something like:

auto digest = std::unique_ptr<std::uint8_t[]>{sha.digest()};

And, of course, remove the delete[] line.

            T t = *reinterpret_cast<T*>(digest);

You have a bug here. You cannot assume the memory allocated by the SHA256 interface is appropriately aligned for a T. That cast (or the subsequent access) may trigger a fault on some hardware. In general, reinterpret_cast is a code smell.

Just do auto t = T{};, then copy the bytes from the digest into t.

                //shuffle back
                for (size_t s = 1; s < m_state.size(); s++) {
                    m_state[s - 1] = m_state[s];
                }

Don’t write raw for loops, especially when it’s just a standard algorithm. In this case, that loop is just std::ranges::shift_left(m_state, 1);.

                m_state[m_state.size() - 1] = digest[0];

This would be much more readable as just m_state.back() = digest[0];.

And, also:

            std::copy(digest, digest + 32, m_state.data());

This could be simpler with copy_n().

\$\endgroup\$
4
  • 2
    \$\begingroup\$ It's not so much that evaluating a "good PRNG" is mathematically difficult, it's more that it's an ill-specified problem. For many monte carlo algorithms, even RANDU is actually perfectly ok to use, although it's from a modern perspective a catastrophically bad PRNG. The current standard PRNGs are good for current applications, but it may well happen that a completely new sort of domain arises in 10 years where they turn out to be unusable (perhaps some AI adversarial issue or so). \$\endgroup\$ Commented Oct 17, 2022 at 11:20
  • 6
    \$\begingroup\$ "So there is no possible way I can even begin to evaluate whether your idea is good or not." It is true that you cannot begin to evaluate if the idea is good, but it is very easy to demonstrate that this idea is bad. The current implementation allows the caller complete knowledge of internal state after 32 calls. That's bad. \$\endgroup\$ Commented Oct 17, 2022 at 20:47
  • \$\begingroup\$ @MooingDuck I'm sorry but I don't see why leaking the internal state is an issue. Anyone who has knowledge of the header knows where the state data is situated and can copy it with a simple memcpy. Care to enlighten me? If that's really an issue, one could use m_state.back() = (digest[0] ^ 0xff);... I guess. \$\endgroup\$
    – PinkTurtle
    Commented Oct 19, 2022 at 12:13
  • \$\begingroup\$ Well, in a video game, that means a character only needs to do 32 things that use the RNG, and then from then on, they can accurately predict every "random" thing that happens for the rest of the game. hit/miss/crit, the next card in the deck, etc. It gets even worse if you try to use this PRNG for anything involving security. This is a hacker's dream come true. \$\endgroup\$ Commented Oct 19, 2022 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.