Make sure that calls to Fingerprint::combine do not undermine collision safety

[arielb1]

Fingerprint::combine is not a cryptographic hash, so when we use it we might lose the "cryptographic" guarantee of collision safety. Potentially even worse, Fingerprint::combine is associative: Fingerprint::combine(Fingerprint::combine(a, b), c) = Fingerprint::combine(a, Fingerprint::combine(b, c)), and that might cause "algebraic" collisions in some cases.

For example:

rust/src/librustc/dep_graph/dep_node.rs

Line 595 in 2f1ef9e

def_path_hash_0.0.combine(def_path_hash_1.0)

rust/src/librustc/dep_graph/dep_node.rs

Lines 614 to 623 in 2f1ef9e

	fn to_fingerprint(&self, tcx: TyCtxt) -> Fingerprint {
	let mut fingerprint = Fingerprint::zero();
	for &def_id in self.0.iter() {
	let def_path_hash = tcx.def_path_hash(def_id);
	fingerprint = fingerprint.combine(def_path_hash.0);
	}
	fingerprint
	}

And another case added by my PR:
https://github.com/arielb1/rust/blob/d14ed92f6b5aa23fd06f8affe4554f2c370bc79d/src/librustc/dep_graph/dep_node.rs#L647-L657

I believe the only requirement for DepNode is that the map from QueryKey -> (DepKind, Fingerprint) is injective. It might be a good idea to have a good sense of the requirements there to avoid accidental collisions.

[michaelwoerister]

Just to clarify, we do not require these Fingerprint values to be cryptographically secure in any way. We just need them to be (roughly) as unlikely to collide as random 128 bit numbers would be.

[arielb1]

@michaelwoerister

But cryptographic collision-resistance is a nice property, because it is fairly robust and implies we don't have to worry about odd interactions.

[Enselic]

Triage: Closing as won't fix since I don't see how keeping this open can lead anywhere. Making a case for cryptographic collision-resistance of these hashes is probably better done in an RFC or perhaps even better in Zulip.