Re: 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?

 > 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 
>>>tree
>>>to leaf O(log(n)) time, then compare hashes O(n) time, total time
>>>O(nlog(m)).
>>
>>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.

True, true.


 
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:
    [email protected]

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/