Laughably tiny random engine

Question

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 ?

Answer 1

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.

Answer 2

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().