Re: Merke Tree Structure

On Thu, 17 Mar 2005 19:14:59 -0800, Joseph Ashwood <[email protected]> wrote:
> From: "Konstantin 'Kosta' Welke" <[email protected]>

Damn, I almost thought I got what you were saying. Seems like I got
it wrong. Basically, what I am trying to grasp is what you meant by

|> I think that the cost is depth*N. How do you check a node without knowing
|> its silblings?
|
|By having the sibling heads embedded in the parent. That makes it so the the
|download of the siblings is not necessary for verification. The algorithm is
|instead:
|
|Verify parent hash integrity
|Verify child hash integrity
|Verify that child head matches parent-child head
|
|The first two require hash finalizations, the last is a binary compare.

At some point I lost it and though with your method, you could also
leave out all ancestors.

Now lets recapture: each node not only has the hash of its children, but
also of his silblings. This doubles node payload, but that might be worth
it. Now, to verify one node, you need to download all its ancestors but no
silblings. The ancestor adds the "node to verify" hash to the hash of its
silblings and compares that to its hash of children.

Hmmm, should work. Did I finally get your proposal right?

In that case, binary trees are, of course, the worst way and a flat tree
would be optimal...

> The root node is assumed trusted, this is a necessary assumption. Beyond the
> root each node is considered validated if and only if the node's parent can
> computationally vouch for it.

Ok. Sounds much better than what I tought you might propose :)

Kosta


 
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/