Re: Have maps (was Merkle, URLs, etc)

----- Original Message ----- 
From: "Elliott Mitchell" <[email protected]>
Subject: Re: [BitTorrent] Have maps (was Merkle, URLs, etc)


>
>>From: Joseph Ashwood <[email protected]>
>> From: "Konstantin 'Kosta' Welke" <[email protected]>
>> > On Sun, 6 Mar 2005 17:36:43 -0800, Joseph Ashwood <[email protected]> 
>> > 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.

Actually you will need 2, otherwise you cannot complete the hash computation 
for the next level.

> With a non-binary tree you will need to send all the /other/
> hashes for verification at each level.

For binary you will as well, or did you forget that the hash actually has to 
be computed?

> This means with the flat model
> you're sending all but one hash every time to verify the node.

Completely incorrect. Each hash only needs to be known once, so the transfer 
overhead is necessarily linear in the number of internal nodes. The n-ary 
tree has fewer internal nodes, and hence will have lower cost.

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

I seriously hope you were half-asleep when you wrote this. In the binary 
tree case you will have nlog2(n) bandwidth, in the K-ary tree case you will 
have nlogK(n) bandwidth. Guess which is better.

I believe your misunderstanding is the belief that each child node needs to 
have the hashes of all it's direct siblings in order to verify, that is 
incorrect, each parent node needs to hashes of it's children in order to 
verify, greater branching = lower overhead = faster verification.

> 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 will grant that there are ways to transfer the hash once instead of the 
twice that I have proposed, but hose methods also require downloading the 
siblings before verification of a node. If we really want to take this as 
far as possible it is also possible to compute the Merkle tree without any 
transferred hashes, but that is more wasteful than even the binary trees.


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

Here we have another fallacy on your part. 2 orders of magnitude will not 
overcome the finalization cost in the sizes that are typically discussed 
(4KB seems the most common). The choice still comes down to the number of 
hashes per file size. In the example I gave (4KB blocks, 478 MB) this was a 
difference of 7 fold, even if your argument held, that would still leave 
N-ary trees more efficient, two orders of magnitude would only bring the 
difference down to 1.75x, still well above being equal to N-ary trees.


> The number of times the hash function is run relates to the tree depth.

That is correct.

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

And due to the finalization even if your 2 orders of magnitude was correct, 
the N-ary tree would still be better.

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

Incorrect. At the sizes being discussed the dominant factor is the 
finalization of the hash (e.g. IIRC finalization of SHA-512 takes 20 times 
the number of computations of inserting 1024-bits), and as such the smaller 
the number of hashes, the faster it will be. I will admit that as filesize 
approaches blocksize the n-ary advantage disappears, but since we are 
discussing blocks in the KB range, and files in the GB range, this is no 
where near reality.

In addition you are making heavily flawed assumptions, you are assuming that 
the binary tree only has to verify once, but assuming that the n-ary tree 
must verify multiple times. In truth the n-ary tree will have to verify 
fewer times than the binary.

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

I was going to say that there are cases where that is true, but we've 
already established that binary trees require at least as many hash data 
insertions as N-ary trees, which leaves the number of finalizations as the 
dominant factor, N-ary has fewer, N-ary is more speed efficient.

N-ary is more speed efficient in every case. N-ary is at least as space 
efficient in every case. N-ary is more hash efficient. N-ary is inherently 
superior to the binary trees for BitTorrent.
                    Joe 



 
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/