[BitTorrent] Back to Merkle Hash Trees...

Elliott Mitchell ehem at m5p.com
Fri Feb 11 02:15:18 EST 2005

>From: "Joseph Ashwood" <ashwood at msn.com>
> ----- 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]

"library"? Meaning payload (actual content)? m and k being? (node count
and branching count?)

Any record keeping data is going to grow as the payload grows, as long as
it is no worse than linear I think we're in pretty good shape.

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

Reading the payload from memory or storage is going to be roughly linear
with the size of the payload. It doesn't matter if the computation is
worse than linear with respect to anything other than the payload size.
If it is no worse than linear WRT payload size, then we're going as fast
as we can read the payload and we cannot do any better.

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

As long as we are no worse than linear with respect to payload, this is
irrelevant. I suspect variable branching will lose due to complexity.

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

As long as we are no worse than linear with respect to payload, this is
irrelevant. I suspect (though you're welcome to code and prove me wrong)
variable branching will lose due to complexity.

>From: Joseph Ashwood <ashwood at msn.com>
> ----- Original Message ----- 
> From: "Konstantin 'Kosta' Welke" <kosta at fillibach.de>
> > in order to verify a downloaded piece, one needs the part of the
> > hash tree that verifies it. This means that usually, the the parts of the
> > hash tree that are needed to verify the piece will be downloaded in 
> > parallel.
> > A smart client would of course try to download the hash tree first, but
> > this is not a must at all.
> Quite the contrary, a smart client will go for the least impacted portions 
> first, and hence the data portiond. The reason for this is simple; having 
> the least available portions makes it more likely that the downloader will 
> finish a download. As the seeds go offline the data portions will become 
> more scarce, while the tree will be propogated, the smart downloader simply 
> has to wait around and collect the tree later. In the mean time the smart 
> downloader is unable to contribute to the overall bandwidth, making the 
> potentially most valuable swarm member a leech. I see this contradictory 
> condition problematic at best.
> >> There is a minor escape hatch in that eventually those clients should 
> >> have
> >> the tree, but with a large tree, and a slow modem that could be quite 
> >> some
> >> time away.
> >
> > In the end, they have to download ~2% more. So if these 2% take too
> > much time, then the whole file takes 50 times too much time :)
> You're looking at it the wrong direction.
> As the modem becomes the only source for data portions the entire swarm will 
> grind to a halt waiting on the modem. Take an extreme situation; the swarm 
> has 10,000 members, 9,999 members have effectively unlimited connections, 
> one has a modem. The modem line is the only member with large portions of 
> the data, everyone else has the tree. The tree of course propogates very 
> quickly among 9,999 members, but the modem, because it won't upload 
> unverified data, has no bandwidth coming in until the entire tree is 
> exchanged (upload speed = 0; download speed = 0). Once the entire tree is 
> exchanged among the rest then the modem gets some bandwidth, and begins 
> downloading the tree, very slowly. Eventually the modem has downloaded the 
> parts of the tree necessary to verify pieceN, and so uploads that piece. Now 
> the modem if effectively cut off again as the bandwidth kings swap the new 
> piece around, repeat until the modem has uploaded the entire file. The end 
> result is that this network of monstrous bandwidth is forced down to the 
> transfer rate of a modem, perhaps worse as multiple requests are serviced 
> for the same blocks.

I completely reject your argument.

You are correct that clients should tend to go after rare pieces first
(I doubt there is a client that doesn't do this). It would be ludicrus
for a client to get the entire payload and not the tree for two key
reasons: First, without the tree the client cannot verify that it has
any good data and could therefore of been garbage during uploads and
given the peer credit for uploading. Second, if a client has the entire
payload the client can completely regenerate the tree, and in fact
doesn't care about the tree because it is simple useless overhead at that

The tree is merely a means to an end, not the end itself!

> On multi-torrent connections. It may be beneficial to include the hash of 
> the complete file in every 6-tuple making it a 7-tuple, but since this will 
> be a waste of space the majority of the time there is little reason for it.

Once per peer handshake, irrelevant overhead.

I would tend to use the block hash in REQUEST and PIECE messages because
that is enough to uniquely identify the block, offset, and which torrent
it belongs to without any additional information.

(\___(\___(\______          --=> 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:

<*> To unsubscribe from this group, send an email to:
    BitTorrent-unsubscribe at yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:

More information about the BitTorrent mailing list