[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
http://us.click.yahoo.com/Z1wmxD/DREIAA/yQLSAA/dkFolB/TM
--------------------------------------------------------------------~-> 

 
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