[BitTorrent] Back to Merkle Hash Trees...
ashwood at msn.com
Sat Feb 5 04:57:14 EST 2005
I'll reexplain it for those that have had a bit of time between their math
education and now.
----- Original Message -----
From: "John Hoffman" <theshadow at shambala.net>
Subject: Re: [BitTorrent] Back to Merkle Hash Trees...
>>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
>>Higher overhead...: Computing root hash using current method O(n) time.
>>Computing root hash for Merkle O(nlogn) time.
> Well... the O(n) overhead is a lot heavier than the O(n log n)
> overhead, so except on extremely large torrents (read >100G) you aren't
> going to see a significant increase.
Actually it is quite the opposite, the change becomes immediate. The O(n)
hashing will require processing n bytes, the O(nlogn) hashing will require
no less. Simple proof:
Assume: the number of bytes hashed depends on the input, if not all input is
hashed then the system collapses
Assume: hashes take O(n) time or greater, otherwise the hash does not depend
on all the input and assumption 1 is broken
Reality: Modern cryptographic hashes (e.g. SHA-1) are trivially more
expensive than O(n), but more so for smaller n
Assume: Generating a stream of hashes is needed regardless.
Assume: The straight hashing is actually equivalent to the Merkle tree in
the case where the log base is infinite.
Assume: Log(n) strictly increases as the log base decreases, for values of n
The assumptions are trivially correct, but not worth proving.
Since all functional Merkle trees cannot have an infinite log base, we have
a clear math situation where:
nlogn > n for all values of n > base of log
For clarity log base 2:
n O(n) O(nlogn)
2 2 2
4 4 8
Since the flat file hash is equivalent to a depth 2 Merkle tree (root level,
leaf level), the Merkle tree cannot have less overhead than the flat case,
where both are optimized to the same level.
So clearly your claim has two completely incorrect statements:
1) The Merkle tree is computationally cheaper. Wrong by proof 1
2) The Merkle tree overhead is lower than the flat. Wrong by proof 2.
While these difference may not be noticable in small files the difference is
very real, and will be noticable well before the claimed >100G.
> >Longer download: Currently the overhead is known. In the case of
>>bad segments, Merkle overhead will necesarily include downloading the
>>Merkle tree, in addition to the current overhead. Where detecting bad
>>segment is unnecessary the overhead remains the same.
> The idea is to both send opposing tree data, as requested, with chunks,
> and to cache the data. It does not require redownloading the entire
> tree in the case of an error, but merely the hashes received with a bad
> chunk, which would not be a large number (30 or less, max 600 bytes,
> probably much less).
I never claimed that the entire tree would need to be downloaded again, read
what I wrote, I wrote that the entire tree would have to be downloaded, by
proof #1 above the Merkle tree will NEVER be smaller than the flat hash, and
so it will take longer to download. The impact of this is open to
discussion, but the math does not lie.
>>There are additional problems in balancing the signed library tree in
>>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
>>requires tuning in such a way that numHashes*512/160 is as close as
>>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.
> It's not really necessary to balance the tree so perfectly. A
> breadth-first parse is quite adequate.
Actually due to the computational cost of verification of the tree the
balance of the tree becomes increasingly important as sizes rise. I will
agree that when a verification covers 2 bytes the difference is irrelevant,
but when there are a number of nodes in the tree, simply verifying the tree
can become very costly. To verify this consider a Btree search, the Btree
search is identical to the full verification of a node. In a balanced Btree
the search is O(logn) time, in an unbalanced tree the search tends towards
O(n) time, anyone can do the math on those and see that the balance becomes
very important as the size increases. Again when you are verifying a 2 bytes
file the difference is negligible, but as the tree size grows the
verification will become much more costly as the tree becomes unbalanced.
>>Bed segment propogation is already a small problem as parts may be
>>downloaded and uploaded before verification. By using a Merkle tree you
>>raising the computational overhead to perform verification, and in some
>>cases may be delaying the verification until the complete file is
>>(to compute the non-downloaded complete tree), creating a situation where
>>there is a high likelihood of large scale propogation of any bad data.
> No, downloaded chunks will be verified as they come in.
Then explain why bad segments are received when the transmission medium
remains unchanged. There will be downloaded chunks that are not verified,
and they will be shipped around regardless of how many time we repeat to
ourselves that this won't happen. If each segment was verified before it was
sent on, there would be no need to verify the segment on receipt, simply
verify the communication medium. Instead the segments must be verified
before they can be trusted. Incidently, you will find this listed as proof
I stand behind what I said earlier, the Merkle tree/library signing
algorithm is not well suited to the purpose of BitTorrent, it is only
suitable when a filesystem is put in place and attempting to wedge it into
the BitTorrent solution is simply not necessary.
I didn't discuss it last time because I assumed it would be obvious, since
it appears there are a number of people on here without suitable math
educations, a far better solution would be a descendancy of hashes, for
RootHash = hash(data, hash( for all Level1 hash))
Level1 hash [i]= hash(datasegment[i], hash(for all Level2 hash))
LevelM hash[i] = hash(datasegment[i], hash(for all LevelM+1 hash))
LevelK hash[i] = hash(datasegment[i], 0000...0000)
(for known K) where for each level the datasegment length is decreased by a
given factor. This creates an O(1) lookup for each datasegment hash of any
of the established sizes. At the cost that the initial hash must be
performed K times resulting in a creation time of O(Kn), as opposed to the
Merkle trees O(nlogn).
The other downside is that it still maintains the size of a Merkle tree,
something which is simply unnecessary for BitTorrent's uses.
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