Quoting Michael Rogers <[email protected]> from ml.gnutella.dev-forum:
:The probability of an SHA1 collision is negligible, so I don't think we
:need to take any special measures to avoid it.
I know the probability is low, however...
:Metadata can be supported without changing the protocol by incorporating
:the metadata into the key. For example, to store a push proxy address,
:prepend "PUSH:" to your GUID and hash the result to get the DHT key. To
:store a file address, prepend "SHA1:" to the file's SHA1 and hash the
:result to get the DHT key.
... that would make the nature of the data stored opaque. I prefer a
scheme where the nature of the data stored in the DHT can be monitored
and analyzed. For instance, we can enforce different architectural TTL
limits for different types of data.
Knowing the type of data stored can also allow validation of the data
at store time, rejecting badly-formed values. When storing an alt-loc
for a file for instance, or a push-proxy address, we can ensure the
IP is not that of a private LAN (which would not be reachable from the
outside). If you don't know the data you're storing, this kind of sanity
check is impossible.
One problem with validation is that it can prevent extensibility. We
cannot foresee today all the possible value types we're going to be
willing to store in the DHT, so it is not possible to validate types
we do not know about. However, if we choose the route of this "explicit
typing" of values, we have to be clear that an unknown type is something
that is totally acceptable by DHT nodes, only it won't be validated and
therefore "semantic errors" will not be detected as early as they could.
As the nodes evolve, these new data type will eventually be specified
(because there is little value in storing something in a DHT that cannot
be publicly retrieved and understood) and then these nodes will learn
how to validate the new value type.
:> We could therefore slightly modify the FIND_NODE calls to add an argument
:> to the mandatory KUID: a flag indicating whether we're locating for PUT
:> purposes or not, and which type of data we're looking at ('H' or 'P' for
:> instance). Only when locating for PUT purposes would the FIND_NODE
:> return a meaningful Security Token in the reply (by specifying the length
:> of the token to be 0, we can avoid sending anything back in the current
:> LimeWire published message architecture).
:
:It might be worth returning a security token even if the lookup is for a
:GET, because the node performing the lookup can cache the token and use
:it in future PUTs. (Incidentally, did we resolve the question of how
:long security tokens should be valid?)
Maybe. The answer to whether this is worth or not really depends on
the recommended lifetime of the Security Token. If one follows the
pure logic behind the existence of the token, its lifetime should be
short, i.e. a few minutes. That would physically prevent someone to
store on a node without going through the FIND_NODE protocol first
(which is useful in my little DSHT design here because "hiding" of full
hosts can be done during FIND_NODE, precisely).
Such a decision would make caching Security Tokens totally useless.
However, it is a difficult decision to make for me today because I have
not yet completed the implementation of the basic Kademlia layer in
gtk-gnutella, so I cannot analyse the exact amount of traffic that goes
on during a STORE operation.
:> What does this buy us? It gives a node the opportunity to filter-out the
:> ideal target for a PUT if it is itself storing data for that key and it is
:> also "Full" already. It knows that the ideal target is also "Full" because
:> it gets periodic republishing from the ideal target and it can see how many
:> items that node holds, and therefore can tell whether it is also "Full".
:
:Can I suggest a slight modification? Instead of trying to work out
:whether the ideal location is full, the node should just return a flag
:indicating whether the node itself full. If so, the requester should
:store the item at the previous node visited. If not, continue the
:lookup. This saves DHT nodes from having to monitor each other's fullness.
That is a good suggestion indeed. There is already an architected
"Contact's flag" field in the header of all Kademlia messages in the
LW documentation. However, I am not sure we can steal one bit here to
report "busy" conditions if these pertain to only a specific key and not
to a general flag about the node.
Reporting a "full" bit in these flags would be for instance OK if this meant
that the node no longer has any space to store new values. But to indicate
that the key which is looked for a PUT is a hotspot, we would probably need
to change the message format and add this indication in the reply payload.
:If you agree with the suggestions above about metadata and security
:tokens then I believe the "full" flag in FIND_NODE_RESPONSE is the only
:change we need to make to the protocol.
Well, not only. We need to extend the set of error codes that can be
returned. I'm not satisfied by having to report "0x2 - Error" on STORE
if that can mean several conditions, including "Full" for the key, or
"Full" as in: no more storage available for any key.
We need to distinguish FIND_NODE for bucket refreshes from FIND_NODE
preparing a STORE operation. Because we don't necessarily want to hide a
node that is the hotspot for a given key in bucket refreshes, or the node
that precede it in the KUID space will soon become the hotspot as everyone
will start to think it is the ideal place to store and lookup for the key!
Last but not least, I would want to hear LimeWire's views on all this.
The aim here is to come up with something that can be inter-operable,
not something that is gtk-gnutella specific. All nodes in the DHT must
share the same logic on how things are orchestrated, otherwise we will
have random chaos that benefits nobody.
Since I have not yet started implementation of this "high-level" part of
the Kademlia layer, I'm fairly open. Whereas LimeWire has already coded
something and deployed it, so I'm expecting a fair level of reluctance to
"change something that works".
Raphael
P.S: The LimeWire folks have a strange line of thinking, that can be
demonstrated by the following example:
A long time ago, I architected and publicly documented the GGEP "H"
extension used to carry binary hashes in messages.
The GGEP "H" payload format is the following:
<hash type> 1 byte
<binary hash digest> x bytes, determined by hash type
Type Hash Digest length URN scheme
---- -------- ------------- -------------
0x01 sha1 20 urn:sha1:
0x02 bitprint 20+24=44 (a) urn:bitprint:
0x03 md5 16 urn:md5:
0x04 uuid 16 (b) uuid:
0x05 md4 16 urn:md4:
LimeWire has never been willing to support GGEP "H", instead emitting the
SHA1 in base32 encoding preceded by urn:sha1:, which is a waste of bytes.
Also they were emitting urn:ttroot: followed by a base32 representation
of the root of the Tiger Tree Hash.
Recently though, they must have been realizing how much a waste this was
creating and decided... to create a GGEP "TT" extension to hold the binary
represention of the root of the TTH!
Why not use GGEP "H", which is already standard, for which support is
advertised during queries, in the query flags (so that servents can reply
with GGEP "H" only if they know the remote end will understand it, which
is nice), and whose type 0x02 can hold both the SHA1 and the TTH root in
one big binary payload...?
Beats me.
So I've learned that LimeWire will not always do what is the most logical,
unfortunately!
lmpx.com only provides a reader for public news (NNTP) servers. It is not
affiliated with the servers or forums shown here and is not responsible for
the content of articles, which is written by their respective authors.