- Add reverse resolution with limited functionality

11 files changed, 987 insertions, 160 deletions

diff --git a/src/gns/Makefile.am b/src/gns/Makefile.am
index 33fd96d9d..0b65a3d17 100644
--- a/src/gns/Makefile.am
+++ b/src/gns/Makefile.am
@@ -184,6 +184,7 @@ w32nsp_resolve_LDADD = -lws2_32
 gnunet_service_gns_SOURCES = \
  gnunet-service-gns.c \
  gnunet-service-gns_resolver.c gnunet-service-gns_resolver.h \
+ gnunet-service-gns_reverser.c gnunet-service-gns_reverser.h \
  gnunet-service-gns_shorten.c gnunet-service-gns_shorten.h \
  gnunet-service-gns_interceptor.c gnunet-service-gns_interceptor.h
 gnunet_service_gns_LDADD = \
@@ -258,7 +259,8 @@ check_SCRIPTS = \
   test_gns_rel_expiration.sh\
   test_gns_soa_lookup.sh\
   test_gns_revocation.sh\
-  test_gns_cname_lookup.sh
+  test_gns_cname_lookup.sh \
+        test_gns_reverse_lookup.sh
 
 if ENABLE_TEST_RUN
 if HAVE_SQLITE
diff --git a/src/gns/gns.h b/src/gns/gns.h
index 476cb0fd2..ca5525f80 100644
--- a/src/gns/gns.h
+++ b/src/gns/gns.h
@@ -91,6 +91,32 @@ struct LookupMessage
 
 
 /**
+ * Message from client to GNS service to lookup records.
+ */
+struct ReverseLookupMessage
+{
+  /**
+   * Header of type #GNUNET_MESSAGE_TYPE_GNS_REVERSE_LOOKUP
+   */
+  struct GNUNET_MessageHeader header;
+
+  /**
+   * Unique identifier for this request (for key collisions).
+   */
+  uint32_t id GNUNET_PACKED;
+
+  /**
+   * Zone that is target for reverse lookup
+   */
+  struct GNUNET_CRYPTO_EcdsaPublicKey zone_pkey;
+  
+  /**
+   * Root zone
+   */
+  struct GNUNET_CRYPTO_EcdsaPublicKey root_pkey;
+};
+
+/**
  * Message from GNS service to client: new results.
  */
 struct LookupResultMessage
@@ -114,6 +140,24 @@ struct LookupResultMessage
 
 };
 
+/**
+ * Message from GNS service to client: new results.
+ */
+struct ReverseLookupResultMessage
+{
+  /**
+    * Header of type #GNUNET_MESSAGE_TYPE_GNS_REVERSE_LOOKUP_RESULT
+   */
+  struct GNUNET_MessageHeader header;
+
+  /**
+   * Unique identifier for this request (for key collisions).
+   */
+  uint32_t id GNUNET_PACKED;
+
+  /* followed by the resulting name of the reverse lookup */
+};
+
 
 GNUNET_NETWORK_STRUCT_END
 
diff --git a/src/gns/gns_api.c b/src/gns/gns_api.c
index b9b95b7c2..3f6425b42 100644
--- a/src/gns/gns_api.c
+++ b/src/gns/gns_api.c
@@ -79,6 +79,49 @@ struct GNUNET_GNS_LookupRequest
 
 };
 
+/**
+ * Handle to a lookup request
+ */
+struct GNUNET_GNS_ReverseLookupRequest
+{
+
+  /**
+   * DLL
+   */
+  struct GNUNET_GNS_ReverseLookupRequest *next;
+
+  /**
+   * DLL
+   */
+  struct GNUNET_GNS_ReverseLookupRequest *prev;
+
+  /**
+   * handle to gns
+   */
+  struct GNUNET_GNS_Handle *gns_handle;
+
+  /**
+   * processor to call on lookup result
+   */
+  GNUNET_GNS_ReverseLookupResultProcessor lookup_proc;
+
+  /**
+   * @e lookup_proc closure
+   */
+  void *proc_cls;
+
+  /**
+   * Envelope with the message for this queue entry.
+   */
+  struct GNUNET_MQ_Envelope *env;
+
+  /**
+   * request id
+   */
+  uint32_t r_id;
+
+};
+
 
 /**
  * Connection to the GNS service.
@@ -107,6 +150,15 @@ struct GNUNET_GNS_Handle
   struct GNUNET_GNS_LookupRequest *lookup_tail;
 
   /**
+   * Head of linked list of active reverse lookup requests.
+   */
+  struct GNUNET_GNS_ReverseLookupRequest *rev_lookup_head;
+
+  /**
+   * Tail of linked list of active reverse lookup requests.
+   */
+  struct GNUNET_GNS_ReverseLookupRequest *rev_lookup_tail;
+  /**
    * Reconnect task
    */
   struct GNUNET_SCHEDULER_Task *reconnect_task;
@@ -180,10 +232,71 @@ mq_error_handler (void *cls,
                   enum GNUNET_MQ_Error error)
 {
   struct GNUNET_GNS_Handle *handle = cls;
-
+  LOG (GNUNET_ERROR_TYPE_WARNING, "Problem with message queue. error: %i\n",
+       error);
   force_reconnect (handle);
 }
 
+/**
+ * Check validity of message received from the GNS service
+ *
+ * @param cls the `struct GNUNET_GNS_Handle *`
+ * @param loookup_msg the incoming message
+ */
+static int
+check_rev_result (void *cls,
+              const struct ReverseLookupResultMessage *lookup_msg)
+{
+  size_t mlen = ntohs (lookup_msg->header.size) - sizeof (*lookup_msg);
+  char *name;
+  
+  name = (char*) &lookup_msg[1];
+  if ('\0' != name[mlen-1])
+  {
+    GNUNET_break (0);
+    return GNUNET_SYSERR;
+  }
+  return GNUNET_OK;
+}
+
+
+/**
+ * Handler for messages received from the GNS service
+ *
+ * @param cls the `struct GNUNET_GNS_Handle *`
+ * @param loookup_msg the incoming message
+ */
+static void
+handle_rev_result (void *cls,
+                   const struct ReverseLookupResultMessage *lookup_msg)
+{
+  struct GNUNET_GNS_Handle *handle = cls;
+  char *name;
+  uint32_t r_id = ntohl (lookup_msg->id);
+  struct GNUNET_GNS_ReverseLookupRequest *rlr;
+  GNUNET_GNS_ReverseLookupResultProcessor proc;
+  void *proc_cls;
+
+  name = (char*)&lookup_msg[1];
+  LOG (GNUNET_ERROR_TYPE_DEBUG,
+       "Received reverse lookup reply from GNS service (%s)\n",
+       name);
+  for (rlr = handle->rev_lookup_head; NULL != rlr; rlr = rlr->next)
+    if (rlr->r_id == r_id)
+      break;
+  if (NULL == rlr)
+    return;
+  proc = rlr->lookup_proc;
+  proc_cls = rlr->proc_cls;
+  GNUNET_CONTAINER_DLL_remove (handle->rev_lookup_head,
+                               handle->rev_lookup_tail,
+                               rlr);
+  GNUNET_free (rlr);
+  proc (proc_cls,
+        name);
+}
+
+
 
 /**
  * Check validity of message received from the GNS service
@@ -269,9 +382,14 @@ reconnect (struct GNUNET_GNS_Handle *handle)
                            GNUNET_MESSAGE_TYPE_GNS_LOOKUP_RESULT,
                            struct LookupResultMessage,
                            handle),
+    GNUNET_MQ_hd_var_size (rev_result,
+                           GNUNET_MESSAGE_TYPE_GNS_REVERSE_LOOKUP_RESULT,
+                           struct ReverseLookupResultMessage,
+                           handle),
     GNUNET_MQ_handler_end ()
   };
   struct GNUNET_GNS_LookupRequest *lh;
+  struct GNUNET_GNS_ReverseLookupRequest *rlh;
 
   GNUNET_assert (NULL == handle->mq);
   LOG (GNUNET_ERROR_TYPE_DEBUG,
@@ -286,6 +404,9 @@ reconnect (struct GNUNET_GNS_Handle *handle)
   for (lh = handle->lookup_head; NULL != lh; lh = lh->next)
     GNUNET_MQ_send_copy (handle->mq,
                          lh->env);
+  for (rlh = handle->rev_lookup_head; NULL != rlh; rlh = rlh->next)
+    GNUNET_MQ_send_copy (handle->mq,
+                         rlh->env);
 }
 
 
@@ -331,6 +452,7 @@ GNUNET_GNS_disconnect (struct GNUNET_GNS_Handle *handle)
     handle->reconnect_task = NULL;
   }
   GNUNET_assert (NULL == handle->lookup_head);
+  GNUNET_assert (NULL == handle->rev_lookup_head);
   GNUNET_free (handle);
 }
 
@@ -352,6 +474,22 @@ GNUNET_GNS_lookup_cancel (struct GNUNET_GNS_LookupRequest *lr)
   GNUNET_free (lr);
 }
 
+/**
+ * Cancel pending reverse lookup request
+ *
+ * @param lr the lookup request to cancel
+ */
+void
+GNUNET_GNS_reverse_lookup_cancel (struct GNUNET_GNS_ReverseLookupRequest *lr)
+{
+  struct GNUNET_GNS_Handle *handle = lr->gns_handle;
+
+  GNUNET_CONTAINER_DLL_remove (handle->rev_lookup_head,
+                               handle->rev_lookup_tail,
+                               lr);
+  GNUNET_MQ_discard (lr->env);
+  GNUNET_free (lr);
+}
 
 /**
  * Perform an asynchronous lookup operation on the GNS.
@@ -368,13 +506,13 @@ GNUNET_GNS_lookup_cancel (struct GNUNET_GNS_LookupRequest *lr)
  */
 struct GNUNET_GNS_LookupRequest*
 GNUNET_GNS_lookup (struct GNUNET_GNS_Handle *handle,
-                   const char *name,
-                   const struct GNUNET_CRYPTO_EcdsaPublicKey *zone,
-                   uint32_t type,
-                   enum GNUNET_GNS_LocalOptions options,
-                   const struct GNUNET_CRYPTO_EcdsaPrivateKey *shorten_zone_key,
-                   GNUNET_GNS_LookupResultProcessor proc,
-                   void *proc_cls)
+                   const char *name,
+                   const struct GNUNET_CRYPTO_EcdsaPublicKey *zone,
+                   uint32_t type,
+                   enum GNUNET_GNS_LocalOptions options,
+                   const struct GNUNET_CRYPTO_EcdsaPrivateKey *shorten_zone_key,
+                   GNUNET_GNS_LookupResultProcessor proc,
+                   void *proc_cls)
 {
   /* IPC to shorten gns names, return shorten_handle */
   struct LookupMessage *lookup_msg;
@@ -413,8 +551,8 @@ GNUNET_GNS_lookup (struct GNUNET_GNS_Handle *handle,
     lookup_msg->shorten_key = *shorten_zone_key;
   }
   GNUNET_memcpy (&lookup_msg[1],
-          name,
-          nlen);
+                 name,
+                 nlen);
   GNUNET_CONTAINER_DLL_insert (handle->lookup_head,
                                handle->lookup_tail,
                                lr);
@@ -424,5 +562,50 @@ GNUNET_GNS_lookup (struct GNUNET_GNS_Handle *handle,
   return lr;
 }
 
+/**
+ * Perform an asynchronous reverse lookup operation on the GNS.
+ *
+ * @param handle handle to the GNS service
+ * @param zone_key zone to find a name for
+ * @param root_key our zone
+ * @param proc processor to call on result
+ * @param proc_cls closure for @a proc
+ * @return handle to the request
+ */
+struct GNUNET_GNS_ReverseLookupRequest*
+GNUNET_GNS_reverse_lookup (struct GNUNET_GNS_Handle *handle,
+                           const struct GNUNET_CRYPTO_EcdsaPublicKey *zone_key,
+                           const struct GNUNET_CRYPTO_EcdsaPublicKey *root_key,
+                           GNUNET_GNS_ReverseLookupResultProcessor proc,
+                           void *proc_cls)
+{
+  /* IPC to shorten gns names, return shorten_handle */
+  struct ReverseLookupMessage *rev_lookup_msg;
+  struct GNUNET_GNS_ReverseLookupRequest *lr;
 
+  if ((NULL == zone_key) || (NULL == root_key))
+  {
+    GNUNET_break (0);
+    return NULL;
+  }
+  LOG (GNUNET_ERROR_TYPE_DEBUG,
+       "Trying to reverse lookup in GNS\n");
+  lr = GNUNET_new (struct GNUNET_GNS_ReverseLookupRequest);
+  lr->gns_handle = handle;
+  lr->lookup_proc = proc;
+  lr->proc_cls = proc_cls;
+  lr->r_id = handle->r_id_gen++;
+  lr->env = GNUNET_MQ_msg (rev_lookup_msg,
+                           GNUNET_MESSAGE_TYPE_GNS_REVERSE_LOOKUP);
+  rev_lookup_msg->id = htonl (lr->r_id);
+  rev_lookup_msg->zone_pkey = *zone_key;
+  rev_lookup_msg->root_pkey = *root_key;
+  GNUNET_CONTAINER_DLL_insert (handle->rev_lookup_head,
+                               handle->rev_lookup_tail,
+                               lr);
+  if (NULL != handle->mq)
+    GNUNET_MQ_send_copy (handle->mq,
+                         lr->env);
+  return lr;
+}
 /* end of gns_api.c */
diff --git a/src/gns/gnunet-gns.c b/src/gns/gnunet-gns.c
index 62cec54cb..17fe4cbda 100644
--- a/src/gns/gnunet-gns.c
+++ b/src/gns/gnunet-gns.c
@@ -66,6 +66,16 @@ static char *zone_ego_name;
 static char *public_key;
 
 /**
+ * Reverse key
+ */
+static char *reverse_key;
+
+/**
+ * Reverse key
+ */
+static struct GNUNET_CRYPTO_EcdsaPublicKey rkey;
+
+/**
  * Set to GNUNET_GNS_LO_LOCAL_MASTER if we are looking up in the master zone.
  */
 static enum GNUNET_GNS_LocalOptions local_options;
@@ -86,6 +96,11 @@ static int rtype;
 static struct GNUNET_GNS_LookupRequest *lookup_request;
 
 /**
+ * Handle to reverse lookup request
+ */
+static struct GNUNET_GNS_ReverseLookupRequest *rev_lookup_request;
+
+/**
  * Lookup an ego with the identity service.
  */
 static struct GNUNET_IDENTITY_EgoLookup *el;
@@ -159,6 +174,24 @@ do_timeout (void *cls)
   GNUNET_SCHEDULER_shutdown ();
 }
 
+static void
+process_reverse_result (void *cls,
+                        const char *name)
+{
+  rev_lookup_request = NULL;
+  if (NULL == name)
+  {
+    printf ("No name found.\n");
+    return;
+  }
+  if (raw)
+    printf ("%s\n", name);
+  else
+    printf ("%s is known as %s\n",
+            reverse_key,
+            name);
+  GNUNET_SCHEDULER_shutdown ();
+}
 
 /**
  * Function called with the result of a GNS lookup.
@@ -248,6 +281,14 @@ lookup_with_keys (const struct GNUNET_CRYPTO_EcdsaPublicKey *pkey,
                                         &process_lookup_result,
                                         lookup_name);
   }
+  else if (NULL != reverse_key)
+  {
+    rev_lookup_request = GNUNET_GNS_reverse_lookup (gns,
+                                                &rkey,
+                                                pkey,
+                                                &process_reverse_result,
+                                                NULL);
+  }
   else
   {
     fprintf (stderr,
@@ -416,49 +457,77 @@ run (void *cls,
     return;
   }
   tt = GNUNET_SCHEDULER_add_delayed (timeout,
-                                     &do_timeout, NULL);
+                                     &do_timeout, NULL);
   GNUNET_SCHEDULER_add_shutdown (&do_shutdown, NULL);
+  if (NULL != reverse_key)
+  {
+    if (GNUNET_OK !=
+        GNUNET_CRYPTO_ecdsa_public_key_from_string (reverse_key,
+                                                    strlen (reverse_key),
+                                                    &rkey))
+    {
+      fprintf (stderr,
+               _("Reverse key `%s' is not well-formed\n"),
+               reverse_key);
+      GNUNET_SCHEDULER_shutdown ();
+      return;
+    }
+  }
   if (NULL != public_key)
   {
     if (GNUNET_OK !=
-        GNUNET_CRYPTO_ecdsa_public_key_from_string (public_key,
-                                                  strlen (public_key),
-                                                  &pkey))
+        GNUNET_CRYPTO_ecdsa_public_key_from_string (public_key,
+                                                    strlen (public_key),
+                                                    &pkey))
     {
       fprintf (stderr,
-               _("Public key `%s' is not well-formed\n"),
-               public_key);
+               _("Public key `%s' is not well-formed\n"),
+               public_key);
       GNUNET_SCHEDULER_shutdown ();
       return;
     }
     lookup_with_public_key (&pkey);
     return;
   }
+  if (NULL != reverse_key)
+  {
+    if (GNUNET_OK !=
+        GNUNET_CRYPTO_ecdsa_public_key_from_string (reverse_key,
+                                                    strlen (reverse_key),
+                                                    &rkey))
+    {
+      fprintf (stderr,
+               _("Reverse key `%s' is not well-formed\n"),
+               reverse_key);
+      GNUNET_SCHEDULER_shutdown ();
+      return;
+    }
+  }
   if (NULL != zone_ego_name)
   {
     el = GNUNET_IDENTITY_ego_lookup (cfg,
-                                     zone_ego_name,
-                                     &identity_zone_cb,
-                                     NULL);
+                                     zone_ego_name,
+                                     &identity_zone_cb,
+                                     NULL);
     return;
   }
   if ( (NULL != lookup_name) &&
        (strlen (lookup_name) > 4) &&
        (0 == strcmp (".zkey",
-                     &lookup_name[strlen (lookup_name) - 4])) )
+                     &lookup_name[strlen (lookup_name) - 4])) )
   {
     /* no zone required, use 'anonymous' zone */
     GNUNET_CRYPTO_ecdsa_key_get_public (GNUNET_CRYPTO_ecdsa_key_get_anonymous (),
-                                      &pkey);
+                                        &pkey);
     lookup_with_public_key (&pkey);
   }
   else
   {
     GNUNET_break (NULL == id_op);
     id_op = GNUNET_IDENTITY_get (identity,
-                                 "gns-master",
-                                 &identity_master_cb,
-                                 NULL);
+                                 "gns-master",
+                                 &identity_master_cb,
+                                 NULL);
     GNUNET_assert (NULL != id_op);
   }
 }
@@ -493,6 +562,9 @@ main (int argc, char *const *argv)
     {'z', "zone", "NAME",
       gettext_noop ("Specify the name of the ego of the zone to lookup the record in"), 1,
       &GNUNET_GETOPT_set_string, &zone_ego_name},
+    {'R', "reverse", "PKEY",
+      gettext_noop ("Specify the public key of the zone to reverse lookup a name for"), 1,
+      &GNUNET_GETOPT_set_string, &reverse_key},
     GNUNET_GETOPT_OPTION_END
   };
   int ret;
@@ -503,11 +575,11 @@ main (int argc, char *const *argv)
 
   GNUNET_log_setup ("gnunet-gns", "WARNING", NULL);
   ret =
-      (GNUNET_OK ==
-       GNUNET_PROGRAM_run (argc, argv, "gnunet-gns",
-                           _("GNUnet GNS resolver tool"),
-                           options,
-                           &run, NULL)) ? 0 : 1;
+    (GNUNET_OK ==
+     GNUNET_PROGRAM_run (argc, argv, "gnunet-gns",
+                         _("GNUnet GNS resolver tool"),
+                         options,
+                         &run, NULL)) ? 0 : 1;
   GNUNET_free ((void*) argv);
   return ret;
 }
diff --git a/src/gns/gnunet-service-gns.c b/src/gns/gnunet-service-gns.c
index 386e6d744..221d75bba 100644
--- a/src/gns/gnunet-service-gns.c
+++ b/src/gns/gnunet-service-gns.c
@@ -35,6 +35,7 @@
 #include "gnunet_statistics_service.h"
 #include "gns.h"
 #include "gnunet-service-gns_resolver.h"
+#include "gnunet-service-gns_reverser.h"
 #include "gnunet-service-gns_shorten.h"
 #include "gnunet-service-gns_interceptor.h"
 #include "gnunet_protocols.h"
@@ -109,6 +110,11 @@ struct ClientLookupHandle
   struct GNS_ResolverHandle *lookup;
 
   /**
+   * Active handle for a reverse lookup
+   */
+  struct GNS_ReverserHandle *rev_lookup;
+
+  /**
    * request id
    */
   uint32_t request_id;
@@ -367,7 +373,10 @@ client_disconnect_cb (void *cls,
               client);
   while (NULL != (clh = gc->clh_head))
   {
-    GNS_resolver_lookup_cancel (clh->lookup);
+    if (NULL != clh->lookup)
+      GNS_resolver_lookup_cancel (clh->lookup);
+    if (NULL != clh->rev_lookup)
+      GNS_reverse_lookup_cancel (clh->rev_lookup);
     GNUNET_CONTAINER_DLL_remove (gc->clh_head,
                                  gc->clh_tail,
                                  clh);
@@ -846,6 +855,47 @@ send_lookup_response (void* cls,
                             GNUNET_NO);
 }
 
+/**
+ * Reply to client with the result from our reverse lookup.
+ *
+ * @param cls the closure (our client lookup handle)
+ * @param rd_count the number of records in @a rd
+ * @param rd the record data
+ */
+static void
+send_reverse_lookup_response (void* cls,
+                              const char *name)
+{
+  struct ClientLookupHandle *clh = cls;
+  struct GNUNET_MQ_Envelope *env;
+  struct ReverseLookupResultMessage *rmsg;
+  size_t len;
+
+  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
+              "Sending LOOKUP_RESULT message with %s\n",
+              name);
+
+  if (NULL == name)
+    len = 1;
+  else
+    len = strlen (name) + 1;
+  env = GNUNET_MQ_msg_extra (rmsg,
+                             len,
+                             GNUNET_MESSAGE_TYPE_GNS_REVERSE_LOOKUP_RESULT);
+  rmsg->id = clh->request_id;
+  if (1 < len)
+    GNUNET_memcpy ((char*) &rmsg[1],
+                   name,
+                   strlen (name));
+  GNUNET_MQ_send (GNUNET_SERVICE_client_get_mq(clh->gc->client),
+                  env);
+  GNUNET_CONTAINER_DLL_remove (clh->gc->clh_head, clh->gc->clh_tail, clh);
+  GNUNET_free (clh);
+  GNUNET_STATISTICS_update (statistics,
+                            "Completed reverse lookups", 1,
+                            GNUNET_NO);
+}
+
 
 /**
  * Checks a #GNUNET_MESSAGE_TYPE_GNS_LOOKUP message
@@ -856,7 +906,7 @@ send_lookup_response (void* cls,
  */
 static int
 check_lookup (void *cls,
-                    const struct LookupMessage *l_msg)
+              const struct LookupMessage *l_msg)
 {
   size_t msg_size;
   const char* name;
@@ -936,6 +986,37 @@ handle_lookup (void *cls,
                             1, GNUNET_NO);
 }
 
+/**
+ * Handle reverse lookup requests from client
+ *
+ * @param cls the closure
+ * @param client the client
+ * @param message the message
+ */
+static void
+handle_rev_lookup (void *cls,
+                   const struct ReverseLookupMessage *sh_msg)
+{
+  struct GnsClient *gc = cls;
+  struct ClientLookupHandle *clh;
+
+  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
+              "Received REVERSE_LOOKUP message\n");
+  GNUNET_SERVICE_client_continue (gc->client);
+
+  clh = GNUNET_new (struct ClientLookupHandle);
+  GNUNET_CONTAINER_DLL_insert (gc->clh_head, gc->clh_tail, clh);
+  clh->gc = gc;
+  clh->request_id = sh_msg->id;
+  clh->rev_lookup = GNS_reverse_lookup (&sh_msg->zone_pkey,
+                                        &sh_msg->root_pkey,
+                                        &send_reverse_lookup_response,
+                                        clh);
+  GNUNET_STATISTICS_update (statistics,
+                            "Reverse lookup attempts",
+                            1, GNUNET_NO);
+}
+
 
 /**
  * The zone monitor is now in SYNC with the current state of the
@@ -1149,6 +1230,10 @@ GNUNET_SERVICE_MAIN
                         GNUNET_MESSAGE_TYPE_GNS_LOOKUP,
                         struct LookupMessage,
                         NULL),
+ GNUNET_MQ_hd_fixed_size (rev_lookup,
+                          GNUNET_MESSAGE_TYPE_GNS_REVERSE_LOOKUP,
+                          struct ReverseLookupMessage,
+                          NULL),
  GNUNET_MQ_handler_end());
 
 
diff --git a/src/gns/gnunet-service-gns_reverser.c b/src/gns/gnunet-service-gns_reverser.c
new file mode 100644
index 000000000..6bae20b61
--- /dev/null
+++ b/src/gns/gnunet-service-gns_reverser.c
@@ -0,0 +1,244 @@
+/*
+     This file is part of GNUnet.
+     Copyright (C) 2009-2013 GNUnet e.V.
+
+     GNUnet is free software; you can redistribute it and/or modify
+     it under the terms of the GNU General Public License as published
+     by the Free Software Foundation; either version 3, or (at your
+     option) any later version.
+
+     GNUnet is distributed in the hope that it will be useful, but
+     WITHOUT ANY WARRANTY; without even the implied warranty of
+     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+     General Public License for more details.
+
+     You should have received a copy of the GNU General Public License
+     along with GNUnet; see the file COPYING.  If not, write to the
+     Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+     Boston, MA 02110-1301, USA.
+*/
+/**
+ * @file gns/gnunet-service-gns_reverser.c
+ * @brief GNUnet GNS service
+ * @author Martin Schanzenbach
+ */
+
+
+#include "platform.h"
+#include "gnunet_gns_service.h"
+#include "gnunet-service-gns_resolver.h"
+#include "gnunet-service-gns_reverser.h"
+
+struct ReverseTreeNode
+{
+  /**
+   * DLL
+   */
+  struct ReverseTreeNode *next;
+
+  /**
+   * DLL
+   */
+  struct ReverseTreeNode *prev;
+
+  /**
+   * Resolved name until now
+   */
+  char *name;
+
+  /**
+   * Depth of the resolution at this node
+   */
+  uint8_t depth;
+
+  /**
+   * The pkey of the namespace
+   */
+  struct GNUNET_CRYPTO_EcdsaPublicKey pkey;
+
+};
+
+
+struct GNS_ReverserHandle
+{
+  /**
+   * GNS resolver handle
+   */
+  struct GNS_ResolverHandle *rh;
+
+  /**
+   * The authority to look for
+   */
+  struct GNUNET_CRYPTO_EcdsaPublicKey authority;
+  
+  /**
+   * Resolution candidate queue
+   */
+  struct ReverseTreeNode *node_queue_head;
+
+  /**
+   * Resolution candidate queue
+   */
+  struct ReverseTreeNode *node_queue_tail;
+
+  /**
+   * Max depth for the resolution
+   */
+  uint8_t max_depth;
+
+  /**
+   * Result callback
+   */
+  GNS_ReverseResultProcessor proc;
+
+  /**
+   * Callback closure
+   */
+  void *proc_cls;
+};
+
+void
+cleanup_handle (struct GNS_ReverserHandle *rh)
+{
+  struct ReverseTreeNode *rtn;
+
+  for (rtn = rh->node_queue_head; NULL != rtn; rtn = rh->node_queue_head)
+  {
+    if (NULL != rtn->name)
+      GNUNET_free (rtn->name);
+    GNUNET_CONTAINER_DLL_remove (rh->node_queue_head,
+                                 rh->node_queue_tail,
+                                 rtn);
+    GNUNET_free (rtn);
+  }
+}
+
+void
+handle_gns_result (void *cls,
+                   uint32_t rd_count,
+                   const struct GNUNET_GNSRECORD_Data *rd)
+{
+  struct GNS_ReverserHandle *rh = cls;
+  const struct GNUNET_GNSRECORD_ReverseRecord *rr;
+  struct ReverseTreeNode *rtn;
+  char *result;
+  const char *name;
+  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
+              "Got result (%d)\n", rd_count);
+
+  for (int i = 0; i < rd_count; i++)
+  {
+    /**
+     * Check if we are in the delegation set
+     */
+    if (GNUNET_GNSRECORD_TYPE_REVERSE != rd[i].record_type)
+      continue;
+    rr = rd[i].data;
+    name = (const char*) &rr[1];
+    if (0 == memcmp (&rh->authority,
+                     &rr->pkey,
+                     sizeof (struct GNUNET_CRYPTO_EcdsaPublicKey)))
+    {
+      //Found!
+      GNUNET_asprintf (&result,
+                       "%s.%s.gnu",
+                       rh->node_queue_head->name,
+                       name);
+      GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
+                  "Found path from %s\n", result);
+
+      rh->proc (rh->proc_cls, result);
+      cleanup_handle (rh);
+      GNUNET_free (result);
+      return;
+    } else {
+      if (rh->node_queue_head->depth >= rh->max_depth)
+        break;
+      GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
+                  "Found REVERSE from %s\n", name);
+
+      rtn = GNUNET_new (struct ReverseTreeNode);
+      if (NULL == rh->node_queue_head->name)
+        rtn->name = GNUNET_strdup (name);
+      else
+        GNUNET_asprintf (&rtn->name,
+                         "%s.%s",
+                         rh->node_queue_head->name,
+                         name);
+      rtn->depth = rh->node_queue_head->depth + 1;
+      rtn->pkey = rr->pkey;
+      GNUNET_CONTAINER_DLL_insert_tail (rh->node_queue_head,
+                                        rh->node_queue_tail,
+                                        rtn);
+    }
+  }
+
+  /**
+   * Done here remove node from queue
+   */
+  rtn = rh->node_queue_head;
+  GNUNET_CONTAINER_DLL_remove (rh->node_queue_head,
+                               rh->node_queue_tail,
+                               rtn);
+  if (NULL == rh->node_queue_head)
+  {
+    //No luck
+    rh->proc (rh->proc_cls, NULL);
+    cleanup_handle (rh);
+    return;
+  }
+  rh->rh = GNS_resolver_lookup (&rh->node_queue_head->pkey,
+                                GNUNET_GNSRECORD_TYPE_REVERSE,
+                                "+.gnu",
+                                NULL,
+                                GNUNET_GNS_LO_DEFAULT,
+                                &handle_gns_result,
+                                rh);
+}
+
+struct GNS_ReverserHandle *
+GNS_reverse_lookup (const struct GNUNET_CRYPTO_EcdsaPublicKey *target,
+                    const struct GNUNET_CRYPTO_EcdsaPublicKey *authority,
+                    GNS_ReverseResultProcessor proc,
+                    void *proc_cls)
+{
+  struct GNS_ReverserHandle *rh;
+  struct ReverseTreeNode *rtn;
+
+  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
+              "Starting reverse resolution\n");
+  rh = GNUNET_new (struct GNS_ReverserHandle);
+  rh->proc = proc;
+  rh->proc_cls = proc_cls;
+  rtn = GNUNET_new (struct ReverseTreeNode);
+  rtn->name = NULL;
+  rtn->pkey = *target;
+  rtn->depth = 0;
+  GNUNET_CONTAINER_DLL_insert (rh->node_queue_head,
+                               rh->node_queue_tail,
+                               rtn);
+  rh->authority = *authority;
+  rh->max_depth = 3; //TODO make argument
+  rh->rh = GNS_resolver_lookup (target,
+                                GNUNET_GNSRECORD_TYPE_REVERSE,
+                                "+.gnu",
+                                NULL,
+                                GNUNET_GNS_LO_DEFAULT,
+                                &handle_gns_result,
+                                rh);
+  return rh;
+}
+
+/**
+ * Cancel active resolution (i.e. client disconnected).
+ *
+ * @param rh resolution to abort
+ */
+void
+GNS_reverse_lookup_cancel (struct GNS_ReverserHandle *rh)
+{
+  cleanup_handle (rh);
+  return;
+}
+
+
diff --git a/src/gns/gnunet-service-gns_reverser.h b/src/gns/gnunet-service-gns_reverser.h
new file mode 100644
index 000000000..ecec7d743
--- /dev/null
+++ b/src/gns/gnunet-service-gns_reverser.h
@@ -0,0 +1,72 @@
+/*
+     This file is part of GNUnet.
+     Copyright (C) 2009-2013 GNUnet e.V.
+
+     GNUnet is free software; you can redistribute it and/or modify
+     it under the terms of the GNU General Public License as published
+     by the Free Software Foundation; either version 3, or (at your
+     option) any later version.
+
+     GNUnet is distributed in the hope that it will be useful, but
+     WITHOUT ANY WARRANTY; without even the implied warranty of
+     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+     General Public License for more details.
+
+     You should have received a copy of the GNU General Public License
+     along with GNUnet; see the file COPYING.  If not, write to the
+     Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+     Boston, MA 02110-1301, USA.
+*/
+/**
+ * @file gns/gnunet-service-gns_reverser.h
+ * @brief GNUnet GNS service
+ * @author Martin Schanzenbach
+ */
+#ifndef GNS_REVERSER_H
+#define GNS_REVERSER_H
+#include "gns.h"
+#include "gnunet_gns_service.h"
+
+/**
+ * Handle for an active request.
+ */
+struct GNS_ReverserHandle;
+
+
+/**
+ * Function called with results for a GNS resolution.
+ *
+ * @param cls closure
+ * @param rd_count number of records in @a rd
+ * @param rd records returned for the lookup
+ */
+typedef void (*GNS_ReverseResultProcessor)(void *cls,
+                                           const char *name);
+
+
+/**
+ * Reverse lookup of a specific zone
+ * calls RecordLookupProcessor on result or timeout
+ *
+ * @param target the zone to perform the lookup in
+ * @param authority the authority
+ * @param proc the processor to call
+ * @param proc_cls the closure to pass to @a proc
+ * @return handle to cancel operation
+ */
+struct GNS_ReverserHandle *
+GNS_reverse_lookup (const struct GNUNET_CRYPTO_EcdsaPublicKey *target,
+                    const struct GNUNET_CRYPTO_EcdsaPublicKey *authority,
+                    GNS_ReverseResultProcessor proc,
+                    void *proc_cls);
+
+
+/**
+ * Cancel active resolution (i.e. client disconnected).
+ *
+ * @param rh resolution to abort
+ */
+void
+GNS_reverse_lookup_cancel (struct GNS_ReverserHandle *rh);
+
+#endif
diff --git a/src/gns/plugin_gnsrecord_gns.c b/src/gns/plugin_gnsrecord_gns.c
index 360500af7..5faca4578 100644
--- a/src/gns/plugin_gnsrecord_gns.c
+++ b/src/gns/plugin_gnsrecord_gns.c
@@ -31,6 +31,7 @@
 #include "gnunet_gnsrecord_lib.h"
 #include "gnunet_dnsparser_lib.h"
 #include "gnunet_gnsrecord_plugin.h"
+#include <inttypes.h>
 
 
 /**
@@ -139,6 +140,30 @@ gns_value_to_string (void *cls,
       GNUNET_free (ival);
       return box_str;
     }
+  case GNUNET_GNSRECORD_TYPE_REVERSE:
+    {
+      struct GNUNET_GNSRECORD_ReverseRecord rev;
+      char *rev_str;
+      char *pkey_str;
+
+      if (data_size < sizeof (struct GNUNET_GNSRECORD_ReverseRecord))
+        return NULL; /* malformed */
+
+      memcpy (&rev,
+              data,
+              sizeof (rev));
+      cdata = data;
+      pkey_str = GNUNET_CRYPTO_ecdsa_public_key_to_string (&rev.pkey);
+
+      GNUNET_asprintf (&rev_str,
+                       "%s %s %"SCNu64,
+                       &cdata[sizeof (rev)],
+                       pkey_str,
+                       rev.expiration.abs_value_us);
+      GNUNET_free (pkey_str);
+      return rev_str;
+
+    }
   default:
     return NULL;
   }
@@ -170,147 +195,184 @@ gns_string_to_value (void *cls,
   switch (type)
   {
 
-  case GNUNET_GNSRECORD_TYPE_PKEY:
-    if (GNUNET_OK !=
-        GNUNET_CRYPTO_ecdsa_public_key_from_string (s, strlen (s), &pkey))
-    {
-      GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
-           _("Unable to parse PKEY record `%s'\n"),
-           s);
-      return GNUNET_SYSERR;
-    }
-    *data = GNUNET_new (struct GNUNET_CRYPTO_EcdsaPublicKey);
-    GNUNET_memcpy (*data, &pkey, sizeof (pkey));
-    *data_size = sizeof (struct GNUNET_CRYPTO_EcdsaPublicKey);
-    return GNUNET_OK;
-
-  case GNUNET_GNSRECORD_TYPE_NICK:
-    *data = GNUNET_strdup (s);
-    *data_size = strlen (s);
-    return GNUNET_OK;
-  case GNUNET_GNSRECORD_TYPE_LEHO:
-    *data = GNUNET_strdup (s);
-    *data_size = strlen (s);
-    return GNUNET_OK;
-  case GNUNET_GNSRECORD_TYPE_GNS2DNS:
-    {
-      char nsbuf[514];
-      char *cpy;
-      char *at;
-      size_t off;
-
-      cpy = GNUNET_strdup (s);
-      at = strchr (cpy, '@');
-      if (NULL == at)
+    case GNUNET_GNSRECORD_TYPE_PKEY:
+      if (GNUNET_OK !=
+          GNUNET_CRYPTO_ecdsa_public_key_from_string (s, strlen (s), &pkey))
       {
         GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
-                    _("Unable to parse GNS2DNS record `%s'\n"),
+                    _("Unable to parse PKEY record `%s'\n"),
                     s);
-        GNUNET_free (cpy);
         return GNUNET_SYSERR;
       }
-      *at = '\0';
-      at++;
+      *data = GNUNET_new (struct GNUNET_CRYPTO_EcdsaPublicKey);
+      GNUNET_memcpy (*data, &pkey, sizeof (pkey));
+      *data_size = sizeof (struct GNUNET_CRYPTO_EcdsaPublicKey);
+      return GNUNET_OK;
 
-      off = 0;
-      if ( (GNUNET_OK !=
-            GNUNET_DNSPARSER_builder_add_name (nsbuf,
-                                               sizeof (nsbuf),
-                                               &off,
-                                               cpy)) ||
-           (GNUNET_OK !=
-            GNUNET_DNSPARSER_builder_add_name (nsbuf,
-                                               sizeof (nsbuf),
-                                               &off,
-                                               at)) )
+    case GNUNET_GNSRECORD_TYPE_NICK:
+      *data = GNUNET_strdup (s);
+      *data_size = strlen (s);
+      return GNUNET_OK;
+    case GNUNET_GNSRECORD_TYPE_LEHO:
+      *data = GNUNET_strdup (s);
+      *data_size = strlen (s);
+      return GNUNET_OK;
+    case GNUNET_GNSRECORD_TYPE_GNS2DNS:
       {
-        GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
-                    _("Failed to serialize GNS2DNS record with value `%s'\n"),
-                    s);
+        char nsbuf[514];
+        char *cpy;
+        char *at;
+        size_t off;
+
+        cpy = GNUNET_strdup (s);
+        at = strchr (cpy, '@');
+        if (NULL == at)
+        {
+          GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+                      _("Unable to parse GNS2DNS record `%s'\n"),
+                      s);
+          GNUNET_free (cpy);
+          return GNUNET_SYSERR;
+        }
+        *at = '\0';
+        at++;
+
+        off = 0;
+        if ( (GNUNET_OK !=
+              GNUNET_DNSPARSER_builder_add_name (nsbuf,
+                                                 sizeof (nsbuf),
+                                                 &off,
+                                                 cpy)) ||
+             (GNUNET_OK !=
+              GNUNET_DNSPARSER_builder_add_name (nsbuf,
+                                                 sizeof (nsbuf),
+                                                 &off,
+                                                 at)) )
+        {
+          GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+                      _("Failed to serialize GNS2DNS record with value `%s'\n"),
+                      s);
+          GNUNET_free (cpy);
+          return GNUNET_SYSERR;
+        }
         GNUNET_free (cpy);
-        return GNUNET_SYSERR;
+        *data_size = off;
+        *data = GNUNET_malloc (off);
+        GNUNET_memcpy (*data, nsbuf, off);
+        return GNUNET_OK;
       }
-      GNUNET_free (cpy);
-      *data_size = off;
-      *data = GNUNET_malloc (off);
-      GNUNET_memcpy (*data, nsbuf, off);
-      return GNUNET_OK;
-    }
-  case GNUNET_GNSRECORD_TYPE_VPN:
-    {
-      struct GNUNET_TUN_GnsVpnRecord *vpn;
-      char s_peer[103 + 1];
-      char s_serv[253 + 1];
-      unsigned int proto;
-
-      if (3 != SSCANF (s,
-                       "%u %103s %253s",
-                       &proto, s_peer, s_serv))
+    case GNUNET_GNSRECORD_TYPE_VPN:
       {
-        GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
-                    _("Unable to parse VPN record string `%s'\n"),
-                    s);
-        return GNUNET_SYSERR;
+        struct GNUNET_TUN_GnsVpnRecord *vpn;
+        char s_peer[103 + 1];
+        char s_serv[253 + 1];
+        unsigned int proto;
+
+        if (3 != SSCANF (s,
+                         "%u %103s %253s",
+                         &proto, s_peer, s_serv))
+        {
+          GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+                      _("Unable to parse VPN record string `%s'\n"),
+                      s);
+          return GNUNET_SYSERR;
+        }
+        *data_size = sizeof (struct GNUNET_TUN_GnsVpnRecord) + strlen (s_serv) + 1;
+        *data = vpn = GNUNET_malloc (*data_size);
+        if (GNUNET_OK != GNUNET_CRYPTO_eddsa_public_key_from_string ((char*) s_peer,
+                                                                     strlen (s_peer),
+                                                                     &vpn->peer.public_key))
+        {
+          GNUNET_free (vpn);
+          *data_size = 0;
+          return GNUNET_SYSERR;
+        }
+        vpn->proto = htons ((uint16_t) proto);
+        strcpy ((char*)&vpn[1], s_serv);
+        return GNUNET_OK;
       }
-      *data_size = sizeof (struct GNUNET_TUN_GnsVpnRecord) + strlen (s_serv) + 1;
-      *data = vpn = GNUNET_malloc (*data_size);
-      if (GNUNET_OK != GNUNET_CRYPTO_eddsa_public_key_from_string ((char*) s_peer,
-                                                                   strlen (s_peer),
-                                                                   &vpn->peer.public_key))
+    case GNUNET_GNSRECORD_TYPE_BOX:
       {
-        GNUNET_free (vpn);
-        *data_size = 0;
-        return GNUNET_SYSERR;
+        struct GNUNET_GNSRECORD_BoxRecord *box;
+        size_t rest;
+        unsigned int protocol;
+        unsigned int service;
+        unsigned int record_type;
+        void *bval;
+        size_t bval_size;
+
+        if (3 != SSCANF (s,
+                         "%u %u %u ",
+                         &protocol,
+                         &service,
+                         &record_type))
+        {
+          GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+                      _("Unable to parse BOX record string `%s'\n"),
+                      s);
+          return GNUNET_SYSERR;
+        }
+        rest = snprintf (NULL, 0,
+                         "%u %u %u ",
+                         protocol,
+                         service,
+                         record_type);
+        if (GNUNET_OK !=
+            GNUNET_GNSRECORD_string_to_value (record_type,
+                                              &s[rest],
+                                              &bval,
+                                              &bval_size))
+          return GNUNET_SYSERR;
+        *data_size = sizeof (struct GNUNET_GNSRECORD_BoxRecord) + bval_size;
+        *data = box = GNUNET_malloc (*data_size);
+        box->protocol = htons (protocol);
+        box->service = htons (service);
+        box->record_type = htonl (record_type);
+        GNUNET_memcpy (&box[1],
+                       bval,
+                       bval_size);
+        GNUNET_free (bval);
+        return GNUNET_OK;
       }
-      vpn->proto = htons ((uint16_t) proto);
-      strcpy ((char*)&vpn[1], s_serv);
-      return GNUNET_OK;
-    }
-  case GNUNET_GNSRECORD_TYPE_BOX:
-    {
-      struct GNUNET_GNSRECORD_BoxRecord *box;
-      size_t rest;
-      unsigned int protocol;
-      unsigned int service;
-      unsigned int record_type;
-      void *bval;
-      size_t bval_size;
-
-      if (3 != SSCANF (s,
-                       "%u %u %u ",
-                       &protocol,
-                       &service,
-                       &record_type))
+    case GNUNET_GNSRECORD_TYPE_REVERSE:
       {
-        GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
-                    _("Unable to parse BOX record string `%s'\n"),
-                    s);
-        return GNUNET_SYSERR;
+        struct GNUNET_GNSRECORD_ReverseRecord *rev;
+        char known_by[253 + 1];
+        struct GNUNET_TIME_Absolute expiration;
+
+        /* TODO: From crypto_ecc.c
+         * Why is this not a constant???
+         */
+        size_t enclen = (sizeof (struct GNUNET_CRYPTO_EcdsaPublicKey)) * 8;
+        if (enclen % 5 > 0)
+          enclen += 5 - enclen % 5;
+        enclen /= 5; /* 260/5 = 52 */
+        char pkey_str[enclen + 1];
+
+        if (3 != SSCANF (s,
+                         "%253s %52s %"SCNu64,
+                         known_by,
+                         pkey_str,
+                         &expiration.abs_value_us))
+        {
+          GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+                      _("Unable to parse REVERSE record string `%s'\n"),
+                      s);
+          return GNUNET_SYSERR;
+        }
+        *data_size = sizeof (struct GNUNET_GNSRECORD_ReverseRecord) + strlen (known_by) + 1;
+        *data = rev = GNUNET_malloc (*data_size);
+        GNUNET_CRYPTO_ecdsa_public_key_from_string (pkey_str,
+                                                    strlen (pkey_str),
+                                                    &rev->pkey);
+        rev->expiration = expiration;
+        GNUNET_memcpy (&rev[1],
+                       known_by,
+                       strlen (known_by));
+        return GNUNET_OK;
       }
-      rest = snprintf (NULL, 0,
-                       "%u %u %u ",
-                       protocol,
-                       service,
-                       record_type);
-      if (GNUNET_OK !=
-          GNUNET_GNSRECORD_string_to_value (record_type,
-                                            &s[rest],
-                                            &bval,
-                                            &bval_size))
-        return GNUNET_SYSERR;
-      *data_size = sizeof (struct GNUNET_GNSRECORD_BoxRecord) + bval_size;
-      *data = box = GNUNET_malloc (*data_size);
-      box->protocol = htons (protocol);
-      box->service = htons (service);
-      box->record_type = htonl (record_type);
-      GNUNET_memcpy (&box[1],
-              bval,
-              bval_size);
-      GNUNET_free (bval);
-      return GNUNET_OK;
-    }
-  default:
-    return GNUNET_SYSERR;
+    default:
+      return GNUNET_SYSERR;
   }
 }
 
@@ -329,6 +391,7 @@ static struct {
   { "VPN", GNUNET_GNSRECORD_TYPE_VPN },
   { "GNS2DNS", GNUNET_GNSRECORD_TYPE_GNS2DNS },
   { "BOX", GNUNET_GNSRECORD_TYPE_BOX },
+  { "REVERSE", GNUNET_GNSRECORD_TYPE_REVERSE },
   { NULL, UINT32_MAX }
 };
 
@@ -348,7 +411,7 @@ gns_typename_to_number (void *cls,
 
   i=0;
   while ( (NULL != gns_name_map[i].name) &&
-          (0 != strcasecmp (gns_typename,
+          (0 != strcasecmp (gns_typename,
                             gns_name_map[i].name)) )
     i++;
   return gns_name_map[i].number;
@@ -370,7 +433,7 @@ gns_number_to_typename (void *cls,
 
   i=0;
   while ( (NULL != gns_name_map[i].name) &&
-          (type != gns_name_map[i].number) )
+          (type != gns_name_map[i].number) )
     i++;
   return gns_name_map[i].name;
 }
diff --git a/src/include/gnunet_gns_service.h b/src/include/gnunet_gns_service.h
index 1d74408fc..8a1099444 100644
--- a/src/include/gnunet_gns_service.h
+++ b/src/include/gnunet_gns_service.h
@@ -94,6 +94,16 @@ typedef void (*GNUNET_GNS_LookupResultProcessor) (void *cls,
                                                   uint32_t rd_count,
                                                   const struct GNUNET_GNSRECORD_Data *rd);
 
+/**
+ * Iterator called on obtained result for a GNS lookup.
+ *
+ * @param cls closure
+ * @param rd_count number of records in @a rd
+ * @param rd the records in reply
+ */
+typedef void (*GNUNET_GNS_ReverseLookupResultProcessor) (void *cls,
+                                                  const char* name);
+
 
 /**
  * Options for the GNS lookup.
@@ -146,6 +156,23 @@ GNUNET_GNS_lookup (struct GNUNET_GNS_Handle *handle,
                    GNUNET_GNS_LookupResultProcessor proc,
                    void *proc_cls);
 
+/**
+ * Perform an asynchronous reverse lookup operation on the GNS.
+ *
+ * @param handle handle to the GNS service
+ * @param zone_key zone to find a name for
+ * @param root_key our zone
+ * @param proc processor to call on result
+ * @param proc_cls closure for @a proc
+ * @return handle to the request
+ */
+struct GNUNET_GNS_ReverseLookupRequest*
+GNUNET_GNS_reverse_lookup (struct GNUNET_GNS_Handle *handle,
+                           const struct GNUNET_CRYPTO_EcdsaPublicKey *zone_key,
+                           const struct GNUNET_CRYPTO_EcdsaPublicKey *root_key,
+                           GNUNET_GNS_ReverseLookupResultProcessor proc,
+                           void *proc_cls);
+
 
 /**
  * Cancel pending lookup request
diff --git a/src/include/gnunet_gnsrecord_lib.h b/src/include/gnunet_gnsrecord_lib.h
index b7920cbb8..985ae1f7a 100644
--- a/src/include/gnunet_gnsrecord_lib.h
+++ b/src/include/gnunet_gnsrecord_lib.h
@@ -108,6 +108,10 @@ extern "C"
  */
 #define GNUNET_GNSRECORD_TYPE_ID_TOKEN_METADATA 65546
 
+/**
+ * Record type for reverse lookups
+ */
+#define GNUNET_GNSRECORD_TYPE_REVERSE 65548
 
 /**
  * Flags that can be set for a record.
@@ -286,6 +290,27 @@ struct GNUNET_GNSRECORD_BoxRecord
 
 };
 
+/**
+ * Record type used internally to keep track of reverse mappings into a
+ * namespace.
+ * The record contains data related to PKEY delegations from other namespaces to
+ * the namespace the record belongs to.
+ * It is exclusively found under the label ``+''.
+ */
+struct GNUNET_GNSRECORD_ReverseRecord
+{
+  /**
+   * The public key of the namespace the is delegating to our namespace
+   */
+  struct GNUNET_CRYPTO_EcdsaPublicKey pkey;
+
+  /**
+   * The expiration time of the delegation
+   */
+  struct GNUNET_TIME_Absolute expiration;
+
+  /* followed by the name the delegator uses to refer to our namespace */
+};
 
 GNUNET_NETWORK_STRUCT_END
 
diff --git a/src/include/gnunet_protocols.h b/src/include/gnunet_protocols.h
index f9f6cbd9c..0da6780cb 100644
--- a/src/include/gnunet_protocols.h
+++ b/src/include/gnunet_protocols.h
@@ -1529,6 +1529,16 @@ extern "C"
  */
 #define GNUNET_MESSAGE_TYPE_GNS_LOOKUP_RESULT 501
 
+/**
+ * Reverse lookup
+ */
+#define GNUNET_MESSAGE_TYPE_GNS_REVERSE_LOOKUP 503
+
+/**
+ * Response to reverse lookup
+ */
+#define GNUNET_MESSAGE_TYPE_GNS_REVERSE_LOOKUP_RESULT 504
+
 
 /*******************************************************************************
  * CONSENSUS message types