[BitTorrent] Back to Merkle Hash Trees...
Olaf van der Spek
OvdSpek at LIACS.NL
Mon Feb 7 14:02:25 EST 2005
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?
> 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?
>>>Harder .... bad parts. Current process: lookup segment hash in O(1) time,
>>>compare hash O(m) time, total time O(n). Merkle process: step through
>>>to leaf O(log(n)) time, then compare hashes O(n) time, total time
>>Isn't that limited by network transfer rate instead of CPU time?
> As with any bottleneck it moves around as assumptions change. Assuming
> SHA-512, 2.1 GHz pentium 4, Windows XP, Crypto++ used for implementation,
> and assuming a 100baseT connection the situation changes substantially. The
> system can receive at 12.5Mbytes/second, but can only hash at 11.4 MB/s even
> the flat file would be unable to keep up. Admittedly this situation is not
> in the near future for most uses, but my systems spends most of their time
> at 100% computation load, the extra overhead required for a non-flat
> traversal would have an impact even if I was running on an 800 baud modem.
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