Re: Back to Merkle Hash Trees...

On Thu, 10 Feb 2005 16:20:38 -0800, Joseph Ashwood <[email protected]> wrote:

> Quite the contrary, a smart client will go for the least impacted portions
> first, and hence the data portiond. [...] In the mean time the smart
> downloader is unable to contribute to the overall bandwidth, making the
> potentially most valuable swarm member a leech.

Lets re-define "smart client". Of course he would like to get rare pieces,
(everyone agrees on this, i guess),  but he also likes to spread love to
his peers (tit-for-tat). This means he is interested in verifying what he
downloaded so far. For this, he needs exactly those parts of the tree
that enable him to verify his pieces. I.e. he needs all his silblings
and all of his ancestors and all of his ancestors silblings.
I hope we all agree so far...

I guess our point of disapprovement is that you think the client needs
the whole tree to verify that piece. This is because the you favor the
flat tree: It has the least overhead, its internal nodes are very very
few, you can count them on one hand. (if i got you right, the optimal
would be just one root hash). With a flat tree, if the clients wants
to verify a piece, it of course needs the piece hash. To verify the
piece hash, it needs, in your optimal flat tree, the whole tree.

The other extreme tree construction favors a binary tree. Here, a piece
has log2(piece count) ancestors, which each have one sister, so it only
needs a fraction (something around O(log2(piece count))) of the tree. On
the other hand, the *total* overhead is bigger, because you have
much more leaves (around O(n) iirc).

Lets throw some numbers around:
I assume internal node piece size is 20 bytes, which would only be the
sha1 hash. It would be bigger if we send the meta-information you and
others proposed. Feel free to multiply any total by your_node_size/20.

Lets say you download a 1 gig file with 4K piece size. This gives you
262 144 pieces. In your flat tree, there would be one root node with
262 144 children, giving a total tree size of (262144+1)*20 = 5 Megabyte
(plus 20 bytes, if you're nitpicking). So the client needs to download
these 5 Megabytes to verify one piece.
In a binary tree, this would make up a perfect binary tree of depth
18, consisting of of 2^19-1 internal nodes, which would make a tree
of about 10 Megabytes. But to verify one piece, the client only needs
to download 2*19 internal nodes, which is 760 bytes.

Of course we could do some tradeoff and use n-ary trees, if someone
would want to code that.

Hope this makes the whole tree-structure discussion a bit more
clear...

HTH,
Kosta


 
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/