[Nix-dev] Accidental store paths collisions

[Ludovic Courtès]

Hello,

Peter Simons <simons at cryp.to> writes:

> I have one more question and would appreciate if someone could enlighten
> me. I use a shared store for building nix on both 32- and 64-bit Linux.
> That works great. While bootstrapping the store on MacOS X, however, I
> had the impression that the MacOS store collides with store paths from
> Linux (and thus cannot be shared). Is that possible?

I think the probability of an accidental collision between any two store
paths (regardless of the ‘stdenv.system’ value) is that of an accidental
collision between any two SHA256 hashes of two different inputs.

Since this is a 256-bit hash, we’d have to produce (on average) 2^128
derivations before an accidental collision occurs.  The probability that
a given pair of distinct derivations yield the same hash is 2^-256 [0].

To paraphrase [0], you are roughly 2^186 times “more likely to win a
U.S. state lottery /and/ be struck by lightning simultaneously than you
are to encounter this type of error” in your Nix store.  :-)

Thanks,
Ludo’.

[0] See “Compare-by-Hash: A Reasoned Analysis”, John Black, 2006,
    http://www.cs.colorado.edu/~jrblack/papers.html .