[BitTorrent] Have maps (was Merkle, URLs, etc)

Joseph Ashwood 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 
32688 bytes.

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

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

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.
                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:
    BitTorrent-unsubscribe at yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/
 





More information about the BitTorrent mailing list