Hierarchical classes Splittable/Unsplittable Gen

[lehins]

There is currently a totally useless CPP in random:

#ifdef ENABLE_SPLITTABLEGEN
class SplittableGen g where
#endif

which hints at what I am about to suggest.

There are some pure RNGs like mersenne-twister for example, that are not splittable. Question is do we want to bring this distinction to the type level or not? I personally would like to avoid seeing such code:

instance RandomGen PureMT where
   next  = randomInt
   split = error "System.Random.Mersenne.Pure: unable to split the mersenne twister"

There are four approaches I see that we can take:

1. Follow the current path laid out in the code and simply remove the CPP pragmas:

class RandomGen g where
  ...
class RandomGen g => SplittableGen g where
  split    :: g -> (g, g)

• Disadvantage: breaks bunch of code in the wild that depends on split.
• Advantage: none

2. Similar to the above, but use default signatures and deprecation

class RandomGen g where
  ...
  split    :: g -> (g, g)
  default split :: SplittableGen g => g -> (g, g)
  split = splitGen
  {-# DEPRECATED split "In favor of `splitGen`" #-}

class RandomGen g => SplittableGen g where
  splitGen    :: g -> (g, g)

• Disadvantage: eventually it will affect the user code
• Advantage: not a breaking change for RNG libraries

3. Invert the dependency and create an UnsplittableGen (name is up for a debate)

class NoSplitGen g where
  ...
  genWord64 :: g -> (Word64, g)
class NoSplitGen g => RandomGen g where
  split  :: g -> (g, g)

• Advantage: will not break the user code, unless they are using a non-splittable RNG.
• Disadvantage: breaks current RNG libraries, which I think is OK, since they will need to be updated anyways.

4. Not to worry about distinction between splittable/not-splittable and leave it as is:

• Advantages: less changes for everyone
• Disadvantages: partial code in the wild and hard to see the lack/presence of splitability property in th RNG

My favorite is the 3rd one. Any thoughts?

[Shimuuar]

AFAIR most of generators are not splittable. It's very rare and special property. However some PRNGs are able to produce multiple streams of random numbers from same seed. PCG & random123 are examples. So we may want to provide type class for that as well. It's not urgent and could be put off to later date

Nitpick: mersenne-twister is in the same class as mwc-random with huge mutable state. I think pure wrapper does some tricks to amortize update cost.

[peteroupc]

A splittable PRNG can be constructed from any so-called counter-based PRNG, as in the PRNG used by JAX, as well as in the design by Claessen in 2013. In general, a counter-based PRNG uses either a block cipher or a hash function to generate random numbers from a seed and an incrementing counter. For example, JAX's splittable PRNG uses the Threefry hash function, but any other hash function could substitute for Threefry as long as it provides good randomness.

Some of the known constructions for splittable PRNGs are surveyed in "Evaluation of Splittable Pseudo-Random Generators" by H. G. Schaathun, 2015. Some of them are general enough to be used by any PRNG (including Mersenne Twister), but do not necessarily lead to high-quality splittable PRNGs. (EDIT: JuliaLang/julia#34852 is another example of a splittable PRNG, introduced after I started this post.)

By the way, note that what PCG calls "streams" (namely, its use of an additive constant) does not produce independent random number sequences.

[curiousleo]

If I'm reading this correctly, then JuliaLang/julia#34852 (comment) suggests a generic split construction using a hash function:

Use the old state to generate K pseudo-random bits, use them to seed the child RNG; put a random function into the middle

In that thread, MurmurHash (a fast, non-cryptographic hash function) and SHA256 are mentioned. The idea is that split will typically get called many orders of magnitude less frequently than the generator functions, so split can be more expensive.

If this works, then my preferred approach would be as follows:

• the generic RandomGen continues to include split
• we provide a default split implementation based on this idea, using a to-be-determined hash function
• PRNGs that natively support splitting (including counter-based PRNGs) implement split themselves

The advantages of this approach, as I see them:

• the interface is simple; no need to distinguish splittable/unsplittable PRNGs at the API level
• a good default: given a strong hash function, the default split implementation creates independent seeds
• splittable PRNGs can improve performance by implementing their own split

---

An issue that needs a little bit of thought here is: how will we create seeds / instantiate PRNGs in a generic way (i.e. how should split :: g -> (g, g) make a new g)?

This relates to #3 (comment) as well, where it was suggested that random should use OS-specific randomness sources for the purpose of seeding.

To make it explicit, the issue is that we don't know the concrete type of the seed nor how large it is. So in order to instantiate a seed generically, we need to provide it with a source of randomness from which it can consume as much randomness as it needs. Luckily, we already have a typeclass that can provide randomness: RandomGen!

So the simplest thing that comes to mind is something along these lines:

class Seed s where
  mkSeed :: RandomGen g => g -> s

The default split implementation could then work as follows:

• We implement a RandomGen instance that is instantiated using another RandomGen and uses a hash function to implement uniform value generation. Concrete example: we could implement MurmurHashGen, which implements uniformWord64 using murmurhash64 on the output of some other RandomGen.
• The default split instantiates this MurmurHashGen and feeds its output into mkSeed, the result of which is then used to instantiate two new RandomGen of the original type (using restore?)

#3 (comment) could be addressed in a similar way by providing a RandomGen implementation backed by the OS randomness source, which can be fed to mkSeed to instantiate a well-seeded RandomGen of any type.

[lehins]

Even if it s true that any pure RNG can be made splittable by using something like sha256, I really doubt it applies to cryptographic RNGs and we don't want somebody getting excited that they can split ChaCha and falling on that default split implementation and using it for cryptography.

With regards to Seed, we definitely don't want to make it possible to draw randomnesss for the seed from any arbitrary RNG, which is what that Seed class suggests.

Anyways, those are just my concerns and I might be totally wrong and what you are suggesting is totally fine.

[Shimuuar]

I think that adding ability to initialize from some bytestring and exposing how much random bytes generator needs would be enough. Adding ability to serialize generator state back would be certainly helpful too

[lehins]

#10 would make it possible to generate a random ByteArray (consequently ByteString too) using any generator. So all we need from RNG is information about how many bytes it needs for the seed and how to go from ByteArray to the Seed

initialize from some bytestring

[curiousleo]

Even if it s true that any pure RNG can be made splittable by using something like sha256, I really doubt it applies to cryptographic RNGs and we don't want somebody getting excited that they can split ChaCha and falling on that default split implementation and using it for cryptography.

That's a fair point, I had not considered the interaction with CPRNGs here. I need to think about that.

With regards to Seed, we definitely don't want to make it possible to draw randomnesss for the seed from any arbitrary RNG, which is what that Seed class suggests.

I don't see the issue, perhaps you can make it more explicit? However, seeing

I think that adding ability to initialize from some bytestring and exposing how much random bytes generator needs would be enough.

perhaps my problem was that when you have a hammer (RandomGen), everything looks like a nail (mkSeed :: RandomGen g => g -> s).

Still, at least in order to provide the ability to seed from a system randomness source, we need a generic API. If I'm understanding you correctly, this could be something like the following (now without RandomGen):

class Seed s where
  size :: Word64 -- ^ size of the seed in bytes; this is the length in bytes of the argument to 'init'
  init :: ByteArray -> s -- ^ initialize seed; the argument must have 'size' bytes

[lehins]

@curiousleo It is better solved as an associated type family:

random/System/Random.hs

Lines 138 to 144 in 4bb37cf

	class RandomGen g where
	type GenSeed g :: *
	type GenSeed g = Word64
	mkGen :: GenSeed g -> g
	saveGen :: g -> GenSeed g

Only thing is missing something along those lines:

  seedSize :: Proxy g -> Int
  seedInit :: Proxy g -> ByteArray -> GenSeed g

Same approach would be for MonadRandom

[lehins]

@curiousleo Consider drawing bytes for the seed from current StdGen for SMGen(splitmix), this means initial state of the latter is only as good as StdGen. Now elevate to CRNGs and things become even more serious. Does it make sense?

I don't see the issue, perhaps you can make it more explicit? However, seeing

[peteroupc]

Even if it s true that any pure RNG can be made splittable by using something like sha256, I really doubt it applies to cryptographic RNGs and we don't want somebody getting excited that they can split ChaCha and falling on that default split implementation and using it for cryptography.

The hash function involved here need not be SHA-256 or even be a cryptographic quality hash function; any other hash function can be used as long as the resulting splittable PRNG provides adequate randomness. The pull request I linked to chose was considering SHA-256 to try to ensure there was "no chance in hell of interacting with" the splittable PRNG's underlying PRNG.

[curiousleo]

@lehins thanks for the example and the clarification.

  seedSize :: Proxy g -> Int
  seedInit :: Proxy g -> ByteArray -> GenSeed g

This is not a great API in my opinion. Concretely, I can think of two important constraints implicit in it that are not expressed on the type level:

• seedSize must be greater than 0
• seedInit must be fed a ByteArray with at least (or exactly?) seedSize bytes

The first one is pretty obvious and the second one is not complicated either, but it strikes me as suboptimal. I tried to side-step these issues with mkSeed, which would let the seed construction algorithm decide how many bytes it wanted to consume. I guess what I was really getting at was something like mkSeed :: ByteStream -> s (or the associated type family equivalent of it).

However, seedSize and seedInit are definitely adequate, they allow us to do what we want to do. So I may be getting into bikeshedding territory here.

[peteroupc]

@chethega : Can you discuss your splittable PRNG construction here?

[Shimuuar]

seedInit must be fed a ByteArray with at least (or exactly?) seedSize bytes

I'm of the opinion that it should work for any byte array. This is approach that mwc-random takes. Missing data is filled from predetermined seed and if too much data is provided it's simply ignored

[chethega]

@chethega : Can you discuss your splittable PRNG construction here?

Sure! So, first of all: My PR over at julialang is not using SHA at all; I was just considering it. Instead, it currently uses some hand-rolled nonsense based on murmur3; simply because the julia repo already had an implementation lying around in some source folder, as a stand-in for whatever will be eventually used.

The only model that I really understand is random oracle. Suppose we have a random oracle function F that maps 32 byte -> 32 byte; we extract 8 bytes of randomness by mapping (state <- F(state); output <- lowest64(state), i.e. newState, output <- F(oldState). (in crypto-speak, they afaik call this an ideal sponge).

That's my RNG. Now to split off a new instance, just extract 32 bytes from the parent RNG, and use it as the initial state of the child RNG. The fact that this gives good properties (in the ideal sponge / random oracle model) is obvious, and probably needs no proof (but I'm sure intro textbooks will have a proof).

In reality, we don't have an ideal sponge / random oracle; we have @vigna's xoshiro256. I don't understand what are weak keys (weak initial states), and what one is allowed to do with it and what not. So my new assumption is the following: People are for unfathomable reasons happy to use xoshiro stream as random stream, so I accept that (axiomatically). Nobody told me how xoshiro can be properly seeded, so the conservative choice is to use something cryptographic -- i.e. transform the childState with a cryptographic random function on splitting. Then, all the nice proofs carry over: If the function is indistinguishable from true random and xoshiro is good enough, then the splitting construct is good enough.

I'd like some statement from @vigna on this: I.e. a statement that the streams from xoshiro(state0) and xoshiro(xoshiro(state0, 4)) are uncorrelated.

The difficult/fancy part for reproducible multithreaded monte-carlo is that we need the state of the RNG to be small enough, and the splitting to be fast enough, to be affordable overhead on task / coroutine spawning, and to teach the runtime to do this. That is super expensive with mersenne twister, and affordable with xoshiro.

The julia community is obsessed with speed (I'm guilty as well) over security, and also desires cross-platform reproducibility of random streams (imo a misguided goal). Therefore the nice feature I want (reproducible multithreaded monte-carlo) only has a chance of getting taken seriously if it doesn't cause any performance regressions, or better blows DSFMT out of the water.

Afaiu you haskell people value correctness over speed.

As such, I would recommend to only provide cryptographic PRNG, and use the same trick to make it task-local (i.e. each task/coroutine owns its own RNG state, and a new one is split from the parent on creation). I would advise to give up on cross-platform reproducibility of random stream on default builds, and chose something reasonably fast as default RNG on each platform: AES-CTR when hardware acceleration is available, chacha12 / salsa12 otherwise. Have a couple #ifdef to switch between them.

Task/coroutine local RNG state introduces some overhead in each coroutine, and needs to be managed by the runtime. Therefore, you can have at most one such local RNG, and it cannot be implemented in haskell (but similar to julia, feel free to also use it directly from haskell if more convenient than C).

[vigna]

I don't know what xoshiro(xoshiro(state0, 4)) means.

The suggested way to do splitting with xoshiro256++ and similar generators is pass a good bijection over the state. The Java code in the DSI Utilities is as follows:

	public XoShiRo256PlusPlusRandom split() {
		final XoShiRo256PlusPlusRandom split = new XoShiRo256PlusPlusRandom();
		split.s0 = HashCommon.murmurHash3(s0);
		split.s1 = HashCommon.murmurHash3(s1);
		split.s2 = HashCommon.murmurHash3(s2);
		split.s3 = HashCommon.murmurHash3(s3);
		return split;
	}

HashCommon.murmurHash3() is simply MurmurHash3's finalizer (the same bijection used by SplitMix64).

If we assume the bijection generates a state that is placed randomly in the generator state space, the probability of overlap of sequences is negligible.

This is fact analogous to what others are doing using ideal sponges etc., just with a different assumption (remember that nobody is using anything that's provably random or uncorrelated—we're always talking about reasonable assumptions based on practical considerations).

As for "independent streams", someone already noted correctly that PCG does not produce independent streams at all. Different starting points in a counter-based generator which uses strong cryptographic primitives might be considered independent, in the sense that dependence would imply breaking somehow the cryptographic primitive (which nobody ever proved being unbreakable in the first place, so we're always running in circles).

Multiplicative congruential generators (i.e., using a prime modulus) have the nice property that the difference of two sequences is a possible sequence emitted by the generator, so it should look random, and linear generators have the same property for the xor of two sequences, which suggests different sequences are pairwise (somewhat) independent. But these are just hints, not proofs.

[chethega]

xoshiro(xoshiro(state0, 4)) was supposed to mean: Extract 4 x i64 from the parent stream, and that's our new initial state. This is kinda scary, so something should be done to fix it.

Thanks a lot for confirming that murmur3 and xoshiro probably don't interact!

Just FYI, in our case we must advance the parent's stream on child creation: Otherwise two children that are created without intermediate random events would share streams. The above java function you posted looks like a giant footgun to me.

Regarding the mixing, is a 64-bit mixing on seed enough? I mean, we have 32 bytes of internal state, and no way of guessing which of these 32 bytes contain any entropy. We'd need a 256 bit mixing function. And the first 4 outputs of xoshiro look very non-random if you fail to seed all 4 state integers. Or is it preferable to simply "warm up" the rng by applying it N times, where e.g. N = 8?

[vigna]

Ouch, I really thought (my bad) that splitting should not disturb the caller's stream. I see your point—indeed, SplittableRandom generates a new instance using nextLong() as seed. I'll fix the library ASAP—thank you for the tip.

I think a next-state operation (before scrambling the state) should be enough: xoroshiro and xoshiro update all words of state, and we're using a mixing function with excellent avalanching properties. You can do more than one round of update if you think one round of mixing is not enough, but it is difficult to measure if you're improving the result in any way. I'd rather use a stronger mixing function (e.g., as you were mentioning, a 256-bit mix function).

Why would you not seed all state? That's not the suggested way to use the generator. Even if you have a small amount of entropy, use it to seed SplitMix64 and initialize all the state (that's the suggested way).

One way of measuring how far you get from the initial state is to use the "escape from zero" stat, that is, starting from a state with exactly one bit set how much time it takes for the state to contain about half zeros, half ones:

     1  0.010742
     2  0.016602
     3  0.029297
     4  0.049316
     5  0.061768
     6  0.094727
     7  0.103760
     8  0.143311
     9  0.188232
    10  0.198730
    11  0.199829
    12  0.239258
    13  0.301514
    14  0.300781
    15  0.290527
    16  0.341675
    17  0.411499
    18  0.419800
    19  0.401489
    20  0.436279
    21  0.436523
    22  0.429688
    23  0.432251
    24  0.459839
    25  0.478027
    26  0.493408
    27  0.496460
    28  0.486450
    29  0.473633
    30  0.475464
    31  0.475952
    32  0.486816

This is the result averaged on all possible 256 starting states with exactly one bit set. It is a ridiculously worst-case analysis, because it tells you how many iterations you need to get a completely different state after you change one bit, and you're potentially changing all bits, and it doesn't take into account the scrambler, but it can be a starting point for a discussion.

[vigna]

BTW, @chethega, if you send me a real name in private I'll add some thanks to the CHANGES file for the DSI Utilities (where the above code lives).

[chethega]

So, could you take a look at the following splitting procedure?

void rng_split(jl_task_t *parent, jl_task_t *child) {
  // fixme: Possibly run some tests (bigcrunch).
  // needs to be relatively fast, paid on every task creation.
  // int64hash is murmur3. Assumes that parent is in steady state 
  /* Discuss: stealing internal state for splitting deviates from sponge model.
   Maybe pay a handful of unneeded extra cycles to be easier to analyze? 
   Conservative alternative (still < 100 cycles on broadwell):
  child->rngState0 = int64hash(jl_tasklocal_genrandom(parent));
  child->rngState1 = int64hash(jl_tasklocal_genrandom(parent));
  child->rngState2 = int64hash(jl_tasklocal_genrandom(parent));
  child->rngState3 = int64hash(jl_tasklocal_genrandom(parent));
  jl_tasklocal_genrandom(child);
  */
  jl_tasklocal_genrandom(parent);
  child->rngState0 = int64hash(parent->rngState0);
  child->rngState1 = int64hash(parent->rngState1);
  child->rngState2 = int64hash(parent->rngState2);
  child->rngState3 = int64hash(parent->rngState3);
  jl_tasklocal_genrandom(child); // pure paranoia, discard first random number from stream
}

Why would you not seed all state? That's not the suggested way to use the generator. Even if you have a small amount of entropy, use it to seed SplitMix64 and initialize all the state (that's the suggested way).

For code that we control, I agree.

But the user-facing API accepts anything as input; it is common to have things like seed!(42) in scripts, i.e. nothing-up-my-sleeve constants. Hence we need to routinely deal with the possibility that user-provided seeds are abysmal. Users can also provide 4 x uint64, so we need to be prepared for e.g. [42, 0, 0, 0]. Otoh performance for user-seeding is irrelevant, so we can just use a cryptographic hash and be done with it.

[curiousleo]

@chethega @vigna thanks for you comments!

This issue is about how to / whether we need to differentiate at the API level between splittable and unsplittable PRNGs. My view is that if we can avoid this complication, we should.

Hence the discussion about a generic split function. The ideal outcome, in my view, would be a default implementation of split that works well with any (well behaved) PRNG. Natively splittable PRNGs could overwrite this with their custom implementation.

It seems to me like such a generic split function may exist in the form of a mixing function. One complication is that a default implementation would need to work for any PRNG, which includes ones with much larger state (e.g. Mersenne Twister).

So the idea would be:

split :: RandomGen g => g -> (g, g)
split gen = (genL, genR) where
  (genL, randomBytes) = uniformByteArray gen seedSize -- generate 'seedSize' random bytes from 'gen'
  stateR = map mix randomBytes -- apply 'mix' to each Word64 in 'r'
  genR = seedInit state -- create a generator from the state

Do we think this would work?

---

I would recommend to only provide cryptographic PRNG

Interesting. My view here is that if a PRNG passes statistical tests, it's good enough for Monte Carlo, games, and similar applications. To me, security relevant code has another set of constraints entirely, and should e.g. pick algorithms explicitly rather than using defaults (unless they're explicitly advertised as being secure building blocks).

@lehins and I benchmarked chacha against non-crypto PRNGs here: lehins/haskell-benchmarks#6

Task/coroutine local RNG state introduces some overhead in each coroutine, and needs to be managed by the runtime. Therefore, you can have at most one such local RNG, and it cannot be implemented in haskell (but similar to julia, feel free to also use it directly from haskell if more convenient than C).

This discussion here is happening in the context of a Haskell library, not a runtime. split would be a function users call explicitly; there is no automatic initialisation of thread-local PRNGs happening here.

Edit: see #12 for a prototype implementation of this idea.

[chethega]

split :: RandomGen g => g -> (g, g)
split gen = (genL, genR) where
  (genL, randomBytes) = uniformByteArray gen seedSize -- generate 'seedSize' random bytes from 'gen'
  stateR = map mix randomBytes -- apply 'mix' to each Word64 in 'r'
  genR = seedInit state -- create a generator from the state

looks good to me. The mix step could be omitted if the seed function is well-behaved, but it is cheap enough to be included as a conservative safety measure.

The API should probably be: Given a source RNG instance, and a destination RNG type, split off a child of dest-type from the source.

The julia PR in discussion used that construct for fast bulk generation of random: When users request a large array, we split off an ephemeral RNG, and use that to fill the array. The ephemeral RNG is never written to heap (realistically it lives in register only, nothing should spill), and has larger state and output size (it only produces 32 byte chunks), and uses pretty fast AVX2 code.

[vigna]

@chethega I think that the version using the output (instead of just copying the internal state) has an advantage: you're using the scrambler, too. Moreover, the next-state function updates all words, it's true, but it's quite sparse, so for example the last word of the next state is just the xor of two previous words, rotated.

On the other hand, with the + and ++ scramblers there's a subtle mathematical issue: you won't get all possible sequences of 4 outputs because those scramblers lose one degree of equidistribution. This means that the probabilistic model in which you consider the new state of the splitted generator a uniformly chosen random state is not correct, as you cannot get all states.

Thus, from a mathematical view point using a scrambled copy of the state after a next-state operation is the right thing to do. I would however do k next() operations on the split generator, where k is the number of words, to spread the effect of the 64-bit mixing function. My present candidate Java code is as follows:

	public XoShiRo256StarStarRandom split() {
		nextLong();
		final XoShiRo256StarStarRandom split = new XoShiRo256StarStarRandom(HashCommon.murmurHash3(s0), HashCommon.murmurHash3(s1), HashCommon.murmurHash3(s2), HashCommon.murmurHash3(s3));
		for(int i = 0; i < 4; i++) split.nextLong();
		return split;
	}

It is possible that it is a bit too much, that is, that you need less iterations. But iterating on these generators is really fast.

Comments are welcome.

[vigna]

Actually, thinking twice about it, iterating does not make any sense. We're simply discarding 4 outputs. It would be interesting, rather, to iterate once and apply the mixing function again. But probably that's too much.

[vigna]

Always continuing my line of thoughts, I think actually the best thing is to have a very good 256-bit mixing function. I plan to use SpookyHash ShortMix sequence, as in

	public XoShiRo256PlusPlusRandomGenerator split() {
		nextLong();
		final XoShiRo256PlusPlusRandomGenerator split = copy();

		long h0 = split.s0;
		long h1 = split.s1;
		long h2 = split.s2;
		long h3 = split.s3;

		// A round of SpookyHash ShortMix
		h2 = Long.rotateLeft(h2, 50);
		h2 += h3;
		h0 ^= h2;
		h3 = Long.rotateLeft(h3, 52);
		h3 += h0;
		h1 ^= h3;
		h0 = Long.rotateLeft(h0, 30);
		h0 += h1;
		h2 ^= h0;
		h1 = Long.rotateLeft(h1, 41);
		h1 += h2;
		h3 ^= h1;
		h2 = Long.rotateLeft(h2, 54);
		h2 += h3;
		h0 ^= h2;
		h3 = Long.rotateLeft(h3, 48);
		h3 += h0;
		h1 ^= h3;
		h0 = Long.rotateLeft(h0, 38);
		h0 += h1;
		h2 ^= h0;
		h1 = Long.rotateLeft(h1, 37);
		h1 += h2;
		h3 ^= h1;
		h2 = Long.rotateLeft(h2, 62);
		h2 += h3;
		h0 ^= h2;
		h3 = Long.rotateLeft(h3, 34);
		h3 += h0;
		h1 ^= h3;
		h0 = Long.rotateLeft(h0, 5);
		h0 += h1;
		h2 ^= h0;
		h1 = Long.rotateLeft(h1, 36);
		h1 += h2;
		h3 ^= h1;

		split.s0 = h0;
		split.s1 = h1;
		split.s2 = h2;
		split.s3 = h3;

		return split;
	}

[curiousleo]

@lehins wrote:

Even if it s true that any pure RNG can be made splittable by using something like sha256, I really doubt it applies to cryptographic RNGs and we don't want somebody getting excited that they can split ChaCha and falling on that default split implementation and using it for cryptography.

In light of the discussion on this thread, is this still a concern you have against including a generic split function?

Misquoting @chethega:

If the [mixing] function is indistinguishable from true random and [the PRNG] is good enough, then the splitting construct is good enough.

Personally, I can see how this applies if the mixing function is a cryptographic one. If I understand @peteroupc correctly, a non-cryptographic mixing function may be sufficient too - #7 (comment).

In #12 I've prototyped this with a variant of MurmurHash3 as the mixing function (non-cryptographic), mainly to show what interface changes would be required to make this work generically.

[lehins]

What I think is the best way forward in light of this information that an RNG can be made splittable is to provide a standalone helper function defaultSplit with explanation how it works and a warning that it cannot be applied to cryptographic RNGs.

This would allow us to keep the interface the same as it is now without splitting the unsplittable class, pun intended. This way we can accommodate the common case, for example making mersenne splittable, without sacrificing safety of CRNGs.

The most important part is that random package cannot decide the behavior of any CRNG beforehand. Even if we come up with some cryptograhically secure way of splitting a CRNG there is a good chance it is not gonna apply to all possible CRNGs, therefore providing default implementation would be wrong. If CRNG is really unsplittable, then split = error "unsplittable" would be an ok implementation. It is better to fail then produce insecure behavior.

[curiousleo]

[...] provide a standalone helper function defaultSplit with explanation how it works and a warning that it cannot be applied to cryptographic RNGs.

If CRNG is really unsplittable, then split = error "unsplittable" would be an ok implementation. It is better to fail then produce insecure behavior.

Just to make sure I'm understanding this proposal: the idea here would be to have

class RandomGen g where
  ...
  split  :: g -> (g, g) -- no default implementation!

defaultSplit :: RandomGen g => g -> (g, g)
defaultSplit g = ...

So that most RNG implementations can say

instance RandomGen MyGen where
  split = defaultSplit -- use the 'defaultSplit' implemented in 'random'

But also have the freedom to deny splitting via split = error "nope" or use their own split implementation.

Did I get that right?

[lehins]

Yes, that is exactly what I meant.17:04, February 28, 2020, Leonhard Markert <[email protected]>: [...] provide a standalone helper function defaultSplit with explanation how it works and a warning that it cannot be applied to cryptographic RNGs. If CRNG is really unsplittable, then split = error "unsplittable" would be an ok implementation. It is better to fail then produce insecure behavior. Just to make sure I'm understanding this proposal: the idea here would be to have class RandomGen g where ... split :: g -> (g, g) -- no default implementation! defaultSplit :: RandomGen g => g -> (g, g) defaultSplit g = ... So that most RNG implementations can say instance RandomGen MyGen where split = defaultSplit -- use the 'defaultSplit' implemented in 'random' But also have the freedom to deny splitting via split = error "nope" or use their own split implementation. Did I get that right? —You are receiving this because you were mentioned.Reply to this email directly, view it on GitHub, or unsubscribe. Отправлено из мобильной Яндекс.Почты: http://m.ya.ru/ymail

[Shimuuar]

I also agree that 3 is best approach. It doesn't break code that uses type class but breaks instances.

Disadvantage: breaks current RNG libraries, which I think is OK, since they will need to be updated anyways.

This is advantage. If we add genWord and friends we must make sure that all instances break. Otherwise they will compile just fine and then will just fail at runtime. Which is I think very poor failure mode

[idontgetoutmuch]

Afaiu you haskell people value correctness over speed.

The main focus of this library is not to provide crypotographic quality random numbers; we want a reasonable trade-off between speed and "randomness". Haskell has had problems with split implementations that have behaved infelicitously and thus we are (well at least I am) a bit cautious about implementing a default split for every RNG.

[idontgetoutmuch]

See also the discussion starting here: #9 (comment)

[curiousleo]

This issue has been inactive for over a month now, closing. For the moment we're going with split being present in RandomGen, but PRNGs that don't support it are supposed to error out: https://htmlpreview.github.io/?https://raw.githubusercontent.com/idontgetoutmuch/random/haddock-preview/docs/System-Random.html#v:split