[BitTorrent] addressing (was Merkle, URLs, etc)

Justin Cormack justin at street-vision.com
Fri Mar 4 07:27:42 EST 2005


> I had always assumed that there are two ways to properly address a node, by
> the {file, nodeID (the {tree level, nodeOnLevel} pair)} and by the hash.
> Alternately in order to expand the maximum size to infinite the nodes can be
> addressed as {parentHash, childNumber}, actually this will only create an
> addressable space of sqrt(output space of hash) nodes (by birthday paradox),
> and so with SHA-256 the limit would be 2^128 nodes, but I don't consider
> 2^128 bytes to be too small by any measure, but if the gain of a factor of

(file, nodeID) pairs are ok but assume a standard node ID ordering (which
imposes severe restrictions on how you implement) and the file will be
a hash already so its not very compact. (parenthash, child) causes problems
when adding a file you have: you dont know the parent hashes at the point
where you have hashed the block. I think only hash alone makes sense.

> nodeSize is important this can be considered. The advantage of addressing
> purely based on the hash is simple, multiple torrents can be created that
> share subtrees, or more plainly a multi-file torrent and a series of
> singe-file torrents have the majority of the same nodes, assuming we are
> willing to accept variable length nodes in the middle of the tree, and have
> multiple nodes that claim to be root internally (multi-file torrent root +
> for_each(file, file root)). Additionally, multi-torrent connections become
> reasonable, especially when used with the MerklePool concept below.

Yes it looks quite nice. Its not even clear to me that there needs to be
such a thing as root (just nodes you dont yet have a parent for, its not
a special concept).

> Placing a piece of the tree in the open is difficult, the only thing that
> can be dependably done (without completely monotonic serialization) is to
> place the node in a pool of data. In a theoretical, but not practical sense
> this can be used to build a pool of peers with data, even though they may
> have no idea what to do with it except share. Realistically the usefulness
> of this is that peer1 can feed peer2 pieces of the file that peer1 knows
> peer2 will need (verified by descendancy from the internal/root node that
> peer2 requested). This descendancy trait allows SIMD pipelining, that is,
> one request results in multiple responses at the discretion of the serving
> peer.

Can you explain this a bit more, sorry.



 
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