Merge branch 'ticket17238_029_02-resquash'

Conflicts:
	src/or/rendclient.c
	src/or/rendcommon.c
	src/or/routerparse.c
	src/test/test_dir.c
	src/trunnel/ed25519_cert.h

29 files changed, 4207 insertions, 1076 deletions

diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c
index a0988c6d93..dee103e36a 100644
--- a/src/or/circuitlist.c
+++ b/src/or/circuitlist.c
@@ -64,6 +64,7 @@
 #include "connection_or.h"
 #include "control.h"
 #include "main.h"
+#include "hs_common.h"
 #include "networkstatus.h"
 #include "nodelist.h"
 #include "onion.h"
@@ -1352,9 +1353,11 @@ circuit_get_ready_rend_circ_by_rend_data(const rend_data_t *rend_data)
     if (!circ->marked_for_close &&
         circ->purpose == CIRCUIT_PURPOSE_C_REND_READY) {
       origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
-      if (ocirc->rend_data &&
-          !rend_cmp_service_ids(rend_data->onion_address,
-                                ocirc->rend_data->onion_address) &&
+      if (ocirc->rend_data == NULL) {
+        continue;
+      }
+      if (!rend_cmp_service_ids(rend_data_get_address(rend_data),
+                                rend_data_get_address(ocirc->rend_data)) &&
           tor_memeq(ocirc->rend_data->rend_cookie,
                     rend_data->rend_cookie,
                     REND_COOKIE_LEN))
@@ -1366,13 +1369,14 @@ circuit_get_ready_rend_circ_by_rend_data(const rend_data_t *rend_data)
 }
 
 /** Return the first circuit originating here in global_circuitlist after
- * <b>start</b> whose purpose is <b>purpose</b>, and where
- * <b>digest</b> (if set) matches the rend_pk_digest field. Return NULL if no
- * circuit is found.  If <b>start</b> is NULL, begin at the start of the list.
+ * <b>start</b> whose purpose is <b>purpose</b>, and where <b>digest</b> (if
+ * set) matches the private key digest of the rend data associated with the
+ * circuit. Return NULL if no circuit is found. If <b>start</b> is NULL,
+ * begin at the start of the list.
  */
 origin_circuit_t *
 circuit_get_next_by_pk_and_purpose(origin_circuit_t *start,
-                                   const char *digest, uint8_t purpose)
+                                   const uint8_t *digest, uint8_t purpose)
 {
   int idx;
   smartlist_t *lst = circuit_get_global_list();
@@ -1384,17 +1388,23 @@ circuit_get_next_by_pk_and_purpose(origin_circuit_t *start,
 
   for ( ; idx < smartlist_len(lst); ++idx) {
     circuit_t *circ = smartlist_get(lst, idx);
+    origin_circuit_t *ocirc;
 
     if (circ->marked_for_close)
       continue;
     if (circ->purpose != purpose)
       continue;
+    /* At this point we should be able to get a valid origin circuit because
+     * the origin purpose we are looking for matches this circuit. */
+    if (BUG(!CIRCUIT_PURPOSE_IS_ORIGIN(circ->purpose))) {
+      break;
+    }
+    ocirc = TO_ORIGIN_CIRCUIT(circ);
     if (!digest)
-      return TO_ORIGIN_CIRCUIT(circ);
-    else if (TO_ORIGIN_CIRCUIT(circ)->rend_data &&
-             tor_memeq(TO_ORIGIN_CIRCUIT(circ)->rend_data->rend_pk_digest,
-                     digest, DIGEST_LEN))
-      return TO_ORIGIN_CIRCUIT(circ);
+      return ocirc;
+    if (rend_circuit_pk_digest_eq(ocirc, digest)) {
+      return ocirc;
+    }
   }
   return NULL;
 }
@@ -1882,7 +1892,7 @@ circuit_about_to_free(circuit_t *circ)
     if (orig_reason != END_CIRC_REASON_IP_NOW_REDUNDANT) {
       /* treat this like getting a nack from it */
       log_info(LD_REND, "Failed intro circ %s to %s (awaiting ack). %s",
-          safe_str_client(ocirc->rend_data->onion_address),
+          safe_str_client(rend_data_get_address(ocirc->rend_data)),
           safe_str_client(build_state_get_exit_nickname(ocirc->build_state)),
           timed_out ? "Recording timeout." : "Removing from descriptor.");
       rend_client_report_intro_point_failure(ocirc->build_state->chosen_exit,
@@ -1899,7 +1909,7 @@ circuit_about_to_free(circuit_t *circ)
         log_info(LD_REND, "Failed intro circ %s to %s "
             "(building circuit to intro point). "
             "Marking intro point as possibly unreachable.",
-            safe_str_client(ocirc->rend_data->onion_address),
+            safe_str_client(rend_data_get_address(ocirc->rend_data)),
             safe_str_client(build_state_get_exit_nickname(
                                               ocirc->build_state)));
         rend_client_report_intro_point_failure(ocirc->build_state->chosen_exit,
diff --git a/src/or/circuitlist.h b/src/or/circuitlist.h
index 2707b426ab..2e9ce896cc 100644
--- a/src/or/circuitlist.h
+++ b/src/or/circuitlist.h
@@ -45,7 +45,7 @@ origin_circuit_t *circuit_get_by_global_id(uint32_t id);
 origin_circuit_t *circuit_get_ready_rend_circ_by_rend_data(
   const rend_data_t *rend_data);
 origin_circuit_t *circuit_get_next_by_pk_and_purpose(origin_circuit_t *start,
-                                         const char *digest, uint8_t purpose);
+                                         const uint8_t *digest, uint8_t purpose);
 or_circuit_t *circuit_get_rendezvous(const uint8_t *cookie);
 or_circuit_t *circuit_get_intro_point(const uint8_t *digest);
 void circuit_set_rendezvous_cookie(or_circuit_t *circ, const uint8_t *cookie);
diff --git a/src/or/circuituse.c b/src/or/circuituse.c
index 11d78201f4..1adb6fc887 100644
--- a/src/or/circuituse.c
+++ b/src/or/circuituse.c
@@ -40,6 +40,7 @@
 #include "connection_edge.h"
 #include "control.h"
 #include "entrynodes.h"
+#include "hs_common.h"
 #include "nodelist.h"
 #include "networkstatus.h"
 #include "policies.h"
@@ -172,8 +173,8 @@ circuit_is_acceptable(const origin_circuit_t *origin_circ,
     if ((edge_conn->rend_data && !origin_circ->rend_data) ||
         (!edge_conn->rend_data && origin_circ->rend_data) ||
         (edge_conn->rend_data && origin_circ->rend_data &&
-         rend_cmp_service_ids(edge_conn->rend_data->onion_address,
-                              origin_circ->rend_data->onion_address))) {
+         rend_cmp_service_ids(rend_data_get_address(edge_conn->rend_data),
+                              rend_data_get_address(origin_circ->rend_data)))) {
       /* this circ is not for this conn */
       return 0;
     }
@@ -2036,7 +2037,7 @@ circuit_get_open_circ_or_launch(entry_connection_t *conn,
       if (!extend_info) {
         log_info(LD_REND,
                  "No intro points for '%s': re-fetching service descriptor.",
-                 safe_str_client(rend_data->onion_address));
+                 safe_str_client(rend_data_get_address(rend_data)));
         rend_client_refetch_v2_renddesc(rend_data);
         connection_ap_mark_as_non_pending_circuit(conn);
         ENTRY_TO_CONN(conn)->state = AP_CONN_STATE_RENDDESC_WAIT;
@@ -2044,7 +2045,7 @@ circuit_get_open_circ_or_launch(entry_connection_t *conn,
       }
       log_info(LD_REND,"Chose %s as intro point for '%s'.",
                extend_info_describe(extend_info),
-               safe_str_client(rend_data->onion_address));
+               safe_str_client(rend_data_get_address(rend_data)));
     }
 
     /* If we have specified a particular exit node for our
diff --git a/src/or/connection.c b/src/or/connection.c
index 49cb78e389..2e3df34a5a 100644
--- a/src/or/connection.c
+++ b/src/or/connection.c
@@ -82,6 +82,7 @@
 #include "ext_orport.h"
 #include "geoip.h"
 #include "main.h"
+#include "hs_common.h"
 #include "nodelist.h"
 #include "policies.h"
 #include "reasons.h"
@@ -4126,12 +4127,12 @@ connection_get_by_type_state_rendquery(int type, int state,
          (type == CONN_TYPE_DIR &&
           TO_DIR_CONN(conn)->rend_data &&
           !rend_cmp_service_ids(rendquery,
-                                TO_DIR_CONN(conn)->rend_data->onion_address))
+                    rend_data_get_address(TO_DIR_CONN(conn)->rend_data)))
          ||
               (CONN_IS_EDGE(conn) &&
                TO_EDGE_CONN(conn)->rend_data &&
                !rend_cmp_service_ids(rendquery,
-                            TO_EDGE_CONN(conn)->rend_data->onion_address))
+                    rend_data_get_address(TO_EDGE_CONN(conn)->rend_data)))
          ));
 }
 
diff --git a/src/or/connection_edge.c b/src/or/connection_edge.c
index 0c18de0089..875c911f01 100644
--- a/src/or/connection_edge.c
+++ b/src/or/connection_edge.c
@@ -75,6 +75,7 @@
 #include "directory.h"
 #include "dirserv.h"
 #include "hibernate.h"
+#include "hs_common.h"
 #include "main.h"
 #include "nodelist.h"
 #include "policies.h"
@@ -1861,21 +1862,22 @@ connection_ap_handshake_rewrite_and_attach(entry_connection_t *conn,
     if (rend_data == NULL) {
       return -1;
     }
+    const char *onion_address = rend_data_get_address(rend_data);
     log_info(LD_REND,"Got a hidden service request for ID '%s'",
-             safe_str_client(rend_data->onion_address));
+             safe_str_client(onion_address));
 
     /* Lookup the given onion address. If invalid, stop right now.
      * Otherwise, we might have it in the cache or not. */
     unsigned int refetch_desc = 0;
     rend_cache_entry_t *entry = NULL;
     const int rend_cache_lookup_result =
-      rend_cache_lookup_entry(rend_data->onion_address, -1, &entry);
+      rend_cache_lookup_entry(onion_address, -1, &entry);
     if (rend_cache_lookup_result < 0) {
       switch (-rend_cache_lookup_result) {
       case EINVAL:
         /* We should already have rejected this address! */
         log_warn(LD_BUG,"Invalid service name '%s'",
-            safe_str_client(rend_data->onion_address));
+                 safe_str_client(onion_address));
         connection_mark_unattached_ap(conn, END_STREAM_REASON_TORPROTOCOL);
         return -1;
       case ENOENT:
@@ -1901,7 +1903,7 @@ connection_ap_handshake_rewrite_and_attach(entry_connection_t *conn,
       connection_ap_mark_as_non_pending_circuit(conn);
       base_conn->state = AP_CONN_STATE_RENDDESC_WAIT;
       log_info(LD_REND, "Unknown descriptor %s. Fetching.",
-          safe_str_client(rend_data->onion_address));
+               safe_str_client(onion_address));
       rend_client_refetch_v2_renddesc(rend_data);
       return 0;
     }
diff --git a/src/or/control.c b/src/or/control.c
index 6e45fe99e9..96cc41bc4b 100644
--- a/src/or/control.c
+++ b/src/or/control.c
@@ -57,6 +57,7 @@
 #include "entrynodes.h"
 #include "geoip.h"
 #include "hibernate.h"
+#include "hs_common.h"
 #include "main.h"
 #include "networkstatus.h"
 #include "nodelist.h"
@@ -2539,7 +2540,7 @@ circuit_describe_status_for_controller(origin_circuit_t *circ)
 
   if (circ->rend_data != NULL) {
     smartlist_add_asprintf(descparts, "REND_QUERY=%s",
-                 circ->rend_data->onion_address);
+                           rend_data_get_address(circ->rend_data));
   }
 
   {
@@ -6856,8 +6857,10 @@ control_event_hs_descriptor_requested(const rend_data_t *rend_query,
 
   send_control_event(EVENT_HS_DESC,
                      "650 HS_DESC REQUESTED %s %s %s %s\r\n",
-                     rend_hsaddress_str_or_unknown(rend_query->onion_address),
-                     rend_auth_type_to_string(rend_query->auth_type),
+                     rend_hsaddress_str_or_unknown(
+                          rend_data_get_address(rend_query)),
+                     rend_auth_type_to_string(
+                          TO_REND_DATA_V2(rend_query)->auth_type),
                      node_describe_longname_by_id(id_digest),
                      desc_id_base32);
 }
@@ -6873,11 +6876,12 @@ get_desc_id_from_query(const rend_data_t *rend_data, const char *hsdir_fp)
 {
   int replica;
   const char *desc_id = NULL;
+  const rend_data_v2_t *rend_data_v2 = TO_REND_DATA_V2(rend_data);
 
   /* Possible if the fetch was done using a descriptor ID. This means that
    * the HSFETCH command was used. */
-  if (!tor_digest_is_zero(rend_data->desc_id_fetch)) {
-    desc_id = rend_data->desc_id_fetch;
+  if (!tor_digest_is_zero(rend_data_v2->desc_id_fetch)) {
+    desc_id = rend_data_v2->desc_id_fetch;
     goto end;
   }
 
@@ -6885,7 +6889,7 @@ get_desc_id_from_query(const rend_data_t *rend_data, const char *hsdir_fp)
    * is the one associated with the HSDir fingerprint. */
   for (replica = 0; replica < REND_NUMBER_OF_NON_CONSECUTIVE_REPLICAS;
        replica++) {
-    const char *digest = rend_data->descriptor_id[replica];
+    const char *digest = rend_data_get_desc_id(rend_data, replica, NULL);
 
     SMARTLIST_FOREACH_BEGIN(rend_data->hsdirs_fp, char *, fingerprint) {
       if (tor_memcmp(fingerprint, hsdir_fp, DIGEST_LEN) == 0) {
@@ -6994,7 +6998,8 @@ control_event_hs_descriptor_receive_end(const char *action,
                      "650 HS_DESC %s %s %s %s%s%s\r\n",
                      action,
                      rend_hsaddress_str_or_unknown(onion_address),
-                     rend_auth_type_to_string(rend_data->auth_type),
+                     rend_auth_type_to_string(
+                          TO_REND_DATA_V2(rend_data)->auth_type),
                      node_describe_longname_by_id(id_digest),
                      desc_id_field ? desc_id_field : "",
                      reason_field ? reason_field : "");
@@ -7091,7 +7096,7 @@ control_event_hs_descriptor_failed(const rend_data_t *rend_data,
     return;
   }
   control_event_hs_descriptor_receive_end("FAILED",
-                                          rend_data->onion_address,
+                                          rend_data_get_address(rend_data),
                                           rend_data, id_digest, reason);
 }
 
diff --git a/src/or/directory.c b/src/or/directory.c
index fdfb3391a8..ba6d38c426 100644
--- a/src/or/directory.c
+++ b/src/or/directory.c
@@ -3,6 +3,8 @@
  * Copyright (c) 2007-2016, The Tor Project, Inc. */
 /* See LICENSE for licensing information */
 
+#define DIRECTORY_PRIVATE
+
 #include "or.h"
 #include "backtrace.h"
 #include "buffers.h"
@@ -16,6 +18,8 @@
 #include "dirvote.h"
 #include "entrynodes.h"
 #include "geoip.h"
+#include "hs_cache.h"
+#include "hs_common.h"
 #include "main.h"
 #include "microdesc.h"
 #include "networkstatus.h"
@@ -2385,10 +2389,10 @@ connection_dir_client_reached_eof(dir_connection_t *conn)
                                          conn->identity_digest, \
                                          reason) )
     #define SEND_HS_DESC_FAILED_CONTENT() ( \
-      control_event_hs_descriptor_content(conn->rend_data->onion_address, \
-                                          conn->requested_resource, \
-                                          conn->identity_digest, \
-                                          NULL) )
+  control_event_hs_descriptor_content(rend_data_get_address(conn->rend_data), \
+                                      conn->requested_resource,         \
+                                      conn->identity_digest,            \
+                                      NULL) )
     tor_assert(conn->rend_data);
     log_info(LD_REND,"Received rendezvous descriptor (size %d, status %d "
              "(%s))",
@@ -2461,7 +2465,7 @@ connection_dir_client_reached_eof(dir_connection_t *conn)
     #define SEND_HS_DESC_UPLOAD_FAILED_EVENT(reason) ( \
       control_event_hs_descriptor_upload_failed( \
         conn->identity_digest, \
-        conn->rend_data->onion_address, \
+        rend_data_get_address(conn->rend_data), \
         reason) )
     log_info(LD_REND,"Uploaded rendezvous descriptor (status %d "
              "(%s))",
@@ -2475,7 +2479,7 @@ connection_dir_client_reached_eof(dir_connection_t *conn)
                  "Uploading rendezvous descriptor: finished with status "
                  "200 (%s)", escaped(reason));
         control_event_hs_descriptor_uploaded(conn->identity_digest,
-                                             conn->rend_data->onion_address);
+                                    rend_data_get_address(conn->rend_data));
         rend_service_desc_has_uploaded(conn->rend_data);
         break;
       case 400:
@@ -2586,7 +2590,8 @@ connection_dir_about_to_close(dir_connection_t *dir_conn)
    * refetching is unnecessary.) */
   if (conn->purpose == DIR_PURPOSE_FETCH_RENDDESC_V2 &&
       dir_conn->rend_data &&
-      strlen(dir_conn->rend_data->onion_address) == REND_SERVICE_ID_LEN_BASE32)
+      strlen(rend_data_get_address(dir_conn->rend_data)) ==
+             REND_SERVICE_ID_LEN_BASE32)
     rend_client_refetch_v2_renddesc(dir_conn->rend_data);
 }
 
@@ -2806,8 +2811,8 @@ static int handle_get_descriptor(dir_connection_t *conn,
                                 const get_handler_args_t *args);
 static int handle_get_keys(dir_connection_t *conn,
                                 const get_handler_args_t *args);
-static int handle_get_rendezvous2(dir_connection_t *conn,
-                                const get_handler_args_t *args);
+static int handle_get_hs_descriptor_v2(dir_connection_t *conn,
+                                       const get_handler_args_t *args);
 static int handle_get_robots(dir_connection_t *conn,
                                 const get_handler_args_t *args);
 static int handle_get_networkstatus_bridges(dir_connection_t *conn,
@@ -2823,7 +2828,8 @@ static const url_table_ent_t url_table[] = {
   { "/tor/server/", 1, handle_get_descriptor },
   { "/tor/extra/", 1, handle_get_descriptor },
   { "/tor/keys/", 1, handle_get_keys },
-  { "/tor/rendezvous2/", 1, handle_get_rendezvous2 },
+  { "/tor/rendezvous2/", 1, handle_get_hs_descriptor_v2 },
+  { "/tor/hs/3/", 1, handle_get_hs_descriptor_v3 },
   { "/tor/robots.txt", 0, handle_get_robots },
   { "/tor/networkstatus-bridges", 0, handle_get_networkstatus_bridges },
   { NULL, 0, NULL },
@@ -3391,7 +3397,8 @@ handle_get_keys(dir_connection_t *conn, const get_handler_args_t *args)
 /** Helper function for GET /tor/rendezvous2/
  */
 static int
-handle_get_rendezvous2(dir_connection_t *conn, const get_handler_args_t *args)
+handle_get_hs_descriptor_v2(dir_connection_t *conn,
+                            const get_handler_args_t *args)
 {
   const char *url = args->url;
   if (connection_dir_is_encrypted(conn)) {
@@ -3425,6 +3432,50 @@ handle_get_rendezvous2(dir_connection_t *conn, const get_handler_args_t *args)
   return 0;
 }
 
+/** Helper function for GET /tor/hs/3/<z>. Only for version 3.
+ */
+STATIC int
+handle_get_hs_descriptor_v3(dir_connection_t *conn,
+                            const get_handler_args_t *args)
+{
+  int retval;
+  const char *desc_str = NULL;
+  const char *pubkey_str = NULL;
+  const char *url = args->url;
+
+  /* Don't serve v3 descriptors if next gen onion service is disabled. */
+  if (!hs_v3_protocol_is_enabled()) {
+    /* 404 is used for an unrecognized URL so send back the same. */
+    write_http_status_line(conn, 404, "Not found");
+    goto done;
+  }
+
+  /* Reject unencrypted dir connections */
+  if (!connection_dir_is_encrypted(conn)) {
+    write_http_status_line(conn, 404, "Not found");
+    goto done;
+  }
+
+  /* After the path prefix follows the base64 encoded blinded pubkey which we
+   * use to get the descriptor from the cache. Skip the prefix and get the
+   * pubkey. */
+  tor_assert(!strcmpstart(url, "/tor/hs/3/"));
+  pubkey_str = url + strlen("/tor/hs/3/");
+  retval = hs_cache_lookup_as_dir(HS_VERSION_THREE,
+                                  pubkey_str, &desc_str);
+  if (retval < 0) {
+    write_http_status_line(conn, 404, "Not found");
+    goto done;
+  }
+
+  /* Found requested descriptor! Pass it to this nice client. */
+  write_http_response_header(conn, strlen(desc_str), 0, 0);
+  connection_write_to_buf(desc_str, strlen(desc_str), TO_CONN(conn));
+
+ done:
+  return 0;
+}
+
 /** Helper function for GET /tor/networkstatus-bridges
  */
 static int
@@ -3480,6 +3531,90 @@ handle_get_robots(dir_connection_t *conn, const get_handler_args_t *args)
   return 0;
 }
 
+/* Given the <b>url</b> from a POST request, try to extract the version number
+ * using the provided <b>prefix</b>. The version should be after the prefix and
+ * ending with the seperator "/". For instance:
+ *      /tor/hs/3/publish
+ *
+ * On success, <b>end_pos</b> points to the position right after the version
+ * was found. On error, it is set to NULL.
+ *
+ * Return version on success else negative value. */
+STATIC int
+parse_hs_version_from_post(const char *url, const char *prefix,
+                           const char **end_pos)
+{
+  int ok;
+  unsigned long version;
+  const char *start;
+  char *end = NULL;
+
+  tor_assert(url);
+  tor_assert(prefix);
+  tor_assert(end_pos);
+
+  /* Check if the prefix does start the url. */
+  if (strcmpstart(url, prefix)) {
+    goto err;
+  }
+  /* Move pointer to the end of the prefix string. */
+  start = url + strlen(prefix);
+  /* Try this to be the HS version and if we are still at the separator, next
+   * will be move to the right value. */
+  version = tor_parse_long(start, 10, 0, INT_MAX, &ok, &end);
+  if (!ok) {
+    goto err;
+  }
+
+  *end_pos = end;
+  return (int) version;
+ err:
+  *end_pos = NULL;
+  return -1;
+}
+
+/* Handle the POST request for a hidden service descripror. The request is in
+ * <b>url</b>, the body of the request is in <b>body</b>. Return 200 on success
+ * else return 400 indicating a bad request. */
+STATIC int
+handle_post_hs_descriptor(const char *url, const char *body)
+{
+  int version;
+  const char *end_pos;
+
+  tor_assert(url);
+  tor_assert(body);
+
+  version = parse_hs_version_from_post(url, "/tor/hs/", &end_pos);
+  if (version < 0) {
+    goto err;
+  }
+
+  /* We have a valid version number, now make sure it's a publish request. Use
+   * the end position just after the version and check for the command. */
+  if (strcmpstart(end_pos, "/publish")) {
+    goto err;
+  }
+
+  switch (version) {
+  case HS_VERSION_THREE:
+    if (hs_cache_store_as_dir(body) < 0) {
+      goto err;
+    }
+    log_info(LD_REND, "Publish request for HS descriptor handled "
+                      "successfully.");
+    break;
+  default:
+    /* Unsupported version, return a bad request. */
+    goto err;
+  }
+
+  return 200;
+ err:
+  /* Bad request. */
+  return 400;
+}
+
 /** Helper function: called when a dirserver gets a complete HTTP POST
  * request.  Look for an uploaded server descriptor or rendezvous
  * service descriptor.  On finding one, process it and write a
@@ -3524,6 +3659,28 @@ directory_handle_command_post(dir_connection_t *conn, const char *headers,
     goto done;
   }
 
+  /* Handle HS descriptor publish request. */
+  /* XXX: This should be disabled with a consensus param until we want to
+   * the prop224 be deployed and thus use. */
+  if (connection_dir_is_encrypted(conn) && !strcmpstart(url, "/tor/hs/")) {
+    const char *msg = "HS descriptor stored successfully.";
+    /* Don't accept v3 and onward publish request if next gen onion service is
+     * disabled. */
+    if (!hs_v3_protocol_is_enabled()) {
+      /* 404 is used for an unrecognized URL so send back the same. */
+      write_http_status_line(conn, 404, "Not found");
+      goto done;
+    }
+
+    /* We most probably have a publish request for an HS descriptor. */
+    int code = handle_post_hs_descriptor(url, body);
+    if (code != 200) {
+      msg = "Invalid HS descriptor. Rejected.";
+    }
+    write_http_status_line(conn, code, msg);
+    goto done;
+  }
+
   if (!authdir_mode(options)) {
     /* we just provide cached directories; we don't want to
      * receive anything. */
diff --git a/src/or/directory.h b/src/or/directory.h
index f1cdd9fcfe..acb7394136 100644
--- a/src/or/directory.h
+++ b/src/or/directory.h
@@ -135,8 +135,16 @@ time_t download_status_get_next_attempt_at(const download_status_t *dls);
 int purpose_needs_anonymity(uint8_t dir_purpose, uint8_t router_purpose,
                             const char *resource);
 
+#ifdef DIRECTORY_PRIVATE
+
+struct get_handler_args_t;
+STATIC int handle_get_hs_descriptor_v3(dir_connection_t *conn,
+                                       const struct get_handler_args_t *args);
+
+#endif
+
 #ifdef TOR_UNIT_TESTS
-/* Used only by directory.c and test_dir.c */
+/* Used only by test_dir.c */
 
 STATIC int parse_http_url(const char *headers, char **url);
 STATIC dirinfo_type_t dir_fetch_type(int dir_purpose, int router_purpose,
@@ -150,6 +158,8 @@ STATIC int download_status_schedule_get_delay(download_status_t *dls,
                                               int min_delay, int max_delay,
                                               time_t now);
 
+STATIC int handle_post_hs_descriptor(const char *url, const char *body);
+
 STATIC char* authdir_type_to_string(dirinfo_type_t auth);
 STATIC const char * dir_conn_purpose_to_string(int purpose);
 STATIC int should_use_directory_guards(const or_options_t *options);
@@ -161,6 +171,9 @@ STATIC void find_dl_min_and_max_delay(download_status_t *dls,
                                       int *min, int *max);
 STATIC int next_random_exponential_delay(int delay, int max_delay);
 
+STATIC int parse_hs_version_from_post(const char *url, const char *prefix,
+                                      const char **end_pos);
+
 #endif
 
 #endif
diff --git a/src/or/hs_cache.c b/src/or/hs_cache.c
new file mode 100644
index 0000000000..868f936422
--- /dev/null
+++ b/src/or/hs_cache.c
@@ -0,0 +1,384 @@
+/* Copyright (c) 2016, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file hs_cache.c
+ * \brief Handle hidden service descriptor caches.
+ **/
+
+/* For unit tests.*/
+#define HS_CACHE_PRIVATE
+
+#include "hs_cache.h"
+
+#include "or.h"
+#include "config.h"
+#include "hs_common.h"
+#include "hs_descriptor.h"
+#include "rendcache.h"
+
+/* Directory descriptor cache. Map indexed by blinded key. */
+static digest256map_t *hs_cache_v3_dir;
+
+/* Remove a given descriptor from our cache. */
+static void
+remove_v3_desc_as_dir(const hs_cache_dir_descriptor_t *desc)
+{
+  tor_assert(desc);
+  digest256map_remove(hs_cache_v3_dir, desc->key);
+}
+
+/* Store a given descriptor in our cache. */
+static void
+store_v3_desc_as_dir(hs_cache_dir_descriptor_t *desc)
+{
+  tor_assert(desc);
+  digest256map_set(hs_cache_v3_dir, desc->key, desc);
+}
+
+/* Query our cache and return the entry or NULL if not found. */
+static hs_cache_dir_descriptor_t *
+lookup_v3_desc_as_dir(const uint8_t *key)
+{
+  tor_assert(key);
+  return digest256map_get(hs_cache_v3_dir, key);
+}
+
+/* Free a directory descriptor object. */
+static void
+cache_dir_desc_free(hs_cache_dir_descriptor_t *desc)
+{
+  if (desc == NULL) {
+    return;
+  }
+  hs_desc_plaintext_data_free(desc->plaintext_data);
+  tor_free(desc->encoded_desc);
+  tor_free(desc);
+}
+
+/* Helper function: Use by the free all function using the digest256map
+ * interface to cache entries. */
+static void
+cache_dir_desc_free_(void *ptr)
+{
+  hs_cache_dir_descriptor_t *desc = ptr;
+  cache_dir_desc_free(desc);
+}
+
+/* Create a new directory cache descriptor object from a encoded descriptor.
+ * On success, return the heap-allocated cache object, otherwise return NULL if
+ * we can't decode the descriptor. */
+static hs_cache_dir_descriptor_t *
+cache_dir_desc_new(const char *desc)
+{
+  hs_cache_dir_descriptor_t *dir_desc;
+
+  tor_assert(desc);
+
+  dir_desc = tor_malloc_zero(sizeof(hs_cache_dir_descriptor_t));
+  dir_desc->plaintext_data =
+    tor_malloc_zero(sizeof(hs_desc_plaintext_data_t));
+  dir_desc->encoded_desc = tor_strdup(desc);
+
+  if (hs_desc_decode_plaintext(desc, dir_desc->plaintext_data) < 0) {
+    log_debug(LD_DIR, "Unable to decode descriptor. Rejecting.");
+    goto err;
+  }
+
+  /* The blinded pubkey is the indexed key. */
+  dir_desc->key = dir_desc->plaintext_data->blinded_kp.pubkey.pubkey;
+  dir_desc->created_ts = time(NULL);
+  return dir_desc;
+
+ err:
+  cache_dir_desc_free(dir_desc);
+  return NULL;
+}
+
+/* Return the size of a cache entry in bytes. */
+static size_t
+cache_get_entry_size(const hs_cache_dir_descriptor_t *entry)
+{
+  return (sizeof(*entry) + hs_desc_plaintext_obj_size(entry->plaintext_data)
+          + strlen(entry->encoded_desc));
+}
+
+/* Try to store a valid version 3 descriptor in the directory cache. Return 0
+ * on success else a negative value is returned indicating that we have a
+ * newer version in our cache. On error, caller is responsible to free the
+ * given descriptor desc. */
+static int
+cache_store_v3_as_dir(hs_cache_dir_descriptor_t *desc)
+{
+  hs_cache_dir_descriptor_t *cache_entry;
+
+  tor_assert(desc);
+
+  /* Verify if we have an entry in the cache for that key and if yes, check
+   * if we should replace it? */
+  cache_entry = lookup_v3_desc_as_dir(desc->key);
+  if (cache_entry != NULL) {
+    /* Only replace descriptor if revision-counter is greater than the one
+     * in our cache */
+    if (cache_entry->plaintext_data->revision_counter >=
+        desc->plaintext_data->revision_counter) {
+      log_info(LD_REND, "Descriptor revision counter in our cache is "
+                        "greater or equal than the one we received. "
+                        "Rejecting!");
+      goto err;
+    }
+    /* We now know that the descriptor we just received is a new one so
+     * remove the entry we currently have from our cache so we can then
+     * store the new one. */
+    remove_v3_desc_as_dir(cache_entry);
+    cache_dir_desc_free(cache_entry);
+    rend_cache_decrement_allocation(cache_get_entry_size(cache_entry));
+  }
+  /* Store the descriptor we just got. We are sure here that either we
+   * don't have the entry or we have a newer descriptor and the old one
+   * has been removed from the cache. */
+  store_v3_desc_as_dir(desc);
+
+  /* Update our total cache size with this entry for the OOM. This uses the
+   * old HS protocol cache subsystem for which we are tied with. */
+  rend_cache_increment_allocation(cache_get_entry_size(desc));
+
+  /* XXX: Update HS statistics. We should have specific stats for v3. */
+
+  return 0;
+
+ err:
+  return -1;
+}
+
+/* Using the query which is the base64 encoded blinded key of a version 3
+ * descriptor, lookup in our directory cache the entry. If found, 1 is
+ * returned and desc_out is populated with a newly allocated string being the
+ * encoded descriptor. If not found, 0 is returned and desc_out is untouched.
+ * On error, a negative value is returned and desc_out is untouched. */
+static int
+cache_lookup_v3_as_dir(const char *query, const char **desc_out)
+{
+  int found = 0;
+  ed25519_public_key_t blinded_key;
+  const hs_cache_dir_descriptor_t *entry;
+
+  tor_assert(query);
+
+  /* Decode blinded key using the given query value. */
+  if (ed25519_public_from_base64(&blinded_key, query) < 0) {
+    log_info(LD_REND, "Unable to decode the v3 HSDir query %s.",
+             safe_str_client(query));
+    goto err;
+  }
+
+  entry = lookup_v3_desc_as_dir(blinded_key.pubkey);
+  if (entry != NULL) {
+    found = 1;
+    if (desc_out) {
+      *desc_out = entry->encoded_desc;
+    }
+  }
+
+  return found;
+
+ err:
+  return -1;
+}
+
+/* Clean the v3 cache by removing any entry that has expired using the
+ * <b>global_cutoff</b> value. If <b>global_cutoff</b> is 0, the cleaning
+ * process will use the lifetime found in the plaintext data section. Return
+ * the number of bytes cleaned. */
+STATIC size_t
+cache_clean_v3_as_dir(time_t now, time_t global_cutoff)
+{
+  size_t bytes_removed = 0;
+
+  /* Code flow error if this ever happens. */
+  tor_assert(global_cutoff >= 0);
+
+  if (!hs_cache_v3_dir) { /* No cache to clean. Just return. */
+    return 0;
+  }
+
+  DIGEST256MAP_FOREACH_MODIFY(hs_cache_v3_dir, key,
+                              hs_cache_dir_descriptor_t *, entry) {
+    size_t entry_size;
+    time_t cutoff = global_cutoff;
+    if (!cutoff) {
+      /* Cutoff is the lifetime of the entry found in the descriptor. */
+      cutoff = now - entry->plaintext_data->lifetime_sec;
+    }
+
+    /* If the entry has been created _after_ the cutoff, not expired so
+     * continue to the next entry in our v3 cache. */
+    if (entry->created_ts > cutoff) {
+      continue;
+    }
+    /* Here, our entry has expired, remove and free. */
+    MAP_DEL_CURRENT(key);
+    entry_size = cache_get_entry_size(entry);
+    bytes_removed += entry_size;
+    /* Entry is not in the cache anymore, destroy it. */
+    cache_dir_desc_free(entry);
+    /* Update our cache entry allocation size for the OOM. */
+    rend_cache_decrement_allocation(entry_size);
+    /* Logging. */
+    {
+      char key_b64[BASE64_DIGEST256_LEN + 1];
+      base64_encode(key_b64, sizeof(key_b64), (const char *) key,
+                    DIGEST256_LEN, 0);
+      log_info(LD_REND, "Removing v3 descriptor '%s' from HSDir cache",
+               safe_str_client(key_b64));
+    }
+  } DIGEST256MAP_FOREACH_END;
+
+  return bytes_removed;
+}
+
+/* Given an encoded descriptor, store it in the directory cache depending on
+ * which version it is. Return a negative value on error. On success, 0 is
+ * returned. */
+int
+hs_cache_store_as_dir(const char *desc)
+{
+  hs_cache_dir_descriptor_t *dir_desc = NULL;
+
+  tor_assert(desc);
+
+  /* Create a new cache object. This can fail if the descriptor plaintext data
+   * is unparseable which in this case a log message will be triggered. */
+  dir_desc = cache_dir_desc_new(desc);
+  if (dir_desc == NULL) {
+    goto err;
+  }
+
+  /* Call the right function against the descriptor version. At this point,
+   * we are sure that the descriptor's version is supported else the
+   * decoding would have failed. */
+  switch (dir_desc->plaintext_data->version) {
+  case HS_VERSION_THREE:
+  default:
+    if (cache_store_v3_as_dir(dir_desc) < 0) {
+      goto err;
+    }
+    break;
+  }
+  return 0;
+
+ err:
+  cache_dir_desc_free(dir_desc);
+  return -1;
+}
+
+/* Using the query, lookup in our directory cache the entry. If found, 1 is
+ * returned and desc_out is populated with a newly allocated string being
+ * the encoded descriptor. If not found, 0 is returned and desc_out is
+ * untouched. On error, a negative value is returned and desc_out is
+ * untouched. */
+int
+hs_cache_lookup_as_dir(uint32_t version, const char *query,
+                       const char **desc_out)
+{
+  int found;
+
+  tor_assert(query);
+  /* This should never be called with an unsupported version. */
+  tor_assert(hs_desc_is_supported_version(version));
+
+  switch (version) {
+  case HS_VERSION_THREE:
+  default:
+    found = cache_lookup_v3_as_dir(query, desc_out);
+    break;
+  }
+
+  return found;
+}
+
+/* Clean all directory caches using the current time now. */
+void
+hs_cache_clean_as_dir(time_t now)
+{
+  time_t cutoff;
+
+  /* Start with v2 cache cleaning. */
+  cutoff = now - rend_cache_max_entry_lifetime();
+  rend_cache_clean_v2_descs_as_dir(cutoff);
+
+  /* Now, clean the v3 cache. Set the cutoff to 0 telling the cleanup function
+   * to compute the cutoff by itself using the lifetime value. */
+  cache_clean_v3_as_dir(now, 0);
+}
+
+/* Do a round of OOM cleanup on all directory caches. Return the amount of
+ * removed bytes. It is possible that the returned value is lower than
+ * min_remove_bytes if the caches get emptied out so the caller should be
+ * aware of this. */
+size_t
+hs_cache_handle_oom(time_t now, size_t min_remove_bytes)
+{
+  time_t k;
+  size_t bytes_removed = 0;
+
+  /* Our OOM handler called with 0 bytes to remove is a code flow error. */
+  tor_assert(min_remove_bytes != 0);
+
+  /* The algorithm is as follow. K is the oldest expected descriptor age.
+   *
+   *   1) Deallocate all entries from v2 cache that are older than K hours.
+   *      1.1) If the amount of remove bytes has been reached, stop.
+   *   2) Deallocate all entries from v3 cache that are older than K hours
+   *      2.1) If the amount of remove bytes has been reached, stop.
+   *   3) Set K = K - RendPostPeriod and repeat process until K is < 0.
+   *
+   * This ends up being O(Kn).
+   */
+
+  /* Set K to the oldest expected age in seconds which is the maximum
+   * lifetime of a cache entry. We'll use the v2 lifetime because it's much
+   * bigger than the v3 thus leading to cleaning older descriptors. */
+  k = rend_cache_max_entry_lifetime();
+
+  do {
+    time_t cutoff;
+
+    /* If K becomes negative, it means we've empty the caches so stop and
+     * return what we were able to cleanup. */
+    if (k < 0) {
+      break;
+    }
+    /* Compute a cutoff value with K and the current time. */
+    cutoff = now - k;
+
+    /* Start by cleaning the v2 cache with that cutoff. */
+    bytes_removed += rend_cache_clean_v2_descs_as_dir(cutoff);
+
+    if (bytes_removed < min_remove_bytes) {
+      /* We haven't remove enough bytes so clean v3 cache. */
+      bytes_removed += cache_clean_v3_as_dir(now, cutoff);
+      /* Decrement K by a post period to shorten the cutoff. */
+      k -= get_options()->RendPostPeriod;
+    }
+  } while (bytes_removed < min_remove_bytes);
+
+  return bytes_removed;
+}
+
+/* Initialize the hidden service cache subsystem. */
+void
+hs_cache_init(void)
+{
+  /* Calling this twice is very wrong code flow. */
+  tor_assert(!hs_cache_v3_dir);
+  hs_cache_v3_dir = digest256map_new();
+}
+
+/* Cleanup the hidden service cache subsystem. */
+void
+hs_cache_free_all(void)
+{
+  tor_assert(hs_cache_v3_dir);
+  digest256map_free(hs_cache_v3_dir, cache_dir_desc_free_);
+}
diff --git a/src/or/hs_cache.h b/src/or/hs_cache.h
new file mode 100644
index 0000000000..01abb8002f
--- /dev/null
+++ b/src/or/hs_cache.h
@@ -0,0 +1,61 @@
+/* Copyright (c) 2016, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file hs_cache.h
+ * \brief Header file for hs_cache.c
+ **/
+
+#ifndef TOR_HS_CACHE_H
+#define TOR_HS_CACHE_H
+
+#include <stdint.h>
+
+#include "crypto.h"
+#include "crypto_ed25519.h"
+#include "hs_common.h"
+#include "hs_descriptor.h"
+#include "torcert.h"
+
+/* Descriptor representation on the directory side which is a subset of
+ * information that the HSDir can decode and serve it. */
+typedef struct hs_cache_dir_descriptor_t {
+  /* This object is indexed using the blinded pubkey located in the plaintext
+   * data which is populated only once the descriptor has been successfully
+   * decoded and validated. This simply points to that pubkey. */
+  const uint8_t *key;
+
+  /* When does this entry has been created. Used to expire entries. */
+  time_t created_ts;
+
+  /* Descriptor plaintext information. Obviously, we can't decrypt the
+   * encrypted part of the descriptor. */
+  hs_desc_plaintext_data_t *plaintext_data;
+
+  /* Encoded descriptor which is basically in text form. It's a NUL terminated
+   * string thus safe to strlen(). */
+  char *encoded_desc;
+} hs_cache_dir_descriptor_t;
+
+/* Public API */
+
+void hs_cache_init(void);
+void hs_cache_free_all(void);
+void hs_cache_clean_as_dir(time_t now);
+size_t hs_cache_handle_oom(time_t now, size_t min_remove_bytes);
+
+/* Store and Lookup function. They are version agnostic that is depending on
+ * the requested version of the descriptor, it will be re-routed to the
+ * right function. */
+int hs_cache_store_as_dir(const char *desc);
+int hs_cache_lookup_as_dir(uint32_t version, const char *query,
+                           const char **desc_out);
+
+#ifdef HS_CACHE_PRIVATE
+
+STATIC size_t cache_clean_v3_as_dir(time_t now, time_t global_cutoff);
+
+#endif /* HS_CACHE_PRIVATE */
+
+#endif /* TOR_HS_CACHE_H */
+
diff --git a/src/or/hs_common.c b/src/or/hs_common.c
new file mode 100644
index 0000000000..448bf5b800
--- /dev/null
+++ b/src/or/hs_common.c
@@ -0,0 +1,280 @@
+/* Copyright (c) 2016, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file hs_common.c
+ * \brief Contains code shared between different HS protocol version as well
+ *        as useful data structures and accessors used by other subsystems.
+ *        The rendcommon.c should only contains code relating to the v2
+ *        protocol.
+ **/
+
+#include "or.h"
+
+#include "config.h"
+#include "networkstatus.h"
+#include "hs_common.h"
+#include "rendcommon.h"
+
+/* Create a new rend_data_t for a specific given <b>version</b>.
+ * Return a pointer to the newly allocated data structure. */
+static rend_data_t *
+rend_data_alloc(uint32_t version)
+{
+  rend_data_t *rend_data = NULL;
+
+  switch (version) {
+  case HS_VERSION_TWO:
+  {
+    rend_data_v2_t *v2 = tor_malloc_zero(sizeof(*v2));
+    v2->base_.version = HS_VERSION_TWO;
+    v2->base_.hsdirs_fp = smartlist_new();
+    rend_data = &v2->base_;
+    break;
+  }
+  default:
+    tor_assert(0);
+    break;
+  }
+
+  return rend_data;
+}
+
+/** Free all storage associated with <b>data</b> */
+void
+rend_data_free(rend_data_t *data)
+{
+  if (!data) {
+    return;
+  }
+  /* By using our allocation function, this should always be set. */
+  tor_assert(data->hsdirs_fp);
+  /* Cleanup the HSDir identity digest. */
+  SMARTLIST_FOREACH(data->hsdirs_fp, char *, d, tor_free(d));
+  smartlist_free(data->hsdirs_fp);
+  /* Depending on the version, cleanup. */
+  switch (data->version) {
+  case HS_VERSION_TWO:
+  {
+    rend_data_v2_t *v2_data = TO_REND_DATA_V2(data);
+    tor_free(v2_data);
+    break;
+  }
+  default:
+    tor_assert(0);
+  }
+}
+
+/* Allocate and return a deep copy of <b>data</b>. */
+rend_data_t *
+rend_data_dup(const rend_data_t *data)
+{
+  rend_data_t *data_dup = NULL;
+  smartlist_t *hsdirs_fp = smartlist_new();
+
+  tor_assert(data);
+  tor_assert(data->hsdirs_fp);
+
+  SMARTLIST_FOREACH(data->hsdirs_fp, char *, fp,
+                    smartlist_add(hsdirs_fp, tor_memdup(fp, DIGEST_LEN)));
+
+  switch (data->version) {
+  case HS_VERSION_TWO:
+  {
+    rend_data_v2_t *v2_data = tor_memdup(TO_REND_DATA_V2(data),
+                                         sizeof(*v2_data));
+    data_dup = &v2_data->base_;
+    data_dup->hsdirs_fp = hsdirs_fp;
+    break;
+  }
+  default:
+    tor_assert(0);
+    break;
+  }
+
+  return data_dup;
+}
+
+/* Compute the descriptor ID for each HS descriptor replica and save them. A
+ * valid onion address must be present in the <b>rend_data</b>.
+ *
+ * Return 0 on success else -1. */
+static int
+compute_desc_id(rend_data_t *rend_data)
+{
+  int ret = 0;
+  unsigned replica;
+  time_t now = time(NULL);
+
+  tor_assert(rend_data);
+
+  switch (rend_data->version) {
+  case HS_VERSION_TWO:
+  {
+    rend_data_v2_t *v2_data = TO_REND_DATA_V2(rend_data);
+    /* Compute descriptor ID for each replicas. */
+    for (replica = 0; replica < ARRAY_LENGTH(v2_data->descriptor_id);
+         replica++) {
+      ret = rend_compute_v2_desc_id(v2_data->descriptor_id[replica],
+                                    v2_data->onion_address,
+                                    v2_data->descriptor_cookie,
+                                    now, replica);
+      if (ret < 0) {
+        goto end;
+      }
+    }
+    break;
+  }
+  default:
+    tor_assert(0);
+  }
+
+ end:
+  return ret;
+}
+
+/* Allocate and initialize a rend_data_t object for a service using the
+ * provided arguments. All arguments are optional (can be NULL), except from
+ * <b>onion_address</b> which MUST be set.
+ *
+ * Return a valid rend_data_t pointer. This only returns a version 2 object of
+ * rend_data_t. */
+rend_data_t *
+rend_data_service_create(const char *onion_address, const char *pk_digest,
+                         const uint8_t *cookie, rend_auth_type_t auth_type)
+{
+  /* Create a rend_data_t object for version 2. */
+  rend_data_t *rend_data = rend_data_alloc(HS_VERSION_TWO);
+  rend_data_v2_t *v2= TO_REND_DATA_V2(rend_data);
+
+  /* We need at least one else the call is wrong. */
+  tor_assert(onion_address != NULL);
+
+  if (pk_digest) {
+    memcpy(v2->rend_pk_digest, pk_digest, sizeof(v2->rend_pk_digest));
+  }
+  if (cookie) {
+    memcpy(rend_data->rend_cookie, cookie, sizeof(rend_data->rend_cookie));
+  }
+
+  strlcpy(v2->onion_address, onion_address, sizeof(v2->onion_address));
+  v2->auth_type = auth_type;
+
+  return rend_data;
+}
+
+/* Allocate and initialize a rend_data_t object for a client request using
+ * the given arguments.  Either an onion address or a descriptor ID is
+ * needed. Both can be given but only the onion address will be used to make
+ * the descriptor fetch.
+ *
+ * Return a valid rend_data_t pointer or NULL on error meaning the
+ * descriptor IDs couldn't be computed from the given data. */
+rend_data_t *
+rend_data_client_create(const char *onion_address, const char *desc_id,
+                        const char *cookie, rend_auth_type_t auth_type)
+{
+  /* Create a rend_data_t object for version 2. */
+  rend_data_t *rend_data = rend_data_alloc(HS_VERSION_TWO);
+  rend_data_v2_t *v2= TO_REND_DATA_V2(rend_data);
+
+  /* We need at least one else the call is wrong. */
+  tor_assert(onion_address != NULL || desc_id != NULL);
+
+  if (cookie) {
+    memcpy(v2->descriptor_cookie, cookie, sizeof(v2->descriptor_cookie));
+  }
+  if (desc_id) {
+    memcpy(v2->desc_id_fetch, desc_id, sizeof(v2->desc_id_fetch));
+  }
+  if (onion_address) {
+    strlcpy(v2->onion_address, onion_address, sizeof(v2->onion_address));
+    if (compute_desc_id(rend_data) < 0) {
+      goto error;
+    }
+  }
+
+  v2->auth_type = auth_type;
+
+  return rend_data;
+
+ error:
+  rend_data_free(rend_data);
+  return NULL;
+}
+
+/* Return the onion address from the rend data. Depending on the version,
+ * the size of the address can vary but it's always NUL terminated. */
+const char *
+rend_data_get_address(const rend_data_t *rend_data)
+{
+  tor_assert(rend_data);
+
+  switch (rend_data->version) {
+  case HS_VERSION_TWO:
+    return TO_REND_DATA_V2(rend_data)->onion_address;
+  default:
+    /* We should always have a supported version. */
+    tor_assert(0);
+  }
+}
+
+/* Return the descriptor ID for a specific replica number from the rend
+ * data. The returned data is a binary digest and depending on the version its
+ * size can vary. The size of the descriptor ID is put in <b>len_out</b> if
+ * non NULL. */
+const char *
+rend_data_get_desc_id(const rend_data_t *rend_data, uint8_t replica,
+                      size_t *len_out)
+{
+  tor_assert(rend_data);
+
+  switch (rend_data->version) {
+  case HS_VERSION_TWO:
+    tor_assert(replica < REND_NUMBER_OF_NON_CONSECUTIVE_REPLICAS);
+    if (len_out) {
+      *len_out = DIGEST_LEN;
+    }
+    return TO_REND_DATA_V2(rend_data)->descriptor_id[replica];
+  default:
+    /* We should always have a supported version. */
+    tor_assert(0);
+  }
+}
+
+/* Return the public key digest using the given <b>rend_data</b>. The size of
+ * the digest is put in <b>len_out</b> (if set) which can differ depending on
+ * the version. */
+const uint8_t *
+rend_data_get_pk_digest(const rend_data_t *rend_data, size_t *len_out)
+{
+  tor_assert(rend_data);
+
+  switch (rend_data->version) {
+  case HS_VERSION_TWO:
+  {
+    const rend_data_v2_t *v2_data = TO_REND_DATA_V2(rend_data);
+    if (len_out) {
+      *len_out = sizeof(v2_data->rend_pk_digest);
+    }
+    return (const uint8_t *) v2_data->rend_pk_digest;
+  }
+  default:
+    /* We should always have a supported version. */
+    tor_assert(0);
+  }
+}
+
+/* Return true iff the Onion Services protocol version 3 is enabled. This only
+ * considers the consensus parameter. If the parameter is not found, the
+ * default is that it's enabled. */
+int
+hs_v3_protocol_is_enabled(void)
+{
+  /* This consensus param controls if the the onion services version 3 is
+   * enabled or not which is the first version of the next generation
+   * (proposal 224). If this option is set to 0, the tor daemon won't support
+   * the protocol as either a relay, directory, service or client. By default,
+   * it's enabled if the parameter is not found. */
+  return networkstatus_get_param(NULL, "EnableOnionServicesV3", 1, 0, 1);
+}
diff --git a/src/or/hs_common.h b/src/or/hs_common.h
new file mode 100644
index 0000000000..2502f35ad4
--- /dev/null
+++ b/src/or/hs_common.h
@@ -0,0 +1,39 @@
+/* Copyright (c) 2016, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file hs_common.h
+ * \brief Header file containing common data for the whole HS subsytem.
+ **/
+
+#ifndef TOR_HS_COMMON_H
+#define TOR_HS_COMMON_H
+
+#include "or.h"
+
+/* Protocol version 2. Use this instead of hardcoding "2" in the code base,
+ * this adds a clearer semantic to the value when used. */
+#define HS_VERSION_TWO 2
+/* Version 3 of the protocol (prop224). */
+#define HS_VERSION_THREE 3
+
+void rend_data_free(rend_data_t *data);
+rend_data_t *rend_data_dup(const rend_data_t *data);
+rend_data_t *rend_data_client_create(const char *onion_address,
+                                     const char *desc_id,
+                                     const char *cookie,
+                                     rend_auth_type_t auth_type);
+rend_data_t *rend_data_service_create(const char *onion_address,
+                                      const char *pk_digest,
+                                      const uint8_t *cookie,
+                                      rend_auth_type_t auth_type);
+const char *rend_data_get_address(const rend_data_t *rend_data);
+const char *rend_data_get_desc_id(const rend_data_t *rend_data,
+                                  uint8_t replica, size_t *len_out);
+const uint8_t *rend_data_get_pk_digest(const rend_data_t *rend_data,
+                                       size_t *len_out);
+
+int hs_v3_protocol_is_enabled(void);
+
+#endif /* TOR_HS_COMMON_H */
+
diff --git a/src/or/hs_descriptor.c b/src/or/hs_descriptor.c
new file mode 100644
index 0000000000..a0ddf272fc
--- /dev/null
+++ b/src/or/hs_descriptor.c
@@ -0,0 +1,1939 @@
+/* Copyright (c) 2016, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file hs_descriptor.c
+ * \brief Handle hidden service descriptor encoding/decoding.
+ **/
+
+/* For unit tests.*/
+#define HS_DESCRIPTOR_PRIVATE
+
+#include "hs_descriptor.h"
+
+#include "or.h"
+#include "ed25519_cert.h" /* Trunnel interface. */
+#include "parsecommon.h"
+#include "rendcache.h"
+
+/* Constant string value used for the descriptor format. */
+#define str_hs_desc "hs-descriptor"
+#define str_desc_cert "descriptor-signing-key-cert"
+#define str_rev_counter "revision-counter"
+#define str_encrypted "encrypted"
+#define str_signature "signature"
+#define str_lifetime "descriptor-lifetime"
+/* Constant string value for the encrypted part of the descriptor. */
+#define str_create2_formats "create2-formats"
+#define str_auth_required "authentication-required"
+#define str_intro_point "introduction-point"
+#define str_ip_auth_key "auth-key"
+#define str_ip_enc_key "enc-key"
+#define str_ip_enc_key_cert "enc-key-certification"
+#define str_intro_point_start "\n" str_intro_point " "
+/* Constant string value for the construction to encrypt the encrypted data
+ * section. */
+#define str_enc_hsdir_data "hsdir-encrypted-data"
+/* Prefix required to compute/verify HS desc signatures */
+#define str_desc_sig_prefix "Tor onion service descriptor sig v3"
+
+/* Authentication supported types. */
+static const struct {
+  hs_desc_auth_type_t type;
+  const char *identifier;
+} auth_types[] = {
+  { HS_DESC_AUTH_PASSWORD, "password" },
+  { HS_DESC_AUTH_ED25519, "ed25519" },
+  /* Indicate end of array. */
+  { 0, NULL }
+};
+
+/* Descriptor ruleset. */
+static token_rule_t hs_desc_v3_token_table[] = {
+  T1_START(str_hs_desc, R_HS_DESCRIPTOR, EQ(1), NO_OBJ),
+  T1(str_lifetime, R3_DESC_LIFETIME, EQ(1), NO_OBJ),
+  T1(str_desc_cert, R3_DESC_SIGNING_CERT, NO_ARGS, NEED_OBJ),
+  T1(str_rev_counter, R3_REVISION_COUNTER, EQ(1), NO_OBJ),
+  T1(str_encrypted, R3_ENCRYPTED, NO_ARGS, NEED_OBJ),
+  T1_END(str_signature, R3_SIGNATURE, EQ(1), NO_OBJ),
+  END_OF_TABLE
+};
+
+/* Descriptor ruleset for the encrypted section. */
+static token_rule_t hs_desc_encrypted_v3_token_table[] = {
+  T1_START(str_create2_formats, R3_CREATE2_FORMATS, CONCAT_ARGS, NO_OBJ),
+  T01(str_auth_required, R3_AUTHENTICATION_REQUIRED, ARGS, NO_OBJ),
+  END_OF_TABLE
+};
+
+/* Descriptor ruleset for the introduction points section. */
+static token_rule_t hs_desc_intro_point_v3_token_table[] = {
+  T1_START(str_intro_point, R3_INTRODUCTION_POINT, EQ(1), NO_OBJ),
+  T1(str_ip_auth_key, R3_INTRO_AUTH_KEY, NO_ARGS, NEED_OBJ),
+  T1(str_ip_enc_key, R3_INTRO_ENC_KEY, ARGS, OBJ_OK),
+  T1_END(str_ip_enc_key_cert, R3_INTRO_ENC_KEY_CERTIFICATION,
+         NO_ARGS, NEED_OBJ),
+  END_OF_TABLE
+};
+
+/* Free a descriptor intro point object. */
+static void
+desc_intro_point_free(hs_desc_intro_point_t *ip)
+{
+  if (!ip) {
+    return;
+  }
+  if (ip->link_specifiers) {
+    SMARTLIST_FOREACH(ip->link_specifiers, hs_desc_link_specifier_t *,
+                      ls, tor_free(ls));
+    smartlist_free(ip->link_specifiers);
+  }
+  tor_cert_free(ip->auth_key_cert);
+  if (ip->enc_key_type == HS_DESC_KEY_TYPE_LEGACY) {
+    crypto_pk_free(ip->enc_key.legacy);
+  }
+  tor_free(ip);
+}
+
+/* Free the content of the plaintext section of a descriptor. */
+static void
+desc_plaintext_data_free_contents(hs_desc_plaintext_data_t *desc)
+{
+  if (!desc) {
+    return;
+  }
+
+  if (desc->encrypted_blob) {
+    tor_free(desc->encrypted_blob);
+  }
+  tor_cert_free(desc->signing_key_cert);
+
+  memwipe(desc, 0, sizeof(*desc));
+}
+
+/* Free the content of the encrypted section of a descriptor. */
+static void
+desc_encrypted_data_free_contents(hs_desc_encrypted_data_t *desc)
+{
+  if (!desc) {
+    return;
+  }
+
+  if (desc->auth_types) {
+    SMARTLIST_FOREACH(desc->auth_types, char *, a, tor_free(a));
+    smartlist_free(desc->auth_types);
+  }
+  if (desc->intro_points) {
+    SMARTLIST_FOREACH(desc->intro_points, hs_desc_intro_point_t *, ip,
+                      desc_intro_point_free(ip));
+    smartlist_free(desc->intro_points);
+  }
+  memwipe(desc, 0, sizeof(*desc));
+}
+
+/* === ENCODING === */
+
+/* Encode the ed25519 certificate <b>cert</b> and put the newly allocated
+ * string in <b>cert_str_out</b>. Return 0 on success else a negative value. */
+STATIC int
+encode_cert(const tor_cert_t *cert, char **cert_str_out)
+{
+  int ret = -1;
+  char *ed_cert_b64 = NULL;
+  size_t ed_cert_b64_len;
+
+  tor_assert(cert);
+  tor_assert(cert_str_out);
+
+  /* Get the encoded size and add the NUL byte. */
+  ed_cert_b64_len = base64_encode_size(cert->encoded_len,
+                                       BASE64_ENCODE_MULTILINE) + 1;
+  ed_cert_b64 = tor_malloc_zero(ed_cert_b64_len);
+
+  /* Base64 encode the encoded certificate. */
+  if (base64_encode(ed_cert_b64, ed_cert_b64_len,
+                    (const char *) cert->encoded, cert->encoded_len,
+                    BASE64_ENCODE_MULTILINE) < 0) {
+    log_err(LD_BUG, "Couldn't base64-encode descriptor signing key cert!");
+    goto err;
+  }
+
+  /* Put everything together in a NUL terminated string. */
+  tor_asprintf(cert_str_out,
+               "-----BEGIN ED25519 CERT-----\n"
+               "%s"
+               "-----END ED25519 CERT-----",
+               ed_cert_b64);
+  /* Success! */
+  ret = 0;
+
+ err:
+  tor_free(ed_cert_b64);
+  return ret;
+}
+
+/* Encode the given link specifier objects into a newly allocated string.
+ * This can't fail so caller can always assume a valid string being
+ * returned. */
+STATIC char *
+encode_link_specifiers(const smartlist_t *specs)
+{
+  char *encoded_b64 = NULL;
+  link_specifier_list_t *lslist = link_specifier_list_new();
+
+  tor_assert(specs);
+  /* No link specifiers is a code flow error, can't happen. */
+  tor_assert(smartlist_len(specs) > 0);
+  tor_assert(smartlist_len(specs) <= UINT8_MAX);
+
+  link_specifier_list_set_n_spec(lslist, smartlist_len(specs));
+
+  SMARTLIST_FOREACH_BEGIN(specs, const hs_desc_link_specifier_t *,
+                          spec) {
+    link_specifier_t *ls = link_specifier_new();
+    link_specifier_set_ls_type(ls, spec->type);
+
+    switch (spec->type) {
+    case LS_IPV4:
+      link_specifier_set_un_ipv4_addr(ls,
+                                      tor_addr_to_ipv4h(&spec->u.ap.addr));
+      link_specifier_set_un_ipv4_port(ls, spec->u.ap.port);
+      /* Four bytes IPv4 and two bytes port. */
+      link_specifier_set_ls_len(ls, sizeof(spec->u.ap.addr.addr.in_addr) +
+                                    sizeof(spec->u.ap.port));
+      break;
+    case LS_IPV6:
+    {
+      size_t addr_len = link_specifier_getlen_un_ipv6_addr(ls);
+      const uint8_t *in6_addr = tor_addr_to_in6_addr8(&spec->u.ap.addr);
+      uint8_t *ipv6_array = link_specifier_getarray_un_ipv6_addr(ls);
+      memcpy(ipv6_array, in6_addr, addr_len);
+      link_specifier_set_un_ipv6_port(ls, spec->u.ap.port);
+      /* Sixteen bytes IPv6 and two bytes port. */
+      link_specifier_set_ls_len(ls, addr_len + sizeof(spec->u.ap.port));
+      break;
+    }
+    case LS_LEGACY_ID:
+    {
+      size_t legacy_id_len = link_specifier_getlen_un_legacy_id(ls);
+      uint8_t *legacy_id_array = link_specifier_getarray_un_legacy_id(ls);
+      memcpy(legacy_id_array, spec->u.legacy_id, legacy_id_len);
+      link_specifier_set_ls_len(ls, legacy_id_len);
+      break;
+    }
+    default:
+      tor_assert(0);
+    }
+
+    link_specifier_list_add_spec(lslist, ls);
+  } SMARTLIST_FOREACH_END(spec);
+
+  {
+    uint8_t *encoded;
+    ssize_t encoded_len, encoded_b64_len, ret;
+
+    encoded_len = link_specifier_list_encoded_len(lslist);
+    tor_assert(encoded_len > 0);
+    encoded = tor_malloc_zero(encoded_len);
+    ret = link_specifier_list_encode(encoded, encoded_len, lslist);
+    tor_assert(ret == encoded_len);
+
+    /* Base64 encode our binary format. Add extra NUL byte for the base64
+     * encoded value. */
+    encoded_b64_len = base64_encode_size(encoded_len, 0) + 1;
+    encoded_b64 = tor_malloc_zero(encoded_b64_len);
+    ret = base64_encode(encoded_b64, encoded_b64_len, (const char *) encoded,
+                        encoded_len, 0);
+    tor_assert(ret == (encoded_b64_len - 1));
+    tor_free(encoded);
+  }
+
+  link_specifier_list_free(lslist);
+  return encoded_b64;
+}
+
+/* Encode an introduction point encryption key and return a newly allocated
+ * string with it. On failure, return NULL. */
+static char *
+encode_enc_key(const ed25519_keypair_t *sig_key,
+               const hs_desc_intro_point_t *ip)
+{
+  char *encoded = NULL;
+  time_t now = time(NULL);
+
+  tor_assert(sig_key);
+  tor_assert(ip);
+
+  switch (ip->enc_key_type) {
+  case HS_DESC_KEY_TYPE_LEGACY:
+  {
+    char *key_str, b64_cert[256];
+    ssize_t cert_len;
+    size_t key_str_len;
+    uint8_t *cert_data;
+
+    /* Create cross certification cert. */
+    cert_len = tor_make_rsa_ed25519_crosscert(&sig_key->pubkey,
+                                              ip->enc_key.legacy,
+                                              now + HS_DESC_CERT_LIFETIME,
+                                              &cert_data);
+    if (cert_len < 0) {
+      log_warn(LD_REND, "Unable to create legacy crosscert.");
+      goto err;
+    }
+    /* Encode cross cert. */
+    if (base64_encode(b64_cert, sizeof(b64_cert), (const char *) cert_data,
+                      cert_len, BASE64_ENCODE_MULTILINE) < 0) {
+      log_warn(LD_REND, "Unable to encode legacy crosscert.");
+      goto err;
+    }
+    /* Convert the encryption key to a string. */
+    if (crypto_pk_write_public_key_to_string(ip->enc_key.legacy, &key_str,
+                                             &key_str_len) < 0) {
+      log_warn(LD_REND, "Unable to encode legacy encryption key.");
+      goto err;
+    }
+    tor_asprintf(&encoded,
+                 "%s legacy\n%s"  /* Newline is added by the call above. */
+                 "%s\n"
+                 "-----BEGIN CROSSCERT-----\n"
+                 "%s"
+                 "-----END CROSSCERT-----",
+                 str_ip_enc_key, key_str,
+                 str_ip_enc_key_cert, b64_cert);
+    tor_free(key_str);
+    break;
+  }
+  case HS_DESC_KEY_TYPE_CURVE25519:
+  {
+    int signbit;
+    char *encoded_cert, key_fp_b64[CURVE25519_BASE64_PADDED_LEN + 1];
+    ed25519_keypair_t curve_kp;
+
+    if (ed25519_keypair_from_curve25519_keypair(&curve_kp, &signbit,
+                                                &ip->enc_key.curve25519)) {
+      goto err;
+    }
+    tor_cert_t *cross_cert = tor_cert_create(&curve_kp, CERT_TYPE_CROSS_HS_IP_KEYS,
+                                             &sig_key->pubkey, now,
+                                             HS_DESC_CERT_LIFETIME,
+                                             CERT_FLAG_INCLUDE_SIGNING_KEY);
+    memwipe(&curve_kp, 0, sizeof(curve_kp));
+    if (!cross_cert) {
+      goto err;
+    }
+    if (encode_cert(cross_cert, &encoded_cert)) {
+      goto err;
+    }
+    if (curve25519_public_to_base64(key_fp_b64,
+                                    &ip->enc_key.curve25519.pubkey) < 0) {
+      tor_free(encoded_cert);
+      goto err;
+    }
+    tor_asprintf(&encoded,
+                 "%s ntor %s\n"
+                 "%s\n%s",
+                 str_ip_enc_key, key_fp_b64,
+                 str_ip_enc_key_cert, encoded_cert);
+    tor_free(encoded_cert);
+    break;
+  }
+  default:
+    tor_assert(0);
+  }
+
+ err:
+  return encoded;
+}
+
+/* Encode an introduction point object and return a newly allocated string
+ * with it. On failure, return NULL. */
+static char *
+encode_intro_point(const ed25519_keypair_t *sig_key,
+                   const hs_desc_intro_point_t *ip)
+{
+  char *encoded_ip = NULL;
+  smartlist_t *lines = smartlist_new();
+
+  tor_assert(ip);
+  tor_assert(sig_key);
+
+  /* Encode link specifier. */
+  {
+    char *ls_str = encode_link_specifiers(ip->link_specifiers);
+    smartlist_add_asprintf(lines, "%s %s", str_intro_point, ls_str);
+    tor_free(ls_str);
+  }
+
+  /* Authentication key encoding. */
+  {
+    char *encoded_cert;
+    if (encode_cert(ip->auth_key_cert, &encoded_cert) < 0) {
+      goto err;
+    }
+    smartlist_add_asprintf(lines, "%s\n%s", str_ip_auth_key, encoded_cert);
+    tor_free(encoded_cert);
+  }
+
+  /* Encryption key encoding. */
+  {
+    char *encoded_enc_key = encode_enc_key(sig_key, ip);
+    if (encoded_enc_key == NULL) {
+      goto err;
+    }
+    smartlist_add_asprintf(lines, "%s", encoded_enc_key);
+    tor_free(encoded_enc_key);
+  }
+
+  /* Join them all in one blob of text. */
+  encoded_ip = smartlist_join_strings(lines, "\n", 1, NULL);
+
+ err:
+  SMARTLIST_FOREACH(lines, char *, l, tor_free(l));
+  smartlist_free(lines);
+  return encoded_ip;
+}
+
+/* Using a given decriptor object, build the secret input needed for the
+ * KDF and put it in the dst pointer which is an already allocated buffer
+ * of size dstlen. */
+static void
+build_secret_input(const hs_descriptor_t *desc, uint8_t *dst, size_t dstlen)
+{
+  size_t offset = 0;
+
+  tor_assert(desc);
+  tor_assert(dst);
+  tor_assert(HS_DESC_ENCRYPTED_SECRET_INPUT_LEN <= dstlen);
+
+  /* XXX use the destination length as the memcpy length */
+  /* Copy blinded public key. */
+  memcpy(dst, desc->plaintext_data.blinded_kp.pubkey.pubkey,
+         sizeof(desc->plaintext_data.blinded_kp.pubkey.pubkey));
+  offset += sizeof(desc->plaintext_data.blinded_kp.pubkey.pubkey);
+  /* Copy subcredential. */
+  memcpy(dst + offset, desc->subcredential, sizeof(desc->subcredential));
+  offset += sizeof(desc->subcredential);
+  /* Copy revision counter value. */
+  set_uint64(dst + offset, tor_ntohll(desc->plaintext_data.revision_counter));
+  offset += sizeof(uint64_t);
+  tor_assert(HS_DESC_ENCRYPTED_SECRET_INPUT_LEN == offset);
+}
+
+/* Do the KDF construction and put the resulting data in key_out which is of
+ * key_out_len length. It uses SHAKE-256 as specified in the spec. */
+static void
+build_kdf_key(const hs_descriptor_t *desc,
+              const uint8_t *salt, size_t salt_len,
+              uint8_t *key_out, size_t key_out_len)
+{
+  uint8_t secret_input[HS_DESC_ENCRYPTED_SECRET_INPUT_LEN];
+  crypto_xof_t *xof;
+
+  tor_assert(desc);
+  tor_assert(salt);
+  tor_assert(key_out);
+
+  /* Build the secret input for the KDF computation. */
+  build_secret_input(desc, secret_input, sizeof(secret_input));
+
+  xof = crypto_xof_new();
+  /* Feed our KDF. [SHAKE it like a polaroid picture --Yawning]. */
+  crypto_xof_add_bytes(xof, secret_input, sizeof(secret_input));
+  crypto_xof_add_bytes(xof, salt, salt_len);
+  crypto_xof_add_bytes(xof, (const uint8_t *) str_enc_hsdir_data,
+                       strlen(str_enc_hsdir_data));
+  /* Eat from our KDF. */
+  crypto_xof_squeeze_bytes(xof, key_out, key_out_len);
+  crypto_xof_free(xof);
+  memwipe(secret_input,  0, sizeof(secret_input));
+}
+
+/* Using the given descriptor and salt, run it through our KDF function and
+ * then extract a secret key in key_out, the IV in iv_out and MAC in mac_out.
+ * This function can't fail. */
+static void
+build_secret_key_iv_mac(const hs_descriptor_t *desc,
+                        const uint8_t *salt, size_t salt_len,
+                        uint8_t *key_out, size_t key_len,
+                        uint8_t *iv_out, size_t iv_len,
+                        uint8_t *mac_out, size_t mac_len)
+{
+  size_t offset = 0;
+  uint8_t kdf_key[HS_DESC_ENCRYPTED_KDF_OUTPUT_LEN];
+
+  tor_assert(desc);
+  tor_assert(salt);
+  tor_assert(key_out);
+  tor_assert(iv_out);
+  tor_assert(mac_out);
+
+  build_kdf_key(desc, salt, salt_len, kdf_key, sizeof(kdf_key));
+  /* Copy the bytes we need for both the secret key and IV. */
+  memcpy(key_out, kdf_key, key_len);
+  offset += key_len;
+  memcpy(iv_out, kdf_key + offset, iv_len);
+  offset += iv_len;
+  memcpy(mac_out, kdf_key + offset, mac_len);
+  /* Extra precaution to make sure we are not out of bound. */
+  tor_assert((offset + mac_len) == sizeof(kdf_key));
+  memwipe(kdf_key, 0, sizeof(kdf_key));
+}
+
+/* Using a key, salt and encrypted payload, build a MAC and put it in mac_out.
+ * We use SHA3-256 for the MAC computation.
+ * This function can't fail. */
+static void
+build_mac(const uint8_t *mac_key, size_t mac_key_len,
+          const uint8_t *salt, size_t salt_len,
+          const uint8_t *encrypted, size_t encrypted_len,
+          uint8_t *mac_out, size_t mac_len)
+{
+  crypto_digest_t *digest;
+
+  const uint64_t mac_len_netorder = tor_htonll(mac_key_len);
+  const uint64_t salt_len_netorder = tor_htonll(salt_len);
+
+  tor_assert(mac_key);
+  tor_assert(salt);
+  tor_assert(encrypted);
+  tor_assert(mac_out);
+
+  digest = crypto_digest256_new(DIGEST_SHA3_256);
+  /* As specified in section 2.5 of proposal 224, first add the mac key
+   * then add the salt first and then the encrypted section. */
+
+  crypto_digest_add_bytes(digest, (const char *) &mac_len_netorder, 8);
+  crypto_digest_add_bytes(digest, (const char *) mac_key, mac_key_len);
+  crypto_digest_add_bytes(digest, (const char *) &salt_len_netorder, 8);
+  crypto_digest_add_bytes(digest, (const char *) salt, salt_len);
+  crypto_digest_add_bytes(digest, (const char *) encrypted, encrypted_len);
+  crypto_digest_get_digest(digest, (char *) mac_out, mac_len);
+  crypto_digest_free(digest);
+}
+
+/* Given a source length, return the new size including padding for the
+ * plaintext encryption. */
+static size_t
+compute_padded_plaintext_length(size_t plaintext_len)
+{
+  size_t plaintext_padded_len;
+
+  /* Make sure we won't overflow. */
+  tor_assert(plaintext_len <=
+             (SIZE_T_CEILING - HS_DESC_PLAINTEXT_PADDING_MULTIPLE));
+
+  /* Get the extra length we need to add. For example, if srclen is 234 bytes,
+   * this will expand to (2 * 128) == 256 thus an extra 22 bytes. */
+  plaintext_padded_len = CEIL_DIV(plaintext_len,
+                                  HS_DESC_PLAINTEXT_PADDING_MULTIPLE) *
+                         HS_DESC_PLAINTEXT_PADDING_MULTIPLE;
+  /* Can never be extra careful. Make sure we are _really_ padded. */
+  tor_assert(!(plaintext_padded_len % HS_DESC_PLAINTEXT_PADDING_MULTIPLE));
+  return plaintext_padded_len;
+}
+
+/* Given a buffer, pad it up to the encrypted section padding requirement. Set
+ * the newly allocated string in padded_out and return the length of the
+ * padded buffer. */
+STATIC size_t
+build_plaintext_padding(const char *plaintext, size_t plaintext_len,
+                        uint8_t **padded_out)
+{
+  size_t padded_len;
+  uint8_t *padded;
+
+  tor_assert(plaintext);
+  tor_assert(padded_out);
+
+  /* Allocate the final length including padding. */
+  padded_len = compute_padded_plaintext_length(plaintext_len);
+  tor_assert(padded_len >= plaintext_len);
+  padded = tor_malloc_zero(padded_len);
+
+  memcpy(padded, plaintext, plaintext_len);
+  *padded_out = padded;
+  return padded_len;
+}
+
+/* Using a key, IV and plaintext data of length plaintext_len, create the
+ * encrypted section by encrypting it and setting encrypted_out with the
+ * data. Return size of the encrypted data buffer. */
+static size_t
+build_encrypted(const uint8_t *key, const uint8_t *iv, const char *plaintext,
+                size_t plaintext_len, uint8_t **encrypted_out)
+{
+  size_t encrypted_len;
+  uint8_t *padded_plaintext, *encrypted;
+  crypto_cipher_t *cipher;
+
+  tor_assert(key);
+  tor_assert(iv);
+  tor_assert(plaintext);
+  tor_assert(encrypted_out);
+
+  /* This creates a cipher for AES128. It can't fail. */
+  cipher = crypto_cipher_new_with_iv((const char *) key, (const char *) iv);
+  /* This can't fail. */
+  encrypted_len = build_plaintext_padding(plaintext, plaintext_len,
+                                          &padded_plaintext);
+  /* Extra precautions that we have a valie padding length. */
+  tor_assert(encrypted_len <= HS_DESC_PADDED_PLAINTEXT_MAX_LEN);
+  tor_assert(!(encrypted_len % HS_DESC_PLAINTEXT_PADDING_MULTIPLE));
+  /* We use a stream cipher so the encrypted length will be the same as the
+   * plaintext padded length. */
+  encrypted = tor_malloc_zero(encrypted_len);
+  /* This can't fail. */
+  crypto_cipher_encrypt(cipher, (char *) encrypted,
+                        (const char *) padded_plaintext, encrypted_len);
+  *encrypted_out = encrypted;
+  /* Cleanup. */
+  crypto_cipher_free(cipher);
+  tor_free(padded_plaintext);
+  return encrypted_len;
+}
+
+/* Encrypt the given plaintext buffer and using the descriptor to get the
+ * keys. Set encrypted_out with the encrypted data and return the length of
+ * it. */
+static size_t
+encrypt_descriptor_data(const hs_descriptor_t *desc, const char *plaintext,
+             char **encrypted_out)
+{
+  char *final_blob;
+  size_t encrypted_len, final_blob_len, offset = 0;
+  uint8_t *encrypted;
+  uint8_t salt[HS_DESC_ENCRYPTED_SALT_LEN];
+  uint8_t secret_key[CIPHER_KEY_LEN], secret_iv[CIPHER_IV_LEN];
+  uint8_t mac_key[DIGEST256_LEN], mac[DIGEST256_LEN];
+
+  tor_assert(desc);
+  tor_assert(plaintext);
+  tor_assert(encrypted_out);
+
+  /* Get our salt. The returned bytes are already hashed. */
+  crypto_strongest_rand(salt, sizeof(salt));
+
+  /* KDF construction resulting in a key from which the secret key, IV and MAC
+   * key are extracted which is what we need for the encryption. */
+  build_secret_key_iv_mac(desc, salt, sizeof(salt),
+                          secret_key, sizeof(secret_key),
+                          secret_iv, sizeof(secret_iv),
+                          mac_key, sizeof(mac_key));
+
+  /* Build the encrypted part that is do the actual encryption. */
+  encrypted_len = build_encrypted(secret_key, secret_iv, plaintext,
+                                  strlen(plaintext), &encrypted);
+  memwipe(secret_key, 0, sizeof(secret_key));
+  memwipe(secret_iv, 0, sizeof(secret_iv));
+  /* This construction is specified in section 2.5 of proposal 224. */
+  final_blob_len = sizeof(salt) + encrypted_len + DIGEST256_LEN;
+  final_blob = tor_malloc_zero(final_blob_len);
+
+  /* Build the MAC. */
+  build_mac(mac_key, sizeof(mac_key), salt, sizeof(salt),
+            encrypted, encrypted_len, mac, sizeof(mac));
+  memwipe(mac_key, 0, sizeof(mac_key));
+
+  /* The salt is the first value. */
+  memcpy(final_blob, salt, sizeof(salt));
+  offset = sizeof(salt);
+  /* Second value is the encrypted data. */
+  memcpy(final_blob + offset, encrypted, encrypted_len);
+  offset += encrypted_len;
+  /* Third value is the MAC. */
+  memcpy(final_blob + offset, mac, sizeof(mac));
+  offset += sizeof(mac);
+  /* Cleanup the buffers. */
+  memwipe(salt, 0, sizeof(salt));
+  memwipe(encrypted, 0, encrypted_len);
+  tor_free(encrypted);
+  /* Extra precaution. */
+  tor_assert(offset == final_blob_len);
+
+  *encrypted_out = final_blob;
+  return final_blob_len;
+}
+
+/* Take care of encoding the encrypted data section and then encrypting it
+ * with the descriptor's key. A newly allocated NUL terminated string pointer
+ * containing the encrypted encoded blob is put in encrypted_blob_out. Return
+ * 0 on success else a negative value. */
+static int
+encode_encrypted_data(const hs_descriptor_t *desc,
+                      char **encrypted_blob_out)
+{
+  int ret = -1;
+  char *encoded_str, *encrypted_blob;
+  smartlist_t *lines = smartlist_new();
+
+  tor_assert(desc);
+  tor_assert(encrypted_blob_out);
+
+  /* Build the start of the section prior to the introduction points. */
+  {
+    if (!desc->encrypted_data.create2_ntor) {
+      log_err(LD_BUG, "HS desc doesn't have recognized handshake type.");
+      goto err;
+    }
+    smartlist_add_asprintf(lines, "%s %d\n", str_create2_formats,
+                           ONION_HANDSHAKE_TYPE_NTOR);
+
+    if (desc->encrypted_data.auth_types &&
+        smartlist_len(desc->encrypted_data.auth_types)) {
+      /* Put the authentication-required line. */
+      char *buf = smartlist_join_strings(desc->encrypted_data.auth_types, " ",
+                                         0, NULL);
+      smartlist_add_asprintf(lines, "%s %s\n", str_auth_required, buf);
+      tor_free(buf);
+    }
+  }
+
+  /* Build the introduction point(s) section. */
+  SMARTLIST_FOREACH_BEGIN(desc->encrypted_data.intro_points,
+                          const hs_desc_intro_point_t *, ip) {
+    char *encoded_ip = encode_intro_point(&desc->plaintext_data.signing_kp,
+                                          ip);
+    if (encoded_ip == NULL) {
+      log_err(LD_BUG, "HS desc intro point is malformed.");
+      goto err;
+    }
+    smartlist_add(lines, encoded_ip);
+  } SMARTLIST_FOREACH_END(ip);
+
+  /* Build the entire encrypted data section into one encoded plaintext and
+   * then encrypt it. */
+  encoded_str = smartlist_join_strings(lines, "", 0, NULL);
+
+  /* Encrypt the section into an encrypted blob that we'll base64 encode
+   * before returning it. */
+  {
+    char *enc_b64;
+    ssize_t enc_b64_len, ret_len, enc_len;
+
+    enc_len = encrypt_descriptor_data(desc, encoded_str, &encrypted_blob);
+    tor_free(encoded_str);
+    /* Get the encoded size plus a NUL terminating byte. */
+    enc_b64_len = base64_encode_size(enc_len, BASE64_ENCODE_MULTILINE) + 1;
+    enc_b64 = tor_malloc_zero(enc_b64_len);
+    /* Base64 the encrypted blob before returning it. */
+    ret_len = base64_encode(enc_b64, enc_b64_len, encrypted_blob, enc_len,
+                            BASE64_ENCODE_MULTILINE);
+    /* Return length doesn't count the NUL byte. */
+    tor_assert(ret_len == (enc_b64_len - 1));
+    tor_free(encrypted_blob);
+    *encrypted_blob_out = enc_b64;
+  }
+  /* Success! */
+  ret = 0;
+
+ err:
+  SMARTLIST_FOREACH(lines, char *, l, tor_free(l));
+  smartlist_free(lines);
+  return ret;
+}
+
+/* Encode a v3 HS descriptor. Return 0 on success and set encoded_out to the
+ * newly allocated string of the encoded descriptor. On error, -1 is returned
+ * and encoded_out is untouched. */
+static int
+desc_encode_v3(const hs_descriptor_t *desc, char **encoded_out)
+{
+  int ret = -1;
+  char *encoded_str = NULL;
+  size_t encoded_len;
+  smartlist_t *lines = smartlist_new();
+
+  tor_assert(desc);
+  tor_assert(encoded_out);
+  tor_assert(desc->plaintext_data.version == 3);
+
+  /* Build the non-encrypted values. */
+  {
+    char *encoded_cert;
+    /* Encode certificate then create the first line of the descriptor. */
+    if (desc->plaintext_data.signing_key_cert->cert_type
+        != CERT_TYPE_SIGNING_HS_DESC) {
+      log_err(LD_BUG, "HS descriptor signing key has an unexpected cert type "
+              "(%d)", (int) desc->plaintext_data.signing_key_cert->cert_type);
+      goto err;
+    }
+    if (encode_cert(desc->plaintext_data.signing_key_cert,
+                    &encoded_cert) < 0) {
+      /* The function will print error logs. */
+      goto err;
+    }
+    /* Create the hs descriptor line. */
+    smartlist_add_asprintf(lines, "%s %" PRIu32, str_hs_desc,
+                           desc->plaintext_data.version);
+    /* Add the descriptor lifetime line (in minutes). */
+    smartlist_add_asprintf(lines, "%s %" PRIu32, str_lifetime,
+                           desc->plaintext_data.lifetime_sec / 60);
+    /* Create the descriptor certificate line. */
+    smartlist_add_asprintf(lines, "%s\n%s", str_desc_cert, encoded_cert);
+    tor_free(encoded_cert);
+    /* Create the revision counter line. */
+    smartlist_add_asprintf(lines, "%s %" PRIu64, str_rev_counter,
+                           desc->plaintext_data.revision_counter);
+  }
+
+  /* Build the encrypted data section. */
+  {
+    char *enc_b64_blob;
+    if (encode_encrypted_data(desc, &enc_b64_blob) < 0) {
+      goto err;
+    }
+    smartlist_add_asprintf(lines,
+                           "%s\n"
+                           "-----BEGIN MESSAGE-----\n"
+                           "%s"
+                           "-----END MESSAGE-----",
+                           str_encrypted, enc_b64_blob);
+    tor_free(enc_b64_blob);
+  }
+
+  /* Join all lines in one string so we can generate a signature and append
+   * it to the descriptor. */
+  encoded_str = smartlist_join_strings(lines, "\n", 1, &encoded_len);
+
+  /* Sign all fields of the descriptor with our short term signing key. */
+  {
+    ed25519_signature_t sig;
+    char ed_sig_b64[ED25519_SIG_BASE64_LEN + 1];
+    if (ed25519_sign_prefixed(&sig,
+                              (const uint8_t *) encoded_str, encoded_len,
+                              str_desc_sig_prefix,
+                              &desc->plaintext_data.signing_kp) < 0) {
+      log_warn(LD_BUG, "Can't sign encoded HS descriptor!");
+      tor_free(encoded_str);
+      goto err;
+    }
+    if (ed25519_signature_to_base64(ed_sig_b64, &sig) < 0) {
+      log_warn(LD_BUG, "Can't base64 encode descriptor signature!");
+      tor_free(encoded_str);
+      goto err;
+    }
+    /* Create the signature line. */
+    smartlist_add_asprintf(lines, "%s %s", str_signature, ed_sig_b64);
+  }
+  /* Free previous string that we used so compute the signature. */
+  tor_free(encoded_str);
+  encoded_str = smartlist_join_strings(lines, "\n", 1, NULL);
+  *encoded_out = encoded_str;
+
+  /* XXX: Trigger a control port event. */
+
+  /* Success! */
+  ret = 0;
+
+ err:
+  SMARTLIST_FOREACH(lines, char *, l, tor_free(l));
+  smartlist_free(lines);
+  return ret;
+}
+
+/* === DECODING === */
+
+/* XXX: Stub until this function is upstream. */
+static int
+rsa_ed25519_crosscert_check(const uint8_t *crosscert,
+                            const size_t crosscert_len,
+                            const crypto_pk_t *rsa_id_key,
+                            const ed25519_public_key_t *master_key)
+{
+  (void) crosscert;
+  (void) crosscert_len;
+  (void) rsa_id_key;
+  (void) master_key;
+  return 0;
+}
+
+/* Given an encoded string of the link specifiers, return a newly allocated
+ * list of decoded link specifiers. Return NULL on error. */
+STATIC smartlist_t *
+decode_link_specifiers(const char *encoded)
+{
+  int decoded_len;
+  size_t encoded_len, i;
+  uint8_t *decoded;
+  smartlist_t *results = NULL;
+  link_specifier_list_t *specs = NULL;
+
+  tor_assert(encoded);
+
+  encoded_len = strlen(encoded);
+  decoded = tor_malloc(encoded_len);
+  decoded_len = base64_decode((char *) decoded, encoded_len, encoded,
+                              encoded_len);
+  if (decoded_len < 0) {
+    goto err;
+  }
+
+  if (link_specifier_list_parse(&specs, decoded,
+                                (size_t) decoded_len) < decoded_len) {
+    goto err;
+  }
+  tor_assert(specs);
+  results = smartlist_new();
+
+  for (i = 0; i < link_specifier_list_getlen_spec(specs); i++) {
+    hs_desc_link_specifier_t *hs_spec;
+    link_specifier_t *ls = link_specifier_list_get_spec(specs, i);
+    tor_assert(ls);
+
+    hs_spec = tor_malloc_zero(sizeof(*hs_spec));
+    hs_spec->type = link_specifier_get_ls_type(ls);
+    switch (hs_spec->type) {
+    case LS_IPV4:
+      tor_addr_from_ipv4h(&hs_spec->u.ap.addr,
+                          link_specifier_get_un_ipv4_addr(ls));
+      hs_spec->u.ap.port = link_specifier_get_un_ipv4_port(ls);
+      break;
+    case LS_IPV6:
+      tor_addr_from_ipv6_bytes(&hs_spec->u.ap.addr, (const char *)
+                               link_specifier_getarray_un_ipv6_addr(ls));
+      hs_spec->u.ap.port = link_specifier_get_un_ipv6_port(ls);
+      break;
+    case LS_LEGACY_ID:
+      /* Both are known at compile time so let's make sure they are the same
+       * else we can copy memory out of bound. */
+      tor_assert(link_specifier_getlen_un_legacy_id(ls) ==
+                 sizeof(hs_spec->u.legacy_id));
+      memcpy(hs_spec->u.legacy_id, link_specifier_getarray_un_legacy_id(ls),
+             sizeof(hs_spec->u.legacy_id));
+      break;
+    default:
+      goto err;
+    }
+
+    smartlist_add(results, hs_spec);
+  }
+
+  goto done;
+ err:
+  if (results) {
+    SMARTLIST_FOREACH(results, hs_desc_link_specifier_t *, s, tor_free(s));
+    smartlist_free(results);
+    results = NULL;
+  }
+ done:
+  link_specifier_list_free(specs);
+  tor_free(decoded);
+  return results;
+}
+
+/* Given a list of authentication types, decode it and put it in the encrypted
+ * data section. Return 1 if we at least know one of the type or 0 if we know
+ * none of them. */
+static int
+decode_auth_type(hs_desc_encrypted_data_t *desc, const char *list)
+{
+  int match = 0;
+
+  tor_assert(desc);
+  tor_assert(list);
+
+  desc->auth_types = smartlist_new();
+  smartlist_split_string(desc->auth_types, list, " ", 0, 0);
+
+  /* Validate the types that we at least know about one. */
+  SMARTLIST_FOREACH_BEGIN(desc->auth_types, const char *, auth) {
+    for (int idx = 0; auth_types[idx].identifier; idx++) {
+      if (!strncmp(auth, auth_types[idx].identifier,
+                   strlen(auth_types[idx].identifier))) {
+        match = 1;
+        break;
+      }
+    }
+  } SMARTLIST_FOREACH_END(auth);
+
+  return match;
+}
+
+/* Parse a space-delimited list of integers representing CREATE2 formats into
+ * the bitfield in hs_desc_encrypted_data_t. Ignore unrecognized values. */
+static void
+decode_create2_list(hs_desc_encrypted_data_t *desc, const char *list)
+{
+  smartlist_t *tokens;
+
+  tor_assert(desc);
+  tor_assert(list);
+
+  tokens = smartlist_new();
+  smartlist_split_string(tokens, list, " ", 0, 0);
+
+  SMARTLIST_FOREACH_BEGIN(tokens, char *, s) {
+    int ok;
+    unsigned long type = tor_parse_ulong(s, 10, 1, UINT16_MAX, &ok, NULL);
+    if (!ok) {
+      log_warn(LD_REND, "Unparseable value %s in create2 list", escaped(s));
+      continue;
+    }
+    switch (type) {
+    case ONION_HANDSHAKE_TYPE_NTOR:
+      desc->create2_ntor = 1;
+      break;
+    default:
+      /* We deliberately ignore unsupported handshake types */
+      continue;
+    }
+  } SMARTLIST_FOREACH_END(s);
+
+  SMARTLIST_FOREACH(tokens, char *, s, tor_free(s));
+  smartlist_free(tokens);
+}
+
+/* Given a certificate, validate the certificate for certain conditions which
+ * are if the given type matches the cert's one, if the signing key is
+ * included and if the that key was actually used to sign the certificate.
+ *
+ * Return 1 iff if all conditions pass or 0 if one of them fails. */
+STATIC int
+cert_is_valid(tor_cert_t *cert, uint8_t type, const char *log_obj_type)
+{
+  tor_assert(log_obj_type);
+
+  if (cert == NULL) {
+    log_warn(LD_REND, "Certificate for %s couldn't be parsed.", log_obj_type);
+    goto err;
+  }
+  if (cert->cert_type != type) {
+    log_warn(LD_REND, "Invalid cert type %02x for %s.", cert->cert_type,
+             log_obj_type);
+    goto err;
+  }
+  /* All certificate must have its signing key included. */
+  if (!cert->signing_key_included) {
+    log_warn(LD_REND, "Signing key is NOT included for %s.", log_obj_type);
+    goto err;
+  }
+  /* The following will not only check if the signature matches but also the
+   * expiration date and overall validity. */
+  if (tor_cert_checksig(cert, &cert->signing_key, time(NULL)) < 0) {
+    log_warn(LD_REND, "Invalid signature for %s.", log_obj_type);
+    goto err;
+  }
+
+  return 1;
+ err:
+  return 0;
+}
+
+/* Given some binary data, try to parse it to get a certificate object. If we
+ * have a valid cert, validate it using the given wanted type. On error, print
+ * a log using the err_msg has the certificate identifier adding semantic to
+ * the log and cert_out is set to NULL. On success, 0 is returned and cert_out
+ * points to a newly allocated certificate object. */
+static int
+cert_parse_and_validate(tor_cert_t **cert_out, const char *data,
+                        size_t data_len, unsigned int cert_type_wanted,
+                        const char *err_msg)
+{
+  tor_cert_t *cert;
+
+  tor_assert(cert_out);
+  tor_assert(data);
+  tor_assert(err_msg);
+
+  /* Parse certificate. */
+  cert = tor_cert_parse((const uint8_t *) data, data_len);
+  if (!cert) {
+    log_warn(LD_REND, "Certificate for %s couldn't be parsed.", err_msg);
+    goto err;
+  }
+
+  /* Validate certificate. */
+  if (!cert_is_valid(cert, cert_type_wanted, err_msg)) {
+    goto err;
+  }
+
+  *cert_out = cert;
+  return 0;
+
+ err:
+  tor_cert_free(cert);
+  *cert_out = NULL;
+  return -1;
+}
+
+/* Return true iff the given length of the encrypted data of a descriptor
+ * passes validation. */
+STATIC int
+encrypted_data_length_is_valid(size_t len)
+{
+  /* Check for the minimum length possible. */
+  if (len < HS_DESC_ENCRYPTED_MIN_LEN) {
+    log_warn(LD_REND, "Length of descriptor's encrypted data is too small. "
+                      "Got %lu but minimum value is %d",
+             len, HS_DESC_ENCRYPTED_MIN_LEN);
+    goto err;
+  }
+
+  /* Encrypted data has the salt and MAC concatenated to it so remove those
+   * from the validation calculation. */
+  len -= HS_DESC_ENCRYPTED_SALT_LEN + DIGEST256_LEN;
+
+  /* Check that it's aligned on the block size of the crypto algorithm. */
+  if (len % HS_DESC_PLAINTEXT_PADDING_MULTIPLE) {
+    log_warn(LD_REND, "Length of descriptor's encrypted data is invalid. "
+                      "Got %lu which is not a multiple of %d.",
+             len, HS_DESC_PLAINTEXT_PADDING_MULTIPLE);
+    goto err;
+  }
+
+  /* XXX: Check maximum size. Will strongly depends on the maximum intro point
+   * allowed we decide on and probably if they will all have to use the legacy
+   * key which is bigger than the ed25519 key. */
+
+  return 1;
+ err:
+  return 0;
+}
+
+/* Decrypt the encrypted section of the descriptor using the given descriptor
+ * object desc. A newly allocated NUL terminated string is put in
+ * decrypted_out. Return the length of decrypted_out on success else 0 is
+ * returned and decrypted_out is set to NULL. */
+static size_t
+desc_decrypt_data_v3(const hs_descriptor_t *desc, char **decrypted_out)
+{
+  uint8_t *decrypted = NULL;
+  uint8_t secret_key[CIPHER_KEY_LEN], secret_iv[CIPHER_IV_LEN];
+  uint8_t mac_key[DIGEST256_LEN], our_mac[DIGEST256_LEN];
+  const uint8_t *salt, *encrypted, *desc_mac;
+  size_t encrypted_len, result_len = 0;
+
+  tor_assert(decrypted_out);
+  tor_assert(desc);
+  tor_assert(desc->plaintext_data.encrypted_blob);
+
+  /* Construction is as follow: SALT | ENCRYPTED_DATA | MAC */
+  if (!encrypted_data_length_is_valid(
+                desc->plaintext_data.encrypted_blob_size)) {
+    goto err;
+  }
+
+  /* Start of the blob thus the salt. */
+  salt = desc->plaintext_data.encrypted_blob;
+  /* Next is the encrypted data. */
+  encrypted = desc->plaintext_data.encrypted_blob +
+    HS_DESC_ENCRYPTED_SALT_LEN;
+  encrypted_len = desc->plaintext_data.encrypted_blob_size -
+    (HS_DESC_ENCRYPTED_SALT_LEN + DIGEST256_LEN);
+
+  /* At the very end is the MAC. Make sure it's of the right size. */
+  {
+    desc_mac = encrypted + encrypted_len;
+    size_t desc_mac_size = desc->plaintext_data.encrypted_blob_size -
+                           (desc_mac - desc->plaintext_data.encrypted_blob);
+    if (desc_mac_size != DIGEST256_LEN) {
+      log_warn(LD_REND, "Service descriptor MAC length of encrypted data "
+                        "is invalid (%lu, expected %u)",
+               desc_mac_size, DIGEST256_LEN);
+      goto err;
+    }
+  }
+
+  /* KDF construction resulting in a key from which the secret key, IV and MAC
+   * key are extracted which is what we need for the decryption. */
+  build_secret_key_iv_mac(desc, salt, HS_DESC_ENCRYPTED_SALT_LEN,
+                          secret_key, sizeof(secret_key),
+                          secret_iv, sizeof(secret_iv),
+                          mac_key, sizeof(mac_key));
+
+  /* Build MAC. */
+  build_mac(mac_key, sizeof(mac_key), salt, HS_DESC_ENCRYPTED_SALT_LEN,
+            encrypted, encrypted_len, our_mac, sizeof(our_mac));
+  memwipe(mac_key, 0, sizeof(mac_key));
+  /* Verify MAC; MAC is H(mac_key || salt || encrypted)
+   *
+   * This is a critical check that is making sure the computed MAC matches the
+   * one in the descriptor. */
+  if (!tor_memeq(our_mac, desc_mac, sizeof(our_mac))) {
+    log_warn(LD_REND, "Encrypted service descriptor MAC check failed");
+    goto err;
+  }
+
+  {
+    /* Decrypt. Here we are assured that the encrypted length is valid for
+     * decryption. */
+    crypto_cipher_t *cipher;
+    cipher = crypto_cipher_new_with_iv((const char *) secret_key,
+                                       (const char *) secret_iv);
+    /* Extra byte for the NUL terminated byte. */
+    decrypted = tor_malloc_zero(encrypted_len + 1);
+    crypto_cipher_decrypt(cipher, (char *) decrypted,
+                          (const char *) encrypted, encrypted_len);
+    crypto_cipher_free(cipher);
+  }
+
+  {
+    /* Adjust length to remove NULL padding bytes */
+    uint8_t *end = memchr(decrypted, 0, encrypted_len);
+    result_len = encrypted_len;
+    if (end) {
+      result_len = end - decrypted;
+    }
+  }
+
+  /* Make sure to NUL terminate the string. */
+  decrypted[encrypted_len] = '\0';
+  *decrypted_out = (char *) decrypted;
+  goto done;
+
+ err:
+  if (decrypted) {
+    tor_free(decrypted);
+  }
+  *decrypted_out = NULL;
+  result_len = 0;
+
+ done:
+  memwipe(secret_key, 0, sizeof(secret_key));
+  memwipe(secret_iv, 0, sizeof(secret_iv));
+  return result_len;
+}
+
+/* Given the start of a section and the end of it, decode a single
+ * introduction point from that section. Return a newly allocated introduction
+ * point object containing the decoded data. Return NULL if the section can't
+ * be decoded. */
+STATIC hs_desc_intro_point_t *
+decode_introduction_point(const hs_descriptor_t *desc, const char *start)
+{
+  hs_desc_intro_point_t *ip = NULL;
+  memarea_t *area = NULL;
+  smartlist_t *tokens = NULL;
+  tor_cert_t *cross_cert = NULL;
+  const directory_token_t *tok;
+
+  tor_assert(desc);
+  tor_assert(start);
+
+  area = memarea_new();
+  tokens = smartlist_new();
+  if (tokenize_string(area, start, start + strlen(start),
+                      tokens, hs_desc_intro_point_v3_token_table, 0) < 0) {
+    log_warn(LD_REND, "Introduction point is not parseable");
+    goto err;
+  }
+
+  /* Ok we seem to have a well formed section containing enough tokens to
+   * parse. Allocate our IP object and try to populate it. */
+  ip = tor_malloc_zero(sizeof(hs_desc_intro_point_t));
+
+  /* "introduction-point" SP link-specifiers NL */
+  tok = find_by_keyword(tokens, R3_INTRODUCTION_POINT);
+  tor_assert(tok->n_args == 1);
+  ip->link_specifiers = decode_link_specifiers(tok->args[0]);
+  if (!ip->link_specifiers) {
+    log_warn(LD_REND, "Introduction point has invalid link specifiers");
+    goto err;
+  }
+
+  /* "auth-key" NL certificate NL */
+  tok = find_by_keyword(tokens, R3_INTRO_AUTH_KEY);
+  tor_assert(tok->object_body);
+  if (strcmp(tok->object_type, "ED25519 CERT")) {
+    log_warn(LD_REND, "Unexpected object type for introduction auth key");
+    goto err;
+  }
+
+  /* Parse cert and do some validation. */
+  if (cert_parse_and_validate(&ip->auth_key_cert, tok->object_body,
+                              tok->object_size, CERT_TYPE_AUTH_HS_IP_KEY,
+                              "introduction point auth-key") < 0) {
+    goto err;
+  }
+
+  /* Exactly one "enc-key" ... */
+  tok = find_by_keyword(tokens, R3_INTRO_ENC_KEY);
+  if (!strcmp(tok->args[0], "ntor")) {
+    /* "enc-key" SP "ntor" SP key NL */
+    if (tok->n_args != 2 || tok->object_body) {
+      log_warn(LD_REND, "Introduction point ntor encryption key is invalid");
+      goto err;
+    }
+
+    if (curve25519_public_from_base64(&ip->enc_key.curve25519.pubkey,
+                                      tok->args[1]) < 0) {
+      log_warn(LD_REND, "Introduction point ntor encryption key is invalid");
+      goto err;
+    }
+    ip->enc_key_type = HS_DESC_KEY_TYPE_CURVE25519;
+  } else if (!strcmp(tok->args[0], "legacy")) {
+    /* "enc-key" SP "legacy" NL key NL */
+    if (!tok->key) {
+      log_warn(LD_REND, "Introduction point legacy encryption key is "
+               "invalid");
+      goto err;
+    }
+    ip->enc_key.legacy = crypto_pk_dup_key(tok->key);
+    ip->enc_key_type = HS_DESC_KEY_TYPE_LEGACY;
+  } else {
+    /* Unknown key type so we can't use that introduction point. */
+    log_warn(LD_REND, "Introduction point encryption key is unrecognized.");
+    goto err;
+  }
+
+  /* "enc-key-certification" NL certificate NL */
+  tok = find_by_keyword(tokens, R3_INTRO_ENC_KEY_CERTIFICATION);
+  tor_assert(tok->object_body);
+  /* Do the cross certification. */
+  switch (ip->enc_key_type) {
+  case HS_DESC_KEY_TYPE_CURVE25519:
+  {
+    if (strcmp(tok->object_type, "ED25519 CERT")) {
+      log_warn(LD_REND, "Introduction point ntor encryption key "
+                        "cross-certification has an unknown format.");
+      goto err;
+    }
+    if (cert_parse_and_validate(&cross_cert, tok->object_body,
+                       tok->object_size, CERT_TYPE_CROSS_HS_IP_KEYS,
+                       "introduction point enc-key-certification") < 0) {
+      goto err;
+    }
+    break;
+  }
+  case HS_DESC_KEY_TYPE_LEGACY:
+    if (strcmp(tok->object_type, "CROSSCERT")) {
+      log_warn(LD_REND, "Introduction point legacy encryption key "
+                        "cross-certification has an unknown format.");
+      goto err;
+    }
+    if (rsa_ed25519_crosscert_check((const uint8_t *) tok->object_body,
+          tok->object_size, ip->enc_key.legacy,
+          &desc->plaintext_data.signing_key_cert->signing_key)) {
+      log_warn(LD_REND, "Unable to cross certify the introduction point "
+                        "legacy encryption key.");
+      goto err;
+    }
+    break;
+  default:
+    tor_assert(0);
+    break;
+  }
+  /* It is successfully cross certified. Flag the object. */
+  ip->cross_certified = 1;
+  goto done;
+
+ err:
+  desc_intro_point_free(ip);
+  ip = NULL;
+
+ done:
+  tor_cert_free(cross_cert);
+  SMARTLIST_FOREACH(tokens, directory_token_t *, t, token_clear(t));
+  smartlist_free(tokens);
+  memarea_drop_all(area);
+
+  return ip;
+}
+
+/* Given a descriptor string at <b>data</b>, decode all possible introduction
+ * points that we can find. Add the introduction point object to desc_enc as we
+ * find them. Return 0 on success.
+ *
+ * On error, a negative value is returned. It is possible that some intro
+ * point object have been added to the desc_enc, they should be considered
+ * invalid. One single bad encoded introduction point will make this function
+ * return an error. */
+STATIC int
+decode_intro_points(const hs_descriptor_t *desc,
+                    hs_desc_encrypted_data_t *desc_enc,
+                    const char *data)
+{
+  int retval = -1;
+  smartlist_t *chunked_desc = smartlist_new();
+  smartlist_t *intro_points = smartlist_new();
+
+  tor_assert(desc);
+  tor_assert(desc_enc);
+  tor_assert(data);
+  tor_assert(desc_enc->intro_points);
+
+  /* Take the desc string, and extract the intro point substrings out of it */
+  {
+    /* Split the descriptor string using the intro point header as delimiter */
+    smartlist_split_string(chunked_desc, data, str_intro_point_start, 0, 0);
+
+    /* Check if there are actually any intro points included. The first chunk
+     * should be other descriptor fields (e.g. create2-formats), so it's not an
+     * intro point. */
+    if (smartlist_len(chunked_desc) < 2) {
+      goto done;
+    }
+  }
+
+  /* Take the intro point substrings, and prepare them for parsing */
+  {
+    int i = 0;
+    /* Prepend the introduction-point header to all the chunks, since
+       smartlist_split_string() devoured it. */
+    SMARTLIST_FOREACH_BEGIN(chunked_desc, char *, chunk) {
+      /* Ignore first chunk. It's other descriptor fields. */
+      if (i++ == 0) {
+        continue;
+      }
+
+      smartlist_add_asprintf(intro_points, "%s %s", str_intro_point, chunk);
+    } SMARTLIST_FOREACH_END(chunk);
+  }
+
+  /* Parse the intro points! */
+  SMARTLIST_FOREACH_BEGIN(intro_points, const char *, intro_point) {
+    hs_desc_intro_point_t *ip = decode_introduction_point(desc, intro_point);
+    if (!ip) {
+      /* Malformed introduction point section. Stop right away, this
+       * descriptor shouldn't be used. */
+      goto err;
+    }
+    smartlist_add(desc_enc->intro_points, ip);
+  } SMARTLIST_FOREACH_END(intro_point);
+
+ done:
+  retval = 0;
+
+ err:
+  if (chunked_desc) {
+    SMARTLIST_FOREACH(chunked_desc, char *, a, tor_free(a));
+    smartlist_free(chunked_desc);
+  }
+  if (intro_points) {
+    SMARTLIST_FOREACH(intro_points, char *, a, tor_free(a));
+    smartlist_free(intro_points);
+  }
+
+  return retval;
+}
+/* Return 1 iff the given base64 encoded signature in b64_sig from the encoded
+ * descriptor in encoded_desc validates the descriptor content. */
+STATIC int
+desc_sig_is_valid(const char *b64_sig, const ed25519_keypair_t *signing_kp,
+                  const char *encoded_desc, size_t encoded_len)
+{
+  int ret = 0;
+  ed25519_signature_t sig;
+  const char *sig_start;
+
+  tor_assert(b64_sig);
+  tor_assert(signing_kp);
+  tor_assert(encoded_desc);
+  /* Verifying nothing won't end well :). */
+  tor_assert(encoded_len > 0);
+
+  /* Signature length check. */
+  if (strlen(b64_sig) != ED25519_SIG_BASE64_LEN) {
+    log_warn(LD_REND, "Service descriptor has an invalid signature length."
+                      "Exptected %d but got %lu",
+             ED25519_SIG_BASE64_LEN, strlen(b64_sig));
+    goto err;
+  }
+
+  /* First, convert base64 blob to an ed25519 signature. */
+  if (ed25519_signature_from_base64(&sig, b64_sig) != 0) {
+    log_warn(LD_REND, "Service descriptor does not contain a valid "
+                      "signature");
+    goto err;
+  }
+
+  /* Find the start of signature. */
+  sig_start = tor_memstr(encoded_desc, encoded_len, "\n" str_signature);
+  /* Getting here means the token parsing worked for the signature so if we
+   * can't find the start of the signature, we have a code flow issue. */
+  if (BUG(!sig_start)) {
+    goto err;
+  }
+  /* Skip newline, it has to go in the signature check. */
+  sig_start++;
+
+  /* Validate signature with the full body of the descriptor. */
+  if (ed25519_checksig_prefixed(&sig,
+                                (const uint8_t *) encoded_desc,
+                                sig_start - encoded_desc,
+                                str_desc_sig_prefix,
+                                &signing_kp->pubkey) != 0) {
+    log_warn(LD_REND, "Invalid signature on service descriptor");
+    goto err;
+  }
+  /* Valid signature! All is good. */
+  ret = 1;
+
+ err:
+  return ret;
+}
+
+/* Decode descriptor plaintext data for version 3. Given a list of tokens, an
+ * allocated plaintext object that will be populated and the encoded
+ * descriptor with its length. The last one is needed for signature
+ * verification. Unknown tokens are simply ignored so this won't error on
+ * unknowns but requires that all v3 token be present and valid.
+ *
+ * Return 0 on success else a negative value. */
+static int
+desc_decode_plaintext_v3(smartlist_t *tokens,
+                         hs_desc_plaintext_data_t *desc,
+                         const char *encoded_desc, size_t encoded_len)
+{
+  int ok;
+  directory_token_t *tok;
+
+  tor_assert(tokens);
+  tor_assert(desc);
+  /* Version higher could still use this function to decode most of the
+   * descriptor and then they decode the extra part. */
+  tor_assert(desc->version >= 3);
+
+  /* Descriptor lifetime parsing. */
+  tok = find_by_keyword(tokens, R3_DESC_LIFETIME);
+  tor_assert(tok->n_args == 1);
+  desc->lifetime_sec = (uint32_t) tor_parse_ulong(tok->args[0], 10, 0,
+                                                  UINT32_MAX, &ok, NULL);
+  if (!ok) {
+    log_warn(LD_REND, "Service descriptor lifetime value is invalid");
+    goto err;
+  }
+  /* Put it from minute to second. */
+  desc->lifetime_sec *= 60;
+  if (desc->lifetime_sec > HS_DESC_MAX_LIFETIME) {
+    log_warn(LD_REND, "Service descriptor lifetime is too big. "
+                      "Got %" PRIu32 " but max is %d",
+             desc->lifetime_sec, HS_DESC_MAX_LIFETIME);
+    goto err;
+  }
+
+  /* Descriptor signing certificate. */
+  tok = find_by_keyword(tokens, R3_DESC_SIGNING_CERT);
+  tor_assert(tok->object_body);
+  /* Expecting a prop220 cert with the signing key extension, which contains
+   * the blinded public key. */
+  if (strcmp(tok->object_type, "ED25519 CERT") != 0) {
+    log_warn(LD_REND, "Service descriptor signing cert wrong type (%s)",
+             escaped(tok->object_type));
+    goto err;
+  }
+  if (cert_parse_and_validate(&desc->signing_key_cert, tok->object_body,
+                              tok->object_size, CERT_TYPE_SIGNING_HS_DESC,
+                              "service descriptor signing key") < 0) {
+    goto err;
+  }
+
+  /* Copy the public keys into signing_kp and blinded_kp */
+  memcpy(&desc->signing_kp.pubkey, &desc->signing_key_cert->signed_key,
+         sizeof(ed25519_public_key_t));
+  memcpy(&desc->blinded_kp.pubkey, &desc->signing_key_cert->signing_key,
+         sizeof(ed25519_public_key_t));
+
+  /* Extract revision counter value. */
+  tok = find_by_keyword(tokens, R3_REVISION_COUNTER);
+  tor_assert(tok->n_args == 1);
+  desc->revision_counter = tor_parse_uint64(tok->args[0], 10, 0,
+                                            UINT64_MAX, &ok, NULL);
+  if (!ok) {
+    log_warn(LD_REND, "Service descriptor revision-counter is invalid");
+    goto err;
+  }
+
+  /* Extract the encrypted data section. */
+  tok = find_by_keyword(tokens, R3_ENCRYPTED);
+  tor_assert(tok->object_body);
+  if (strcmp(tok->object_type, "MESSAGE") != 0) {
+    log_warn(LD_REND, "Service descriptor encrypted data section is invalid");
+    goto err;
+  }
+  /* Make sure the length of the encrypted blob is valid. */
+  if (!encrypted_data_length_is_valid(tok->object_size)) {
+    goto err;
+  }
+
+  /* Copy the encrypted blob to the descriptor object so we can handle it
+   * latter if needed. */
+  desc->encrypted_blob = tor_memdup(tok->object_body, tok->object_size);
+  desc->encrypted_blob_size = tok->object_size;
+
+  /* Extract signature and verify it. */
+  tok = find_by_keyword(tokens, R3_SIGNATURE);
+  tor_assert(tok->n_args == 1);
+  /* First arg here is the actual encoded signature. */
+  if (!desc_sig_is_valid(tok->args[0], &desc->signing_kp,
+                         encoded_desc, encoded_len)) {
+    goto err;
+  }
+
+  return 0;
+
+ err:
+  return -1;
+}
+
+/* Decode the version 3 encrypted section of the given descriptor desc. The
+ * desc_encrypted_out will be populated with the decoded data. Return 0 on
+ * success else -1. */
+static int
+desc_decode_encrypted_v3(const hs_descriptor_t *desc,
+                         hs_desc_encrypted_data_t *desc_encrypted_out)
+{
+  int result = -1;
+  char *message = NULL;
+  size_t message_len;
+  memarea_t *area = NULL;
+  directory_token_t *tok;
+  smartlist_t *tokens = NULL;
+
+  tor_assert(desc);
+  tor_assert(desc_encrypted_out);
+
+  /* Decrypt the encrypted data that is located in the plaintext section in
+   * the descriptor as a blob of bytes. The following functions will use the
+   * keys found in the same section. */
+  message_len = desc_decrypt_data_v3(desc, &message);
+  if (!message_len) {
+    log_warn(LD_REND, "Service descriptor decryption failed.");
+    goto err;
+  }
+  tor_assert(message);
+
+  area = memarea_new();
+  tokens = smartlist_new();
+  if (tokenize_string(area, message, message + message_len,
+                      tokens, hs_desc_encrypted_v3_token_table, 0) < 0) {
+    log_warn(LD_REND, "Encrypted service descriptor is not parseable.");
+    goto err;
+  }
+
+  /* CREATE2 supported cell format. It's mandatory. */
+  tok = find_by_keyword(tokens, R3_CREATE2_FORMATS);
+  tor_assert(tok);
+  decode_create2_list(desc_encrypted_out, tok->args[0]);
+  /* Must support ntor according to the specification */
+  if (!desc_encrypted_out->create2_ntor) {
+    log_warn(LD_REND, "Service create2-formats does not include ntor.");
+    goto err;
+  }
+
+  /* Authentication type. It's optional but only once. */
+  tok = find_opt_by_keyword(tokens, R3_AUTHENTICATION_REQUIRED);
+  if (tok) {
+    if (!decode_auth_type(desc_encrypted_out, tok->args[0])) {
+      log_warn(LD_REND, "Service descriptor authentication type has "
+                        "invalid entry(ies).");
+      goto err;
+    }
+  }
+  /* Initialize the descriptor's introduction point list before we start
+   * decoding. Having 0 intro point is valid. Then decode them all. */
+  desc_encrypted_out->intro_points = smartlist_new();
+  if (decode_intro_points(desc, desc_encrypted_out, message) < 0) {
+    goto err;
+  }
+  /* Validation of maximum introduction points allowed. */
+  if (smartlist_len(desc_encrypted_out->intro_points) > MAX_INTRO_POINTS) {
+    log_warn(LD_REND, "Service descriptor contains too many introduction "
+                      "points. Maximum allowed is %d but we have %d",
+             MAX_INTRO_POINTS,
+             smartlist_len(desc_encrypted_out->intro_points));
+    goto err;
+  }
+
+  /* NOTE: Unknown fields are allowed because this function could be used to
+   * decode other descriptor version. */
+
+  result = 0;
+  goto done;
+
+ err:
+  tor_assert(result < 0);
+  desc_encrypted_data_free_contents(desc_encrypted_out);
+
+ done:
+  if (tokens) {
+    SMARTLIST_FOREACH(tokens, directory_token_t *, t, token_clear(t));
+    smartlist_free(tokens);
+  }
+  if (area) {
+    memarea_drop_all(area);
+  }
+  if (message) {
+    tor_free(message);
+  }
+  return result;
+}
+
+/* Table of encrypted decode function version specific. The function are
+ * indexed by the version number so v3 callback is at index 3 in the array. */
+static int
+  (*decode_encrypted_handlers[])(
+      const hs_descriptor_t *desc,
+      hs_desc_encrypted_data_t *desc_encrypted) =
+{
+  /* v0 */ NULL, /* v1 */ NULL, /* v2 */ NULL,
+  desc_decode_encrypted_v3,
+};
+
+/* Decode the encrypted data section of the given descriptor and store the
+ * data in the given encrypted data object. Return 0 on success else a
+ * negative value on error. */
+int
+hs_desc_decode_encrypted(const hs_descriptor_t *desc,
+                         hs_desc_encrypted_data_t *desc_encrypted)
+{
+  int ret;
+  uint32_t version;
+
+  tor_assert(desc);
+  /* Ease our life a bit. */
+  version = desc->plaintext_data.version;
+  tor_assert(desc_encrypted);
+  /* Calling this function without an encrypted blob to parse is a code flow
+   * error. The plaintext parsing should never succeed in the first place
+   * without an encrypted section. */
+  tor_assert(desc->plaintext_data.encrypted_blob);
+  /* Let's make sure we have a supported version as well. By correctly parsing
+   * the plaintext, this should not fail. */
+  if (BUG(!hs_desc_is_supported_version(version))) {
+    ret = -1;
+    goto err;
+  }
+  /* Extra precaution. Having no handler for the supported version should
+   * never happened else we forgot to add it but we bumped the version. */
+  tor_assert(ARRAY_LENGTH(decode_encrypted_handlers) >= version);
+  tor_assert(decode_encrypted_handlers[version]);
+
+  /* Run the version specific plaintext decoder. */
+  ret = decode_encrypted_handlers[version](desc, desc_encrypted);
+  if (ret < 0) {
+    goto err;
+  }
+
+ err:
+  return ret;
+}
+
+/* Table of plaintext decode function version specific. The function are
+ * indexed by the version number so v3 callback is at index 3 in the array. */
+static int
+  (*decode_plaintext_handlers[])(
+      smartlist_t *tokens,
+      hs_desc_plaintext_data_t *desc,
+      const char *encoded_desc,
+      size_t encoded_len) =
+{
+  /* v0 */ NULL, /* v1 */ NULL, /* v2 */ NULL,
+  desc_decode_plaintext_v3,
+};
+
+/* Fully decode the given descriptor plaintext and store the data in the
+ * plaintext data object. Returns 0 on success else a negative value. */
+int
+hs_desc_decode_plaintext(const char *encoded,
+                         hs_desc_plaintext_data_t *plaintext)
+{
+  int ok = 0, ret = -1;
+  memarea_t *area = NULL;
+  smartlist_t *tokens = NULL;
+  size_t encoded_len;
+  directory_token_t *tok;
+
+  tor_assert(encoded);
+  tor_assert(plaintext);
+
+  encoded_len = strlen(encoded);
+  if (encoded_len >= HS_DESC_MAX_LEN) {
+    log_warn(LD_REND, "Service descriptor is too big (%lu bytes)",
+             encoded_len);
+    goto err;
+  }
+
+  area = memarea_new();
+  tokens = smartlist_new();
+  /* Tokenize the descriptor so we can start to parse it. */
+  if (tokenize_string(area, encoded, encoded + encoded_len, tokens,
+                      hs_desc_v3_token_table, 0) < 0) {
+    log_warn(LD_REND, "Service descriptor is not parseable");
+    goto err;
+  }
+
+  /* Get the version of the descriptor which is the first mandatory field of
+   * the descriptor. From there, we'll decode the right descriptor version. */
+  tok = find_by_keyword(tokens, R_HS_DESCRIPTOR);
+  tor_assert(tok->n_args == 1);
+  plaintext->version = (uint32_t) tor_parse_ulong(tok->args[0], 10, 0,
+                                                  UINT32_MAX, &ok, NULL);
+  if (!ok) {
+    log_warn(LD_REND, "Service descriptor has unparseable version %s",
+             escaped(tok->args[0]));
+    goto err;
+  }
+  if (!hs_desc_is_supported_version(plaintext->version)) {
+    log_warn(LD_REND, "Service descriptor has unsupported version %" PRIu32,
+             plaintext->version);
+    goto err;
+  }
+  /* Extra precaution. Having no handler for the supported version should
+   * never happened else we forgot to add it but we bumped the version. */
+  tor_assert(ARRAY_LENGTH(decode_plaintext_handlers) >= plaintext->version);
+  tor_assert(decode_plaintext_handlers[plaintext->version]);
+
+  /* Run the version specific plaintext decoder. */
+  ret = decode_plaintext_handlers[plaintext->version](tokens, plaintext,
+                                                      encoded, encoded_len);
+  if (ret < 0) {
+    goto err;
+  }
+  /* Success. Descriptor has been populated with the data. */
+  ret = 0;
+
+ err:
+  if (tokens) {
+    SMARTLIST_FOREACH(tokens, directory_token_t *, t, token_clear(t));
+    smartlist_free(tokens);
+  }
+  if (area) {
+    memarea_drop_all(area);
+  }
+  return ret;
+}
+
+/* Fully decode an encoded descriptor and set a newly allocated descriptor
+ * object in desc_out. Subcredentials are used if not NULL else it's ignored.
+ *
+ * Return 0 on success. A negative value is returned on error and desc_out is
+ * set to NULL. */
+int
+hs_desc_decode_descriptor(const char *encoded,
+                          const uint8_t *subcredential,
+                          hs_descriptor_t **desc_out)
+{
+  int ret;
+  hs_descriptor_t *desc;
+
+  tor_assert(encoded);
+
+  desc = tor_malloc_zero(sizeof(hs_descriptor_t));
+
+  /* Subcredentials are optional. */
+  if (subcredential) {
+    memcpy(desc->subcredential, subcredential, sizeof(desc->subcredential));
+  }
+
+  ret = hs_desc_decode_plaintext(encoded, &desc->plaintext_data);
+  if (ret < 0) {
+    goto err;
+  }
+
+  ret = hs_desc_decode_encrypted(desc, &desc->encrypted_data);
+  if (ret < 0) {
+    goto err;
+  }
+
+  if (desc_out) {
+    *desc_out = desc;
+  } else {
+    hs_descriptor_free(desc);
+  }
+  return ret;
+
+ err:
+  hs_descriptor_free(desc);
+  if (desc_out) {
+    *desc_out = NULL;
+  }
+
+  tor_assert(ret < 0);
+  return ret;
+}
+
+/* Table of encode function version specific. The function are indexed by the
+ * version number so v3 callback is at index 3 in the array. */
+static int
+  (*encode_handlers[])(
+      const hs_descriptor_t *desc,
+      char **encoded_out) =
+{
+  /* v0 */ NULL, /* v1 */ NULL, /* v2 */ NULL,
+  desc_encode_v3,
+};
+
+/* Encode the given descriptor desc. On success, encoded_out points to a newly
+ * allocated NUL terminated string that contains the encoded descriptor as a
+ * string.
+ *
+ * Return 0 on success and encoded_out is a valid pointer. On error, -1 is
+ * returned and encoded_out is set to NULL. */
+int
+hs_desc_encode_descriptor(const hs_descriptor_t *desc, char **encoded_out)
+{
+  int ret = -1;
+
+  tor_assert(desc);
+  tor_assert(encoded_out);
+
+  /* Make sure we support the version of the descriptor format. */
+  if (!hs_desc_is_supported_version(desc->plaintext_data.version)) {
+    goto err;
+  }
+  /* Extra precaution. Having no handler for the supported version should
+   * never happened else we forgot to add it but we bumped the version. */
+  tor_assert(ARRAY_LENGTH(encode_handlers) >= desc->plaintext_data.version);
+  tor_assert(encode_handlers[desc->plaintext_data.version]);
+
+  ret = encode_handlers[desc->plaintext_data.version](desc, encoded_out);
+  if (ret < 0) {
+    goto err;
+  }
+
+  /* Try to decode what we just encoded. Symmetry is nice! */
+  ret = hs_desc_decode_descriptor(*encoded_out, desc->subcredential, NULL);
+  if (BUG(ret < 0)) {
+    goto err;
+  }
+
+  return 0;
+
+ err:
+  *encoded_out = NULL;
+  return ret;
+}
+
+/* Free the descriptor plaintext data object. */
+void
+hs_desc_plaintext_data_free(hs_desc_plaintext_data_t *desc)
+{
+  desc_plaintext_data_free_contents(desc);
+  tor_free(desc);
+}
+
+/* Free the descriptor encrypted data object. */
+void
+hs_desc_encrypted_data_free(hs_desc_encrypted_data_t *desc)
+{
+  desc_encrypted_data_free_contents(desc);
+  tor_free(desc);
+}
+
+/* Free the given descriptor object. */
+void
+hs_descriptor_free(hs_descriptor_t *desc)
+{
+  if (!desc) {
+    return;
+  }
+
+  desc_plaintext_data_free_contents(&desc->plaintext_data);
+  desc_encrypted_data_free_contents(&desc->encrypted_data);
+  tor_free(desc);
+}
+
+/* Return the size in bytes of the given plaintext data object. A sizeof() is
+ * not enough because the object contains pointers and the encrypted blob.
+ * This is particularly useful for our OOM subsystem that tracks the HSDir
+ * cache size for instance. */
+size_t
+hs_desc_plaintext_obj_size(const hs_desc_plaintext_data_t *data)
+{
+  tor_assert(data);
+  return (sizeof(*data) + sizeof(*data->signing_key_cert) +
+          data->encrypted_blob_size);
+}
+
diff --git a/src/or/hs_descriptor.h b/src/or/hs_descriptor.h
new file mode 100644
index 0000000000..b48079e219
--- /dev/null
+++ b/src/or/hs_descriptor.h
@@ -0,0 +1,238 @@
+/* Copyright (c) 2016, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file hs_descriptor.h
+ * \brief Header file for hs_descriptor.c
+ **/
+
+#ifndef TOR_HS_DESCRIPTOR_H
+#define TOR_HS_DESCRIPTOR_H
+
+#include <stdint.h>
+
+#include "address.h"
+#include "container.h"
+#include "crypto.h"
+#include "crypto_ed25519.h"
+#include "torcert.h"
+
+/* The earliest descriptor format version we support. */
+#define HS_DESC_SUPPORTED_FORMAT_VERSION_MIN 3
+/* The latest descriptor format version we support. */
+#define HS_DESC_SUPPORTED_FORMAT_VERSION_MAX 3
+
+/* Maximum lifetime of a descriptor in seconds. The value is set at 12 hours
+ * which is 720 minutes or 43200 seconds. */
+#define HS_DESC_MAX_LIFETIME (12 * 60 * 60)
+/* Lifetime of certificate in the descriptor. This defines the lifetime of the
+ * descriptor signing key and the cross certification cert of that key. */
+#define HS_DESC_CERT_LIFETIME (24 * 60 * 60)
+/* Length of the salt needed for the encrypted section of a descriptor. */
+#define HS_DESC_ENCRYPTED_SALT_LEN 16
+/* Length of the secret input needed for the KDF construction which derives
+ * the encryption key for the encrypted data section of the descriptor. This
+ * adds up to 68 bytes being the blinded key, hashed subcredential and
+ * revision counter. */
+#define HS_DESC_ENCRYPTED_SECRET_INPUT_LEN \
+  ED25519_PUBKEY_LEN + DIGEST256_LEN + sizeof(uint64_t)
+/* Length of the KDF output value which is the length of the secret key,
+ * the secret IV and MAC key length which is the length of H() output. */
+#define HS_DESC_ENCRYPTED_KDF_OUTPUT_LEN \
+  CIPHER_KEY_LEN + CIPHER_IV_LEN + DIGEST256_LEN
+/* We need to pad the plaintext version of the encrypted data section before
+ * encryption and it has to be a multiple of this value. */
+#define HS_DESC_PLAINTEXT_PADDING_MULTIPLE 128
+/* XXX: Let's make sure this makes sense as an upper limit for the padded
+ * plaintext section. Then we should enforce it as now only an assert will be
+ * triggered if we are above it. */
+/* Once padded, this is the maximum length in bytes for the plaintext. */
+#define HS_DESC_PADDED_PLAINTEXT_MAX_LEN 8192
+/* Minimum length in bytes of the encrypted portion of the descriptor. */
+#define HS_DESC_ENCRYPTED_MIN_LEN \
+  HS_DESC_ENCRYPTED_SALT_LEN + \
+  HS_DESC_PLAINTEXT_PADDING_MULTIPLE + DIGEST256_LEN
+/* Maximum length in bytes of a full hidden service descriptor. */
+#define HS_DESC_MAX_LEN 32768 // XXX justify
+/* The minimum amount of fields a descriptor should contain. The parsing of
+ * the fields are version specific so the only required field, as a generic
+ * view of a descriptor, is 1 that is the version field. */
+#define HS_DESC_PLAINTEXT_MIN_FIELDS 1
+
+/* Type of authentication in the descriptor. */
+typedef enum {
+  HS_DESC_AUTH_PASSWORD = 1,
+  HS_DESC_AUTH_ED25519  = 2,
+} hs_desc_auth_type_t;
+
+/* Type of encryption key in the descriptor. */
+typedef enum {
+  HS_DESC_KEY_TYPE_LEGACY     = 1,
+  HS_DESC_KEY_TYPE_CURVE25519 = 2,
+} hs_desc_key_type_t;
+
+/* Link specifier object that contains information on how to extend to the
+ * relay that is the address, port and handshake type. */
+typedef struct hs_desc_link_specifier_t {
+  /* Indicate the type of link specifier. See trunnel ed25519_cert
+   * specification. */
+  uint8_t type;
+
+  /* It's either an address/port or a legacy identity fingerprint. */
+  union {
+    /* IP address and port of the relay use to extend. */
+    tor_addr_port_t ap;
+    /* Legacy identity. A 20-byte SHA1 identity fingerprint. */
+    uint8_t legacy_id[DIGEST_LEN];
+  } u;
+} hs_desc_link_specifier_t;
+
+/* Introduction point information located in a descriptor. */
+typedef struct hs_desc_intro_point_t {
+  /* Link specifier(s) which details how to extend to the relay. This list
+   * contains hs_desc_link_specifier_t object. It MUST have at least one. */
+  smartlist_t *link_specifiers;
+
+  /* Authentication key used to establish the introduction point circuit and
+   * cross-certifies the blinded public key for the replica thus signed by
+   * the blinded key and in turn signs it. */
+  tor_cert_t *auth_key_cert;
+
+  /* Encryption key type so we know which one to use in the union below. */
+  hs_desc_key_type_t enc_key_type;
+
+  /* Keys are mutually exclusive thus the union. */
+  union {
+    /* Encryption key used to encrypt request to hidden service. */
+    curve25519_keypair_t curve25519;
+
+    /* Backward compat: RSA 1024 encryption key for legacy purposes.
+     * Mutually exclusive with enc_key. */
+    crypto_pk_t *legacy;
+  } enc_key;
+
+  /* True iff the introduction point has passed the cross certification. Upon
+   * decoding an intro point, this must be true. */
+  unsigned int cross_certified : 1;
+} hs_desc_intro_point_t;
+
+/* The encrypted data section of a descriptor. Obviously the data in this is
+ * in plaintext but encrypted once encoded. */
+typedef struct hs_desc_encrypted_data_t {
+  /* Bitfield of CREATE2 cell supported formats. The only currently supported
+   * format is ntor. */
+  unsigned int create2_ntor : 1;
+
+  /* A list of authentication types that a client must at least support one
+   * in order to contact the service. Contains NULL terminated strings. */
+  smartlist_t *auth_types;
+
+  /* A list of intro points. Contains hs_desc_intro_point_t objects. */
+  smartlist_t *intro_points;
+} hs_desc_encrypted_data_t;
+
+/* Plaintext data that is unencrypted information of the descriptor. */
+typedef struct hs_desc_plaintext_data_t {
+  /* Version of the descriptor format. Spec specifies this field as a
+   * positive integer. */
+  uint32_t version;
+
+  /* The lifetime of the descriptor in seconds. */
+  uint32_t lifetime_sec;
+
+  /* Certificate with the short-term ed22519 descriptor signing key for the
+   * replica which is signed by the blinded public key for that replica. */
+  tor_cert_t *signing_key_cert;
+
+  /* Signing keypair which is used to sign the descriptor. Same public key
+   * as in the signing key certificate. */
+  ed25519_keypair_t signing_kp;
+
+  /* Blinded keypair used for this descriptor derived from the master
+   * identity key and generated for a specific replica number. */
+  ed25519_keypair_t blinded_kp;
+
+  /* Revision counter is incremented at each upload, regardless of whether
+   * the descriptor has changed. This avoids leaking whether the descriptor
+   * has changed. Spec specifies this as a 8 bytes positive integer. */
+  uint64_t revision_counter;
+
+  /* Decoding only: The base64-decoded encrypted blob from the descriptor */
+  uint8_t *encrypted_blob;
+
+  /* Decoding only: Size of the encrypted_blob */
+  size_t encrypted_blob_size;
+} hs_desc_plaintext_data_t;
+
+/* Service descriptor in its decoded form. */
+typedef struct hs_descriptor_t {
+  /* Contains the plaintext part of the descriptor. */
+  hs_desc_plaintext_data_t plaintext_data;
+
+  /* The following contains what's in the encrypted part of the descriptor.
+   * It's only encrypted in the encoded version of the descriptor thus the
+   * data contained in that object is in plaintext. */
+  hs_desc_encrypted_data_t encrypted_data;
+
+  /* Subcredentials of a service, used by the client and service to decrypt
+   * the encrypted data. */
+  uint8_t subcredential[DIGEST256_LEN];
+} hs_descriptor_t;
+
+/* Return true iff the given descriptor format version is supported. */
+static inline int
+hs_desc_is_supported_version(uint32_t version)
+{
+  if (version < HS_DESC_SUPPORTED_FORMAT_VERSION_MIN ||
+      version > HS_DESC_SUPPORTED_FORMAT_VERSION_MAX) {
+    return 0;
+  }
+  return 1;
+}
+
+/* Public API. */
+
+void hs_descriptor_free(hs_descriptor_t *desc);
+void hs_desc_plaintext_data_free(hs_desc_plaintext_data_t *desc);
+void hs_desc_encrypted_data_free(hs_desc_encrypted_data_t *desc);
+
+int hs_desc_encode_descriptor(const hs_descriptor_t *desc,
+                              char **encoded_out);
+
+int hs_desc_decode_descriptor(const char *encoded,
+                              const uint8_t *subcredential,
+                              hs_descriptor_t **desc_out);
+int hs_desc_decode_plaintext(const char *encoded,
+                             hs_desc_plaintext_data_t *plaintext);
+int hs_desc_decode_encrypted(const hs_descriptor_t *desc,
+                             hs_desc_encrypted_data_t *desc_out);
+
+size_t hs_desc_plaintext_obj_size(const hs_desc_plaintext_data_t *data);
+
+#ifdef HS_DESCRIPTOR_PRIVATE
+
+/* Encoding. */
+STATIC int encode_cert(const tor_cert_t *cert, char **cert_str_out);
+STATIC char *encode_link_specifiers(const smartlist_t *specs);
+STATIC size_t build_plaintext_padding(const char *plaintext,
+                                      size_t plaintext_len,
+                                      uint8_t **padded_out);
+/* Decoding. */
+STATIC smartlist_t *decode_link_specifiers(const char *encoded);
+STATIC hs_desc_intro_point_t *decode_introduction_point(
+                                const hs_descriptor_t *desc,
+                                const char *text);
+STATIC int decode_intro_points(const hs_descriptor_t *desc,
+                               hs_desc_encrypted_data_t *desc_enc,
+                               const char *data);
+STATIC int encrypted_data_length_is_valid(size_t len);
+STATIC int cert_is_valid(tor_cert_t *cert, uint8_t type,
+                         const char *log_obj_type);
+STATIC int desc_sig_is_valid(const char *b64_sig,
+                             const ed25519_keypair_t *signing_kp,
+                             const char *encoded_desc, size_t encoded_len);
+
+#endif /* HS_DESCRIPTOR_PRIVATE */
+
+#endif /* TOR_HS_DESCRIPTOR_H */
+
diff --git a/src/or/include.am b/src/or/include.am
index b4554aadb9..10f8b85bdf 100644
--- a/src/or/include.am
+++ b/src/or/include.am
@@ -48,6 +48,9 @@ LIBTOR_A_SOURCES = \
 	src/or/entrynodes.c				\
 	src/or/ext_orport.c				\
 	src/or/hibernate.c				\
+	src/or/hs_cache.c				\
+	src/or/hs_common.c				\
+	src/or/hs_descriptor.c				\
 	src/or/keypin.c					\
 	src/or/main.c					\
 	src/or/microdesc.c				\
@@ -59,6 +62,7 @@ LIBTOR_A_SOURCES = \
 	src/or/shared_random.c			\
 	src/or/shared_random_state.c		\
 	src/or/transports.c				\
+	src/or/parsecommon.c			\
 	src/or/periodic.c				\
 	src/or/protover.c				\
 	src/or/policies.c				\
@@ -157,6 +161,9 @@ ORHEADERS = \
 	src/or/geoip.h					\
 	src/or/entrynodes.h				\
 	src/or/hibernate.h				\
+	src/or/hs_cache.h				\
+	src/or/hs_common.h				\
+	src/or/hs_descriptor.h				\
 	src/or/keypin.h					\
 	src/or/main.h					\
 	src/or/microdesc.h				\
@@ -171,6 +178,7 @@ ORHEADERS = \
 	src/or/shared_random.h			\
 	src/or/shared_random_state.h		\
 	src/or/transports.h				\
+	src/or/parsecommon.h			\
 	src/or/periodic.h				\
 	src/or/policies.h				\
 	src/or/protover.h				\
diff --git a/src/or/main.c b/src/or/main.c
index 004ef7e65a..c10f62724a 100644
--- a/src/or/main.c
+++ b/src/or/main.c
@@ -73,6 +73,7 @@
 #include "entrynodes.h"
 #include "geoip.h"
 #include "hibernate.h"
+#include "hs_cache.h"
 #include "keypin.h"
 #include "main.h"
 #include "microdesc.h"
@@ -1748,7 +1749,7 @@ clean_caches_callback(time_t now, const or_options_t *options)
   rep_history_clean(now - options->RephistTrackTime);
   rend_cache_clean(now, REND_CACHE_TYPE_CLIENT);
   rend_cache_clean(now, REND_CACHE_TYPE_SERVICE);
-  rend_cache_clean_v2_descs_as_dir(now, 0);
+  hs_cache_clean_as_dir(now);
   microdesc_cache_rebuild(NULL, 0);
 #define CLEAN_CACHES_INTERVAL (30*60)
   return CLEAN_CACHES_INTERVAL;
@@ -3094,6 +3095,7 @@ tor_free_all(int postfork)
   rend_service_free_all();
   rend_cache_free_all();
   rend_service_authorization_free_all();
+  hs_cache_free_all();
   rep_hist_free_all();
   dns_free_all();
   clear_pending_onions();
diff --git a/src/or/or.h b/src/or/or.h
index d305eac543..a43e2a33cd 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -114,6 +114,9 @@
 #define NON_ANONYMOUS_MODE_ENABLED 1
 #endif
 
+/** Helper macro: Given a pointer to to.base_, of type from*, return &to. */
+#define DOWNCAST(to, ptr) ((to*)SUBTYPE_P(ptr, to, base_))
+
 /** Length of longest allowable configured nickname. */
 #define MAX_NICKNAME_LEN 19
 /** Length of a router identity encoded as a hexadecimal digest, plus
@@ -779,6 +782,24 @@ typedef struct rend_service_authorization_t {
  * establishment. Not all fields contain data depending on where this struct
  * is used. */
 typedef struct rend_data_t {
+  /* Hidden service protocol version of this base object. */
+  uint32_t version;
+
+  /** List of HSDir fingerprints on which this request has been sent to. This
+   * contains binary identity digest of the directory of size DIGEST_LEN. */
+  smartlist_t *hsdirs_fp;
+
+  /** Rendezvous cookie used by both, client and service. */
+  char rend_cookie[REND_COOKIE_LEN];
+
+  /** Number of streams associated with this rendezvous circuit. */
+  int nr_streams;
+} rend_data_t;
+
+typedef struct rend_data_v2_t {
+  /* Rendezvous base data. */
+  rend_data_t base_;
+
   /** Onion address (without the .onion part) that a client requests. */
   char onion_address[REND_SERVICE_ID_LEN_BASE32+1];
 
@@ -800,17 +821,16 @@ typedef struct rend_data_t {
 
   /** Hash of the hidden service's PK used by a service. */
   char rend_pk_digest[DIGEST_LEN];
+} rend_data_v2_t;
 
-  /** Rendezvous cookie used by both, client and service. */
-  char rend_cookie[REND_COOKIE_LEN];
-
-  /** List of HSDir fingerprints on which this request has been sent to.
-   * This contains binary identity digest of the directory. */
-  smartlist_t *hsdirs_fp;
-
-  /** Number of streams associated with this rendezvous circuit. */
-  int nr_streams;
-} rend_data_t;
+/* From a base rend_data_t object <b>d</d>, return the v2 object. */
+static inline
+rend_data_v2_t *TO_REND_DATA_V2(const rend_data_t *d)
+{
+  tor_assert(d);
+  tor_assert(d->version == 2);
+  return DOWNCAST(rend_data_v2_t, d);
+}
 
 /** Time interval for tracking replays of DH public keys received in
  * INTRODUCE2 cells.  Used only to avoid launching multiple
@@ -1805,8 +1825,6 @@ typedef struct control_connection_t {
 
 /** Cast a connection_t subtype pointer to a connection_t **/
 #define TO_CONN(c) (&(((c)->base_)))
-/** Helper macro: Given a pointer to to.base_, of type from*, return &to. */
-#define DOWNCAST(to, ptr) ((to*)SUBTYPE_P(ptr, to, base_))
 
 /** Cast a entry_connection_t subtype pointer to a edge_connection_t **/
 #define ENTRY_TO_EDGE_CONN(c) (&(((c))->edge_))
diff --git a/src/or/parsecommon.c b/src/or/parsecommon.c
new file mode 100644
index 0000000000..6622d7d671
--- /dev/null
+++ b/src/or/parsecommon.c
@@ -0,0 +1,450 @@
+/* Copyright (c) 2016, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file parsecommon.c
+ * \brief Common code to parse and validate various type of descriptors.
+ **/
+
+#include "parsecommon.h"
+#include "torlog.h"
+#include "util_format.h"
+
+#define MIN_ANNOTATION A_PURPOSE
+#define MAX_ANNOTATION A_UNKNOWN_
+
+#define ALLOC_ZERO(sz) memarea_alloc_zero(area,sz)
+#define ALLOC(sz) memarea_alloc(area,sz)
+#define STRDUP(str) memarea_strdup(area,str)
+#define STRNDUP(str,n) memarea_strndup(area,(str),(n))
+
+#define RET_ERR(msg)                                               \
+  STMT_BEGIN                                                       \
+    if (tok) token_clear(tok);                                      \
+    tok = ALLOC_ZERO(sizeof(directory_token_t));                   \
+    tok->tp = ERR_;                                                \
+    tok->error = STRDUP(msg);                                      \
+    goto done_tokenizing;                                          \
+  STMT_END
+
+/** Free all resources allocated for <b>tok</b> */
+void
+token_clear(directory_token_t *tok)
+{
+  if (tok->key)
+    crypto_pk_free(tok->key);
+}
+
+/** Read all tokens from a string between <b>start</b> and <b>end</b>, and add
+ * them to <b>out</b>.  Parse according to the token rules in <b>table</b>.
+ * Caller must free tokens in <b>out</b>.  If <b>end</b> is NULL, use the
+ * entire string.
+ */
+int
+tokenize_string(memarea_t *area,
+                const char *start, const char *end, smartlist_t *out,
+                token_rule_t *table, int flags)
+{
+  const char **s;
+  directory_token_t *tok = NULL;
+  int counts[NIL_];
+  int i;
+  int first_nonannotation;
+  int prev_len = smartlist_len(out);
+  tor_assert(area);
+
+  s = &start;
+  if (!end) {
+    end = start+strlen(start);
+  } else {
+    /* it's only meaningful to check for nuls if we got an end-of-string ptr */
+    if (memchr(start, '\0', end-start)) {
+      log_warn(LD_DIR, "parse error: internal NUL character.");
+      return -1;
+    }
+  }
+  for (i = 0; i < NIL_; ++i)
+    counts[i] = 0;
+
+  SMARTLIST_FOREACH(out, const directory_token_t *, t, ++counts[t->tp]);
+
+  while (*s < end && (!tok || tok->tp != EOF_)) {
+    tok = get_next_token(area, s, end, table);
+    if (tok->tp == ERR_) {
+      log_warn(LD_DIR, "parse error: %s", tok->error);
+      token_clear(tok);
+      return -1;
+    }
+    ++counts[tok->tp];
+    smartlist_add(out, tok);
+    *s = eat_whitespace_eos(*s, end);
+  }
+
+  if (flags & TS_NOCHECK)
+    return 0;
+
+  if ((flags & TS_ANNOTATIONS_OK)) {
+    first_nonannotation = -1;
+    for (i = 0; i < smartlist_len(out); ++i) {
+      tok = smartlist_get(out, i);
+      if (tok->tp < MIN_ANNOTATION || tok->tp > MAX_ANNOTATION) {
+        first_nonannotation = i;
+        break;
+      }
+    }
+    if (first_nonannotation < 0) {
+      log_warn(LD_DIR, "parse error: item contains only annotations");
+      return -1;
+    }
+    for (i=first_nonannotation;  i < smartlist_len(out); ++i) {
+      tok = smartlist_get(out, i);
+      if (tok->tp >= MIN_ANNOTATION && tok->tp <= MAX_ANNOTATION) {
+        log_warn(LD_DIR, "parse error: Annotations mixed with keywords");
+        return -1;
+      }
+    }
+    if ((flags & TS_NO_NEW_ANNOTATIONS)) {
+      if (first_nonannotation != prev_len) {
+        log_warn(LD_DIR, "parse error: Unexpected annotations.");
+        return -1;
+      }
+    }
+  } else {
+    for (i=0;  i < smartlist_len(out); ++i) {
+      tok = smartlist_get(out, i);
+      if (tok->tp >= MIN_ANNOTATION && tok->tp <= MAX_ANNOTATION) {
+        log_warn(LD_DIR, "parse error: no annotations allowed.");
+        return -1;
+      }
+    }
+    first_nonannotation = 0;
+  }
+  for (i = 0; table[i].t; ++i) {
+    if (counts[table[i].v] < table[i].min_cnt) {
+      log_warn(LD_DIR, "Parse error: missing %s element.", table[i].t);
+      return -1;
+    }
+    if (counts[table[i].v] > table[i].max_cnt) {
+      log_warn(LD_DIR, "Parse error: too many %s elements.", table[i].t);
+      return -1;
+    }
+    if (table[i].pos & AT_START) {
+      if (smartlist_len(out) < 1 ||
+          (tok = smartlist_get(out, first_nonannotation))->tp != table[i].v) {
+        log_warn(LD_DIR, "Parse error: first item is not %s.", table[i].t);
+        return -1;
+      }
+    }
+    if (table[i].pos & AT_END) {
+      if (smartlist_len(out) < 1 ||
+          (tok = smartlist_get(out, smartlist_len(out)-1))->tp != table[i].v) {
+        log_warn(LD_DIR, "Parse error: last item is not %s.", table[i].t);
+        return -1;
+      }
+    }
+  }
+  return 0;
+}
+
+/** Helper: parse space-separated arguments from the string <b>s</b> ending at
+ * <b>eol</b>, and store them in the args field of <b>tok</b>.  Store the
+ * number of parsed elements into the n_args field of <b>tok</b>.  Allocate
+ * all storage in <b>area</b>.  Return the number of arguments parsed, or
+ * return -1 if there was an insanely high number of arguments. */
+static inline int
+get_token_arguments(memarea_t *area, directory_token_t *tok,
+                    const char *s, const char *eol)
+{
+/** Largest number of arguments we'll accept to any token, ever. */
+#define MAX_ARGS 512
+  char *mem = memarea_strndup(area, s, eol-s);
+  char *cp = mem;
+  int j = 0;
+  char *args[MAX_ARGS];
+  while (*cp) {
+    if (j == MAX_ARGS)
+      return -1;
+    args[j++] = cp;
+    cp = (char*)find_whitespace(cp);
+    if (!cp || !*cp)
+      break; /* End of the line. */
+    *cp++ = '\0';
+    cp = (char*)eat_whitespace(cp);
+  }
+  tok->n_args = j;
+  tok->args = memarea_memdup(area, args, j*sizeof(char*));
+  return j;
+#undef MAX_ARGS
+}
+
+/** Helper: make sure that the token <b>tok</b> with keyword <b>kwd</b> obeys
+ * the object syntax of <b>o_syn</b>.  Allocate all storage in <b>area</b>.
+ * Return <b>tok</b> on success, or a new ERR_ token if the token didn't
+ * conform to the syntax we wanted.
+ **/
+static inline directory_token_t *
+token_check_object(memarea_t *area, const char *kwd,
+                   directory_token_t *tok, obj_syntax o_syn)
+{
+  char ebuf[128];
+  switch (o_syn) {
+    case NO_OBJ:
+      /* No object is allowed for this token. */
+      if (tok->object_body) {
+        tor_snprintf(ebuf, sizeof(ebuf), "Unexpected object for %s", kwd);
+        RET_ERR(ebuf);
+      }
+      if (tok->key) {
+        tor_snprintf(ebuf, sizeof(ebuf), "Unexpected public key for %s", kwd);
+        RET_ERR(ebuf);
+      }
+      break;
+    case NEED_OBJ:
+      /* There must be a (non-key) object. */
+      if (!tok->object_body) {
+        tor_snprintf(ebuf, sizeof(ebuf), "Missing object for %s", kwd);
+        RET_ERR(ebuf);
+      }
+      break;
+    case NEED_KEY_1024: /* There must be a 1024-bit public key. */
+    case NEED_SKEY_1024: /* There must be a 1024-bit private key. */
+      if (tok->key && crypto_pk_num_bits(tok->key) != PK_BYTES*8) {
+        tor_snprintf(ebuf, sizeof(ebuf), "Wrong size on key for %s: %d bits",
+                     kwd, crypto_pk_num_bits(tok->key));
+        RET_ERR(ebuf);
+      }
+      /* fall through */
+    case NEED_KEY: /* There must be some kind of key. */
+      if (!tok->key) {
+        tor_snprintf(ebuf, sizeof(ebuf), "Missing public key for %s", kwd);
+        RET_ERR(ebuf);
+      }
+      if (o_syn != NEED_SKEY_1024) {
+        if (crypto_pk_key_is_private(tok->key)) {
+          tor_snprintf(ebuf, sizeof(ebuf),
+               "Private key given for %s, which wants a public key", kwd);
+          RET_ERR(ebuf);
+        }
+      } else { /* o_syn == NEED_SKEY_1024 */
+        if (!crypto_pk_key_is_private(tok->key)) {
+          tor_snprintf(ebuf, sizeof(ebuf),
+               "Public key given for %s, which wants a private key", kwd);
+          RET_ERR(ebuf);
+        }
+      }
+      break;
+    case OBJ_OK:
+      /* Anything goes with this token. */
+      break;
+  }
+
+ done_tokenizing:
+  return tok;
+}
+
+/** Helper function: read the next token from *s, advance *s to the end of the
+ * token, and return the parsed token.  Parse *<b>s</b> according to the list
+ * of tokens in <b>table</b>.
+ */
+directory_token_t *
+get_next_token(memarea_t *area,
+               const char **s, const char *eos, token_rule_t *table)
+{
+  /** Reject any object at least this big; it is probably an overflow, an
+   * attack, a bug, or some other nonsense. */
+#define MAX_UNPARSED_OBJECT_SIZE (128*1024)
+  /** Reject any line at least this big; it is probably an overflow, an
+   * attack, a bug, or some other nonsense. */
+#define MAX_LINE_LENGTH (128*1024)
+
+  const char *next, *eol, *obstart;
+  size_t obname_len;
+  int i;
+  directory_token_t *tok;
+  obj_syntax o_syn = NO_OBJ;
+  char ebuf[128];
+  const char *kwd = "";
+
+  tor_assert(area);
+  tok = ALLOC_ZERO(sizeof(directory_token_t));
+  tok->tp = ERR_;
+
+  /* Set *s to first token, eol to end-of-line, next to after first token */
+  *s = eat_whitespace_eos(*s, eos); /* eat multi-line whitespace */
+  tor_assert(eos >= *s);
+  eol = memchr(*s, '\n', eos-*s);
+  if (!eol)
+    eol = eos;
+  if (eol - *s > MAX_LINE_LENGTH) {
+    RET_ERR("Line far too long");
+  }
+
+  next = find_whitespace_eos(*s, eol);
+
+  if (!strcmp_len(*s, "opt", next-*s)) {
+    /* Skip past an "opt" at the start of the line. */
+    *s = eat_whitespace_eos_no_nl(next, eol);
+    next = find_whitespace_eos(*s, eol);
+  } else if (*s == eos) {  /* If no "opt", and end-of-line, line is invalid */
+    RET_ERR("Unexpected EOF");
+  }
+
+  /* Search the table for the appropriate entry.  (I tried a binary search
+   * instead, but it wasn't any faster.) */
+  for (i = 0; table[i].t ; ++i) {
+    if (!strcmp_len(*s, table[i].t, next-*s)) {
+      /* We've found the keyword. */
+      kwd = table[i].t;
+      tok->tp = table[i].v;
+      o_syn = table[i].os;
+      *s = eat_whitespace_eos_no_nl(next, eol);
+      /* We go ahead whether there are arguments or not, so that tok->args is
+       * always set if we want arguments. */
+      if (table[i].concat_args) {
+        /* The keyword takes the line as a single argument */
+        tok->args = ALLOC(sizeof(char*));
+        tok->args[0] = STRNDUP(*s,eol-*s); /* Grab everything on line */
+        tok->n_args = 1;
+      } else {
+        /* This keyword takes multiple arguments. */
+        if (get_token_arguments(area, tok, *s, eol)<0) {
+          tor_snprintf(ebuf, sizeof(ebuf),"Far too many arguments to %s", kwd);
+          RET_ERR(ebuf);
+        }
+        *s = eol;
+      }
+      if (tok->n_args < table[i].min_args) {
+        tor_snprintf(ebuf, sizeof(ebuf), "Too few arguments to %s", kwd);
+        RET_ERR(ebuf);
+      } else if (tok->n_args > table[i].max_args) {
+        tor_snprintf(ebuf, sizeof(ebuf), "Too many arguments to %s", kwd);
+        RET_ERR(ebuf);
+      }
+      break;
+    }
+  }
+
+  if (tok->tp == ERR_) {
+    /* No keyword matched; call it an "K_opt" or "A_unrecognized" */
+    if (**s == '@')
+      tok->tp = A_UNKNOWN_;
+    else
+      tok->tp = K_OPT;
+    tok->args = ALLOC(sizeof(char*));
+    tok->args[0] = STRNDUP(*s, eol-*s);
+    tok->n_args = 1;
+    o_syn = OBJ_OK;
+  }
+
+  /* Check whether there's an object present */
+  *s = eat_whitespace_eos(eol, eos);  /* Scan from end of first line */
+  tor_assert(eos >= *s);
+  eol = memchr(*s, '\n', eos-*s);
+  if (!eol || eol-*s<11 || strcmpstart(*s, "-----BEGIN ")) /* No object. */
+    goto check_object;
+
+  obstart = *s; /* Set obstart to start of object spec */
+  if (*s+16 >= eol || memchr(*s+11,'\0',eol-*s-16) || /* no short lines, */
+      strcmp_len(eol-5, "-----", 5) ||           /* nuls or invalid endings */
+      (eol-*s) > MAX_UNPARSED_OBJECT_SIZE) {     /* name too long */
+    RET_ERR("Malformed object: bad begin line");
+  }
+  tok->object_type = STRNDUP(*s+11, eol-*s-16);
+  obname_len = eol-*s-16; /* store objname length here to avoid a strlen() */
+  *s = eol+1;    /* Set *s to possible start of object data (could be eos) */
+
+  /* Go to the end of the object */
+  next = tor_memstr(*s, eos-*s, "-----END ");
+  if (!next) {
+    RET_ERR("Malformed object: missing object end line");
+  }
+  tor_assert(eos >= next);
+  eol = memchr(next, '\n', eos-next);
+  if (!eol)  /* end-of-line marker, or eos if there's no '\n' */
+    eol = eos;
+  /* Validate the ending tag, which should be 9 + NAME + 5 + eol */
+  if ((size_t)(eol-next) != 9+obname_len+5 ||
+      strcmp_len(next+9, tok->object_type, obname_len) ||
+      strcmp_len(eol-5, "-----", 5)) {
+    tor_snprintf(ebuf, sizeof(ebuf), "Malformed object: mismatched end tag %s",
+             tok->object_type);
+    ebuf[sizeof(ebuf)-1] = '\0';
+    RET_ERR(ebuf);
+  }
+  if (next - *s > MAX_UNPARSED_OBJECT_SIZE)
+    RET_ERR("Couldn't parse object: missing footer or object much too big.");
+
+  if (!strcmp(tok->object_type, "RSA PUBLIC KEY")) { /* If it's a public key */
+    tok->key = crypto_pk_new();
+    if (crypto_pk_read_public_key_from_string(tok->key, obstart, eol-obstart))
+      RET_ERR("Couldn't parse public key.");
+  } else if (!strcmp(tok->object_type, "RSA PRIVATE KEY")) { /* private key */
+    tok->key = crypto_pk_new();
+    if (crypto_pk_read_private_key_from_string(tok->key, obstart, eol-obstart))
+      RET_ERR("Couldn't parse private key.");
+  } else { /* If it's something else, try to base64-decode it */
+    int r;
+    tok->object_body = ALLOC(next-*s); /* really, this is too much RAM. */
+    r = base64_decode(tok->object_body, next-*s, *s, next-*s);
+    if (r<0)
+      RET_ERR("Malformed object: bad base64-encoded data");
+    tok->object_size = r;
+  }
+  *s = eol;
+
+ check_object:
+  tok = token_check_object(area, kwd, tok, o_syn);
+
+ done_tokenizing:
+  return tok;
+
+#undef RET_ERR
+#undef ALLOC
+#undef ALLOC_ZERO
+#undef STRDUP
+#undef STRNDUP
+}
+
+/** Find the first token in <b>s</b> whose keyword is <b>keyword</b>; fail
+ * with an assert if no such keyword is found.
+ */
+directory_token_t *
+find_by_keyword_(smartlist_t *s, directory_keyword keyword,
+                 const char *keyword_as_string)
+{
+  directory_token_t *tok = find_opt_by_keyword(s, keyword);
+  if (PREDICT_UNLIKELY(!tok)) {
+    log_err(LD_BUG, "Missing %s [%d] in directory object that should have "
+         "been validated. Internal error.", keyword_as_string, (int)keyword);
+    tor_assert(tok);
+  }
+  return tok;
+}
+
+/** Find the first token in <b>s</b> whose keyword is <b>keyword</b>; return
+ * NULL if no such keyword is found.
+ */
+directory_token_t *
+find_opt_by_keyword(smartlist_t *s, directory_keyword keyword)
+{
+  SMARTLIST_FOREACH(s, directory_token_t *, t, if (t->tp == keyword) return t);
+  return NULL;
+}
+
+/** If there are any directory_token_t entries in <b>s</b> whose keyword is
+ * <b>k</b>, return a newly allocated smartlist_t containing all such entries,
+ * in the same order in which they occur in <b>s</b>.  Otherwise return
+ * NULL. */
+smartlist_t *
+find_all_by_keyword(smartlist_t *s, directory_keyword k)
+{
+  smartlist_t *out = NULL;
+  SMARTLIST_FOREACH(s, directory_token_t *, t,
+                    if (t->tp == k) {
+                    if (!out)
+                    out = smartlist_new();
+                    smartlist_add(out, t);
+                    });
+  return out;
+}
+
diff --git a/src/or/parsecommon.h b/src/or/parsecommon.h
new file mode 100644
index 0000000000..3a86c52f3c
--- /dev/null
+++ b/src/or/parsecommon.h
@@ -0,0 +1,314 @@
+/* Copyright (c) 2016, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file parsecommon.h
+ * \brief Header file for parsecommon.c
+ **/
+
+#ifndef TOR_PARSECOMMON_H
+#define TOR_PARSECOMMON_H
+
+#include "container.h"
+#include "crypto.h"
+#include "memarea.h"
+
+/** Enumeration of possible token types.  The ones starting with K_ correspond
+* to directory 'keywords'. A_ is for an annotation, R or C is related to
+* hidden services, ERR_ is an error in the tokenizing process, EOF_ is an
+* end-of-file marker, and NIL_ is used to encode not-a-token.
+*/
+typedef enum {
+  K_ACCEPT = 0,
+  K_ACCEPT6,
+  K_DIRECTORY_SIGNATURE,
+  K_RECOMMENDED_SOFTWARE,
+  K_REJECT,
+  K_REJECT6,
+  K_ROUTER,
+  K_SIGNED_DIRECTORY,
+  K_SIGNING_KEY,
+  K_ONION_KEY,
+  K_ONION_KEY_NTOR,
+  K_ROUTER_SIGNATURE,
+  K_PUBLISHED,
+  K_RUNNING_ROUTERS,
+  K_ROUTER_STATUS,
+  K_PLATFORM,
+  K_PROTO,
+  K_OPT,
+  K_BANDWIDTH,
+  K_CONTACT,
+  K_NETWORK_STATUS,
+  K_UPTIME,
+  K_DIR_SIGNING_KEY,
+  K_FAMILY,
+  K_FINGERPRINT,
+  K_HIBERNATING,
+  K_READ_HISTORY,
+  K_WRITE_HISTORY,
+  K_NETWORK_STATUS_VERSION,
+  K_DIR_SOURCE,
+  K_DIR_OPTIONS,
+  K_CLIENT_VERSIONS,
+  K_SERVER_VERSIONS,
+  K_RECOMMENDED_CLIENT_PROTOCOLS,
+  K_RECOMMENDED_RELAY_PROTOCOLS,
+  K_REQUIRED_CLIENT_PROTOCOLS,
+  K_REQUIRED_RELAY_PROTOCOLS,
+  K_OR_ADDRESS,
+  K_ID,
+  K_P,
+  K_P6,
+  K_R,
+  K_A,
+  K_S,
+  K_V,
+  K_W,
+  K_M,
+  K_EXTRA_INFO,
+  K_EXTRA_INFO_DIGEST,
+  K_CACHES_EXTRA_INFO,
+  K_HIDDEN_SERVICE_DIR,
+  K_ALLOW_SINGLE_HOP_EXITS,
+  K_IPV6_POLICY,
+  K_ROUTER_SIG_ED25519,
+  K_IDENTITY_ED25519,
+  K_MASTER_KEY_ED25519,
+  K_ONION_KEY_CROSSCERT,
+  K_NTOR_ONION_KEY_CROSSCERT,
+
+  K_DIRREQ_END,
+  K_DIRREQ_V2_IPS,
+  K_DIRREQ_V3_IPS,
+  K_DIRREQ_V2_REQS,
+  K_DIRREQ_V3_REQS,
+  K_DIRREQ_V2_SHARE,
+  K_DIRREQ_V3_SHARE,
+  K_DIRREQ_V2_RESP,
+  K_DIRREQ_V3_RESP,
+  K_DIRREQ_V2_DIR,
+  K_DIRREQ_V3_DIR,
+  K_DIRREQ_V2_TUN,
+  K_DIRREQ_V3_TUN,
+  K_ENTRY_END,
+  K_ENTRY_IPS,
+  K_CELL_END,
+  K_CELL_PROCESSED,
+  K_CELL_QUEUED,
+  K_CELL_TIME,
+  K_CELL_CIRCS,
+  K_EXIT_END,
+  K_EXIT_WRITTEN,
+  K_EXIT_READ,
+  K_EXIT_OPENED,
+
+  K_DIR_KEY_CERTIFICATE_VERSION,
+  K_DIR_IDENTITY_KEY,
+  K_DIR_KEY_PUBLISHED,
+  K_DIR_KEY_EXPIRES,
+  K_DIR_KEY_CERTIFICATION,
+  K_DIR_KEY_CROSSCERT,
+  K_DIR_ADDRESS,
+  K_DIR_TUNNELLED,
+
+  K_VOTE_STATUS,
+  K_VALID_AFTER,
+  K_FRESH_UNTIL,
+  K_VALID_UNTIL,
+  K_VOTING_DELAY,
+
+  K_KNOWN_FLAGS,
+  K_PARAMS,
+  K_BW_WEIGHTS,
+  K_VOTE_DIGEST,
+  K_CONSENSUS_DIGEST,
+  K_ADDITIONAL_DIGEST,
+  K_ADDITIONAL_SIGNATURE,
+  K_CONSENSUS_METHODS,
+  K_CONSENSUS_METHOD,
+  K_LEGACY_DIR_KEY,
+  K_DIRECTORY_FOOTER,
+  K_SIGNING_CERT_ED,
+  K_SR_FLAG,
+  K_COMMIT,
+  K_PREVIOUS_SRV,
+  K_CURRENT_SRV,
+  K_PACKAGE,
+
+  A_PURPOSE,
+  A_LAST_LISTED,
+  A_UNKNOWN_,
+
+  R_RENDEZVOUS_SERVICE_DESCRIPTOR,
+  R_VERSION,
+  R_PERMANENT_KEY,
+  R_SECRET_ID_PART,
+  R_PUBLICATION_TIME,
+  R_PROTOCOL_VERSIONS,
+  R_INTRODUCTION_POINTS,
+  R_SIGNATURE,
+
+  R_HS_DESCRIPTOR, /* From version 3, this MUST be generic to all future
+                      descriptor versions thus making it R_. */
+  R3_DESC_LIFETIME,
+  R3_DESC_SIGNING_CERT,
+  R3_REVISION_COUNTER,
+  R3_ENCRYPTED,
+  R3_SIGNATURE,
+  R3_CREATE2_FORMATS,
+  R3_AUTHENTICATION_REQUIRED,
+  R3_INTRODUCTION_POINT,
+  R3_INTRO_AUTH_KEY,
+  R3_INTRO_ENC_KEY,
+  R3_INTRO_ENC_KEY_CERTIFICATION,
+
+  R_IPO_IDENTIFIER,
+  R_IPO_IP_ADDRESS,
+  R_IPO_ONION_PORT,
+  R_IPO_ONION_KEY,
+  R_IPO_SERVICE_KEY,
+
+  C_CLIENT_NAME,
+  C_DESCRIPTOR_COOKIE,
+  C_CLIENT_KEY,
+
+  ERR_,
+  EOF_,
+  NIL_
+} directory_keyword;
+
+/** Structure to hold a single directory token.
+ *
+ * We parse a directory by breaking it into "tokens", each consisting
+ * of a keyword, a line full of arguments, and a binary object.  The
+ * arguments and object are both optional, depending on the keyword
+ * type.
+ *
+ * This structure is only allocated in memareas; do not allocate it on
+ * the heap, or token_clear() won't work.
+ */
+typedef struct directory_token_t {
+  directory_keyword tp;        /**< Type of the token. */
+  int n_args:30;               /**< Number of elements in args */
+  char **args;                 /**< Array of arguments from keyword line. */
+
+  char *object_type;           /**< -----BEGIN [object_type]-----*/
+  size_t object_size;          /**< Bytes in object_body */
+  char *object_body;           /**< Contents of object, base64-decoded. */
+
+  crypto_pk_t *key;        /**< For public keys only.  Heap-allocated. */
+
+  char *error;                 /**< For ERR_ tokens only. */
+} directory_token_t;
+
+/** We use a table of rules to decide how to parse each token type. */
+
+/** Rules for whether the keyword needs an object. */
+typedef enum {
+  NO_OBJ,        /**< No object, ever. */
+  NEED_OBJ,      /**< Object is required. */
+  NEED_SKEY_1024,/**< Object is required, and must be a 1024 bit private key */
+  NEED_KEY_1024, /**< Object is required, and must be a 1024 bit public key */
+  NEED_KEY,      /**< Object is required, and must be a public key. */
+  OBJ_OK,        /**< Object is optional. */
+} obj_syntax;
+
+#define AT_START 1
+#define AT_END 2
+
+#define TS_ANNOTATIONS_OK 1
+#define TS_NOCHECK 2
+#define TS_NO_NEW_ANNOTATIONS 4
+
+/**
+ * @name macros for defining token rules
+ *
+ * Helper macros to define token tables.  's' is a string, 't' is a
+ * directory_keyword, 'a' is a trio of argument multiplicities, and 'o' is an
+ * object syntax.
+ */
+/**@{*/
+
+/** Appears to indicate the end of a table. */
+#define END_OF_TABLE { NULL, NIL_, 0,0,0, NO_OBJ, 0, INT_MAX, 0, 0 }
+/** An item with no restrictions: used for obsolete document types */
+#define T(s,t,a,o)    { s, t, a, o, 0, INT_MAX, 0, 0 }
+/** An item with no restrictions on multiplicity or location. */
+#define T0N(s,t,a,o)  { s, t, a, o, 0, INT_MAX, 0, 0 }
+/** An item that must appear exactly once */
+#define T1(s,t,a,o)   { s, t, a, o, 1, 1, 0, 0 }
+/** An item that must appear exactly once, at the start of the document */
+#define T1_START(s,t,a,o)   { s, t, a, o, 1, 1, AT_START, 0 }
+/** An item that must appear exactly once, at the end of the document */
+#define T1_END(s,t,a,o)   { s, t, a, o, 1, 1, AT_END, 0 }
+/** An item that must appear one or more times */
+#define T1N(s,t,a,o)  { s, t, a, o, 1, INT_MAX, 0, 0 }
+/** An item that must appear no more than once */
+#define T01(s,t,a,o)  { s, t, a, o, 0, 1, 0, 0 }
+/** An annotation that must appear no more than once */
+#define A01(s,t,a,o)  { s, t, a, o, 0, 1, 0, 1 }
+
+/** Argument multiplicity: any number of arguments. */
+#define ARGS        0,INT_MAX,0
+/** Argument multiplicity: no arguments. */
+#define NO_ARGS     0,0,0
+/** Argument multiplicity: concatenate all arguments. */
+#define CONCAT_ARGS 1,1,1
+/** Argument multiplicity: at least <b>n</b> arguments. */
+#define GE(n)       n,INT_MAX,0
+/** Argument multiplicity: exactly <b>n</b> arguments. */
+#define EQ(n)       n,n,0
+/**@}*/
+
+/** Determines the parsing rules for a single token type. */
+typedef struct token_rule_t {
+  /** The string value of the keyword identifying the type of item. */
+  const char *t;
+  /** The corresponding directory_keyword enum. */
+  directory_keyword v;
+  /** Minimum number of arguments for this item */
+  int min_args;
+  /** Maximum number of arguments for this item */
+  int max_args;
+  /** If true, we concatenate all arguments for this item into a single
+   * string. */
+  int concat_args;
+  /** Requirements on object syntax for this item. */
+  obj_syntax os;
+  /** Lowest number of times this item may appear in a document. */
+  int min_cnt;
+  /** Highest number of times this item may appear in a document. */
+  int max_cnt;
+  /** One or more of AT_START/AT_END to limit where the item may appear in a
+   * document. */
+  int pos;
+  /** True iff this token is an annotation. */
+  int is_annotation;
+} token_rule_t;
+
+void token_clear(directory_token_t *tok);
+
+int tokenize_string(memarea_t *area,
+                    const char *start, const char *end,
+                    smartlist_t *out,
+                    token_rule_t *table,
+                    int flags);
+directory_token_t *get_next_token(memarea_t *area,
+                                  const char **s,
+                                  const char *eos,
+                                  token_rule_t *table);
+
+directory_token_t *find_by_keyword_(smartlist_t *s,
+                                    directory_keyword keyword,
+                                    const char *keyword_str);
+
+#define find_by_keyword(s, keyword) \
+  find_by_keyword_((s), (keyword), #keyword)
+
+directory_token_t *find_opt_by_keyword(smartlist_t *s,
+                                       directory_keyword keyword);
+smartlist_t * find_all_by_keyword(smartlist_t *s, directory_keyword k);
+
+#endif /* TOR_PARSECOMMON_H */
+
diff --git a/src/or/relay.c b/src/or/relay.c
index 99750af975..8d48239e47 100644
--- a/src/or/relay.c
+++ b/src/or/relay.c
@@ -60,6 +60,7 @@
 #include "connection_or.h"
 #include "control.h"
 #include "geoip.h"
+#include "hs_cache.h"
 #include "main.h"
 #include "networkstatus.h"
 #include "nodelist.h"
@@ -2439,9 +2440,7 @@ cell_queues_check_size(void)
       if (rend_cache_total > get_options()->MaxMemInQueues / 5) {
         const size_t bytes_to_remove =
           rend_cache_total - (size_t)(get_options()->MaxMemInQueues / 10);
-        rend_cache_clean_v2_descs_as_dir(time(NULL), bytes_to_remove);
-        alloc -= rend_cache_total;
-        alloc += rend_cache_get_total_allocation();
+        alloc -= hs_cache_handle_oom(time(NULL), bytes_to_remove);
       }
       circuits_handle_oom(alloc);
       return 1;
diff --git a/src/or/rendcache.c b/src/or/rendcache.c
index e61a96b677..bf43407289 100644
--- a/src/or/rendcache.c
+++ b/src/or/rendcache.c
@@ -86,7 +86,7 @@ rend_cache_get_total_allocation(void)
 }
 
 /** Decrement the total bytes attributed to the rendezvous cache by n. */
-STATIC void
+void
 rend_cache_decrement_allocation(size_t n)
 {
   static int have_underflowed = 0;
@@ -103,7 +103,7 @@ rend_cache_decrement_allocation(size_t n)
 }
 
 /** Increase the total bytes attributed to the rendezvous cache by n. */
-STATIC void
+void
 rend_cache_increment_allocation(size_t n)
 {
   static int have_overflowed = 0;
@@ -462,45 +462,36 @@ rend_cache_intro_failure_note(rend_intro_point_failure_t failure,
 }
 
 /** Remove all old v2 descriptors and those for which this hidden service
- * directory is not responsible for any more.
- *
- * If at all possible, remove at least <b>force_remove</b> bytes of data.
- */
-void
-rend_cache_clean_v2_descs_as_dir(time_t now, size_t force_remove)
+ * directory is not responsible for any more. The cutoff is the time limit for
+ * which we want to keep the cache entry. In other words, any entry created
+ * before will be removed. */
+size_t
+rend_cache_clean_v2_descs_as_dir(time_t cutoff)
 {
   digestmap_iter_t *iter;
-  time_t cutoff = now - REND_CACHE_MAX_AGE - REND_CACHE_MAX_SKEW;
-  const int LAST_SERVED_CUTOFF_STEP = 1800;
-  time_t last_served_cutoff = cutoff;
   size_t bytes_removed = 0;
-  do {
-    for (iter = digestmap_iter_init(rend_cache_v2_dir);
-         !digestmap_iter_done(iter); ) {
-      const char *key;
-      void *val;
-      rend_cache_entry_t *ent;
-      digestmap_iter_get(iter, &key, &val);
-      ent = val;
-      if (ent->parsed->timestamp < cutoff ||
-          ent->last_served < last_served_cutoff) {
-        char key_base32[REND_DESC_ID_V2_LEN_BASE32 + 1];
-        base32_encode(key_base32, sizeof(key_base32), key, DIGEST_LEN);
-        log_info(LD_REND, "Removing descriptor with ID '%s' from cache",
-                 safe_str_client(key_base32));
-        bytes_removed += rend_cache_entry_allocation(ent);
-        iter = digestmap_iter_next_rmv(rend_cache_v2_dir, iter);
-        rend_cache_entry_free(ent);
-      } else {
-        iter = digestmap_iter_next(rend_cache_v2_dir, iter);
-      }
+
+  for (iter = digestmap_iter_init(rend_cache_v2_dir);
+       !digestmap_iter_done(iter); ) {
+    const char *key;
+    void *val;
+    rend_cache_entry_t *ent;
+    digestmap_iter_get(iter, &key, &val);
+    ent = val;
+    if (ent->parsed->timestamp < cutoff) {
+      char key_base32[REND_DESC_ID_V2_LEN_BASE32 + 1];
+      base32_encode(key_base32, sizeof(key_base32), key, DIGEST_LEN);
+      log_info(LD_REND, "Removing descriptor with ID '%s' from cache",
+               safe_str_client(key_base32));
+      bytes_removed += rend_cache_entry_allocation(ent);
+      iter = digestmap_iter_next_rmv(rend_cache_v2_dir, iter);
+      rend_cache_entry_free(ent);
+    } else {
+      iter = digestmap_iter_next(rend_cache_v2_dir, iter);
     }
+  }
 
-    /* In case we didn't remove enough bytes, advance the cutoff a little. */
-    last_served_cutoff += LAST_SERVED_CUTOFF_STEP;
-    if (last_served_cutoff > now)
-      break;
-  } while (bytes_removed < force_remove);
+  return bytes_removed;
 }
 
 /** Lookup in the client cache the given service ID <b>query</b> for
@@ -849,6 +840,8 @@ rend_cache_store_v2_desc_as_client(const char *desc,
   char want_desc_id[DIGEST_LEN];
   rend_cache_entry_t *e;
   int retval = -1;
+  rend_data_v2_t *rend_data = TO_REND_DATA_V2(rend_query);
+
   tor_assert(rend_cache);
   tor_assert(desc);
   tor_assert(desc_id_base32);
@@ -874,11 +867,11 @@ rend_cache_store_v2_desc_as_client(const char *desc,
     log_warn(LD_REND, "Couldn't compute service ID.");
     goto err;
   }
-  if (rend_query->onion_address[0] != '\0' &&
-      strcmp(rend_query->onion_address, service_id)) {
+  if (rend_data->onion_address[0] != '\0' &&
+      strcmp(rend_data->onion_address, service_id)) {
     log_warn(LD_REND, "Received service descriptor for service ID %s; "
              "expected descriptor for service ID %s.",
-             service_id, safe_str(rend_query->onion_address));
+             service_id, safe_str(rend_data->onion_address));
     goto err;
   }
   if (tor_memneq(desc_id, want_desc_id, DIGEST_LEN)) {
@@ -890,14 +883,14 @@ rend_cache_store_v2_desc_as_client(const char *desc,
   /* Decode/decrypt introduction points. */
   if (intro_content && intro_size > 0) {
     int n_intro_points;
-    if (rend_query->auth_type != REND_NO_AUTH &&
-        !tor_mem_is_zero(rend_query->descriptor_cookie,
-                         sizeof(rend_query->descriptor_cookie))) {
+    if (rend_data->auth_type != REND_NO_AUTH &&
+        !tor_mem_is_zero(rend_data->descriptor_cookie,
+                         sizeof(rend_data->descriptor_cookie))) {
       char *ipos_decrypted = NULL;
       size_t ipos_decrypted_size;
       if (rend_decrypt_introduction_points(&ipos_decrypted,
                                            &ipos_decrypted_size,
-                                           rend_query->descriptor_cookie,
+                                           rend_data->descriptor_cookie,
                                            intro_content,
                                            intro_size) < 0) {
         log_warn(LD_REND, "Failed to decrypt introduction points. We are "
diff --git a/src/or/rendcache.h b/src/or/rendcache.h
index 270b614c38..746f142fcc 100644
--- a/src/or/rendcache.h
+++ b/src/or/rendcache.h
@@ -53,10 +53,17 @@ typedef enum {
   REND_CACHE_TYPE_SERVICE = 2,
 } rend_cache_type_t;
 
+/* Return maximum lifetime in seconds of a cache entry. */
+static inline time_t
+rend_cache_max_entry_lifetime(void)
+{
+  return REND_CACHE_MAX_AGE + REND_CACHE_MAX_SKEW;
+}
+
 void rend_cache_init(void);
 void rend_cache_clean(time_t now, rend_cache_type_t cache_type);
 void rend_cache_failure_clean(time_t now);
-void rend_cache_clean_v2_descs_as_dir(time_t now, size_t min_to_remove);
+size_t rend_cache_clean_v2_descs_as_dir(time_t cutoff);
 void rend_cache_purge(void);
 void rend_cache_free_all(void);
 int rend_cache_lookup_entry(const char *query, int version,
@@ -77,6 +84,8 @@ void rend_cache_intro_failure_note(rend_intro_point_failure_t failure,
                                    const uint8_t *identity,
                                    const char *service_id);
 void rend_cache_failure_purge(void);
+void rend_cache_decrement_allocation(size_t n);
+void rend_cache_increment_allocation(size_t n);
 
 #ifdef RENDCACHE_PRIVATE
 
@@ -89,8 +98,6 @@ STATIC int cache_failure_intro_lookup(const uint8_t *identity,
                                       const char *service_id,
                                       rend_cache_failure_intro_t
                                       **intro_entry);
-STATIC void rend_cache_decrement_allocation(size_t n);
-STATIC void rend_cache_increment_allocation(size_t n);
 STATIC rend_cache_failure_intro_t *rend_cache_failure_intro_entry_new(
                                       rend_intro_point_failure_t failure);
 STATIC rend_cache_failure_t *rend_cache_failure_entry_new(void);
diff --git a/src/or/rendclient.c b/src/or/rendclient.c
index a93bc94a9c..b0dcf52507 100644
--- a/src/or/rendclient.c
+++ b/src/or/rendclient.c
@@ -16,6 +16,7 @@
 #include "connection.h"
 #include "connection_edge.h"
 #include "directory.h"
+#include "hs_common.h"
 #include "main.h"
 #include "networkstatus.h"
 #include "nodelist.h"
@@ -104,7 +105,7 @@ rend_client_reextend_intro_circuit(origin_circuit_t *circ)
   if (!extend_info) {
     log_warn(LD_REND,
              "No usable introduction points left for %s. Closing.",
-             safe_str_client(circ->rend_data->onion_address));
+             safe_str_client(rend_data_get_address(circ->rend_data)));
     circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_INTERNAL);
     return -1;
   }
@@ -144,18 +145,19 @@ rend_client_send_introduction(origin_circuit_t *introcirc,
   off_t dh_offset;
   crypto_pk_t *intro_key = NULL;
   int status = 0;
+  const char *onion_address;
 
   tor_assert(introcirc->base_.purpose == CIRCUIT_PURPOSE_C_INTRODUCING);
   tor_assert(rendcirc->base_.purpose == CIRCUIT_PURPOSE_C_REND_READY);
   tor_assert(introcirc->rend_data);
   tor_assert(rendcirc->rend_data);
-  tor_assert(!rend_cmp_service_ids(introcirc->rend_data->onion_address,
-                                   rendcirc->rend_data->onion_address));
+  tor_assert(!rend_cmp_service_ids(rend_data_get_address(introcirc->rend_data),
+                                  rend_data_get_address(rendcirc->rend_data)));
   assert_circ_anonymity_ok(introcirc, options);
   assert_circ_anonymity_ok(rendcirc, options);
+  onion_address = rend_data_get_address(introcirc->rend_data);
 
-  r = rend_cache_lookup_entry(introcirc->rend_data->onion_address, -1,
-                              &entry);
+  r = rend_cache_lookup_entry(onion_address, -1, &entry);
   /* An invalid onion address is not possible else we have a big issue. */
   tor_assert(r != -EINVAL);
   if (r < 0 || !rend_client_any_intro_points_usable(entry)) {
@@ -164,14 +166,13 @@ rend_client_send_introduction(origin_circuit_t *introcirc,
     log_info(LD_REND,
              "query %s didn't have valid rend desc in cache. "
              "Refetching descriptor.",
-             safe_str_client(introcirc->rend_data->onion_address));
+             safe_str_client(onion_address));
     rend_client_refetch_v2_renddesc(introcirc->rend_data);
     {
       connection_t *conn;
 
       while ((conn = connection_get_by_type_state_rendquery(CONN_TYPE_AP,
-                       AP_CONN_STATE_CIRCUIT_WAIT,
-                       introcirc->rend_data->onion_address))) {
+                       AP_CONN_STATE_CIRCUIT_WAIT, onion_address))) {
         connection_ap_mark_as_non_pending_circuit(TO_ENTRY_CONN(conn));
         conn->state = AP_CONN_STATE_RENDDESC_WAIT;
       }
@@ -195,7 +196,7 @@ rend_client_send_introduction(origin_circuit_t *introcirc,
     log_info(LD_REND, "Could not find intro key for %s at %s; we "
              "have a v2 rend desc with %d intro points. "
              "Trying a different intro point...",
-             safe_str_client(introcirc->rend_data->onion_address),
+             safe_str_client(onion_address),
              safe_str_client(extend_info_describe(
                                    introcirc->build_state->chosen_exit)),
              smartlist_len(entry->parsed->intro_nodes));
@@ -235,11 +236,12 @@ rend_client_send_introduction(origin_circuit_t *introcirc,
   /* If version is 3, write (optional) auth data and timestamp. */
   if (entry->parsed->protocols & (1<<3)) {
     tmp[0] = 3; /* version 3 of the cell format */
-    tmp[1] = (uint8_t)introcirc->rend_data->auth_type; /* auth type, if any */
+    /* auth type, if any */
+    tmp[1] = (uint8_t) TO_REND_DATA_V2(introcirc->rend_data)->auth_type;
     v3_shift = 1;
-    if (introcirc->rend_data->auth_type != REND_NO_AUTH) {
+    if (tmp[1] != REND_NO_AUTH) {
       set_uint16(tmp+2, htons(REND_DESC_COOKIE_LEN));
-      memcpy(tmp+4, introcirc->rend_data->descriptor_cookie,
+      memcpy(tmp+4, TO_REND_DATA_V2(introcirc->rend_data)->descriptor_cookie,
              REND_DESC_COOKIE_LEN);
       v3_shift += 2+REND_DESC_COOKIE_LEN;
     }
@@ -359,7 +361,7 @@ rend_client_rendcirc_has_opened(origin_circuit_t *circ)
  * Called to close other intro circuits we launched in parallel.
  */
 static void
-rend_client_close_other_intros(const char *onion_address)
+rend_client_close_other_intros(const uint8_t *rend_pk_digest)
 {
   /* abort parallel intro circs, if any */
   SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t *, c) {
@@ -368,8 +370,7 @@ rend_client_close_other_intros(const char *onion_address)
         !c->marked_for_close && CIRCUIT_IS_ORIGIN(c)) {
       origin_circuit_t *oc = TO_ORIGIN_CIRCUIT(c);
       if (oc->rend_data &&
-          !rend_cmp_service_ids(onion_address,
-                                oc->rend_data->onion_address)) {
+          rend_circuit_pk_digest_eq(oc, rend_pk_digest)) {
         log_info(LD_REND|LD_CIRC, "Closing introduction circuit %d that we "
                  "built in parallel (Purpose %d).", oc->global_identifier,
                  c->purpose);
@@ -431,7 +432,8 @@ rend_client_introduction_acked(origin_circuit_t *circ,
     circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_FINISHED);
 
     /* close any other intros launched in parallel */
-    rend_client_close_other_intros(circ->rend_data->onion_address);
+    rend_client_close_other_intros(rend_data_get_pk_digest(circ->rend_data,
+                                                           NULL));
   } else {
     /* It's a NAK; the introduction point didn't relay our request. */
     circuit_change_purpose(TO_CIRCUIT(circ), CIRCUIT_PURPOSE_C_INTRODUCING);
@@ -440,7 +442,7 @@ rend_client_introduction_acked(origin_circuit_t *circ,
      * If none remain, refetch the service descriptor.
      */
     log_info(LD_REND, "Got nack for %s from %s...",
-        safe_str_client(circ->rend_data->onion_address),
+        safe_str_client(rend_data_get_address(circ->rend_data)),
         safe_str_client(extend_info_describe(circ->build_state->chosen_exit)));
     if (rend_client_report_intro_point_failure(circ->build_state->chosen_exit,
                                              circ->rend_data,
@@ -694,13 +696,15 @@ pick_hsdir(const char *desc_id, const char *desc_id_base32)
  * in the case that no hidden service directory is left to ask for the
  * descriptor, return 0, and in case of a failure -1.  */
 static int
-directory_get_from_hs_dir(const char *desc_id, const rend_data_t *rend_query,
+directory_get_from_hs_dir(const char *desc_id,
+                          const rend_data_t *rend_query,
                           routerstatus_t *rs_hsdir)
 {
   routerstatus_t *hs_dir = rs_hsdir;
   char *hsdir_fp;
   char desc_id_base32[REND_DESC_ID_V2_LEN_BASE32 + 1];
   char descriptor_cookie_base64[3*REND_DESC_COOKIE_LEN_BASE64];
+  const rend_data_v2_t *rend_data;
 #ifdef ENABLE_TOR2WEB_MODE
   const int tor2web_mode = get_options()->Tor2webMode;
   const int how_to_fetch = tor2web_mode ? DIRIND_ONEHOP : DIRIND_ANONYMOUS;
@@ -709,6 +713,8 @@ directory_get_from_hs_dir(const char *desc_id, const rend_data_t *rend_query,
 #endif
 
   tor_assert(desc_id);
+  tor_assert(rend_query);
+  rend_data = TO_REND_DATA_V2(rend_query);
 
   base32_encode(desc_id_base32, sizeof(desc_id_base32),
                 desc_id, DIGEST_LEN);
@@ -731,10 +737,11 @@ directory_get_from_hs_dir(const char *desc_id, const rend_data_t *rend_query,
   /* Encode descriptor cookie for logging purposes. Also, if the cookie is
    * malformed, no fetch is triggered thus this needs to be done before the
    * fetch request. */
-  if (rend_query->auth_type != REND_NO_AUTH) {
+  if (rend_data->auth_type != REND_NO_AUTH) {
     if (base64_encode(descriptor_cookie_base64,
                       sizeof(descriptor_cookie_base64),
-                      rend_query->descriptor_cookie, REND_DESC_COOKIE_LEN,
+                      rend_data->descriptor_cookie,
+                      REND_DESC_COOKIE_LEN,
                       0)<0) {
       log_warn(LD_BUG, "Could not base64-encode descriptor cookie.");
       return 0;
@@ -760,9 +767,9 @@ directory_get_from_hs_dir(const char *desc_id, const rend_data_t *rend_query,
                     "service '%s' with descriptor ID '%s', auth type %d, "
                     "and descriptor cookie '%s' to hidden service "
                     "directory %s",
-           rend_query->onion_address, desc_id_base32,
-           rend_query->auth_type,
-           (rend_query->auth_type == REND_NO_AUTH ? "[none]" :
+           rend_data->onion_address, desc_id_base32,
+           rend_data->auth_type,
+           (rend_data->auth_type == REND_NO_AUTH ? "[none]" :
             escaped_safe_str_client(descriptor_cookie_base64)),
            routerstatus_describe(hs_dir));
   control_event_hs_descriptor_requested(rend_query,
@@ -777,8 +784,8 @@ directory_get_from_hs_dir(const char *desc_id, const rend_data_t *rend_query,
  * On success, 1 is returned. If no hidden service is left to ask, return 0.
  * On error, -1 is returned. */
 static int
-fetch_v2_desc_by_descid(const char *desc_id, const rend_data_t *rend_query,
-                        smartlist_t *hsdirs)
+fetch_v2_desc_by_descid(const char *desc_id,
+                        const rend_data_t *rend_query, smartlist_t *hsdirs)
 {
   int ret;
 
@@ -811,13 +818,12 @@ fetch_v2_desc_by_descid(const char *desc_id, const rend_data_t *rend_query,
  * On success, 1 is returned. If no hidden service is left to ask, return 0.
  * On error, -1 is returned. */
 static int
-fetch_v2_desc_by_addr(rend_data_t *query, smartlist_t *hsdirs)
+fetch_v2_desc_by_addr(rend_data_t *rend_query, smartlist_t *hsdirs)
 {
   char descriptor_id[DIGEST_LEN];
   int replicas_left_to_try[REND_NUMBER_OF_NON_CONSECUTIVE_REPLICAS];
   int i, tries_left, ret;
-
-  tor_assert(query);
+  rend_data_v2_t *rend_data = TO_REND_DATA_V2(rend_query);
 
   /* Randomly iterate over the replicas until a descriptor can be fetched
    * from one of the consecutive nodes, or no options are left. */
@@ -831,9 +837,10 @@ fetch_v2_desc_by_addr(rend_data_t *query, smartlist_t *hsdirs)
     int chosen_replica = replicas_left_to_try[rand_val];
     replicas_left_to_try[rand_val] = replicas_left_to_try[--tries_left];
 
-    ret = rend_compute_v2_desc_id(descriptor_id, query->onion_address,
-                                  query->auth_type == REND_STEALTH_AUTH ?
-                                  query->descriptor_cookie : NULL,
+    ret = rend_compute_v2_desc_id(descriptor_id,
+                                  rend_data->onion_address,
+                                  rend_data->auth_type == REND_STEALTH_AUTH ?
+                                    rend_data->descriptor_cookie : NULL,
                                   time(NULL), chosen_replica);
     if (ret < 0) {
       /* Normally, on failure the descriptor_id is untouched but let's be
@@ -841,18 +848,18 @@ fetch_v2_desc_by_addr(rend_data_t *query, smartlist_t *hsdirs)
       goto end;
     }
 
-    if (tor_memcmp(descriptor_id, query->descriptor_id[chosen_replica],
+    if (tor_memcmp(descriptor_id, rend_data->descriptor_id[chosen_replica],
                    sizeof(descriptor_id)) != 0) {
       /* Not equal from what we currently have so purge the last hid serv
        * request cache and update the descriptor ID with the new value. */
       purge_hid_serv_from_last_hid_serv_requests(
-                                        query->descriptor_id[chosen_replica]);
-      memcpy(query->descriptor_id[chosen_replica], descriptor_id,
-             sizeof(query->descriptor_id[chosen_replica]));
+                                     rend_data->descriptor_id[chosen_replica]);
+      memcpy(rend_data->descriptor_id[chosen_replica], descriptor_id,
+             sizeof(rend_data->descriptor_id[chosen_replica]));
     }
 
     /* Trigger the fetch with the computed descriptor ID. */
-    ret = fetch_v2_desc_by_descid(descriptor_id, query, hsdirs);
+    ret = fetch_v2_desc_by_descid(descriptor_id, rend_query, hsdirs);
     if (ret != 0) {
       /* Either on success or failure, as long as we tried a fetch we are
        * done here. */
@@ -880,16 +887,23 @@ int
 rend_client_fetch_v2_desc(rend_data_t *query, smartlist_t *hsdirs)
 {
   int ret;
+  rend_data_v2_t *rend_data;
+  const char *onion_address;
 
   tor_assert(query);
 
+  /* Get the version 2 data structure of the query. */
+  rend_data = TO_REND_DATA_V2(query);
+  onion_address = rend_data_get_address(query);
+
   /* Depending on what's available in the rend data query object, we will
    * trigger a fetch by HS address or using a descriptor ID. */
 
-  if (query->onion_address[0] != '\0') {
+  if (onion_address[0] != '\0') {
     ret = fetch_v2_desc_by_addr(query, hsdirs);
-  } else if (!tor_digest_is_zero(query->desc_id_fetch)) {
-    ret = fetch_v2_desc_by_descid(query->desc_id_fetch, query, hsdirs);
+  } else if (!tor_digest_is_zero(rend_data->desc_id_fetch)) {
+    ret = fetch_v2_desc_by_descid(rend_data->desc_id_fetch, query,
+                                  hsdirs);
   } else {
     /* Query data is invalid. */
     ret = -1;
@@ -907,10 +921,11 @@ void
 rend_client_refetch_v2_renddesc(rend_data_t *rend_query)
 {
   rend_cache_entry_t *e = NULL;
+  const char *onion_address = rend_data_get_address(rend_query);
 
   tor_assert(rend_query);
   /* Before fetching, check if we already have a usable descriptor here. */
-  if (rend_cache_lookup_entry(rend_query->onion_address, -1, &e) == 0 &&
+  if (rend_cache_lookup_entry(onion_address, -1, &e) == 0 &&
       rend_client_any_intro_points_usable(e)) {
     log_info(LD_REND, "We would fetch a v2 rendezvous descriptor, but we "
                       "already have a usable descriptor here. Not fetching.");
@@ -923,7 +938,7 @@ rend_client_refetch_v2_renddesc(rend_data_t *rend_query)
     return;
   }
   log_debug(LD_REND, "Fetching v2 rendezvous descriptor for service %s",
-            safe_str_client(rend_query->onion_address));
+            safe_str_client(onion_address));
 
   rend_client_fetch_v2_desc(rend_query, NULL);
   /* We don't need to look the error code because either on failure or
@@ -959,7 +974,7 @@ rend_client_cancel_descriptor_fetches(void)
       } else {
         log_debug(LD_REND, "Marking for close dir conn fetching "
                   "rendezvous descriptor for service %s",
-                  safe_str(rd->onion_address));
+                  safe_str(rend_data_get_address(rd)));
       }
       connection_mark_for_close(conn);
     }
@@ -989,25 +1004,26 @@ rend_client_cancel_descriptor_fetches(void)
  */
 int
 rend_client_report_intro_point_failure(extend_info_t *failed_intro,
-                                       rend_data_t *rend_query,
+                                       rend_data_t *rend_data,
                                        unsigned int failure_type)
 {
   int i, r;
   rend_cache_entry_t *ent;
   connection_t *conn;
+  const char *onion_address = rend_data_get_address(rend_data);
 
-  r = rend_cache_lookup_entry(rend_query->onion_address, -1, &ent);
+  r = rend_cache_lookup_entry(onion_address, -1, &ent);
   if (r < 0) {
     /* Either invalid onion address or cache entry not found. */
     switch (-r) {
     case EINVAL:
       log_warn(LD_BUG, "Malformed service ID %s.",
-          escaped_safe_str_client(rend_query->onion_address));
+               escaped_safe_str_client(onion_address));
       return -1;
     case ENOENT:
       log_info(LD_REND, "Unknown service %s. Re-fetching descriptor.",
-          escaped_safe_str_client(rend_query->onion_address));
-      rend_client_refetch_v2_renddesc(rend_query);
+               escaped_safe_str_client(onion_address));
+      rend_client_refetch_v2_renddesc(rend_data);
       return 0;
     default:
       log_warn(LD_BUG, "Unknown cache lookup returned code: %d", r);
@@ -1031,7 +1047,7 @@ rend_client_report_intro_point_failure(extend_info_t *failed_intro,
       case INTRO_POINT_FAILURE_GENERIC:
         rend_cache_intro_failure_note(failure_type,
                                       (uint8_t *)failed_intro->identity_digest,
-                                      rend_query->onion_address);
+                                      onion_address);
         rend_intro_point_free(intro);
         smartlist_del(ent->parsed->intro_nodes, i);
         break;
@@ -1049,8 +1065,7 @@ rend_client_report_intro_point_failure(extend_info_t *failed_intro,
           if (zap_intro_point) {
             rend_cache_intro_failure_note(
                 failure_type,
-                (uint8_t *) failed_intro->identity_digest,
-                rend_query->onion_address);
+                (uint8_t *) failed_intro->identity_digest, onion_address);
             rend_intro_point_free(intro);
             smartlist_del(ent->parsed->intro_nodes, i);
           }
@@ -1064,14 +1079,14 @@ rend_client_report_intro_point_failure(extend_info_t *failed_intro,
   if (! rend_client_any_intro_points_usable(ent)) {
     log_info(LD_REND,
              "No more intro points remain for %s. Re-fetching descriptor.",
-             escaped_safe_str_client(rend_query->onion_address));
-    rend_client_refetch_v2_renddesc(rend_query);
+             escaped_safe_str_client(onion_address));
+    rend_client_refetch_v2_renddesc(rend_data);
 
     /* move all pending streams back to renddesc_wait */
     /* NOTE: We can now do this faster, if we use pending_entry_connections */
     while ((conn = connection_get_by_type_state_rendquery(CONN_TYPE_AP,
                                    AP_CONN_STATE_CIRCUIT_WAIT,
-                                   rend_query->onion_address))) {
+                                   onion_address))) {
       connection_ap_mark_as_non_pending_circuit(TO_ENTRY_CONN(conn));
       conn->state = AP_CONN_STATE_RENDDESC_WAIT;
     }
@@ -1080,7 +1095,7 @@ rend_client_report_intro_point_failure(extend_info_t *failed_intro,
   }
   log_info(LD_REND,"%d options left for %s.",
            smartlist_len(ent->parsed->intro_nodes),
-           escaped_safe_str_client(rend_query->onion_address));
+           escaped_safe_str_client(onion_address));
   return 1;
 }
 
@@ -1221,10 +1236,11 @@ rend_client_desc_trynow(const char *query)
     rend_data = ENTRY_TO_EDGE_CONN(conn)->rend_data;
     if (!rend_data)
       continue;
-    if (rend_cmp_service_ids(query, rend_data->onion_address))
+    const char *onion_address = rend_data_get_address(rend_data);
+    if (rend_cmp_service_ids(query, onion_address))
       continue;
     assert_connection_ok(base_conn, now);
-    if (rend_cache_lookup_entry(rend_data->onion_address, -1,
+    if (rend_cache_lookup_entry(onion_address, -1,
                                 &entry) == 0 &&
         rend_client_any_intro_points_usable(entry)) {
       /* either this fetch worked, or it failed but there was a
@@ -1259,11 +1275,12 @@ rend_client_note_connection_attempt_ended(const rend_data_t *rend_data)
 {
   unsigned int have_onion = 0;
   rend_cache_entry_t *cache_entry = NULL;
+  const char *onion_address = rend_data_get_address(rend_data);
+  rend_data_v2_t *rend_data_v2 = TO_REND_DATA_V2(rend_data);
 
-  if (*rend_data->onion_address != '\0') {
+  if (onion_address[0] != '\0') {
     /* Ignore return value; we find an entry, or we don't. */
-    (void) rend_cache_lookup_entry(rend_data->onion_address, -1,
-                                   &cache_entry);
+    (void) rend_cache_lookup_entry(onion_address, -1, &cache_entry);
     have_onion = 1;
   }
 
@@ -1277,17 +1294,17 @@ rend_client_note_connection_attempt_ended(const rend_data_t *rend_data)
   /* Remove the HS's entries in last_hid_serv_requests. */
   if (have_onion) {
     unsigned int replica;
-    for (replica = 0; replica < ARRAY_LENGTH(rend_data->descriptor_id);
+    for (replica = 0; replica < ARRAY_LENGTH(rend_data_v2->descriptor_id);
          replica++) {
-      const char *desc_id = rend_data->descriptor_id[replica];
+      const char *desc_id = rend_data_v2->descriptor_id[replica];
       purge_hid_serv_from_last_hid_serv_requests(desc_id);
     }
     log_info(LD_REND, "Connection attempt for %s has ended; "
              "cleaning up temporary state.",
-             safe_str_client(rend_data->onion_address));
+             safe_str_client(onion_address));
   } else {
     /* We only have an ID for a fetch. Probably used by HSFETCH. */
-    purge_hid_serv_from_last_hid_serv_requests(rend_data->desc_id_fetch);
+    purge_hid_serv_from_last_hid_serv_requests(rend_data_v2->desc_id_fetch);
   }
 }
 
@@ -1301,12 +1318,13 @@ rend_client_get_random_intro(const rend_data_t *rend_query)
   int ret;
   extend_info_t *result;
   rend_cache_entry_t *entry;
+  const char *onion_address = rend_data_get_address(rend_query);
 
-  ret = rend_cache_lookup_entry(rend_query->onion_address, -1, &entry);
+  ret = rend_cache_lookup_entry(onion_address, -1, &entry);
   if (ret < 0 || !rend_client_any_intro_points_usable(entry)) {
     log_warn(LD_REND,
              "Query '%s' didn't have valid rend desc in cache. Failing.",
-             safe_str_client(rend_query->onion_address));
+             safe_str_client(onion_address));
     /* XXX: Should we refetch the descriptor here if the IPs are not usable
      * anymore ?. */
     return NULL;
diff --git a/src/or/rendclient.h b/src/or/rendclient.h
index b8f8c2f871..164305a773 100644
--- a/src/or/rendclient.h
+++ b/src/or/rendclient.h
@@ -27,7 +27,7 @@ void rend_client_cancel_descriptor_fetches(void);
 void rend_client_purge_last_hid_serv_requests(void);
 
 int rend_client_report_intro_point_failure(extend_info_t *failed_intro,
-                                           rend_data_t *rend_query,
+                                           rend_data_t *rend_data,
                                            unsigned int failure_type);
 
 int rend_client_rendezvous_acked(origin_circuit_t *circ,
diff --git a/src/or/rendcommon.c b/src/or/rendcommon.c
index d9d39b1f19..1e5d1ab121 100644
--- a/src/or/rendcommon.c
+++ b/src/or/rendcommon.c
@@ -12,6 +12,7 @@
 #include "circuitbuild.h"
 #include "config.h"
 #include "control.h"
+#include "hs_common.h"
 #include "rendclient.h"
 #include "rendcommon.h"
 #include "rendmid.h"
@@ -804,124 +805,6 @@ rend_process_relay_cell(circuit_t *circ, const crypt_path_t *layer_hint,
              command);
 }
 
-/** Allocate and return a new rend_data_t with the same
- * contents as <b>query</b>. */
-rend_data_t *
-rend_data_dup(const rend_data_t *data)
-{
-  rend_data_t *data_dup;
-  tor_assert(data);
-  data_dup = tor_memdup(data, sizeof(rend_data_t));
-  data_dup->hsdirs_fp = smartlist_new();
-  SMARTLIST_FOREACH(data->hsdirs_fp, char *, fp,
-                    smartlist_add(data_dup->hsdirs_fp,
-                                  tor_memdup(fp, DIGEST_LEN)));
-  return data_dup;
-}
-
-/** Compute descriptor ID for each replicas and save them. A valid onion
- * address must be present in the <b>rend_data</b>.
- *
- * Return 0 on success else -1. */
-static int
-compute_desc_id(rend_data_t *rend_data)
-{
-  int ret = 0;
-  unsigned replica;
-  time_t now = time(NULL);
-
-  tor_assert(rend_data);
-
-  /* Compute descriptor ID for each replicas. */
-  for (replica = 0; replica < ARRAY_LENGTH(rend_data->descriptor_id);
-       replica++) {
-    ret = rend_compute_v2_desc_id(rend_data->descriptor_id[replica],
-                                  rend_data->onion_address,
-                                  rend_data->descriptor_cookie,
-                                  now, replica);
-    if (ret < 0) {
-      goto end;
-    }
-  }
-
- end:
-  return ret;
-}
-
-/** Allocate and initialize a rend_data_t object for a service using the
- * given arguments. Only the <b>onion_address</b> is not optional.
- *
- * Return a valid rend_data_t pointer. */
-rend_data_t *
-rend_data_service_create(const char *onion_address, const char *pk_digest,
-                         const uint8_t *cookie, rend_auth_type_t auth_type)
-{
-  rend_data_t *rend_data = tor_malloc_zero(sizeof(*rend_data));
-
-  /* We need at least one else the call is wrong. */
-  tor_assert(onion_address != NULL);
-
-  if (pk_digest) {
-    memcpy(rend_data->rend_pk_digest, pk_digest,
-           sizeof(rend_data->rend_pk_digest));
-  }
-  if (cookie) {
-    memcpy(rend_data->rend_cookie, cookie,
-           sizeof(rend_data->rend_cookie));
-  }
-
-  strlcpy(rend_data->onion_address, onion_address,
-          sizeof(rend_data->onion_address));
-  rend_data->auth_type = auth_type;
-  /* Won't be used but still need to initialize it for rend_data dup and
-   * free. */
-  rend_data->hsdirs_fp = smartlist_new();
-
-  return rend_data;
-}
-
-/** Allocate and initialize a rend_data_t object for a client request using
- * the given arguments.  Either an onion address or a descriptor ID is
- * needed. Both can be given but only the onion address will be used to make
- * the descriptor fetch.
- *
- * Return a valid rend_data_t pointer or NULL on error meaning the
- * descriptor IDs couldn't be computed from the given data. */
-rend_data_t *
-rend_data_client_create(const char *onion_address, const char *desc_id,
-                        const char *cookie, rend_auth_type_t auth_type)
-{
-  rend_data_t *rend_data = tor_malloc_zero(sizeof(*rend_data));
-
-  /* We need at least one else the call is wrong. */
-  tor_assert(onion_address != NULL || desc_id != NULL);
-
-  if (cookie) {
-    memcpy(rend_data->descriptor_cookie, cookie,
-           sizeof(rend_data->descriptor_cookie));
-  }
-  if (desc_id) {
-    memcpy(rend_data->desc_id_fetch, desc_id,
-           sizeof(rend_data->desc_id_fetch));
-  }
-  if (onion_address) {
-    strlcpy(rend_data->onion_address, onion_address,
-            sizeof(rend_data->onion_address));
-    if (compute_desc_id(rend_data) < 0) {
-      goto error;
-    }
-  }
-
-  rend_data->auth_type = auth_type;
-  rend_data->hsdirs_fp = smartlist_new();
-
-  return rend_data;
-
- error:
-  rend_data_free(rend_data);
-  return NULL;
-}
-
 /** Determine the routers that are responsible for <b>id</b> (binary) and
  * add pointers to those routers' routerstatus_t to <b>responsible_dirs</b>.
  * Return -1 if we're returning an empty smartlist, else return 0.
@@ -1116,3 +999,33 @@ assert_circ_anonymity_ok(origin_circuit_t *circ,
   }
 }
 
+/* Return 1 iff the given <b>digest</b> of a permenanent hidden service key is
+ * equal to the digest in the origin circuit <b>ocirc</b> of its rend data .
+ * If the rend data doesn't exist, 0 is returned. This function is agnostic to
+ * the rend data version. */
+int
+rend_circuit_pk_digest_eq(const origin_circuit_t *ocirc,
+                          const uint8_t *digest)
+{
+  size_t rend_pk_digest_len;
+  const uint8_t *rend_pk_digest;
+
+  tor_assert(ocirc);
+  tor_assert(digest);
+
+  if (ocirc->rend_data == NULL) {
+    goto no_match;
+  }
+
+  rend_pk_digest = rend_data_get_pk_digest(ocirc->rend_data,
+                                           &rend_pk_digest_len);
+  if (tor_memeq(rend_pk_digest, digest, rend_pk_digest_len)) {
+    goto match;
+  }
+ no_match:
+  return 0;
+ match:
+  return 1;
+}
+
+
diff --git a/src/or/rendcommon.h b/src/or/rendcommon.h
index 090e6f25e0..942ace5761 100644
--- a/src/or/rendcommon.h
+++ b/src/or/rendcommon.h
@@ -18,19 +18,6 @@ typedef enum rend_intro_point_failure_t {
   INTRO_POINT_FAILURE_UNREACHABLE = 2,
 } rend_intro_point_failure_t;
 
-/** Free all storage associated with <b>data</b> */
-static inline void
-rend_data_free(rend_data_t *data)
-{
-  if (!data) {
-    return;
-  }
-  /* Cleanup the HSDir identity digest. */
-  SMARTLIST_FOREACH(data->hsdirs_fp, char *, d, tor_free(d));
-  smartlist_free(data->hsdirs_fp);
-  tor_free(data);
-}
-
 int rend_cmp_service_ids(const char *one, const char *two);
 
 void rend_process_relay_cell(circuit_t *circ, const crypt_path_t *layer_hint,
@@ -60,15 +47,8 @@ void rend_get_descriptor_id_bytes(char *descriptor_id_out,
 int hid_serv_get_responsible_directories(smartlist_t *responsible_dirs,
                                          const char *id);
 
-rend_data_t *rend_data_dup(const rend_data_t *data);
-rend_data_t *rend_data_client_create(const char *onion_address,
-                                     const char *desc_id,
-                                     const char *cookie,
-                                     rend_auth_type_t auth_type);
-rend_data_t *rend_data_service_create(const char *onion_address,
-                                      const char *pk_digest,
-                                      const uint8_t *cookie,
-                                      rend_auth_type_t auth_type);
+int rend_circuit_pk_digest_eq(const origin_circuit_t *ocirc,
+                              const uint8_t *digest);
 
 char *rend_auth_encode_cookie(const uint8_t *cookie_in,
                               rend_auth_type_t auth_type);
diff --git a/src/or/rendservice.c b/src/or/rendservice.c
index 7083051cce..b6bf63d829 100644
--- a/src/or/rendservice.c
+++ b/src/or/rendservice.c
@@ -17,6 +17,7 @@
 #include "config.h"
 #include "control.h"
 #include "directory.h"
+#include "hs_common.h"
 #include "main.h"
 #include "networkstatus.h"
 #include "nodelist.h"
@@ -761,8 +762,7 @@ rend_config_services(const or_options_t *options, int validate_only)
         int keep_it = 0;
         tor_assert(oc->rend_data);
         SMARTLIST_FOREACH(surviving_services, rend_service_t *, ptr, {
-          if (tor_memeq(ptr->pk_digest, oc->rend_data->rend_pk_digest,
-                      DIGEST_LEN)) {
+          if (rend_circuit_pk_digest_eq(oc, (uint8_t *) ptr->pk_digest)) {
             keep_it = 1;
             break;
           }
@@ -772,7 +772,7 @@ rend_config_services(const or_options_t *options, int validate_only)
         log_info(LD_REND, "Closing intro point %s for service %s.",
                  safe_str_client(extend_info_describe(
                                             oc->build_state->chosen_exit)),
-                 oc->rend_data->onion_address);
+                 rend_data_get_address(oc->rend_data));
         circuit_mark_for_close(circ, END_CIRC_REASON_FINISHED);
         /* XXXX Is there another reason we should use here? */
       }
@@ -899,12 +899,13 @@ rend_service_del_ephemeral(const char *service_id)
          circ->purpose == CIRCUIT_PURPOSE_S_INTRO)) {
       origin_circuit_t *oc = TO_ORIGIN_CIRCUIT(circ);
       tor_assert(oc->rend_data);
-      if (!tor_memeq(s->pk_digest, oc->rend_data->rend_pk_digest, DIGEST_LEN))
+      if (!rend_circuit_pk_digest_eq(oc, (uint8_t *) s->pk_digest)) {
         continue;
+      }
       log_debug(LD_REND, "Closing intro point %s for service %s.",
                 safe_str_client(extend_info_describe(
                                           oc->build_state->chosen_exit)),
-                oc->rend_data->onion_address);
+                rend_data_get_address(oc->rend_data));
       circuit_mark_for_close(circ, END_CIRC_REASON_FINISHED);
     }
   } SMARTLIST_FOREACH_END(circ);
@@ -1649,7 +1650,7 @@ rend_service_receive_introduction(origin_circuit_t *circuit,
   const or_options_t *options = get_options();
   char *err_msg = NULL;
   int err_msg_severity = LOG_WARN;
-  const char *stage_descr = NULL;
+  const char *stage_descr = NULL, *rend_pk_digest;
   int reason = END_CIRC_REASON_TORPROTOCOL;
   /* Service/circuit/key stuff we can learn before parsing */
   char serviceid[REND_SERVICE_ID_LEN_BASE32+1];
@@ -1683,14 +1684,15 @@ rend_service_receive_introduction(origin_circuit_t *circuit,
 
   assert_circ_anonymity_ok(circuit, options);
   tor_assert(circuit->rend_data);
+  /* XXX: This is version 2 specific (only one supported). */
+  rend_pk_digest = (char *) rend_data_get_pk_digest(circuit->rend_data, NULL);
 
   /* We'll use this in a bazillion log messages */
   base32_encode(serviceid, REND_SERVICE_ID_LEN_BASE32+1,
-                circuit->rend_data->rend_pk_digest, REND_SERVICE_ID_LEN);
+                rend_pk_digest, REND_SERVICE_ID_LEN);
 
   /* look up service depending on circuit. */
-  service =
-    rend_service_get_by_pk_digest(circuit->rend_data->rend_pk_digest);
+  service = rend_service_get_by_pk_digest(rend_pk_digest);
   if (!service) {
     log_warn(LD_BUG,
              "Internal error: Got an INTRODUCE2 cell on an intro "
@@ -1913,8 +1915,7 @@ rend_service_receive_introduction(origin_circuit_t *circuit,
   /* Fill in the circuit's state. */
 
   launched->rend_data =
-    rend_data_service_create(service->service_id,
-                             circuit->rend_data->rend_pk_digest,
+    rend_data_service_create(service->service_id, rend_pk_digest,
                              parsed_req->rc, service->auth_type);
 
   launched->build_state->service_pending_final_cpath_ref =
@@ -2948,9 +2949,9 @@ count_intro_point_circuits(const rend_service_t *service)
          circ->purpose == CIRCUIT_PURPOSE_S_INTRO)) {
       origin_circuit_t *oc = TO_ORIGIN_CIRCUIT(circ);
       if (oc->rend_data &&
-          !rend_cmp_service_ids(service->service_id,
-                                oc->rend_data->onion_address))
+          rend_circuit_pk_digest_eq(oc, (uint8_t *) service->pk_digest)) {
         num_ipos++;
+      }
     }
   }
   SMARTLIST_FOREACH_END(circ);
@@ -2970,17 +2971,19 @@ rend_service_intro_has_opened(origin_circuit_t *circuit)
   char auth[DIGEST_LEN + 9];
   char serviceid[REND_SERVICE_ID_LEN_BASE32+1];
   int reason = END_CIRC_REASON_TORPROTOCOL;
+  const char *rend_pk_digest;
 
   tor_assert(circuit->base_.purpose == CIRCUIT_PURPOSE_S_ESTABLISH_INTRO);
   assert_circ_anonymity_ok(circuit, get_options());
   tor_assert(circuit->cpath);
   tor_assert(circuit->rend_data);
+  /* XXX: This is version 2 specific (only on supported). */
+  rend_pk_digest = (char *) rend_data_get_pk_digest(circuit->rend_data, NULL);
 
   base32_encode(serviceid, REND_SERVICE_ID_LEN_BASE32+1,
-                circuit->rend_data->rend_pk_digest, REND_SERVICE_ID_LEN);
+                rend_pk_digest, REND_SERVICE_ID_LEN);
 
-  service = rend_service_get_by_pk_digest(
-                circuit->rend_data->rend_pk_digest);
+  service = rend_service_get_by_pk_digest(rend_pk_digest);
   if (!service) {
     log_warn(LD_REND, "Unrecognized service ID %s on introduction circuit %u.",
              safe_str_client(serviceid), (unsigned)circuit->base_.n_circ_id);
@@ -3021,9 +3024,8 @@ rend_service_intro_has_opened(origin_circuit_t *circuit)
       circuit_change_purpose(TO_CIRCUIT(circuit), CIRCUIT_PURPOSE_C_GENERAL);
 
       {
-        rend_data_t *rend_data = circuit->rend_data;
+        rend_data_free(circuit->rend_data);
         circuit->rend_data = NULL;
-        rend_data_free(rend_data);
       }
       {
         crypto_pk_t *intro_key = circuit->intro_key;
@@ -3106,15 +3108,17 @@ rend_service_intro_established(origin_circuit_t *circuit,
   char serviceid[REND_SERVICE_ID_LEN_BASE32+1];
   (void) request;
   (void) request_len;
+  tor_assert(circuit->rend_data);
+  /* XXX: This is version 2 specific (only supported one for now). */
+  const char *rend_pk_digest =
+    (char *) rend_data_get_pk_digest(circuit->rend_data, NULL);
 
   if (circuit->base_.purpose != CIRCUIT_PURPOSE_S_ESTABLISH_INTRO) {
     log_warn(LD_PROTOCOL,
              "received INTRO_ESTABLISHED cell on non-intro circuit.");
     goto err;
   }
-  tor_assert(circuit->rend_data);
-  service = rend_service_get_by_pk_digest(
-                circuit->rend_data->rend_pk_digest);
+  service = rend_service_get_by_pk_digest(rend_pk_digest);
   if (!service) {
     log_warn(LD_REND, "Unknown service on introduction circuit %u.",
              (unsigned)circuit->base_.n_circ_id);
@@ -3137,7 +3141,7 @@ rend_service_intro_established(origin_circuit_t *circuit,
   circuit_change_purpose(TO_CIRCUIT(circuit), CIRCUIT_PURPOSE_S_INTRO);
 
   base32_encode(serviceid, REND_SERVICE_ID_LEN_BASE32 + 1,
-                circuit->rend_data->rend_pk_digest, REND_SERVICE_ID_LEN);
+                rend_pk_digest, REND_SERVICE_ID_LEN);
   log_info(LD_REND,
            "Received INTRO_ESTABLISHED cell on circuit %u for service %s",
            (unsigned)circuit->base_.n_circ_id, serviceid);
@@ -3164,6 +3168,7 @@ rend_service_rendezvous_has_opened(origin_circuit_t *circuit)
   char serviceid[REND_SERVICE_ID_LEN_BASE32+1];
   char hexcookie[9];
   int reason;
+  const char *rend_cookie, *rend_pk_digest;
 
   tor_assert(circuit->base_.purpose == CIRCUIT_PURPOSE_S_CONNECT_REND);
   tor_assert(circuit->cpath);
@@ -3171,6 +3176,11 @@ rend_service_rendezvous_has_opened(origin_circuit_t *circuit)
   assert_circ_anonymity_ok(circuit, get_options());
   tor_assert(circuit->rend_data);
 
+  /* XXX: This is version 2 specific (only one supported). */
+  rend_pk_digest = (char *) rend_data_get_pk_digest(circuit->rend_data,
+                                                    NULL);
+  rend_cookie = circuit->rend_data->rend_cookie;
+
   /* Declare the circuit dirty to avoid reuse, and for path-bias */
   if (!circuit->base_.timestamp_dirty)
     circuit->base_.timestamp_dirty = time(NULL);
@@ -3180,9 +3190,9 @@ rend_service_rendezvous_has_opened(origin_circuit_t *circuit)
 
   hop = circuit->build_state->service_pending_final_cpath_ref->cpath;
 
-  base16_encode(hexcookie,9,circuit->rend_data->rend_cookie,4);
+  base16_encode(hexcookie,9, rend_cookie,4);
   base32_encode(serviceid, REND_SERVICE_ID_LEN_BASE32+1,
-                circuit->rend_data->rend_pk_digest, REND_SERVICE_ID_LEN);
+                rend_pk_digest, REND_SERVICE_ID_LEN);
 
   log_info(LD_REND,
            "Done building circuit %u to rendezvous with "
@@ -3211,8 +3221,7 @@ rend_service_rendezvous_has_opened(origin_circuit_t *circuit)
   circuit->build_state->pending_final_cpath = hop;
   circuit->build_state->service_pending_final_cpath_ref->cpath = NULL;
 
-  service = rend_service_get_by_pk_digest(
-                circuit->rend_data->rend_pk_digest);
+  service = rend_service_get_by_pk_digest(rend_pk_digest);
   if (!service) {
     log_warn(LD_GENERAL, "Internal error: unrecognized service ID on "
              "rendezvous circuit.");
@@ -3221,7 +3230,7 @@ rend_service_rendezvous_has_opened(origin_circuit_t *circuit)
   }
 
   /* All we need to do is send a RELAY_RENDEZVOUS1 cell... */
-  memcpy(buf, circuit->rend_data->rend_cookie, REND_COOKIE_LEN);
+  memcpy(buf, rend_cookie, REND_COOKIE_LEN);
   if (crypto_dh_get_public(hop->rend_dh_handshake_state,
                            buf+REND_COOKIE_LEN, DH_KEY_LEN)<0) {
     log_warn(LD_GENERAL,"Couldn't get DH public key.");
@@ -3284,8 +3293,8 @@ find_intro_circuit(rend_intro_point_t *intro, const char *pk_digest)
   origin_circuit_t *circ = NULL;
 
   tor_assert(intro);
-  while ((circ = circuit_get_next_by_pk_and_purpose(circ,pk_digest,
-                                                  CIRCUIT_PURPOSE_S_INTRO))) {
+  while ((circ = circuit_get_next_by_pk_and_purpose(circ,
+                         (uint8_t *) pk_digest, CIRCUIT_PURPOSE_S_INTRO))) {
     if (tor_memeq(circ->build_state->chosen_exit->identity_digest,
                 intro->extend_info->identity_digest, DIGEST_LEN) &&
         circ->rend_data) {
@@ -3294,8 +3303,9 @@ find_intro_circuit(rend_intro_point_t *intro, const char *pk_digest)
   }
 
   circ = NULL;
-  while ((circ = circuit_get_next_by_pk_and_purpose(circ,pk_digest,
-                                        CIRCUIT_PURPOSE_S_ESTABLISH_INTRO))) {
+  while ((circ = circuit_get_next_by_pk_and_purpose(circ,
+                         (uint8_t *) pk_digest,
+                         CIRCUIT_PURPOSE_S_ESTABLISH_INTRO))) {
     if (tor_memeq(circ->build_state->chosen_exit->identity_digest,
                 intro->extend_info->identity_digest, DIGEST_LEN) &&
         circ->rend_data) {
@@ -3334,7 +3344,7 @@ find_intro_point(origin_circuit_t *circ)
   tor_assert(TO_CIRCUIT(circ)->purpose == CIRCUIT_PURPOSE_S_ESTABLISH_INTRO ||
              TO_CIRCUIT(circ)->purpose == CIRCUIT_PURPOSE_S_INTRO);
   tor_assert(circ->rend_data);
-  serviceid = circ->rend_data->onion_address;
+  serviceid = rend_data_get_address(circ->rend_data);
 
   SMARTLIST_FOREACH(rend_service_list, rend_service_t *, s,
     if (tor_memeq(s->service_id, serviceid, REND_SERVICE_ID_LEN_BASE32)) {
@@ -3719,10 +3729,13 @@ void
 rend_service_desc_has_uploaded(const rend_data_t *rend_data)
 {
   rend_service_t *service;
+  const char *onion_address;
 
   tor_assert(rend_data);
 
-  service = rend_service_get_by_service_id(rend_data->onion_address);
+  onion_address = rend_data_get_address(rend_data);
+
+  service = rend_service_get_by_service_id(onion_address);
   if (service == NULL) {
     return;
   }
@@ -4109,14 +4122,16 @@ rend_service_set_connection_addr_port(edge_connection_t *conn,
   smartlist_t *matching_ports;
   rend_service_port_config_t *chosen_port;
   unsigned int warn_once = 0;
+  const char *rend_pk_digest;
 
   tor_assert(circ->base_.purpose == CIRCUIT_PURPOSE_S_REND_JOINED);
   tor_assert(circ->rend_data);
   log_debug(LD_REND,"beginning to hunt for addr/port");
+  /* XXX: This is version 2 specific (only one supported). */
+  rend_pk_digest = (char *) rend_data_get_pk_digest(circ->rend_data, NULL);
   base32_encode(serviceid, REND_SERVICE_ID_LEN_BASE32+1,
-                circ->rend_data->rend_pk_digest, REND_SERVICE_ID_LEN);
-  service = rend_service_get_by_pk_digest(
-                circ->rend_data->rend_pk_digest);
+                rend_pk_digest, REND_SERVICE_ID_LEN);
+  service = rend_service_get_by_pk_digest(rend_pk_digest);
   if (!service) {
     log_warn(LD_REND, "Couldn't find any service associated with pk %s on "
              "rendezvous circuit %u; closing.",
diff --git a/src/or/routerparse.c b/src/or/routerparse.c
index cb2bc72d0c..5bc2d39579 100644
--- a/src/or/routerparse.c
+++ b/src/or/routerparse.c
@@ -60,6 +60,7 @@
 #include "circuitstats.h"
 #include "dirserv.h"
 #include "dirvote.h"
+#include "parsecommon.h"
 #include "policies.h"
 #include "protover.h"
 #include "rendcommon.h"
@@ -81,267 +82,6 @@
 
 /****************************************************************************/
 
-/** Enumeration of possible token types.  The ones starting with K_ correspond
- * to directory 'keywords'. A_ is for an annotation, R or C is related to
- * hidden services, ERR_ is an error in the tokenizing process, EOF_ is an
- * end-of-file marker, and NIL_ is used to encode not-a-token.
- */
-typedef enum {
-  K_ACCEPT = 0,
-  K_ACCEPT6,
-  K_DIRECTORY_SIGNATURE,
-  K_RECOMMENDED_SOFTWARE,
-  K_REJECT,
-  K_REJECT6,
-  K_ROUTER,
-  K_SIGNED_DIRECTORY,
-  K_SIGNING_KEY,
-  K_ONION_KEY,
-  K_ONION_KEY_NTOR,
-  K_ROUTER_SIGNATURE,
-  K_PUBLISHED,
-  K_RUNNING_ROUTERS,
-  K_ROUTER_STATUS,
-  K_PLATFORM,
-  K_PROTO,
-  K_OPT,
-  K_BANDWIDTH,
-  K_CONTACT,
-  K_NETWORK_STATUS,
-  K_UPTIME,
-  K_DIR_SIGNING_KEY,
-  K_FAMILY,
-  K_FINGERPRINT,
-  K_HIBERNATING,
-  K_READ_HISTORY,
-  K_WRITE_HISTORY,
-  K_NETWORK_STATUS_VERSION,
-  K_DIR_SOURCE,
-  K_DIR_OPTIONS,
-  K_CLIENT_VERSIONS,
-  K_SERVER_VERSIONS,
-  K_RECOMMENDED_CLIENT_PROTOCOLS,
-  K_RECOMMENDED_RELAY_PROTOCOLS,
-  K_REQUIRED_CLIENT_PROTOCOLS,
-  K_REQUIRED_RELAY_PROTOCOLS,
-  K_OR_ADDRESS,
-  K_ID,
-  K_P,
-  K_P6,
-  K_R,
-  K_A,
-  K_S,
-  K_V,
-  K_W,
-  K_M,
-  K_EXTRA_INFO,
-  K_EXTRA_INFO_DIGEST,
-  K_CACHES_EXTRA_INFO,
-  K_HIDDEN_SERVICE_DIR,
-  K_ALLOW_SINGLE_HOP_EXITS,
-  K_IPV6_POLICY,
-  K_ROUTER_SIG_ED25519,
-  K_IDENTITY_ED25519,
-  K_MASTER_KEY_ED25519,
-  K_ONION_KEY_CROSSCERT,
-  K_NTOR_ONION_KEY_CROSSCERT,
-
-  K_DIRREQ_END,
-  K_DIRREQ_V2_IPS,
-  K_DIRREQ_V3_IPS,
-  K_DIRREQ_V2_REQS,
-  K_DIRREQ_V3_REQS,
-  K_DIRREQ_V2_SHARE,
-  K_DIRREQ_V3_SHARE,
-  K_DIRREQ_V2_RESP,
-  K_DIRREQ_V3_RESP,
-  K_DIRREQ_V2_DIR,
-  K_DIRREQ_V3_DIR,
-  K_DIRREQ_V2_TUN,
-  K_DIRREQ_V3_TUN,
-  K_ENTRY_END,
-  K_ENTRY_IPS,
-  K_CELL_END,
-  K_CELL_PROCESSED,
-  K_CELL_QUEUED,
-  K_CELL_TIME,
-  K_CELL_CIRCS,
-  K_EXIT_END,
-  K_EXIT_WRITTEN,
-  K_EXIT_READ,
-  K_EXIT_OPENED,
-
-  K_DIR_KEY_CERTIFICATE_VERSION,
-  K_DIR_IDENTITY_KEY,
-  K_DIR_KEY_PUBLISHED,
-  K_DIR_KEY_EXPIRES,
-  K_DIR_KEY_CERTIFICATION,
-  K_DIR_KEY_CROSSCERT,
-  K_DIR_ADDRESS,
-  K_DIR_TUNNELLED,
-
-  K_VOTE_STATUS,
-  K_VALID_AFTER,
-  K_FRESH_UNTIL,
-  K_VALID_UNTIL,
-  K_VOTING_DELAY,
-
-  K_KNOWN_FLAGS,
-  K_PARAMS,
-  K_BW_WEIGHTS,
-  K_VOTE_DIGEST,
-  K_CONSENSUS_DIGEST,
-  K_ADDITIONAL_DIGEST,
-  K_ADDITIONAL_SIGNATURE,
-  K_CONSENSUS_METHODS,
-  K_CONSENSUS_METHOD,
-  K_LEGACY_DIR_KEY,
-  K_DIRECTORY_FOOTER,
-  K_SIGNING_CERT_ED,
-  K_SR_FLAG,
-  K_COMMIT,
-  K_PREVIOUS_SRV,
-  K_CURRENT_SRV,
-  K_PACKAGE,
-
-  A_PURPOSE,
-  A_LAST_LISTED,
-  A_UNKNOWN_,
-
-  R_RENDEZVOUS_SERVICE_DESCRIPTOR,
-  R_VERSION,
-  R_PERMANENT_KEY,
-  R_SECRET_ID_PART,
-  R_PUBLICATION_TIME,
-  R_PROTOCOL_VERSIONS,
-  R_INTRODUCTION_POINTS,
-  R_SIGNATURE,
-
-  R_IPO_IDENTIFIER,
-  R_IPO_IP_ADDRESS,
-  R_IPO_ONION_PORT,
-  R_IPO_ONION_KEY,
-  R_IPO_SERVICE_KEY,
-
-  C_CLIENT_NAME,
-  C_DESCRIPTOR_COOKIE,
-  C_CLIENT_KEY,
-
-  ERR_,
-  EOF_,
-  NIL_
-} directory_keyword;
-
-#define MIN_ANNOTATION A_PURPOSE
-#define MAX_ANNOTATION A_UNKNOWN_
-
-/** Structure to hold a single directory token.
- *
- * We parse a directory by breaking it into "tokens", each consisting
- * of a keyword, a line full of arguments, and a binary object.  The
- * arguments and object are both optional, depending on the keyword
- * type.
- *
- * This structure is only allocated in memareas; do not allocate it on
- * the heap, or token_clear() won't work.
- */
-typedef struct directory_token_t {
-  directory_keyword tp;        /**< Type of the token. */
-  int n_args:30;               /**< Number of elements in args */
-  char **args;                 /**< Array of arguments from keyword line. */
-
-  char *object_type;           /**< -----BEGIN [object_type]-----*/
-  size_t object_size;          /**< Bytes in object_body */
-  char *object_body;           /**< Contents of object, base64-decoded. */
-
-  crypto_pk_t *key;        /**< For public keys only.  Heap-allocated. */
-
-  char *error;                 /**< For ERR_ tokens only. */
-} directory_token_t;
-
-/* ********************************************************************** */
-
-/** We use a table of rules to decide how to parse each token type. */
-
-/** Rules for whether the keyword needs an object. */
-typedef enum {
-  NO_OBJ,        /**< No object, ever. */
-  NEED_OBJ,      /**< Object is required. */
-  NEED_SKEY_1024,/**< Object is required, and must be a 1024 bit private key */
-  NEED_KEY_1024, /**< Object is required, and must be a 1024 bit public key */
-  NEED_KEY,      /**< Object is required, and must be a public key. */
-  OBJ_OK,        /**< Object is optional. */
-} obj_syntax;
-
-#define AT_START 1
-#define AT_END 2
-
-/** Determines the parsing rules for a single token type. */
-typedef struct token_rule_t {
-  /** The string value of the keyword identifying the type of item. */
-  const char *t;
-  /** The corresponding directory_keyword enum. */
-  directory_keyword v;
-  /** Minimum number of arguments for this item */
-  int min_args;
-  /** Maximum number of arguments for this item */
-  int max_args;
-  /** If true, we concatenate all arguments for this item into a single
-   * string. */
-  int concat_args;
-  /** Requirements on object syntax for this item. */
-  obj_syntax os;
-  /** Lowest number of times this item may appear in a document. */
-  int min_cnt;
-  /** Highest number of times this item may appear in a document. */
-  int max_cnt;
-  /** One or more of AT_START/AT_END to limit where the item may appear in a
-   * document. */
-  int pos;
-  /** True iff this token is an annotation. */
-  int is_annotation;
-} token_rule_t;
-
-/**
- * @name macros for defining token rules
- *
- * Helper macros to define token tables.  's' is a string, 't' is a
- * directory_keyword, 'a' is a trio of argument multiplicities, and 'o' is an
- * object syntax.
- */
-/**@{*/
-
-/** Appears to indicate the end of a table. */
-#define END_OF_TABLE { NULL, NIL_, 0,0,0, NO_OBJ, 0, INT_MAX, 0, 0 }
-/** An item with no restrictions: used for obsolete document types */
-#define T(s,t,a,o)    { s, t, a, o, 0, INT_MAX, 0, 0 }
-/** An item with no restrictions on multiplicity or location. */
-#define T0N(s,t,a,o)  { s, t, a, o, 0, INT_MAX, 0, 0 }
-/** An item that must appear exactly once */
-#define T1(s,t,a,o)   { s, t, a, o, 1, 1, 0, 0 }
-/** An item that must appear exactly once, at the start of the document */
-#define T1_START(s,t,a,o)   { s, t, a, o, 1, 1, AT_START, 0 }
-/** An item that must appear exactly once, at the end of the document */
-#define T1_END(s,t,a,o)   { s, t, a, o, 1, 1, AT_END, 0 }
-/** An item that must appear one or more times */
-#define T1N(s,t,a,o)  { s, t, a, o, 1, INT_MAX, 0, 0 }
-/** An item that must appear no more than once */
-#define T01(s,t,a,o)  { s, t, a, o, 0, 1, 0, 0 }
-/** An annotation that must appear no more than once */
-#define A01(s,t,a,o)  { s, t, a, o, 0, 1, 0, 1 }
-
-/** Argument multiplicity: any number of arguments. */
-#define ARGS        0,INT_MAX,0
-/** Argument multiplicity: no arguments. */
-#define NO_ARGS     0,0,0
-/** Argument multiplicity: concatenate all arguments. */
-#define CONCAT_ARGS 1,1,1
-/** Argument multiplicity: at least <b>n</b> arguments. */
-#define GE(n)       n,INT_MAX,0
-/** Argument multiplicity: exactly <b>n</b> arguments. */
-#define EQ(n)       n,n,0
-/**@}*/
-
 /** List of tokens recognized in router descriptors */
 static token_rule_t routerdesc_token_table[] = {
   T0N("reject",              K_REJECT,              ARGS,    NO_OBJ ),
@@ -628,28 +368,8 @@ static int router_get_hashes_impl(const char *s, size_t s_len,
                                   common_digests_t *digests,
                                   const char *start_str, const char *end_str,
                                   char end_char);
-static void token_clear(directory_token_t *tok);
-static smartlist_t *find_all_by_keyword(smartlist_t *s, directory_keyword k);
 static smartlist_t *find_all_exitpolicy(smartlist_t *s);
-static directory_token_t *find_by_keyword_(smartlist_t *s,
-                                           directory_keyword keyword,
-                                           const char *keyword_str);
-#define find_by_keyword(s, keyword) find_by_keyword_((s), (keyword), #keyword)
-static directory_token_t *find_opt_by_keyword(smartlist_t *s,
-                                              directory_keyword keyword);
-
-#define TS_ANNOTATIONS_OK 1
-#define TS_NOCHECK 2
-#define TS_NO_NEW_ANNOTATIONS 4
-static int tokenize_string(memarea_t *area,
-                           const char *start, const char *end,
-                           smartlist_t *out,
-                           token_rule_t *table,
-                           int flags);
-static directory_token_t *get_next_token(memarea_t *area,
-                                         const char **s,
-                                         const char *eos,
-                                         token_rule_t *table);
+
 #define CST_CHECK_AUTHORITY   (1<<0)
 #define CST_NO_CHECK_OBJTYPE  (1<<1)
 static int check_signature_token(const char *digest,
@@ -4738,445 +4458,6 @@ assert_addr_policy_ok(smartlist_t *lst)
   });
 }
 
-/*
- * Low-level tokenizer for router descriptors and directories.
- */
-
-/** Free all resources allocated for <b>tok</b> */
-static void
-token_clear(directory_token_t *tok)
-{
-  if (tok->key)
-    crypto_pk_free(tok->key);
-}
-
-#define ALLOC_ZERO(sz) memarea_alloc_zero(area,sz)
-#define ALLOC(sz) memarea_alloc(area,sz)
-#define STRDUP(str) memarea_strdup(area,str)
-#define STRNDUP(str,n) memarea_strndup(area,(str),(n))
-
-#define RET_ERR(msg)                                               \
-  STMT_BEGIN                                                       \
-    if (tok) token_clear(tok);                                      \
-    tok = ALLOC_ZERO(sizeof(directory_token_t));                   \
-    tok->tp = ERR_;                                                \
-    tok->error = STRDUP(msg);                                      \
-    goto done_tokenizing;                                          \
-  STMT_END
-
-/** Helper: make sure that the token <b>tok</b> with keyword <b>kwd</b> obeys
- * the object syntax of <b>o_syn</b>.  Allocate all storage in <b>area</b>.
- * Return <b>tok</b> on success, or a new ERR_ token if the token didn't
- * conform to the syntax we wanted.
- **/
-static inline directory_token_t *
-token_check_object(memarea_t *area, const char *kwd,
-                   directory_token_t *tok, obj_syntax o_syn)
-{
-  char ebuf[128];
-  switch (o_syn) {
-    case NO_OBJ:
-      /* No object is allowed for this token. */
-      if (tok->object_body) {
-        tor_snprintf(ebuf, sizeof(ebuf), "Unexpected object for %s", kwd);
-        RET_ERR(ebuf);
-      }
-      if (tok->key) {
-        tor_snprintf(ebuf, sizeof(ebuf), "Unexpected public key for %s", kwd);
-        RET_ERR(ebuf);
-      }
-      break;
-    case NEED_OBJ:
-      /* There must be a (non-key) object. */
-      if (!tok->object_body) {
-        tor_snprintf(ebuf, sizeof(ebuf), "Missing object for %s", kwd);
-        RET_ERR(ebuf);
-      }
-      break;
-    case NEED_KEY_1024: /* There must be a 1024-bit public key. */
-    case NEED_SKEY_1024: /* There must be a 1024-bit private key. */
-      if (tok->key && crypto_pk_num_bits(tok->key) != PK_BYTES*8) {
-        tor_snprintf(ebuf, sizeof(ebuf), "Wrong size on key for %s: %d bits",
-                     kwd, crypto_pk_num_bits(tok->key));
-        RET_ERR(ebuf);
-      }
-      /* fall through */
-    case NEED_KEY: /* There must be some kind of key. */
-      if (!tok->key) {
-        tor_snprintf(ebuf, sizeof(ebuf), "Missing public key for %s", kwd);
-        RET_ERR(ebuf);
-      }
-      if (o_syn != NEED_SKEY_1024) {
-        if (crypto_pk_key_is_private(tok->key)) {
-          tor_snprintf(ebuf, sizeof(ebuf),
-               "Private key given for %s, which wants a public key", kwd);
-          RET_ERR(ebuf);
-        }
-      } else { /* o_syn == NEED_SKEY_1024 */
-        if (!crypto_pk_key_is_private(tok->key)) {
-          tor_snprintf(ebuf, sizeof(ebuf),
-               "Public key given for %s, which wants a private key", kwd);
-          RET_ERR(ebuf);
-        }
-      }
-      break;
-    case OBJ_OK:
-      /* Anything goes with this token. */
-      break;
-  }
-
- done_tokenizing:
-  return tok;
-}
-
-/** Helper: parse space-separated arguments from the string <b>s</b> ending at
- * <b>eol</b>, and store them in the args field of <b>tok</b>.  Store the
- * number of parsed elements into the n_args field of <b>tok</b>.  Allocate
- * all storage in <b>area</b>.  Return the number of arguments parsed, or
- * return -1 if there was an insanely high number of arguments. */
-static inline int
-get_token_arguments(memarea_t *area, directory_token_t *tok,
-                    const char *s, const char *eol)
-{
-/** Largest number of arguments we'll accept to any token, ever. */
-#define MAX_ARGS 512
-  char *mem = memarea_strndup(area, s, eol-s);
-  char *cp = mem;
-  int j = 0;
-  char *args[MAX_ARGS];
-  while (*cp) {
-    if (j == MAX_ARGS)
-      return -1;
-    args[j++] = cp;
-    cp = (char*)find_whitespace(cp);
-    if (!cp || !*cp)
-      break; /* End of the line. */
-    *cp++ = '\0';
-    cp = (char*)eat_whitespace(cp);
-  }
-  tok->n_args = j;
-  tok->args = memarea_memdup(area, args, j*sizeof(char*));
-  return j;
-#undef MAX_ARGS
-}
-
-/** Helper function: read the next token from *s, advance *s to the end of the
- * token, and return the parsed token.  Parse *<b>s</b> according to the list
- * of tokens in <b>table</b>.
- */
-static directory_token_t *
-get_next_token(memarea_t *area,
-               const char **s, const char *eos, token_rule_t *table)
-{
-  /** Reject any object at least this big; it is probably an overflow, an
-   * attack, a bug, or some other nonsense. */
-#define MAX_UNPARSED_OBJECT_SIZE (128*1024)
-  /** Reject any line at least this big; it is probably an overflow, an
-   * attack, a bug, or some other nonsense. */
-#define MAX_LINE_LENGTH (128*1024)
-
-  const char *next, *eol, *obstart;
-  size_t obname_len;
-  int i;
-  directory_token_t *tok;
-  obj_syntax o_syn = NO_OBJ;
-  char ebuf[128];
-  const char *kwd = "";
-
-  tor_assert(area);
-  tok = ALLOC_ZERO(sizeof(directory_token_t));
-  tok->tp = ERR_;
-
-  /* Set *s to first token, eol to end-of-line, next to after first token */
-  *s = eat_whitespace_eos(*s, eos); /* eat multi-line whitespace */
-  tor_assert(eos >= *s);
-  eol = memchr(*s, '\n', eos-*s);
-  if (!eol)
-    eol = eos;
-  if (eol - *s > MAX_LINE_LENGTH) {
-    RET_ERR("Line far too long");
-  }
-
-  next = find_whitespace_eos(*s, eol);
-
-  if (!strcmp_len(*s, "opt", next-*s)) {
-    /* Skip past an "opt" at the start of the line. */
-    *s = eat_whitespace_eos_no_nl(next, eol);
-    next = find_whitespace_eos(*s, eol);
-  } else if (*s == eos) {  /* If no "opt", and end-of-line, line is invalid */
-    RET_ERR("Unexpected EOF");
-  }
-
-  /* Search the table for the appropriate entry.  (I tried a binary search
-   * instead, but it wasn't any faster.) */
-  for (i = 0; table[i].t ; ++i) {
-    if (!strcmp_len(*s, table[i].t, next-*s)) {
-      /* We've found the keyword. */
-      kwd = table[i].t;
-      tok->tp = table[i].v;
-      o_syn = table[i].os;
-      *s = eat_whitespace_eos_no_nl(next, eol);
-      /* We go ahead whether there are arguments or not, so that tok->args is
-       * always set if we want arguments. */
-      if (table[i].concat_args) {
-        /* The keyword takes the line as a single argument */
-        tok->args = ALLOC(sizeof(char*));
-        tok->args[0] = STRNDUP(*s,eol-*s); /* Grab everything on line */
-        tok->n_args = 1;
-      } else {
-        /* This keyword takes multiple arguments. */
-        if (get_token_arguments(area, tok, *s, eol)<0) {
-          tor_snprintf(ebuf, sizeof(ebuf),"Far too many arguments to %s", kwd);
-          RET_ERR(ebuf);
-        }
-        *s = eol;
-      }
-      if (tok->n_args < table[i].min_args) {
-        tor_snprintf(ebuf, sizeof(ebuf), "Too few arguments to %s", kwd);
-        RET_ERR(ebuf);
-      } else if (tok->n_args > table[i].max_args) {
-        tor_snprintf(ebuf, sizeof(ebuf), "Too many arguments to %s", kwd);
-        RET_ERR(ebuf);
-      }
-      break;
-    }
-  }
-
-  if (tok->tp == ERR_) {
-    /* No keyword matched; call it an "K_opt" or "A_unrecognized" */
-    if (**s == '@')
-      tok->tp = A_UNKNOWN_;
-    else
-      tok->tp = K_OPT;
-    tok->args = ALLOC(sizeof(char*));
-    tok->args[0] = STRNDUP(*s, eol-*s);
-    tok->n_args = 1;
-    o_syn = OBJ_OK;
-  }
-
-  /* Check whether there's an object present */
-  *s = eat_whitespace_eos(eol, eos);  /* Scan from end of first line */
-  tor_assert(eos >= *s);
-  eol = memchr(*s, '\n', eos-*s);
-  if (!eol || eol-*s<11 || strcmpstart(*s, "-----BEGIN ")) /* No object. */
-    goto check_object;
-
-  obstart = *s; /* Set obstart to start of object spec */
-  if (*s+16 >= eol || memchr(*s+11,'\0',eol-*s-16) || /* no short lines, */
-      strcmp_len(eol-5, "-----", 5) ||           /* nuls or invalid endings */
-      (eol-*s) > MAX_UNPARSED_OBJECT_SIZE) {     /* name too long */
-    RET_ERR("Malformed object: bad begin line");
-  }
-  tok->object_type = STRNDUP(*s+11, eol-*s-16);
-  obname_len = eol-*s-16; /* store objname length here to avoid a strlen() */
-  *s = eol+1;    /* Set *s to possible start of object data (could be eos) */
-
-  /* Go to the end of the object */
-  next = tor_memstr(*s, eos-*s, "-----END ");
-  if (!next) {
-    RET_ERR("Malformed object: missing object end line");
-  }
-  tor_assert(eos >= next);
-  eol = memchr(next, '\n', eos-next);
-  if (!eol)  /* end-of-line marker, or eos if there's no '\n' */
-    eol = eos;
-  /* Validate the ending tag, which should be 9 + NAME + 5 + eol */
-  if ((size_t)(eol-next) != 9+obname_len+5 ||
-      strcmp_len(next+9, tok->object_type, obname_len) ||
-      strcmp_len(eol-5, "-----", 5)) {
-    tor_snprintf(ebuf, sizeof(ebuf), "Malformed object: mismatched end tag %s",
-             tok->object_type);
-    ebuf[sizeof(ebuf)-1] = '\0';
-    RET_ERR(ebuf);
-  }
-  if (next - *s > MAX_UNPARSED_OBJECT_SIZE)
-    RET_ERR("Couldn't parse object: missing footer or object much too big.");
-
-  if (!strcmp(tok->object_type, "RSA PUBLIC KEY")) { /* If it's a public key */
-    tok->key = crypto_pk_new();
-    if (crypto_pk_read_public_key_from_string(tok->key, obstart, eol-obstart))
-      RET_ERR("Couldn't parse public key.");
-  } else if (!strcmp(tok->object_type, "RSA PRIVATE KEY")) { /* private key */
-    tok->key = crypto_pk_new();
-    if (crypto_pk_read_private_key_from_string(tok->key, obstart, eol-obstart))
-      RET_ERR("Couldn't parse private key.");
-  } else { /* If it's something else, try to base64-decode it */
-    int r;
-    tok->object_body = ALLOC(next-*s); /* really, this is too much RAM. */
-    r = base64_decode(tok->object_body, next-*s, *s, next-*s);
-    if (r<0)
-      RET_ERR("Malformed object: bad base64-encoded data");
-    tok->object_size = r;
-  }
-  *s = eol;
-
- check_object:
-  tok = token_check_object(area, kwd, tok, o_syn);
-
- done_tokenizing:
-  return tok;
-
-#undef RET_ERR
-#undef ALLOC
-#undef ALLOC_ZERO
-#undef STRDUP
-#undef STRNDUP
-}
-
-/** Read all tokens from a string between <b>start</b> and <b>end</b>, and add
- * them to <b>out</b>.  Parse according to the token rules in <b>table</b>.
- * Caller must free tokens in <b>out</b>.  If <b>end</b> is NULL, use the
- * entire string.
- */
-static int
-tokenize_string(memarea_t *area,
-                const char *start, const char *end, smartlist_t *out,
-                token_rule_t *table, int flags)
-{
-  const char **s;
-  directory_token_t *tok = NULL;
-  int counts[NIL_];
-  int i;
-  int first_nonannotation;
-  int prev_len = smartlist_len(out);
-  tor_assert(area);
-
-  s = &start;
-  if (!end) {
-    end = start+strlen(start);
-  } else {
-    /* it's only meaningful to check for nuls if we got an end-of-string ptr */
-    if (memchr(start, '\0', end-start)) {
-      log_warn(LD_DIR, "parse error: internal NUL character.");
-      return -1;
-    }
-  }
-  for (i = 0; i < NIL_; ++i)
-    counts[i] = 0;
-
-  SMARTLIST_FOREACH(out, const directory_token_t *, t, ++counts[t->tp]);
-
-  while (*s < end && (!tok || tok->tp != EOF_)) {
-    tok = get_next_token(area, s, end, table);
-    if (tok->tp == ERR_) {
-      log_warn(LD_DIR, "parse error: %s", tok->error);
-      token_clear(tok);
-      return -1;
-    }
-    ++counts[tok->tp];
-    smartlist_add(out, tok);
-    *s = eat_whitespace_eos(*s, end);
-  }
-
-  if (flags & TS_NOCHECK)
-    return 0;
-
-  if ((flags & TS_ANNOTATIONS_OK)) {
-    first_nonannotation = -1;
-    for (i = 0; i < smartlist_len(out); ++i) {
-      tok = smartlist_get(out, i);
-      if (tok->tp < MIN_ANNOTATION || tok->tp > MAX_ANNOTATION) {
-        first_nonannotation = i;
-        break;
-      }
-    }
-    if (first_nonannotation < 0) {
-      log_warn(LD_DIR, "parse error: item contains only annotations");
-      return -1;
-    }
-    for (i=first_nonannotation;  i < smartlist_len(out); ++i) {
-      tok = smartlist_get(out, i);
-      if (tok->tp >= MIN_ANNOTATION && tok->tp <= MAX_ANNOTATION) {
-        log_warn(LD_DIR, "parse error: Annotations mixed with keywords");
-        return -1;
-      }
-    }
-    if ((flags & TS_NO_NEW_ANNOTATIONS)) {
-      if (first_nonannotation != prev_len) {
-        log_warn(LD_DIR, "parse error: Unexpected annotations.");
-        return -1;
-      }
-    }
-  } else {
-    for (i=0;  i < smartlist_len(out); ++i) {
-      tok = smartlist_get(out, i);
-      if (tok->tp >= MIN_ANNOTATION && tok->tp <= MAX_ANNOTATION) {
-        log_warn(LD_DIR, "parse error: no annotations allowed.");
-        return -1;
-      }
-    }
-    first_nonannotation = 0;
-  }
-  for (i = 0; table[i].t; ++i) {
-    if (counts[table[i].v] < table[i].min_cnt) {
-      log_warn(LD_DIR, "Parse error: missing %s element.", table[i].t);
-      return -1;
-    }
-    if (counts[table[i].v] > table[i].max_cnt) {
-      log_warn(LD_DIR, "Parse error: too many %s elements.", table[i].t);
-      return -1;
-    }
-    if (table[i].pos & AT_START) {
-      if (smartlist_len(out) < 1 ||
-          (tok = smartlist_get(out, first_nonannotation))->tp != table[i].v) {
-        log_warn(LD_DIR, "Parse error: first item is not %s.", table[i].t);
-        return -1;
-      }
-    }
-    if (table[i].pos & AT_END) {
-      if (smartlist_len(out) < 1 ||
-          (tok = smartlist_get(out, smartlist_len(out)-1))->tp != table[i].v) {
-        log_warn(LD_DIR, "Parse error: last item is not %s.", table[i].t);
-        return -1;
-      }
-    }
-  }
-  return 0;
-}
-
-/** Find the first token in <b>s</b> whose keyword is <b>keyword</b>; return
- * NULL if no such keyword is found.
- */
-static directory_token_t *
-find_opt_by_keyword(smartlist_t *s, directory_keyword keyword)
-{
-  SMARTLIST_FOREACH(s, directory_token_t *, t, if (t->tp == keyword) return t);
-  return NULL;
-}
-
-/** Find the first token in <b>s</b> whose keyword is <b>keyword</b>; fail
- * with an assert if no such keyword is found.
- */
-static directory_token_t *
-find_by_keyword_(smartlist_t *s, directory_keyword keyword,
-                 const char *keyword_as_string)
-{
-  directory_token_t *tok = find_opt_by_keyword(s, keyword);
-  if (PREDICT_UNLIKELY(!tok)) {
-    log_err(LD_BUG, "Missing %s [%d] in directory object that should have "
-         "been validated. Internal error.", keyword_as_string, (int)keyword);
-    tor_assert(tok);
-  }
-  return tok;
-}
-
-/** If there are any directory_token_t entries in <b>s</b> whose keyword is
- * <b>k</b>, return a newly allocated smartlist_t containing all such entries,
- * in the same order in which they occur in <b>s</b>.  Otherwise return
- * NULL. */
-static smartlist_t *
-find_all_by_keyword(smartlist_t *s, directory_keyword k)
-{
-  smartlist_t *out = NULL;
-  SMARTLIST_FOREACH(s, directory_token_t *, t,
-                    if (t->tp == k) {
-                      if (!out)
-                        out = smartlist_new();
-                      smartlist_add(out, t);
-                    });
-  return out;
-}
-
 /** Return a newly allocated smartlist of all accept or reject tokens in
  * <b>s</b>.
  */
diff --git a/src/or/torcert.h b/src/or/torcert.h
index f7ca0ff521..4bd816f4a4 100644
--- a/src/or/torcert.h
+++ b/src/or/torcert.h
@@ -6,12 +6,15 @@
 
 #include "crypto_ed25519.h"
 
-#define SIGNED_KEY_TYPE_ED25519 0x01
-
-#define CERT_TYPE_ID_SIGNING    0x04
-#define CERT_TYPE_SIGNING_LINK  0x05
-#define CERT_TYPE_SIGNING_AUTH  0x06
-#define CERT_TYPE_ONION_ID      0x0A
+#define SIGNED_KEY_TYPE_ED25519     0x01
+
+#define CERT_TYPE_ID_SIGNING        0x04
+#define CERT_TYPE_SIGNING_LINK      0x05
+#define CERT_TYPE_SIGNING_AUTH      0x06
+#define CERT_TYPE_SIGNING_HS_DESC   0x08
+#define CERT_TYPE_AUTH_HS_IP_KEY    0x09
+#define CERT_TYPE_ONION_ID          0x0A
+#define CERT_TYPE_CROSS_HS_IP_KEYS  0x0B
 
 #define CERT_FLAG_INCLUDE_SIGNING_KEY 0x1