[BitTorrent] Back to Merkle Hash Trees...

Joseph Ashwood ashwood at msn.com
Thu Feb 10 19:20:38 EST 2005


----- Original Message ----- 
From: "Konstantin 'Kosta' Welke" <kosta at fillibach.de>
Subject: Re: [BitTorrent] Back to Merkle Hash Trees...


> 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 am completely unconcered about the effect the modem has on downloading for 
the modem user, they expect that performance, but the rest of the network 
should not be completely hosed by that one smart client. By flattening  the 
tree as far as possible (generally two levels) this situation becomes almost 
impossible, and if the formatting is done correctly, the tree is embedded 
into the data blocks (e.g. {nodeInfo, nodeData}) leaving only a very small 
number of blocks high value, instead of many, this changes the above 
scenario to the modem will only have a very small number of unverified 
blocks, while it will have a larger number of verified blocks, allowing it 
to exchange earlier without being cut off from the swarm. The flattened tree 
is cheaper to transfer, creates fewer rare blocks, is easier to secure, 
cheaper to verify, smaller to download, and in exchange you give up the 
ability to clog the CPU.

So to clarify my proposal in terms of creating something to work from, 
you'll probably notice that this is evolving each time I make mention of it, 
I truly don't have the time to solve every problem at once. The new .torrent 
file would include
announce
creation date
length
name
numPieces
Root 6-tuple
Hash of root complete block 0

Block 0 would be
{{0, size, (0,0), (0,0), numDirectChildren, hash(all children nodes 
6-tuples)}, list of original 6-tuple for chilren (e.g. {0, size, (0,0), 
(0,0), numDirectChildren, hash(all children nodes 6-tuples)})}
Inner nodes would maintain the same form but obviously the parent node and 
nodeId would change. The list of children is new, and is only there to 
reduce the likelihood of rare inner nodes.
Leaf nodes
{{k, size, parentId, myId, 0}, hash(data), data}

This gives a bulk sanity check for the child node in that the 6-tuple will 
already be known, and so a simple binary check can be made. Then checking 
the hash of the data. The biggest downside I see is that the 6-tuples are 
all transferred twice, but if we're working from the assumption that the 
claimed 2% growth from the 2-branching merkle tree is acceptable then the 
allowed flattened tree with it's much smaller overhead is doable. For those 
that really believe that a 2-branch Merkle tree is optimal for their 
situation, they are free to set numDirectChildren = 2 for all the nodes in 
their files.

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