Re: Using the DHT to find download sources

I saw many good ideas! Instead of going to the technique details
directly, however, I'd like to take a step back and get requirements,
etc clear, as I suggested in our email discussion. I think we can save
time this way. 

Usage of the DHT:
1) helping Gnutella for keyword searches. A DHT can be used to publish
and to search the rare files. We don't want the DHT to handle popular
files because Gnutella is already good at searching popular files. And
we don't want to overload DHT or create hotspots. 
2) publishing and searching push-proxies, alt-locs, and magnet links. 
3) serving as distributed tracker for bittorrent enabled clients. A
DHT can also be used to search torrent files.

Requirements:
1) Fast search and low overhead.
2) Hotspot mitigation. 
3) Quota system. 
4) Security related. 
  i) Data security. E.g., One user's published data must not be
deleted by another user; 
  ii) Index poisoning/pollution attack mitigation. 
  iii) Routing security. I.e., always be able to find the replica roots.
5) Spam mitigation. This is also security related.
6) A richer API. The DHT can be used for several things which may have
different requirements.

These lists are what I can think of so far. Just want to start our
discussion. Please edit... I will also add more items later. Then we
will need to prioritize things...





--- In [email protected], Raphael_Manfredi@... wrote:
>
> Quoting Michael Rogers <m.rogers@...> 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!
>