Merke Tree Structure

----- Original Message ----- 
From: "Konstantin 'Kosta' Welke" <[email protected]>
Subject: Re: [BitTorrent] Merke Tree Structure (was: Have maps)


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

point = "I am node # point on this level"

>
>> 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?

Can't, the verification is purely top-down, the parent ID simply allows the 
child to find the parent (albeit undependably e.g. each tree will have a 
node (0,0)).

> 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.

The MerklePool concept was just a storage medium. Each node in the pool is 
self-verified, the root node is known externally. The pool allows for 
searches for the children. It is purely a convenience, but useful for 
searching.

> 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.

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.

> In other words: Some malicious client could send bogus data and hashes
> that support it without being detected for now.

Only if the nodes were unrequested. A big part of the process is only 
requesting nodes that can be verified (I'd suggest request by nodeHash), 
this is necessary with all Merkle implementations.

> In a flat tree, this would mean re-transfer of all leaf hash
> nodes, as you cannot tell where the error is at.

Actually you can tell exactly where the error is. From the root step down 
through each level (you have the information to check each internal node 
seperately) when a node does not match what it should, all the descendent 
nodes are in error.

> 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.

As the client should in any tree.

> 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?

I am absolutely in favor of only sharing data that has been traced to root. 
Unverified subtrees are acceptable for local storage, and in many cases even 
beneficial, but no node should distribute data that it has not traced to a 
root node.

There are ways of enforcing this, but the one that comes best to my mind 
requires a move from file/range transfers to node transfers. There are 
certainly arguments on each side, but it has little to do with tree 
structure.
                Joe 



 
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/