[BitTorrent] Back to Merkle Hash Trees...
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