[BitTorrent] Back to Merkle Hash Trees...

Olaf van der Spek OvdSpek at LIACS.NL
Sat Feb 5 09:59:47 EST 2005

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

<*> 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 mailing list