[BitTorrent] BT2 & hash trees
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