sh4dowmatter

2005-02-04 00:38:59 UTC

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:

ROOT=IH(H+E)

/ \

/ \

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,

ROOT=IH(G+H)

/ \

/ \

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?

Thanks,

shadowmatter

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/

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:

ROOT=IH(H+E)

/ \

/ \

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,

ROOT=IH(G+H)

/ \

/ \

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?

Thanks,

shadowmatter

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/