Re: Back to Merkle Hash Trees...

----- Original Message ----- 
From: "Elliott Mitchell" <[email protected]>
Subject: Re: [BitTorrent] Back to Merkle Hash Trees...


>
> Yes. Hopefully I've shot down these concerns?
Not for me, because think Merkle tress are in general a bad idea for most 
purposes, but perhaps in general.

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

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

Of course the order of the tuples is irrelevant, and perhaps it would be 
helpful to move the most parsed information (the 3-tuple) to the front to 
ease parsing. The Segment # is only for indexing and request purposes, if 
the requests are reworked to be a nodeID from above then the Segment # can 
go away entirely.

This noticably increases the transferred data, by adding at leadt 20 bytes. 
Some may think this is trivial, I do not, but if Merkle trees are needed, at 
least do them securely.
                Joe


*The original library signing algorithm did in fact have this, although it 
was somewhat hidden. Because the books were assumed to be in alphabetical 
order, and classed based on subject again alphabetized, the tree was 
serializable. 



 
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/