[BitTorrent] BT2 & hash trees

Elliott Mitchell ehem at m5p.com
Thu Jul 22 19:57:31 EDT 2004


>From: Gregorio Roper <gregorio at gmx.li>
> 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.

Yes, and the file on those networks will be *exactly* identical? No
comments in the file headers which will cause the hashes not to work? Not
to mention using exactly the same hash structure? (the number of bytes in
the lowest level of hashes is actually one of the smaller issues for
this)



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

Without more data I must consider this claim *very* dubious.

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

"still not trivial to find" is putting it mildly. You do need some way to
confirm that you've got everything, and that must be verified by the root
hash, but distinct hashes are far from the only way of doing this.


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

I'm noting you using the phrases "_I_ would prefer" and "_my_
implementation". I've already shown two sample implementations of exactly
what I am suggesting. They didn't require very much work at all to
produce. Given this I must reject any assertions that it is hard to do.

http://www.m5p.com/~ehem/BitTorrent.patch  (against mainline 3.4.2)
http://www.m5p.com/~ehem/libbt.patch       (against libbt 1.02)

(note that these actually use the older complete hash in the HAVE
messages, I may get these updated soon)


> 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 

I concur with Olaf's answer to this. You can retrieve the first level,
get two hashes and verify against the root, then go for the second level.
Alternatively you can retrieve the entire second level, getting four
hashes, from them compute the first level and thereby confirm against the
root. Care needs to be taken that the jump size is right, but skipping 10
levels is pretty reasonable.

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

This is almost the exact approach I've been thinking of for some time
here. I can't read minds, but I suspect this is along the lines of what
Bram is thinking of.

The main issue becomes how exactly you pack the tree into BT pieces.
Likely the torrent file should contain three crucial pieces of
information, the hash of the entire file (useful for confirmation by
shell scripts or paranoid humans), the root hash of the file, and a tag
pointing to the first piece containing hashes. From this point on you
treat blocks of hashes as ordinary data blocks.

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

I disagree. The above is a pretty simple way to do it. Also, you're not
going to be transfering hash data at the 1KB sub-piece or 16/32KB block
level in a torrent file. BTv2 /might/ place 256K piece resolution in
torrent files, but I highly doubt any lower because generally that isn't
needed, and the size is pretty large. This leaves the peer as the obvious
place for the fine grained data, leaving the question of how you pack
hashes into data blocks.


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

Hmm, that phrase again, "_my_ implementation". Please see above,
continued claims that this will be hard to implement may cause me to
start ignoring you.


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

Latency isn't a problem on my connection either, but for some people it
is an issue. Transfering a 16KB block will remove 4 levels of hashes
being transfered, as 16KB will only take a little over 2 seconds on a 56k
modem; it seems that we have broken even, trading latency for bandwidth.
On faster links latency will be much smaller, but again due to the higher
bandwidth the cost of transfering more data will also be smaller, so yet
again the cost is similar. As the BT protocol may end up with block size
hard coded, it seems worthwhile to use 16KB blocks everywhere.



>From: Gregorio Roper <gregorio at gmx.li>
> > In the case of a software/hardware failure it is unlikely they'll be able
> > to compute checksums correctly and I'd be surprised that you got anything
> > out of them (have to be a really subtle failure to manage to send things,
> > and not get caught somewhere). In a case like this I suppose you /might/
> > manage to only damage a portion of a block.
> > 
> > Enemy action is far more likely to produce failures that don't get caught
> > in the network stack. In a case like this is enemy going to bother only
> > damaging 1KB and send the other 15KB to you intact? Why not send as much
> > corrupt data as possible, and cause the most damage possible? In this
> > case it is *highly* unlikely that *any* of the data this peer has sent to
> > you is valid; so why bother verifying 1KB sub-blocks when almost
> > certainly the *entire* 16KB (or 32KB with some clients) block that was
> > sent is bad?
> 
> Actually most file corruptions are caused by sloppy programming. In a 
> multi-vendor environment the occasional failure of one vendor is not fatal, so 

You didn't say anything about my point. You expect to get _any_ useful
data out of such a badly implemented peer?

> it is likely to go unnoticed for a long while (aka lessons learned from Gnutella 
> I to X). Even worse, p2p clients are very often created by notorious hackers who 
> do not believe in unit tests or comments.

Oh gee, I imagine everyone on this mailing list is grateful for your
feedback.

> An attacker trying disrupt the BT network would not upload corrupt ranges, he 
> would simply take down the trackers.

I said "enemy action", not "trying disrupt" (though the example was a
disruptive one). Enemy action could be as simple as a leech client trying
to send you garbage to pursuade you to send data in return.

There are folks proposing methods of implementing distributed trackers,
making the trackers harder to attack. If they succeed the clients will
become a more interesting target. If the BT protocol (or even merely one
client) becomes easier to attack, an attacker will target it as an easier
target.


>From: John Hoffman <theshadow at shambala.net>
> 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.

Ouch! Lesson from Cryptography, if it isn't well reviewed it is almost
certainly garbage. The design of Merkle trees *requires* a secure hash
to work, such as SHA1. As I haven't seen any reviews of the "Tiger" hash
in Cryptographic circles, time to "Run Away! Run Away!"


>From: Gregorio Roper <gregorio at gmx.li>
> 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.

If you don't want to use THEX, then why are you so interested in
interoperability with it?


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

Good idea. Thing is there isn't one yet for BitTorrent version 2, so it
will be written as things progress.

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

Yuck. Hard to deal with, often insecure. Though I don't like the existing
method of combining files in BT, XML is just plain silly.

 
>From: John Hoffman <theshadow at shambala.net>
> 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.

Good paragraph to read.


-- 
(\___(\___(\______          --=> 8-) EHM <=--          ______/)___/)___/)
 \   (    |         EHeM at gremlin.m5p.com PGP 8881EF59         |    )   /
  \_  \   |  _____  -O #include <stddisclaimer.h> O-   _____  |   /  _/
    \___\_|_/82 04 A1 3C C7 B1 37 2A*E3 6E 84 DA 97 4C 40 E6\_|_/___/




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