from_rng and value-stability

[dhardy]

From the doc for SeedableRng::from_rng:

    /// Usage of this method is not recommended when reproducibility is required
    /// since implementing PRNGs are not required to fix Endianness and are
    /// allowed to modify implementations in new releases.

The rationale of not making this method value-stable is to allow more room for optimisation and potentially entropy:

• no need to worry about Endianness
• no value-stability means the method is open to optimisation in the future
• RNGs with large internal state space (Hc128Rng, ISAAC) can fill the entire state directly instead of using key expansion — except we never implemented this for Hc128Rng, and ISAAC still uses the same routines to scramble the key in case it is poor quality

The rationale against this:

• it is natural to want to write let mut my_new_rng = MyRng::from_rng(master_rng);, but we have to tell people not to do this if they want value-stability
• directly filling the internal state space is not really an advantage for entropy since CryptoRngs already use sufficiently large keys, and adding more entropy is irrelevant relative to the strengths of the algorithm and available computational power (256 bits already being sufficient, unless we quantum computing requires major changes to cryptography in the future)
• directly filling the internal state space is not a performance advantage when we must use scrambling routines anyway
• the other rationales for are trivial

So it seems sensible to change this. I'd like @pitdicker's input since he was part of the current design.

Making this value-stable in a future version of rand_core is not a breaking change in any way, though users should not be able to count on value-stability until their dependencies depend on the new rand_core version.

[burdges]

I consider stability the normal case myself because everybody must write test vectors eventually. There is never anything to prevent traits from being implemented wrong, at least not until we get trait tests, so I'd suggest you write roughly:

"""
We emphasize that most SeedableRng should be "stable", in the sense that Seed completely determines their output. As a result, many users expect stability form a SeedableRng, almost all do in some tests. Also, some generic code assumes this stability, and again most all generic code assumes stability in some tests. Yet, there are conceivably SeedableRngs that lack stability as an optimization. but perhaps because they intentionally consume external randomness but implement SeedableRng anyways.

We therefore ask that stable SeedableRngs make a stability guarantee as part of their public API. We require public unstable SeedableRngs to warn about their instability in any types implementing SeedableRng unstably. We also suggest that any SeedableRngs that exploit instability provide both stable and unstable versions, either by types or by build features. In practice, almost all SeedableRngs require test vectors, so such a stable variant would normally exist under the hood anyways.
"""

We could look into requiring PRNGs that exploit instability to warn users with a wrapper type, but imho that's overkill, and might discourage them from exposing both stable and unstable variants

#[derive(Default)]
pub struct UnstableSeedableRngSeed<T>(pub T) where T: Sized + Default + AsMut<[u8]>;

[dhardy]

I think we should keep things as simple as possible. Documentation alone may be enough, but it would be clearer to add another marker trait:

pub trait StableRng: SeedableRng {}

[vks]

Yet, there are conceivably SeedableRngs that lack stability, probably as an optimization, but perhaps because they intentionally consume external randomness but implement SeedableRng anyways.

Could you please give a more concrete example? It is not clear to me why you would want to implement SeedableRng for a non-deterministic RNG. I don't think we have any such RNG in Rand.

[burdges]

I struck out the confusing sentence fragment because I agree such intentionally non-deterministic SeedableRngs are going to be an OS-like PRNG like EntropyRng. We now know those get complicated enough that they require distinct machinery. :)

I'm weakly against a marker trait because stability should be so common that a marker trait wastes everyone's time.

[dhardy]

I think that category would mainly be populated by generators which are deterministic but where the code behind them may change. SmallRng and StdRng fall into this category, although we decided that changes should require at least a bump to the minor version number.

I agree with @burdges; there is little reason to add a marker trait. We could recommend that SeedableRng::Seed use a wrapper type as suggested above, but this can't be used for the other methods, seed_from_u64 and from_rng. Additionally, we cannot guarantee that it would always be done in practice, thus users would still need to read documentation.

By the way, what do you think of the original idea suggested in this thread, of dropping the note about instability of from_rng? I think we should move away from the idea of per-item value-stability and just consider everything is either stable or deterministic, but exceptionally allow value-stability breaking changes in minor version bumps with a clear note in the changelog.

[burdges]

I agree with dropping the existing note of course. I wrote the text above as a "replacement" that encourages good behavior. I'll make it more compact:

/// We expect `SeedableRng` should be "stable", in the sense that 
/// `Seed` completely determines their output.  Aside from users who
/// depend upon stability explicitly, almost all users expect stability
/// form a `SeedableRng` in testing frameworks.  We therefore suggest
/// that stable `SeedableRng`s make a stability guarantee as part of
/// their public API. 

/// If some `SeedableRng` violates stability, then we expect their
/// documentation clearly warns about instability, and that they
/// provide both stable and unstable versions, either by types or
/// by build features.  

Another idea would saying that CryptoRng+SeedableRng requires stability. I presume numerics people care about test vectors too though, at least from they RNGs.

[dhardy]

both stable and unstable versions

Sounds about right except for this bit. If someone specifically wants an unstable SeedableRng, whether because it's some weird multi-source RNG or some special-purpose thing, then you probably don't want to use the "stable" version of it anyway.

No to the last point, stability is not specifically a cryptographic feature.