[BitTorrent] Re: Back to Merkle Hash Trees...
Joseph Ashwood
ashwood at msn.com
Thu Feb 10 19:47:56 EST 2005
----- Original Message -----
From: "sh4dowmatter" <mgp at ucla.edu>
Subject: [BitTorrent] Re: Back to Merkle Hash Trees...
> I still fail to understand how a Merkle hash tree takes O(n logn)
> space, assuming that the number of leaves (which we start with) is
> proportional to the size of the file.
>
> In any tree -- a binary tree, a ternary tree, any tree where any
> interior node has more than one sibling (indeed, if this weren't the
> case, it would be one lame tree, and you could construct it better) --
> the number of internal nodes is always less than the number of leaves.
> But the number of leaves is O(n), because they are all of a constant
> size (say k) and n is the size of our file. So if the number of leaves
> is O(n), and the number of internal nodes is bounded above by the
> number of leaves, it must be O(n) too! So our total memory requirement
> is O(n).
I think we're both having a problem of not using enough letter. The library
takes n space, the merkle tree take mlogm space, where typically mlogm < n.
So there is an argument that a Merkle tree will fit in n space, but it leads
to missed opportunities to optimize the process.
[altered to use the m I used above, m changed to k, for clarity]
> 1) Computing the leaf hashes takes O(m) time: I think we agree on this
> part. The file has size n, and leaves are hashes are of size k; thus
> the number of leaf hashes is ceil(m/k), which is O(m).
Agreed, the leaf nodes will take O(m) time, if for no other reason than each
must be touched, and there are m of them.
> 2) Computing the internal hashes takes O(m) time
Actually you have not succeeded in establishing that except through flawed
logic, and I have given an exact counter example (the 4 node tree I gave
before, as opposed to the 5 nodes that would've been required under your
estimates).
> It thus takes O(k)
> time.
Correct enough
> Since there are O(m) internal nodes, the total time to compute
> all internal nodes is O(mk).
> You could argue that m is large enough so
> that O(mk) > O(m logm), but then you're totally abusing what
> O-notation is: I can always find some n0 such that for m >= m0, O(mk)
> < O(m logm). And the finale: k is a fixed constant -- so really this
> is O(m) time.
Problem, there are on the order of mlogm internal nodes, where the branching
rate and log base are the same value. Leading to a complete time of O(mlogm)
due to the assumption that they are all the same size and that the hash
function operates on all values of the same length at the same rate.
> The height of the tree is, quite simply, irrelevant. You could have a
> full binary tree, of minimum height, or a completely unbalanced tree
> of maximum height, but the time to compute the internal hashes in the
> tree is the same. This is because the number of internal hashes does
> not vary, and the number of children per internal node is fixed, and
> that is all the computation depends on. So I don't think log n belongs
> into the equation...
You are also making a false assumption that the branching rate needs to be
or even should be a fixed constant, if you reread my statements from before
you will find that the optimal solution for 99+% of the problems is as flat
of a tree as possible, branch rate 2 is as tall of a tree as possible
(excluding degenerate cases) and so is directly contradictory to the optimal
solution.
> Finally, I'm sorry if my last response sounded demeaning or full of
> vitriol.
I'm a cryptanalyst, we're extremely rough and tumble about things and I have
actually had conversations open with (pardon the language) "You're a fucking
idiot, and here's why" wherein he proceeded to rip my work for the last 8
months completely apart, we're actually still friends, there is unlikely to
be anything you could say that would offend me.
> I'm just looking to find an answer we can both agree upon,
> regardless of who (if either!) of us is right.
How's this. We stop bickering over O() numbers, and deal with what's
important. The important part is finding a solution that works extremely
well. I propose using a variable branching tree, that would allow people
such as myself to use the maximum possible branching, while people such as
yourself could use the minimum. Just a few minutes ago I posted a proposal
(I won't duplicate it here) if you would look at it, there might be
something you can comment on.
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