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

From [email protected]  Wed Feb  9 18:23:23 2005
Return-Path: <[email protected]>
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 <[email protected]>; Wed, 9 Feb 2005 18:23:22 GMT
Resent-Date: Wed, 9 Feb 2005 18:23:22 GMT
Resent-Message-Id: <[email protected]>
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 [email protected]; 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 [email protected]; 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 [email protected]; 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 [email protected]; Wed, 09 Feb 2005 13:30:45 -0500
From: Bill Cox <[email protected]>
To: "[email protected]" <[email protected]>
In-Reply-To: <[email protected]>
References: <[email protected]>
Content-Type: text/plain
Message-Id: <1107965792.4005.14.camel@swordfish>
Mime-Version: 1.0
Subject: Here's a post I would like forwarded... thanks!
Resent-From: Bill Cox <[email protected]>
Resent-To: [email protected]
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

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

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:
    [email protected]

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