[BitTorrent] Re: Back to Merkle Hash Trees...
Joseph Ashwood
ashwood at msn.com
Sun Feb 6 16:00:38 EST 2005
----- Original Message -----
From: "sh4dowmatter" <mgp at ucla.edu>
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:
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