[BitTorrent] Back to Merkle Hash Trees...

sh4dowmatter mgp at ucla.edu
Thu Feb 3 19:38:59 EST 2005

Not to beat a dead horse, but...

So I was re-reading the description of Merkle Hash Trees over at the
THEX specification (see
http://www.open-content.net/specs/draft-jchapweske-thex-02.html), and
I was thinking of implementing an efficient, array-based version in C.

The current spec defines a five-leaf tree as:

                        /        \
                       /          \
                H=IH(F+G)          E
                /       \           \
               /         \           \
        F=IH(A+B)       G=IH(C+D)     E
        /     \           /     \      \
       /       \         /       \      \
  A=LH(S1)  B=LH(S2) C=LH(S3)  D=LH(S4) E=LH(S5)

That is, starting with the leaf hashes as the bottom level, I go
through and hash in pairs, appending each hash to a new list; if at
the end of the level I find a leaf remaining, I simply append it to
the list. I then use the list as my next level up, and repeat the
process until I generate a list with only one hash -- the root.

But say I define it as a full binary tree instead; that is,

                           /           \  
                          /             \  
                  F=IH(F+C)             G=IH(D+E)
                 /         \            /       \
                /           \          /         \
        H=IH(A+B)      C=LH(S3)     D=LH(S4)   E=LH(S5)
       /        \
      /          \
   A=LH(S1)   B=LH(S2)

There are still only five leaf hashes, and four internal hashes
(including root), but I get the power of being able to use array-based
indexing in the tree (so indexing with ROOT at 0, H at 1, G at 2,
etc). That is, I get lchild[i] = 2 * i + 1 and rchild[i] = 2 * i + 2.
Also, the size of the underlying array has a simple closed form -- the
number of 'hash elements' to allocate is simply 2 * num_leaves - 1.
Finally, given If I'm doing an array-based implementation, then I know
that the first internal node is at element array_size - num_leaves -
1; assigning i this index downto 0, I can compute each internal hash
as simply hash(lchild[i] + rchild[i]). I not afforded this convenience
so easily by using the format shown in THEX.

This must all seem utterly trivial, so I just want wondering if the
powers that be, whether it was originally Merkle or someone else, said
that "all Merkle trees shall be formed breadth-first, and not as a
full binary tree." If I try pursue this idea above, can I call it a
Merkle hash tree? 


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