[BitTorrent] BT2 & hash trees

Gregorio Roper gregorio at gmx.li
Thu Jul 22 12:55:44 EDT 2004

John Hoffman wrote:
> I considered recommending using THEX as the algorithm for BT2, but THEX 
> is based on the Tiger hash, and on a low-iteration version of the hash 
> at that.  I'm not convinced Tiger is very secure, so I recommend a tree 
> based on SHA1 instead.

Yeah, I wasn't a fan of Tiger either, - especially since we were already using 
SHA1 when THEX was introduced but the problem was we were too late with our 
implementation and some other vendor was already using Tiger so LimeWire had to 
support Tiger too.
I did not propose using Tiger, and actually I expected you to use SHA1 hash trees.

If I were you, I would probably not use THEX (though it suggests support to SHA1 
as well), it requires support for DIME & XML, - both are not trivial to 
implement, even if getting a parser for XML should not be a problem.

> 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 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.

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.

It may be due of my 'upbringing' in the Gnutella world but I always try to use 
existing standards as far as possible.

If I had designed BT, .torrent files would be zip'd XML documents and my peer 
protocol would consist of XML-like extensible messages ;-).


------------------------ Yahoo! Groups Sponsor --------------------~--> 
Make a clean sweep of pop-up ads. Yahoo! Companion Toolbar.
Now with Pop-Up Blocker. Get it for free!

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