Merge branch 'dgoulet_ticket19043_030_03_squashed'

17 files changed, 1048 insertions, 251 deletions

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);