[BitTorrent] hash-based requests
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