[BitTorrent] Have maps (was Merkle, URLs, etc)
ashwood at msn.com
Thu Mar 17 07:23:32 EST 2005
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" <kosta at fillibach.de>
Subject: Re: [BitTorrent] Have maps (was Merkle, URLs, etc)
> 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
> how its security drawbacks?
As I have currently implemented it (wastes a lot of space), the head if 80
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.
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