Here's a post I would like forwarded... thanks! (fwd)

[Justin Cormack]

Return-Path: <SRS0=Q2BZBw=QX=viasic.com=***@yourhostingaccount.com>
Received: from out-mail03.yourhostingaccount.com (mailrelay4.yourhostingaccount.com [38.113.1.63])
by tench.street-vision.com (8.11.6/8.11.6) with ESMTP id j19INM404981
for <***@street-vision.com>; Wed, 9 Feb 2005 18:23:22 GMT
Resent-Date: Wed, 9 Feb 2005 18:23:22 GMT
Resent-Message-Id: <***@tench.street-vision.com>
Received: from scan05.yourhostingaccount.com ([10.1.1.235] helo=scan05.yourhostingaccount.com)
by mail03.yourhostingaccount.com with esmtp (Exim)
id 1Cywbv-0005cE-Jp
for ***@street-vision.com; Wed, 09 Feb 2005 13:30:47 -0500
Received: from mail01.yourhostingaccount.com ([10.1.1.72] ident=exim)
by scan05.yourhostingaccount.com with spamscanlookuphost (Exim)
id 1Cywbv-00016P-Sf
for ***@street-vision.com; Wed, 09 Feb 2005 13:30:47 -0500
Received: from mail01.yourhostingaccount.com ([10.1.1.72] helo=inc-mail01.yourhostingaccount.com)
by scan05.yourhostingaccount.com with esmtp (Exim)
id 1Cywbu-000169-CV
for ***@street-vision.com; Wed, 09 Feb 2005 13:30:46 -0500
Received: from 66-162-193-13.gen.twtelecom.net ([66.162.193.13] helo=192.168.1.104)
by mail01.yourhostingaccount.com with esmtpsa (TLSv1:RC4-MD5:128)
(Exim)
id 1Cywbt-0007nO-1q
for ***@street-vision.com; Wed, 09 Feb 2005 13:30:45 -0500
From: Bill Cox <***@viasic.com>
To: "***@yahoogroups.com" <***@yahoogroups.com>
In-Reply-To: <ctug73+***@eGroups.com>
References: <ctug73+***@eGroups.com>
Content-Type: text/plain
Message-Id: <***@swordfish>
Mime-Version: 1.0
Subject: Here's a post I would like forwarded... thanks!
Resent-From: Bill Cox <***@viasic.com>
Resent-To: ***@street-vision.com
Organization: ViASIC
Date: Wed, 09 Feb 2005 13:30:39 -0500
X-Mailer: Evolution 2.0.2 (2.0.2-3)
Content-Transfer-Encoding: 7bit

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

There are other cool properties that shadowmatter talked about. For
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





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-***@yahoogroups.com

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

[Justin Cormack]

Post by Justin Cormack

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-

Yes I would prefer a dense to a sparse tree.

This isnt the only way to achieve it of course, you can virtually pad
the content with zeros until it is a power of 2 in size, you know the hash
of all zeros so you dont compute it, then all rows are the same. This takes
up a little more space but is even more regular. There are probably other
solutions too.

j



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-***@yahoogroups.com

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