Move PRNG algorithms out of Rand

@vks

Edit by dhardy: adding a tracker for the planned tasks:

Replace SmallRng algorithm (see Requirements for a small fast RNG dhardy/rand#60 and Shootout: small, fast PRNGs dhardy/rand#52)
Deprecate XorshiftRng (required: that the RNG is available in another crate)
Move ISAAC* to new crate
Publish PCG RNGs somewhere (rand_rngs, rand_pcg or something)
Publish SFC generators somewhere
Review xoshiro crate by @vks
Review state of other published RNGs (see linked comment) and fix up if useful
Document available RNGs (internal and external crates)

Also: we should consider whether we want to rename PRNGs when moving or adding them.

As decided in dhardy#58.

The idea is to only keep the StdRng and SmallRng wrappers in Rand, and to not expose PRNG algorithms directly.

The field of PRNG algorithms is not static, it seems like a good idea to cut Rand partly loose from the developements to improve our backward-compatability and usability story. Advantages (from the original issue)

rand provide easy to reason generator(s) to satisfy the bulk of the users

rand provides low-friction upgrades and keeps the optimal-ish algorithms readily available

rand will not accumulate and/or deprecate specific algorithms throughout time

Specific rand Rng names won't bleed out to the world, like in forum posts, stackoverflow, etc..

Instead we want to provide an official companion crate, rand_rngs, with a couple of blessed implementations.

Whether Rand should depend on rand_rngs or copy the two algorithms used by StdRng and SmallRng is not fully decided. It might reduce code size if a crate depends on both StdRng and its algorithm (currently Hc128Rng) directly, but that seems rare and not worth much. It has the disadvantage that both implementations should remain in sync. Maybe the CI can check this?

If Rand depends on rand_rngs, it would restrict rand_rngs to only depend on rand_core. But that is what rand_core is for. I am for having Rand depend on rand_rngs.

rand_rngs

rand_rngs should provide a good selection of PRNGs.

Including multiple PRNGs in one crate has the advantage of having a single place to provide guidance, as it helps comparing different algorithms with each other. Also it gives one place to offer consistent benchmarks, to run PRNG test suites, to keep up a common quality level, and possibly to develop functionality that is useful for more than one PRNG (e.g. jumping).

Which PRNGs to include has been the topic of endless discussions. A few are basically decided. I fully expect the number of PRNGs to grow over time. But we also should be careful not to expose too many, as there are hundreds. Every PRNG should have one thing that gives it a clear advantage over others, otherwise it is not worth the inclusion.

Normal PRNGs

dhardy#60 explored normal PRNGs. The following 5 I feel comfortable about for an initial version of rand_rngs:

PCG-XSH-RR 64/32 (LCG)
PCG-XSL-RR 128/64 (MCG)
SFC (32-bit variant)
SFC (64-bit variant)
Xoroshiro128+

The two PCG variants offer good quality and reasonable performance. SFC provides high performance and a chaotic PRNG (not a fixed period). Xoroshiro128+ has acceptable quality but high performance.

An PRNG put together by me, XoroshiroMT, is also good quality and sits between PCG and Xoroshiro128+ qua performance. But now that there is just a new Xoshiro PRNG, it may be worth evaluating that one first, as it is said to also be good quality.

CSPRNGs

For CSPRNGs we currently have two good implementations in Rand

ChaCha20
HC-128

ChaCha20 offers reasonably good performance and uses little memory, while HC-128 brings high performance at the cost of using much memory.

I would also like to see some implementation of AES-CTR DRBG eventually, as it is commonly used, and has hardware support on modern desktop processors.

Other / deprecated PRNGs

We currently have the ISAAC, ISAAC-64 and Xorshift128/32 PRNGs in rand. They have no real advantages over the PRNGs metioned before. It is better to use HC-128 instead of ISAAC, and Xoroshiro128+ or PCG instead of Xorshift. We can include them in something like a deprecated module, but I propose to move them to stand-alone crates outside the Rand repository.

Steps to take

move the prngs module to a seperate rand_rngs crate in the Rand repository, similar to rand_core.
move generators benchmarks over.
lift PRNG implementations from https://github.com/pitdicker/small-rngs (I have updated it to master a while ago, but still have to push the changes)
lift Xoroshiro128+ from https://github.com/vks/xoroshiro/

Does this sound about right?

Why not have one crate per RNG?

…

On Sun, May 6, 2018, 15:40 Paul Dicker ***@***.***> wrote: As decided in dhardy#58 <dhardy#58>. The idea is to only keep the StdRng and SmallRng wrappers in Rand, and to not expose PRNG algorithms directly. The field of PRNG algorithms is not static, it seems like a good idea to cut Rand partly loose from the developements to improve our backward-compatability and usability story. Advantages (from the original issue) - rand provide easy to reason generator(s) to satisfy the bulk of the users - rand provides low-friction upgrades and keeps the optimal-ish algorithms readily available - rand will not accumulate and/or deprecate specific algorithms throughout time - Specific rand Rng names won't bleed out to the world, like in forum posts, stackoverflow, etc.. Instead we want to provide an official companion crate, rand_rngs, with a couple of blessed implementations. Whether Rand should depend on rand_rngs or copy the two algorithms used by StdRng and SmallRng is not fully decided. It might reduce code size if a crate depends on both StdRng and its algorithm (currently Hc128Rng) directly, but that seems rare and not worth much. It has the disadvantage that both implementations should remain in sync. Maybe the CI can check this? If Rand depends on rand_rngs, it would restrict rand_rngs to only depend on rand_core. But that is what rand_core is for. I am for having Rand depend on rand_rngs. rand_rngs rand_rngs should provide a good selection of PRNGs. Including multiple PRNGs in one crate has the advantage of having a single place to provide guidance, as it helps comparing different algorithms with each other. Also it gives one place to offer consistent benchmarks, to run PRNG test suites, to keep up a common quality level, and possibly to develop functionality that is useful for more than one PRNG (e.g. jumping). Which PRNGs to include has been the topic of endless discussions. A few are basically decided. I fully expect the number of PRNGs to grow over time. But we also should be careful not to expose too many, as there are hundreds. Every PRNG should have one thing that gives it a clear advantage over others, otherwise it is not worth the inclusion. Normal PRNGs dhardy#60 <dhardy#60> explored normal PRNGs. The following 5 I feel comfortable about for an initial version of rand_rngs: - PCG-XSH-RR 64/32 (LCG) - PCG-XSL-RR 128/64 (MCG) - SFC (32-bit variant) - SFC (64-bit variant) - Xoroshiro128+ The two PCG variants offer good quality and reasonable performance. SFC provides high performance and a chaotic PRNG (not a fixed period). Xoroshiro128+ has acceptable quality but high performance. An PRNG put together by me, XoroshiroMT, is also good quality and sits between PCG and Xoroshiro128+ qua performance. But now that there is just a new Xoshiro PRNG, it may be worth evaluating that one first, as it is said to also be good quality. CSPRNGs For CSPRNGs we currently have two good implementations in Rand - ChaCha20 - HC-128 ChaCha20 offers reasonably good performance and uses little memory, while HC-128 brings high performance at the cost of using much memory. I would also like to see some implementation of AES-CTR DRBG eventually, as it is commonly used, and has hardware support on modern desktop processors. Other / deprecated PRNGs We currently have the ISAAC, ISAAC-64 and Xorshift128/32 PRNGs in rand. They have no real advantages over the PRNGs metioned before. It is better to use HC-128 instead of ISAAC, and Xoroshiro128+ or PCG instead of Xorshift. We can include them in something like a deprecated module, but I propose to move them to stand-alone crates outside the Rand repository. Steps to take - move the prngs module to a seperate rand_rngs crate in the Rand repository, similar to rand_core. - move generators benchmarks over. - lift PRNG implementations from https://github.com/pitdicker/small-rngs (I have updated it to master a while ago, but still have to push the changes) - lift Xoroshiro128+ from https://github.com/vks/xoroshiro/ Does this sound about right? — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#431>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AACCtJsl20y6PoCkWCeYCSRhM0dRq4Pvks5tvv0ygaJpZM4T0Cak> .

See the first post and the linked issue.

I actually see no reason that we shouldn't have one crate per RNG (or perhaps family of RNGs), but I think it's worth having these in the Rand repo and the crates owned by the Rand team (currently me and the libs team). Or we could try organising more and have a rust-rand project and set of repositories on GH maybe.

Both the new xoshiro and xoroshiro** variants I think are worth consideration.

Vigna claims xoroshiro256** has a higher degree polynomial than PCG 128 variants https://www.reddit.com/r/programming/comments/8gx2d3/new_line_of_fast_prngs_released_by_the_author_of/dygkkng/, so xoshiro variants are probably even stronger.

Edit: poor wording

Is the separate repository is merely a transitional detail? It improves code size if any code that gets used actually gets exposed somewhere, even if only in another crate. It would improve tests if all this lives in the rand repository, right?

@TheIronBorn

@TheIronBorn this issue isn't about what algorithms we include, it's just about organisation and presentation.

@burdges

@burdges I'm not sure what you mean about transitional; no. The easiest option is I think just to have sub-projects in this repo (like rand_core).

I'm not even sure if it does help with testing having everything in the same repo; in one way it makes it worse since CI must run all unit-tests on any change (although with API-breaking changes this may be necessary).

Once we have stable core APIs it may make more sense to use separate repos since most changes (docs, new features, tweaks to other features) will not affect other crates. I.e. once rand_core is stable then changes to things like the distribution code will have no effect on the RNG implementations, so separate repos do make some sense.

In this issue and the previous one I have given arguments that it would really benefit users to have one crate, as it helps comparing and contrasting them. And real but smaller benefits for us. Are those reasons wrong?

Maybe it is good to also collect the reasons multiple crates can be a good idea.

Two related thoughts:

most non-cryptographic PRNGs only need 5-10 lines for the algorithm. About 30 additional lines to implement the necessary traits. Then a handful of tests, documentation, license header, and benchmarks. Seems a bit small for a crate to me, but that is not unique.
how do we show separate crates are similar enough to compare directly (benchmarks, quality, support)? Anyone is free to create a rand_* crate.

CI must run all unit-tests on any change.

The unit tests we have now for PRNGs run in a fraction of a second, easily a 100 times less than the set-up time for Travis.

There is precedence to have one crate per algorithm in [RustCrypto]( https://github.com/RustCrypto/hashes?files=1). You can still have a crate reexporting them all, but I'm not sure how useful that is. It might make sense to have some comparison in Rand's documentation, where we advertise the recommended RNGs and their crates.

…

On Mon, May 7, 2018, 08:32 Paul Dicker ***@***.***> wrote: In this issue and the previous one I have given arguments that it would really benefit users to have one crate, as it helps comparing and contrasting them. And real but smaller benefits for us. Are those reasons wrong? Maybe it is good to also collect the reasons multiple crates can be a good idea. Two related thoughts: - most non-cryptographic PRNGs only need 5-10 lines for the algorithm. About 30 additional lines to implement the necessary traits. Then a handful of tests, documentation, license header, and benchmarks. Seems a bit small for a crate to me, but that is not unique. - how do we show separate crates are similar enough to compare directly (benchmarks, quality, support)? Anyone is free to create a rand_* crate. CI must run all unit-tests on any change. The unit tests we have now for PRNGs run in a fraction of a second, easily a 100 times less than the set-up time for Travis. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#431 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AACCtKxNDruFXra7bvopRZ0gZTadbl2_ks5tv-qSgaJpZM4T0Cak> .

@newpavlov

So sounds like

we should put new crates within the same repo, at least for now (like rand_core is)
everything in the prng module should move
still to decide exact crates
probably we should make rand depend on whichever crates are necessary for the StdRng and SmallRng algorithms

How many crates do we want? Only 1-3 (e.g. crypto, non-crypto and deprecated)? One crate per family of RNGs? One crate per RNG?

having many crates means we don't have to deprecate generators; we can just update the doc and ignore the relevant crate(s) (potentially move to a new repo)
having many crates may make comprehensive testing and benchmarking painful (extra scripts required; lots of binaries to compile); having a "master" crate may alleviate this
each crate has extra boilerplate (cargo.toml, readme, possibly tests and benchmarks)
each crate has to be published independently

@newpavlov do you have anything to say about the many-small-crates design of RustCrypto's hashes (and other projects)?

@dhardy

In my opinion small crates work pretty well (but not too small, i.e. crates for family of algorithms, not for each variation), yes there is some headache with coordinated upgrades to the new trait version, but if rand_core will be relatively stable, I don't think it will be a big problem.

having many crates may make comprehensive testing and benchmarking painful

cargo test --all and cargo bench --all more or less solve this problem. There is an issue with features when you work with virtual manifest, but I don't think that RNG crates will suffer from it.

each crate has extra boilerplate (cargo.toml, readme, possibly tests and benchmarks)

RustCrpyto partially solves this problem by having feature gated dev module in trait crates, which define functions and macros to make it easier to write tests and benchmarks. Though I am not sure if RNG crates should follow this approach.

I would like suggest to move CryptoRng crates to the RustCrypto/CSRNGs repo. (of course with full access granted to @dhardy and lang team) Pros:

CSPRNGs usually tightly coupled with stream ciphers, so they could share underlying implementations, which will make easier to work on optimizations.
I plan to have other CSRNGs in addition to algorithms from rand crate, e.g. rdrand (@nagisa gave his consent) and aesrng developed by @vks

Con is of course is the split of RNG crates between two organizations.

Actually we already stopped using --all for most tests because of this issue. It's a shame it's not been solved.

It'd be nice to save code size by using stream cipher code for CSPRNGs of course, but not that pressing. At first blush, I kinda think moving CSPRNG crates into another project, especially one less blessed by Mozilla, sounds premature and distracting. At minimum, all the BlockRng business will make reading the code annoying.

Note: xorshift4096* also exists. Probably impractical but it's curious. (not sure why it's no longer listed)

@astocko

Well, I'll try again: @astocko are you interested in maintaining your Xorshift crate?

But given the lack of commits in the last year it seems unlikely. The code is CC0 so it may be sensible at this point to pull out what we want and make a new rand_xorshift crate.

@vks what do you think should be the divide between Xorshift, Xoroshiro and Xoshiro generators, since you already have the latter two in your crate?

I see you mentioned me here as an author of randomorg crate. I am the one and I just wanted to remind you that this crate unfortunately is not going to have Rng traits implementations due to its nature of remote data source.

@dhardy My crates are based on the recommendations by Vigna. The xoroshiro crate includes xorshift1024*phi, because that was recommended together with the xoroshiro generators. The xoshiro crate implements the new generation of Vigna's generators, which includes some xoroshiro variants incompatible to the xoroshiro crate (!). So yes, the crate names are a bit misleading, but I think the current separation makes the most sense. A more accurate name would be rngs_vigna2018, but I'm not sure it would be a better name. I should probably clarify that in the docs.

…

On Sat, Jul 14, 2018, 09:52 Diggory Hardy ***@***.***> wrote: Well, I'll try again: @astocko <https://github.com/astocko> are you interested in maintaining your Xorshift crate? But given the lack of commits in the last year it seems unlikely. The code is CC0 so it may be sensible at this point to pull out what we want and make a new rand_xorshift crate. @vks <https://github.com/vks> what do you think should be the divide between Xorshift, Xoroshiro and Xoshiro generators, since you already have the latter two in your crate? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#431 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AACCtBdWGQeAOE_GE66fWNGjJW8V1cJjks5uGaNFgaJpZM4T0Cak> .

We could just throw it all under rand_vigna, but a separate crate for Xorshift is also fine. His recommendations have changed over time, so putting this years' recommendations under vigna2018 doesn't seem sensible for what we hope will become a stable crate.

Well, stability is why I decided to create a new crate, so the old one can still be used for reproducibility. One of the advantages of moving the algorithms out of Rand it that we can just add and drop crates from the recommendations without breaking anyone's code.

Hey, author of the Pcg32 crate here. The other PcgRand crate seems much more full-fledged than mine, but I'd be happy to continue maintaining Pcg32.

I personally would advocate for some sort of vetting/benchmarking with the rand crates. Even something like dieharder scores would be nice to see.

We currently have quality comparisons here: https://docs.rs/rand/0.5.4/rand/prng/index.html#basic-pseudo-random-number-generators-prngs

I don't know if we've thought about listing actual test data though (probably TestU01 or PractRand if anything)

@droundy

@droundy if you're still interested, we'd accept Xorshift1024 in the new rand_xorshift sub-crate (see #557).

@pitdicker

@pitdicker I think it's time to turn your small-rngs repo into a real crate 😄

As you say, it is more useful having a small crate with a few high-quality PRNGs than to have a huge collection, so how about we create rand_small_rngs with the following guide-lines:

non-crypto only
keep it small (5-20 RNGs)
try to avoid overlap with other high-quality crates — which probably means Xorshift and Xoshiro should be omitted from this crate, though (for now at least) some PCG variants included

Potentially we can add a separate rand_rngs sub-project for comparison purposes (benchmarks, quality testing). These should be separate: the former is a small collection of high-quality RNGs not hosted elsewhere (and should remain small); the latter is a comparison across many RNGs (and could host the generators.rs benchmarks later).

I've just gone ahead and implements a xoroshiro256+ in my own code, which ended up seeming simplest, after I decided that compatibility with my old C code didn't matter. Maybe I'll use a "standard" xoroshiro implementation at some later point, but for now it seemed easiest to just translate the C code myself. That way I didn't have to mess with serde feature flags, and I could easily get proper seeding with a u64 as recommended by Vigna.

If it helps you decide which PRNGs to include where, I have written an article on random number generators and categorized "good" RNGs into two categories. Essentially:

A cryptographic PRNG is designed such that prior unseen outputs are hard to guess, and has a state length of at least 128 bits.
A statistical PRNG "must either satisfy the one-way property or be significantly more likely than not to pass all tests (other than MatrixRank and LinearComp) of BigCrush", and has a state length of at least 64 bits.

Any RNG other than a cryptographic or statistical RNG, as defined in my article, should be considered low-quality, I think.

I updated my pcg crate to implement the RngCore/Rng traits

Navigation Menu

Repository navigation

Move PRNG algorithms out of Rand #431

rand_rngs

Normal PRNGs

CSPRNGs

Other / deprecated PRNGs

Steps to take

22 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Move PRNG algorithms out of Rand #431

Description

rand_rngs

Normal PRNGs

CSPRNGs

Other / deprecated PRNGs

Steps to take

Activity

vks commented on May 6, 2018

pitdicker commented on May 6, 2018

dhardy commented on May 6, 2018

TheIronBorn commented on May 6, 2018

burdges commented on May 6, 2018

dhardy commented on May 7, 2018

dhardy commented on May 7, 2018

pitdicker commented on May 7, 2018

vks commented on May 7, 2018

dhardy commented on May 16, 2018

newpavlov commented on May 16, 2018

dhardy commented on May 16, 2018

burdges commented on May 16, 2018

22 remaining items

TheIronBorn commented on Jul 13, 2018

dhardy commented on Jul 14, 2018

iddm commented on Jul 14, 2018

vks commented on Jul 14, 2018

dhardy commented on Jul 14, 2018

vks commented on Jul 14, 2018

afnanenayet commented on Jul 14, 2018

TheIronBorn commented on Jul 14, 2018

dhardy commented on Jul 31, 2018

dhardy commented on Jul 31, 2018

droundy commented on Jul 31, 2018

peteroupc commented on Aug 22, 2018

afnanenayet commented on Aug 22, 2018

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions