[BitTorrent] Back to Merkle Hash Trees...
bill at viasic.com
Fri Feb 4 07:06:04 EST 2005
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?
Yahoo! Groups Links
<*> To visit your group on the web, go to:
<*> To unsubscribe from this group, send an email to:
BitTorrent-unsubscribe at yahoogroups.com
<*> Your use of Yahoo! Groups is subject to:
More information about the BitTorrent