[BitTorrent] Back to Merkle Hash Trees...

Elliott Mitchell ehem at m5p.com
Fri Feb 11 18:24:45 EST 2005


>From: Justin Cormack <justin at street-vision.com>
> > I would tend to use the block hash in REQUEST and PIECE messages because
> > that is enough to uniquely identify the block, offset, and which torrent
> > it belongs to without any additional information.
> 
> no it isnt, 2 torrents could have the same leaf hash somewhere, but be part
> of different trees. This would be a problem, as they have different parents.
> Also hashes are 20 bytes which is quite long.

Replaces piece#, offset and length, 12 bytes for 20. On a multi-torrent
connection, also takes care of which of the multiple torrents is being
mentioned (either 4 or 20 bytes). So exchanging 12/16 bytes for 20. Given
that REQUEST and PIECE messages occur once per piece, these messages are
less than 0.1% of the bandwidth used. So bandwidth isn't an issue.

As to collisions. You've claimed knowledge of Cryptography, so you should
know the numbers just as well as I do. 2^80th blocks before you hit a 50%
chance of a collision with SHA1. We're discussing block sizes of 16KB or
32KB. So the combined torrents will have to be 2^96 bytes for a 50%
chance. More than 65,536 yottabytes (the listing of prefixes I found
topped out at 10^24/2^80/yotta).

Such a large collection is a vague concern for a super-huge cache in
maybe 30 years time. By that point we'd be worrying about having to go to
something larger than 64-bit data types in the protocol to handle so much
data. I'll admit this is something to be aware of and a concern for the
future, but the chance of two leaves on two distinct torrents on the
whole of the planet Earth having the same hash value within the next ten
years is pretty well zero. You're okay to mention it as a concern for the
future, but your Cryptography reputation with me it fading for suggesting
it is a severe concern now.


-- 
(\___(\___(\______          --=> 8-) EHM <=--          ______/)___/)___/)
 \   (    |         EHeM at gremlin.m5p.com PGP 8881EF59         |    )   /
  \_  \   |  _____  -O #include <stddisclaimer.h> O-   _____  |   /  _/
    \___\_|_/82 04 A1 3C C7 B1 37 2A*E3 6E 84 DA 97 4C 40 E6\_|_/___/




 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/BitTorrent/

<*> To unsubscribe from this group, send an email to:
    BitTorrent-unsubscribe at yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/
 





More information about the BitTorrent mailing list