Re: Merke Tree Structure (was: Have maps)

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

> I suggest that if we continue this thread that we move it to a new subject,
> we have distinctly left Have maps completely behind.

Done. :)
Whoever replies please cut the "(was:..." from the subject line. thx.

> NodeNumber was there for strict file serialization (can be safely dropped),
> while nodeID is an address (level, count) so

Okay. In my "binary tree world", only NodeNumber would be needed, but
we should discuss that when everybody agrees on the other stuff.

> but I don't think numChildren can be safely removed. Removing
> numChildren would make multifile torrents more difficult, and variably sized
> nodes impossible (for balancing).

ack

> As I have currently implemented it (wastes a lot of space), the head if 80
> bytes:
> 64-bit me.level
> 64-bit me.point
> 64-bit parent.level
> 64-bit parent.point
> 64-bit numChildren
> 64-bit nodeSize
> 256-bit SHA-256 hash of data

level = depth and point = "i am child number point of my parent"?

> Except for the leaf nodes the data is a concatenation of the heads of the
> children, the leaf fills the remaining area with file data. So for a firmer
> example the root node of the 4MB file I just encoded is (in hex):
> 00 00 00 00 00 00 00 00 (me.level)
> 00 00 00 00 00 00 00 00 (me.point)
> 00 00 00 00 00 00 00 00 (parent.level)
> 00 00 00 00 00 00 00 00 (parent.point)
> 00 00 00 00 00 00 00 1A (numChildren)
> 00 00 00 00 00 00 08 20 (nodeSize)
> 2C 88 89 9A 71 B5 EA 5E
> 99 71 28 F4 C0 DE F9 4F
> 6B 3A 82 13 72 D1 87 D9
> 41 3A 32 26 D0 27 C6 03 (hash of child heads)

Can you explain how a child can, using these headers, validate its parent?

Usually, a parent can validate its children, but to validate the parent,
you need its parent. This goes up until the root (which is the concept
many others and me proposed).

I understood your Merkle Pool idea in a way that the parent and child
can verify each other "somehow", "for now"; and looked in your tuples
for this. Now it looks like you just proposed that if the parent of
the leaf provides a hash that marks it as correct, you assume that
both are not lying.

In other words: Some malicious client could send bogus data and hashes
that support it without being detected for now. Later, everything would
blow up. In a flat tree, this would mean re-transfer of all leaf hash
nodes, as you cannot tell where the error is at. In an n-ary tree, this
would propably be detected earlier, as the client would try to build up
a complete tree while transfering data.

Now how propable is such an attack?
Lets say the swarm is seeding something someone else doesnt want distributed.
This could be "pirated" content or just a commercial competitor.
The slower (more data needs to be transfered) version would get all
anchestors and anchestors silblings, so that one corrupted piece is
detected directly. The client might decide that if he only gets corrupted
content from a peer, he block him completely.
In the faster (verify only one level above) version, the client might
get a bogus parent from the peer. He can evade this by getting the node
 from another client as the data, so he has a (#goodnodes/#totalnodes)
chance of getting a good parent.

In both versions, lots of wrong data will be transferred, but only in
the second one, "good" nodes might share bad data, making the problem
worse.

I personally favor the strict but slow idea.

Any comments?

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/