[BitTorrent] Have maps (was Merkle, URLs, etc)

Elliott Mitchell ehem at m5p.com
Wed Mar 9 19:47:58 EST 2005


>From: Joseph Ashwood <ashwood at msn.com>
> From: "Konstantin 'Kosta' Welke" <kosta at fillibach.de>
> > On Sun, 6 Mar 2005 17:36:43 -0800, Joseph Ashwood <ashwood at msn.com> wrote:
> 
> [Optimal case for binary trees?]
> > In the case of "I need to verify this one piece to be able to share it".
> 
> Actually the optimum case for that is having the verification in the node, 
> regardless of branching. this then leads to the overhead to verification = 
> depth, binary trees will be deepest, they are not optimal.

Incorrect.

The binary tree will be deeper, however you only need to send one hash
per level. With a non-binary tree you will need to send all the /other/
hashes for verification at each level. This means with the flat model
you're sending all but one hash every time to verify the node. In general
With 'n' nodes and 'b' branching factor, you'll send logb(n)*(b-1) hashes
(actually ceil(logb(n))*(b-1)) for verification of a leaf node. As 'b'
gets higher logb(b) (the height) will approach 1, however b-1 turns into
n.

If you transfer the verification hashes with each piece (in node
verification), you're expending a total of nlog2(n) bandwidth over the
entire payload while flat will cost n^2. Guess which is better.

This is why I suggest handling of blocks of hashes similarly to payload
hashes at the lowest layer. The (possibly large) cost of transfering of
hashes will be accounted for with the rest of the major data transfer.
This also means hashes are transfered *once*, rather than multiple times
with every node.

> > I think that the tree implementation should imply
> > what hash is whose parent and child (for binary trees, this is very easy).
> > So there is no need for "searching". Did I miss something?
> 
> Searching is important when a piece is requested, there is a search overhead 
> to determine whether or not that piece is available. Using a perfectly flat 
> tree this is a search of the minimum possible area, using a binary tree it 
> is a search of the maximum possible area. These represent the extremes 
> available, the binary tree is the most costly.

This is a client issue, not a protocol issue. The tree is a protocol data
structure. What data structure a _client_ uses to resolve hashes/indicies
into an address where a piece is located is *strictly* a client issue.
The protocol cannot mandate a structure to be used.

I hope you're not doing a linear search of your entire set of hashes to
find a match...

> >> The search overhead is related but can be solved using some of the more
> >> esoteric possibilities of the MerklePool concept I laid out before.
> >
> > Sorry I must have missed both the problem and your solution. Can you point
> > me to a date/time and subject of your message so I can re-read it?
> 
> I didn't post about it. The search overhead problem is succinctly "find me 
> piece with hash X" finding it in a Merkle tree is costly, binary is the most 
> costly, flat the least, but finding it in a 256-ary tree in a shared 
> MerklePool eliminates the advantage/disadvantage in this case.

You *don't* search the Merkle tree for a hash X!

The Merkle tree is *strictly* a _protocol_ structure for hash
_verification_, it may or may not relate to the actual data structures
used on the client! The client can (and certainly should) maintain a
search tree or hash table to resolve a hash into the associated piece.

> >> The hash size vs input size problem is that the hashes used slow down as
> >> there is less input, leading to exponential slow down of the entire 
> >> system
> >> as the inputs shrink.
> >
> > Can you please rephrase this sentence so that I can understand it?
> 
> Modern hashes have substantial overhead in the finalization operations, by 
> having the smallest nodes possible the finalization code is executed the 
> maximum number of times. As the size of the nodes shrinks linearly, the 
> number of internal nodes increases super-linearly. As the number of nodes 
> increases the number of times it is necessary to run the finalization code 
> increases. I did have a misstep there, I believe it is only a polynomial 
> increase, not exponential.

Even with finalization being expensive, the more than two orders of
magnitude more data being processed at the leaves overwhelms the cost of
internal node computation.

> >> Is that enough problems or should I think for more than 30 seconds on it?
> >
> > Please think of more. ;)
> >
> > Note that I do neither think that binary trees are the best choice. They 
> > are
> > worst case for tree size but optimal case for quick verification of a 
> > single
> > piece.
> 
> Here is where we substantially differ. In verifying a single piece in a 
> properly formatted n-ary tree (like my proposal) the cost is the tree depth. 
> This is the same optimal cost for binary trees. The n-ary tree will be 
> flatter and so offers faster verification of the piece than the binary 
> version. For reference, my implemenation can verify a single piece of a 
> 478MB file in 4 hashes, assuming 4KB blocks, the same performance for a 
> binary tree would only be a 65KB file, again assuming 4KB blocks. Verifying 
> the same 478MB file would take a binary tree 29 hashes (assuming I counted 
> correctly) approximately 7 times as long. 7 times the time is not a small 
> performance penalty.

The number of times the hash function is run relates to the tree depth.
The amount of data run through the hash function relates to the branching
factor. You are decreasing the number of times the hash function is run,
but increasing the amount of data run through the hash each time it is
run.

If you do verification once (either piecewise, or as the whole tree),
both methods are similar in cost because the node verification is
overwhelmed by the much greater data size of leaf verification. If you
are trying to verify a piece without knowing knowing the validity of the
rest of the tree, the cost of your method is greater because you have to
run a much larger amount of data through the hash.


-- 
(\___(\___(\______          --=> 8-) EHM <=--          ______/)___/)___/)
 \   (    |         EHeM at gremlin.m5p.com PGP 8881EF59         |    )   /
  \_  \   |  _____  -O #include <stddisclaimer.h> O-   _____  |   /  _/
    \___\_|_/82 04 A1 3C C7 B1 37 2A*E3 6E 84 DA 97 4C 40 E6\_|_/___/




 
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