[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
> downloaded).
> 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
> 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?

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