[BitTorrent] Re: bt2 protocol features

Stephen Thomas flabdablet at yahoo.com
Fri Jul 16 23:08:52 EDT 2004


--- In BitTorrent at yahoogroups.com, John Prevost <j.prevost at g...>
wrote:
> 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.

Given that the "real" downloading of which you speak generally happens
in a random order, meaning you can't make much use of the downloaded
file until almost all of it has arrived anyway, why is it useful to
make a conceptual distinction between downloaded hash data and
downloaded file data?  You have to download the whole lot regardless;
why not pick the scheme that minimizes the total amount?

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

The reason to have more than one level in the tree is that if you
chunk the hashes into blocks the same size you break your files into,
you can then use exactly the same mechanisms for transferring and
verifying blocks of hash data as you do for transferring and verifying
blocks of file data: each incoming block of either is immediately
verifiable against the trusted hash value you had to have in order to
ask for the block in the first place.

There is also no need to transfer *all* the hash data up front; *some*
will do.  At any stage, there is nothing to stop you requesting any
block for which you already hold a hash code.  Naturally, the very
first block you will ever collect will be the one that matches the
root hash, because that's the only hash you hold to start with, but
from there on it's open slather.

There would be nothing to stop you working your way from the root down
the left-hand edge of the tree and picking up the first file block to
have a sniff at before committing to collecting any more tree or data.
ISTM that this would be kind of pointless, because if you're not
getting your root hash from a trusted source you're screwed anyway,
but you *could* do it.

The .torrent file kind of disappears into the machinery with this
scheme, and since there's no need to download it from a central point
there's no pressing need to keep it absolutely teeny-tiny; multiple
megabytes of hash info for an 8GB file won't overload anybody.

If you're willing to countenance total hash overheads of the order of
2% (as you seem to be, given your support for the binary Merkle tree
scheme) you could do a ~60-way hash tree scheme with blocks as small
as 2K.  With a more reasonable block size - say 16K - you could use
super-robust SHA256 hashes and still keep hash tree overhead under
0.2%.

Another interesting possibility is to allow variable block sizes up to
a maximum of say 16K, and use a tree of hash-code-and-data-length
values in place of pure hash codes; any time you saw a data length
exceeding the defined maximum block size, you'd know there were more
tree levels between there and the leaves.  With careful publishing,
this could allow overlap between swarms for individual files out of a
tar or zip archive or ISO image and the swarm for the whole thing.

This idea plays well with another, which is that in a scheme of this
kind there is no need for all the leaf nodes to be the same distance
from the root.  For example, you could assemble an ISO image using the
existing hash trees for the files inside it, augmented with
hash+length codes covering the ISO overhead stuff before (and possibly
between) those files.  You'd end up with a messy-looking unbalanced
tree, but the vast bulk of it would be close to optimal and it would
be nicely shareable.

Another nice optimization you can do with a hash tree is to unify the
Bitfield, Have, Want and Unwant message formats: all such messages
could consist of a hash code followed by an optional bit string.  For
an N-way hash tree, this allows you to specify <= N blocks with a
single message of 32 bytes (assuming SHA256) plus N bits.  If these
messages are suitably batched it should be possible to better the
performance of the existing BT index-based message scheme; perhaps
breadth-first recursive schemes would allow even better performance
again.

> Why?  Because: 1) anything other than binary is
> silly,

Silliness can sometimes be quite appealing :-)

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

Trees are beautiful, man.  Hug a tree today!

> 3) sending the validation data with every piece is much simpler than
> trying to negotiate which hashes are needed--simple is good.

Sending validation data with each piece looks to me like overhead that
could be used more effectively.  But of course I have yet to write any
code and therefore have no credibility, as usual.  Sigh.

Cheers
Stephen




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