Joseph Ashwood
2005-03-04 00:27:30 UTC
I apologize for my aparent falling off the earth act being an entrepreneur I
work when I have to, and I can only dedicate some free time to this.
Speed ratings for hashes. Wei Dai maintains benchmarks for all the
operations that Crypto++ supports available via
http://www.eskimo.com/~weidai/benchmarks.html . These benchmarks are:
32-bit machine
SHA-1 68 MB/sec
SHA-256 44 MB/sec
SHA-512 11 MB/sec
64-bit machine
SHA-1 100 MB/sec
SHA-256 58 MB/sec
SHA-512 93 MB/sec
While this clearly demonstrates the linear effect of moving to the larger
hashes, but in the current situation there is actually a second linear
problem, as the hash size grows the size of the data to be hashed at the
next level grows, leading to slow but exponential growth. The security
benefits though are more substantial and with SHA-1 broken there is plenty
of reason to move up.
URL formatting: It seems to me that for this it would be necessary for the
URL to include at the very least a tracker, and a root hash or filename.
Beyond that a tracker could supply the extra information. However this
potentially makes poor use of the available room in a URL, and as such the
URL should include a filesize, blocksize, and branching rate for the tree.
Merkle Trees: For verification of my suggestion I took some time and
implemented my proposed format (although I am not ready to call it finished
it does work). In the current implementation it will scale to 2^128 bytes of
original file size, but that should probably be shrunk some to save
overhead. I should say that it takes a huge amount of time build the tree
from a file, as I type I'm 29 minutes into processing a 180 MB file at 4kb
pieces ~ 95% done, and it occupies huge amounts of RAM, the test will occupy
about 4 times the storage space, but has 2 copies of the original file along
with the tree in memory at one point.
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
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.
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.
Binary Merkle Trees: Are heavily flawed, and the only suggestion made to fix
it was to send the grandchildren as well, which completely defeats the point
of the child nodes, making the child nodes pure overhead, they serve no
purpose except to enlarge the tranfer and raise the CPU time.
MerklePool: It occured to me during the implementation that in many ways the
most efficient way to implement the storage of the Merkle encoded files
(including the partials) is to store them in one central pool structure,
with search mechanisms used to find nodes by hash, this allows rare blocks
to be distributed widely, and for blocks to be multicast among systems that
should be interested at a later date.
Have maps: Actually with the MerkleTree since it is known that the root must
be retrieved first (at least be designation), there can be a child Have Map
associated with each request, that is specifically that when serving up an
internal node a bitmap of the immediate children is supplied as well. This
map will generally be only a few bytes and will be on the order of 0.2% of
the overall transfers. Also moving the requests for these maps to immediate
descendants of a node (or nodelist to reduce overhead) will have the same
effect.
This works because sending the client a list of haves for nodes they know
nothing about is pointless. The downside is that all requests are now based
on node instead of file location, something that can be troublesome.
Tracker to Tracker discussion: By doing this we're starting to approach what
Bram has referred to as a "gossip" network, as such a certain degree of
dependable, verifiable information has to be included. This is currently
done by only communicating it with trusted trackers. Later diversifying this
to include a cloud of trackers handling all the clients, this gets a bit
chaotic.
Instead what I would like to see is tracker redundancy. So where it is used
for clustering, this would still be the case, but all the peers would by
default connect to tracker1, if tracker1 is unavailable tracker2, etc. The
benefit of this keeping all the immediately used data on one system, so the
sync signals are minimal. It is only once the swarm reaches the size where a
single tracker cannot handle the load that distribution needs to take place.
With this size load, make a decision based on the swarm size, if the problem
is that the current tracker is overloaded, make a different tracker
tracker1. If the problem is the swarm itself it too big, split the swarm in
half and there is no reason to maintain a perfect list because the only
collisions will happen is trackerA goes down and all the clients default to
trackerB. The bulk of the information flow will be from trackerA to peers
during connection that the new default tracker (for the peer not
neccessarily for the whole swarm) is now trackerB. This load balancing while
rather primitive reduces the backend load on the trackers. This design is
based in large part of the experiences I have gleaned from others as well as
myself that dictate that a single BitTorrent tracker generally maxes out
around 90,000 peers, but this max-out is due to the lookups for the
peer-list, so the first bottleneck is actually the peer database, not the
other bandwidths. By clustering the trackers you will only bring down more
trackers at once in these lookups, but by splitting the peer database it
scales linearly (potentially super-linearly if the split is super-smart).
End-game overhead: I can see little possibility of improving this with a
purely random acquisition strategy. Moving to a method that is not
completely random does have advantages. So for example choosing rare pieces
first, and taking recommendations. So peers can recommend to each other an
order to grab descendants. This should be out of the main pipe and optional
both for send and recieve, but where implemented I can see no benefit to
suggesting badly to another peer due to the short lived preferencing in
BitTorrent. The result of this is that k peers will effectively team up to
get the file, and partially depend on between themselves transfers to finish
the end game.
This moves the end game problem but does not eliminate it. It reduces the
likelihood of not having a piece among team members, but the lack of benefit
actually drops off during end-game where tit-for-tat is no longer a concern.
This could also be implemented as a BEG command, that is the BEGgar is
asking for help in acquiring the piece listed, the BEGgee has the option of
helping in the search. It is also important that BEG misuse be detected, so
for example if badPeer uses BEG exclusively as a way of greedily getting
pieces, this can create substantial overhead for the BEGgees as they attempt
to track who has BEGged what, this is DOS detection. Used sparingly it can
be used to reduce the end-game overhead as BEG signals that a piece is rare
and should be acquired as quickly as possible, thus making it common.
THEX: The only time thex is a good thing is when you have a speech
impediment. THEX as a design lacks security, fails to make anything
resembling proper use of the available space (7/8 of the overhead bits are
wasted immediately), scales poorly and again the only suggestion to improve
it is to send the grandchildren as well which makes the children pure
overhead, having no redeeming value what so ever. THEX is wasteful,
pointless and insecure for BitTorrent..
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-***@yahoogroups.com
<*> Your use of Yahoo! Groups is subject to:
http://docs.yahoo.com/info/terms/
work when I have to, and I can only dedicate some free time to this.
Speed ratings for hashes. Wei Dai maintains benchmarks for all the
operations that Crypto++ supports available via
http://www.eskimo.com/~weidai/benchmarks.html . These benchmarks are:
32-bit machine
SHA-1 68 MB/sec
SHA-256 44 MB/sec
SHA-512 11 MB/sec
64-bit machine
SHA-1 100 MB/sec
SHA-256 58 MB/sec
SHA-512 93 MB/sec
While this clearly demonstrates the linear effect of moving to the larger
hashes, but in the current situation there is actually a second linear
problem, as the hash size grows the size of the data to be hashed at the
next level grows, leading to slow but exponential growth. The security
benefits though are more substantial and with SHA-1 broken there is plenty
of reason to move up.
URL formatting: It seems to me that for this it would be necessary for the
URL to include at the very least a tracker, and a root hash or filename.
Beyond that a tracker could supply the extra information. However this
potentially makes poor use of the available room in a URL, and as such the
URL should include a filesize, blocksize, and branching rate for the tree.
Merkle Trees: For verification of my suggestion I took some time and
implemented my proposed format (although I am not ready to call it finished
it does work). In the current implementation it will scale to 2^128 bytes of
original file size, but that should probably be shrunk some to save
overhead. I should say that it takes a huge amount of time build the tree
from a file, as I type I'm 29 minutes into processing a 180 MB file at 4kb
pieces ~ 95% done, and it occupies huge amounts of RAM, the test will occupy
about 4 times the storage space, but has 2 copies of the original file along
with the tree in memory at one point.
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
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.
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.
Binary Merkle Trees: Are heavily flawed, and the only suggestion made to fix
it was to send the grandchildren as well, which completely defeats the point
of the child nodes, making the child nodes pure overhead, they serve no
purpose except to enlarge the tranfer and raise the CPU time.
MerklePool: It occured to me during the implementation that in many ways the
most efficient way to implement the storage of the Merkle encoded files
(including the partials) is to store them in one central pool structure,
with search mechanisms used to find nodes by hash, this allows rare blocks
to be distributed widely, and for blocks to be multicast among systems that
should be interested at a later date.
Have maps: Actually with the MerkleTree since it is known that the root must
be retrieved first (at least be designation), there can be a child Have Map
associated with each request, that is specifically that when serving up an
internal node a bitmap of the immediate children is supplied as well. This
map will generally be only a few bytes and will be on the order of 0.2% of
the overall transfers. Also moving the requests for these maps to immediate
descendants of a node (or nodelist to reduce overhead) will have the same
effect.
This works because sending the client a list of haves for nodes they know
nothing about is pointless. The downside is that all requests are now based
on node instead of file location, something that can be troublesome.
Tracker to Tracker discussion: By doing this we're starting to approach what
Bram has referred to as a "gossip" network, as such a certain degree of
dependable, verifiable information has to be included. This is currently
done by only communicating it with trusted trackers. Later diversifying this
to include a cloud of trackers handling all the clients, this gets a bit
chaotic.
Instead what I would like to see is tracker redundancy. So where it is used
for clustering, this would still be the case, but all the peers would by
default connect to tracker1, if tracker1 is unavailable tracker2, etc. The
benefit of this keeping all the immediately used data on one system, so the
sync signals are minimal. It is only once the swarm reaches the size where a
single tracker cannot handle the load that distribution needs to take place.
With this size load, make a decision based on the swarm size, if the problem
is that the current tracker is overloaded, make a different tracker
tracker1. If the problem is the swarm itself it too big, split the swarm in
half and there is no reason to maintain a perfect list because the only
collisions will happen is trackerA goes down and all the clients default to
trackerB. The bulk of the information flow will be from trackerA to peers
during connection that the new default tracker (for the peer not
neccessarily for the whole swarm) is now trackerB. This load balancing while
rather primitive reduces the backend load on the trackers. This design is
based in large part of the experiences I have gleaned from others as well as
myself that dictate that a single BitTorrent tracker generally maxes out
around 90,000 peers, but this max-out is due to the lookups for the
peer-list, so the first bottleneck is actually the peer database, not the
other bandwidths. By clustering the trackers you will only bring down more
trackers at once in these lookups, but by splitting the peer database it
scales linearly (potentially super-linearly if the split is super-smart).
End-game overhead: I can see little possibility of improving this with a
purely random acquisition strategy. Moving to a method that is not
completely random does have advantages. So for example choosing rare pieces
first, and taking recommendations. So peers can recommend to each other an
order to grab descendants. This should be out of the main pipe and optional
both for send and recieve, but where implemented I can see no benefit to
suggesting badly to another peer due to the short lived preferencing in
BitTorrent. The result of this is that k peers will effectively team up to
get the file, and partially depend on between themselves transfers to finish
the end game.
This moves the end game problem but does not eliminate it. It reduces the
likelihood of not having a piece among team members, but the lack of benefit
actually drops off during end-game where tit-for-tat is no longer a concern.
This could also be implemented as a BEG command, that is the BEGgar is
asking for help in acquiring the piece listed, the BEGgee has the option of
helping in the search. It is also important that BEG misuse be detected, so
for example if badPeer uses BEG exclusively as a way of greedily getting
pieces, this can create substantial overhead for the BEGgees as they attempt
to track who has BEGged what, this is DOS detection. Used sparingly it can
be used to reduce the end-game overhead as BEG signals that a piece is rare
and should be acquired as quickly as possible, thus making it common.
THEX: The only time thex is a good thing is when you have a speech
impediment. THEX as a design lacks security, fails to make anything
resembling proper use of the available space (7/8 of the overhead bits are
wasted immediately), scales poorly and again the only suggestion to improve
it is to send the grandchildren as well which makes the children pure
overhead, having no redeeming value what so ever. THEX is wasteful,
pointless and insecure for BitTorrent..
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-***@yahoogroups.com
<*> Your use of Yahoo! Groups is subject to:
http://docs.yahoo.com/info/terms/