[BitTorrent] Have maps (was Merkle, URLs, etc)
ashwood at msn.com
Thu Mar 10 21:02:28 EST 2005
----- Original Message -----
From: "Elliott Mitchell" <ehem at m5p.com>
Subject: Re: [BitTorrent] Have maps (was Merkle, URLs, etc)
> I suggest you define what you mean by "in node verification". I took it
> to mean that when you send a data block, you also send sufficient data to
> verify it in lieu of other data (other than the root hash).
Ok, that's where we have the disconnect. I was referring to the node design
I had posted previously (the 6-tuple head and data). This allows every node
to be verified as internally consistent, and the remaining verification is a
binary compare between the expected and received head. I am still depending
on clients being smart enough to collect the parents itself, in fact I have
previously suggested that all transfers be done according to this tree (e.g.
request a hash, recieve a node). Working from the known root hash, this will
give the information about the next level down, requesting from the first
children will give information about the next level, etc.
[snip because communication was not clear]
> This is more a commentary on transfering hashes /with/ the pieces, than
> on binary versus flat.
That is true, and it began with, as the subject says, have maps.
Transferring fewer hashes is better, but creates more computation overhead.
Absolute worst case (that I have not seen anybody propose) only the root
hash is transferred, along with a branching rate (or implicitly 2), from
there the entire file is downloaded, the tree is computed, and root is
checked. This creates hashSize overhead , but costs in both transfer to
verify a single piece and in computation time to verify a piece. Best case
for computations the current format is used. We just seem to be arguing over
where in between everything should be.
>> I will grant that there are ways to transfer the hash once instead of the
>> twice that I have proposed, but hose methods also require downloading the
>> siblings before verification of a node.
Not necessarily. If the child node head is exclusively in the parent, then
the head is transferred only once (I had not previously proposed this and it
looks sufficiently confusing). That is the torrent includes the root head.
The root node has no head only the child heads, etc. This will transfer each
head once, but nodes cannot be verified without knowing the parent.
> 4KB is the smallest size anyone has seriously proposed. 16KB or 32KB is
> more likely when things happen though. I don't have much to respond to
> here as you haven't given me a specific number.
Ok at 32KB node size. N-ary trees with all 64-bit integers, with the design
I proposed before will create a 408-ary tree, and the leafs will each hold
Level 1 = 1 node = 32688 bytes
Level 2 = 408 nodes = 12.7 MB
Level 3 = 166464 node = 5.2 GB
Level 4 = 67917312 nodes = 2067.6 GB
Verification for a leaf node in a 1GB file will take 3 hashes, each of
around the point where the hash finalization and the rest of the hash are
about equal, so for the sake of leniency let's mulitply it by 3 for a solid
1GB at 32KB = 15 levels
15 finalizations, the insertion doesn't make any real difference.
This as estimated 9 time units, versus 15 times units to verify the first
piece. Assuming verification of nodes is cached verifying the second piece
will cost on average for the n-ary tree 2 verifications (root is now
verified) for an estimated finalization cost metric of 6, and for the binary
on average 14.5 finalizations, cost difference is now above 2. I don't feel
like doing the math beyond that because it starts to get complicated. Doing
some rough estimations in my head the n-ary tree will stay at 2
verifications for a while, but will decrease to an average of one, long
before the binary tree does. The last few pieces the average cost will be
The grossest estimate is the 3x penalty for the n-ary nodes. I'll run some
tests later today to determine the penalty at various input sizes.
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