Re: Have maps (was Merkle, URLs, etc)

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

----- Original Message ----- 
From: "Konstantin 'Kosta' Welke" <[email protected]>
Subject: Re: [BitTorrent] Have maps (was Merkle, URLs, etc)


[Joe's proposal]

> What is the difference between NodeNumber and NodeID?

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

> NodeSize should be
> implicit, NodeNumber, numChildren could be.

Theoretically it could be. I think I placed it there as a convenience in 
parsing a flattened (but not decoded) file back into a tree, otherwise a 
node header would be necessary, and that can get messy. NodeNumber can be 
dropped, 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). The more assumptions are pushed into the 
code the smaller the tree, but the more difficult a tree becomes to handle. 
In the current implementation it is not necessary to know the file length 
before parsing can begin, in some situations this is a decided advantage. 
But it is a trade-off, I went for my preference there with having everything 
as explicit as possible.

> by hash (head of children) you
> mean the hash of the 6-tuples of the child nodes? is ID somehow related to
> hash? I cant see how exactly...

Yes I meant the hash of the 6-tuples of the children. ID is only an 
addressing form for finding nodes arbitrarily. If a slight lack of 
serialization is acceptable the NodeID concept can be completely discarded, 
although this would leave finding the parent difficult unless a replacement 
ParentID were put in place (I'd suggest the hash from the parent 6-tuple).

> Could you describe this touple format a in a little more detail (i couldnt
> find a good description in your older emails either)? Could you also 
> describe
> how its security drawbacks?

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

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)

And I really don't feel like typing 2080 bytes of hex for the children 
heads, they are of the same format, each head is 80 bytes.

There is an enormous amount of wasted space in this; NodeIDs can be dropped 
(saves 32-bytes), numChildren and nodeSize can be reduced to either 16 or 
24-bits (saves 10-12 bytes), leaving a 36-byte head, this will increase the 
space efficiency further.

The trade-off with reducing the nodeSize and numChildren sizes is that node 
space efficiency decrease. With an 8-bit nodeSize the maximum internal node 
efficiency is 98.44%, and in general the maximum node space efficiency is 
(  floor(  (2^nodeSize)/headSize  )   * headSize  ) / (2^nodeSize) which may 
or may not be of interest.
                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/