4 ms·

> Each artifact is identified by a cryptographic hash of its content, expressed as a lower-case hexadecimal string [...] It is assumed that the hash names of a

> Each artifact is identified by a cryptographic hash of its content, expressed as a lower-case hexadecimal string [...] It is assumed that the hash names of artifacts are unique - that every artifact has a different hash Isn't that kinda scary with the birthday problem paradox for people who use Fossil to manage a large number of artifacts

MathMonkeyMan 3y ago
I don't think it will be a problem: <https://fossil-scm.org/home/doc/trunk/www/hashpolicy.wiki https://fossil-scm.org/home/doc/trunk/www/hashpolicy.wiki>
eesmith 3y ago
As a rough approximation, you need something like sqrt(N) entities before the birthday paradox becomes an issue. The Wikipedia article at https://en.wikipedia.org/wiki/Birthday_problem#Square_approximation https://en.wikipedia.org/wiki/Birthday_problem#Square_approx... gives the approximation as: n = sqrt(2 * m * p(n)) where p(n) is the probability of having a collision. Let p(n) be 1e-9 (a 1 in a billion chance). With fossil's old default of SHA1's 160 bits you'll need roughly sqrt(2 * 2^80 * 1e-9) = 49 million artifacts before the likely duplicate. A 1 in a billion chance might still be scary (if everyone on Earth has their own 50 million repo, each with unique artifacts, then there will be duplicates!), but SHA1 use in fossil is mostly a historical issue. With fossil's new default (since v2.10 in 2019) of SHA3-256, you'll need something like 1.5e34 artifacts before there is a 1-to-a-billion chance of a duplicate. As MathMonkeyMan's link points out, you can configure your repository to "shun-sha1" and only allow sha3.
- gliptic 3y ago
  It's not nearly that bad. You effectively did the sqrt twice by setting m = 2^80 when it should be 2^160. You need 5.4e19 artifacts before the chance is 1 in a billion.
  - eesmith 3y ago
    Thanks for the correction!
- sebstefan 3y ago
  That's exactly the reply I was looking for, thanks
rkangel 3y ago
Note that exactly the same constraints exist for Git.

MathMonkeyMan 3y ago

I don't think it will be a problem: <https://fossil-scm.org/home/doc/trunk/www/hashpolicy.wiki https://fossil-scm.org/home/doc/trunk/www/hashpolicy.wiki>

eesmith 3y ago

As a rough approximation, you need something like sqrt(N) entities before the birthday paradox becomes an issue. The Wikipedia article at https://en.wikipedia.org/wiki/Birthday_problem#Square_approximation https://en.wikipedia.org/wiki/Birthday_problem#Square_approx... gives the approximation as: n = sqrt(2 * m * p(n)) where p(n) is the probability of having a collision. Let p(n) be 1e-9 (a 1 in a billion chance). With fossil's old default of SHA1's 160 bits you'll need roughly sqrt(2 * 2^80 * 1e-9) = 49 million artifacts before the likely duplicate. A 1 in a billion chance might still be scary (if everyone on Earth has their own 50 million repo, each with unique artifacts, then there will be duplicates!), but SHA1 use in fossil is mostly a historical issue. With fossil's new default (since v2.10 in 2019) of SHA3-256, you'll need something like 1.5e34 artifacts before there is a 1-to-a-billion chance of a duplicate. As MathMonkeyMan's link points out, you can configure your repository to "shun-sha1" and only allow sha3.

gliptic 3y ago
It's not nearly that bad. You effectively did the sqrt twice by setting m = 2^80 when it should be 2^160. You need 5.4e19 artifacts before the chance is 1 in a billion.
- eesmith 3y ago
  Thanks for the correction!
sebstefan 3y ago
That's exactly the reply I was looking for, thanks

rkangel 3y ago

Note that exactly the same constraints exist for Git.