Merge remote-tracking branch 'mikeperry/bug23101-mergeready-squashed'

11 files changed, 696 insertions, 50 deletions

diff --git a/changes/bug13837 b/changes/bug13837
new file mode 100644
index 0000000000..5791dcee58
--- /dev/null
+++ b/changes/bug13837
@@ -0,0 +1,4 @@
+  o Major features (Onion Services):
+    - Provide torrc options to pin the second and third hops of onion service
+      circuits to a list of nodes. The option HSLayer2Guards pins the second hop,
+      and the option HSLayer3Guards pins the third hop. Closes ticket 13837.
diff --git a/changes/bug23101 b/changes/bug23101
new file mode 100644
index 0000000000..7f366793f6
--- /dev/null
+++ b/changes/bug23101
@@ -0,0 +1,3 @@
+  o Minor features (Performance):
+    - Support predictive circuit building for onion service circuits with
+      multiple layers of guards. Closes ticket 23101.
diff --git a/doc/tor.1.txt b/doc/tor.1.txt
index 115f09bc31..8e27a25de4 100644
--- a/doc/tor.1.txt
+++ b/doc/tor.1.txt
@@ -1531,6 +1531,100 @@ The following options are useful only for clients (that is, if
     If no nodes in Tor2webRendezvousPoints are currently available for
     use, Tor will choose a random node when building HS circuits.
 
+[[_HSLayer2Nodes]] **_HSLayer2Nodes** __node__,__node__,__...__::
+    A list of identity fingerprints, nicknames, country codes, and
+    address patterns of nodes that are allowed to be used as the
+    second hop in all client or service-side Onion Service circuits.
+    This option mitigates attacks where the adversary runs middle nodes
+    and induces your client or service to create many circuits, in order
+    to discover your primary guard node.
+    (Default: Any node in the network may be used in the second hop.)
+ +
+    (Example:
+    _HSLayer2Nodes ABCD1234CDEF5678ABCD1234CDEF5678ABCD1234, \{cc}, 255.254.0.0/8) +
+ +
+    When this is set, the resulting hidden service paths will
+    look like:
+ +
+        C - G - L2 - M - Rend +
+        C - G - L2 - M - HSDir +
+        C - G - L2 - M - Intro +
+        S - G - L2 - M - Rend +
+        S - G - L2 - M - HSDir +
+        S - G - L2 - M - Intro +
+ +
+    where C is this client, S is the service, G is the Guard node,
+    L2 is a node from this option, and M is a random middle node.
+    Rend, HSDir, and Intro point selection is not affected by this
+    option.
+ +
+    This option may be combined with _HSLayer3Nodes to create
+    paths of the form:
+ +
+        C - G - L2 - L3 - Rend +
+        C - G - L2 - L3 - M - HSDir +
+        C - G - L2 - L3 - M - Intro +
+        S - G - L2 - L3 - M - Rend +
+        S - G - L2 - L3 - HSDir +
+        S - G - L2 - L3 - Intro +
+ +
+    ExcludeNodes have higher priority than _HSLayer2Nodes,
+    which means that nodes specified in ExcludeNodes will not be
+    picked.
+ +
+    This option is meant to be managed by a Tor controller such as
+    https://github.com/mikeperry-tor/vanguards that selects and
+    updates this set of nodes for you. Hence it does not do load
+    balancing if fewer than 20 nodes are selected, and if no nodes in
+    _HSLayer2Nodes are currently available for use, Tor will not work.
+    Please use extreme care if you are setting this option manually.
+
+[[_HSLayer3Nodes]] **_HSLayer3Nodes** __node__,__node__,__...__::
+    A list of identity fingerprints, nicknames, country codes, and
+    address patterns of nodes that are allowed to be used as the
+    third hop in all client and service-side Onion Service circuits.
+    This option mitigates attacks where the adversary runs middle nodes
+    and induces your client or service to create many circuits, in order
+    to discover your primary or Layer2 guard nodes.
+    (Default: Any node in the network may be used in the third hop.)
+ +
+    (Example:
+    _HSLayer3Nodes ABCD1234CDEF5678ABCD1234CDEF5678ABCD1234, \{cc}, 255.254.0.0/8) +
+ +
+    When this is set by itself, the resulting hidden service paths
+    will look like: +
+        C - G - M - L3 - Rend +
+        C - G - M - L3 - M - HSDir +
+        C - G - M - L3 - M - Intro +
+        S - G - M - L3 - M - Rend +
+        S - G - M - L3 - HSDir +
+        S - G - M - L3 - Intro +
+    where C is this client, S is the service, G is the Guard node,
+    L2 is a node from this option, and M is a random middle node.
+    Rend, HSDir, and Intro point selection is not affected by this
+    option.
+ +
+    While it is possible to use this option by itself, it should be
+    combined with _HSLayer2Nodes to create paths of the form:
+ +
+        C - G - L2 - L3 - Rend +
+        C - G - L2 - L3 - M - HSDir +
+        C - G - L2 - L3 - M - Intro +
+        S - G - L2 - L3 - M - Rend +
+        S - G - L2 - L3 - HSDir +
+        S - G - L2 - L3 - Intro +
+ +
+    ExcludeNodes have higher priority than _HSLayer3Nodes,
+    which means that nodes specified in ExcludeNodes will not be
+    picked.
+  +
+    This option is meant to be managed by a Tor controller such as
+    https://github.com/mikeperry-tor/vanguards that selects and
+    updates this set of nodes for you. Hence it does not do load
+    balancing if fewer than 20 nodes are selected, and if no nodes in
+    _HSLayer3Nodes are currently available for use, Tor will not work.
+    Please use extreme care if you are setting this option manually.
+
 [[UseMicrodescriptors]] **UseMicrodescriptors** **0**|**1**|**auto**::
     Microdescriptors are a smaller version of the information that Tor needs
     in order to build its circuits.  Using microdescriptors makes Tor clients
diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index a350f6c142..ddcb72bf47 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -80,6 +80,10 @@ static int circuit_send_first_onion_skin(origin_circuit_t *circ);
 static int circuit_build_no_more_hops(origin_circuit_t *circ);
 static int circuit_send_intermediate_onion_skin(origin_circuit_t *circ,
                                                 crypt_path_t *hop);
+static const node_t *choose_good_middle_server(uint8_t purpose,
+                          cpath_build_state_t *state,
+                          crypt_path_t *head,
+                          int cur_len);
 
 /** This function tries to get a channel to the specified endpoint,
  * and then calls command_setup_channel() to give it the right
@@ -1653,12 +1657,49 @@ onionskin_answer(or_circuit_t *circ,
  * new_route_len()) in the one-hop tunnel case, so we don't need to
  * handle that.
  */
-static int
+int
 route_len_for_purpose(uint8_t purpose, extend_info_t *exit_ei)
 {
   int routelen = DEFAULT_ROUTE_LEN;
   int known_purpose = 0;
 
+  if (circuit_should_use_vanguards(purpose)) {
+    /* Clients want an extra hop for rends to avoid linkability.
+     * Services want it for intro points to avoid publishing their
+     * layer3 guards. They want it for hsdir posts to use
+     * their full layer3 guard set for those connections.
+     * Ex: C - G - L2 - L3 - R
+     *     S - G - L2 - L3 - HSDIR
+     *     S - G - L2 - L3 - I
+     */
+    if (purpose == CIRCUIT_PURPOSE_C_ESTABLISH_REND ||
+        purpose == CIRCUIT_PURPOSE_S_HSDIR_POST ||
+        purpose == CIRCUIT_PURPOSE_HS_VANGUARDS ||
+        purpose == CIRCUIT_PURPOSE_S_ESTABLISH_INTRO)
+      return routelen+1;
+
+    /* If we only have Layer2 vanguards, then we do not need
+     * the extra hop for linkabilty reasons (see below).
+     * This means all hops can be of the form:
+     *   S/C - G - L2 - M - R/HSDir/I
+     */
+    if (get_options()->HSLayer2Nodes && !get_options()->HSLayer3Nodes)
+      return routelen+1;
+
+    /* For connections to hsdirs, clients want two extra hops
+     * when using layer3 guards, to avoid linkability.
+     * Same goes for intro points. Note that the route len
+     * includes the intro point or hsdir, hence the +2.
+     * Ex: C - G - L2 - L3 - M - I
+     *     C - G - L2 - L3 - M - HSDIR
+     *     S - G - L2 - L3 - M - R
+     */
+    if (purpose == CIRCUIT_PURPOSE_S_CONNECT_REND ||
+        purpose == CIRCUIT_PURPOSE_C_HSDIR_GET ||
+        purpose == CIRCUIT_PURPOSE_C_INTRODUCING)
+      return routelen+2;
+  }
+
   if (!exit_ei)
     return routelen;
 
@@ -1675,6 +1716,8 @@ route_len_for_purpose(uint8_t purpose, extend_info_t *exit_ei)
     /* These three purposes connect to a router that someone else
      * might have chosen, so add an extra hop to protect anonymity. */
   case CIRCUIT_PURPOSE_C_GENERAL:
+  case CIRCUIT_PURPOSE_C_HSDIR_GET:
+  case CIRCUIT_PURPOSE_S_HSDIR_POST:
     /* connecting to hidden service directory */
   case CIRCUIT_PURPOSE_C_INTRODUCING:
     /* client connecting to introduction point */
@@ -2123,6 +2166,98 @@ pick_rendezvous_node(router_crn_flags_t flags)
   return router_choose_random_node(NULL, options->ExcludeNodes, flags);
 }
 
+/*
+ * Helper function to pick a configured restricted middle node
+ * (either HSLayer2Nodes or HSLayer3Nodes).
+ *
+ * Make sure that the node we chose is alive, and not excluded,
+ * and return it.
+ *
+ * The exclude_set is a routerset of nodes that the selected node
+ * must not match, and the exclude_list is a simple list of nodes
+ * that the selected node must not be in. Either or both may be
+ * NULL.
+ *
+ * Return NULL if no usable nodes could be found. */
+static const node_t *
+pick_restricted_middle_node(router_crn_flags_t flags,
+                            const routerset_t *pick_from,
+                            const routerset_t *exclude_set,
+                            const smartlist_t *exclude_list,
+                            int position_hint)
+{
+  const node_t *middle_node = NULL;
+
+  smartlist_t *whitelisted_live_middles = smartlist_new();
+  smartlist_t *all_live_nodes = smartlist_new();
+
+  tor_assert(pick_from);
+
+  /* Add all running nodes to all_live_nodes */
+  router_add_running_nodes_to_smartlist(all_live_nodes,
+                                        (flags & CRN_NEED_UPTIME) != 0,
+                                        (flags & CRN_NEED_CAPACITY) != 0,
+                                        (flags & CRN_NEED_GUARD) != 0,
+                                        (flags & CRN_NEED_DESC) != 0,
+                                        (flags & CRN_PREF_ADDR) != 0,
+                                        (flags & CRN_DIRECT_CONN) != 0);
+
+  /* Filter all_live_nodes to only add live *and* whitelisted middles
+   * to the list whitelisted_live_middles. */
+  SMARTLIST_FOREACH_BEGIN(all_live_nodes, node_t *, live_node) {
+    if (routerset_contains_node(pick_from, live_node)) {
+      smartlist_add(whitelisted_live_middles, live_node);
+    }
+  } SMARTLIST_FOREACH_END(live_node);
+
+  /* Honor ExcludeNodes */
+  if (exclude_set) {
+    routerset_subtract_nodes(whitelisted_live_middles, exclude_set);
+  }
+
+  if (exclude_list) {
+    smartlist_subtract(whitelisted_live_middles, exclude_list);
+  }
+
+  /**
+   * Max number of restricted nodes before we alert the user and try
+   * to load balance for them.
+   *
+   * The most agressive vanguard design had 16 nodes at layer3.
+   * Let's give a small ceiling above that. */
+#define MAX_SANE_RESTRICTED_NODES 20
+  /* If the user (or associated tor controller) selected only a few nodes,
+   * assume they took load balancing into account and don't do it for them.
+   *
+   * If there are a lot of nodes in here, assume they did not load balance
+   * and do it for them, but also warn them that they may be Doing It Wrong.
+   */
+  if (smartlist_len(whitelisted_live_middles) <=
+          MAX_SANE_RESTRICTED_NODES) {
+    middle_node = smartlist_choose(whitelisted_live_middles);
+  } else {
+    static ratelim_t pinned_notice_limit = RATELIM_INIT(24*3600);
+    log_fn_ratelim(&pinned_notice_limit, LOG_NOTICE, LD_CIRC,
+            "Your _HSLayer%dNodes setting has resulted "
+            "in %d total nodes. This is a lot of nodes. "
+            "You may want to consider using a Tor controller "
+            "to select and update a smaller set of nodes instead.",
+            position_hint, smartlist_len(whitelisted_live_middles));
+
+    /* NO_WEIGHTING here just means don't take node flags into account
+     * (ie: use consensus measurement only). This is done so that
+     * we don't further surprise the user by not using Exits that they
+     * specified at all */
+    middle_node = node_sl_choose_by_bandwidth(whitelisted_live_middles,
+                                              NO_WEIGHTING);
+  }
+
+  smartlist_free(whitelisted_live_middles);
+  smartlist_free(all_live_nodes);
+
+  return middle_node;
+}
+
 /** Return a pointer to a suitable router to be the exit node for the
  * circuit of purpose <b>purpose</b> that we're about to build (or NULL
  * if no router is suitable).
@@ -2134,9 +2269,8 @@ pick_rendezvous_node(router_crn_flags_t flags)
  * toward the preferences in 'options'.
  */
 static const node_t *
-choose_good_exit_server(uint8_t purpose,
-                        int need_uptime, int need_capacity, int is_internal,
-                        int need_hs_v3)
+choose_good_exit_server(origin_circuit_t *circ, int need_uptime,
+                        int need_capacity, int is_internal, int need_hs_v3)
 {
   const or_options_t *options = get_options();
   router_crn_flags_t flags = CRN_NEED_DESC;
@@ -2147,7 +2281,13 @@ choose_good_exit_server(uint8_t purpose,
   if (need_hs_v3)
     flags |= CRN_RENDEZVOUS_V3;
 
-  switch (purpose) {
+  switch (TO_CIRCUIT(circ)->purpose) {
+    case CIRCUIT_PURPOSE_C_HSDIR_GET:
+    case CIRCUIT_PURPOSE_S_HSDIR_POST:
+    case CIRCUIT_PURPOSE_HS_VANGUARDS:
+      /* For these three, we want to pick the exit like a middle hop,
+       * since it should be random. */
+      tor_assert_nonfatal(is_internal);
     case CIRCUIT_PURPOSE_C_GENERAL:
       if (is_internal) /* pick it like a middle hop */
         return router_choose_random_node(NULL, options->ExcludeNodes, flags);
@@ -2162,7 +2302,7 @@ choose_good_exit_server(uint8_t purpose,
         return rendezvous_node;
       }
   }
-  log_warn(LD_BUG,"Unhandled purpose %d", purpose);
+  log_warn(LD_BUG,"Unhandled purpose %d", TO_CIRCUIT(circ)->purpose);
   tor_fragile_assert();
   return NULL;
 }
@@ -2192,6 +2332,8 @@ warn_if_last_router_excluded(origin_circuit_t *circ,
                (int)purpose,
                circuit_purpose_to_string(purpose));
       return;
+    case CIRCUIT_PURPOSE_S_HSDIR_POST:
+    case CIRCUIT_PURPOSE_C_HSDIR_GET:
     case CIRCUIT_PURPOSE_C_GENERAL:
       if (circ->build_state->is_internal)
         return;
@@ -2276,7 +2418,7 @@ onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit_ei,
     exit_ei = extend_info_dup(exit_ei);
   } else { /* we have to decide one */
     const node_t *node =
-      choose_good_exit_server(circ->base_.purpose, state->need_uptime,
+      choose_good_exit_server(circ, state->need_uptime,
                               state->need_capacity, state->is_internal,
                               is_hs_v3_rp_circuit);
     if (!node) {
@@ -2410,6 +2552,118 @@ cpath_get_n_hops(crypt_path_t **head_ptr)
 
 #endif /* defined(TOR_UNIT_TESTS) */
 
+/**
+ * Build a list of nodes to exclude from the choice of this middle
+ * hop, based on already chosen nodes.
+ *
+ * XXX: At present, this function does not exclude any nodes from
+ * the vanguard circuits. See
+ * https://trac.torproject.org/projects/tor/ticket/24487
+ */
+static smartlist_t *
+build_middle_exclude_list(uint8_t purpose,
+                          cpath_build_state_t *state,
+                          crypt_path_t *head,
+                          int cur_len)
+{
+  smartlist_t *excluded;
+  const node_t *r;
+  crypt_path_t *cpath;
+  int i;
+
+  excluded = smartlist_new();
+
+  /* Add the exit to the exclude list (note that the exit/last hop is always
+   * chosen first in circuit_establish_circuit()). */
+  if ((r = build_state_get_exit_node(state))) {
+    nodelist_add_node_and_family(excluded, r);
+  }
+
+  /* XXX: We don't apply any other previously selected node restrictions for
+   * vanguards, and allow nodes to be reused for those hop positions in the
+   * same circuit. This is because after many rotations, you get to learn
+   * inner guard nodes through the nodes that are not selected for outer
+   * hops.
+   *
+   * The alternative is building the circuit in reverse. Reverse calls to
+   * onion_extend_cpath() (ie: select outer hops first) would then have the
+   * property that you don't gain information about inner hops by observing
+   * outer ones. See https://trac.torproject.org/projects/tor/ticket/24487
+   * for this.
+   *
+   * (Note further that we can and do still exclude the exit in the block
+   * above, because it is chosen first in circuit_establish_circuit()..) */
+  if (circuit_should_use_vanguards(purpose)) {
+    return excluded;
+  }
+
+  for (i = 0, cpath = head; cpath && i < cur_len; ++i, cpath=cpath->next) {
+    if ((r = node_get_by_id(cpath->extend_info->identity_digest))) {
+      nodelist_add_node_and_family(excluded, r);
+    }
+  }
+
+  return excluded;
+}
+
+/** Return true if we MUST use vanguards for picking this middle node. */
+static int
+middle_node_must_be_vanguard(const or_options_t *options,
+                             uint8_t purpose, int cur_len)
+{
+  /* If this is not a hidden service circuit, don't use vanguards */
+  if (!circuit_purpose_is_hidden_service(purpose)) {
+    return 0;
+  }
+
+  /* If we have sticky L2 nodes, and this is an L2 pick, use vanguards */
+  if (options->HSLayer2Nodes && cur_len == 1) {
+    return 1;
+  }
+
+  /* If we have sticky L3 nodes, and this is an L3 pick, use vanguards */
+  if (options->HSLayer3Nodes && cur_len == 2) {
+    return 1;
+  }
+
+  return 0;
+}
+
+/** Pick a sticky vanguard middle node or return NULL if not found.
+ *  See doc of pick_restricted_middle_node() for argument details. */
+static const node_t *
+pick_vanguard_middle_node(const or_options_t *options,
+                          router_crn_flags_t flags, int cur_len,
+                          const smartlist_t *excluded)
+{
+  const routerset_t *vanguard_routerset = NULL;
+  const node_t *node = NULL;
+
+  /* Pick the right routerset based on the current hop */
+  if (cur_len == 1) {
+    vanguard_routerset = options->HSLayer2Nodes;
+  } else if (cur_len == 2) {
+    vanguard_routerset = options->HSLayer3Nodes;
+  } else {
+    /* guaranteed by middle_node_should_be_vanguard() */
+    tor_assert_nonfatal_unreached();
+    return NULL;
+  }
+
+  node = pick_restricted_middle_node(flags, vanguard_routerset,
+                                     options->ExcludeNodes, excluded,
+                                     cur_len+1);
+
+  if (!node) {
+    static ratelim_t pinned_warning_limit = RATELIM_INIT(300);
+    log_fn_ratelim(&pinned_warning_limit, LOG_WARN, LD_CIRC,
+            "Could not find a node that matches the configured "
+            "_HSLayer%dNodes set", cur_len+1);
+  }
+
+  return node;
+}
+
 /** A helper function used by onion_extend_cpath(). Use <b>purpose</b>
  * and <b>state</b> and the cpath <b>head</b> (currently populated only
  * to length <b>cur_len</b> to decide a suitable middle hop for a
@@ -2422,9 +2676,7 @@ choose_good_middle_server(uint8_t purpose,
                           crypt_path_t *head,
                           int cur_len)
 {
-  int i;
-  const node_t *r, *choice;
-  crypt_path_t *cpath;
+  const node_t *choice;
   smartlist_t *excluded;
   const or_options_t *options = get_options();
   router_crn_flags_t flags = CRN_NEED_DESC;
@@ -2433,20 +2685,20 @@ choose_good_middle_server(uint8_t purpose,
 
   log_debug(LD_CIRC, "Contemplating intermediate hop #%d: random choice.",
             cur_len+1);
-  excluded = smartlist_new();
-  if ((r = build_state_get_exit_node(state))) {
-    nodelist_add_node_and_family(excluded, r);
-  }
-  for (i = 0, cpath = head; i < cur_len; ++i, cpath=cpath->next) {
-    if ((r = node_get_by_id(cpath->extend_info->identity_digest))) {
-      nodelist_add_node_and_family(excluded, r);
-    }
-  }
+
+  excluded = build_middle_exclude_list(purpose, state, head, cur_len);
 
   if (state->need_uptime)
     flags |= CRN_NEED_UPTIME;
   if (state->need_capacity)
     flags |= CRN_NEED_CAPACITY;
+
+  /** If a hidden service circuit wants a specific middle node, pin it. */
+  if (middle_node_must_be_vanguard(options, purpose, cur_len)) {
+    log_debug(LD_GENERAL, "Picking a sticky node (cur_len = %d)", cur_len);
+    return pick_vanguard_middle_node(options, flags, cur_len, excluded);
+  }
+
   choice = router_choose_random_node(excluded, options->ExcludeNodes, flags);
   smartlist_free(excluded);
   return choice;
diff --git a/src/or/circuitbuild.h b/src/or/circuitbuild.h
index a85ef672f9..1014477663 100644
--- a/src/or/circuitbuild.h
+++ b/src/or/circuitbuild.h
@@ -12,6 +12,7 @@
 #ifndef TOR_CIRCUITBUILD_H
 #define TOR_CIRCUITBUILD_H
 
+int route_len_for_purpose(uint8_t purpose, extend_info_t *exit_ei);
 char *circuit_list_path(origin_circuit_t *circ, int verbose);
 char *circuit_list_path_for_controller(origin_circuit_t *circ);
 void circuit_log_path(int severity, unsigned int domain,
diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c
index 028fdbfc2f..27d8c62b5b 100644
--- a/src/or/circuitlist.c
+++ b/src/or/circuitlist.c
@@ -689,6 +689,10 @@ circuit_purpose_to_controller_string(uint8_t purpose)
 
     case CIRCUIT_PURPOSE_C_GENERAL:
       return "GENERAL";
+
+    case CIRCUIT_PURPOSE_C_HSDIR_GET:
+      return "HS_CLIENT_HSDIR";
+
     case CIRCUIT_PURPOSE_C_INTRODUCING:
     case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT:
     case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED:
@@ -700,6 +704,9 @@ circuit_purpose_to_controller_string(uint8_t purpose)
     case CIRCUIT_PURPOSE_C_REND_JOINED:
       return "HS_CLIENT_REND";
 
+    case CIRCUIT_PURPOSE_S_HSDIR_POST:
+      return "HS_SERVICE_HSDIR";
+
     case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
     case CIRCUIT_PURPOSE_S_INTRO:
       return "HS_SERVICE_INTRO";
@@ -716,6 +723,8 @@ circuit_purpose_to_controller_string(uint8_t purpose)
       return "CONTROLLER";
     case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
       return "PATH_BIAS_TESTING";
+    case CIRCUIT_PURPOSE_HS_VANGUARDS:
+      return "HS_VANGUARDS";
 
     default:
       tor_snprintf(buf, sizeof(buf), "UNKNOWN_%d", (int)purpose);
@@ -744,6 +753,7 @@ circuit_purpose_to_controller_hs_state_string(uint8_t purpose)
     case CIRCUIT_PURPOSE_TESTING:
     case CIRCUIT_PURPOSE_CONTROLLER:
     case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
+    case CIRCUIT_PURPOSE_HS_VANGUARDS:
       return NULL;
 
     case CIRCUIT_PURPOSE_INTRO_POINT:
@@ -753,6 +763,7 @@ circuit_purpose_to_controller_hs_state_string(uint8_t purpose)
     case CIRCUIT_PURPOSE_REND_ESTABLISHED:
       return "OR_HS_R_JOINED";
 
+    case CIRCUIT_PURPOSE_C_HSDIR_GET:
     case CIRCUIT_PURPOSE_C_INTRODUCING:
       return "HSCI_CONNECTING";
     case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT:
@@ -769,6 +780,7 @@ circuit_purpose_to_controller_hs_state_string(uint8_t purpose)
     case CIRCUIT_PURPOSE_C_REND_JOINED:
       return "HSCR_JOINED";
 
+    case CIRCUIT_PURPOSE_S_HSDIR_POST:
     case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
       return "HSSI_CONNECTING";
     case CIRCUIT_PURPOSE_S_INTRO:
@@ -813,6 +825,9 @@ circuit_purpose_to_string(uint8_t purpose)
       return "Hidden service client: Pending rendezvous point (ack received)";
     case CIRCUIT_PURPOSE_C_REND_JOINED:
       return "Hidden service client: Active rendezvous point";
+    case CIRCUIT_PURPOSE_C_HSDIR_GET:
+      return "Hidden service client: Fetching HS descriptor";
+
     case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT:
       return "Measuring circuit timeout";
 
@@ -824,6 +839,8 @@ circuit_purpose_to_string(uint8_t purpose)
       return "Hidden service: Connecting to rendezvous point";
     case CIRCUIT_PURPOSE_S_REND_JOINED:
       return "Hidden service: Active rendezvous point";
+    case CIRCUIT_PURPOSE_S_HSDIR_POST:
+      return "Hidden service: Uploading HS descriptor";
 
     case CIRCUIT_PURPOSE_TESTING:
       return "Testing circuit";
@@ -834,6 +851,9 @@ circuit_purpose_to_string(uint8_t purpose)
     case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
       return "Path-bias testing circuit";
 
+    case CIRCUIT_PURPOSE_HS_VANGUARDS:
+      return "Hidden service: Pre-built vanguard circuit";
+
     default:
       tor_snprintf(buf, sizeof(buf), "UNKNOWN_%d", (int)purpose);
       return buf;
@@ -1705,14 +1725,29 @@ circuit_can_be_cannibalized_for_v3_rp(const origin_circuit_t *circ)
   return 0;
 }
 
+/** We are trying to create a circuit of purpose <b>purpose</b> and we are
+ *  looking for cannibalizable circuits. Return the circuit purpose we would be
+ *  willing to cannibalize. */
+static uint8_t
+get_circuit_purpose_needed_to_cannibalize(uint8_t purpose)
+{
+  if (circuit_should_use_vanguards(purpose)) {
+    /* If we are using vanguards, then we should only cannibalize vanguard
+     * circuits so that we get the same path construction logic. */
+    return CIRCUIT_PURPOSE_HS_VANGUARDS;
+  } else {
+    /* If no vanguards are used just get a general circuit! */
+    return CIRCUIT_PURPOSE_C_GENERAL;
+  }
+}
+
 /** 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
  * as any of its hops; or NULL if no circuit fits this description.
  *
- * The <b>purpose</b> argument (currently ignored) refers to the purpose of
- * the circuit we want to create, not the purpose of the circuit we want to
- * cannibalize.
+ * The <b>purpose</b> argument refers to the purpose of the circuit we want to
+ * create, not the purpose of the circuit we want to cannibalize.
  *
  * If !CIRCLAUNCH_NEED_UPTIME, prefer returning non-uptime circuits.
  *
@@ -1725,7 +1760,7 @@ circuit_can_be_cannibalized_for_v3_rp(const origin_circuit_t *circ)
  * a new circuit.)
  */
 origin_circuit_t *
-circuit_find_to_cannibalize(uint8_t purpose, extend_info_t *info,
+circuit_find_to_cannibalize(uint8_t purpose_to_produce, extend_info_t *info,
                             int flags)
 {
   origin_circuit_t *best=NULL;
@@ -1733,29 +1768,46 @@ circuit_find_to_cannibalize(uint8_t purpose, extend_info_t *info,
   int need_capacity = (flags & CIRCLAUNCH_NEED_CAPACITY) != 0;
   int internal = (flags & CIRCLAUNCH_IS_INTERNAL) != 0;
   const or_options_t *options = get_options();
+  /* We want the circuit we are trying to cannibalize to have this purpose */
+  int purpose_to_search_for;
 
   /* Make sure we're not trying to create a onehop circ by
    * cannibalization. */
   tor_assert(!(flags & CIRCLAUNCH_ONEHOP_TUNNEL));
 
+  purpose_to_search_for = get_circuit_purpose_needed_to_cannibalize(
+                                                  purpose_to_produce);
+
+  tor_assert_nonfatal(purpose_to_search_for == CIRCUIT_PURPOSE_C_GENERAL ||
+                      purpose_to_search_for == CIRCUIT_PURPOSE_HS_VANGUARDS);
+
   log_debug(LD_CIRC,
             "Hunting for a circ to cannibalize: purpose %d, uptime %d, "
             "capacity %d, internal %d",
-            purpose, need_uptime, need_capacity, internal);
+            purpose_to_produce, need_uptime, need_capacity, internal);
 
   SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t *, circ_) {
     if (CIRCUIT_IS_ORIGIN(circ_) &&
         circ_->state == CIRCUIT_STATE_OPEN &&
         !circ_->marked_for_close &&
-        circ_->purpose == CIRCUIT_PURPOSE_C_GENERAL &&
+        circ_->purpose == purpose_to_search_for &&
         !circ_->timestamp_dirty) {
       origin_circuit_t *circ = TO_ORIGIN_CIRCUIT(circ_);
+
+      /* Only cannibalize from reasonable length circuits. If we
+       * want C_GENERAL, then only choose 3 hop circs. If we want
+       * HS_VANGUARDS, only choose 4 hop circs.
+       */
+      if (circ->build_state->desired_path_len !=
+          route_len_for_purpose(purpose_to_search_for, NULL)) {
+        goto next;
+      }
+
       if ((!need_uptime || circ->build_state->need_uptime) &&
           (!need_capacity || circ->build_state->need_capacity) &&
           (internal == circ->build_state->is_internal) &&
           !circ->unusable_for_new_conns &&
           circ->remaining_relay_early_cells &&
-          circ->build_state->desired_path_len == DEFAULT_ROUTE_LEN &&
           !circ->build_state->onehop_tunnel &&
           !circ->isolation_values_set) {
         if (info) {
diff --git a/src/or/circuituse.c b/src/or/circuituse.c
index f04448ffce..5f9567ea16 100644
--- a/src/or/circuituse.c
+++ b/src/or/circuituse.c
@@ -54,6 +54,7 @@
 #include "rephist.h"
 #include "router.h"
 #include "routerlist.h"
+#include "config.h"
 
 static void circuit_expire_old_circuits_clientside(void);
 static void circuit_increment_failure_count(void);
@@ -133,6 +134,7 @@ circuit_is_acceptable(const origin_circuit_t *origin_circ,
   }
 
   if (purpose == CIRCUIT_PURPOSE_C_GENERAL ||
+      purpose == CIRCUIT_PURPOSE_HS_VANGUARDS ||
       purpose == CIRCUIT_PURPOSE_C_REND_JOINED) {
     if (circ->timestamp_dirty &&
        circ->timestamp_dirty+get_options()->MaxCircuitDirtiness <= now)
@@ -156,7 +158,9 @@ circuit_is_acceptable(const origin_circuit_t *origin_circ,
   if (need_internal != build_state->is_internal)
     return 0;
 
-  if (purpose == CIRCUIT_PURPOSE_C_GENERAL) {
+  if (purpose == CIRCUIT_PURPOSE_C_GENERAL ||
+      purpose == CIRCUIT_PURPOSE_S_HSDIR_POST ||
+      purpose == CIRCUIT_PURPOSE_C_HSDIR_GET) {
     tor_addr_t addr;
     const int family = tor_addr_parse(&addr, conn->socks_request->address);
     if (!exitnode && !build_state->onehop_tunnel) {
@@ -238,6 +242,8 @@ circuit_is_better(const origin_circuit_t *oa, const origin_circuit_t *ob,
     return 1; /* oa is better. It's not relaxed. */
 
   switch (purpose) {
+    case CIRCUIT_PURPOSE_S_HSDIR_POST:
+    case CIRCUIT_PURPOSE_C_HSDIR_GET:
     case CIRCUIT_PURPOSE_C_GENERAL:
       /* if it's used but less dirty it's best;
        * else if it's more recently created it's best
@@ -323,6 +329,9 @@ circuit_get_best(const entry_connection_t *conn,
   tor_assert(conn);
 
   tor_assert(purpose == CIRCUIT_PURPOSE_C_GENERAL ||
+             purpose == CIRCUIT_PURPOSE_HS_VANGUARDS ||
+             purpose == CIRCUIT_PURPOSE_C_HSDIR_GET ||
+             purpose == CIRCUIT_PURPOSE_S_HSDIR_POST ||
              purpose == CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT ||
              purpose == CIRCUIT_PURPOSE_C_REND_JOINED);
 
@@ -1080,7 +1089,8 @@ circuit_is_available_for_use(const circuit_t *circ)
     return 0; /* Don't mess with marked circs */
   if (circ->timestamp_dirty)
     return 0; /* Only count clean circs */
-  if (circ->purpose != CIRCUIT_PURPOSE_C_GENERAL)
+  if (circ->purpose != CIRCUIT_PURPOSE_C_GENERAL &&
+      circ->purpose != CIRCUIT_PURPOSE_HS_VANGUARDS)
     return 0; /* We only pay attention to general purpose circuits.
                  General purpose circuits are always origin circuits. */
 
@@ -1192,6 +1202,25 @@ needs_circuits_for_build(int num)
   return 0;
 }
 
+/**
+ * Launch the appropriate type of predicted circuit for hidden
+ * services, depending on our options.
+ */
+static void
+circuit_launch_predicted_hs_circ(int flags)
+{
+  /* K.I.S.S. implementation of bug #23101: If we are using
+   * vanguards or pinned middles, pre-build a specific purpose
+   * for HS circs. */
+  if (circuit_should_use_vanguards(CIRCUIT_PURPOSE_HS_VANGUARDS)) {
+    circuit_launch(CIRCUIT_PURPOSE_HS_VANGUARDS, flags);
+  } else {
+    /* If no vanguards, then no HS-specific prebuilt circuits are needed.
+     * Normal GENERAL circs are fine */
+    circuit_launch(CIRCUIT_PURPOSE_C_GENERAL, flags);
+  }
+}
+
 /** Determine how many circuits we have open that are clean,
  * Make sure it's enough for all the upcoming behaviors we predict we'll have.
  * But put an upper bound on the total number of circuits.
@@ -1245,7 +1274,7 @@ circuit_predict_and_launch_new(void)
              "Have %d clean circs (%d internal), need another internal "
              "circ for my hidden service.",
              num, num_internal);
-    circuit_launch(CIRCUIT_PURPOSE_C_GENERAL, flags);
+    circuit_launch_predicted_hs_circ(flags);
     return;
   }
 
@@ -1263,7 +1292,8 @@ circuit_predict_and_launch_new(void)
              "Have %d clean circs (%d uptime-internal, %d internal), need"
              " another hidden service circ.",
              num, num_uptime_internal, num_internal);
-    circuit_launch(CIRCUIT_PURPOSE_C_GENERAL, flags);
+
+    circuit_launch_predicted_hs_circ(flags);
     return;
   }
 
@@ -1458,6 +1488,9 @@ circuit_expire_old_circuits_clientside(void)
     } else if (!circ->timestamp_dirty && circ->state == CIRCUIT_STATE_OPEN) {
       if (timercmp(&circ->timestamp_began, &cutoff, OP_LT)) {
         if (circ->purpose == CIRCUIT_PURPOSE_C_GENERAL ||
+                circ->purpose == CIRCUIT_PURPOSE_C_HSDIR_GET ||
+                circ->purpose == CIRCUIT_PURPOSE_S_HSDIR_POST ||
+                circ->purpose == CIRCUIT_PURPOSE_HS_VANGUARDS ||
                 circ->purpose == CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT ||
                 circ->purpose == CIRCUIT_PURPOSE_S_ESTABLISH_INTRO ||
                 circ->purpose == CIRCUIT_PURPOSE_TESTING ||
@@ -1650,6 +1683,8 @@ circuit_has_opened(origin_circuit_t *circ)
       hs_client_circuit_has_opened(circ);
       break;
     case CIRCUIT_PURPOSE_C_GENERAL:
+    case CIRCUIT_PURPOSE_C_HSDIR_GET:
+    case CIRCUIT_PURPOSE_S_HSDIR_POST:
       /* Tell any AP connections that have been waiting for a new
        * circuit that one is ready. */
       circuit_try_attaching_streams(circ);
@@ -1727,6 +1762,8 @@ circuit_build_failed(origin_circuit_t *circ)
       circ->cpath->prev->prev->state == CPATH_STATE_OPEN) {
     failed_at_last_hop = 1;
   }
+
+  /* Check if we failed at first hop */
   if (circ->cpath &&
       circ->cpath->state != CPATH_STATE_OPEN &&
       ! circ->base_.received_destroy) {
@@ -1762,8 +1799,22 @@ circuit_build_failed(origin_circuit_t *circ)
                TO_CIRCUIT(circ)->n_circ_id, circ->global_identifier);
     }
     if (n_chan_id && !already_marked) {
-      /* New guard API: we failed. */
-      if (circ->guard_state)
+      /*
+       * If we have guard state (new guard API) and our path selection
+       * code actually chose a full path, then blame the failure of this
+       * circuit on the guard.
+       *
+       * Note that we deliberately use circuit_get_cpath_len() (and not
+       * circuit_get_cpath_opened_len()) because we only want to ensure
+       * that a full path is *chosen*. This is different than a full path
+       * being *built*. We only want to blame *build* failures on this
+       * guard. Path selection failures can happen spuriously for a number
+       * of reasons (such as aggressive/invalid user-specified path
+       * restrictions in the torrc, as well as non-user reasons like
+       * exitpolicy issues), and so should not be counted here.
+       */
+      if (circ->guard_state &&
+          circuit_get_cpath_len(circ) >= circ->build_state->desired_path_len)
         entry_guard_failed(&circ->guard_state);
       /* if there are any one-hop streams waiting on this circuit, fail
        * them now so they can retry elsewhere. */
@@ -1772,6 +1823,8 @@ circuit_build_failed(origin_circuit_t *circ)
   }
 
   switch (circ->base_.purpose) {
+    case CIRCUIT_PURPOSE_C_HSDIR_GET:
+    case CIRCUIT_PURPOSE_S_HSDIR_POST:
     case CIRCUIT_PURPOSE_C_GENERAL:
       /* If we never built the circuit, note it as a failure. */
       circuit_increment_failure_count();
@@ -1856,6 +1909,106 @@ have_enough_path_info(int need_exit)
     return router_have_consensus_path() != CONSENSUS_PATH_UNKNOWN;
 }
 
+/**
+ * Tell us if a circuit is a hidden service circuit.
+ */
+int
+circuit_purpose_is_hidden_service(uint8_t purpose)
+{
+   if (purpose == CIRCUIT_PURPOSE_HS_VANGUARDS) {
+     return 1;
+   }
+
+   /* Client-side purpose */
+   if (purpose >= CIRCUIT_PURPOSE_C_HS_MIN_ &&
+       purpose <= CIRCUIT_PURPOSE_C_HS_MAX_) {
+     return 1;
+   }
+
+   /* Service-side purpose */
+   if (purpose >= CIRCUIT_PURPOSE_S_HS_MIN_ &&
+       purpose <= CIRCUIT_PURPOSE_S_HS_MAX_) {
+     return 1;
+   }
+
+   return 0;
+}
+
+/**
+ * Return true if this circuit purpose should use vanguards
+ * or pinned Layer2 or Layer3 guards.
+ *
+ * This function takes both the circuit purpose and the
+ * torrc options for pinned middles/vanguards into account
+ * (ie: the circuit must be a hidden service circuit and
+ * vanguards/pinned middles must be enabled for it to return
+ * true).
+ */
+int
+circuit_should_use_vanguards(uint8_t purpose)
+{
+  const or_options_t *options = get_options();
+
+  /* Only hidden service circuits use vanguards */
+  if (!circuit_purpose_is_hidden_service(purpose))
+    return 0;
+
+  /* Pinned middles are effectively vanguards */
+  if (options->HSLayer2Nodes || options->HSLayer3Nodes)
+    return 1;
+
+  return 0;
+}
+
+/**
+ * Return true for the set of conditions for which it is OK to use
+ * a cannibalized circuit.
+ *
+ * Don't cannibalize for onehops, or tor2web, or certain purposes.
+ */
+static int
+circuit_should_cannibalize_to_build(uint8_t purpose_to_build,
+                                    int has_extend_info,
+                                    int onehop_tunnel,
+                                    int need_specific_rp)
+{
+
+  /* Do not try to cannibalize if this is a one hop circuit, or
+   * is a tor2web/special rp. */
+  if (onehop_tunnel || need_specific_rp) {
+    return 0;
+  }
+
+  /* Don't try to cannibalize for general purpose circuits that do not
+   * specify a custom exit. */
+  if (purpose_to_build == CIRCUIT_PURPOSE_C_GENERAL && !has_extend_info) {
+    return 0;
+  }
+
+  /* Don't cannibalize for testing circuits. We want to see if they
+   * complete normally. Also don't cannibalize for vanguard-purpose
+   * circuits, since those are specially pre-built for later
+   * cannibalization by the actual specific circuit types that need
+   * vanguards.
+   */
+  if (purpose_to_build == CIRCUIT_PURPOSE_TESTING ||
+      purpose_to_build == CIRCUIT_PURPOSE_HS_VANGUARDS) {
+    return 0;
+  }
+
+  /* For vanguards, the server-side intro circ is not cannibalized
+   * because we pre-build 4 hop HS circuits, and it only needs a 3 hop
+   * circuit. It is also long-lived, so it is more important that
+   * it have lower latency than get built fast.
+   */
+  if (circuit_should_use_vanguards(purpose_to_build) &&
+      purpose_to_build == CIRCUIT_PURPOSE_S_ESTABLISH_INTRO) {
+    return 0;
+  }
+
+  return 1;
+}
+
 /** Launch a new circuit with purpose <b>purpose</b> and exit node
  * <b>extend_info</b> (or NULL to select a random exit node).  If flags
  * contains CIRCLAUNCH_NEED_UPTIME, choose among routers with high uptime.  If
@@ -1890,9 +2043,12 @@ circuit_launch_by_extend_info(uint8_t purpose,
     need_specific_rp = 1;
   }
 
-  if ((extend_info || purpose != CIRCUIT_PURPOSE_C_GENERAL) &&
-      purpose != CIRCUIT_PURPOSE_TESTING &&
-      !onehop_tunnel && !need_specific_rp) {
+  /* If we can/should cannibalize another circuit to build this one,
+   * then do so. */
+  if (circuit_should_cannibalize_to_build(purpose,
+                                          extend_info != NULL,
+                                          onehop_tunnel,
+                                          need_specific_rp)) {
     /* see if there are appropriate circs available to cannibalize. */
     /* XXX if we're planning to add a hop, perhaps we want to look for
      * internal circs rather than exit circs? -RD */
@@ -1947,6 +2103,8 @@ circuit_launch_by_extend_info(uint8_t purpose,
         case CIRCUIT_PURPOSE_C_INTRODUCING:
         case CIRCUIT_PURPOSE_S_CONNECT_REND:
         case CIRCUIT_PURPOSE_C_GENERAL:
+        case CIRCUIT_PURPOSE_S_HSDIR_POST:
+        case CIRCUIT_PURPOSE_C_HSDIR_GET:
         case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
           /* need to add a new hop */
           tor_assert(extend_info);
@@ -2211,7 +2369,9 @@ circuit_get_open_circ_or_launch(entry_connection_t *conn,
     /* If we have specified a particular exit node for our
      * connection, then be sure to open a circuit to that exit node.
      */
-    if (desired_circuit_purpose == CIRCUIT_PURPOSE_C_GENERAL) {
+    if (desired_circuit_purpose == CIRCUIT_PURPOSE_C_GENERAL ||
+        desired_circuit_purpose == CIRCUIT_PURPOSE_S_HSDIR_POST ||
+        desired_circuit_purpose == CIRCUIT_PURPOSE_C_HSDIR_GET) {
       if (conn->chosen_exit_name) {
         const node_t *r;
         int opt = conn->chosen_exit_optional;
@@ -2319,7 +2479,9 @@ circuit_get_open_circ_or_launch(entry_connection_t *conn,
 
     /* Now trigger things that need to happen when we launch circuits */
 
-    if (desired_circuit_purpose == CIRCUIT_PURPOSE_C_GENERAL) {
+    if (desired_circuit_purpose == CIRCUIT_PURPOSE_C_GENERAL ||
+        desired_circuit_purpose == CIRCUIT_PURPOSE_C_HSDIR_GET ||
+        desired_circuit_purpose == CIRCUIT_PURPOSE_S_HSDIR_POST) {
       /* We just caused a circuit to get built because of this stream.
        * If this stream has caused a _lot_ of circuits to be built, that's
        * a bad sign: we should tell the user. */
@@ -2448,6 +2610,8 @@ link_apconn_to_circ(entry_connection_t *apconn, origin_circuit_t *circ,
   /* See if we can use optimistic data on this circuit */
   if (optimistic_data_enabled() &&
       (circ->base_.purpose == CIRCUIT_PURPOSE_C_GENERAL ||
+       circ->base_.purpose == CIRCUIT_PURPOSE_C_HSDIR_GET ||
+       circ->base_.purpose == CIRCUIT_PURPOSE_S_HSDIR_POST ||
        circ->base_.purpose == CIRCUIT_PURPOSE_C_REND_JOINED))
     apconn->may_use_optimistic_data = 1;
   else
@@ -2568,6 +2732,39 @@ connection_ap_handshake_attach_chosen_circuit(entry_connection_t *conn,
   return 1;
 }
 
+/**
+ * Return an appropriate circuit purpose for non-rend streams.
+ * We don't handle rends here because a rend stream triggers two
+ * circuit builds with different purposes, so it is handled elsewhere.
+ *
+ * This function just figures out what type of hsdir activity this is,
+ * and tells us. Everything else is general.
+ */
+static int
+connection_ap_get_nonrend_circ_purpose(const entry_connection_t *conn)
+{
+  const connection_t *base_conn = ENTRY_TO_CONN(conn);
+  tor_assert_nonfatal(!connection_edge_is_rendezvous_stream(
+                      ENTRY_TO_EDGE_CONN(conn)));
+
+  if (base_conn->linked_conn &&
+      base_conn->linked_conn->type == CONN_TYPE_DIR) {
+    /* Set a custom purpose for hsdir activity */
+    if (base_conn->linked_conn->purpose == DIR_PURPOSE_UPLOAD_RENDDESC_V2 ||
+       base_conn->linked_conn->purpose == DIR_PURPOSE_UPLOAD_HSDESC) {
+      return CIRCUIT_PURPOSE_S_HSDIR_POST;
+    } else if (base_conn->linked_conn->purpose
+                 == DIR_PURPOSE_FETCH_RENDDESC_V2 ||
+               base_conn->linked_conn->purpose
+                 == DIR_PURPOSE_FETCH_HSDESC) {
+      return CIRCUIT_PURPOSE_C_HSDIR_GET;
+    }
+  }
+
+  /* All other purposes are general for now */
+  return CIRCUIT_PURPOSE_C_GENERAL;
+}
+
 /** Try to find a safe live circuit for stream <b>conn</b>.  If we find one,
  * attach the stream, send appropriate cells, and return 1.  Otherwise,
  * try to launch new circuit(s) for the stream.  If we can launch
@@ -2666,9 +2863,12 @@ connection_ap_handshake_attach_circuit(entry_connection_t *conn)
     }
 
     /* Find the circuit that we should use, if there is one. Otherwise
-     * launch it. */
-    retval = circuit_get_open_circ_or_launch(
-        conn, CIRCUIT_PURPOSE_C_GENERAL, &circ);
+     * launch it
+     */
+    retval = circuit_get_open_circ_or_launch(conn,
+            connection_ap_get_nonrend_circ_purpose(conn),
+            &circ);
+
     if (retval < 1) {
       /* We were either told "-1" (complete failure) or 0 (circuit in
        * progress); we can't attach this stream yet. */
diff --git a/src/or/circuituse.h b/src/or/circuituse.h
index 2b0f983f1a..71c818b978 100644
--- a/src/or/circuituse.h
+++ b/src/or/circuituse.h
@@ -63,6 +63,9 @@ int hostname_in_track_host_exits(const or_options_t *options,
                                  const char *address);
 void mark_circuit_unusable_for_new_conns(origin_circuit_t *circ);
 
+int circuit_purpose_is_hidden_service(uint8_t);
+int circuit_should_use_vanguards(uint8_t);
+
 #ifdef TOR_UNIT_TESTS
 /* Used only by circuituse.c and test_circuituse.c */
 
diff --git a/src/or/config.c b/src/or/config.c
index bd309bc87a..afaf867851 100644
--- a/src/or/config.c
+++ b/src/or/config.c
@@ -404,6 +404,8 @@ static config_var_t option_vars_[] = {
   V(Socks5ProxyPassword,         STRING,   NULL),
   VAR("KeyDirectory",            FILENAME, KeyDirectory_option, NULL),
   V(KeyDirectoryGroupReadable,   BOOL,     "0"),
+  VAR("_HSLayer2Nodes",          ROUTERSET,  HSLayer2Nodes,  NULL),
+  VAR("_HSLayer3Nodes",          ROUTERSET,  HSLayer3Nodes,  NULL),
   V(KeepalivePeriod,             INTERVAL, "5 minutes"),
   V(KeepBindCapabilities,            AUTOBOOL, "auto"),
   VAR("Log",                     LINELIST, Logs,             NULL),
@@ -1648,6 +1650,8 @@ options_need_geoip_info(const or_options_t *options, const char **reason_out)
     routerset_needs_geoip(options->ExitNodes) ||
     routerset_needs_geoip(options->ExcludeExitNodes) ||
     routerset_needs_geoip(options->ExcludeNodes) ||
+    routerset_needs_geoip(options->HSLayer2Nodes) ||
+    routerset_needs_geoip(options->HSLayer3Nodes) ||
     routerset_needs_geoip(options->Tor2webRendezvousPoints);
 
   if (routerset_usage && reason_out) {
@@ -2089,6 +2093,10 @@ options_act(const or_options_t *old_options)
                          options->ExcludeExitNodes) ||
         !routerset_equal(old_options->EntryNodes, options->EntryNodes) ||
         !routerset_equal(old_options->ExitNodes, options->ExitNodes) ||
+        !routerset_equal(old_options->HSLayer2Nodes,
+                         options->HSLayer2Nodes) ||
+        !routerset_equal(old_options->HSLayer3Nodes,
+                         options->HSLayer3Nodes) ||
         !routerset_equal(old_options->Tor2webRendezvousPoints,
                          options->Tor2webRendezvousPoints) ||
         options->StrictNodes != old_options->StrictNodes) {
diff --git a/src/or/connection_edge.c b/src/or/connection_edge.c
index 0c4352ea13..4021ca9e0c 100644
--- a/src/or/connection_edge.c
+++ b/src/or/connection_edge.c
@@ -2592,6 +2592,8 @@ connection_ap_supports_optimistic_data(const entry_connection_t *conn)
   if (edge_conn->on_circuit == NULL ||
       edge_conn->on_circuit->state != CIRCUIT_STATE_OPEN ||
       (edge_conn->on_circuit->purpose != CIRCUIT_PURPOSE_C_GENERAL &&
+       edge_conn->on_circuit->purpose != CIRCUIT_PURPOSE_C_HSDIR_GET &&
+       edge_conn->on_circuit->purpose != CIRCUIT_PURPOSE_S_HSDIR_POST &&
        edge_conn->on_circuit->purpose != CIRCUIT_PURPOSE_C_REND_JOINED))
     return 0;
 
diff --git a/src/or/or.h b/src/or/or.h
index d9fab69c06..c81e29c95c 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -506,6 +506,7 @@ typedef enum {
  */
 /** Client-side circuit purpose: Normal circuit, with cpath. */
 #define CIRCUIT_PURPOSE_C_GENERAL 5
+#define CIRCUIT_PURPOSE_C_HS_MIN_ 6
 /** Client-side circuit purpose: at the client, connecting to intro point. */
 #define CIRCUIT_PURPOSE_C_INTRODUCING 6
 /** Client-side circuit purpose: at the client, sent INTRODUCE1 to intro point,
@@ -523,28 +524,46 @@ typedef enum {
 #define CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED 11
 /** Client-side circuit purpose: at the client, rendezvous established. */
 #define CIRCUIT_PURPOSE_C_REND_JOINED 12
+/** This circuit is used for getting hsdirs */
+#define CIRCUIT_PURPOSE_C_HSDIR_GET 13
+#define CIRCUIT_PURPOSE_C_HS_MAX_ 13
 /** This circuit is used for build time measurement only */
-#define CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT 13
-#define CIRCUIT_PURPOSE_C_MAX_ 13
+#define CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT 14
+#define CIRCUIT_PURPOSE_C_MAX_ 14
+
+#define CIRCUIT_PURPOSE_S_HS_MIN_ 15
 /** Hidden-service-side circuit purpose: at the service, waiting for
  * introductions. */
-#define CIRCUIT_PURPOSE_S_ESTABLISH_INTRO 14
+#define CIRCUIT_PURPOSE_S_ESTABLISH_INTRO 15
 /** Hidden-service-side circuit purpose: at the service, successfully
  * established intro. */
-#define CIRCUIT_PURPOSE_S_INTRO 15
+#define CIRCUIT_PURPOSE_S_INTRO 16
 /** Hidden-service-side circuit purpose: at the service, connecting to rend
  * point. */
-#define CIRCUIT_PURPOSE_S_CONNECT_REND 16
+#define CIRCUIT_PURPOSE_S_CONNECT_REND 17
 /** Hidden-service-side circuit purpose: at the service, rendezvous
  * established. */
-#define CIRCUIT_PURPOSE_S_REND_JOINED 17
+#define CIRCUIT_PURPOSE_S_REND_JOINED 18
+/** This circuit is used for uploading hsdirs */
+#define CIRCUIT_PURPOSE_S_HSDIR_POST 19
+#define CIRCUIT_PURPOSE_S_HS_MAX_ 19
+
 /** A testing circuit; not meant to be used for actual traffic. */
-#define CIRCUIT_PURPOSE_TESTING 18
+#define CIRCUIT_PURPOSE_TESTING 20
 /** A controller made this circuit and Tor should not use it. */
-#define CIRCUIT_PURPOSE_CONTROLLER 19
+#define CIRCUIT_PURPOSE_CONTROLLER 21
 /** This circuit is used for path bias probing only */
-#define CIRCUIT_PURPOSE_PATH_BIAS_TESTING 20
-#define CIRCUIT_PURPOSE_MAX_ 20
+#define CIRCUIT_PURPOSE_PATH_BIAS_TESTING 22
+
+/** This circuit is used for vanguards/restricted paths.
+ *
+ *  This type of circuit is *only* created preemptively and never
+ *  on-demand. When an HS operation needs to take place (e.g. connect to an
+ *  intro point), these circuits are then cannibalized and repurposed to the
+ *  actual needed HS purpose. */
+#define CIRCUIT_PURPOSE_HS_VANGUARDS 23
+
+#define CIRCUIT_PURPOSE_MAX_ 23
 /** A catch-all for unrecognized purposes. Currently we don't expect
  * to make or see any circuits with this purpose. */
 #define CIRCUIT_PURPOSE_UNKNOWN 255
@@ -3876,6 +3895,14 @@ typedef struct {
   /** A routerset that should be used when picking RPs for HS circuits. */
   routerset_t *Tor2webRendezvousPoints;
 
+  /** A routerset that should be used when picking middle nodes for HS
+   *  circuits. */
+  routerset_t *HSLayer2Nodes;
+
+  /** A routerset that should be used when picking third-hop nodes for HS
+   *  circuits. */
+  routerset_t *HSLayer3Nodes;
+
   /** Onion Services in HiddenServiceSingleHopMode make one-hop (direct)
    * circuits between the onion service server, and the introduction and
    * rendezvous points. (Onion service descriptors are still posted using