Re: Back to Merkle Hash Trees...

Justin Cormack wrote:
>>>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?
>>
>>
>>>Higher overhead...: Computing root hash using current method O(n) time.
>>>Computing root hash for Merkle O(nlogn) time.
>>
>>Isn't that limited by disk transfer rate instead of CPU time?
> 
> 
> sha1 (let alone sha256 - dont have an implementation lying around to test)
> is pretty CPU intensive.. 
> 
> ok my desktop can manage 130MB/s, though thats only the speed of a couple
> of disks. A VIA C3 I have lying around can only manage 10MB/s, much slower
> than its disk.
> 
> Merkle SHA256 is a significant amount more CPU time, its a question of
> whether it is worth it.

But the extra hashing required to calculate the merkle tree is tiny 
compared to the normal hashing. So I still consider this point not relevant.


 
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/