Re: Back to Merkle Hash Trees...

----- Original Message ----- 
From: "Olaf van der Spek" <[email protected]>
Subject: Re: [BitTorrent] Back to Merkle Hash Trees...


>> On Fri, 04 Feb 2005 00:38:59 -0000, sh4dowmatter <[email protected]> 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
computing hashes, longer download times (extra hashes need to be
downloaded).

If you're building a filesystem then Merkle tress are useful in forming the
signed library, but otherwise rather useless.

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

Higher overhead...: Computing root hash using current method O(n) time.
Computing root hash for Merkle O(nlogn) time.

Longer download: Currently the overhead is known. In the case of detecting
bad segments, Merkle overhead will necesarily include downloading the entire
Merkle tree, in addition to the current overhead. Where detecting bad
segment is unnecessary the overhead remains the same.

There are additional problems in balancing the signed library tree in order
to achieve maximum speed and in not propogating the bad segments.

For maximum processing speed the tree needs to be properly balanced doing
this requires properly balancing across the hash. In the case os SHA-1 this
requires tuning in such a way that numHashes*512/160 is as close as possible
to an integer, while this is not immediately apparent as computationally
intensive you have to understand that it is actually an O(nlogn) problem,
and while not overly costly is not cheap.

Bed segment propogation is already a small problem as parts may be
downloaded and uploaded before verification. By using a Merkle tree you are
raising the computational overhead to perform verification, and in some
cases may be delaying the verification until the complete file is downloaded
(to compute the non-downloaded complete tree), creating a situation where
there is a high likelihood of large scale propogation of any bad data.

As I said earlier, only in a filesystem architecure are merkle trees of
substantial use. In the file system each file is hashed, then categories,
etc, forming what is called a signed library. This allows the library to be
updated in O(logn) time instead of O(n) at the cost that the initial
creation is O(nlogn) instead of O(n). During download it is important to
realize that flat hashes require O(downloads*n) time and Merkle trees will
require O(downloads*nlogn) time, as the downloads become the dominant factor
the advantage of flat hashes becomes ever greater. Only in the transfer of
live data, or data that is often updated (which would require updating the
torrent file) does the Merkle tree pose any advantage.

For those that are truly security conscious of security there are a great 
deal many other things that must be addressed to maintain the security that 
I have not even touched on, but suffice it to say that the original Merkle 
tree should not be considered secure.
                Joe


Trust Laboratories
Changing Software Development
http://www.trustlaboratories.com



 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/BitTorrent/

<*> To unsubscribe from this group, send an email to:
    [email protected]

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/