[BitTorrent] hash-based requests

Justin Cormack justin at street-vision.com
Tue Feb 15 20:45:05 EST 2005

> >From: Justin Cormack <justin at street-vision.com>
> >  
> > > If HAVE messages are somehow indexed to tree location, then it works
> > > pretty well.
> > 
> > You can encode the path down a binary tree (left = 0, 1 = right) as the
> > HAVE message payload. Thats fairly independent of how (if at all) you
> > actually index your nodes. You can with non binary trees too if you insist...
> Problem is this turns back into a variable length string.

But log N bounded, which isnt very much. But it doesnt buy you anything.
> > > > The other alternative is a two-phase protocol where you first obtain the Merkle
> > > > tree before you can do anything else.
> > > 
> > > I'm working on a sample implementation which computes the hashes, and
> > > uses a midsize branching factor. Turns out working with n-ary trees isn't
> > > always easy.  %-)
> > 
> > Its almost never worth it. Possbly never... Whats your reason for not using
> > binary?
> I'm working with block size divided by hash size as the branching factor.
> This results in a node fitting into a single message. At the same time
> a block of hashes can be accounted for like a payload block. Should also
> mollify the folks looking for a flatish tree (2TB with only 3 levels).
> Problem is computing the indicies correctly.  %-)

Well you can get that right (and padding the tree with empty leaves (length 0,
hash to match) might help.

However why not have a binary tree and send more children and granchildren
with a request if you want to get the message size up? It pretty much amounts
to the same thing and is simpler. With a 32k message, and 20 byte hashes, 
each request will get 10 levels of a binary tree in one message (slightly
smaller, so only 1TB fits in 3 levels...)

Yahoo! Groups Links

<*> To visit your group on the web, go to:

<*> To unsubscribe from this group, send an email to:
    BitTorrent-unsubscribe at yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:

More information about the BitTorrent mailing list