[BitTorrent] Back to Merkle Hash Trees...
Olaf van der Spek
OvdSpek at LIACS.NL
Sat Feb 5 05:53:45 EST 2005
Joseph Ashwood wrote:
> ----- Original Message -----
> From: "Olaf van der Spek" <OvdSpek at LIACS.NL>
> Subject: Re: [BitTorrent] Back to Merkle Hash Trees...
>>>On Fri, 04 Feb 2005 00:38:59 -0000, sh4dowmatter <mgp at ucla.edu> wrote:
>>>who still doesnt understand where the big advantage over a list
>>>of hashed blocks is, anyways
>>Tiny .torrent size, smaller verification granularity, compatibility with
>>other merkle tree hashes.
> And the associated disadvantages of not having those hashes immediately
> available. Harder to determine the bad parts of the file, higher overhead in
Who said anything about not having the hashes available when needed?
> computing hashes, longer download times (extra hashes need to be
> Now for those that don't believe the statements above, one at a time:
> 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?
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