[BitTorrent] BT2 & hash trees

John Hoffman theshadow at shambala.net
Thu Jul 22 14:37:45 EDT 2004

>>I did some tests and calculating hashes on such a fine-grained level 
>>does impose a significant amount of additional overhead, and since BT 
>>never transfers data at that level anyway, I don't recommend using a 
>>block size below 4K (and 16K would be much better)  for the BT2 tree 
>>hashes.  As for interoperability, if you really want it, there's no real 
>>reason you can't include THEX roots in the torrent files in addition to 
>>the BT2 root hashes.  There doesn't need to be a one-to-one 
>>correspondence between THEX's and BT2's tree's leaf node sizes, so long 
>>as one is as factor of two of the other.
>I don't quite understang: Calculating hashes on such a fine-grained level does 
>not slow down the hashing process by more than 2% compared to hashing the file 
>as a whole. Where do you see the significant overhead?

I did a test on CPU usage; while the effective overhead may be smaller 
during practical use, since disk operations would be the bottleneck, I 
still think saving CPU is worthwhile.

>I did not suggest that you should transfer the hashes for 1KB pieces, I just 
>proposed using the same segment size for the leaf nodes of the tree and the same 
>way of distinguishing between leaf hashes and internal hashes. To which level 
>you transfer the hash tree does not make any difference to me. You could 
>transfer the hashes for 1,024KB pieces or 512KB pieces, any multiple of 2 of the 
>segment size. If you used a different segment size or different internal / leaf 
>hash functions you get a different root hash which is a problem for me.

Obviously.  But if you aren't going to use it on that level, I don't see 
any significant reason to generate it on that level either.

>Of course, I can get around such a problem. Having BT2 create hash trees in a 
>similar fashion to THEX is just very convenient for me. I could take those sha1 
>tree root hashes using a simple URN (uniform resource name) like 
>urn:tree:sha1:XXXXXX (or urn:tree:tiger:XXXXX in case of a tiger tree) and save 
>it. If I do a search for urn:tree:sha1:XXXXXXX some Gnutella clients will 
>already understand it because the urn:tree: namespace is already more or less 
>defined and there is a slim chance of one or the other Gnutella client already 
>calculating this kind of hash.
>If you decide to use something else, I couldn't use the same namespace but still 
>I could work with it. For .torrents created by LimeWire clients, I would simply 
>add some additional root hashes to the .torrent.

BitTorrent's paradigm is largely incompatible with searchable systems 
like Gnutella.  While there may be some advantages to being able to 
interface with such systems, I don't think it's appropriate to change 
the design of the tree to match such systems, especially since, as you 
said, most clients would never have generated the urn:tree:sha1 
signatures anyway.  It's better IMO to have a hash tree optimized for 
BitTorrent and then add a urn:tree:tiger key if desired.

------------------------ Yahoo! Groups Sponsor --------------------~--> 
Yahoo! Domains - Claim yours for only $14.70

Yahoo! Groups Links

<*> To visit your group on the web, go to:

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

<*> Your use of Yahoo! Groups is subject to:

More information about the BitTorrent mailing list