[BitTorrent] Back to Merkle Hash Trees...

Bill Cox bill at viasic.com
Tue Feb 8 02:21:08 EST 2005



On Mon, 2005-02-07 at 23:02 +0100, Olaf van der Spek wrote: 
> Bill Cox wrote:
> >>>Is there some URL somewhere that describes the way Merkle hash
> >>>trees are supposed to be used in bt2? It seems that a lot of
> >>
> >>No (AFAIK), but I've got an experimental implementation described at 
> >>http://62.216.18.38/bt_merkle/
> > 
> > 
> > Olaf,
> > 
> > This spec is excellent.  It's an outstanding document.  Also, it sounds
> > like you've already tested it, so it shouldn't have too many surprises
> > for implementers.
> > 
> > While there are minor points that I would have liked to fine-tune, I
> 
> What would you like to tune?

First, I've got to disagree with Justin...  Your spec seems to me to be
well thought out.  It reads like a spec written by a guy who actually
went and tried it first.  I'm a 41 year old hacker.  I've written a lot
of code conforming to a lot of specs.  I'll take a spec written by a
smart programmer (like Bram) any day over a committee drafted spec that
was formally standardized before ever being coded.

As for those minor points, here's a couple.

I like shadowmatter's suggestion of using array based trees.  In my
experience, the code comes out faster, uses less memory, and is simpler
to write.  Is compatibility with THEX important?  If not, I'd consider
array based trees an improvement.

The gzip requirement for .torrent files bothers me.  For one thing, it's
already out of date, in that bzip2 generally results in better
compression, and I've heard that bzip2 is no longer king either.  It
also goes against the goals of compatibility and simplicity, and given
the smaller .torrent file sizes, this extension seems less important.
Could we get some of the compression by having directory trees rather
than listing full paths for each file?  Replicated path data in
the .torrent files bug me.

The 2^47 byte limit on torrent size evokes an irrational emotional
response in me, like when I see needles used for injections.  I remember
thinking 640K would be more memory than anyone should ever need, and
later that a 2 gig hard drive limit was plenty big enough.  The pain and
suffering 16 vs 32 bit pointer madness caused has scarred me for life.
I think this is a gut reaction rather than a rational concern, but if I
have it, others may also.  Would it be so bad to give piece and request
messages a piece index and a chunk index?

I like the 2^15 fixed size chunk.  It's simple to implement, and forces
chunk alignment so that either a peer has the whole chunk, or none of
it.  However, I'm pretty sure that this fixed chunk size is one of those
things that will bother guys who casually read your spec.  In fact, it
bugged me enough to go spent an hour or so coming up with a variable-
sized chunk scheme.  What I've come up with so far violates
compatibility and is too complex, but it's also fun, so I'll describe
it.  However, the right thing to do is probably stick to 32K byte fixed
chunks.

So let's assume that pieces are 1K byte, the same size used as leaves in
the Merkle hash tree.  This creates multiple problems.  For one thing,
we have to come up with a better way to represent the pieces that peers
have, since the bitfields will be huge otherwise.

We can represent the data that peers have as a tree, just like the
Merkle hash tree.  Instead of sending a bitfield after the handshake, a
peer would send its list of fully downloaded nodes.  A fully downloaded
node would be defined as a node in the Merkle hash tree for which all
leaf piece nodes under it have been downloaded, but who's sibling node
still has pieces under it left to download.  HAVE messages would send
node indexes of fully downloaded nodes, rather than piece indexes.

A node would be identified by it's array index.  A node index would be
prefixed with a byte that states how many bytes long the node index is.
Nodes near the top of the tree would have shorter node indexes.

If clients preferred to download pieces that are close in the tree to
pieces that have already been downloaded, then the data required to
describe their trees should remain small throughout the download
process.  This has the added benefit of minimizing the authentication
path data needing to be transmitted between peers.

To help maintain high numbers of copies of each piece in a torrent,
clients should download rarest pieces whenever their number of full
nodes drops below some threshold.  For example, if there were less than
128 fully downloaded nodes, it might be time to go get that rarest
piece.

HAVE messages should be sent when a client thinks it's worth doing in
order to interest more peers, and not for each piece and full node (that
really wouldn't work so well with a 1K byte piece size).  Early on, when
a node near the bottom of the tree becomes full, it may be worth sending
HAVE messages just to get a few peers interested in you.  Later on, when
almost all your peers have declared that they are interested, you might
only transmit HAVE messages for very high-level newly full nodes.  This
has potential to significantly reduce HAVE messages, which currently
seem to be the most common message in a torrent by far.

Normally, I defer to the KISS rule, but there's an exception clause to
the KISS rule in very fine print...  If an algorithm is fun enough,
programmers will overcome the complexity.  If it's boring, it may never
happen.  It might just be me, but this whole array based Merkle hash
tree variable sized stuff sounds fun.  Besides, it'll perform slightly
better, and what's better than being better?

Ok, perhaps 32K byte chunks are a no brainer and we should move on...

Bill







 
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