Review which hash algorithm to use for incremental compilation hashes.

[michaelwoerister]

For incremental compilation we are hashing lots of things, HIR, crate metadata and soon also type checking tables. These hashes are used purely as fingerprints, that is, we compare these hashes in order to find out if the things having been hashed are equal or not. Consequently the primary qualities we require from the hash algorithm are:

1. That it acts as a pseudo-random-function, i.e. whatever we feed in, the resulting hashes should have a collision probability that is roughly the same as that of random numbers.
2. That it produces wide enough hash values so the collision probabilities are low enough (128 bits should be fine).
3. That it is fast.

It remains to be clarified whether it makes sense to use a cryptographic hash function, i.e. that it is hard to find/construct collisions. My guess is no:

• Incremental compilation caches are not meant to be distributed. They are platform dependent files created locally by your compiler and there is little use in distributing them.
• A 128 bit hash is probably susceptible to a brute force attack anyway.
• I cannot think of an attack that exploits a hash collision here. If one wants to tamper with an incremental compilation cache, one could just replace the object file in the cache without a need to ever touch item hashes.

I'd be very interested though if someone could come up with an attack scenario. But even then the solution would probably be to implement some general code signing scheme for these caches.

At the moment we are using BLAKE2 as our hashing algorithm which is a cryptographic hash function and thus fulfills requirements (1) and (2) very well. However, compared to non-cryptographic hash functions it is rather slow. For raw throughput SipHash would be about three times as fast and fast hash functions like Metrohash can be 20 times as fast. Before you get too excited though: Most of the time computing hashes is spent gathering the data that is fed into the hash function, not actually running the function on it. But there are still some gains to be had, here are some preliminary tests of using BLAKE2 -- which is our "worst case" -- and MetroHash -- which is among the fastest hash functions providing 128 bit hashes:

	BLAKE2	MetroHash	SipHash 1-3	SipHash 2-4
libcore	0.258s	0.193s (-25%)	0.189s (-26%)	0.201s (-22%)
librustc	0.435s	0.345s (-20%)	0.320s (-26%)	0.327s (-25%)
syntex_syntax (HIR)	0.221s	0.166s (-25%)	0.168s (-24%)	0.176s (-20%)
syntex_syntax (Metadata)	0.456s	0.326s (-28%)	0.312s (-31%)	0.347s (-24%)

So it seems that a fast hash functions allows to save 20-30% spent during ICH computation. If we could get some confidence that:

• a function like MetroHash provides low enough collision probability and
• we really don't need a cryptographic hash function

then we could have some free speedups here.

UPDATE:
I added the 128 bit version of SipHash to the table and the timings are as good as the ones for MetroHash.

[est31]

As another idea, if non cryptographic hashes are allowed, we could use SHA-1 on platforms where its hardware accelerated (apparently Ryzen and newer and Goldmont and newer). SHA-1 is slightly slower than BLAKE2, but I guess with hardware acceleration it will be much faster, maybe faster than a MetroHash implemented with generic instructions. Would be interesting to have benchmarks on this.

[michaelwoerister]

That's an interesting idea. However, I'd need to see actual numbers for that and they would have to be very compelling in order to justify adding platform-specific code.
Also, once we go down the platform-specific road: MetroHash can also make use of some special instructions, almost doubling its speed.

[michaelwoerister]

A 128 bit SipHash13 might also be a good contender. It's pretty fast and it's designed to be a good PRF.

[arthurprs]

Siphash is probably a sensible choice here if the numbers look good. Metrohash is great but I think we should try to be conservative to some extent.

[michaelwoerister]

@rust-lang/libs: There are no plans of making the 128-bit version of SipHash available in the standard library, right?

[sfackler]

Not in a stable manner, no, but that shouldn't matter for compiler internals.

[est31]

Also, afaik its possible to simply use crates from crates.io now. Just add them to the Cargo.toml and commit both that change and the change to Cargo.lock into git.

[michaelwoerister]

I added the 128 bit version of SipHash to the table and the timings are as good as the ones for MetroHash.

[arthurprs]

Sounds like a clear winner to me. Is that 1-3 or 2-4 variant?

[michaelwoerister]

It's 1-3 ...

[michaelwoerister]

I added the SipHash 2-4 timings too. As expected they are slightly worse but still pretty good.

[briansmith]

That it produces wide enough hash values so the collision probabilities are low enough (128 bits should be fine).

NIT: It doesn't make sense to measure hashes by the number of bits this way, because the number of bits doesn't correlate strongly enough with the desired collision probability. For example, `SHA-1(x)||"123456789012" is a 256-bit hash but it isn't nearly as strong as SHA-256.

Instead, it would be good to mention the desired collision probability. Also, what's the threat model? I.e. is there any way that something could go wrong if there's a collision? AFAICT a collision could easily be disasterous.

Also, I don't think the use of non-Rust implementations should be rejected since a huge amount of the compiler isn't written in Rust already. I would rather the compiler use a safer algorithm written in assembly language then a weaker algorithm that's implemented in Rust.

[michaelwoerister]

NIT: It doesn't make sense to measure hashes by the number of bits this way, because the number of bits doesn't correlate strongly enough with the desired collision probability. For example, `SHA-1(x)||"123456789012" is a 256-bit hash but it isn't nearly as strong as SHA-256.

I'm working under the assumption that a high-quality hash function will use all bits available.

Also, what's the threat model? I.e. is there any way that something could go wrong if there's a collision? AFAICT a collision could easily be disasterous.

A collision would result in some piece data not being detected as having changed. I would not talk about "threat model" though. Cache files are not meant to be distributed. An attacker would be better off just manipulating rlibs directly.

Also, I don't think the use of non-Rust implementations should be rejected since a huge amount of the compiler isn't written in Rust already. I would rather the compiler use a safer algorithm written in assembly language then a weaker algorithm that's implemented in Rust.

Nobody said it has to be written in Rust. But maintenance cost is a factor too.