You are here

Reverse lookups in GNS

Motivation
DNS allows to resolve the name of an IP address. This is sometimes called "reverse lookup". In fact, it is actually "normal" resolution of a PTR record. The name of such a record would be, for example, 4.4.8.8.in-addr.arpa. The .arpa TLD is managed by IANA.

This blogpost is meant to spread ideas that have been exchanged via private email and might be interesting for a broader audience. If you feel like you have useful comments, don't hesitate to do so.

Reverse resolution is a useful feature to enhance readability of service descriptors.
Examples where reverse lookups are useful include:
Received an email from bob@ABCD.zkey or pubkey authentication by ABCD.zkey to my service.
In GNS, reverse resolution is currently not supported and even if it was, there are some obstacles that need to be managed.

Reverse lookups in GNS
GNS names (.gnu TLD) are resolved relative the the user's local root zone. GNS reverse lookups are limited to PKEYs. e.g. Alice wants to know who ABCD.zkey is and how her root namespace relates to that identity.

A simple example reverse lookup would be:

$ gnunet-gns -R ABCD.zkey
Result: dave.bob.gnu

This tells alice that ABCD.zkey is actually "dave" that is known by Alice's friend "bob".
However, the actual lookup of this delegation is non-trivial in GNS as bob can choose any name for dave's PKEY. This name is unknown to Alice.
A straight forward approach for a lookup would be the following:

  1. Alice check's her local root namespace for a delegation record (PKEY) with label "name" that contains ABCD
    1. If a record is found, stop and return name.gnu
    2. else continue with 2.
  2. Alice performs a GNS lookup for the NICKname of ABCD resulting in a result "nick"
  3. Alice checks if one of the zones she delegates to contain a PKEY record with name "nick" and value ABDC
  4. If a result is found as a delegation to dave.delegation.gnu the result is returned
  5. Else resolution stops

Why does resultion stop at 5.? Because if Alice cannot find a delegation to ABCD in one of her known and delegated PKEYs there is no way for her to enumerate all records in those namespaces (by design, GNS leverages this for query privacy and record confidentiality).
This method is characterized by two properties:

  • The resolution direction is "forward", i.e. lookup starts at the root zone and not at the target zone
  • The algorithm tries to "guess" likely chosen names (NICKs) to resolve 3rd party delegation
  • Without some additional meta information, reverse lookups are limited to two hops, e.g. dave.bob.gnu is possible, dave.carol.bob.gnu is not

Advanced reverse lookups in GNS
In some discussions with Christian we have established a few approches that can improve reverse resolution.

REVERSE records
If namespaces would contain special records under the "+" label that point back to other namespaces delegating to them it would allow us to implement an algorithm to lookup the delegation "backwards", i.e. starting from the zone in question (ABCD):

  1. Alice resolves "+" REVERSE records in ABCD, if not existant resolution fails
  2. For each entry e_n in the REVERSE record set, Alice checks if she has a delegation to that PKEY in her master zone, return chain if true
  3. Repeat 2 until found or a certain theshold/limit of recursions is reached and return error

This approach requires the addition and management of REVERSE records. As this cannot be expected by the user it must be done by GNS automatically. For example, GNS might periodically check if any namespaces delegated to from the root zone also contain a delegation back to our root zone (e.g. by checking if alice.bob.gnu can be resolved to Alice's root zone). Those namespaces are added in a REVERSE record.

  • The resolution direction is "backward", i.e. lookup starts at the target zone and not at the root zone
  • The algorithm relies on correct mappings in REVERSE record and the usage of likely chosen names (NICKs) to resolve 3rd party delegation
  • It supports any length of delegations

REVERSE and FORWARD records
We could also support some kind of directed
search from both ends:

  1. The "+" record set contains a special record with
    a list of PKEY delegations that I'm aware of (REVERSE)
  2. The "+" record can similarly contain a list of public
    labels of PKEY records that I delegate to (FORWARD)

Now, if we want to find out who ABCD.zkey is, we start from both ends:

  1. Match REVERSE of ABCD.zkey against all of my names/delegations; if not found: 2
  2. Download zones below all of my names; see if they match those found in previous step
  3. Get FORWARDS of zones from 2; match against ABCD and ABCD's REVERSEs
  4. continue collecting FORWARDS and REVERSE and matching them

Each of the iterations results in an exponential increase in the
working sets, so we shoud stop at some maximum number of records inspected with "not found".

  • The resolution direction is "forward" AND "backward", i.e. lookup starts at the target zone and at the root zone
  • The algorithm does not rely on correct mappings in REVERSE records and the usage of likely chosen names (NICKs) to resolve 3rd party delegation
  • It supports any length of delegations
  • It _might_ be a time improvement over only REVERSE "backward" resolution by trading it for state space
  • EDIT: One other thing is that this approach improves resolution success in cases where no complete REVERSE chain exists

Global delegation DB
If we add a way to distribute the public
delegations, for which something simple like running a combination of
gossip (new public record) and the existing GNUnet SET union protocol
(new neighbour) between peers should allow us to easily replicate the
entire public DB globally. Then, reverse lookup is trivial (local
DB operation), at least as long as all public links can be globally
replicated. Might combine it with some modest proof-of-work to avoid
people spamming the network.
This might also require us to redefine record visibility to:

  • private: (as in private in GNS right now, or local signature in
    GnuPG):
    only I can use them
  • public: (as in GnuPG Web-of-trust):
    everybody can see that X has delegated name Y to key Z
  • default: (as in GNS non-private / GNS default):
    the records are stored encrypted/obfuscated in a DHT, if you know
    the zone and label, you can get and decode them
  • Aka "Too boring and too inefficient"[sic]