Stream: t-compiler/const-eval

Topic: Determinism in const eval


Elichai Turkel (Mar 02 2020 at 20:36, on Zulip):

Hi, I'm watching @oli's talk in RustConf and I just wanted to comment about determinism, I do think that non determinism can be a wanted feature specifically the one you mentioned generating randomness,
Right now there are crates like https://github.com/tkaitchuck/constrandom for providing something that could've easily happened in a const fn

oli (Mar 03 2020 at 16:53, on Zulip):

True randomness in const eval would break our type system. You could end up with a situation where two arrays of different lengths are considered equal types. Also the query system likely would break in horrible ways

eddyb (Mar 23 2020 at 15:44, on Zulip):

also that kind of crate is just terrible for deterministic builds

eddyb (Mar 23 2020 at 15:44, on Zulip):

oh it's the same one

eddyb (Mar 23 2020 at 15:45, on Zulip):

@Elichai Turkel that crate broke determinism for all users of hashbrown, by default

eddyb (Mar 23 2020 at 15:45, on Zulip):

I hit this while investigating non-deterministic build causes for a client

HeroicKatora (Mar 23 2020 at 15:48, on Zulip):

How are static differentiated from const in the compiler? Maybe it could be somehow allowed to have random statics but not random constants, as the former can't be used in types.

eddyb (Mar 23 2020 at 15:49, on Zulip):

what, link-time RNG?

eddyb (Mar 23 2020 at 15:49, on Zulip):

it's still a terrible idea because non-deterministic builds

eddyb (Mar 23 2020 at 15:49, on Zulip):

just load randomness at runtime

eddyb (Mar 23 2020 at 15:50, on Zulip):

computing non-determinism during the build process is the worst of all worlds

eddyb (Mar 23 2020 at 15:52, on Zulip):

if you want to inject a seed into your builds, use an env variable (or a build script that extracts it from somewhere controllable), at least then you can reproduce the same build (this could be e.g. a git hash)

eddyb (Mar 23 2020 at 15:52, on Zulip):

if you just want RNG at runtime, do it right

RalfJ (Mar 23 2020 at 16:43, on Zulip):

agreed with @eddyb -- it is crucial to be able to exactly re-construct a bianary. that is pretty much the only technique we have to prove that a given binary actually comes from a given sourcecode.

RalfJ (Mar 23 2020 at 16:43, on Zulip):

@eddyb is there an issue for the hashbrown nondet?

eddyb (Mar 23 2020 at 17:25, on Zulip):

@RalfJ https://github.com/rust-lang/hashbrown/pull/125

RalfJ (Mar 23 2020 at 17:34, on Zulip):

but that doesnt sound like anyone was concerned with reproducible builds? (which is itself quite concerning)

Elichai Turkel (Mar 23 2020 at 17:40, on Zulip):

You're right.
I didn't think it through, non determinism in the binary is a bad idea.

eddyb (Mar 23 2020 at 17:56, on Zulip):

@RalfJ there's this I guess https://github.com/paritytech/trie/pull/36

eddyb (Mar 23 2020 at 17:57, on Zulip):

it links everything I could find on the subject at the time

Elichai Turkel (Mar 23 2020 at 18:03, on Zulip):

Arghh I wouldn't switch to ahash that easily :/.
It's not peer reviewed, there's not even a paper analyzing it or proving that the hash function construction is as secure as the aes function.
But it's off topic so sorry.

eddyb (Mar 23 2020 at 18:04, on Zulip):

I've heard similar things, don't worry

eddyb (Mar 23 2020 at 18:05, on Zulip):

it couldn't be as secure as AES, it's presumably DoS-protection-only (but I doubt it's as good as, idk, SipHash)

nagisa (Mar 24 2020 at 01:51, on Zulip):

not to mention its not reproducible across architectures...

Elichai Turkel (Mar 29 2020 at 14:45, on Zulip):

https://github.com/tkaitchuck/constrandom/pull/13 :)

eddyb (Mar 29 2020 at 14:57, on Zulip):

cc-ing @David Tolnay on this thread, I guess (the env var thing should already suffice to make this reasonable, IMO)

eddyb (Mar 29 2020 at 14:58, on Zulip):

although the default "every build gets randomness" still seems potentially misguided, it's good to have workarounds

David Tolnay (Mar 29 2020 at 15:01, on Zulip):

oh yeah screw that crate

eddyb (Mar 29 2020 at 15:02, on Zulip):

lol

Amanieu (Mar 29 2020 at 15:03, on Zulip):

:(

Amanieu (Mar 29 2020 at 15:03, on Zulip):

AFAIK hashbrown is the only real user of constrandom.

eddyb (Mar 29 2020 at 15:03, on Zulip):

@David Tolnay I found out about it while trying to get a combined host + wasm build deterministic, late last year, and I'm glad I started with same-directory builds before going to different-directory

Amanieu (Mar 29 2020 at 15:04, on Zulip):

Actually no, it seems a lot of crates are using ahash.

eddyb (Mar 29 2020 at 15:04, on Zulip):

there was this and there was a bug in wasm debuginfo generation (UB in C++, reading from uninitialized variables), IIRC

Amanieu (Mar 29 2020 at 15:05, on Zulip):

/me is considering just disabling the "ahash-compile-time-rng" feature by default since so many people are complaining about it...

David Tolnay (Mar 29 2020 at 15:06, on Zulip):

i hit it because our codebase needs a concurrent hashmap

David Tolnay (Mar 29 2020 at 15:06, on Zulip):

chashmap is unusable due to race conditions

David Tolnay (Mar 29 2020 at 15:06, on Zulip):

dashmap is unusable due to const_random

David Tolnay (Mar 29 2020 at 15:07, on Zulip):

we've ended up using a deterministic fork of dashmap

eddyb (Mar 29 2020 at 15:10, on Zulip):

ddashmap? :P

RalfJ (Mar 29 2020 at 15:12, on Zulip):

eddyb said:

although the default "every build gets randomness" still seems potentially misguided, it's good to have workarounds

yeah, I feel the default should be reproducible. I am also not convinced build-time randomness is sufficient defense against hashDoS attacks. it feels more like papering over the issue...

RalfJ (Mar 29 2020 at 15:12, on Zulip):

Amanieu said:

Actually no, it seems a lot of crates are using ahash.

I wonder how many of those went "ah it's used by hashbrown, so it must be high quality"...

eddyb (Mar 29 2020 at 15:16, on Zulip):

haha Q_Q

Elichai Turkel (Mar 31 2020 at 13:45, on Zulip):

RalfJ said:

yeah, I feel the default should be reproducible. I am also not convinced build-time randomness is sufficient defense against hashDoS attacks. it feels more like papering over the issue...

I'm not even convinced aHash is sufficient to defend against hashDoS attack anyway.
I think Abseil's hashmap uses CityHash, which AFAICT isn't secure against hashDoS either, so i'm not sure if the default should be secure or not

Last update: Apr 03 2020 at 17:20UTC