Merge branch 'dgoulet_ticket19043_030_03_squashed'

28 files changed, 1655 insertions, 291 deletions

diff --git a/src/common/crypto.c b/src/common/crypto.c
index be42d36af6..60d77fcfaa 100644
--- a/src/common/crypto.c
+++ b/src/common/crypto.c
@@ -2123,6 +2123,35 @@ crypto_hmac_sha256(char *hmac_out,
   tor_assert(rv);
 }
 
+/** Compute a MAC using SHA3-256 of <b>msg_len</b> bytes in <b>msg</b> using a
+ * <b>key</b> of length <b>key_len</b> and a <b>salt</b> of length
+ * <b>salt_len</b>. Store the result of <b>len_out</b> bytes in in
+ * <b>mac_out</b>. This function can't fail. */
+void
+crypto_mac_sha3_256(uint8_t *mac_out, size_t len_out,
+                    const uint8_t *key, size_t key_len,
+                    const uint8_t *msg, size_t msg_len)
+{
+  crypto_digest_t *digest;
+
+  const uint64_t key_len_netorder = tor_htonll(key_len);
+
+  tor_assert(mac_out);
+  tor_assert(key);
+  tor_assert(msg);
+
+  digest = crypto_digest256_new(DIGEST_SHA3_256);
+
+  /* Order matters here that is any subsystem using this function should
+   * expect this very precise ordering in the MAC construction. */
+  crypto_digest_add_bytes(digest, (const char *) &key_len_netorder,
+                          sizeof(key_len_netorder));
+  crypto_digest_add_bytes(digest, (const char *) key, key_len);
+  crypto_digest_add_bytes(digest, (const char *) msg, msg_len);
+  crypto_digest_get_digest(digest, (char *) mac_out, len_out);
+  crypto_digest_free(digest);
+}
+
 /** Internal state for a eXtendable-Output Function (XOF). */
 struct crypto_xof_t {
   keccak_state s;
diff --git a/src/common/crypto.h b/src/common/crypto.h
index 116e0a62fd..bf2fa06aaa 100644
--- a/src/common/crypto.h
+++ b/src/common/crypto.h
@@ -255,6 +255,10 @@ void crypto_digest_assign(crypto_digest_t *into,
 void crypto_hmac_sha256(char *hmac_out,
                         const char *key, size_t key_len,
                         const char *msg, size_t msg_len);
+void crypto_mac_sha3_256(uint8_t *mac_out, size_t len_out,
+                         const uint8_t *key, size_t key_len,
+                         const uint8_t *msg, size_t msg_len);
+
 crypto_xof_t *crypto_xof_new(void);
 void crypto_xof_add_bytes(crypto_xof_t *xof, const uint8_t *data, size_t len);
 void crypto_xof_squeeze_bytes(crypto_xof_t *xof, uint8_t *out, size_t len);
diff --git a/src/common/crypto_ed25519.c b/src/common/crypto_ed25519.c
index b7c8311475..8977e7a325 100644
--- a/src/common/crypto_ed25519.c
+++ b/src/common/crypto_ed25519.c
@@ -275,11 +275,11 @@ ed25519_sign(ed25519_signature_t *signature_out,
  * Like ed25519_sign(), but also prefix <b>msg</b> with <b>prefix_str</b>
  * before signing. <b>prefix_str</b> must be a NUL-terminated string.
  */
-int
-ed25519_sign_prefixed(ed25519_signature_t *signature_out,
-                      const uint8_t *msg, size_t msg_len,
-                      const char *prefix_str,
-                      const ed25519_keypair_t *keypair)
+MOCK_IMPL(int,
+ed25519_sign_prefixed,(ed25519_signature_t *signature_out,
+                       const uint8_t *msg, size_t msg_len,
+                       const char *prefix_str,
+                       const ed25519_keypair_t *keypair))
 {
   int retval;
   size_t prefixed_msg_len;
diff --git a/src/common/crypto_ed25519.h b/src/common/crypto_ed25519.h
index a58b416943..56782cc12e 100644
--- a/src/common/crypto_ed25519.h
+++ b/src/common/crypto_ed25519.h
@@ -55,11 +55,12 @@ int ed25519_checksig(const ed25519_signature_t *signature,
                      const uint8_t *msg, size_t len,
                      const ed25519_public_key_t *pubkey);
 
-int
-ed25519_sign_prefixed(ed25519_signature_t *signature_out,
-                      const uint8_t *msg, size_t len,
-                      const char *prefix_str,
-                      const ed25519_keypair_t *keypair);
+MOCK_DECL(int,
+ed25519_sign_prefixed,(ed25519_signature_t *signature_out,
+                       const uint8_t *msg, size_t len,
+                       const char *prefix_str,
+                       const ed25519_keypair_t *keypair));
+
 int
 ed25519_checksig_prefixed(const ed25519_signature_t *signature,
                           const uint8_t *msg, size_t len,
diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c
index dee103e36a..b7ae3f5f48 100644
--- a/src/or/circuitlist.c
+++ b/src/or/circuitlist.c
@@ -63,6 +63,7 @@
 #include "connection_edge.h"
 #include "connection_or.h"
 #include "control.h"
+#include "hs_circuitmap.h"
 #include "main.h"
 #include "hs_common.h"
 #include "networkstatus.h"
@@ -93,9 +94,6 @@ static smartlist_t *circuits_pending_close = NULL;
 
 static void circuit_free_cpath_node(crypt_path_t *victim);
 static void cpath_ref_decref(crypt_path_reference_t *cpath_ref);
-//static void circuit_set_rend_token(or_circuit_t *circ, int is_rend_circ,
-//                                   const uint8_t *token);
-static void circuit_clear_rend_token(or_circuit_t *circ);
 static void circuit_about_to_free_atexit(circuit_t *circ);
 static void circuit_about_to_free(circuit_t *circ);
 
@@ -866,7 +864,9 @@ circuit_free(circuit_t *circ)
     crypto_cipher_free(ocirc->n_crypto);
     crypto_digest_free(ocirc->n_digest);
 
-    circuit_clear_rend_token(ocirc);
+    if (ocirc->hs_token) {
+      hs_circuitmap_remove_circuit(ocirc);
+    }
 
     if (ocirc->rend_splice) {
       or_circuit_t *other = ocirc->rend_splice;
@@ -1409,177 +1409,6 @@ circuit_get_next_by_pk_and_purpose(origin_circuit_t *start,
   return NULL;
 }
 
-/** Map from rendezvous cookie to or_circuit_t */
-static digestmap_t *rend_cookie_map = NULL;
-
-/** Map from introduction point digest to or_circuit_t */
-static digestmap_t *intro_digest_map = NULL;
-
-/** Return the OR circuit whose purpose is <b>purpose</b>, and whose
- * rend_token is the REND_TOKEN_LEN-byte <b>token</b>. If <b>is_rend_circ</b>,
- * look for rendezvous point circuits; otherwise look for introduction point
- * circuits. */
-static or_circuit_t *
-circuit_get_by_rend_token_and_purpose(uint8_t purpose, int is_rend_circ,
-                                      const char *token)
-{
-  or_circuit_t *circ;
-  digestmap_t *map = is_rend_circ ? rend_cookie_map : intro_digest_map;
-
-  if (!map)
-    return NULL;
-
-  circ = digestmap_get(map, token);
-  if (!circ ||
-      circ->base_.purpose != purpose ||
-      circ->base_.marked_for_close)
-    return NULL;
-
-  if (!circ->rendinfo) {
-    char *t = tor_strdup(hex_str(token, REND_TOKEN_LEN));
-    log_warn(LD_BUG, "Wanted a circuit with %s:%d, but lookup returned a "
-             "circuit with no rendinfo set.",
-             safe_str(t), is_rend_circ);
-    tor_free(t);
-    return NULL;
-  }
-
-  if (! bool_eq(circ->rendinfo->is_rend_circ, is_rend_circ) ||
-      tor_memneq(circ->rendinfo->rend_token, token, REND_TOKEN_LEN)) {
-    char *t = tor_strdup(hex_str(token, REND_TOKEN_LEN));
-    log_warn(LD_BUG, "Wanted a circuit with %s:%d, but lookup returned %s:%d",
-             safe_str(t), is_rend_circ,
-             safe_str(hex_str(circ->rendinfo->rend_token, REND_TOKEN_LEN)),
-             (int)circ->rendinfo->is_rend_circ);
-    tor_free(t);
-    return NULL;
-  }
-
-  return circ;
-}
-
-/** Clear the rendezvous cookie or introduction point key digest that's
- * configured on <b>circ</b>, if any, and remove it from any such maps. */
-static void
-circuit_clear_rend_token(or_circuit_t *circ)
-{
-  or_circuit_t *found_circ;
-  digestmap_t *map;
-
-  if (!circ || !circ->rendinfo)
-    return;
-
-  map = circ->rendinfo->is_rend_circ ? rend_cookie_map : intro_digest_map;
-
-  if (!map) {
-    log_warn(LD_BUG, "Tried to clear rend token on circuit, but found no map");
-    return;
-  }
-
-  found_circ = digestmap_get(map, circ->rendinfo->rend_token);
-  if (found_circ == circ) {
-    /* Great, this is the right one. */
-    digestmap_remove(map, circ->rendinfo->rend_token);
-  } else if (found_circ) {
-    log_warn(LD_BUG, "Tried to clear rend token on circuit, but "
-             "it was already replaced in the map.");
-  } else {
-    log_warn(LD_BUG, "Tried to clear rend token on circuit, but "
-             "it not in the map at all.");
-  }
-
-  tor_free(circ->rendinfo); /* Sets it to NULL too */
-}
-
-/** Set the rendezvous cookie (if is_rend_circ), or the introduction point
- * digest (if ! is_rend_circ) of <b>circ</b> to the REND_TOKEN_LEN-byte value
- * in <b>token</b>, and add it to the appropriate map.  If it previously had a
- * token, clear it.  If another circuit previously had the same
- * cookie/intro-digest, mark that circuit and remove it from the map. */
-static void
-circuit_set_rend_token(or_circuit_t *circ, int is_rend_circ,
-                       const uint8_t *token)
-{
-  digestmap_t **map_p, *map;
-  or_circuit_t *found_circ;
-
-  /* Find the right map, creating it as needed */
-  map_p = is_rend_circ ? &rend_cookie_map : &intro_digest_map;
-
-  if (!*map_p)
-    *map_p = digestmap_new();
-
-  map = *map_p;
-
-  /* If this circuit already has a token, we need to remove that. */
-  if (circ->rendinfo)
-    circuit_clear_rend_token(circ);
-
-  if (token == NULL) {
-    /* We were only trying to remove this token, not set a new one. */
-    return;
-  }
-
-  found_circ = digestmap_get(map, (const char *)token);
-  if (found_circ) {
-    tor_assert(found_circ != circ);
-    circuit_clear_rend_token(found_circ);
-    if (! found_circ->base_.marked_for_close) {
-      circuit_mark_for_close(TO_CIRCUIT(found_circ), END_CIRC_REASON_FINISHED);
-      if (is_rend_circ) {
-        log_fn(LOG_PROTOCOL_WARN, LD_REND,
-               "Duplicate rendezvous cookie (%s...) used on two circuits",
-               hex_str((const char*)token, 4)); /* only log first 4 chars */
-      }
-    }
-  }
-
-  /* Now set up the rendinfo */
-  circ->rendinfo = tor_malloc(sizeof(*circ->rendinfo));
-  memcpy(circ->rendinfo->rend_token, token, REND_TOKEN_LEN);
-  circ->rendinfo->is_rend_circ = is_rend_circ ? 1 : 0;
-
-  digestmap_set(map, (const char *)token, circ);
-}
-
-/** Return the circuit waiting for a rendezvous with the provided cookie.
- * Return NULL if no such circuit is found.
- */
-or_circuit_t *
-circuit_get_rendezvous(const uint8_t *cookie)
-{
-  return circuit_get_by_rend_token_and_purpose(
-                                     CIRCUIT_PURPOSE_REND_POINT_WAITING,
-                                     1, (const char*)cookie);
-}
-
-/** Return the circuit waiting for intro cells of the given digest.
- * Return NULL if no such circuit is found.
- */
-or_circuit_t *
-circuit_get_intro_point(const uint8_t *digest)
-{
-  return circuit_get_by_rend_token_and_purpose(
-                                     CIRCUIT_PURPOSE_INTRO_POINT, 0,
-                                     (const char *)digest);
-}
-
-/** Set the rendezvous cookie of <b>circ</b> to <b>cookie</b>.  If another
- * circuit previously had that cookie, mark it. */
-void
-circuit_set_rendezvous_cookie(or_circuit_t *circ, const uint8_t *cookie)
-{
-  circuit_set_rend_token(circ, 1, cookie);
-}
-
-/** Set the intro point key digest of <b>circ</b> to <b>cookie</b>.  If another
- * circuit previously had that intro point digest, mark it. */
-void
-circuit_set_intro_point_digest(or_circuit_t *circ, const uint8_t *digest)
-{
-  circuit_set_rend_token(circ, 0, digest);
-}
-
 /** Return a circuit that is open, is CIRCUIT_PURPOSE_C_GENERAL,
  * has a timestamp_dirty value of 0, has flags matching the CIRCLAUNCH_*
  * flags in <b>flags</b>, and if info is defined, does not already use info
diff --git a/src/or/circuitlist.h b/src/or/circuitlist.h
index 989c02afd5..b38b6d1afa 100644
--- a/src/or/circuitlist.h
+++ b/src/or/circuitlist.h
@@ -46,10 +46,6 @@ 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 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);
-void circuit_set_intro_point_digest(or_circuit_t *circ, const uint8_t *digest);
 origin_circuit_t *circuit_find_to_cannibalize(uint8_t purpose,
                                               extend_info_t *info, int flags);
 void circuit_mark_all_unused_circs(void);
diff --git a/src/or/hs_circuitmap.c b/src/or/hs_circuitmap.c
new file mode 100644
index 0000000000..790c4d3b84
--- /dev/null
+++ b/src/or/hs_circuitmap.c
@@ -0,0 +1,328 @@
+/* Copyright (c) 2016, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file hs_circuitmap.c
+ *
+ * \brief Manage the hidden service circuitmap: A hash table that maps binary
+ *  tokens to introduction and rendezvous circuits.
+ **/
+
+#define HS_CIRCUITMAP_PRIVATE
+
+#include "or.h"
+#include "config.h"
+#include "circuitlist.h"
+#include "hs_circuitmap.h"
+
+/************************** HS circuitmap code *******************************/
+
+/* This is the hidden service circuitmap. It's a hash table that maps
+   introduction and rendezvous tokens to specific circuits such that given a
+   token it's easy to find the corresponding circuit. */
+static struct hs_circuitmap_ht *the_hs_circuitmap = NULL;
+
+/* This is a helper function used by the hash table code (HT_). It returns 1 if
+ * two circuits have the same HS token. */
+static int
+hs_circuits_have_same_token(const or_circuit_t *first_circuit,
+                            const or_circuit_t *second_circuit)
+{
+  const hs_token_t *first_token;
+  const hs_token_t *second_token;
+
+  tor_assert(first_circuit);
+  tor_assert(second_circuit);
+
+  first_token = first_circuit->hs_token;
+  second_token = second_circuit->hs_token;
+
+  /* Both circs must have a token */
+  if (BUG(!first_token) || BUG(!second_token)) {
+    return 0;
+  }
+
+  if (first_token->type != second_token->type) {
+    return 0;
+  }
+
+  if (first_token->token_len != second_token->token_len)
+    return 0;
+
+  return tor_memeq(first_token->token,
+                   second_token->token,
+                   first_token->token_len);
+}
+
+/* This is a helper function for the hash table code (HT_). It hashes a circuit
+ * HS token into an unsigned int for use as a key by the hash table routines.*/
+static inline unsigned int
+hs_circuit_hash_token(const or_circuit_t *circuit)
+{
+  tor_assert(circuit->hs_token);
+
+  return (unsigned) siphash24g(circuit->hs_token->token,
+                               circuit->hs_token->token_len);
+}
+
+/* Register the circuitmap hash table */
+HT_PROTOTYPE(hs_circuitmap_ht, // The name of the hashtable struct
+             or_circuit_t,    // The name of the element struct,
+             hs_circuitmap_node,        // The name of HT_ENTRY member
+             hs_circuit_hash_token, hs_circuits_have_same_token);
+
+HT_GENERATE2(hs_circuitmap_ht, or_circuit_t, hs_circuitmap_node,
+             hs_circuit_hash_token, hs_circuits_have_same_token,
+             0.6, tor_reallocarray, tor_free_);
+
+#ifdef TOR_UNIT_TESTS
+
+/* Return the global HS circuitmap. Used by unittests. */
+hs_circuitmap_ht *
+get_hs_circuitmap(void)
+{
+  return the_hs_circuitmap;
+}
+
+#endif
+
+/****************** HS circuitmap utility functions **************************/
+
+/** Return a new HS token of type <b>type</b> containing <b>token</b>. */
+static hs_token_t *
+hs_token_new(hs_token_type_t type, size_t token_len,
+             const uint8_t *token)
+{
+  tor_assert(token);
+
+  hs_token_t *hs_token = tor_malloc_zero(sizeof(hs_token_t));
+  hs_token->type = type;
+  hs_token->token_len = token_len;
+  hs_token->token = tor_memdup(token, token_len);
+
+  return hs_token;
+}
+
+/** Free memory allocated by this <b>hs_token</b>. */
+static void
+hs_token_free(hs_token_t *hs_token)
+{
+  if (!hs_token) {
+    return;
+  }
+
+  tor_free(hs_token->token);
+  tor_free(hs_token);
+}
+
+/** Return the circuit from the circuitmap with token <b>search_token</b>. */
+static or_circuit_t *
+get_circuit_with_token(hs_token_t *search_token)
+{
+  tor_assert(the_hs_circuitmap);
+
+  /* We use a dummy circuit object for the hash table search routine. */
+  or_circuit_t search_circ;
+  search_circ.hs_token = search_token;
+  return HT_FIND(hs_circuitmap_ht, the_hs_circuitmap, &search_circ);
+}
+
+/* Helper function that registers <b>circ</b> with <b>token</b> on the HS
+   circuitmap. This function steals reference of <b>token</b>. */
+static void
+hs_circuitmap_register_impl(or_circuit_t *circ, hs_token_t *token)
+{
+  tor_assert(circ);
+  tor_assert(token);
+  tor_assert(the_hs_circuitmap);
+
+  /* If this circuit already has a token, clear it. */
+  if (circ->hs_token) {
+    hs_circuitmap_remove_circuit(circ);
+  }
+
+  /* Kill old circuits with the same token. We want new intro/rend circuits to
+     take precedence over old ones, so that HSes and clients and reestablish
+     killed circuits without changing the HS token. */
+  {
+    or_circuit_t *found_circ;
+    found_circ = get_circuit_with_token(token);
+    if (found_circ) {
+      hs_circuitmap_remove_circuit(found_circ);
+      if (!found_circ->base_.marked_for_close) {
+        circuit_mark_for_close(TO_CIRCUIT(found_circ),
+                               END_CIRC_REASON_FINISHED);
+      }
+    }
+  }
+
+  /* Register circuit and token to circuitmap. */
+  circ->hs_token = token;
+  HT_INSERT(hs_circuitmap_ht, the_hs_circuitmap, circ);
+}
+
+/** Helper function: Register <b>circ</b> of <b>type</b> on the HS
+ *  circuitmap. Use the HS <b>token</b> as the key to the hash table.  If
+ *  <b>token</b> is not set, clear the circuit of any HS tokens. */
+static void
+hs_circuitmap_register_circuit(or_circuit_t *circ,
+                               hs_token_type_t type, size_t token_len,
+                               const uint8_t *token)
+{
+  hs_token_t *hs_token = NULL;
+
+  /* Create a new token and register it to the circuitmap */
+  tor_assert(token);
+  hs_token = hs_token_new(type, token_len, token);
+  tor_assert(hs_token);
+  hs_circuitmap_register_impl(circ, hs_token);
+}
+
+/* Query circuitmap for circuit with <b>token</b> of size <b>token_len</b>.
+ * Only returns a circuit with purpose equal to the <b>wanted_circ_purpose</b>
+ * parameter and if it is NOT marked for close. Return NULL if no such circuit
+ * is found. */
+static or_circuit_t *
+hs_circuitmap_get_circuit(hs_token_type_t type,
+                          size_t token_len,
+                          const uint8_t *token,
+                          uint8_t wanted_circ_purpose)
+{
+  or_circuit_t *found_circ = NULL;
+
+  tor_assert(the_hs_circuitmap);
+
+  /* Check the circuitmap if we have a circuit with this token */
+  {
+    hs_token_t *search_hs_token = hs_token_new(type, token_len, token);
+    tor_assert(search_hs_token);
+    found_circ = get_circuit_with_token(search_hs_token);
+    hs_token_free(search_hs_token);
+  }
+
+  /* Check that the circuit is useful to us */
+  if (!found_circ ||
+      found_circ->base_.purpose != wanted_circ_purpose ||
+      found_circ->base_.marked_for_close) {
+    return NULL;
+  }
+
+  return found_circ;
+}
+
+/************** Public circuitmap API ****************************************/
+
+/* Public function: Return v3 introduction circuit with <b>auth_key</b>. Return
+ * NULL if no such circuit is found in the circuitmap. */
+or_circuit_t *
+hs_circuitmap_get_intro_circ_v3(const ed25519_public_key_t *auth_key)
+{
+  tor_assert(auth_key);
+
+  return hs_circuitmap_get_circuit(HS_TOKEN_INTRO_V3,
+                                   ED25519_PUBKEY_LEN, auth_key->pubkey,
+                                   CIRCUIT_PURPOSE_INTRO_POINT);
+}
+
+/* Public function: Return v2 introduction circuit with <b>digest</b>. Return
+ * NULL if no such circuit is found in the circuitmap. */
+or_circuit_t *
+hs_circuitmap_get_intro_circ_v2(const uint8_t *digest)
+{
+  tor_assert(digest);
+
+  return hs_circuitmap_get_circuit(HS_TOKEN_INTRO_V2,
+                                   REND_TOKEN_LEN, digest,
+                                   CIRCUIT_PURPOSE_INTRO_POINT);
+}
+
+/* Public function: Return rendezvous circuit with rendezvous
+ * <b>cookie</b>. Return NULL if no such circuit is found in the circuitmap. */
+or_circuit_t *
+hs_circuitmap_get_rend_circ(const uint8_t *cookie)
+{
+  tor_assert(cookie);
+
+  return hs_circuitmap_get_circuit(HS_TOKEN_REND,
+                                   REND_TOKEN_LEN, cookie,
+                                   CIRCUIT_PURPOSE_REND_POINT_WAITING);
+}
+
+/* Public function: Register rendezvous circuit with key <b>cookie</b> to the
+ * circuitmap. */
+void
+hs_circuitmap_register_rend_circ(or_circuit_t *circ, const uint8_t *cookie)
+{
+  hs_circuitmap_register_circuit(circ,
+                                 HS_TOKEN_REND,
+                                 REND_TOKEN_LEN, cookie);
+}
+
+/* Public function: Register v2 intro circuit with key <b>digest</b> to the
+ * circuitmap. */
+void
+hs_circuitmap_register_intro_circ_v2(or_circuit_t *circ, const uint8_t *digest)
+{
+  hs_circuitmap_register_circuit(circ,
+                                 HS_TOKEN_INTRO_V2,
+                                 REND_TOKEN_LEN, digest);
+}
+
+/* Public function: Register v3 intro circuit with key <b>auth_key</b> to the
+ * circuitmap. */
+void
+hs_circuitmap_register_intro_circ_v3(or_circuit_t *circ,
+                                     const ed25519_public_key_t *auth_key)
+{
+  hs_circuitmap_register_circuit(circ,
+                                 HS_TOKEN_INTRO_V3,
+                                 ED25519_PUBKEY_LEN, auth_key->pubkey);
+}
+
+/** Remove this circuit from the HS circuitmap. Clear its HS token, and remove
+ *  it from the hashtable. */
+void
+hs_circuitmap_remove_circuit(or_circuit_t *circ)
+{
+  tor_assert(the_hs_circuitmap);
+
+  if (!circ || !circ->hs_token) {
+    return;
+  }
+
+  /* Remove circ from circuitmap */
+  or_circuit_t *tmp;
+  tmp = HT_REMOVE(hs_circuitmap_ht, the_hs_circuitmap, circ);
+  /* ... and ensure the removal was successful. */
+  if (tmp) {
+    tor_assert(tmp == circ);
+  } else {
+    log_warn(LD_BUG, "Could not find circuit (%u) in circuitmap.",
+             circ->p_circ_id);
+  }
+
+  /* Clear token from circ */
+  hs_token_free(circ->hs_token);
+  circ->hs_token = NULL;
+}
+
+/* Initialize the global HS circuitmap. */
+void
+hs_circuitmap_init(void)
+{
+  tor_assert(!the_hs_circuitmap);
+
+  the_hs_circuitmap = tor_malloc_zero(sizeof(struct hs_circuitmap_ht));
+  HT_INIT(hs_circuitmap_ht, the_hs_circuitmap);
+}
+
+/* Free all memory allocated by the global HS circuitmap. */
+void
+hs_circuitmap_free_all(void)
+{
+  tor_assert(the_hs_circuitmap);
+
+  HT_CLEAR(hs_circuitmap_ht, the_hs_circuitmap);
+  tor_free(the_hs_circuitmap);
+}
+
diff --git a/src/or/hs_circuitmap.h b/src/or/hs_circuitmap.h
new file mode 100644
index 0000000000..a2be97c029
--- /dev/null
+++ b/src/or/hs_circuitmap.h
@@ -0,0 +1,69 @@
+/* Copyright (c) 2016, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file hs_circuitmap.h
+ * \brief Header file for hs_circuitmap.c.
+ **/
+
+#ifndef TOR_HS_CIRCUITMAP_H
+#define TOR_HS_CIRCUITMAP_H
+
+typedef HT_HEAD(hs_circuitmap_ht, or_circuit_t) hs_circuitmap_ht;
+
+typedef struct hs_token_s hs_token_t;
+typedef struct or_circuit_t or_circuit_t;
+
+/** Public HS circuitmap API: */
+
+or_circuit_t *hs_circuitmap_get_rend_circ(const uint8_t *cookie);
+or_circuit_t *
+hs_circuitmap_get_intro_circ_v3(const ed25519_public_key_t *auth_key);
+or_circuit_t *hs_circuitmap_get_intro_circ_v2(const uint8_t *digest);
+
+void hs_circuitmap_register_rend_circ(or_circuit_t *circ,
+                                      const uint8_t *cookie);
+void hs_circuitmap_register_intro_circ_v2(or_circuit_t *circ,
+                                          const uint8_t *digest);
+void hs_circuitmap_register_intro_circ_v3(or_circuit_t *circ,
+                                         const ed25519_public_key_t *auth_key);
+
+void hs_circuitmap_remove_circuit(or_circuit_t *circ);
+
+void hs_circuitmap_init(void);
+void hs_circuitmap_free_all(void);
+
+#ifdef HS_CIRCUITMAP_PRIVATE
+
+/** Represents the type of HS token. */
+typedef enum {
+  /** A rendezvous cookie (128bit)*/
+  HS_TOKEN_REND,
+  /** A v2 introduction point pubkey (160bit) */
+  HS_TOKEN_INTRO_V2,
+  /** A v3 introduction point pubkey (256bit) */
+  HS_TOKEN_INTRO_V3,
+} hs_token_type_t;
+
+/** Represents a token used in the HS protocol. Each such token maps to a
+ *  specific introduction or rendezvous circuit. */
+struct hs_token_s {
+  /* Type of HS token. */
+  hs_token_type_t type;
+
+  /* The size of the token (depends on the type). */
+  size_t token_len;
+
+  /* The token itself. Memory allocated at runtime. */
+  uint8_t *token;
+};
+
+#endif /* HS_CIRCUITMAP_PRIVATE */
+
+#ifdef TOR_UNIT_TESTS
+
+hs_circuitmap_ht *get_hs_circuitmap(void);
+
+#endif /* TOR_UNIT_TESTS */
+
+#endif /* TOR_HS_CIRCUITMAP_H */
diff --git a/src/or/hs_common.h b/src/or/hs_common.h
index 2502f35ad4..55710b7f79 100644
--- a/src/or/hs_common.h
+++ b/src/or/hs_common.h
@@ -17,6 +17,12 @@
 /* Version 3 of the protocol (prop224). */
 #define HS_VERSION_THREE 3
 
+/* Denotes ed25519 authentication key on ESTABLISH_INTRO cell. */
+#define AUTH_KEY_ED25519 0x02
+
+/* String prefix for the signature of ESTABLISH_INTRO */
+#define ESTABLISH_INTRO_SIG_PREFIX "Tor establish-intro cell v1"
+
 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,
@@ -36,4 +42,3 @@ const uint8_t *rend_data_get_pk_digest(const rend_data_t *rend_data,
 int hs_v3_protocol_is_enabled(void);
 
 #endif /* TOR_HS_COMMON_H */
-
diff --git a/src/or/hs_intropoint.c b/src/or/hs_intropoint.c
new file mode 100644
index 0000000000..67355bc44b
--- /dev/null
+++ b/src/or/hs_intropoint.c
@@ -0,0 +1,288 @@
+/* Copyright (c) 2016, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file hs_intropoint.c
+ * \brief Implement next generation introductions point functionality
+ **/
+
+#define HS_INTROPOINT_PRIVATE
+
+#include "or.h"
+#include "circuitlist.h"
+#include "circuituse.h"
+#include "config.h"
+#include "relay.h"
+#include "rendmid.h"
+#include "rephist.h"
+
+#include "hs/cell_establish_intro.h"
+#include "hs/cell_common.h"
+#include "hs_circuitmap.h"
+#include "hs_intropoint.h"
+#include "hs_common.h"
+
+/** Extract the authentication key from an ESTABLISH_INTRO <b>cell</b> and
+ *  place it in <b>auth_key_out</b>. */
+STATIC void
+get_auth_key_from_establish_intro_cell(ed25519_public_key_t *auth_key_out,
+                                       const hs_cell_establish_intro_t *cell)
+{
+  tor_assert(auth_key_out);
+
+  const uint8_t *key_array =
+    hs_cell_establish_intro_getconstarray_auth_key(cell);
+  tor_assert(key_array);
+  tor_assert(hs_cell_establish_intro_getlen_auth_key(cell) ==
+             sizeof(auth_key_out->pubkey));
+
+  memcpy(auth_key_out->pubkey, key_array, cell->auth_key_len);
+}
+
+/** We received an ESTABLISH_INTRO <b>cell</b>. Verify its signature and MAC,
+ *  given <b>circuit_key_material</b>. Return 0 on success else -1 on error. */
+STATIC int
+verify_establish_intro_cell(const hs_cell_establish_intro_t *cell,
+                            const uint8_t *circuit_key_material,
+                            size_t circuit_key_material_len)
+{
+  /* We only reach this function if the first byte of the cell is 0x02 which
+   * means that auth_key_type is AUTH_KEY_ED25519, hence this check should
+   * always pass. See hs_intro_received_establish_intro().  */
+  if (BUG(cell->auth_key_type != AUTH_KEY_ED25519)) {
+    return -1;
+  }
+
+  /* Make sure the auth key length is of the right size for this type. For
+   * EXTRA safety, we check both the size of the array and the length which
+   * must be the same. Safety first!*/
+  if (hs_cell_establish_intro_getlen_auth_key(cell) != ED25519_PUBKEY_LEN ||
+      hs_cell_establish_intro_get_auth_key_len(cell) != ED25519_PUBKEY_LEN) {
+    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+           "ESTABLISH_INTRO auth key length is invalid");
+    return -1;
+  }
+
+  const uint8_t *msg = cell->start_cell;
+
+  /* Verify the sig */
+  {
+    ed25519_signature_t sig_struct;
+    const uint8_t *sig_array = hs_cell_establish_intro_getconstarray_sig(cell);
+
+    if (hs_cell_establish_intro_getlen_sig(cell) != sizeof(sig_struct.sig)) {
+      log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+             "ESTABLISH_INTRO sig len is invalid");
+      return -1;
+    }
+    /* We are now sure that sig_len is of the right size. */
+    memcpy(sig_struct.sig, sig_array, cell->sig_len);
+
+    ed25519_public_key_t auth_key;
+    get_auth_key_from_establish_intro_cell(&auth_key, cell);
+
+    const size_t sig_msg_len = cell->end_sig_fields - msg;
+    int sig_mismatch = ed25519_checksig_prefixed(&sig_struct,
+                                                 (uint8_t*) msg, sig_msg_len,
+                                                 ESTABLISH_INTRO_SIG_PREFIX,
+                                                 &auth_key);
+    if (sig_mismatch) {
+      log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+             "ESTABLISH_INTRO signature not as expected");
+      return -1;
+    }
+  }
+
+  /* Verify the MAC */
+  {
+    const size_t auth_msg_len = cell->end_mac_fields - msg;
+    uint8_t mac[DIGEST256_LEN];
+    crypto_mac_sha3_256(mac, sizeof(mac),
+                        circuit_key_material, circuit_key_material_len,
+                        msg, auth_msg_len);
+    if (tor_memneq(mac, cell->handshake_mac, sizeof(mac))) {
+      log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+             "ESTABLISH_INTRO handshake_auth not as expected");
+      return -1;
+    }
+  }
+
+  return 0;
+}
+
+/* Send an INTRO_ESTABLISHED cell to <b>circ</b>. */
+MOCK_IMPL(int,
+hs_intro_send_intro_established_cell,(or_circuit_t *circ))
+{
+  int ret;
+  uint8_t *encoded_cell = NULL;
+  ssize_t encoded_len, result_len;
+  hs_cell_intro_established_t *cell;
+  cell_extension_t *ext;
+
+  tor_assert(circ);
+
+  /* Build the cell payload. */
+  cell = hs_cell_intro_established_new();
+  ext = cell_extension_new();
+  cell_extension_set_num(ext, 0);
+  hs_cell_intro_established_set_extensions(cell, ext);
+  /* Encode the cell to binary format. */
+  encoded_len = hs_cell_intro_established_encoded_len(cell);
+  tor_assert(encoded_len > 0);
+  encoded_cell = tor_malloc_zero(encoded_len);
+  result_len = hs_cell_intro_established_encode(encoded_cell, encoded_len,
+                                                cell);
+  tor_assert(encoded_len == result_len);
+
+  ret = relay_send_command_from_edge(0, TO_CIRCUIT(circ),
+                                     RELAY_COMMAND_INTRO_ESTABLISHED,
+                                     (char *) encoded_cell, encoded_len,
+                                     NULL);
+  /* On failure, the above function will close the circuit. */
+  hs_cell_intro_established_free(cell);
+  tor_free(encoded_cell);
+  return ret;
+}
+
+/** We received an ESTABLISH_INTRO <b>parsed_cell</b> on <b>circ</b>. It's
+ *  well-formed and passed our verifications. Perform appropriate actions to
+ *  establish an intro point. */
+static int
+handle_verified_establish_intro_cell(or_circuit_t *circ,
+                               const hs_cell_establish_intro_t *parsed_cell)
+{
+  /* Get the auth key of this intro point */
+  ed25519_public_key_t auth_key;
+  get_auth_key_from_establish_intro_cell(&auth_key, parsed_cell);
+
+  /* Then notify the hidden service that the intro point is established by
+     sending an INTRO_ESTABLISHED cell */
+  if (hs_intro_send_intro_established_cell(circ)) {
+    log_warn(LD_BUG, "Couldn't send INTRO_ESTABLISHED cell.");
+    return -1;
+  }
+
+  /* Associate intro point auth key with this circuit. */
+  hs_circuitmap_register_intro_circ_v3(circ, &auth_key);
+  /* Repurpose this circuit into an intro circuit. */
+  circuit_change_purpose(TO_CIRCUIT(circ), CIRCUIT_PURPOSE_INTRO_POINT);
+
+  return 0;
+}
+
+/** We just received an ESTABLISH_INTRO cell in <b>circ</b> with payload in
+ *  <b>request</b>. Handle it by making <b>circ</b> an intro circuit. Return 0
+ *  if everything went well, or -1 if there were errors. */
+static int
+handle_establish_intro(or_circuit_t *circ, const uint8_t *request,
+                       size_t request_len)
+{
+  int cell_ok, retval = -1;
+  hs_cell_establish_intro_t *parsed_cell = NULL;
+
+  tor_assert(circ);
+  tor_assert(request);
+
+  log_info(LD_REND, "Received an ESTABLISH_INTRO request on circuit %" PRIu32,
+           circ->p_circ_id);
+
+  /* Check that the circuit is in shape to become an intro point */
+  if (!hs_intro_circuit_is_suitable(circ)) {
+    goto err;
+  }
+
+  /* Parse the cell */
+  ssize_t parsing_result = hs_cell_establish_intro_parse(&parsed_cell,
+                                                         request, request_len);
+  if (parsing_result < 0) {
+    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+           "Rejecting %s ESTABLISH_INTRO cell.",
+           parsing_result == -1 ? "invalid" : "truncated");
+    goto err;
+  }
+
+  cell_ok = verify_establish_intro_cell(parsed_cell,
+                                        (uint8_t *) circ->rend_circ_nonce,
+                                        sizeof(circ->rend_circ_nonce));
+  if (cell_ok < 0) {
+    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+           "Failed to verify ESTABLISH_INTRO cell.");
+    goto err;
+  }
+
+  /* This cell is legit. Take the appropriate actions. */
+  cell_ok = handle_verified_establish_intro_cell(circ, parsed_cell);
+  if (cell_ok < 0) {
+    goto err;
+  }
+
+  log_warn(LD_GENERAL, "Established prop224 intro point on circuit %" PRIu32,
+           circ->p_circ_id);
+
+  /* We are done! */
+  retval = 0;
+  goto done;
+
+ err:
+  circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_TORPROTOCOL);
+
+ done:
+  hs_cell_establish_intro_free(parsed_cell);
+  return retval;
+}
+
+
+/* Return True if circuit is suitable for becoming an intro circuit. */
+int
+hs_intro_circuit_is_suitable(const or_circuit_t *circ)
+{
+  /* Basic circuit state sanity checks. */
+  if (circ->base_.purpose != CIRCUIT_PURPOSE_OR) {
+    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+           "Rejecting ESTABLISH_INTRO on non-OR circuit.");
+    return 0;
+  }
+
+  if (circ->base_.n_chan) {
+    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+           "Rejecting ESTABLISH_INTRO on non-edge circuit.");
+    return 0;
+  }
+
+  return 1;
+}
+
+/* We just received an ESTABLISH_INTRO cell in <b>circ</b>. Figure out of it's
+ * a legacy or a next gen cell, and pass it to the appropriate handler. */
+int
+hs_intro_received_establish_intro(or_circuit_t *circ, const uint8_t *request,
+                            size_t request_len)
+{
+  tor_assert(circ);
+  tor_assert(request);
+
+  if (request_len == 0) {
+    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL, "Empty ESTABLISH_INTRO cell.");
+    goto err;
+  }
+
+  /* Using the first byte of the cell, figure out the version of
+   * ESTABLISH_INTRO and pass it to the appropriate cell handler */
+  const uint8_t first_byte = request[0];
+  switch (first_byte) {
+    case HS_INTRO_AUTH_KEY_TYPE_LEGACY0:
+    case HS_INTRO_AUTH_KEY_TYPE_LEGACY1:
+      return rend_mid_establish_intro_legacy(circ, request, request_len);
+    case HS_INTRO_AUTH_KEY_TYPE_ED25519:
+      return handle_establish_intro(circ, request, request_len);
+    default:
+      log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+             "Unrecognized AUTH_KEY_TYPE %u.", first_byte);
+      goto err;
+  }
+
+ err:
+  circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_TORPROTOCOL);
+  return -1;
+}
diff --git a/src/or/hs_intropoint.h b/src/or/hs_intropoint.h
new file mode 100644
index 0000000000..b7846a4d8f
--- /dev/null
+++ b/src/or/hs_intropoint.h
@@ -0,0 +1,40 @@
+/* Copyright (c) 2016, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file hs_intropoint.h
+ * \brief Header file for hs_intropoint.c.
+ **/
+
+#ifndef TOR_HS_INTRO_H
+#define TOR_HS_INTRO_H
+
+/* Authentication key type in an ESTABLISH_INTRO cell. */
+enum hs_intro_auth_key_type {
+  HS_INTRO_AUTH_KEY_TYPE_LEGACY0 = 0x00,
+  HS_INTRO_AUTH_KEY_TYPE_LEGACY1 = 0x01,
+  HS_INTRO_AUTH_KEY_TYPE_ED25519 = 0x02,
+};
+
+int hs_intro_received_establish_intro(or_circuit_t *circ, const uint8_t *request,
+                                size_t request_len);
+
+MOCK_DECL(int, hs_intro_send_intro_established_cell,(or_circuit_t *circ));
+
+/* also used by rendservice.c */
+int hs_intro_circuit_is_suitable(const or_circuit_t *circ);
+
+#ifdef HS_INTROPOINT_PRIVATE
+
+STATIC int
+verify_establish_intro_cell(const hs_cell_establish_intro_t *out,
+                            const uint8_t *circuit_key_material,
+                            size_t circuit_key_material_len);
+
+STATIC void
+get_auth_key_from_establish_intro_cell(ed25519_public_key_t *auth_key_out,
+                                       const hs_cell_establish_intro_t *cell);
+
+#endif /* HS_INTROPOINT_PRIVATE */
+
+#endif /* TOR_HS_INTRO_H */
diff --git a/src/or/hs_service.c b/src/or/hs_service.c
new file mode 100644
index 0000000000..6f0836ca2e
--- /dev/null
+++ b/src/or/hs_service.c
@@ -0,0 +1,175 @@
+/* Copyright (c) 2016, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file hs_service.c
+ * \brief Implement next generation hidden service functionality
+ **/
+
+#define HS_SERVICE_PRIVATE
+
+#include "or.h"
+#include "relay.h"
+#include "rendservice.h"
+#include "circuitlist.h"
+#include "circpathbias.h"
+
+#include "hs_service.h"
+#include "hs_common.h"
+
+#include "hs/cell_establish_intro.h"
+#include "hs/cell_common.h"
+
+/* XXX We don't currently use these functions, apart from generating unittest
+   data. When we start implementing the service-side support for prop224 we
+   should revisit these functions and use them. For now we mark them as
+   unittest-only code: */
+#ifdef TOR_UNIT_TESTS
+
+/** Given an ESTABLISH_INTRO <b>cell</b>, encode it and place its payload in
+ *  <b>buf_out</b> which has size <b>buf_out_len</b>. Return the number of
+ *  bytes written, or a negative integer if there was an error. */
+STATIC ssize_t
+get_establish_intro_payload(uint8_t *buf_out, size_t buf_out_len,
+                            const hs_cell_establish_intro_t *cell)
+{
+  ssize_t bytes_used = 0;
+
+  if (buf_out_len < RELAY_PAYLOAD_SIZE) {
+    return -1;
+  }
+
+  bytes_used = hs_cell_establish_intro_encode(buf_out, buf_out_len,
+                                              cell);
+  return bytes_used;
+}
+
+/* Set the cell extensions of <b>cell</b>. */
+static void
+set_cell_extensions(hs_cell_establish_intro_t *cell)
+{
+  cell_extension_t *cell_extensions = cell_extension_new();
+
+  /* For now, we don't use extensions at all. */
+  cell_extensions->num = 0; /* It's already zeroed, but be explicit. */
+  hs_cell_establish_intro_set_extensions(cell, cell_extensions);
+}
+
+/** Given the circuit handshake info in <b>circuit_key_material</b>, create and
+ *  return an ESTABLISH_INTRO cell. Return NULL if something went wrong.  The
+ *  returned cell is allocated on the heap and it's the responsibility of the
+ *  caller to free it. */
+STATIC hs_cell_establish_intro_t *
+generate_establish_intro_cell(const uint8_t *circuit_key_material,
+                              size_t circuit_key_material_len)
+{
+  hs_cell_establish_intro_t *cell = NULL;
+  ssize_t encoded_len;
+
+  log_warn(LD_GENERAL,
+           "Generating ESTABLISH_INTRO cell (key_material_len: %u)",
+           (unsigned) circuit_key_material_len);
+
+  /* Generate short-term keypair for use in ESTABLISH_INTRO */
+  ed25519_keypair_t key_struct;
+  if (ed25519_keypair_generate(&key_struct, 0) < 0) {
+    goto err;
+  }
+
+  cell = hs_cell_establish_intro_new();
+
+  /* Set AUTH_KEY_TYPE: 2 means ed25519 */
+  hs_cell_establish_intro_set_auth_key_type(cell, AUTH_KEY_ED25519);
+
+  /* Set AUTH_KEY_LEN field */
+  /* Must also set byte-length of AUTH_KEY to match */
+  int auth_key_len = ED25519_PUBKEY_LEN;
+  hs_cell_establish_intro_set_auth_key_len(cell, auth_key_len);
+  hs_cell_establish_intro_setlen_auth_key(cell, auth_key_len);
+
+  /* Set AUTH_KEY field */
+  uint8_t *auth_key_ptr = hs_cell_establish_intro_getarray_auth_key(cell);
+  memcpy(auth_key_ptr, key_struct.pubkey.pubkey, auth_key_len);
+
+  /* No cell extensions needed */
+  set_cell_extensions(cell);
+
+  /* Set signature size.
+     We need to do this up here, because _encode() needs it and we need to call
+     _encode() to calculate the MAC and signature.
+  */
+  int sig_len = ED25519_SIG_LEN;
+  hs_cell_establish_intro_set_sig_len(cell, sig_len);
+  hs_cell_establish_intro_setlen_sig(cell, sig_len);
+
+  /* XXX How to make this process easier and nicer? */
+
+  /* Calculate the cell MAC (aka HANDSHAKE_AUTH). */
+  {
+    /* To calculate HANDSHAKE_AUTH, we dump the cell in bytes, and then derive
+       the MAC from it. */
+    uint8_t cell_bytes_tmp[RELAY_PAYLOAD_SIZE] = {0};
+    uint8_t mac[TRUNNEL_SHA3_256_LEN];
+
+    encoded_len = hs_cell_establish_intro_encode(cell_bytes_tmp,
+                                                 sizeof(cell_bytes_tmp),
+                                                 cell);
+    if (encoded_len < 0) {
+      log_warn(LD_OR, "Unable to pre-encode ESTABLISH_INTRO cell.");
+      goto err;
+    }
+
+    /* sanity check */
+    tor_assert(encoded_len > ED25519_SIG_LEN + 2 + TRUNNEL_SHA3_256_LEN);
+
+    /* Calculate MAC of all fields before HANDSHAKE_AUTH */
+    crypto_mac_sha3_256(mac, sizeof(mac),
+                        circuit_key_material, circuit_key_material_len,
+                        cell_bytes_tmp,
+                        encoded_len - (ED25519_SIG_LEN + 2 + TRUNNEL_SHA3_256_LEN));
+    /* Write the MAC to the cell */
+    uint8_t *handshake_ptr =
+      hs_cell_establish_intro_getarray_handshake_mac(cell);
+    memcpy(handshake_ptr, mac, sizeof(mac));
+  }
+
+  /* Calculate the cell signature */
+  {
+    /* To calculate the sig we follow the same procedure as above. We first
+       dump the cell up to the sig, and then calculate the sig */
+    uint8_t cell_bytes_tmp[RELAY_PAYLOAD_SIZE] = {0};
+    ed25519_signature_t sig;
+
+    encoded_len = hs_cell_establish_intro_encode(cell_bytes_tmp,
+                                                 sizeof(cell_bytes_tmp),
+                                                 cell);
+    if (encoded_len < 0) {
+      log_warn(LD_OR, "Unable to pre-encode ESTABLISH_INTRO cell (2).");
+      goto err;
+    }
+
+    tor_assert(encoded_len > ED25519_SIG_LEN);
+
+    if (ed25519_sign_prefixed(&sig,
+                              (uint8_t*) cell_bytes_tmp,
+                              encoded_len - ED25519_SIG_LEN,
+                              ESTABLISH_INTRO_SIG_PREFIX,
+                              &key_struct)) {
+      log_warn(LD_BUG, "Unable to gen signature for ESTABLISH_INTRO cell.");
+      goto err;
+    }
+
+    /* And write the signature to the cell */
+    uint8_t *sig_ptr = hs_cell_establish_intro_getarray_sig(cell);
+    memcpy(sig_ptr, sig.sig, sig_len);
+  }
+
+  /* We are done! Return the cell! */
+  return cell;
+
+ err:
+  hs_cell_establish_intro_free(cell);
+  return NULL;
+}
+
+#endif /* TOR_UNIT_TESTS */
diff --git a/src/or/hs_service.h b/src/or/hs_service.h
new file mode 100644
index 0000000000..a54a960b8c
--- /dev/null
+++ b/src/or/hs_service.h
@@ -0,0 +1,31 @@
+/* Copyright (c) 2016, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file hs_service.h
+ * \brief Header file for hs_service.c.
+ **/
+
+#ifndef TOR_HS_SERVICE_H
+#define TOR_HS_SERVICE_H
+
+#include "or.h"
+#include "hs/cell_establish_intro.h"
+
+#ifdef HS_SERVICE_PRIVATE
+
+#ifdef TOR_UNIT_TESTS
+
+STATIC hs_cell_establish_intro_t *
+generate_establish_intro_cell(const uint8_t *circuit_key_material,
+                              size_t circuit_key_material_len);
+
+STATIC ssize_t
+get_establish_intro_payload(uint8_t *buf, size_t buf_len,
+                            const hs_cell_establish_intro_t *cell);
+
+#endif /* TOR_UNIT_TESTS */
+
+#endif /* HS_SERVICE_PRIVATE */
+
+#endif /* TOR_HS_SERVICE_H */
diff --git a/src/or/include.am b/src/or/include.am
index 99912a9947..c0ab0bc3e1 100644
--- a/src/or/include.am
+++ b/src/or/include.am
@@ -45,6 +45,9 @@ LIBTOR_A_SOURCES = \
 	src/or/dnsserv.c				\
 	src/or/fp_pair.c				\
 	src/or/geoip.c					\
+	src/or/hs_intropoint.c          \
+	src/or/hs_circuitmap.c          \
+	src/or/hs_service.c             \
 	src/or/entrynodes.c				\
 	src/or/ext_orport.c				\
 	src/or/hibernate.c				\
@@ -164,6 +167,9 @@ ORHEADERS = \
 	src/or/hs_cache.h				\
 	src/or/hs_common.h				\
 	src/or/hs_descriptor.h				\
+	src/or/hs_intropoint.h          \
+	src/or/hs_circuitmap.h          \
+	src/or/hs_service.h             \
 	src/or/keypin.h					\
 	src/or/main.h					\
 	src/or/microdesc.h				\
diff --git a/src/or/main.c b/src/or/main.c
index 8239606c08..327b768842 100644
--- a/src/or/main.c
+++ b/src/or/main.c
@@ -74,6 +74,7 @@
 #include "geoip.h"
 #include "hibernate.h"
 #include "hs_cache.h"
+#include "hs_circuitmap.h"
 #include "keypin.h"
 #include "main.h"
 #include "microdesc.h"
@@ -2400,6 +2401,9 @@ do_main_loop(void)
     }
   }
 
+  /* Initialize relay-side HS circuitmap */
+  hs_circuitmap_init();
+
   /* set up once-a-second callback. */
   if (! second_timer) {
     struct timeval one_second;
@@ -3108,6 +3112,7 @@ tor_free_all(int postfork)
   connection_edge_free_all();
   scheduler_free_all();
   nodelist_free_all();
+  hs_circuitmap_free_all();
   microdesc_free_all();
   routerparse_free_all();
   ext_orport_free_all();
diff --git a/src/or/or.h b/src/or/or.h
index cfbd7b5c75..f63fe06a40 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -80,6 +80,7 @@
 #include "crypto_ed25519.h"
 #include "tor_queue.h"
 #include "util_format.h"
+#include "hs_circuitmap.h"
 
 /* These signals are defined to help handle_control_signal work.
  */
@@ -3355,7 +3356,12 @@ typedef struct or_circuit_t {
    * is not marked for close. */
   struct or_circuit_t *rend_splice;
 
-  struct or_circuit_rendinfo_s *rendinfo;
+  /** If set, points to an HS token that this circuit might be carrying.
+   *  Used by the HS circuitmap.  */
+  hs_token_t *hs_token;
+  /** Hashtable node: used to look up the circuit by its HS token using the HS
+      circuitmap. */
+  HT_ENTRY(or_circuit_t) hs_circuitmap_node;
 
   /** Stores KH for the handshake. */
   char rend_circ_nonce[DIGEST_LEN];/* KH in tor-spec.txt */
@@ -3390,25 +3396,11 @@ typedef struct or_circuit_t {
   uint32_t max_middle_cells;
 } or_circuit_t;
 
-typedef struct or_circuit_rendinfo_s {
-
 #if REND_COOKIE_LEN != DIGEST_LEN
 #error "The REND_TOKEN_LEN macro assumes REND_COOKIE_LEN == DIGEST_LEN"
 #endif
 #define REND_TOKEN_LEN DIGEST_LEN
 
-  /** A hash of location-hidden service's PK if purpose is INTRO_POINT, or a
-   * rendezvous cookie if purpose is REND_POINT_WAITING. Filled with zeroes
-   * otherwise.
-   */
-  char rend_token[REND_TOKEN_LEN];
-
-  /** True if this is a rendezvous point circuit; false if this is an
-   * introduction point. */
-  unsigned is_rend_circ;
-
-} or_circuit_rendinfo_t;
-
 /** Convert a circuit subtype to a circuit_t. */
 #define TO_CIRCUIT(x)  (&((x)->base_))
 
diff --git a/src/or/rendcommon.c b/src/or/rendcommon.c
index f2060e528c..def51b7986 100644
--- a/src/or/rendcommon.c
+++ b/src/or/rendcommon.c
@@ -16,6 +16,7 @@
 #include "rendclient.h"
 #include "rendcommon.h"
 #include "rendmid.h"
+#include "hs_intropoint.h"
 #include "rendservice.h"
 #include "rephist.h"
 #include "router.h"
@@ -762,7 +763,7 @@ rend_process_relay_cell(circuit_t *circ, const crypt_path_t *layer_hint,
   switch (command) {
     case RELAY_COMMAND_ESTABLISH_INTRO:
       if (or_circ)
-        r = rend_mid_establish_intro(or_circ,payload,length);
+        r = hs_intro_received_establish_intro(or_circ,payload,length);
       break;
     case RELAY_COMMAND_ESTABLISH_RENDEZVOUS:
       if (or_circ)
diff --git a/src/or/rendmid.c b/src/or/rendmid.c
index f39c92afae..3319a639b9 100644
--- a/src/or/rendmid.c
+++ b/src/or/rendmid.c
@@ -11,16 +11,19 @@
 #include "circuitlist.h"
 #include "circuituse.h"
 #include "config.h"
+#include "crypto.h"
 #include "relay.h"
 #include "rendmid.h"
 #include "rephist.h"
+#include "hs_circuitmap.h"
+#include "hs_intropoint.h"
 
 /** Respond to an ESTABLISH_INTRO cell by checking the signed data and
  * setting the circuit's purpose and service pk digest.
  */
 int
-rend_mid_establish_intro(or_circuit_t *circ, const uint8_t *request,
-                         size_t request_len)
+rend_mid_establish_intro_legacy(or_circuit_t *circ, const uint8_t *request,
+                                size_t request_len)
 {
   crypto_pk_t *pk = NULL;
   char buf[DIGEST_LEN+9];
@@ -32,15 +35,14 @@ rend_mid_establish_intro(or_circuit_t *circ, const uint8_t *request,
   int reason = END_CIRC_REASON_INTERNAL;
 
   log_info(LD_REND,
-           "Received an ESTABLISH_INTRO request on circuit %u",
+           "Received a legacy ESTABLISH_INTRO request on circuit %u",
            (unsigned) circ->p_circ_id);
 
-  if (circ->base_.purpose != CIRCUIT_PURPOSE_OR || circ->base_.n_chan) {
-    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
-         "Rejecting ESTABLISH_INTRO on non-OR or non-edge circuit.");
+  if (!hs_intro_circuit_is_suitable(circ)) {
     reason = END_CIRC_REASON_TORPROTOCOL;
     goto err;
   }
+
   if (request_len < 2+DIGEST_LEN)
     goto truncated;
   /* First 2 bytes: length of asn1-encoded key. */
@@ -94,7 +96,7 @@ rend_mid_establish_intro(or_circuit_t *circ, const uint8_t *request,
 
   /* Close any other intro circuits with the same pk. */
   c = NULL;
-  while ((c = circuit_get_intro_point((const uint8_t *)pk_digest))) {
+  while ((c = hs_circuitmap_get_intro_circ_v2((const uint8_t *)pk_digest))) {
     log_info(LD_REND, "Replacing old circuit for service %s",
              safe_str(serviceid));
     circuit_mark_for_close(TO_CIRCUIT(c), END_CIRC_REASON_FINISHED);
@@ -102,16 +104,14 @@ rend_mid_establish_intro(or_circuit_t *circ, const uint8_t *request,
   }
 
   /* Acknowledge the request. */
-  if (relay_send_command_from_edge(0, TO_CIRCUIT(circ),
-                                   RELAY_COMMAND_INTRO_ESTABLISHED,
-                                   "", 0, NULL)<0) {
+  if (hs_intro_send_intro_established_cell(circ) < 0) {
     log_info(LD_GENERAL, "Couldn't send INTRO_ESTABLISHED cell.");
     goto err_no_close;
   }
 
   /* Now, set up this circuit. */
   circuit_change_purpose(TO_CIRCUIT(circ), CIRCUIT_PURPOSE_INTRO_POINT);
-  circuit_set_intro_point_digest(circ, (uint8_t *)pk_digest);
+  hs_circuitmap_register_intro_circ_v2(circ, (uint8_t *)pk_digest);
 
   log_info(LD_REND,
            "Established introduction point on circuit %u for service %s",
@@ -181,7 +181,7 @@ rend_mid_introduce(or_circuit_t *circ, const uint8_t *request,
 
   /* The first 20 bytes are all we look at: they have a hash of the service's
    * PK. */
-  intro_circ = circuit_get_intro_point((const uint8_t*)request);
+  intro_circ = hs_circuitmap_get_intro_circ_v2((const uint8_t*)request);
   if (!intro_circ) {
     log_info(LD_REND,
              "No intro circ found for INTRODUCE1 cell (%s) from circuit %u; "
@@ -258,7 +258,7 @@ rend_mid_establish_rendezvous(or_circuit_t *circ, const uint8_t *request,
     goto err;
   }
 
-  if (circuit_get_rendezvous(request)) {
+  if (hs_circuitmap_get_rend_circ(request)) {
     log_warn(LD_PROTOCOL,
              "Duplicate rendezvous cookie in ESTABLISH_RENDEZVOUS.");
     goto err;
@@ -274,7 +274,7 @@ rend_mid_establish_rendezvous(or_circuit_t *circ, const uint8_t *request,
   }
 
   circuit_change_purpose(TO_CIRCUIT(circ), CIRCUIT_PURPOSE_REND_POINT_WAITING);
-  circuit_set_rendezvous_cookie(circ, request);
+  hs_circuitmap_register_rend_circ(circ, request);
 
   base16_encode(hexid,9,(char*)request,4);
 
@@ -323,7 +323,7 @@ rend_mid_rendezvous(or_circuit_t *circ, const uint8_t *request,
            "Got request for rendezvous from circuit %u to cookie %s.",
            (unsigned)circ->p_circ_id, hexid);
 
-  rend_circ = circuit_get_rendezvous(request);
+  rend_circ = hs_circuitmap_get_rend_circ(request);
   if (!rend_circ) {
     log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
          "Rejecting RENDEZVOUS1 cell with unrecognized rendezvous cookie %s.",
@@ -358,7 +358,7 @@ rend_mid_rendezvous(or_circuit_t *circ, const uint8_t *request,
   circuit_change_purpose(TO_CIRCUIT(circ), CIRCUIT_PURPOSE_REND_ESTABLISHED);
   circuit_change_purpose(TO_CIRCUIT(rend_circ),
                          CIRCUIT_PURPOSE_REND_ESTABLISHED);
-  circuit_set_rendezvous_cookie(circ, NULL);
+  hs_circuitmap_remove_circuit(circ);
 
   rend_circ->rend_splice = circ;
   circ->rend_splice = rend_circ;
diff --git a/src/or/rendmid.h b/src/or/rendmid.h
index 10d1287085..374f2b7d66 100644
--- a/src/or/rendmid.h
+++ b/src/or/rendmid.h
@@ -12,8 +12,8 @@
 #ifndef TOR_RENDMID_H
 #define TOR_RENDMID_H
 
-int rend_mid_establish_intro(or_circuit_t *circ, const uint8_t *request,
-                             size_t request_len);
+int rend_mid_establish_intro_legacy(or_circuit_t *circ, const uint8_t *request,
+                                    size_t request_len);
 int rend_mid_introduce(or_circuit_t *circ, const uint8_t *request,
                        size_t request_len);
 int rend_mid_establish_rendezvous(or_circuit_t *circ, const uint8_t *request,
diff --git a/src/or/rendservice.c b/src/or/rendservice.c
index 545fba1449..9a39090ac2 100644
--- a/src/or/rendservice.c
+++ b/src/or/rendservice.c
@@ -3160,6 +3160,57 @@ count_intro_point_circuits(const rend_service_t *service)
   return num_ipos;
 }
 
+/* Given a buffer of at least RELAY_PAYLOAD_SIZE bytes in <b>cell_body_out</b>,
+   write the body of a legacy ESTABLISH_INTRO cell in it. Use <b>intro_key</b>
+   as the intro point auth key, and <b>rend_circ_nonce</b> as the circuit
+   crypto material. On success, fill <b>cell_body_out</b> and return the number
+   of bytes written. On fail, return -1.
+ */
+STATIC ssize_t
+encode_establish_intro_cell_legacy(char *cell_body_out, crypto_pk_t *intro_key,
+                                   char *rend_circ_nonce)
+{
+  int retval = -1;
+  int r;
+  int len = 0;
+  char auth[DIGEST_LEN + 9];
+
+  tor_assert(intro_key);
+  tor_assert(rend_circ_nonce);
+
+  /* Build the payload for a RELAY_ESTABLISH_INTRO cell. */
+  r = crypto_pk_asn1_encode(intro_key, cell_body_out+2,
+                            RELAY_PAYLOAD_SIZE-2);
+  if (r < 0) {
+    log_warn(LD_BUG, "Internal error; failed to establish intro point.");
+    goto err;
+  }
+  len = r;
+  set_uint16(cell_body_out, htons((uint16_t)len));
+  len += 2;
+  memcpy(auth, rend_circ_nonce, DIGEST_LEN);
+  memcpy(auth+DIGEST_LEN, "INTRODUCE", 9);
+  if (crypto_digest(cell_body_out+len, auth, DIGEST_LEN+9))
+    goto err;
+  len += 20;
+  note_crypto_pk_op(REND_SERVER);
+  r = crypto_pk_private_sign_digest(intro_key, cell_body_out+len,
+                                    sizeof(cell_body_out)-len,
+                                    cell_body_out, len);
+  if (r<0) {
+    log_warn(LD_BUG, "Internal error: couldn't sign introduction request.");
+    goto err;
+  }
+  len += r;
+
+  retval = len;
+
+ err:
+  memwipe(auth, 0, sizeof(auth));
+
+  return retval;
+}
+
 /** Called when we're done building a circuit to an introduction point:
  *  sends a RELAY_ESTABLISH_INTRO cell.
  */
@@ -3167,10 +3218,7 @@ void
 rend_service_intro_has_opened(origin_circuit_t *circuit)
 {
   rend_service_t *service;
-  size_t len;
-  int r;
   char buf[RELAY_PAYLOAD_SIZE];
-  char auth[DIGEST_LEN + 9];
   char serviceid[REND_SERVICE_ID_LEN_BASE32+1];
   int reason = END_CIRC_REASON_TORPROTOCOL;
   const char *rend_pk_digest;
@@ -3245,41 +3293,24 @@ rend_service_intro_has_opened(origin_circuit_t *circuit)
            (unsigned)circuit->base_.n_circ_id, serviceid);
   circuit_log_path(LOG_INFO, LD_REND, circuit);
 
-  /* Use the intro key instead of the service key in ESTABLISH_INTRO. */
-  crypto_pk_t *intro_key = circuit->intro_key;
-  /* Build the payload for a RELAY_ESTABLISH_INTRO cell. */
-  r = crypto_pk_asn1_encode(intro_key, buf+2,
-                            RELAY_PAYLOAD_SIZE-2);
-  if (r < 0) {
-    log_warn(LD_BUG, "Internal error; failed to establish intro point.");
-    reason = END_CIRC_REASON_INTERNAL;
-    goto err;
-  }
-  len = r;
-  set_uint16(buf, htons((uint16_t)len));
-  len += 2;
-  memcpy(auth, circuit->cpath->prev->rend_circ_nonce, DIGEST_LEN);
-  memcpy(auth+DIGEST_LEN, "INTRODUCE", 9);
-  if (crypto_digest(buf+len, auth, DIGEST_LEN+9) < 0)
-    goto err;
-  len += 20;
-  note_crypto_pk_op(REND_SERVER);
-  r = crypto_pk_private_sign_digest(intro_key, buf+len, sizeof(buf)-len,
-                                    buf, len);
-  if (r<0) {
-    log_warn(LD_BUG, "Internal error: couldn't sign introduction request.");
-    reason = END_CIRC_REASON_INTERNAL;
-    goto err;
-  }
-  len += r;
+  /* Send the ESTABLISH_INTRO cell */
+  {
+    ssize_t len;
+    len = encode_establish_intro_cell_legacy(buf, circuit->intro_key,
+                                        circuit->cpath->prev->rend_circ_nonce);
+    if (len < 0) {
+      reason = END_CIRC_REASON_INTERNAL;
+      goto err;
+    }
 
-  if (relay_send_command_from_edge(0, TO_CIRCUIT(circuit),
-                                   RELAY_COMMAND_ESTABLISH_INTRO,
-                                   buf, len, circuit->cpath->prev)<0) {
-    log_info(LD_GENERAL,
+    if (relay_send_command_from_edge(0, TO_CIRCUIT(circuit),
+                                     RELAY_COMMAND_ESTABLISH_INTRO,
+                                     buf, len, circuit->cpath->prev)<0) {
+      log_info(LD_GENERAL,
              "Couldn't send introduction request for service %s on circuit %u",
              serviceid, (unsigned)circuit->base_.n_circ_id);
-    goto done;
+      goto done;
+    }
   }
 
   /* We've attempted to use this circuit */
@@ -3291,7 +3322,6 @@ rend_service_intro_has_opened(origin_circuit_t *circuit)
   circuit_mark_for_close(TO_CIRCUIT(circuit), reason);
  done:
   memwipe(buf, 0, sizeof(buf));
-  memwipe(auth, 0, sizeof(auth));
   memwipe(serviceid, 0, sizeof(serviceid));
 
   return;
@@ -4454,4 +4484,3 @@ rend_service_non_anonymous_mode_enabled(const or_options_t *options)
   tor_assert(rend_service_non_anonymous_mode_consistent(options));
   return options->HiddenServiceNonAnonymousMode ? 1 : 0;
 }
-
diff --git a/src/or/rendservice.h b/src/or/rendservice.h
index 3b185672f6..4e6b9a2536 100644
--- a/src/or/rendservice.h
+++ b/src/or/rendservice.h
@@ -129,6 +129,9 @@ STATIC int rend_service_verify_single_onion_poison(
 STATIC int rend_service_poison_new_single_onion_dir(
                                                   const rend_service_t *s,
                                                   const or_options_t* options);
+STATIC ssize_t encode_establish_intro_cell_legacy(char *cell_body_out,
+                                                  crypto_pk_t *intro_key,
+                                                  char *rend_circ_nonce);
 #endif
 
 int num_rend_services(void);
diff --git a/src/test/include.am b/src/test/include.am
index 8d0fc2ff6b..d406d6d324 100644
--- a/src/test/include.am
+++ b/src/test/include.am
@@ -97,6 +97,8 @@ src_test_test_SOURCES = \
 	src/test/test_guardfraction.c \
 	src/test/test_extorport.c \
 	src/test/test_hs.c \
+	src/test/test_hs_service.c \
+	src/test/test_hs_intropoint.c \
 	src/test/test_handles.c \
 	src/test/test_hs_cache.c \
 	src/test/test_hs_descriptor.c \
diff --git a/src/test/test.c b/src/test/test.c
index 750d8b00e4..866408e856 100644
--- a/src/test/test.c
+++ b/src/test/test.c
@@ -1205,9 +1205,11 @@ struct testgroup_t testgroups[] = {
   { "entrynodes/", entrynodes_tests },
   { "guardfraction/", guardfraction_tests },
   { "extorport/", extorport_tests },
-  { "hs/", hs_tests },
+  { "legacy_hs/", hs_tests },
   { "hs_cache/", hs_cache },
   { "hs_descriptor/", hs_descriptor },
+  { "hs_service/", hs_service_tests },
+  { "hs_intropoint/", hs_intropoint_tests },
   { "introduce/", introduce_tests },
   { "keypin/", keypin_tests },
   { "link-handshake/", link_handshake_tests },
diff --git a/src/test/test.h b/src/test/test.h
index 2fa73592ef..2bd58f51c8 100644
--- a/src/test/test.h
+++ b/src/test/test.h
@@ -202,6 +202,8 @@ extern struct testcase_t extorport_tests[];
 extern struct testcase_t hs_tests[];
 extern struct testcase_t hs_cache[];
 extern struct testcase_t hs_descriptor[];
+extern struct testcase_t hs_service_tests[];
+extern struct testcase_t hs_intropoint_tests[];
 extern struct testcase_t introduce_tests[];
 extern struct testcase_t keypin_tests[];
 extern struct testcase_t link_handshake_tests[];
diff --git a/src/test/test_circuitlist.c b/src/test/test_circuitlist.c
index e996c42115..7eed5fe225 100644
--- a/src/test/test_circuitlist.c
+++ b/src/test/test_circuitlist.c
@@ -4,10 +4,12 @@
 #define TOR_CHANNEL_INTERNAL_
 #define CIRCUITBUILD_PRIVATE
 #define CIRCUITLIST_PRIVATE
+#define HS_CIRCUITMAP_PRIVATE
 #include "or.h"
 #include "channel.h"
 #include "circuitbuild.h"
 #include "circuitlist.h"
+#include "hs_circuitmap.h"
 #include "test.h"
 #include "log_test_helpers.h"
 
@@ -185,6 +187,9 @@ test_rend_token_maps(void *arg)
 
   (void)arg;
   (void)tok1; //xxxx
+
+  hs_circuitmap_init();
+
   c1 = or_circuit_new(0, NULL);
   c2 = or_circuit_new(0, NULL);
   c3 = or_circuit_new(0, NULL);
@@ -196,68 +201,68 @@ test_rend_token_maps(void *arg)
   tt_int_op(tok3[REND_TOKEN_LEN-1], OP_EQ, '.');
 
   /* No maps; nothing there. */
-  tt_ptr_op(NULL, OP_EQ, circuit_get_rendezvous(tok1));
-  tt_ptr_op(NULL, OP_EQ, circuit_get_intro_point(tok1));
+  tt_ptr_op(NULL, OP_EQ, hs_circuitmap_get_rend_circ(tok1));
+  tt_ptr_op(NULL, OP_EQ, hs_circuitmap_get_intro_circ_v2(tok1));
 
-  circuit_set_rendezvous_cookie(c1, tok1);
-  circuit_set_intro_point_digest(c2, tok2);
+  hs_circuitmap_register_rend_circ(c1, tok1);
+  hs_circuitmap_register_intro_circ_v2(c2, tok2);
 
-  tt_ptr_op(NULL, OP_EQ, circuit_get_rendezvous(tok3));
-  tt_ptr_op(NULL, OP_EQ, circuit_get_intro_point(tok3));
-  tt_ptr_op(NULL, OP_EQ, circuit_get_rendezvous(tok2));
-  tt_ptr_op(NULL, OP_EQ, circuit_get_intro_point(tok1));
+  tt_ptr_op(NULL, OP_EQ, hs_circuitmap_get_rend_circ(tok3));
+  tt_ptr_op(NULL, OP_EQ, hs_circuitmap_get_intro_circ_v2(tok3));
+  tt_ptr_op(NULL, OP_EQ, hs_circuitmap_get_rend_circ(tok2));
+  tt_ptr_op(NULL, OP_EQ, hs_circuitmap_get_intro_circ_v2(tok1));
 
   /* Without purpose set, we don't get the circuits */
-  tt_ptr_op(NULL, OP_EQ, circuit_get_rendezvous(tok1));
-  tt_ptr_op(NULL, OP_EQ, circuit_get_intro_point(tok2));
+  tt_ptr_op(NULL, OP_EQ, hs_circuitmap_get_rend_circ(tok1));
+  tt_ptr_op(NULL, OP_EQ, hs_circuitmap_get_intro_circ_v2(tok2));
 
   c1->base_.purpose = CIRCUIT_PURPOSE_REND_POINT_WAITING;
   c2->base_.purpose = CIRCUIT_PURPOSE_INTRO_POINT;
 
   /* Okay, make sure they show up now. */
-  tt_ptr_op(c1, OP_EQ, circuit_get_rendezvous(tok1));
-  tt_ptr_op(c2, OP_EQ, circuit_get_intro_point(tok2));
+  tt_ptr_op(c1, OP_EQ, hs_circuitmap_get_rend_circ(tok1));
+  tt_ptr_op(c2, OP_EQ, hs_circuitmap_get_intro_circ_v2(tok2));
 
   /* Two items at the same place with the same token. */
   c3->base_.purpose = CIRCUIT_PURPOSE_REND_POINT_WAITING;
-  circuit_set_rendezvous_cookie(c3, tok2);
-  tt_ptr_op(c2, OP_EQ, circuit_get_intro_point(tok2));
-  tt_ptr_op(c3, OP_EQ, circuit_get_rendezvous(tok2));
+  hs_circuitmap_register_rend_circ(c3, tok2);
+  tt_ptr_op(c2, OP_EQ, hs_circuitmap_get_intro_circ_v2(tok2));
+  tt_ptr_op(c3, OP_EQ, hs_circuitmap_get_rend_circ(tok2));
 
   /* Marking a circuit makes it not get returned any more */
   circuit_mark_for_close(TO_CIRCUIT(c1), END_CIRC_REASON_FINISHED);
-  tt_ptr_op(NULL, OP_EQ, circuit_get_rendezvous(tok1));
+  tt_ptr_op(NULL, OP_EQ, hs_circuitmap_get_rend_circ(tok1));
   circuit_free(TO_CIRCUIT(c1));
   c1 = NULL;
 
   /* Freeing a circuit makes it not get returned any more. */
   circuit_free(TO_CIRCUIT(c2));
   c2 = NULL;
-  tt_ptr_op(NULL, OP_EQ, circuit_get_intro_point(tok2));
+  tt_ptr_op(NULL, OP_EQ, hs_circuitmap_get_intro_circ_v2(tok2));
 
   /* c3 -- are you still there? */
-  tt_ptr_op(c3, OP_EQ, circuit_get_rendezvous(tok2));
+  tt_ptr_op(c3, OP_EQ, hs_circuitmap_get_rend_circ(tok2));
   /* Change its cookie.  This never happens in Tor per se, but hey. */
   c3->base_.purpose = CIRCUIT_PURPOSE_INTRO_POINT;
-  circuit_set_intro_point_digest(c3, tok3);
+  hs_circuitmap_register_intro_circ_v2(c3, tok3);
 
-  tt_ptr_op(NULL, OP_EQ, circuit_get_rendezvous(tok2));
-  tt_ptr_op(c3, OP_EQ, circuit_get_intro_point(tok3));
+  tt_ptr_op(NULL, OP_EQ, hs_circuitmap_get_rend_circ(tok2));
+  tt_ptr_op(c3, OP_EQ, hs_circuitmap_get_intro_circ_v2(tok3));
 
   /* Now replace c3 with c4. */
   c4->base_.purpose = CIRCUIT_PURPOSE_INTRO_POINT;
-  circuit_set_intro_point_digest(c4, tok3);
+  hs_circuitmap_register_intro_circ_v2(c4, tok3);
 
-  tt_ptr_op(c4, OP_EQ, circuit_get_intro_point(tok3));
+  tt_ptr_op(c4, OP_EQ, hs_circuitmap_get_intro_circ_v2(tok3));
 
-  tt_ptr_op(c3->rendinfo, OP_EQ, NULL);
-  tt_ptr_op(c4->rendinfo, OP_NE, NULL);
-  tt_mem_op(c4->rendinfo, OP_EQ, tok3, REND_TOKEN_LEN);
+  tt_ptr_op(c3->hs_token, OP_EQ, NULL);
+  tt_ptr_op(c4->hs_token, OP_NE, NULL);
+  tt_mem_op(c4->hs_token->token, OP_EQ, tok3, REND_TOKEN_LEN);
 
   /* Now clear c4's cookie. */
-  circuit_set_intro_point_digest(c4, NULL);
-  tt_ptr_op(c4->rendinfo, OP_EQ, NULL);
-  tt_ptr_op(NULL, OP_EQ, circuit_get_intro_point(tok3));
+  hs_circuitmap_remove_circuit(c4);
+  tt_ptr_op(c4->hs_token, OP_EQ, NULL);
+  tt_ptr_op(NULL, OP_EQ, hs_circuitmap_get_intro_circ_v2(tok3));
 
  done:
   if (c1)
diff --git a/src/test/test_crypto.c b/src/test/test_crypto.c
index 64a46f7914..d66ddccd4f 100644
--- a/src/test/test_crypto.c
+++ b/src/test/test_crypto.c
@@ -1135,6 +1135,54 @@ test_crypto_sha3_xof(void *arg)
   tor_free(mem_op_hex_tmp);
 }
 
+/* Test our MAC-SHA3 function. There are not actually any MAC-SHA3 test
+ * vectors out there for our H(len(k) || k || m) construction. Hence what we
+ * are gonna do is test our crypto_mac_sha3_256() function against manually
+ * doing H(len(k) || k||m).  If in the future the Keccak group decides to
+ * standarize an MAC construction and make test vectors, we should
+ * incorporate them here. */
+static void
+test_crypto_mac_sha3(void *arg)
+{
+  const char msg[] = "i am in a library somewhere using my computer";
+  const char key[] = "i'm from the past talking to the future.";
+
+  uint8_t hmac_test[DIGEST256_LEN];
+  char hmac_manual[DIGEST256_LEN];
+
+  (void) arg;
+
+  /* First let's use our nice HMAC-SHA3 function */
+  crypto_mac_sha3_256(hmac_test, sizeof(hmac_test),
+                      (uint8_t *) key, strlen(key),
+                      (uint8_t *) msg, strlen(msg));
+
+  /* Now let's try a manual H(len(k) || k || m) construction */
+  {
+    char *key_msg_concat = NULL, *all = NULL;
+    int result;
+    const uint64_t key_len_netorder = tor_htonll(strlen(key));
+    size_t all_len;
+
+    tor_asprintf(&key_msg_concat, "%s%s", key, msg);
+    all_len = sizeof(key_len_netorder) + strlen(key_msg_concat);
+    all = tor_malloc_zero(all_len);
+    memcpy(all, &key_len_netorder, sizeof(key_len_netorder));
+    memcpy(all + sizeof(key_len_netorder), key_msg_concat,
+           strlen(key_msg_concat));
+
+    result = crypto_digest256(hmac_manual, all, all_len, DIGEST_SHA3_256);
+    tor_free(key_msg_concat);
+    tor_free(all);
+    tt_int_op(result, ==, 0);
+  }
+
+  /* Now compare the two results */
+  tt_mem_op(hmac_test, OP_EQ, hmac_manual, DIGEST256_LEN);
+
+ done: ;
+}
+
 /** Run unit tests for our public key crypto functions */
 static void
 test_crypto_pk(void *arg)
@@ -2918,6 +2966,7 @@ struct testcase_t crypto_tests[] = {
   { "digest_names", test_crypto_digest_names, 0, NULL, NULL },
   { "sha3", test_crypto_sha3, TT_FORK, NULL, NULL},
   { "sha3_xof", test_crypto_sha3_xof, TT_FORK, NULL, NULL},
+  { "mac_sha3", test_crypto_mac_sha3, TT_FORK, NULL, NULL},
   CRYPTO_LEGACY(dh),
   { "aes_iv_AES", test_crypto_aes_iv, TT_FORK, &passthrough_setup,
     (void*)"aes" },
diff --git a/src/test/test_hs_intropoint.c b/src/test/test_hs_intropoint.c
new file mode 100644
index 0000000000..608988ba9a
--- /dev/null
+++ b/src/test/test_hs_intropoint.c
@@ -0,0 +1,361 @@
+/* Copyright (c) 2016, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file test_hs_service.c
+ * \brief Test hidden service functionality.
+ */
+
+#define HS_SERVICE_PRIVATE
+#define HS_INTROPOINT_PRIVATE
+#define RENDSERVICE_PRIVATE
+#define CIRCUITLIST_PRIVATE
+
+#include "test.h"
+#include "crypto.h"
+
+#include "or.h"
+#include "ht.h"
+
+#include "hs/cell_establish_intro.h"
+#include "hs_service.h"
+#include "hs_circuitmap.h"
+#include "hs_intropoint.h"
+
+#include "circuitlist.h"
+#include "circuituse.h"
+#include "rendservice.h"
+
+/* Mock function to avoid networking in unittests */
+static int
+mock_send_intro_established_cell(or_circuit_t *circ)
+{
+  (void) circ;
+  return 0;
+}
+
+/* Try sending an ESTABLISH_INTRO cell on a circuit that is already an intro
+ * point. Should fail. */
+static void
+test_establish_intro_wrong_purpose(void *arg)
+{
+  int retval;
+  hs_cell_establish_intro_t *establish_intro_cell = NULL;
+  or_circuit_t *intro_circ = or_circuit_new(0,NULL);;
+  uint8_t cell_body[RELAY_PAYLOAD_SIZE];
+  ssize_t cell_len = 0;
+  uint8_t circuit_key_material[DIGEST_LEN] = {0};
+
+  (void)arg;
+
+  /* Get the auth key of the intro point */
+  crypto_rand((char *) circuit_key_material, sizeof(circuit_key_material));
+  memcpy(intro_circ->rend_circ_nonce, circuit_key_material, DIGEST_LEN);
+
+  /* Set a bad circuit purpose!! :) */
+  circuit_change_purpose(TO_CIRCUIT(intro_circ), CIRCUIT_PURPOSE_INTRO_POINT);
+
+  /* Create outgoing ESTABLISH_INTRO cell and extract its payload so that we
+     attempt to parse it. */
+  establish_intro_cell = generate_establish_intro_cell(circuit_key_material,
+                                           sizeof(circuit_key_material));
+  tt_assert(establish_intro_cell);
+  cell_len = get_establish_intro_payload(cell_body, sizeof(cell_body),
+                                         establish_intro_cell);
+  tt_int_op(cell_len, >, 0);
+
+  /* Receive the cell */
+  retval = hs_intro_received_establish_intro(intro_circ, cell_body, cell_len);
+  tt_int_op(retval, ==, -1);
+
+ done:
+  hs_cell_establish_intro_free(establish_intro_cell);
+  circuit_free(TO_CIRCUIT(intro_circ));
+}
+
+/* Prepare a circuit for accepting an ESTABLISH_INTRO cell */
+static void
+helper_prepare_circ_for_intro(or_circuit_t *circ,
+                              uint8_t *circuit_key_material)
+{
+  /* Prepare the circuit for the incoming ESTABLISH_INTRO */
+  circuit_change_purpose(TO_CIRCUIT(circ), CIRCUIT_PURPOSE_OR);
+  memcpy(circ->rend_circ_nonce, circuit_key_material, DIGEST_LEN);
+}
+
+/* Send an empty ESTABLISH_INTRO cell. Should fail. */
+static void
+test_establish_intro_wrong_keytype(void *arg)
+{
+  int retval;
+  or_circuit_t *intro_circ = or_circuit_new(0,NULL);;
+  uint8_t circuit_key_material[DIGEST_LEN] = {0};
+
+  (void)arg;
+
+  /* Get the auth key of the intro point */
+  crypto_rand((char *) circuit_key_material, sizeof(circuit_key_material));
+  helper_prepare_circ_for_intro(intro_circ, circuit_key_material);
+
+  /* Receive the cell. Should fail. */
+  retval = hs_intro_received_establish_intro(intro_circ, (uint8_t*)"", 0);
+  tt_int_op(retval, ==, -1);
+
+ done:
+  circuit_free(TO_CIRCUIT(intro_circ));
+}
+
+/* Send an ESTABLISH_INTRO cell with an unknown auth key type. Should fail. */
+static void
+test_establish_intro_wrong_keytype2(void *arg)
+{
+  int retval;
+  hs_cell_establish_intro_t *establish_intro_cell = NULL;
+  or_circuit_t *intro_circ = or_circuit_new(0,NULL);;
+  uint8_t cell_body[RELAY_PAYLOAD_SIZE];
+  ssize_t cell_len = 0;
+  uint8_t circuit_key_material[DIGEST_LEN] = {0};
+
+  (void)arg;
+
+  /* Get the auth key of the intro point */
+  crypto_rand((char *) circuit_key_material, sizeof(circuit_key_material));
+  helper_prepare_circ_for_intro(intro_circ, circuit_key_material);
+
+  /* Create outgoing ESTABLISH_INTRO cell and extract its payload so that we
+     attempt to parse it. */
+  establish_intro_cell = generate_establish_intro_cell(circuit_key_material,
+                                           sizeof(circuit_key_material));
+  tt_assert(establish_intro_cell);
+  cell_len = get_establish_intro_payload(cell_body, sizeof(cell_body),
+                                         establish_intro_cell);
+  tt_int_op(cell_len, >, 0);
+
+  /* Mutate the auth key type! :) */
+  cell_body[0] = 42;
+
+  /* Receive the cell. Should fail. */
+  retval = hs_intro_received_establish_intro(intro_circ, cell_body, cell_len);
+  tt_int_op(retval, ==, -1);
+
+ done:
+  hs_cell_establish_intro_free(establish_intro_cell);
+  circuit_free(TO_CIRCUIT(intro_circ));
+}
+
+/* Send a legit ESTABLISH_INTRO cell but slightly change the signature. Should
+ * fail. */
+static void
+test_establish_intro_wrong_sig(void *arg)
+{
+  int retval;
+  hs_cell_establish_intro_t *establish_intro_cell = NULL;
+  or_circuit_t *intro_circ = or_circuit_new(0,NULL);;
+  uint8_t cell_body[RELAY_PAYLOAD_SIZE];
+  ssize_t cell_len = 0;
+  uint8_t circuit_key_material[DIGEST_LEN] = {0};
+
+  (void)arg;
+
+  /* Get the auth key of the intro point */
+  crypto_rand((char *) circuit_key_material, sizeof(circuit_key_material));
+  helper_prepare_circ_for_intro(intro_circ, circuit_key_material);
+
+  /* Create outgoing ESTABLISH_INTRO cell and extract its payload so that we
+     attempt to parse it. */
+  establish_intro_cell = generate_establish_intro_cell(circuit_key_material,
+                                           sizeof(circuit_key_material));
+  tt_assert(establish_intro_cell);
+  cell_len = get_establish_intro_payload(cell_body, sizeof(cell_body),
+                                         establish_intro_cell);
+  tt_int_op(cell_len, >, 0);
+
+  /* Mutate the last byte (signature)! :) */
+  cell_body[cell_len-1]++;
+
+  /* Receive the cell. Should fail. */
+  retval = hs_intro_received_establish_intro(intro_circ, cell_body, cell_len);
+  tt_int_op(retval, ==, -1);
+
+ done:
+  hs_cell_establish_intro_free(establish_intro_cell);
+  circuit_free(TO_CIRCUIT(intro_circ));
+}
+
+/* Helper function: Send a well-formed v3 ESTABLISH_INTRO cell to
+ * <b>intro_circ</b>. Return the cell. */
+static hs_cell_establish_intro_t *
+helper_establish_intro_v3(or_circuit_t *intro_circ)
+{
+  int retval;
+  hs_cell_establish_intro_t *establish_intro_cell = NULL;
+  uint8_t cell_body[RELAY_PAYLOAD_SIZE];
+  ssize_t cell_len = 0;
+  uint8_t circuit_key_material[DIGEST_LEN] = {0};
+
+  tt_assert(intro_circ);
+
+  /* Prepare the circuit for the incoming ESTABLISH_INTRO */
+  crypto_rand((char *) circuit_key_material, sizeof(circuit_key_material));
+  helper_prepare_circ_for_intro(intro_circ, circuit_key_material);
+
+  /* Create outgoing ESTABLISH_INTRO cell and extract its payload so that we
+     attempt to parse it. */
+  establish_intro_cell = generate_establish_intro_cell(circuit_key_material,
+                                           sizeof(circuit_key_material));
+  tt_assert(establish_intro_cell);
+  cell_len = get_establish_intro_payload(cell_body, sizeof(cell_body),
+                                         establish_intro_cell);
+  tt_int_op(cell_len, >, 0);
+
+  /* Receive the cell */
+  retval = hs_intro_received_establish_intro(intro_circ, cell_body, cell_len);
+  tt_int_op(retval, ==, 0);
+
+ done:
+  return establish_intro_cell;
+}
+
+/* Helper function: Send a well-formed v2 ESTABLISH_INTRO cell to
+ * <b>intro_circ</b>. Return the public key advertised in the cell. */
+static crypto_pk_t *
+helper_establish_intro_v2(or_circuit_t *intro_circ)
+{
+  crypto_pk_t *key1 = NULL;
+  int retval;
+  uint8_t cell_body[RELAY_PAYLOAD_SIZE];
+  ssize_t cell_len = 0;
+  uint8_t circuit_key_material[DIGEST_LEN] = {0};
+
+  tt_assert(intro_circ);
+
+  /* Prepare the circuit for the incoming ESTABLISH_INTRO */
+  crypto_rand((char *) circuit_key_material, sizeof(circuit_key_material));
+  helper_prepare_circ_for_intro(intro_circ, circuit_key_material);
+
+  /* Send legacy establish_intro */
+  key1 = pk_generate(0);
+
+  /* Use old circuit_key_material why not */
+  cell_len = encode_establish_intro_cell_legacy((char*)cell_body,
+                                                key1,
+                                                (char *) circuit_key_material);
+  tt_int_op(cell_len, >, 0);
+
+  /* Receive legacy establish_intro */
+  retval = hs_intro_received_establish_intro(intro_circ,
+                                       cell_body, cell_len);
+  tt_int_op(retval, ==, 0);
+
+ done:
+  return key1;
+}
+
+/** Successfuly register a v2 intro point and a v3 intro point. Ensure that HS
+ *  circuitmap is maintained properly. */
+static void
+test_intro_point_registration(void *arg)
+{
+  int retval;
+  hs_circuitmap_ht *the_hs_circuitmap = NULL;
+
+  or_circuit_t *intro_circ = NULL;
+  hs_cell_establish_intro_t *establish_intro_cell = NULL;
+  ed25519_public_key_t auth_key;
+
+  crypto_pk_t *legacy_auth_key = NULL;
+  or_circuit_t *legacy_intro_circ = NULL;
+
+  or_circuit_t *returned_intro_circ = NULL;
+
+  (void) arg;
+
+  MOCK(hs_intro_send_intro_established_cell, mock_send_intro_established_cell);
+
+  hs_circuitmap_init();
+
+  /* Check that the circuitmap is currently empty */
+  {
+    the_hs_circuitmap = get_hs_circuitmap();
+    tt_assert(the_hs_circuitmap);
+    tt_int_op(0, ==, HT_SIZE(the_hs_circuitmap));
+    /* Do a circuitmap query in any case */
+    returned_intro_circ = hs_circuitmap_get_intro_circ_v3(&auth_key);
+    tt_ptr_op(returned_intro_circ, ==, NULL);
+  }
+
+  /* Create a v3 intro point */
+  {
+    intro_circ = or_circuit_new(0, NULL);
+    tt_assert(intro_circ);
+    establish_intro_cell = helper_establish_intro_v3(intro_circ);
+
+    /* Check that the intro point was registered on the HS circuitmap */
+    the_hs_circuitmap = get_hs_circuitmap();
+    tt_assert(the_hs_circuitmap);
+    tt_int_op(1, ==, HT_SIZE(the_hs_circuitmap));
+    get_auth_key_from_establish_intro_cell(&auth_key, establish_intro_cell);
+    returned_intro_circ = hs_circuitmap_get_intro_circ_v3(&auth_key);
+    tt_ptr_op(intro_circ, ==, returned_intro_circ);
+  }
+
+  /* Create a v2 intro point */
+  {
+    char key_digest[DIGEST_LEN];
+
+    legacy_intro_circ = or_circuit_new(1, NULL);
+    tt_assert(legacy_intro_circ);
+    legacy_auth_key = helper_establish_intro_v2(legacy_intro_circ);
+    tt_assert(legacy_auth_key);
+
+    /* Check that the circuitmap now has two elements */
+    the_hs_circuitmap = get_hs_circuitmap();
+    tt_assert(the_hs_circuitmap);
+    tt_int_op(2, ==, HT_SIZE(the_hs_circuitmap));
+
+    /* Check that the new element is our legacy intro circuit. */
+    retval = crypto_pk_get_digest(legacy_auth_key, key_digest);
+    tt_int_op(retval, ==, 0);
+    returned_intro_circ= hs_circuitmap_get_intro_circ_v2((uint8_t*)key_digest);
+    tt_ptr_op(legacy_intro_circ, ==, returned_intro_circ);
+  }
+
+  /* XXX Continue test and try to register a second v3 intro point with the
+   * same auth key. Make sure that old intro circuit gets closed. */
+
+ done:
+  crypto_pk_free(legacy_auth_key);
+  circuit_free(TO_CIRCUIT(intro_circ));
+  circuit_free(TO_CIRCUIT(legacy_intro_circ));
+  hs_cell_establish_intro_free(establish_intro_cell);
+
+  { /* Test circuitmap free_all function. */
+    the_hs_circuitmap = get_hs_circuitmap();
+    tt_assert(the_hs_circuitmap);
+    hs_circuitmap_free_all();
+    the_hs_circuitmap = get_hs_circuitmap();
+    tt_assert(!the_hs_circuitmap);
+  }
+
+  UNMOCK(hs_intro_send_intro_established_cell);
+}
+
+struct testcase_t hs_intropoint_tests[] = {
+  { "intro_point_registration",
+    test_intro_point_registration, TT_FORK, NULL, NULL },
+
+  { "receive_establish_intro_wrong_keytype",
+    test_establish_intro_wrong_keytype, TT_FORK, NULL, NULL },
+
+  { "receive_establish_intro_wrong_keytype2",
+    test_establish_intro_wrong_keytype2, TT_FORK, NULL, NULL },
+
+  { "receive_establish_intro_wrong_purpose",
+    test_establish_intro_wrong_purpose, TT_FORK, NULL, NULL },
+
+  { "receive_establish_intro_wrong_sig",
+    test_establish_intro_wrong_sig, TT_FORK, NULL, NULL },
+
+  END_OF_TESTCASES
+};
+
diff --git a/src/test/test_hs_service.c b/src/test/test_hs_service.c
new file mode 100644
index 0000000000..195e5069cb
--- /dev/null
+++ b/src/test/test_hs_service.c
@@ -0,0 +1,112 @@
+/* Copyright (c) 2016, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file test_hs_service.c
+ * \brief Test hidden service functionality.
+ */
+
+#define HS_SERVICE_PRIVATE
+#define HS_INTROPOINT_PRIVATE
+
+#include "test.h"
+#include "log_test_helpers.h"
+#include "crypto.h"
+
+#include "hs/cell_establish_intro.h"
+#include "hs_service.h"
+#include "hs_intropoint.h"
+
+/** We simulate the creation of an outgoing ESTABLISH_INTRO cell, and then we
+ *  parse it from the receiver side. */
+static void
+test_gen_establish_intro_cell(void *arg)
+{
+  (void) arg;
+  int retval;
+  uint8_t circuit_key_material[DIGEST_LEN] = {0};
+  uint8_t buf[RELAY_PAYLOAD_SIZE];
+  hs_cell_establish_intro_t *cell_out = NULL;
+  hs_cell_establish_intro_t *cell_in = NULL;
+
+  crypto_rand((char *) circuit_key_material, sizeof(circuit_key_material));
+
+  /* Create outgoing ESTABLISH_INTRO cell and extract its payload so that we
+     attempt to parse it. */
+  {
+    cell_out = generate_establish_intro_cell(circuit_key_material,
+                                             sizeof(circuit_key_material));
+    tt_assert(cell_out);
+
+    retval = get_establish_intro_payload(buf, sizeof(buf), cell_out);
+    tt_int_op(retval, >=, 0);
+  }
+
+  /* Parse it as the receiver */
+  {
+    ssize_t parse_result = hs_cell_establish_intro_parse(&cell_in,
+                                                         buf, sizeof(buf));
+    tt_int_op(parse_result, >=, 0);
+
+    retval = verify_establish_intro_cell(cell_in,
+                                         circuit_key_material,
+                                         sizeof(circuit_key_material));
+    tt_int_op(retval, >=, 0);
+  }
+
+ done:
+  hs_cell_establish_intro_free(cell_out);
+  hs_cell_establish_intro_free(cell_in);
+}
+
+/* Mocked ed25519_sign_prefixed() function that always fails :) */
+static int
+mock_ed25519_sign_prefixed(ed25519_signature_t *signature_out,
+                           const uint8_t *msg, size_t msg_len,
+                           const char *prefix_str,
+                           const ed25519_keypair_t *keypair) {
+  (void) signature_out;
+  (void) msg;
+  (void) msg_len;
+  (void) prefix_str;
+  (void) keypair;
+  return -1;
+}
+
+/** We simulate a failure to create an ESTABLISH_INTRO cell */
+static void
+test_gen_establish_intro_cell_bad(void *arg)
+{
+  (void) arg;
+  hs_cell_establish_intro_t *cell = NULL;
+  uint8_t circuit_key_material[DIGEST_LEN] = {0};
+
+  MOCK(ed25519_sign_prefixed, mock_ed25519_sign_prefixed);
+
+  crypto_rand((char *) circuit_key_material, sizeof(circuit_key_material));
+
+  setup_full_capture_of_logs(LOG_WARN);
+  /* Easiest way to make that function fail is to mock the
+     ed25519_sign_prefixed() function and make it fail. */
+  cell = generate_establish_intro_cell(circuit_key_material,
+                                       sizeof(circuit_key_material));
+  expect_log_msg_containing("Unable to gen signature for "
+                            "ESTABLISH_INTRO cell.");
+  teardown_capture_of_logs();
+  tt_assert(!cell);
+
+ done:
+  hs_cell_establish_intro_free(cell);
+  UNMOCK(ed25519_sign_prefixed);
+}
+
+struct testcase_t hs_service_tests[] = {
+  { "gen_establish_intro_cell", test_gen_establish_intro_cell, TT_FORK,
+    NULL, NULL },
+  { "gen_establish_intro_cell_bad", test_gen_establish_intro_cell_bad, TT_FORK,
+    NULL, NULL },
+
+
+  END_OF_TESTCASES
+};
+