[BitTorrent] Back to Merkle Hash Trees...

Justin Cormack justin at street-vision.com
Sat Feb 5 09:22:06 EST 2005

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


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