Simulate the number of expected number of duplicate nonces in the Bitcoin block chain

duplicates.cpp

#include <algorithm>
#include <iostream>
#include <random>

constexpr uint16_t REPEATS{100};
constexpr uint32_t BLOCK_HEIGHT{674293};
 
uint16_t run(int seed)
{
    std::seed_seq seq{seed};

    std::vector<uint32_t> nonces(BLOCK_HEIGHT);
    seq.generate(nonces.begin(), nonces.end());  // seed_seq.generate() generates a sequence of 32 bit outputs
    std::sort(nonces.begin(), nonces.end());

    uint16_t duplicates{0};
    auto it = nonces.begin();
    while (it != nonces.end()) {
        auto next = it + 1;
        if (next != nonces.end() && *it == *next) ++duplicates;
        it = next;
    }
    return duplicates;
}

int main()
{
    float total{0};
    for (auto i=0; i<REPEATS; ++i) {
        auto result = run(i);
        std::cout << result << std::endl;
        total += result;
    }
    
    std::cout << "Average = " << total / REPEATS << std::endl;

    return 0;
}

@martinus I'm not sure what you meant exactly by:

initialize the full state just once with seed_seq, and don't recreate the rng between each run

I've changed this slightly to use seed_seq to generate the random entries into a vector and then sort, but I don't know how to initialize the full state just once.

Hi John! it's unfortunately incredibly hard to correctly seed stuff in C++. The mt19937 has a huge state, and to correctly seed it, you need to fill the whole state with random numbers. Something like that:

std::array<std::uint32_t, std::mt19937_64::state_size> seeds;
std::random_device r;
for (auto& n : seeds) {
    n = r();
}
std::seed_seq seq(seeds.begin(), seeds.end());
std::mt19937_64 eng(seq);

I've long since switched to other non-standard random number generators that are much faster, easier to use, and easier to seed. I personally usually use SFC64: https://github.com/martinus/robin-hood-hashing/blob/master/src/test/app/sfc64.h

If you are interested in the seeding issues: https://www.pcg-random.org/posts/cpp-seeding-surprises.html

And here is a bit more about sfc64: https://numpy.org/doc/stable/reference/random/bit_generators/sfc64.html

Wow. Thanks for the detailed reply!