4 ms·

>Just imagine if this was done all the way down to the piece level. I don't know about that. With a reasonably large number of users, wouldn't you start seeing

>Just imagine if this was done all the way down to the piece level. I don't know about that. With a reasonably large number of users, wouldn't you start seeing hash collisions via birthday paradox? Might be better off keeping it at the file level. (Though this does incentivize malicious users to find hash collisions of particular files they want to defend, and seeding the swarm with garbage files)

doomrobo 6y ago
Hashes are now 256 bits. In order to get a collision with probability 1% you need to produce about 4e37 hashes. For comparison, if you had a 5GHz computer that did a SHA-256 hash every cycle and gave 100 of these computers to every human on Earth, it'd take over 300 million years to produce 4e37 hashes.
- ShinTakuya 6y ago
  Yep, basically while it's entirely possible (as per Murphy's Law) that there'll be an accidental collision, the likelihood is close to zero. It's a fair risk to be taking.
- fenomas 6y ago
  > In order to get a collision with probability 1% you need to produce about 4e37 hashes Does "get a collision" here mean finding a particular collision with a known hash, or finding any collision between any two of the generated hashes?
  - doomrobo 6y ago
    The latter. I used the formula from the Wikipedia page on the birthday attack: p ~= 1 - e^{-n^2/2H} where n is the number of items you've picked and H is the size of the universe
    - fenomas 6y ago
      I see, thanks!
fomine3 6y ago
All git objects on GitHub has unique hash in 2017 even though git uses relatively weak SHA-1. SHA-256 should be safe. https://github.blog/2017-03-20-sha-1-collision-detection-on-github-com/ https://github.blog/2017-03-20-sha-1-collision-detection-on-...
em-bee 6y ago
the birthday paradox comes from the fact that there are an extremly small number of birthdays. sha-256 was chosen because it provides a sufficiently high number of different hashes that this won't be an issue for the forseeable future. more details here: https://stackoverflow.com/questions/4014090/is-it-safe-to-ignore-the-possibility-of-sha-collisions-in-practice https://stackoverflow.com/questions/4014090/is-it-safe-to-ig...

doomrobo 6y ago

Hashes are now 256 bits. In order to get a collision with probability 1% you need to produce about 4e37 hashes. For comparison, if you had a 5GHz computer that did a SHA-256 hash every cycle and gave 100 of these computers to every human on Earth, it'd take over 300 million years to produce 4e37 hashes.

ShinTakuya 6y ago
Yep, basically while it's entirely possible (as per Murphy's Law) that there'll be an accidental collision, the likelihood is close to zero. It's a fair risk to be taking.
fenomas 6y ago
> In order to get a collision with probability 1% you need to produce about 4e37 hashes Does "get a collision" here mean finding a particular collision with a known hash, or finding any collision between any two of the generated hashes?
- doomrobo 6y ago
  The latter. I used the formula from the Wikipedia page on the birthday attack: p ~= 1 - e^{-n^2/2H} where n is the number of items you've picked and H is the size of the universe
  - fenomas 6y ago
    I see, thanks!

fomine3 6y ago

All git objects on GitHub has unique hash in 2017 even though git uses relatively weak SHA-1. SHA-256 should be safe. https://github.blog/2017-03-20-sha-1-collision-detection-on-github-com/ https://github.blog/2017-03-20-sha-1-collision-detection-on-...

em-bee 6y ago

the birthday paradox comes from the fact that there are an extremly small number of birthdays. sha-256 was chosen because it provides a sufficiently high number of different hashes that this won't be an issue for the forseeable future. more details here: https://stackoverflow.com/questions/4014090/is-it-safe-to-ignore-the-possibility-of-sha-collisions-in-practice https://stackoverflow.com/questions/4014090/is-it-safe-to-ig...