[BitTorrent] Back to Merkle Hash Trees...

Joseph Ashwood ashwood at msn.com
Mon Feb 7 18:56:05 EST 2005



----- Original Message ----- 
From: "Olaf van der Spek" <OvdSpek at LIACS.NL>
Subject: Re: [BitTorrent] Back to Merkle Hash Trees...


>
> Joseph Ashwood wrote:
>>>Who said anything about not having the hashes available when needed?
>>
>>
>> Unfortunately the lack of hashes available is a requirement for random
>> access downloading.
>
> Why? BT1 appears to do quite well, or is that not random order 
> downloading?

BT1 does not have random order for download of the hashes, those are in the 
torrent file and as such are downloaded first. In order to verify a given 
block all parent hashs have to be known, that creates a requirement that the 
parent hashes be downloaded first, this is directly counter to the random 
download paradigm that BT relies on in order to scale beyond seeds to the 
entire swarm.


> > If everyone downloads the hash tree first, the hash tree
>> becomes universally available, but the data may not be. In order to 
>> rectify
>> this the tree must be randomly accessed as well during the download. This
>> leads directly to a situation where subtrees may not be linked into the 
>> full
>> tree, and hence the hashes for verification are not available.
>
> Doesn't that 'may' depend on the way you exchange the hashes?

If the hashes are a part of the exchangable values, then the hash tree (or 
at least specific branchs) is necessary before a block can be verified. The 
systems with file portions, but no hash tree, cannot transfer known good 
blocks. My point in this is that the hash tree has to be downloaded first, 
and that this is completely counter to the random download that BT relies 
on.

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