# [BitTorrent] Back to Merkle Hash Trees...

Bill Cox bill at viasic.com
Wed Feb 9 11:16:32 EST 2005

```On Fri, 2005-02-04 at 00:38 +0000, sh4dowmatter wrote:
>
> 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.

Hey, I got a post through!

Well, getting back to sh4dowmatter's original post, I think it's a good
idea.  It sounds like it needs a bit more explaining, so here's some
additional notes I've sent to Olaf on array based complete trees (the
last level can be incomplete).

Here's an example tree for a 9 piece torrent.  The numbers are the node
index for the nodes.  The nodes with dashes around them are leaves, and
represent pieces.

1
|-----------------|
2                 3
|-------|         |---------|
4       5         6         7
|---|    |---|     |---|     |---|
8  -9- -10- -11- -12- -13- -14- -15-
|---|
-16- -17-

The root node has index 1.  It's children are 2 and 3.  In general, your
left child has index that's twice yours, and your right child is the
next node after that.

So, the first pieces's node index is 9, and they go up from there to 17.

To find your sibling, just xor your node index with 1.  For example,
9's sibling is 8.

In this example, the first piece (node 9) has an authentication path of
8-5-3.  The last piece (node 17) has 16-9-5-3.  The last piece listed to
the right (node 15), has authentication path 14-6-2.

So, here's some simple formulas for how to compute things, if there are
N pieces:

Root node index: 1 (not 0)
First piece node index: N
Last piece node index: (N << 1) - 1
Index of piece n (with 0 as the first piece): N + n
Node n's sibling: n ^ 1
Node n's parent: n >> 1
Node n's left child: n << 1
Node n's right child: (n << 1) + 1

example, to perform a bottom-up recursion where we call function "func"
for on each node, but only after processing children, just use:

for(n = lastNodeIndex; n > 0; n--) {
func(n);
}

Top down recursion is just:

for(n = 1; n <= lastNodeIndex; n++) {
func(n);
}

The code winds up being fast and small.  It's also easy, once you get
use to it.

Bill

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

```