[BitTorrent] Back to Merkle Hash Trees...

Elliott Mitchell ehem at m5p.com
Sun Feb 6 02:55:42 EST 2005


>From: Joseph Ashwood <ashwood at msn.com>
> 
> ----- Original Message ----- 
> From: "Elliott Mitchell" <ehem at m5p.com>
> 
> > One you might think about helping me murder is the "THEX" design various
> > folks have been advocating. THEX distinguishes leaves from internal nodes
> > by appending a byte depending on whether it is leaf or payload; *that*
> > is bogus!  (kills alignment, makes testing expensive)
> >
> > http://www.open-content.net/specs/draft-jchapweske-thex-02.html
> 
> Actually I think that if Merkle trees are going to happen THEX is a tiny 
> baby step in the correct direction, although it lacks the serializability 

Hopefully my previous message sufficiently explained why I consider THEX
to be a bad idea. Those reasons have nothing to do with lack of sufficent
data in the nodes. (incidentally, the above should be "prefixing" not
"appending")

> that is necessary to maintain security. For serializability it is necessary 
> to know a number of things about each node: nodeID = (level, horizontal 
> location on level)
> Segment #
> Size
> Hash
> Parent by id
> nodeID
> number of direct children

Some of these need to be known to verify a node, but they needn't be
verified by the root hash, because if they're wrong they'll fail to
verify.

> All of these need to be hashed by the parent so instead of having a Merkle 
> tree as
> Root =  Hash(A|B)
> A = hash(first part)
> B = hash(second part)
> 
> you have
> Root = {1,sizeof(A|B), hash(A|B), (0,0), (1, 1), 2}
> A = {2,sizeof(first part), hash(first part), (1,1),(2,1), 0}
> B = {3,sizeof(second part), hash(second part), (1,1), (2, 2), 0}
> 
> Assuming a secure hash this will allow complete serialization of the data, 
> making it necessary to break the underlying hash in order to fake a tree 
> (original proposal Merkle tree did not have this property). This will also 
> take care of your alignment issues, the {parent, level, location, children} 
> 3-tuple can be constructed to take 128 bits, and sizeof(...) can be 
> constructed in 32-bits. This result is completely serializable and hence is 
> secure.*

If there is only one way to construct the tree, the above is implicit in
the structure of the tree. If it is tampered with the hashes won't
verify.

Given hashes for a pair of siblings, you can compute the parent hash. So,
if you have the hashes for all direct children of the root you can verify
them as a group. Once these are verified you can confirm all of the next
level. This continues down to the leaves.
If the leaves are marked similar to how THEX suggests, then you cannot
pass off a leaf as an internal node nor can you pass an internal node off
as a leaf without breaking the hash.

Given this, you can confirm the complete set of data against the root
hash with no additional data. Given a proper set of data and internal
nodes you can verify all of them against the root.


>From: "Joseph Ashwood" <ashwood at msn.com>
> I'll reexplain it for those that have had a bit of time between their math 
> education and now.

Your math is fine. The problem is you're making incorrect assumptions.

> ----- Original Message ----- 
> From: "John Hoffman" <theshadow at shambala.net>
> 
> Second proof:
> 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.

Incorrect. For n data items, a tree has O(n) nodes. Lookup in an ideal
tree is O(log n), which leads to sorting data items requiring O(n log n)
work.

The tree still only needs O(n) nodes for n data. At this time I'll let
you work through the proof.

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

Proof #1 showed that O(n log n) was larger than O(n). You failed to show
that the tree was O(n log n) size, so with John I must dissent with your
point.

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

You've severely wounded the Merkle implementation that most folks have
been tossing around (incremental verification), but you haven't shot down
Merkle.

In order to verify a block of data only knowing the root, you need the
data plus O(log n) hashes and O(log n) work to verify them (all the
siblings up the tree). This then equates to O(m log n) overhead in both
data transfer and work for transfering m blocks of an n block file.


This is not the only possible handling of Merkle though. If blocks of
tree nodes are handled similarly to any other data blocks, you only
transfer the tree nodes once and only verify them once. At which point
the work and data overhead becomes O(n), where n is the size of the file.
The overhead will be slightly higher if you only do a partial transfer.

> >>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.
> >
> > 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 
> by contradiction.

Verification on receipt implies verification before sending on. There
must be something I'm missing here.

> 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 

My, my, we're really throwing down the gauntlet here. Watch out,
credential war winners are often not the initiator. Though I will admit
I've been repeatedly tempted to start one here.

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

Interesting construction. I must suggest that this is very nearly
equivalent to a Merkle tree in every way. I note that it looks to be much
more expensive to compute though. I also not see it being easier to verify
either incrementally nor as a whole.

To verify a block, you appear to need the block, then you need the hashes
of all sibling blocks and the parent block for the next level up. You
then appear to need the same for all higher levels. You're likely to
transfer those and they appear much larger than Merkle's.


-- 
(\___(\___(\______          --=> 8-) EHM <=--          ______/)___/)___/)
 \   (    |         EHeM at gremlin.m5p.com PGP 8881EF59         |    )   /
  \_  \   |  _____  -O #include <stddisclaimer.h> O-   _____  |   /  _/
    \___\_|_/82 04 A1 3C C7 B1 37 2A*E3 6E 84 DA 97 4C 40 E6\_|_/___/




 
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:
    BitTorrent-unsubscribe at yahoogroups.com

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





More information about the BitTorrent mailing list