Use ChaCha20 in StdRng and feature-gate SmallRng #792

dhardy · 2019-05-07T12:14:25Z

Following #789, we change the StdRng algorithm. Additionally,

introduce stdrng_strong and stdrng_fast feature flags
adjust reseeding threshold from 32 MiB to 64 kiB without observable impact on performance (in part possible because ChaCha has much faster initialisation than HC-128, and in part because the old threshold was very conservative)

Thoughts @kazcw @vks @newpavlov @burdges? I don't exactly like adding configurability here, and maybe it's not worth doing so for a 50% performance boost. ChaCha12 is used by Google's Adiantum (repo) and appears to have a good security margin, though doesn't appear to have wide usage (probably because ChaCha20 is already fast enough for most).

I do think we should only use generators with a good level of trust, thus have not added ChaCha8 as an option (even though it remains unbroken).

Note: the names stdrng_conservative and stdrng_good may be more appropriate, but are likely also confusing.

benches/generators.rs

dhardy · 2019-05-07T15:04:17Z

Note: I need to fix the tests, which shouldn't be using StdRng (how many times have we said don't use it when needing reproducibility?)

burdges · 2019-05-07T15:05:56Z

Aren't features additive? I'm dubious about this plan, but if doing it then using only one feature sounds best. I'd think stdrng_conservative could be default set, maybe meaning ChaCha20, but if anyone wants faster then they should drop the default feature, maybe meaning ChaCha12.

vks · 2019-05-07T15:09:51Z

Maybe it's better to be more conservative and provide no option between ChaCha12 and ChaCha20? We can suggest in the documentation to use ChaCha12 directly via rand_chacha if the additional performance is required.

newpavlov · 2019-05-07T15:15:10Z

I am not sure if I like this approach, to me it looks like features misuse. Also shouldn't be newtype pattern used here instead of type alias? For example it's possible to write code like this:

fn foo(rng: &mut StdRng) { .. }

foo(&mut ChaCha12Rng::from_entropy());

So changing StdRng underlying algorithm can be technically viewed as a breaking change. And of course turning feature may break build as well.

vks · 2019-05-07T15:31:23Z

Also shouldn't be newtype pattern used here instead of type alias?

I believe this is the case for StdRng. However, Core is just a type alias, but I think it is not exported

dhardy · 2019-05-07T15:32:34Z

@burdges yes, but disabling a default feature which is used from multiple sub-crates is hard. @vks the point is to allow tuning of ThreadRng.

@newpavlov I agree, this is feature mis-use. It would be much better if Cargo allowed --features stdrng=ChaCha20 for example, and even better if this could only be specified by the final binary. However, we can't do that. If such a feature became available I would prefer to use that, so of course it is better not to include a feature now we expect to break now — except this is interesting in that it provides a way for users heavily reliant on ThreadRng to tune their apps.

We do use the newtype pattern? The aliases are strictly for internal use.

Of course, ThreadRng performance is probably not a bottleneck for most apps since in that case it would make more sense to use another RNG directly, so quite possibly adding tuning for it is pointless.

newpavlov · 2019-05-07T15:34:28Z

We do use the newtype pattern? The aliases are strictly for internal use.

Ah, yes, you are right.

burdges · 2019-05-07T18:51:32Z

I've no idea what StdRng gets used for. It's not used by ThreadRng, which sounds like the unique place.

dhardy · 2019-05-08T15:37:52Z

I've no idea what StdRng gets used for. It's not used by ThreadRng, which sounds like the unique place.

Me neither actually. By the time you've filtered out the duplicates and re-definitions... not so many. In contrast SmallRng has less total hits, but more actual uses come up (maybe because StdRng has been a part of Rand for much longer).

So I guess we drop the configuration idea. Probably we should keep StdRng because it's basically free (we need the dependency for ThreadRng already).

Shall we feature-gate SmallRng behind features=small? That drops a dependency in standard builds while keeping it (seems useful enough overall, and there isn't another good home).

vks · 2019-05-09T08:26:45Z

Shall we feature-gate SmallRng behind features=small? That drops a dependency in standard builds while keeping it (seems useful enough overall, and there isn't another good home).

I think this is a good idea. It will presumably also make it easier to gauge how much SmallRng is used.

dhardy · 2019-05-13T10:22:57Z

Rebased. First and last commits are the same, the middle two are new. I think this covers all suggestions.

src/rngs/small.rs

dhardy · 2019-05-15T10:08:22Z

The Miri test is failing:

error[E0080]: Miri evaluation error: miri does not support inline assembly
  --> /home/travis/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libcore/../stdsimd/crates/core_arch/src/x86/cpuid.rs:68:9
[snip]
   = note: inside call to `std::detect::check_for` at <::std::std_detect::detect::arch::is_x86_feature_detected macros>:30:37
   = note: inside call to `c2_chacha::guts::init_chacha::dispatch_init` at <::ppv_lite86::x86_64::dispatch_light128 macros>:12:28
[snip]
note: inside call to `<rand_chacha::ChaCha8Rng as rand_core::SeedableRng>::seed_from_u64` at src/lib.rs:566:9
  --> src/lib.rs:566:9
   |
566|         rand_chacha::ChaCha8Rng::seed_from_u64(seed)

So I guess for Miri's sake, we should use a simpler RNG in our tests (perhaps PCG like in rand_distr, if somehow Cargo will allow a dependency to be both optional and a dev-dependency).

dhardy · 2019-05-15T10:18:45Z

The WASM/Emscripten test fails with a linker error. It is not very decipherable, but running the following (prerequisites are in the .travis config, 194-199) on rand_chacha causes a similar error:

~/projects/rand/rand/rand_chacha$ EMCC_CFLAGS="-s ERROR_ON_UNDEFINED_SYMBOLS=0" cargo web test --target wasm32-unknown-emscripten --no-run
info: downloading component 'rust-std' for 'wasm32-unknown-emscripten'
info: installing component 'rust-std' for 'wasm32-unknown-emscripten'
   Compiling lazy_static v1.3.0
   Compiling ppv-lite86 v0.2.3
   Compiling rand_core v0.4.0 (/home/dhardy/projects/rand/rand/rand_core)
   Compiling rand_chacha v0.2.1 (/home/dhardy/projects/rand/rand/rand_chacha)
   Compiling c2-chacha v0.2.2
error: linking with `emcc` failed: exit code: 1

@kazcw is there some way we can make rand_chacha compatible with Emscripten (if necessary, using a slower fallback)?

If this also allows us to work around the Miri issue (#[cfg(miri)]) then even better.

Note: of course we could just cfg the whole thing and include the old implementation, but hopefully there's a solution with less code redundancy. If need be Miri can use a different RNG so don't design around that requirement.

vks · 2019-05-15T11:07:54Z

rand_jitter/src/error.rs

        // Timer check is already quite permissive of failures so we don't
        // expect false-positive failures, i.e. any error is irrecoverable.
        #[cfg(feature = "std")] {
-            Error::with_cause(ErrorKind::Unavailable, "timer jitter failed basic quality tests", err)
+            Error::with_cause(ErrorKind::Unavailable, "timer jitter failed basic quality tests", _err)
        }
        #[cfg(not(feature = "std"))] {


Maybe it's better to add let _ = err; here instead of renaming err to _err?

Does it matter?

I would prefer it, because I think it reflects intent better, but ultimately it's not important and I'm fine with either way.

kazcw · 2019-05-16T05:03:21Z

@dhardy I don't know off the top of my head what problem emscripten would have with the portable fallback; it all safe code and works on x86/arm/mips. I'll dig into it probably this weekend.

vks · 2019-05-23T11:08:51Z

If I understood correctly, the plan for this PR is the following:

Use a copy-and-pasted PCG generator for value-stability tests, instead of ChaCha8.
Use rand_hc instead of rand_chacha for Emscripten targets.

dhardy · 2019-05-23T14:24:41Z

Done. The result is a little hacky, but not too bad.

It seems there is no problem with depending on the same thing twice within Cargo.toml.

vks

rand_distr/tests/uniformity.rs probably should be updated to not use SmallRng. Otherwise this looks very good!

dhardy · 2019-05-23T15:54:54Z

Right. Switched to Pcg32 since we depend on that crate anyway, but could also use thread_rng().

vks · 2019-05-31T11:12:20Z

There are the following failures:

Miri fails due to inline assembly in cpuid. 1 2
seq::test::test_slice_choose fails on 32-bit platforms (Reproducibility of usize samples across architectures #805). 1 2 3
WAsm fails to compile rotate_right. 1

dhardy · 2019-05-31T11:25:18Z

My opinion here is that the Miri and WASM failures lie outside the scope of the Rand project, and unless we get help addressing these issues, we should not block the 0.7 release on switching StdRng to ChaCha (it was never originally a target anyway).

kazcw · 2019-05-31T13:49:54Z

I released ppv-lite86 0.2.4, so Miri should pass now.

dhardy · 2019-06-01T08:35:11Z

Thanks @kazcw, you've been very helpful on this.

The WASM failure is about a u128 rotation, but this is not emscripten. Perhaps a bug? I can't reproduce with a wrapper function.

kazcw · 2019-06-01T16:10:46Z

Wow, that's interesting. I created a project that just has a function that invokes u128::rotate_right:

If I use cargo build --target wasm32-unknown-unknown, I get a .wasm that can be imported without error.

But if I build it with cargo web build --target=wasm32-unknown-unknown, I get a module that can't be loaded:
In headless Chrome: CompileError: AsyncCompilation: (null): Compiling wasm function "_ZN4core3num22_$LT$impl$u20$u128$GT$12rotate_right17hf9a8f167bd77e313E" failed: call[3] expected type i32, found get_local of type i64 @+2163
In Firefox: Error loading Rust wasm module 'test_rotate': CompileError: "wasm validation error: at offset 1206: type mismatch: expression has type i64 but expected i32"

rotate_left is also broken, but other u128 ops that I tried work.

I don't see how this could be anything but a rustc bug, but why does it only break when built with cargo-web?

Filed a bug in cargo-web: koute/cargo-web#193

kazcw · 2019-06-01T17:30:35Z

Ok, as of ppv-lite86 0.2.5 I don't rotate any u128s.

vks · 2019-06-03T09:51:27Z

I think this can be merged after we

~~require ppv-lite86 >= 0.2.5 and~~
merge Uniform distribution: bias and usize portability #809.

Then all tests should pass.

… test We want a value-stable RNG to avoid future vector changes which means using something outside of Rand. Pcg32 is a good fit and is easy to embed if that is ever necessary.

seq::test::test_slice_choose updated with better bounds

Not ideal but seems to work; see: rust-lang/cargo#6945

This is considered an ugly hack, but easier than making the new ChaChaRng compatible with Emscripten. Potentially support for Emscripten will be dropped in the future, if it doesn't get support for u128.

dhardy · 2019-06-03T14:41:19Z

Rebased. Reordered commits and tidied up (squashed) some. Adjusted the test_slice_choose test with better bounds which failed with the new RNG.

dhardy · 2019-06-03T14:45:11Z

require ppv-lite86 >= 0.2.5

Where do you propose we do this? We don't have a direct dependency. I don't think it's worth bothering with minimum patch version requirements personally, especially where this only affects minor platforms (WASM in this case).

vks · 2019-06-03T14:46:26Z

Where do you propose we do this? We don't have a direct dependency. I don't think it's worth bothering with minimum patch version requirements personally, especially where this only affects minor platforms (WASM in this case).

Fair enough, this should be fine then.

vks · 2019-06-03T15:07:26Z

The tests passed! 🎉

vks reviewed May 7, 2019

View reviewed changes

benches/generators.rs Outdated Show resolved Hide resolved

dhardy changed the title ~~Features~~ StdRnd and configuration features May 7, 2019

dhardy force-pushed the features branch from f209854 to 618f890 Compare May 13, 2019 10:22

dhardy changed the title ~~StdRnd and configuration features~~ Use ChaCha20 in StdRng and feature-gate SmallRng May 13, 2019

vks reviewed May 13, 2019

View reviewed changes

src/rngs/small.rs Show resolved Hide resolved

dhardy mentioned this pull request May 15, 2019

Tracker: Rand 0.7 #715

Closed

22 tasks

vks reviewed May 15, 2019

View reviewed changes

vks added this to the 0.7 release milestone May 15, 2019

dhardy mentioned this pull request May 15, 2019

Fix Miri testing of ChaCha #796

Closed

dhardy force-pushed the features branch from d12421b to 66c22e0 Compare May 23, 2019 14:30

vks requested changes May 23, 2019

View reviewed changes

vks approved these changes May 24, 2019

View reviewed changes

dhardy mentioned this pull request May 24, 2019

Reproducibility of usize samples across architectures #805

Closed

dhardy added 7 commits June 3, 2019 14:59

rand_distr: switch test RNG to Pcg32, update vectors and tweak Cauchy…

917d67b

… test We want a value-stable RNG to avoid future vector changes which means using something outside of Rand. Pcg32 is a good fit and is easy to embed if that is ever necessary.

Switch Rand's test::rng to Pcg32

efd3b5c

seq::test::test_slice_choose updated with better bounds

Update features doc

1ea01ae

Feature-gate the SmallRng generator

b7abfb6

Enable small_rng feature requirement for each benchmark

41b9743

Not ideal but seems to work; see: rust-lang/cargo#6945

Replace StdRng algorithm with ChaCha20 and adjust reseeding threshold

33bd404

Use Hc128 on Emscripten

ff121cf

This is considered an ugly hack, but easier than making the new ChaChaRng compatible with Emscripten. Potentially support for Emscripten will be dropped in the future, if it doesn't get support for u128.

dhardy force-pushed the features branch from a1445a2 to ff121cf Compare June 3, 2019 14:39

dhardy merged commit 245fde0 into rust-random:master Jun 3, 2019

dhardy mentioned this pull request Jun 4, 2019

Future of SmallRng #767

Closed

dhardy deleted the features branch June 4, 2019 08:23

dhardy mentioned this pull request Oct 28, 2019

StdRng docs refer to non-existent stdrng_* Cargo features #902

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Use ChaCha20 in StdRng and feature-gate SmallRng #792

Use ChaCha20 in StdRng and feature-gate SmallRng #792

dhardy commented May 7, 2019 •

edited

dhardy commented May 7, 2019

burdges commented May 7, 2019 •

edited

vks commented May 7, 2019

newpavlov commented May 7, 2019 •

edited

vks commented May 7, 2019

dhardy commented May 7, 2019

newpavlov commented May 7, 2019

burdges commented May 7, 2019

dhardy commented May 8, 2019

vks commented May 9, 2019

dhardy commented May 13, 2019

dhardy commented May 15, 2019 •

edited

dhardy commented May 15, 2019 •

edited

vks May 15, 2019

dhardy May 23, 2019

vks May 23, 2019

kazcw commented May 16, 2019

vks commented May 23, 2019

dhardy commented May 23, 2019

vks left a comment

dhardy commented May 23, 2019

vks commented May 31, 2019 •

edited

dhardy commented May 31, 2019

kazcw commented May 31, 2019

dhardy commented Jun 1, 2019

kazcw commented Jun 1, 2019 •

edited

kazcw commented Jun 1, 2019 •

edited

vks commented Jun 3, 2019 •

edited

dhardy commented Jun 3, 2019 •

edited

dhardy commented Jun 3, 2019

vks commented Jun 3, 2019

vks commented Jun 3, 2019

Use ChaCha20 in StdRng and feature-gate SmallRng #792

Use ChaCha20 in StdRng and feature-gate SmallRng #792

Conversation

dhardy commented May 7, 2019 • edited

dhardy commented May 7, 2019

burdges commented May 7, 2019 • edited

vks commented May 7, 2019

newpavlov commented May 7, 2019 • edited

vks commented May 7, 2019

dhardy commented May 7, 2019

newpavlov commented May 7, 2019

burdges commented May 7, 2019

dhardy commented May 8, 2019

vks commented May 9, 2019

dhardy commented May 13, 2019

dhardy commented May 15, 2019 • edited

dhardy commented May 15, 2019 • edited

vks May 15, 2019

Choose a reason for hiding this comment

dhardy May 23, 2019

Choose a reason for hiding this comment

vks May 23, 2019

Choose a reason for hiding this comment

kazcw commented May 16, 2019

vks commented May 23, 2019

dhardy commented May 23, 2019

vks left a comment

Choose a reason for hiding this comment

dhardy commented May 23, 2019

vks commented May 31, 2019 • edited

dhardy commented May 31, 2019

kazcw commented May 31, 2019

dhardy commented Jun 1, 2019

kazcw commented Jun 1, 2019 • edited

kazcw commented Jun 1, 2019 • edited

vks commented Jun 3, 2019 • edited

dhardy commented Jun 3, 2019 • edited

dhardy commented Jun 3, 2019

vks commented Jun 3, 2019

vks commented Jun 3, 2019

dhardy commented May 7, 2019 •

edited

burdges commented May 7, 2019 •

edited

newpavlov commented May 7, 2019 •

edited

dhardy commented May 15, 2019 •

edited

dhardy commented May 15, 2019 •

edited

vks commented May 31, 2019 •

edited

kazcw commented Jun 1, 2019 •

edited

kazcw commented Jun 1, 2019 •

edited

vks commented Jun 3, 2019 •

edited

dhardy commented Jun 3, 2019 •

edited