[BitTorrent] BT2 & hash trees

Gregorio Roper gregorio at gmx.li
Thu Jul 22 05:54:19 EDT 2004


Elliott Mitchell wrote:
>>From: Gregorio Roper <gregorio at gmx.li>
>>Elliott Mitchell wrote:
>>
>>>>So, you don't loose anything if, for the sake of interoperability, you use a block size of 
>>>>1024 bytes for your hash tree (even if 1KB pieces are too small to make sense) and the 
>>>>following internal / leaf hash function (where H is your hash function - probably SHA1)
>>>
>>>Interoperability with what?
>>
>>Interoperability with p2p networks using THEX ( http://www.open-content.net/ ) 
>>that are using the block size and hash functions proposed in the THEX spec ( 
>>this would include Gnutella, OCN, G2 - virtually all networks using tree hashes 
>>already). This gives you one important advantage (which may not be interesting 
>>for you but which is very interesting for me): You can use these networks as a 
>>sort of distributed backup tracker for your torrents without breaking with the 
>>BT protocol and with only small extensions to the respective other networks.
> 
> 
> This assumes you can find the same file on their networks. Possible, but
> highly non-trivial. This would also require a lot of work to keep them
> synchronized.
> 
> Does anyone have plans to implement such a feature on any client? I
> suppose it is a thought, but I'm *very* doubtful of the usefulness.

Searching for a file by its root hash is very easy. Al the networks I mentioned 
can do that today without any changes to the protocol.

The motivation to add such a feature comes mostly due to Shareaza's infamous  BT 
support. Ever since they added BT support you can find virtually all of the more 
popular torrents on Gnutella. The average life time of a file on Gnutella is 
much higher than on BT and I am of course speculating the availability of files 
from BT on Gnutella continues to grow.

Also, since it is becoming more and more likely that LimeWire is going to add my 
BT support, there will most probably be such a feature in one or the other form.


>>You use different hash functions to calculate leaf nodes and internal nodes of 
>>the hash tree to avoid some possible collisions pointed out by the IRTF 
>>Cryptographic Forum Research Group.
> 
> 
> Please point the way to this...   Until you provide a pointer I'm going
> to remain doubtful.

I was not involved in creating the THEX development, its author only mentioned 
that he used different hash functions because the above mentioned group pointed 
out some problems.

John Prevost has provided you with a very good explanation though, and I think 
that he is right. Without different hash functions, you will only need a single 
hash collision (which is still not trivial to find) in order to create a file 
with different content but the same root hash.

> I've already pointed out that things that make sense for REQUEST and
> PIECE messages may or may not make sense for BITFIELD and HAVE messages,
> and vice versa.
> 
> It makes sense for REQUEST and PIECE messages to identify pieces by their
> hash. As there are not many of them the cost is small.
> 
> For this item BITFIELD and HAVE messages are a different matter. Likely
> it is best for HAVE messages to stick with an index into the bitfield.
> When it comes time to send a REQUEST message, then it is time to do the
> bitfield index to hash conversion.
> 
> If you're handling multiple torrents over one connection then each
> message already has to identify which torrent it belongs to, and
> therefore is already transfering a hash with each message. In this case
> HAVE messages have already grown and there isn't much you can do about
> it.

I would prefer having one way of addressing file ranges for all HAVE, CANCEL, 
REQUEST and PIECE messages because it makes my implementation less complex.

>>Transferring the hash tree during the transfer as part of the peer protocol may 
>>not be such a swell idea, - especially if you still plan on addressing single 
>>pieces using the hash. For security, you would have to transfer the hash tree as 
>>a whole (that would be more than 600KB of data only for the first 15 levels) 
>>anyway. So you would probably be better of putting the nth level of your hash 
>>trees along with your root hashes into your torrent file.
> 
> How does transfering the tree as a whole help security? Or perhaps I
> should ask, how does transfering the tree as pieces harm security? Either
> method leads back to the security of the root hash.
>
> I think we've got good evidence that Bram is planning to use the peer
> protocol to transfer the tree data, at which point the question becomes
> what should the encapsulation look like?

Whenever I request a part of the hash tree, I have to be able to verify it 
against the root hash instantly. I cannot do that, if I start with only he root 
hash and request directly some hash for a 32KB piece. I would either have to 
work my way through n levels of the hash tree first, requesting 2*n hashes that 
allow me to verify the hash of that first piece - or I could request the nth 
level as a whole to verify all hashes of the nth level against the root hash at 
once.
The latter solution should clearly be preferred because otherwise you would have 
to request twice as many hashes and send a lot more requests producing more 
overhead. However if you request the nth level of the hash tree as a whole, you 
may easily request 100KB up to even more than 1MB of data.
It would probably be better to keep these hashes in the .torrent file saving you 
some messages you would otherwise have to support. If you are so keen on saving 
the web server hosting the torrent some bandwidth, you may want to consider 
rather adding the .torrent file itself to the .torrent, so all that a client 
needs to start the download is the address of the tracker and the root hash of 
the .torrent file. Then it would first download the .torrent file using the BT 
protocol and get its hashes from the .torrent file. That way you don't have to 
add any messages for requesting hashes.

I don't know what Bram Cohen is planning and actually I won't care until he 
releases some specs. I will just tell you that I don't think that transferring 
hash tree data as part of the peer protocol is a good idea because it makes the 
protocol needlessly complex.

> Depending on how the hashes go over the peer protocol it won't make the
> protocol more complex. If the tree is simply placed in some number of
> pieces then the lowest layers of the protocol don't change at all. At
> higher levels there is some complexity but not too much.
Yes, that may not make the protocol more complex, but it makes my implementation 
a hell of a lot more complex than it is now. I don't want that to happen.

>>One possible scenario for requesting a part of a hash tree that could make sense 
>>  as an optimization (that should not be a requirement by the protocol) is when 
>>you notice one of your 1024KB pieces is corrupted and you are to lazy to 
>>download the whole 1024KB again, so you request the k'th level of the hash tree 
>>of this piece.
>>
>>This is one scenario btw, where you can actually make use of 1KB block size btw: 
>>Suppose one byte of your 1MB piece is corrupted, that's 10 levels above the 1KB 
>>block. You can work your way down the hash tree in 10 requests (that's certainly 
>>less than 200 bytes outgoing traffic) exactly identifying the corrupted block. 
>>The remote host would return you 20 hashes (2 per request) which shouldn't cost 
>>more than 600 bytes (400 bytes for the hashes and less than 200 bytes overhead). 
> 
> 
> Requiring 10 round trips. 5 seconds on a modem (10 if both ends are on
> modems), .2 seconds on DSL/cable, worse on satellite. One of the lessons
> from the X protocol, round trips are expensive.
> 
> These are also going to be tiny packets. 40 bytes for the IP and TCP
> headers on *each* request. If there is other traffic on this connection,
> then it can be combined together and save bandwidth, but this will harm
> latency (oops, can't win).

Latency is like sooooo not an issue for me. And even if you want to add the 
TCP/IP overhead, you will still win with 1KB blocks compared to greater block 
size (e.g. your 16KB), because a block size of 1KB is still a good deal larger 
than one request for two hashes and the reply. You will probably win even more 
using 512 byte blocks.

mfg
gregorio


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