[BitTorrent] Re: bt2 protocol features

John Prevost j.prevost at gmail.com
Thu Jul 15 20:55:02 EDT 2004


On Fri, 16 Jul 2004 01:54:22 +0200, Olaf van der Spek <ovdspek at liacs.nl> wrote:
> 1024?
> That'd mean 16 mbyte of data was invalid.
> Isn't that kinda much with piece sizes <= 2 mb?

It's necessary to fetch a chunk of the hash tree in order to validate
even a single block's worth of data once it's been received.  One
option is to fetch on demand.  Let's do an example:

5 blocks:
         I(ABCD+E) (root)
         /      \
     I(AB+CD)   L(E)*
     /      \     \
    /        \     \
 I(A+B)*   I(C+D)  L(E)
  /  \      /  \     \
L(A) L(B) L(C) L(D)* L(E)

L is the leaf hash, I is the internal node hash, + is byte sequence
concatenation.  Having different functions for L and I is useful to
prevent certain kinds of attacks (which I wouldn't expect to work well
with BT in any case).  A typical difference would be L =
SHA-1("0"+data), I = SHA-1("1"+data).  The leaf L(E) is promoted all
the way to the top, since it has nothing to pair with.  And for
simplicity, I wrote I(A+B) instead of I(L(A)+L(B)), and I(AB+CD)
instead of I(I(L(A)+L(B))+I(L(C)+L(D))), and so on.

In this picture, the root hash (I(ABCD+E)) is the only thing that the
peers receive.  Now say that you receive block C.  The minimum data
that you need to verify the correctness of C is I(AB), L(D), and L(E),
marked on the diagram.  Since you have C itself, you can calculate
L(C), then use L(C) and L(D) together to compute I(C+D), then use that
with I(A+B) to calculate I(AB+CD), then use that with L(E) to
calculate I(ABCD+E).  And now you know that block C is correct, and
you have those other values for later computations.  You need log_2(n)
hashes to validate each block--specifically, you need the hash at each
level of the path you did *not* choose to take.

The power of this approach is that you can receive those intermediate
hashes from untrusted sources, as long as you received the root hash
from a trusted source.  It would be very difficult to forge values for
I(AB), L(D), and L(E) and invalid (or chosen) data for C such that the
root hash is matched.  So the very small root hash is sufficient to
validate the whole file, and to allow verification of small pieces of
the file without having all of the individual block hashes come from a
trusted source (i.e. the .torrent file.)

Now: The *other* approach to distributing the hash data would be to
have each peer simply request the leaf level hashes from their peers
(perhaps all from one peer, perhaps requesting a handful from
individual peers until the list is complete.)  This allows the same
computation, but decreases the final amount of data sent.  Sending
each hash once, including intermediate levels, requires n*log_2(n)*k
space (where k is the hash size), plus whatever protocol overhead. 
Sending only the leaf hashes requires n*k space.  Still, either
approach is workable, with different drawbacks.

In the case of getting all of the leaf hashes at once, there's a
fairly large load of data that needs to be downloaded before any
validation can begin.  For an 8GB torrent with a 16kb block size, that
would be 10MB of data up front, which is probably unreasonable.

In the case of getting only the neccessary pieces each time, the
simplest solution would be to have the PIECE message look like this:

PIECE: length PIECE root-hash piece num-hashes hashes data

Whenever a piece is requested, a peer would include all of the hashes
required to validate that piece, from the top of the tree down.  So in
the above example of block C:

16449 PIECE I(ABCD+E) 3 3 L(E) I(AB) L(D) C
           piece num -^ ^- # of hashes

In the case of a single 8GB file (which is excessively huge for a
single file!) the number of hashes for each piece would be 19, adding
2.3% of the data size to each PIECE message.  In a more reasonable
large file, say 600MB, it would be 16, and add 2.0%.  In a 100MB file
it would be 12, or 1.5%.  So the amount of overhead is kind of high
and irritating, but at least does not increase much with file size.

Contrariwise, the send-them-all-at-once model only adds 0.12% to the
total amount of data transferred, but you need to transfer *all* of it
before any other verification can be done: for the 8GB file, it's 10MB
downloaded before the real downloading can begin.  For the 600MB file,
it's 750kB, and for the 100MB file it's 125kB.

And finally, of course, it's possible to decrease the overhead in both
systems by having larger block sizes (I've been assuming 16kB).  In
the tree-branch-send system, that will only decrease the number of
hashes sent per block by one.

Oh--and as a note, I think some people have suggested that using a
larger branching factor would be a good idea.  That will not in fact
help.  Remember up above, where I said that you need to send the
hashes for the path-not-taken at each level?  If you extend from a
binary tree to an n-ary tree, that extends to *all* of the
paths-not-taken at each level.  So if you switch from a binary tree to
a 4-ary tree, you halve the number of levels involved, but triple the
number of hashes at each level, increasing overhead by a factor of
1.5.

The flip side of that is that if you choose to transmit all leaf
hashes before the transfer even starts, there's no reason to have more
than one level in the tree.  (The root hash would simply be the hash
of all of the leaf hashes combined.)

So my suspicion (from what little Bram has said so far) is: binary
Merkle hash tree, and each PIECE message includes the hashes needed to
validate that piece.  Why?  Because: 1) anything other than binary is
silly, 2) if you're not going to use the tree-ness (i.e. you'll
transfer all leaf hashes) there's no reason to use a tree at all, and
3) sending the validation data with every piece is much simpler than
trying to negotiate which hashes are needed--simple is good.

John.


------------------------ Yahoo! Groups Sponsor --------------------~--> 
Make a clean sweep of pop-up ads. Yahoo! Companion Toolbar.
Now with Pop-Up Blocker. Get it for free!
http://us.click.yahoo.com/L5YrjA/eSIIAA/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