Move PRNG algorithms out of Rand

[pitdicker]

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?

[vks]

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

[pitdicker]

See the first post and the linked issue.

[dhardy]

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.

[TheIronBorn]

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

[burdges]

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?

[dhardy]

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

[dhardy]

@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.

[pitdicker]

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.

[vks]

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

[dhardy]

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)?