Re: Back to Merkle Hash Trees...

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

A requirement for an RFC is an open source implementation. In fact nothing
is accepted without several. The process of drawing up standards involves
a lot of testing, discussion and analysis. (The name RFC is misleading,
and most only ever acquire draft status).
 
> 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.

It is generally best not to specify an implementation method like array
based but to make it compatible with such an efficient implementation.
 
> 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.

Given that http can request gzip it is pointless adding it to the
protocol.

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

Agree, see my comments on sizes elsewhere.
 
> 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.

Interestingly quite similar to my scheme sent before your mail arrived.
 
> 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...

32k byte needs justifying.


 
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:
    [email protected]

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/