Re: Re: Back to Merkle Hash Trees...

----- Original Message ----- 
From: "sh4dowmatter" <[email protected]>
Subject: [BitTorrent] Re: Back to Merkle Hash Trees...


> I don't know where you people learned your maths and fancy proofs...
> But the last time I checked, a tree with k leaves requires k-1
> "interior" nodes, regardless of how the tree was constructed --
> whether it's maximally unbalanced, full, etc. The size of the tree is
> thus k + k-1 = 2k - 1. And then, "trivially," 2k - 1 < 2k, or O(k).
> But k is some fraction of n, so k = cn for some constant c <= 1. Hence
> the size of the tree is O(n).

Completely incorrect. First and foremost O() cannot be applied to memory 
constraints, there is an entirely seperate notation reserved for that. I 
apologize if I made the mistake first. Second your assumptions are entirely 
fallacious as well. Your assumptions require that the the branch rate be 
fixed, and beyond that it requires that it be fixed at 2. Second, your 
method of computation is invlid for O() notation, O() notation requires the 
use of calculus in the summing, otherwise the variables become unusable. To 
give a firm example the following is perfectly valid for a Merkle tree:
Root = hash(A,B,C)
A - leaf node
B - leaf node
C - leaf node

This has 4 nodes instead of the required 5 under your constructions.  Next 
O() requires that you keep those reals that are critical to the 
understanding, or at the very least disclose them, in this case your 
dropping of the 2 shows a situation where dropping the real eliminates 
information that is necessary for proper understanding. So to be entirely 
blunt, you used the wrong notation, you calculated wrong, and your 
calculations were inaccurate anyway.

> To prove that reconstructing the tree takes O(n) time (assuming
> top-down reconstruction), realize that you have to "verify" 2n-2 nodes
> -- that is, every node in the tree except the root. To verify a node,
> you just need to 1) hash it with its sibling and 2) check that it
> equals the parent. (Actually, note that since this also verifies the
> sibling simultaneously, this only happens for (2n-2)/2 = n-1 nodes.)
> The hashes are a constant size, and there is only one sibling for each
> verification. So verifying a node takes constant time. Once every node
> is the tree is verified, it is constructed. There are 2n-2 (or n-1)
> verifications, which is O(n). Which means constructing the tree is O(n).

Your proof if valid, except for one, not so minor, problem. Your n-space 
equation is incorrect, the Merkle tree requires nlogn space, leading to 
O(nlogn) time to verify. Beyond this reconstruction will also require 
O(nlogn) because the insertion requires that the tree be stepped through 
downwards n times. Since the depth of the tree is logn, the time to insert 
one node will be O(logn), multiply by the n times necessary, and we reach 
O(nlogn) reconstruction time.

> To prove that constructing the tree takes O(n) time, apply a similar
> argument.

And the argument falls apart for exactly the same reason. You are reaching 
your result assuming that your first result is correct, and you made major 
errors in your argument, making such an argument invalid.

Your math is not as bad as I first assumed, and O() notation is horribly 
confusing for a wide range of people. I have even seen professional 
mathematicians mess up on it for the same reasons you have. The reason is 
that they have been taught the non-calculus method that usually delivers 
good answers, and they have been taught to drop all integers.

If you would like to further your education in this regards, I would suggest 
reading most anything published by Knuth, he is well respected and maintains 
nearly perfectly strict notation.
                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/