Re: Back to Merkle Hash Trees...

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

IMO, you're improvement is worth doing.  Speed and simplicity still
count, even if you have to compute a SHA1 for each internal node.

Olaf, your client is testing Merkle hash trees now?  If you can send me
a spec, I'll upgrade the client I'm playing around with (btslave), and
perhaps we can test them with each other.  I like the upgrade proposed
by shadowmatter.  Would it be hard to modify what you've done?

Thanks,
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/