Logic to implement rendezvous/introduction via unknown servers.

- Add a new extend_info_t datatype to hold information needed to
  extend a circuit (addr,port,keyid,onion_key).  Use it in cpath and
  build_state.  Make appropriate functions take or return it instead of
  routerinfo_t or keyid.

- #if 0 needless check in circuit_get_by_edge_conn; if nobody triggers this
  error in 0.1.0.10, nobody will trigger it.

- Implement new hidden service descriptor format, which contains "extend
  info" for introduction points, along with protocol version list.
  - Parse new format.
  - Generate new format
  - Cache old and new formats alongside each other.
  - Directories serve "old" format if asked in old way, "newest available"
    format if asked in new way.
  - Use new format to find introduction points if possible; otherwise fall
    back.  Keep nickname lists and extendinfo lists in sync.
  - Tests for new format.

- Implement new "v2" INTRODUCE cell format.
  - Accept new format
  - Use new format if we have a versioned service descriptor that says the
    server accepts the new format.

- Add documentation for functions and data types.


svn:r4506

13 files changed, 666 insertions, 338 deletions

diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index e351dcee23..fcdb8ec7ee 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -21,13 +21,12 @@ extern circuit_t *global_circuitlist;
 
 static int circuit_deliver_create_cell(circuit_t *circ,
                                        uint8_t cell_type, char *payload);
-static int onion_pick_cpath_exit(circuit_t *circ, routerinfo_t *exit);
+static int onion_pick_cpath_exit(circuit_t *circ, extend_info_t *exit);
 static crypt_path_t *onion_next_hop_in_cpath(crypt_path_t *cpath);
-static int onion_next_router_in_cpath(circuit_t *circ, routerinfo_t **router);
 static int onion_extend_cpath(uint8_t purpose, crypt_path_t **head_ptr,
                               cpath_build_state_t *state);
 static int count_acceptable_routers(smartlist_t *routers);
-static int onion_append_hop(crypt_path_t **head_ptr, routerinfo_t *choice);
+static int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice);
 
 /** Iterate over values of circ_id, starting from conn-\>next_circ_id,
  * and with the high bit specified by circ_id_type (see
@@ -85,31 +84,25 @@ circuit_list_path(circuit_t *circ, int verbose)
   elements = smartlist_create();
 
   if (verbose) {
+    const char *nickname = build_state_get_exit_nickname(circ->build_state);
     tor_snprintf(buf, sizeof(buf)-1, "%s%s circ (length %d, exit %s):",
                  circ->build_state->is_internal ? "internal" : "exit",
                  circ->build_state->need_uptime ? " (high-uptime)" : "",
                  circ->build_state->desired_path_len,
-                 circ->build_state->chosen_exit_name);
+                 nickname?nickname:"unnamed");
     smartlist_add(elements, tor_strdup(buf));
   }
 
   hop = circ->cpath;
   do {
     const char *elt;
-    routerinfo_t *r;
     if (!hop)
       break;
     if (!verbose && hop->state != CPATH_STATE_OPEN)
       break;
-    if ((r = router_get_by_digest(hop->identity_digest))) {
-      elt = r->nickname;
-    } else if (circ->purpose == CIRCUIT_PURPOSE_C_REND_JOINED) {
-      elt = "<rendezvous splice>";
-    } else {
-      buf[0]='$';
-      base16_encode(buf+1,sizeof(buf)-1,hop->identity_digest,DIGEST_LEN);
-      elt = buf;
-    }
+    if (!hop->extend_info)
+      break;
+    elt = hop->extend_info->nickname;
     if (verbose) {
       size_t len = strlen(elt)+2+strlen(states[hop->state])+1;
       char *v = tor_malloc(len);
@@ -166,7 +159,7 @@ circuit_rep_hist_note_result(circuit_t *circ)
     prev_digest = me->identity_digest;
   }
   do {
-    router = router_get_by_digest(hop->identity_digest);
+    router = router_get_by_digest(hop->extend_info->identity_digest);
     if (router) {
       if (prev_digest) {
         if (hop->state == CPATH_STATE_OPEN)
@@ -272,7 +265,7 @@ circuit_init(uint8_t purpose, int need_uptime, int need_capacity, int internal)
   return circ;
 }
 
-/** Build a new circuit for <b>purpose</b>. If <b>exit</b>
+/** Build a new circuit for <b>purpose</b>. If <b>info/b>
  * is defined, then use that as your exit router, else choose a suitable
  * exit node.
  *
@@ -280,14 +273,14 @@ circuit_init(uint8_t purpose, int need_uptime, int need_capacity, int internal)
  * it's not open already.
  */
 circuit_t *
-circuit_establish_circuit(uint8_t purpose, routerinfo_t *exit,
+circuit_establish_circuit(uint8_t purpose, extend_info_t *info,
                           int need_uptime, int need_capacity, int internal)
 {
   circuit_t *circ;
 
   circ = circuit_init(purpose, need_uptime, need_capacity, internal);
 
-  if (onion_pick_cpath_exit(circ, exit) < 0 ||
+  if (onion_pick_cpath_exit(circ, info) < 0 ||
       onion_populate_cpath(circ) < 0) {
     circuit_mark_for_close(circ);
     return NULL;
@@ -309,26 +302,32 @@ circuit_establish_circuit(uint8_t purpose, routerinfo_t *exit,
 int
 circuit_handle_first_hop(circuit_t *circ)
 {
-  routerinfo_t *firsthop;
+  crypt_path_t *firsthop;
   connection_t *n_conn;
+  char tmpbuf[INET_NTOA_BUF_LEN+1];
+  struct in_addr in;
 
-  onion_next_router_in_cpath(circ, &firsthop);
+  firsthop = onion_next_hop_in_cpath(circ->cpath);
   tor_assert(firsthop);
 
   /* now see if we're already connected to the first OR in 'route' */
-  log_fn(LOG_DEBUG,"Looking for firsthop '%s:%u'",
-      firsthop->address,firsthop->or_port);
+  in.s_addr = htonl(firsthop->extend_info->addr);
+  tor_inet_ntoa(&in, tmpbuf, sizeof(tmpbuf));
+  log_fn(LOG_DEBUG,"Looking for firsthop '%s:%u'",tmpbuf,
+         firsthop->extend_info->port);
   /* imprint the circuit with its future n_conn->id */
-  memcpy(circ->n_conn_id_digest, firsthop->identity_digest, DIGEST_LEN);
-  n_conn = connection_get_by_identity_digest(firsthop->identity_digest,
-                                             CONN_TYPE_OR);
+  memcpy(circ->n_conn_id_digest, firsthop->extend_info->identity_digest,
+         DIGEST_LEN);
+  n_conn = connection_get_by_identity_digest(
+         firsthop->extend_info->identity_digest, CONN_TYPE_OR);
   if (!n_conn || n_conn->state != OR_CONN_STATE_OPEN) { /* not currently connected */
-    circ->n_addr = firsthop->addr;
-    circ->n_port = firsthop->or_port;
+    circ->n_addr = firsthop->extend_info->addr;
+    circ->n_port = firsthop->extend_info->port;
 
     if (!n_conn) { /* launch the connection */
-      n_conn = connection_or_connect(firsthop->addr, firsthop->or_port,
-                                     firsthop->identity_digest);
+      n_conn = connection_or_connect(firsthop->extend_info->addr,
+                                     firsthop->extend_info->port,
+                                     firsthop->extend_info->identity_digest);
       if (!n_conn) { /* connect failed, forget the whole thing */
         log_fn(LOG_INFO,"connect to firsthop failed. Closing.");
         return -1;
@@ -452,7 +451,6 @@ circuit_send_next_onion_skin(circuit_t *circ)
 {
   crypt_path_t *hop;
   routerinfo_t *router;
-  int r;
   char payload[2+4+DIGEST_LEN+ONIONSKIN_CHALLENGE_LEN];
   char *onionskin;
   size_t payload_len;
@@ -465,20 +463,15 @@ circuit_send_next_onion_skin(circuit_t *circ)
     log_fn(LOG_DEBUG,"First skin; sending create cell.");
 
     router = router_get_by_digest(circ->n_conn->identity_digest);
-    if (!router) {
-      log_fn(LOG_WARN,"Couldn't find routerinfo for %s",
-             circ->n_conn->nickname);
-      return -1;
-    }
 
     if (1 || /* Disable this '1' once we believe CREATE_FAST works. XXXX */
-        (get_options()->ORPort || !router->platform ||
+        (get_options()->ORPort || !router || !router->platform ||
          !tor_version_as_new_as(router->platform, "0.1.0.6-rc"))) {
       /* We are an OR, or we are connecting to an old Tor: we should
        * send an old slow create cell.
        */
       cell_type = CELL_CREATE;
-      if (onion_skin_create(router->onion_pkey,
+      if (onion_skin_create(circ->cpath->extend_info->onion_key,
                             &(circ->cpath->dh_handshake_state),
                             payload) < 0) {
         log_fn(LOG_WARN,"onion_skin_create (first hop) failed.");
@@ -505,8 +498,8 @@ circuit_send_next_onion_skin(circuit_t *circ)
     tor_assert(circ->cpath->state == CPATH_STATE_OPEN);
     tor_assert(circ->state == CIRCUIT_STATE_BUILDING);
     log_fn(LOG_DEBUG,"starting to send subsequent skin.");
-    r = onion_next_router_in_cpath(circ, &router);
-    if (r > 0) {
+    hop = onion_next_hop_in_cpath(circ->cpath);
+    if (!hop) {
       /* done building the circuit. whew. */
       circ->state = CIRCUIT_STATE_OPEN;
       log_fn(LOG_INFO,"circuit built!");
@@ -524,19 +517,17 @@ circuit_send_next_onion_skin(circuit_t *circ)
       circuit_rep_hist_note_result(circ);
       circuit_has_opened(circ); /* do other actions as necessary */
       return 0;
-    } else if (r < 0) {
-      return -1;
     }
-    hop = onion_next_hop_in_cpath(circ->cpath);
 
-    *(uint32_t*)payload = htonl(hop->addr);
-    *(uint16_t*)(payload+4) = htons(hop->port);
+    *(uint32_t*)payload = htonl(hop->extend_info->addr);
+    *(uint16_t*)(payload+4) = htons(hop->extend_info->port);
 
     onionskin = payload+2+4;
-    memcpy(payload+2+4+ONIONSKIN_CHALLENGE_LEN, hop->identity_digest, DIGEST_LEN);
+    memcpy(payload+2+4+ONIONSKIN_CHALLENGE_LEN, hop->extend_info->identity_digest, DIGEST_LEN);
     payload_len = 2+4+ONIONSKIN_CHALLENGE_LEN+DIGEST_LEN;
 
-    if (onion_skin_create(router->onion_pkey, &(hop->dh_handshake_state), onionskin) < 0) {
+    if (onion_skin_create(hop->extend_info->onion_key,
+                          &(hop->dh_handshake_state), onionskin) < 0) {
       log_fn(LOG_WARN,"onion_skin_create failed.");
       return -1;
     }
@@ -1218,10 +1209,9 @@ choose_good_exit_server(uint8_t purpose, routerlist_t *dir,
  * router (or use <b>exit</b> if provided). Store these in the
  * cpath. Return 0 if ok, -1 if circuit should be closed. */
 static int
-onion_pick_cpath_exit(circuit_t *circ, routerinfo_t *exit)
+onion_pick_cpath_exit(circuit_t *circ, extend_info_t *exit)
 {
   cpath_build_state_t *state = circ->build_state;
-
   routerlist_t *rl;
   int r;
 
@@ -1237,16 +1227,17 @@ onion_pick_cpath_exit(circuit_t *circ, routerinfo_t *exit)
 
   if (exit) { /* the circuit-builder pre-requested one */
     log_fn(LOG_INFO,"Using requested exit node '%s'", exit->nickname);
+    exit = extend_info_dup(exit);
   } else { /* we have to decide one */
-    exit = choose_good_exit_server(circ->purpose, rl,
+    routerinfo_t *router = choose_good_exit_server(circ->purpose, rl,
                                    state->need_uptime, state->need_capacity);
-    if (!exit) {
+    if (!router) {
       log_fn(LOG_WARN,"failed to choose an exit server");
       return -1;
     }
+    exit = extend_info_from_router(router);
   }
-  memcpy(state->chosen_exit_digest, exit->identity_digest, DIGEST_LEN);
-  state->chosen_exit_name = tor_strdup(exit->nickname);
+  state->chosen_exit = exit;
   return 0;
 }
 
@@ -1255,30 +1246,32 @@ onion_pick_cpath_exit(circuit_t *circ, routerinfo_t *exit)
  * the caller will do this if it wants to.
  */
 int
-circuit_append_new_exit(circuit_t *circ, routerinfo_t *exit)
+circuit_append_new_exit(circuit_t *circ, extend_info_t *info)
 {
-  tor_assert(exit);
+  cpath_build_state_t *state;
+  tor_assert(info);
   tor_assert(circ && CIRCUIT_IS_ORIGIN(circ));
-  tor_free(circ->build_state->chosen_exit_name);
-  circ->build_state->chosen_exit_name = tor_strdup(exit->nickname);
-  memcpy(circ->build_state->chosen_exit_digest, exit->identity_digest, DIGEST_LEN);
+
+  state = circ->build_state;
+  tor_assert(state);
+  if (state->chosen_exit)
+    extend_info_free(state->chosen_exit);
+  state->chosen_exit = extend_info_dup(info);
+
   ++circ->build_state->desired_path_len;
-  onion_append_hop(&circ->cpath, exit);
+  onion_append_hop(&circ->cpath, info);
   return 0;
 }
 
-/** Take the open circ originating here, give it a new exit destination
- * to <b>exit</b>, and get it to send the next extend cell. If you can't
- * send the extend cell, mark the circuit for close and return -1, else
- * return 0. */
+/** DOCDOC */
 int
-circuit_extend_to_new_exit(circuit_t *circ, routerinfo_t *exit)
+circuit_extend_to_new_exit(circuit_t *circ, extend_info_t *info)
 {
-  circuit_append_new_exit(circ, exit);
+  circuit_append_new_exit(circ, info);
   circ->state = CIRCUIT_STATE_BUILDING;
   if (circuit_send_next_onion_skin(circ)<0) {
     log_fn(LOG_WARN, "Couldn't extend circuit to new point '%s'.",
-           circ->build_state->chosen_exit_name);
+           info->nickname);
     circuit_mark_for_close(circ);
     return -1;
   }
@@ -1350,7 +1343,7 @@ choose_good_middle_server(uint8_t purpose,
 
   log_fn(LOG_DEBUG, "Contemplating intermediate hop: random choice.");
   excluded = smartlist_create();
-  if ((r = router_get_by_digest(state->chosen_exit_digest))) {
+  if ((r = build_state_get_exit_router(state))) {
     smartlist_add(excluded, r);
     routerlist_add_family(excluded, r);
   }
@@ -1359,7 +1352,7 @@ choose_good_middle_server(uint8_t purpose,
     routerlist_add_family(excluded, r);
   }
   for (i = 0, cpath = head; i < cur_len; ++i, cpath=cpath->next) {
-    if ((r = router_get_by_digest(cpath->identity_digest))) {
+    if ((r = router_get_by_digest(cpath->extend_info->identity_digest))) {
       smartlist_add(excluded, r);
       routerlist_add_family(excluded, r);
     }
@@ -1379,7 +1372,7 @@ choose_good_entry_server(cpath_build_state_t *state)
   smartlist_t *excluded = smartlist_create();
   or_options_t *options = get_options();
 
-  if ((r = router_get_by_digest(state->chosen_exit_digest))) {
+  if ((r = build_state_get_exit_router(state))) {
     smartlist_add(excluded, r);
     routerlist_add_family(excluded, r);
   }
@@ -1424,27 +1417,6 @@ onion_next_hop_in_cpath(crypt_path_t *cpath)
   return NULL;
 }
 
-/** Find the router corresponding to the first non-open hop in
- * circ->cpath. Make sure it's state closed. Return 1 if all
- * hops are open (the circuit is complete), 0 if we find a router
- * (and set it to *router), and -1 if we fail to lookup the router.
- */
-static int
-onion_next_router_in_cpath(circuit_t *circ, routerinfo_t **router) {
-  routerinfo_t *r;
-  crypt_path_t *hop = onion_next_hop_in_cpath(circ->cpath);
-  if (!hop) /* all hops are open */
-    return 1;
-  tor_assert(hop->state == CPATH_STATE_CLOSED);
-  r = router_get_by_digest(hop->identity_digest);
-  if (!r) {
-    log_fn(LOG_WARN,"Circuit intended to extend to a hop whose routerinfo we've lost. Cancelling circuit.");
-    return -1;
-  }
-  *router = r;
-  return 0;
-}
-
 /** Choose a suitable next hop in the cpath <b>head_ptr</b>,
  * based on <b>state</b>. Append the hop info to head_ptr.
  */
@@ -1454,7 +1426,7 @@ onion_extend_cpath(uint8_t purpose, crypt_path_t **head_ptr,
 {
   int cur_len;
   crypt_path_t *cpath;
-  routerinfo_t *choice;
+  extend_info_t *info = NULL;
   smartlist_t *excludednodes;
 
   tor_assert(head_ptr);
@@ -1481,23 +1453,29 @@ onion_extend_cpath(uint8_t purpose, crypt_path_t **head_ptr,
   add_nickname_list_to_smartlist(excludednodes,get_options()->ExcludeNodes,0);
 
   if (cur_len == state->desired_path_len - 1) { /* Picking last node */
-    choice = router_get_by_digest(state->chosen_exit_digest);
+    info = extend_info_dup(state->chosen_exit);
   } else if (cur_len == 0) { /* picking first node */
-    choice = choose_good_entry_server(state);
+    routerinfo_t *r = choose_good_entry_server(state);
+    if (r)
+      info = extend_info_from_router(r);
   } else {
-    choice = choose_good_middle_server(purpose, state, *head_ptr, cur_len);
+    routerinfo_t *r =
+      choose_good_middle_server(purpose, state, *head_ptr, cur_len);
+    if (r)
+      info = extend_info_from_router(r);
   }
 
   smartlist_free(excludednodes);
-  if (!choice) {
+  if (!info) {
     log_fn(LOG_WARN,"Failed to find node for hop %d of our path. Discarding this circuit.", cur_len);
     return -1;
   }
 
   log_fn(LOG_DEBUG,"Chose router %s for hop %d (exit is %s)",
-         choice->nickname, cur_len+1, state->chosen_exit_name);
+         info->nickname, cur_len+1, build_state_get_exit_nickname(state));
 
-  onion_append_hop(head_ptr, choice);
+  onion_append_hop(head_ptr, info);
+  extend_info_free(info);
   return 0;
 }
 
@@ -1505,7 +1483,7 @@ onion_extend_cpath(uint8_t purpose, crypt_path_t **head_ptr,
  * corresponding router <b>choice</b>, and append it to the
  * end of the cpath <b>head_ptr</b>. */
 static int
-onion_append_hop(crypt_path_t **head_ptr, routerinfo_t *choice)
+onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice)
 {
   crypt_path_t *hop = tor_malloc_zero(sizeof(crypt_path_t));
 
@@ -1515,9 +1493,7 @@ onion_append_hop(crypt_path_t **head_ptr, routerinfo_t *choice)
   hop->magic = CRYPT_PATH_MAGIC;
   hop->state = CPATH_STATE_CLOSED;
 
-  hop->port = choice->or_port;
-  hop->addr = choice->addr;
-  memcpy(hop->identity_digest, choice->identity_digest, DIGEST_LEN);
+  hop->extend_info = extend_info_dup(choice);
 
   hop->package_window = CIRCWINDOW_START;
   hop->deliver_window = CIRCWINDOW_START;
@@ -1525,3 +1501,67 @@ onion_append_hop(crypt_path_t **head_ptr, routerinfo_t *choice)
   return 0;
 }
 
+/** Allocate and return a new extend_info_t that can be used to build a
+ * circuit to or through the router <b>r</b>. */
+extend_info_t *
+extend_info_from_router(routerinfo_t *r)
+{
+  extend_info_t *info;
+  tor_assert(r);
+  info = tor_malloc_zero(sizeof(extend_info_t));
+  strlcpy(info->nickname, r->nickname, sizeof(info->nickname));
+  memcpy(info->identity_digest, r->identity_digest, DIGEST_LEN);
+  info->onion_key = crypto_pk_dup_key(r->onion_pkey);
+  info->addr = r->addr;
+  info->port = r->or_port;
+  return info;
+}
+
+/** Release storage held by an extend_info_t struct. */
+void
+extend_info_free(extend_info_t *info)
+{
+  tor_assert(info);
+  crypto_free_pk_env(info->onion_key);
+  tor_free(info);
+}
+
+/** Allocate and return a new extend_info_t with the same contents as
+ * <b>info</b>. */
+extend_info_t *
+extend_info_dup(extend_info_t *info)
+{
+  extend_info_t *newinfo;
+  tor_assert(info);
+  newinfo = tor_malloc(sizeof(extend_info_t));
+  memcpy(newinfo, info, sizeof(extend_info_t));
+  newinfo->onion_key = crypto_pk_dup_key(info->onion_key);
+  return newinfo;
+}
+
+/**
+ * Return the routerinfo_t for the chosen exit router in <b>state</b>.  If
+ * there is no chosen exit, or if we don't know the routerinfo_t for the
+ * chosen exit, return NULL.
+ */
+routerinfo_t *
+build_state_get_exit_router(cpath_build_state_t *state)
+{
+  if (!state || !state->chosen_exit)
+    return NULL;
+  return router_get_by_digest(state->chosen_exit->identity_digest);
+}
+
+/**
+ * Return the nickname for the chosen exit router in <b>state</b>.  If
+ * there is no chosen exit, or if we don't know the routerinfo_t for the
+ * chosen exit, return NULL.
+ */
+const char *
+build_state_get_exit_nickname(cpath_build_state_t *state)
+{
+  if (!state || !state->chosen_exit)
+    return NULL;
+  return state->chosen_exit->nickname;
+}
+
diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c
index 789781c936..9850ca67ce 100644
--- a/src/or/circuitlist.c
+++ b/src/or/circuitlist.c
@@ -24,7 +24,8 @@ static void circuit_free_cpath_node(crypt_path_t *victim);
 
 /********* END VARIABLES ************/
 
-/** DOCDOC This whole section */
+/** A map from OR connection and circuit ID to circuit.  (Lookup performance is
+ * very important here, since we need to do it every time a cell arrives.) */
 struct orconn_circid_circuit_map_t {
   RB_ENTRY(orconn_circid_circuit_map_t) node;
   connection_t *or_conn;
@@ -32,7 +33,9 @@ struct orconn_circid_circuit_map_t {
   circuit_t *circuit;
 };
 
-/** DOCDOC */
+/** helper for RB tree: compare the OR connection and circuit ID for a and b,
+ * and return less than, equal to, or greater than zero appropriately.
+ */
 static INLINE int
 compare_orconn_circid_entries(struct orconn_circid_circuit_map_t *a,
                               struct orconn_circid_circuit_map_t *b)
@@ -49,9 +52,15 @@ static RB_HEAD(orconn_circid_tree, orconn_circid_circuit_map_t) orconn_circid_ci
 RB_PROTOTYPE(orconn_circid_tree, orconn_circid_circuit_map_t, node, compare_orconn_circid_entries);
 RB_GENERATE(orconn_circid_tree, orconn_circid_circuit_map_t, node, compare_orconn_circid_entries);
 
+/** The most recently returned entyr from circuit_get_by_circid_orconn; used
+ * to improve performance when many cells arrive in a row from the same circuit.
+ */
+/* (We tried using splay trees, but round-robin turned out to make them suck.) */
 struct orconn_circid_circuit_map_t *_last_circid_orconn_ent = NULL;
 
-/** DOCDOC */
+/** Set the p_conn or n_conn field of a circuit <b>circ</b>, along with the
+ * corresponding circuit ID, and add the circuit as appropriate to the
+ * (orconn,id)-\>circuit map. */
 void
 circuit_set_circid_orconn(circuit_t *circ, uint16_t id,
                           connection_t *conn,
@@ -154,7 +163,7 @@ circuit_close_all_marked(void)
   }
 }
 
-/** DOCDOC **/
+/** Return the head of the global linked list of circuits. **/
 circuit_t *
 _circuit_get_global_list(void)
 {
@@ -227,7 +236,8 @@ circuit_free(circuit_t *circ)
   if (circ->p_digest)
     crypto_free_digest_env(circ->p_digest);
   if (circ->build_state) {
-    tor_free(circ->build_state->chosen_exit_name);
+    if (circ->build_state->chosen_exit)
+      extend_info_free(circ->build_state->chosen_exit);
     if (circ->build_state->pending_final_cpath)
       circuit_free_cpath_node(circ->build_state->pending_final_cpath);
   }
@@ -296,6 +306,9 @@ circuit_free_cpath_node(crypt_path_t *victim)
     crypto_free_digest_env(victim->b_digest);
   if (victim->dh_handshake_state)
     crypto_dh_free(victim->dh_handshake_state);
+  if (victim->extend_info)
+    extend_info_free(victim->extend_info);
+
   victim->magic = 0xDEADBEEFu;
   tor_free(victim);
 }
@@ -367,7 +380,7 @@ circuit_get_by_circid_orconn(uint16_t circ_id, connection_t *conn)
 
 }
 
-/** DOCDOC */
+/** Return the circuit that a given edge connection is using. */
 circuit_t *
 circuit_get_by_edge_conn(connection_t *conn)
 {
@@ -385,8 +398,9 @@ circuit_get_by_edge_conn(connection_t *conn)
   }
 
   circ = conn->on_circuit;
-  /* All this stuff here is sanity-checking. */
   tor_assert(circ->magic == CIRCUIT_MAGIC);
+#if 0
+  /* All this stuff here is sanity-checking. */
   for (tmpconn = circ->p_streams; tmpconn; tmpconn=tmpconn->next_stream)
     if (tmpconn == conn)
       return circ;
@@ -398,6 +412,8 @@ circuit_get_by_edge_conn(connection_t *conn)
       return circ;
 
   tor_assert(0);
+#endif
+  return circ;
 }
 
 /** Return a circ such that circ is attached to <b>conn</b>, either as
@@ -592,10 +608,14 @@ _circuit_mark_for_close(circuit_t *circ, int line, const char *file)
   }
   if (circ->purpose == CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT) {
     tor_assert(circ->state == CIRCUIT_STATE_OPEN);
+    tor_assert(circ->build_state->chosen_exit);
     /* treat this like getting a nack from it */
     log_fn(LOG_INFO,"Failed intro circ %s to %s (awaiting ack). Removing from descriptor.",
-           safe_str(circ->rend_query), safe_str(circ->build_state->chosen_exit_name));
-    rend_client_remove_intro_point(circ->build_state->chosen_exit_name, circ->rend_query);
+           safe_str(circ->rend_query),
+           safe_str(build_state_get_exit_nickname(circ->build_state)));
+    // XXXX NM
+    rend_client_remove_intro_point(circ->build_state->chosen_exit,
+                                   circ->rend_query);
   }
 
   if (circ->n_conn)
diff --git a/src/or/circuituse.c b/src/or/circuituse.c
index 3f19ae0090..55ae45994e 100644
--- a/src/or/circuituse.c
+++ b/src/or/circuituse.c
@@ -74,12 +74,7 @@ circuit_is_acceptable(circuit_t *circ,
    * circuit, it's the magical extra bob hop. so just check the nickname
    * of the one we meant to finish at.
    */
-  exitrouter = router_get_by_digest(circ->build_state->chosen_exit_digest);
-
-  if (!exitrouter) {
-    log_fn(LOG_INFO,"Skipping broken circ (exit router vanished)");
-    return 0; /* this circuit is screwed and doesn't know it yet */
-  }
+  exitrouter = build_state_get_exit_router(circ->build_state);
 
   if (!circ->build_state->need_uptime &&
       smartlist_string_num_isin(get_options()->LongLivedPorts,
@@ -87,6 +82,11 @@ circuit_is_acceptable(circuit_t *circ,
     return 0;
 
   if (purpose == CIRCUIT_PURPOSE_C_GENERAL) {
+    if (!exitrouter) {
+      log_fn(LOG_DEBUG,"Not considering circuit with unknown router.");
+      return 0; /* this circuit is screwed and doesn't know it yet,
+                 * or is a rendezvous circuit. */
+    }
     if (!connection_ap_can_use_exit(conn, exitrouter)) {
       /* can't exit from this router */
       return 0;
@@ -296,7 +296,7 @@ circuit_stream_is_being_handled(connection_t *conn, uint16_t port, int min)
         circ->purpose == CIRCUIT_PURPOSE_C_GENERAL &&
         (!circ->timestamp_dirty ||
          circ->timestamp_dirty + get_options()->MaxCircuitDirtiness < now)) {
-      exitrouter = router_get_by_digest(circ->build_state->chosen_exit_digest);
+      exitrouter = build_state_get_exit_router(circ->build_state);
       if (exitrouter &&
           (!need_uptime || circ->build_state->need_uptime)) {
         int ok;
@@ -682,7 +682,7 @@ circuit_build_failed(circuit_t *circ)
       /* Don't increment failure count, since Alice may have picked
        * the rendezvous point maliciously */
       log_fn(LOG_INFO,"Couldn't connect to Alice's chosen rend point %s (%s hop failed).",
-             circ->build_state->chosen_exit_name,
+             build_state_get_exit_nickname(circ->build_state),
              failed_at_last_hop?"last":"non-last");
       rend_service_relaunch_rendezvous(circ);
       break;
@@ -703,12 +703,34 @@ static int did_circs_fail_last_period = 0;
  * success. */
 #define MAX_CIRCUIT_FAILURES 5
 
-/** Launch a new circuit based on our arguments. */
+/** Launch a new circuit; see circuit_launch_by_extend_info for details on
+ * arguments. */
 circuit_t *
 circuit_launch_by_router(uint8_t purpose, routerinfo_t *exit,
                          int need_uptime, int need_capacity, int internal)
 {
   circuit_t *circ;
+  extend_info_t *info = NULL;
+  if (exit)
+    info = extend_info_from_router(exit);
+  circ = circuit_launch_by_extend_info(purpose, info, need_uptime, need_capacity,
+                                       internal);
+  if (info)
+    extend_info_free(info);
+  return circ;
+}
+
+/** Launch a new circuit with purpose <b>purpose</b> and exit node <b>info</b>
+ * (or NULL to select a random exit node).  If <b>need_uptime</b> is true,
+ * choose among routers with high uptime.  If <b>need_capacity</b> is true,
+ * choose among routers with high bandwidth.  If <b>internal</b> is true, the
+ * last hop need not be an exit node. Return the newly allocated circuit on
+ * success, or NULL on failure. */
+circuit_t *
+circuit_launch_by_extend_info(uint8_t purpose, extend_info_t *info,
+               int need_uptime, int need_capacity, int internal)
+{
+  circuit_t *circ;
 
   if (!has_fetched_directory) {
     log_fn(LOG_DEBUG,"Haven't fetched directory yet; canceling circuit launch.");
@@ -721,7 +743,7 @@ circuit_launch_by_router(uint8_t purpose, routerinfo_t *exit,
     if ((circ = circuit_get_clean_open(CIRCUIT_PURPOSE_C_GENERAL, need_uptime,
                                        need_capacity, internal))) {
       log_fn(LOG_INFO,"Cannibalizing circ '%s' for purpose %d",
-             circ->build_state->chosen_exit_name, purpose);
+             build_state_get_exit_nickname(circ->build_state), purpose);
       circ->purpose = purpose;
       /* reset the birth date of this circ, else expire_building
        * will see it and think it's been trying to build since it
@@ -740,8 +762,8 @@ circuit_launch_by_router(uint8_t purpose, routerinfo_t *exit,
         case CIRCUIT_PURPOSE_C_INTRODUCING:
         case CIRCUIT_PURPOSE_S_CONNECT_REND:
           /* need to add a new hop */
-          tor_assert(exit);
-          if (circuit_extend_to_new_exit(circ, exit) < 0)
+          tor_assert(info);
+          if (circuit_extend_to_new_exit(circ, info) < 0)
             return NULL;
           break;
         default:
@@ -762,11 +784,12 @@ circuit_launch_by_router(uint8_t purpose, routerinfo_t *exit,
   }
 
   /* try a circ. if it fails, circuit_mark_for_close will increment n_circuit_failures */
-  return circuit_establish_circuit(purpose, exit,
+  return circuit_establish_circuit(purpose, info,
                                    need_uptime, need_capacity, internal);
 }
 
-/** Launch a new circuit and return a pointer to it. Return NULL if you failed. */
+/** Launch a new circuit; see circuit_launch_by_extend_info for details on
+ * arguments. */
 circuit_t *
 circuit_launch_by_nickname(uint8_t purpose, const char *exit_nickname,
                            int need_uptime, int need_capacity, int internal)
@@ -867,30 +890,22 @@ circuit_get_open_circ_or_launch(connection_t *conn,
   /* is one already on the way? */
   circ = circuit_get_best(conn, 0, desired_circuit_purpose);
   if (!circ) {
-    char *exitname=NULL;
+    extend_info_t *extend_info=NULL;
     uint8_t new_circ_purpose;
     int is_internal;
 
     if (desired_circuit_purpose == CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT) {
       /* need to pick an intro point */
-try_an_intro_point:
-      exitname = rend_client_get_random_intro(conn->rend_query);
-      if (!exitname) {
+      extend_info = rend_client_get_random_intro(conn->rend_query);
+      if (!extend_info) {
         log_fn(LOG_INFO,"No intro points for '%s': refetching service descriptor.",
                safe_str(conn->rend_query));
         rend_client_refetch_renddesc(conn->rend_query);
         conn->state = AP_CONN_STATE_RENDDESC_WAIT;
         return 0;
       }
-      if (!router_get_by_nickname(exitname)) {
-        log_fn(LOG_NOTICE,"Advertised intro point '%s' is not recognized for hidserv address '%s'. Skipping over.",
-               exitname, safe_str(conn->rend_query));
-        rend_client_remove_intro_point(exitname, conn->rend_query);
-        tor_free(exitname);
-        goto try_an_intro_point;
-      }
       log_fn(LOG_INFO,"Chose %s as intro point for %s.",
-             exitname, safe_str(conn->rend_query));
+             extend_info->nickname, safe_str(conn->rend_query));
     }
 
     /* If we have specified a particular exit node for our
@@ -898,13 +913,13 @@ try_an_intro_point:
      */
     if (desired_circuit_purpose == CIRCUIT_PURPOSE_C_GENERAL) {
       if (conn->chosen_exit_name) {
-        exitname = tor_strdup(conn->chosen_exit_name);
-        if (!router_get_by_nickname(exitname)) {
+        routerinfo_t *r;
+        if (!(r = router_get_by_nickname(conn->chosen_exit_name))) {
           log_fn(LOG_NOTICE,"Requested exit point '%s' is not known. Closing.",
-                 exitname);
-          tor_free(exitname);
+                 conn->chosen_exit_name);
           return -1;
         }
+        extend_info = extend_info_from_router(r);
       }
     }
 
@@ -916,9 +931,10 @@ try_an_intro_point:
       new_circ_purpose = desired_circuit_purpose;
 
     is_internal = (new_circ_purpose != CIRCUIT_PURPOSE_C_GENERAL || is_resolve);
-    circ = circuit_launch_by_nickname(new_circ_purpose, exitname, need_uptime,
-                                      1, is_internal);
-    tor_free(exitname);
+    circ = circuit_launch_by_extend_info(
+              new_circ_purpose, extend_info, need_uptime, 1, is_internal);
+    if (extend_info)
+      extend_info_free(extend_info);
 
     if (desired_circuit_purpose != CIRCUIT_PURPOSE_C_GENERAL) {
       /* help predict this next time */
@@ -989,18 +1005,18 @@ consider_recording_trackhost(connection_t *conn, circuit_t *circ)
     }
   });
 
-  if (!found_needle)
+  if (!found_needle || !circ->build_state->chosen_exit)
     return;
 
   /* Add this exit/hostname pair to the addressmap. */
   len = strlen(conn->socks_request->address) + 1 /* '.' */ +
-        strlen(circ->build_state->chosen_exit_name) + 1 /* '.' */ +
+        strlen(circ->build_state->chosen_exit->nickname) + 1 /* '.' */ +
         strlen("exit") + 1 /* '\0' */;
   new_address = tor_malloc(len);
 
   tor_snprintf(new_address, len, "%s.%s.exit",
                conn->socks_request->address,
-               circ->build_state->chosen_exit_name);
+               circ->build_state->chosen_exit->nickname);
 
   addressmap_register(conn->socks_request->address, new_address,
                       time(NULL) + options->TrackHostExitsExpire);
diff --git a/src/or/connection_edge.c b/src/or/connection_edge.c
index e0f16e408e..73be5e936e 100644
--- a/src/or/connection_edge.c
+++ b/src/or/connection_edge.c
@@ -1051,7 +1051,7 @@ connection_ap_handshake_process_socks(connection_t *conn)
     log_fn(LOG_INFO,"Got a hidden service request for ID '%s'",
            safe_str(conn->rend_query));
     /* see if we already have it cached */
-    r = rend_cache_lookup_entry(conn->rend_query, &entry);
+    r = rend_cache_lookup_entry(conn->rend_query, -1, &entry);
     if (r<0) {
       log_fn(LOG_WARN,"Invalid service descriptor %s",
              safe_str(conn->rend_query));
diff --git a/src/or/control.c b/src/or/control.c
index 752a6d4dec..9d117b70b2 100644
--- a/src/or/control.c
+++ b/src/or/control.c
@@ -1402,7 +1402,9 @@ handle_control_extendcircuit(connection_t *conn, uint32_t len,
   /* now circ refers to something that is ready to be extended */
   SMARTLIST_FOREACH(routers, routerinfo_t *, r,
   {
-    circuit_append_new_exit(circ, r);
+    extend_info_t *info = extend_info_from_router(r);
+    circuit_append_new_exit(circ, info);
+    extend_info_free(info);
   });
 
   /* now that we've populated the cpath, start extending */
diff --git a/src/or/directory.c b/src/or/directory.c
index e3c8c7960e..247b60d351 100644
--- a/src/or/directory.c
+++ b/src/or/directory.c
@@ -435,6 +435,9 @@ directory_send_command(connection_t *conn, const char *platform,
 
       httpcommand = "GET";
       tor_snprintf(url, sizeof(url), "/tor/rendezvous/%s", resource);
+      /* XXXX011 Once directories understand versioned descriptors, switch to this
+       * URL in order to get the most recent version */
+      // tor_snprintf(url, sizeof(url), "/tor/rendezvous1/%s", resource);
 
       break;
     case DIR_PURPOSE_UPLOAD_RENDDESC:
@@ -1004,10 +1007,13 @@ directory_handle_command_get(connection_t *conn, char *headers,
     return 0;
   }
 
-  if (!strcmpstart(url,"/tor/rendezvous/")) {
+  if (!strcmpstart(url,"/tor/rendezvous/") ||
+      !strcmpstart(url,"/tor/rendezvous1/")) {
     /* rendezvous descriptor fetch */
     const char *descp;
     size_t desc_len;
+    int versioned = !strcmpstart(url,"/tor/rendezvous1/");
+    const char *query = url+strlen("/tor/rendezvous/")+(versioned?1:0);
 
     if (!authdir_mode(get_options())) {
       /* We don't hand out rend descs. In fact, it could be a security
@@ -1019,7 +1025,7 @@ directory_handle_command_get(connection_t *conn, char *headers,
       tor_free(url);
       return 0;
     }
-    switch (rend_cache_lookup_desc(url+strlen("/tor/rendezvous/"), &descp, &desc_len)) {
+    switch (rend_cache_lookup_desc(query, versioned?-1:0, &descp, &desc_len)) {
       case 1: /* valid */
         format_rfc1123_time(date, time(NULL));
         tor_snprintf(tmp, sizeof(tmp), "HTTP/1.0 200 OK\r\nDate: %s\r\nContent-Length: %d\r\nContent-Type: application/octet-stream\r\n\r\n",
diff --git a/src/or/onion.c b/src/or/onion.c
index da5594f22e..00d89c278e 100644
--- a/src/or/onion.c
+++ b/src/or/onion.c
@@ -153,6 +153,9 @@ onion_skin_create(crypto_pk_env_t *dest_router_key,
   crypto_dh_env_t *dh = NULL;
   int dhbytes, pkbytes;
 
+  tor_assert(dest_router_key);
+  tor_assert(handshake_state_out);
+  tor_assert(onion_skin_out);
   *handshake_state_out = NULL;
   memset(onion_skin_out, 0, ONIONSKIN_CHALLENGE_LEN);
 
diff --git a/src/or/or.h b/src/or/or.h
index 59ec3c9ed0..4084d3913d 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -664,7 +664,8 @@ struct connection_t {
   int done_receiving; /**< For half-open connections; not used currently. */
   char has_sent_end; /**< For debugging: set once we've set the stream end,
                         and check in circuit_about_to_close_connection(). */
-  struct circuit_t *on_circuit; /**< DOCDOC */
+  struct circuit_t *on_circuit; /**< The circuit (if any) that this edge
+                                 * connection is using. */
 
   /* Used only by AP connections */
   socks_request_t *socks_request; /**< SOCKS structure describing request (AP
@@ -766,6 +767,17 @@ typedef struct {
   char *signing_router;
 } routerlist_t;
 
+/** Informetation on router used when extending a circuit.  (We don't need a
+ * full routerinfo_t to extend: we only need addr:port:keyid to build an OR
+ * connection, and onion_key to create the onionskin.) */
+typedef struct extend_info_t {
+  char nickname[MAX_HEX_NICKNAME_LEN+1]; /**< This router's nickname for display*/
+  char identity_digest[DIGEST_LEN]; /**< Hash of this router's identity key */
+  uint32_t addr; /**< IP address in host order */
+  uint16_t port; /**< OR port */
+  crypto_pk_env_t *onion_key; /**< Current onionskin key */
+} extend_info_t;
+
 #define CRYPT_PATH_MAGIC 0x70127012u
 
 /** Holds accounting information for a single step in the layered encryption
@@ -793,12 +805,8 @@ struct crypt_path_t {
   /** Negotiated key material shared with the OR at this step. */
   char handshake_digest[DIGEST_LEN];/* KH in tor-spec.txt */
 
-  /** IP4 address of the OR at this step. */
-  uint32_t addr;
-  /** Port of the OR at this step. */
-  uint16_t port;
-  /** Identity key digest of the OR at this step. */
-  char identity_digest[DIGEST_LEN];
+  /** Information to extend to the OR at this step. */
+  extend_info_t *extend_info;
 
   /** Is the circuit built to this step?  Must be one of:
    *    - CPATH_STATE_CLOSED (The circuit has not been extended to this step)
@@ -836,10 +844,8 @@ typedef struct crypt_path_t crypt_path_t;
 typedef struct {
   /** Intended length of the final circuit. */
   int desired_path_len;
-  /** Nickname of planned exit node. */
-  char *chosen_exit_name;
-  /** Identity of planned exit node. */
-  char chosen_exit_digest[DIGEST_LEN];
+  /** How to extend to the planned exit node. */
+  extend_info_t *chosen_exit;
   /** Whether every node in the circ must have adequate uptime. */
   int need_uptime;
   /** Whether every node in the circ must have adequate capacity. */
@@ -1220,7 +1226,7 @@ void circuit_rep_hist_note_result(circuit_t *circ);
 void circuit_dump_by_conn(connection_t *conn, int severity);
 circuit_t *circuit_init(uint8_t purpose, int need_uptime,
                         int need_capacity, int internal);
-circuit_t *circuit_establish_circuit(uint8_t purpose, routerinfo_t *exit,
+circuit_t *circuit_establish_circuit(uint8_t purpose, extend_info_t *exit,
                                      int need_uptime, int need_capacity, int internal);
 int circuit_handle_first_hop(circuit_t *circ);
 void circuit_n_conn_done(connection_t *or_conn, int status);
@@ -1234,9 +1240,14 @@ int onionskin_answer(circuit_t *circ, uint8_t cell_type, char *payload, char *ke
 int circuit_all_predicted_ports_handled(time_t now, int *need_uptime,
                                         int *need_capacity);
 
-int circuit_append_new_exit(circuit_t *circ, routerinfo_t *exit);
-int circuit_extend_to_new_exit(circuit_t *circ, routerinfo_t *exit);
+int circuit_append_new_exit(circuit_t *circ, extend_info_t *info);
+int circuit_extend_to_new_exit(circuit_t *circ, extend_info_t *info);
 void onion_append_to_cpath(crypt_path_t **head_ptr, crypt_path_t *new_hop);
+extend_info_t *extend_info_from_router(routerinfo_t *r);
+extend_info_t *extend_info_dup(extend_info_t *info);
+void extend_info_free(extend_info_t *info);
+routerinfo_t *build_state_get_exit_router(cpath_build_state_t *state);
+const char *build_state_get_exit_nickname(cpath_build_state_t *state);
 
 /********************************* circuitlist.c ***********************/
 
@@ -1280,6 +1291,9 @@ void circuit_has_opened(circuit_t *circ);
 void circuit_build_failed(circuit_t *circ);
 circuit_t *circuit_launch_by_nickname(uint8_t purpose, const char *exit_nickname,
                                       int need_uptime, int need_capacity, int is_internal);
+circuit_t *circuit_launch_by_extend_info(uint8_t purpose,
+                                         extend_info_t *info,
+                                         int need_uptime, int need_capacity, int is_internal);
 circuit_t *circuit_launch_by_router(uint8_t purpose, routerinfo_t *exit,
                                     int need_uptime, int need_capacity, int is_internal);
 void circuit_reset_failure_count(int timeout);
@@ -1707,22 +1721,34 @@ void rend_client_introcirc_has_opened(circuit_t *circ);
 void rend_client_rendcirc_has_opened(circuit_t *circ);
 int rend_client_introduction_acked(circuit_t *circ, const char *request, size_t request_len);
 void rend_client_refetch_renddesc(const char *query);
-int rend_client_remove_intro_point(char *failed_intro, const char *query);
+int rend_client_remove_intro_point(extend_info_t *failed_intro, const char *query);
 int rend_client_rendezvous_acked(circuit_t *circ, const char *request, size_t request_len);
 int rend_client_receive_rendezvous(circuit_t *circ, const char *request, size_t request_len);
-void rend_client_desc_here(char *query);
+void rend_client_desc_here(const char *query);
 
-char *rend_client_get_random_intro(char *query);
+extend_info_t *rend_client_get_random_intro(const char *query);
 
 int rend_client_send_introduction(circuit_t *introcirc, circuit_t *rendcirc);
 
 /********************************* rendcommon.c ***************************/
 
+/** Information used to connect to a  hidden service. */
 typedef struct rend_service_descriptor_t {
-  crypto_pk_env_t *pk;
-  time_t timestamp;
-  int n_intro_points;
+  crypto_pk_env_t *pk; /**< This service's public key. */
+  int version; /**< 0 or 1 */
+  time_t timestamp; /**< Time when the descriptor was generated. */
+  uint16_t protocols; /**< Bitmask: which rendezvous protocols are supporeted?
+                       * (We allow bits '0', '1', and '2' to be set.) */
+  int n_intro_points; /**< Number of introduction points. */
+  /** Array of n_intro_points elements for this service's introduction points'
+   * nicknames.  Elements are removed from this array if introduction attempts
+   * fail. */
   char **intro_points;
+  /** Array of n_intro_points elements for this service's introduction points'
+   * extend_infos, or NULL if this descriptor is V0.  Elements are removed
+   * from this array if introduction attempts fail.  If this array is present,
+   * its elements correspond to the elements of intro_points. */
+  extend_info_t **intro_point_extend_info;
 } rend_service_descriptor_t;
 
 int rend_cmp_service_ids(const char *one, const char *two);
@@ -1732,6 +1758,7 @@ void rend_process_relay_cell(circuit_t *circ, int command, size_t length,
 
 void rend_service_descriptor_free(rend_service_descriptor_t *desc);
 int rend_encode_service_descriptor(rend_service_descriptor_t *desc,
+                                   int version,
                                    crypto_pk_env_t *key,
                                    char **str_out,
                                    size_t *len_out);
@@ -1740,7 +1767,7 @@ int rend_get_service_id(crypto_pk_env_t *pk, char *out);
 
 typedef struct rend_cache_entry_t {
   size_t len; /* Length of desc */
-  time_t received; /* When did we get the descriptor? */
+  time_t received; /* When was the descriptor received? */
   char *desc; /* Service descriptor */
   rend_service_descriptor_t *parsed; /* Parsed value of 'desc' */
 } rend_cache_entry_t;
@@ -1749,8 +1776,8 @@ void rend_cache_init(void);
 void rend_cache_clean(void);
 void rend_cache_free_all(void);
 int rend_valid_service_id(const char *query);
-int rend_cache_lookup_desc(const char *query, const char **desc, size_t *desc_len);
-int rend_cache_lookup_entry(const char *query, rend_cache_entry_t **entry_out);
+int rend_cache_lookup_desc(const char *query, int version, const char **desc, size_t *desc_len);
+int rend_cache_lookup_entry(const char *query, int version, rend_cache_entry_t **entry_out);
 int rend_cache_store(const char *desc, size_t desc_len);
 
 /********************************* rendservice.c ***************************/
diff --git a/src/or/relay.c b/src/or/relay.c
index dd424be107..ff77955110 100644
--- a/src/or/relay.c
+++ b/src/or/relay.c
@@ -633,11 +633,8 @@ connection_edge_process_end_not_open(
     log_fn(LOG_INFO,"Address '%s' refused due to '%s'. Considering retrying.",
            safe_str(conn->socks_request->address),
            connection_edge_end_reason_str(reason));
-    exitrouter = router_get_by_digest(circ->build_state->chosen_exit_digest);
-    if (!exitrouter) {
-      log_fn(LOG_INFO,"Skipping broken circ (exit router vanished)");
-      return 0; /* this circuit is screwed and doesn't know it yet */
-    }
+    exitrouter =
+      router_get_by_digest(circ->build_state->chosen_exit->identity_digest);
     switch (reason) {
       case END_STREAM_REASON_EXITPOLICY:
         if (rh->length >= 5) {
@@ -652,15 +649,15 @@ connection_edge_process_end_not_open(
                                     conn->chosen_exit_name);
         }
         /* check if he *ought* to have allowed it */
-        if (rh->length < 5 ||
-            (!tor_inet_aton(conn->socks_request->address, &in) &&
-             !conn->chosen_exit_name)) {
+        if (exitrouter &&
+            (rh->length < 5 ||
+             (!tor_inet_aton(conn->socks_request->address, &in) &&
+              !conn->chosen_exit_name))) {
           log_fn(LOG_NOTICE,"Exitrouter '%s' seems to be more restrictive than its exit policy. Not using this router as exit for now.", exitrouter->nickname);
           addr_policy_free(exitrouter->exit_policy);
           exitrouter->exit_policy =
             router_parse_addr_policy_from_string("reject *:*");
         }
-
         if (connection_ap_detach_retriable(conn, circ) >= 0)
           return 0;
         /* else, conn will get closed below */
@@ -683,10 +680,11 @@ connection_edge_process_end_not_open(
         break;
       case END_STREAM_REASON_HIBERNATING:
       case END_STREAM_REASON_RESOURCELIMIT:
-        addr_policy_free(exitrouter->exit_policy);
-        exitrouter->exit_policy =
-          router_parse_addr_policy_from_string("reject *:*");
-
+        if (exitrouter) {
+          addr_policy_free(exitrouter->exit_policy);
+          exitrouter->exit_policy =
+            router_parse_addr_policy_from_string("reject *:*");
+        }
         if (connection_ap_detach_retriable(conn, circ) >= 0)
           return 0;
         /* else, will close below */
diff --git a/src/or/rendclient.c b/src/or/rendclient.c
index bb64095ee4..e31179355f 100644
--- a/src/or/rendclient.c
+++ b/src/or/rendclient.c
@@ -58,15 +58,16 @@ rend_client_send_introduction(circuit_t *introcirc, circuit_t *rendcirc)
   size_t payload_len;
   int r;
   char payload[RELAY_PAYLOAD_SIZE];
-  char tmp[1+(MAX_HEX_NICKNAME_LEN+1)+REND_COOKIE_LEN+DH_KEY_LEN];
+  char tmp[RELAY_PAYLOAD_SIZE];
   rend_cache_entry_t *entry;
   crypt_path_t *cpath;
+  off_t dh_offset;
 
   tor_assert(introcirc->purpose == CIRCUIT_PURPOSE_C_INTRODUCING);
   tor_assert(rendcirc->purpose == CIRCUIT_PURPOSE_C_REND_READY);
   tor_assert(!rend_cmp_service_ids(introcirc->rend_query, rendcirc->rend_query));
 
-  if (rend_cache_lookup_entry(introcirc->rend_query, &entry) < 1) {
+  if (rend_cache_lookup_entry(introcirc->rend_query, -1, &entry) < 1) {
     log_fn(LOG_WARN,"query '%s' didn't have valid rend desc in cache. Failing.",
            safe_str(introcirc->rend_query));
     goto err;
@@ -95,22 +96,28 @@ rend_client_send_introduction(circuit_t *introcirc, circuit_t *rendcirc)
   }
 
   /* write the remaining items into tmp */
-#if 0
-  tmp[0] = 1; /* version 1 of the cell format */
-  /* nul pads */
-  strncpy(tmp+1, rendcirc->build_state->chosen_exit_name, (MAX_HEX_NICKNAME_LEN+1));
-  memcpy(tmp+1+MAX_HEX_NICKNAME_LEN+1, rendcirc->rend_cookie, REND_COOKIE_LEN);
-#else
-  strncpy(tmp, rendcirc->build_state->chosen_exit_name, (MAX_NICKNAME_LEN+1)); /* nul pads */
-  memcpy(tmp+MAX_NICKNAME_LEN+1, rendcirc->rend_cookie, REND_COOKIE_LEN);
-#endif
-  if (crypto_dh_get_public(cpath->dh_handshake_state,
-#if 0
-                           tmp+1+MAX_HEX_NICKNAME_LEN+1+REND_COOKIE_LEN,
-#else
-                           tmp+MAX_NICKNAME_LEN+1+REND_COOKIE_LEN,
-#endif
+  if (entry->parsed->protocols & (1<<2)) {
+    /* version 2 format */
+    extend_info_t *extend_info = rendcirc->build_state->chosen_exit;
+    int klen;
+    tmp[0] = 2; /* version 2 of the cell format */
+    /* nul pads */
+    set_uint32(tmp+1, htonl(extend_info->addr));
+    set_uint16(tmp+5, htons(extend_info->port));
+    memcpy(tmp+7, extend_info->identity_digest, DIGEST_LEN);
+    klen = crypto_pk_asn1_encode(extend_info->onion_key, tmp+7+DIGEST_LEN+2,
+                                 sizeof(tmp)-(7+DIGEST_LEN+2));
+    set_uint16(tmp+7+DIGEST_LEN, htons(klen));
+    memcpy(tmp+7+DIGEST_LEN+2+klen, rendcirc->rend_cookie, REND_COOKIE_LEN);
+    dh_offset = 7+DIGEST_LEN+2+klen+REND_COOKIE_LEN;
+  } else {
+    /* Version 0. */
+    strncpy(tmp, rendcirc->build_state->chosen_exit->nickname, (MAX_NICKNAME_LEN+1)); /* nul pads */
+    memcpy(tmp+MAX_NICKNAME_LEN+1, rendcirc->rend_cookie, REND_COOKIE_LEN);
+    dh_offset = MAX_NICKNAME_LEN+1+REND_COOKIE_LEN;
+  }
 
+  if (crypto_dh_get_public(cpath->dh_handshake_state, tmp+dh_offset,
                            DH_KEY_LEN)<0) {
     log_fn(LOG_WARN, "Couldn't extract g^x");
     goto err;
@@ -119,11 +126,7 @@ rend_client_send_introduction(circuit_t *introcirc, circuit_t *rendcirc)
   /*XXX maybe give crypto_pk_public_hybrid_encrypt a max_len arg,
    * to avoid buffer overflows? */
   r = crypto_pk_public_hybrid_encrypt(entry->parsed->pk, payload+DIGEST_LEN, tmp,
-#if 0
-                           1+MAX_HEX_NICKNAME_LEN+1+REND_COOKIE_LEN+DH_KEY_LEN,
-#else
-                           MAX_NICKNAME_LEN+1+REND_COOKIE_LEN+DH_KEY_LEN,
-#endif
+                                      dh_offset+DH_KEY_LEN,
                                       PK_PKCS1_OAEP_PADDING, 0);
   if (r<0) {
     log_fn(LOG_WARN,"hybrid pk encrypt failed.");
@@ -174,7 +177,6 @@ int
 rend_client_introduction_acked(circuit_t *circ,
                                const char *request, size_t request_len)
 {
-  char *nickname;
   circuit_t *rendcirc;
 
   if (circ->purpose != CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT) {
@@ -184,7 +186,8 @@ rend_client_introduction_acked(circuit_t *circ,
     return -1;
   }
 
-  tor_assert(circ->build_state->chosen_exit_name);
+  tor_assert(circ->build_state->chosen_exit);
+  tor_assert(circ->build_state->chosen_exit->nickname);
 
   if (request_len == 0) {
     /* It's an ACK; the introduction point relayed our introduction request. */
@@ -209,27 +212,26 @@ rend_client_introduction_acked(circuit_t *circ,
      * points. If any remain, extend to a new one and try again.
      * If none remain, refetch the service descriptor.
      */
-    if (rend_client_remove_intro_point(circ->build_state->chosen_exit_name,
+    if (rend_client_remove_intro_point(circ->build_state->chosen_exit,
                                        circ->rend_query) > 0) {
       /* There are introduction points left. re-extend the circuit to
        * another intro point and try again. */
-      routerinfo_t *r;
-      nickname = rend_client_get_random_intro(circ->rend_query);
-      tor_assert(nickname);
-      log_fn(LOG_INFO,"Got nack for %s from %s, extending to %s.",
-             safe_str(circ->rend_query),
-             circ->build_state->chosen_exit_name, nickname);
-      if (!(r = router_get_by_nickname(nickname))) {
-        log_fn(LOG_WARN, "Advertised intro point '%s' for %s is not known. Closing.",
-               nickname, safe_str(circ->rend_query));
-        tor_free(nickname);
+      extend_info_t *info;
+      int result;
+      info = rend_client_get_random_intro(circ->rend_query);
+      if (!info) {
+        log_fn(LOG_WARN, "No introduction points left for %s. Closing.",
+               safe_str(circ->rend_query));
         circuit_mark_for_close(circ);
         return -1;
       }
-      log_fn(LOG_INFO, "Chose new intro point %s for %s (circ %d)",
-             nickname, safe_str(circ->rend_query), circ->n_circ_id);
-      tor_free(nickname);
-      return circuit_extend_to_new_exit(circ, r);
+      log_fn(LOG_INFO,"Got nack for %s from %s, extending circ %d to %s.",
+             safe_str(circ->rend_query),
+             circ->build_state->chosen_exit->nickname, circ->n_circ_id,
+             info->nickname);
+      result = circuit_extend_to_new_exit(circ, info);
+      extend_info_free(info);
+      return result;
     }
   }
   return 0;
@@ -257,13 +259,13 @@ rend_client_refetch_renddesc(const char *query)
  * unrecognized, 1 if recognized and some intro points remain.
  */
 int
-rend_client_remove_intro_point(char *failed_intro, const char *query)
+rend_client_remove_intro_point(extend_info_t *failed_intro, const char *query)
 {
   int i, r;
   rend_cache_entry_t *ent;
   connection_t *conn;
 
-  r = rend_cache_lookup_entry(query, &ent);
+  r = rend_cache_lookup_entry(query, -1, &ent);
   if (r<0) {
     log_fn(LOG_WARN, "Malformed service ID '%s'", safe_str(query));
     return -1;
@@ -275,12 +277,31 @@ rend_client_remove_intro_point(char *failed_intro, const char *query)
     return 0;
   }
 
-  for (i=0; i < ent->parsed->n_intro_points; ++i) {
-    if (!strcasecmp(ent->parsed->intro_points[i], failed_intro)) {
-      tor_free(ent->parsed->intro_points[i]);
-      ent->parsed->intro_points[i] =
-        ent->parsed->intro_points[--ent->parsed->n_intro_points];
-      break;
+  if (ent->parsed->intro_point_extend_info) {
+    for (i=0; i < ent->parsed->n_intro_points; ++i) {
+      if (!memcmp(failed_intro->identity_digest,
+                  ent->parsed->intro_point_extend_info[i]->identity_digest,
+                  DIGEST_LEN)) {
+        tor_assert(!strcmp(ent->parsed->intro_points[i],
+                           ent->parsed->intro_point_extend_info[i]->nickname));
+        tor_free(ent->parsed->intro_points[i]);
+        extend_info_free(ent->parsed->intro_point_extend_info[i]);
+        --ent->parsed->n_intro_points;
+        ent->parsed->intro_points[i] =
+          ent->parsed->intro_points[ent->parsed->n_intro_points];
+        ent->parsed->intro_point_extend_info[i] =
+          ent->parsed->intro_point_extend_info[ent->parsed->n_intro_points];
+        break;
+      }
+    }
+  } else {
+    for (i=0; i < ent->parsed->n_intro_points; ++i) {
+      if (!strcasecmp(ent->parsed->intro_points[i], failed_intro->nickname)) {
+        tor_free(ent->parsed->intro_points[i]);
+        ent->parsed->intro_points[i] =
+          ent->parsed->intro_points[--ent->parsed->n_intro_points];
+        break;
+      }
     }
   }
 
@@ -385,7 +406,7 @@ rend_client_receive_rendezvous(circuit_t *circ, const char *request, size_t requ
  * else fail them.
  */
 void
-rend_client_desc_here(char *query)
+rend_client_desc_here(const char *query)
 {
   connection_t *conn;
   rend_cache_entry_t *entry;
@@ -393,7 +414,7 @@ rend_client_desc_here(char *query)
 
   while ((conn = connection_get_by_type_state_rendquery(CONN_TYPE_AP,
                                  AP_CONN_STATE_RENDDESC_WAIT, query))) {
-    if (rend_cache_lookup_entry(conn->rend_query, &entry) == 1 &&
+    if (rend_cache_lookup_entry(conn->rend_query, -1, &entry) == 1 &&
         entry->parsed->n_intro_points > 0) {
       /* either this fetch worked, or it failed but there was a
        * valid entry from before which we should reuse */
@@ -419,37 +440,42 @@ rend_client_desc_here(char *query)
   }
 }
 
-/** strdup a nickname for a random introduction
- * point of query. return NULL if error.
+/** Return a newly allocated extend_info_t* for a randomly chosen introduction
+ * point for the named hidden service.  Return NULL if all introduction points
+ * have been tried and failed.
  */
-char *
-rend_client_get_random_intro(char *query)
+extend_info_t *
+rend_client_get_random_intro(const char *query)
 {
   int i;
-  smartlist_t *sl;
-  char *choice;
-  char *nickname;
   rend_cache_entry_t *entry;
 
-  if (rend_cache_lookup_entry(query, &entry) < 1) {
+  if (rend_cache_lookup_entry(query, -1, &entry) < 1) {
     log_fn(LOG_WARN,"query '%s' didn't have valid rend desc in cache. Failing.",
            safe_str(query));
     return NULL;
   }
 
-  sl = smartlist_create();
+ again:
+  if (!entry->parsed->n_intro_points)
+    return NULL;
 
-  /* add the intro point nicknames */
-  for (i=0;i<entry->parsed->n_intro_points;i++)
-    smartlist_add(sl,entry->parsed->intro_points[i]);
+  i = crypto_pseudo_rand_int(entry->parsed->n_intro_points);
 
-  choice = smartlist_choose(sl);
-  if (!choice) {
-    smartlist_free(sl);
-    return NULL;
+  if (entry->parsed->intro_point_extend_info) {
+    return extend_info_dup(entry->parsed->intro_point_extend_info[i]);
+  } else {
+    /* add the intro point nicknames */
+    char *choice = entry->parsed->intro_points[i];
+    routerinfo_t *router = router_get_by_nickname(choice);
+    if (!router) {
+      log_fn(LOG_WARN, "Unknown router with nickname %s; trying another.",choice);
+      tor_free(choice);
+      entry->parsed->intro_points[i] =
+        entry->parsed->intro_points[--entry->parsed->n_intro_points];
+      goto again;
+    }
+    return extend_info_from_router(router);
   }
-  nickname = tor_strdup(choice);
-  smartlist_free(sl);
-  return nickname;
 }
 
diff --git a/src/or/rendcommon.c b/src/or/rendcommon.c
index ff9bdc9cef..2e3564de55 100644
--- a/src/or/rendcommon.c
+++ b/src/or/rendcommon.c
@@ -29,6 +29,13 @@ void rend_service_descriptor_free(rend_service_descriptor_t *desc)
     }
     tor_free(desc->intro_points);
   }
+  if (desc->intro_point_extend_info) {
+    for (i=0; i < desc->n_intro_points; ++i) {
+      if (desc->intro_point_extend_info[i])
+        extend_info_free(desc->intro_point_extend_info[i]);
+    }
+    tor_free(desc->intro_point_extend_info);
+  }
   tor_free(desc);
 }
 
@@ -38,38 +45,52 @@ void rend_service_descriptor_free(rend_service_descriptor_t *desc)
  */
 int
 rend_encode_service_descriptor(rend_service_descriptor_t *desc,
+                               int version,
                                crypto_pk_env_t *key,
                                char **str_out, size_t *len_out)
 {
-  char *buf, *cp, *ipoint;
+  char *cp;
+  char *end;
   int i;
-  size_t keylen, asn1len;
-  keylen = crypto_pk_keysize(desc->pk);
-  buf = tor_malloc(keylen*2); /* Too long, but that's okay. */
-  i = crypto_pk_asn1_encode(desc->pk, buf, keylen*2);
-  if (i<0) {
-    tor_free(buf);
-    return -1;
-  }
-  asn1len = i;
-  *len_out = 2 + asn1len + 4 + 2 + keylen;
-  for (i = 0; i < desc->n_intro_points; ++i) {
-    *len_out += strlen(desc->intro_points[i]) + 1;
+  size_t asn1len;
+  cp = *str_out = tor_malloc(PK_BYTES*2*(desc->n_intro_points+1)); /*Too long, but ok*/
+  end = cp + PK_BYTES*2*(desc->n_intro_points+1);
+  if (version) {
+    *(uint8_t*)cp = (uint8_t)0xff;
+    *(uint8_t*)(cp+1) = (uint8_t)version;
+    cp += 2;
   }
-  cp = *str_out = tor_malloc(*len_out);
+  asn1len = crypto_pk_asn1_encode(desc->pk, cp+2, end-(cp+2));
   set_uint16(cp, htons((uint16_t)asn1len));
-  cp += 2;
-  memcpy(cp, buf, asn1len);
-  tor_free(buf);
-  cp += asn1len;
+  cp += 2+asn1len;
   set_uint32(cp, htonl((uint32_t)desc->timestamp));
   cp += 4;
+  if (version == 1) {
+    set_uint16(cp, htons(desc->protocols));
+    cp += 2;
+  }
   set_uint16(cp, htons((uint16_t)desc->n_intro_points));
   cp += 2;
-  for (i=0; i < desc->n_intro_points; ++i) {
-    ipoint = (char*)desc->intro_points[i];
-    strlcpy(cp, ipoint, *len_out-(cp-*str_out));
-    cp += strlen(ipoint)+1;
+  if (version == 0) {
+    tor_assert(desc->intro_points);
+    for (i=0; i < desc->n_intro_points; ++i) {
+      char *ipoint = (char*)desc->intro_points[i];
+      strlcpy(cp, ipoint, *len_out-(cp-*str_out));
+      cp += strlen(ipoint)+1;
+    }
+  } else {
+    tor_assert(desc->intro_point_extend_info);
+    for (i=0; i < desc->n_intro_points; ++i) {
+      extend_info_t *info = desc->intro_point_extend_info[i];
+      int klen;
+      set_uint32(cp, htonl(info->addr));
+      set_uint16(cp+4, htons(info->port));
+      memcpy(cp+6, info->identity_digest, DIGEST_LEN);
+      klen = crypto_pk_asn1_encode(info->onion_key, cp+6+DIGEST_LEN+2,
+                                   (end-(cp+6+DIGEST_LEN+2)));
+      set_uint16(cp+6+DIGEST_LEN, htons((uint16_t)klen));
+      cp += 6+DIGEST_LEN+2+klen;
+    }
   }
   i = crypto_pk_private_sign_digest(key, cp, *str_out, cp-*str_out);
   if (i<0) {
@@ -77,7 +98,7 @@ rend_encode_service_descriptor(rend_service_descriptor_t *desc,
     return -1;
   }
   cp += i;
-  tor_assert(*len_out == (size_t)(cp-*str_out));
+  *len_out = (size_t)(cp-*str_out);
   return 0;
 }
 
@@ -92,10 +113,18 @@ rend_parse_service_descriptor(const char *str, size_t len)
   int i;
   size_t keylen, asn1len;
   const char *end, *cp, *eos;
+  int version = 0;
 
   result = tor_malloc_zero(sizeof(rend_service_descriptor_t));
   cp = str;
   end = str+len;
+  if (end-cp<2) goto truncated;
+  if (*(uint8_t*)cp == 0xff) {
+    result->version = version = *(uint8_t*)(cp+1);
+    cp += 2;
+  } else {
+    result->version = version = 0;
+  }
   if (end-cp < 2) goto truncated;
   asn1len = ntohs(get_uint16(cp));
   cp += 2;
@@ -106,16 +135,51 @@ rend_parse_service_descriptor(const char *str, size_t len)
   if (end-cp < 4) goto truncated;
   result->timestamp = (time_t) ntohl(get_uint32(cp));
   cp += 4;
+  if (version == 1) {
+    if (end-cp < 2) goto truncated;
+    result->protocols = ntohs(get_uint16(cp));
+    cp += 2;
+  } else {
+    result->protocols = 1;
+  }
   if (end-cp < 2) goto truncated;
   result->n_intro_points = ntohs(get_uint16(cp));
-  result->intro_points = tor_malloc_zero(sizeof(char*)*result->n_intro_points);
+
   cp += 2;
-  for (i=0;i<result->n_intro_points;++i) {
-    if (end-cp < 2) goto truncated;
-    eos = (const char *)memchr(cp,'\0',end-cp);
-    if (!eos) goto truncated;
-    result->intro_points[i] = tor_strdup(cp);
-    cp = eos+1;
+  if (version == 0) {
+    result->intro_points = tor_malloc_zero(sizeof(char*)*result->n_intro_points);
+    for (i=0;i<result->n_intro_points;++i) {
+      if (end-cp < 2) goto truncated;
+      eos = (const char *)memchr(cp,'\0',end-cp);
+      if (!eos) goto truncated;
+      result->intro_points[i] = tor_strdup(cp);
+      cp = eos+1;
+    }
+  } else {
+    result->intro_point_extend_info =
+      tor_malloc_zero(sizeof(extend_info_t*)*result->n_intro_points);
+    result->intro_points = tor_malloc_zero(sizeof(char*)*result->n_intro_points);
+    for (i=0;i<result->n_intro_points;++i) {
+      extend_info_t *info = result->intro_point_extend_info[i] =
+        tor_malloc_zero(sizeof(extend_info_t));
+      int klen;
+      if (end-cp < 8+DIGEST_LEN) goto truncated;
+      info->addr = ntohl(get_uint32(cp));
+      info->port = ntohs(get_uint16(cp+4));
+      memcpy(info->identity_digest, cp+6, DIGEST_LEN);
+      info->nickname[0] = '$';
+      base16_encode(info->nickname+1, sizeof(info->nickname)-1,
+                    info->identity_digest, DIGEST_LEN);
+      result->intro_points[i] = tor_strdup(info->nickname);
+      klen = ntohs(get_uint16(cp+6+DIGEST_LEN));
+      cp += 8+DIGEST_LEN;
+      if (end-cp < klen) goto truncated;
+      if (!(info->onion_key = crypto_pk_asn1_decode(cp,klen))) {
+        log_fn(LOG_WARN, "error decoding onion key for intro point");
+        goto error;
+      }
+      cp += klen;
+    }
   }
   keylen = crypto_pk_keysize(result->pk);
   tor_assert(end-cp >= 0);
@@ -227,16 +291,28 @@ rend_valid_service_id(const char *query)
   return 1;
 }
 
-/** If we have a cached rend_cache_entry_t for the service ID <b>query</b>, set
- * *<b>e</b> to that entry and return 1.  Else return 0.
+/** If we have a cached rend_cache_entry_t for the service ID <b>query</b>,
+ * set *<b>e</b> to that entry and return 1.  Else return 0.  If
+ * <b>version</b> is nonnegative, only return an entry in that descriptor
+ * format version. Otherwise (if <b>version</b> is negative), return the most
+ * recent format we have.
  */
 int
-rend_cache_lookup_entry(const char *query, rend_cache_entry_t **e)
+rend_cache_lookup_entry(const char *query, int version, rend_cache_entry_t **e)
 {
+  char key[REND_SERVICE_ID_LEN+2];
   tor_assert(rend_cache);
   if (!rend_valid_service_id(query))
     return -1;
-  *e = strmap_get_lc(rend_cache, query);
+  *e = NULL;
+  if (version != 0) {
+    tor_snprintf(key, sizeof(key), "1%s", query);
+    *e = strmap_get_lc(rend_cache, key);
+  }
+  if (!*e && version != 1) {
+    tor_snprintf(key, sizeof(key), "0%s", query);
+    *e = strmap_get_lc(rend_cache, key);
+  }
   if (!*e)
     return 0;
   return 1;
@@ -251,11 +327,11 @@ rend_cache_lookup_entry(const char *query, rend_cache_entry_t **e)
  * *desc.
  */
 int
-rend_cache_lookup_desc(const char *query, const char **desc, size_t *desc_len)
+rend_cache_lookup_desc(const char *query, int version, const char **desc, size_t *desc_len)
 {
   rend_cache_entry_t *e;
   int r;
-  r = rend_cache_lookup_entry(query,&e);
+  r = rend_cache_lookup_entry(query,version,&e);
   if (r <= 0) return r;
   *desc = e->desc;
   *desc_len = e->len;
@@ -275,6 +351,7 @@ rend_cache_store(const char *desc, size_t desc_len)
   rend_cache_entry_t *e;
   rend_service_descriptor_t *parsed;
   char query[REND_SERVICE_ID_LEN+1];
+  char key[REND_SERVICE_ID_LEN+2];
   time_t now;
 
   tor_assert(rend_cache);
@@ -288,6 +365,7 @@ rend_cache_store(const char *desc, size_t desc_len)
     rend_service_descriptor_free(parsed);
     return -1;
   }
+  tor_snprintf(key, sizeof(key), "%c%s", parsed->version?'1':'0', query);
   now = time(NULL);
   if (parsed->timestamp < now-REND_CACHE_MAX_AGE-REND_CACHE_MAX_SKEW) {
     log_fn(LOG_WARN,"Service descriptor %s is too old", safe_str(query));
@@ -300,9 +378,9 @@ rend_cache_store(const char *desc, size_t desc_len)
     rend_service_descriptor_free(parsed);
     return -1;
   }
-  e = (rend_cache_entry_t*) strmap_get_lc(rend_cache, query);
+  e = (rend_cache_entry_t*) strmap_get_lc(rend_cache, key);
   if (e && e->parsed->timestamp > parsed->timestamp) {
-    log_fn(LOG_INFO,"We already have a newer service descriptor %s with the same ID", safe_str(query));
+    log_fn(LOG_INFO,"We already have a newer service descriptor %s with the same ID and version", safe_str(query));
     rend_service_descriptor_free(parsed);
     return 0;
   }
@@ -314,7 +392,7 @@ rend_cache_store(const char *desc, size_t desc_len)
   }
   if (!e) {
     e = tor_malloc_zero(sizeof(rend_cache_entry_t));
-    strmap_set_lc(rend_cache, query, e);
+    strmap_set_lc(rend_cache, key, e);
   } else {
     rend_service_descriptor_free(e->parsed);
     tor_free(e->desc);
diff --git a/src/or/rendservice.c b/src/or/rendservice.c
index d2bf6c7ff2..6169b160fe 100644
--- a/src/or/rendservice.c
+++ b/src/or/rendservice.c
@@ -272,9 +272,12 @@ rend_service_update_descriptor(rend_service_t *service)
   d = service->desc = tor_malloc(sizeof(rend_service_descriptor_t));
   d->pk = crypto_pk_dup_key(service->private_key);
   d->timestamp = time(NULL);
+  d->version = 1;
   n = smartlist_len(service->intro_nodes);
   d->n_intro_points = 0;
-  d->intro_points = tor_malloc(sizeof(char*)*n);
+  d->intro_points = tor_malloc_zero(sizeof(char*)*n);
+  d->intro_point_extend_info = tor_malloc_zero(sizeof(extend_info_t*)*n);
+  d->protocols = (1<<2) | (1<<0); /* We support protocol 2 and protocol 0. */
   for (i=0; i < n; ++i) {
     router = router_get_by_nickname(smartlist_get(service->intro_nodes, i));
     if (!router) {
@@ -285,7 +288,10 @@ rend_service_update_descriptor(rend_service_t *service)
     circ = find_intro_circuit(router, service->pk_digest);
     if (circ && circ->purpose == CIRCUIT_PURPOSE_S_INTRO) {
       /* We have an entirely established intro circuit. */
-      d->intro_points[d->n_intro_points++] = tor_strdup(router->nickname);
+      d->intro_points[d->n_intro_points] = tor_strdup(router->nickname);
+      d->intro_point_extend_info[d->n_intro_points] =
+        extend_info_from_router(router);
+      d->n_intro_points++;
     }
   }
 }
@@ -379,7 +385,8 @@ rend_service_requires_uptime(rend_service_t *service) {
 int
 rend_service_introduce(circuit_t *circuit, const char *request, size_t request_len)
 {
-  char *ptr, *rp_nickname, *r_cookie;
+  char *ptr, *r_cookie;
+  extend_info_t *extend_info = NULL;
   char buf[RELAY_PAYLOAD_SIZE];
   char keys[DIGEST_LEN+CPATH_KEY_MATERIAL_LEN]; /* Holds KH, Df, Db, Kf, Kb */
   rend_service_t *service;
@@ -390,8 +397,6 @@ rend_service_introduce(circuit_t *circuit, const char *request, size_t request_l
   crypt_path_t *cpath = NULL;
   char serviceid[REND_SERVICE_ID_LEN+1];
   char hexcookie[9];
-  int version;
-  size_t nickname_field_len;
   int circ_needs_uptime;
 
   base32_encode(serviceid, REND_SERVICE_ID_LEN+1,
@@ -441,34 +446,73 @@ rend_service_introduce(circuit_t *circuit, const char *request, size_t request_l
     return -1;
   }
   len = r;
-  if (*buf == 1) {
-    rp_nickname = buf+1;
-    nickname_field_len = MAX_HEX_NICKNAME_LEN+1;
-    version = 1;
+  if (*buf == 2) {
+    /* Version 2 INTRODUCE2 cell. */
+    int klen;
+    extend_info = tor_malloc_zero(sizeof(extend_info_t));
+    extend_info->addr = ntohl(get_uint32(buf+1));
+    extend_info->port = ntohs(get_uint16(buf+5));
+    memcpy(extend_info->identity_digest, buf+7, DIGEST_LEN);
+    extend_info->nickname[0] = '$';
+    base16_encode(extend_info->nickname+1, sizeof(extend_info->nickname)-1,
+                  extend_info->identity_digest, DIGEST_LEN);
+
+    klen = ntohs(get_uint16(buf+7+DIGEST_LEN));
+    if (len != 7+DIGEST_LEN+2+klen+20+128) {
+      log_fn(LOG_WARN, "Bad length %u for version 2 INTRODUCE2 cell.", (int)len);
+      goto err;
+    }
+    extend_info->onion_key = crypto_pk_asn1_decode(buf+7+DIGEST_LEN+2, klen);
+    if (!extend_info->onion_key) {
+      log_fn(LOG_WARN, "Error decoding onion key in version 2 INTRODUCE2 cell.");
+      goto err;
+    }
+    ptr = buf+7+DIGEST_LEN+2+klen;
+    len -= 7+DIGEST_LEN+2+klen;
   } else {
-    nickname_field_len = MAX_NICKNAME_LEN+1;
-    rp_nickname = buf;
-    version = 0;
-  }
-  /* XXX when 0.0.9.x is obsolete, change this to reject version != 1. */
-  ptr=memchr(rp_nickname,0,nickname_field_len);
-  if (!ptr || ptr == rp_nickname) {
-    log_fn(LOG_WARN, "Couldn't find a null-padded nickname in INTRODUCE2 cell");
-    return -1;
-  }
-  if ((version == 0 && !is_legal_nickname(rp_nickname)) ||
-      (version == 1 && !is_legal_nickname_or_hexdigest(rp_nickname))) {
-    log_fn(LOG_WARN, "Bad nickname in INTRODUCE2 cell.");
-    return -1;
+    char *rp_nickname;
+    size_t nickname_field_len;
+    routerinfo_t *router;
+    int version;
+    if (*buf == 1) {
+      rp_nickname = buf+1;
+      nickname_field_len = MAX_HEX_NICKNAME_LEN+1;
+      version = 1;
+    } else {
+      nickname_field_len = MAX_NICKNAME_LEN+1;
+      rp_nickname = buf;
+      version = 0;
+    }
+    /* XXX when 0.1.0.x is obsolete, change this to reject version != 2. */
+    ptr=memchr(rp_nickname,0,nickname_field_len);
+    if (!ptr || ptr == rp_nickname) {
+      log_fn(LOG_WARN, "Couldn't find a null-padded nickname in INTRODUCE2 cell");
+      return -1;
+    }
+    if ((version == 0 && !is_legal_nickname(rp_nickname)) ||
+        (version == 1 && !is_legal_nickname_or_hexdigest(rp_nickname))) {
+      log_fn(LOG_WARN, "Bad nickname in INTRODUCE2 cell.");
+      return -1;
+    }
+    /* Okay, now we know that a nickname is at the start of the buffer. */
+    ptr = rp_nickname+nickname_field_len;
+    len -= nickname_field_len;
+    len -= rp_nickname - buf; /* also remove header space used by version, if any */
+    router = router_get_by_nickname(rp_nickname);
+    if (!router) {
+      log_fn(LOG_WARN, "Couldn't found router '%s' named in rendezvous cell.",
+             rp_nickname);
+      goto err;
+    }
+
+    extend_info = extend_info_from_router(router);
   }
-  /* Okay, now we know that a nickname is at the start of the buffer. */
-  ptr = rp_nickname+nickname_field_len;
-  len -= nickname_field_len;
-  len -= rp_nickname - buf; /* also remove header space used by version, if any */
+
   if (len != REND_COOKIE_LEN+DH_KEY_LEN) {
     log_fn(LOG_WARN, "Bad length %u for INTRODUCE2 cell.", (int)len);
     return -1;
   }
+
   r_cookie = ptr;
   base16_encode(hexcookie,9,r_cookie,4);
 
@@ -492,19 +536,20 @@ rend_service_introduce(circuit_t *circuit, const char *request, size_t request_l
   /* Launch a circuit to alice's chosen rendezvous point.
    */
   for (i=0;i<MAX_REND_FAILURES;i++) {
-    launched = circuit_launch_by_nickname(CIRCUIT_PURPOSE_S_CONNECT_REND, rp_nickname,
-                                          circ_needs_uptime, 1, 1);
+    launched = circuit_launch_by_extend_info(
+          CIRCUIT_PURPOSE_S_CONNECT_REND, extend_info, circ_needs_uptime, 1, 1);
+
     if (launched)
       break;
   }
   if (!launched) { /* give up */
     log_fn(LOG_WARN,"Giving up launching first hop of circuit to rendezvous point '%s' for service %s",
-           rp_nickname, serviceid);
+           extend_info->nickname, serviceid);
     goto err;
   }
   log_fn(LOG_INFO,
         "Accepted intro; launching circuit to '%s' (cookie %s) for service %s",
-         rp_nickname, hexcookie, serviceid);
+         extend_info->nickname, hexcookie, serviceid);
   tor_assert(launched->build_state);
   /* Fill in the circuit's state. */
   memcpy(launched->rend_pk_digest, circuit->rend_pk_digest,
@@ -522,11 +567,13 @@ rend_service_introduce(circuit_t *circuit, const char *request, size_t request_l
   if (circuit_init_cpath_crypto(cpath,keys+DIGEST_LEN,1)<0)
     goto err;
   memcpy(cpath->handshake_digest, keys, DIGEST_LEN);
+  if (extend_info) extend_info_free(extend_info);
 
   return 0;
  err:
   if (dh) crypto_dh_free(dh);
   if (launched) circuit_mark_for_close(launched);
+  if (extend_info) extend_info_free(extend_info);
   return -1;
 }
 
@@ -545,7 +592,7 @@ rend_service_relaunch_rendezvous(circuit_t *oldcirc)
       oldcirc->build_state->failure_count > MAX_REND_FAILURES ||
       oldcirc->build_state->expiry_time < time(NULL)) {
     log_fn(LOG_INFO,"Attempt to build circuit to %s for rendezvous has failed too many times or expired; giving up.",
-           oldcirc->build_state->chosen_exit_name);
+           oldcirc->build_state->chosen_exit->nickname);
     return;
   }
 
@@ -558,13 +605,13 @@ rend_service_relaunch_rendezvous(circuit_t *oldcirc)
   }
 
   log_fn(LOG_INFO,"Reattempting rendezvous circuit to %s",
-         oldstate->chosen_exit_name);
+         oldstate->chosen_exit->nickname);
 
-  newcirc = circuit_launch_by_nickname(CIRCUIT_PURPOSE_S_CONNECT_REND,
-                               oldstate->chosen_exit_name, 0, 1, 1);
+  newcirc = circuit_launch_by_extend_info(CIRCUIT_PURPOSE_S_CONNECT_REND,
+                               oldstate->chosen_exit, 0, 1, 1);
   if (!newcirc) {
     log_fn(LOG_WARN,"Couldn't relaunch rendezvous circuit to %s",
-           oldstate->chosen_exit_name);
+           oldstate->chosen_exit->nickname);
     return;
   }
   newstate = newcirc->build_state;
@@ -783,8 +830,8 @@ find_intro_circuit(routerinfo_t *router, const char *pk_digest)
   while ((circ = circuit_get_next_by_pk_and_purpose(circ,pk_digest,
                                                   CIRCUIT_PURPOSE_S_INTRO))) {
     tor_assert(circ->cpath);
-    if (circ->build_state->chosen_exit_name &&
-        !strcasecmp(circ->build_state->chosen_exit_name, router->nickname)) {
+    if (circ->build_state->chosen_exit->nickname &&
+        !strcasecmp(circ->build_state->chosen_exit->nickname, router->nickname)) {
       return circ;
     }
   }
@@ -793,8 +840,8 @@ find_intro_circuit(routerinfo_t *router, const char *pk_digest)
   while ((circ = circuit_get_next_by_pk_and_purpose(circ,pk_digest,
                                         CIRCUIT_PURPOSE_S_ESTABLISH_INTRO))) {
     tor_assert(circ->cpath);
-    if (circ->build_state->chosen_exit_name &&
-        !strcasecmp(circ->build_state->chosen_exit_name, router->nickname)) {
+    if (circ->build_state->chosen_exit->nickname &&
+        !strcasecmp(circ->build_state->chosen_exit->nickname, router->nickname)) {
       return circ;
     }
   }
@@ -805,7 +852,7 @@ find_intro_circuit(routerinfo_t *router, const char *pk_digest)
  * and upload it to all the dirservers.
  */
 static void
-upload_service_descriptor(rend_service_t *service)
+upload_service_descriptor(rend_service_t *service, int version)
 {
   char *desc;
   size_t desc_len;
@@ -813,6 +860,7 @@ upload_service_descriptor(rend_service_t *service)
   /* Update the descriptor. */
   rend_service_update_descriptor(service);
   if (rend_encode_service_descriptor(service->desc,
+                                     version,
                                      service->private_key,
                                      &desc, &desc_len)<0) {
     log_fn(LOG_WARN, "Couldn't encode service descriptor; not uploading");
@@ -963,7 +1011,10 @@ rend_consider_services_upload(time_t now)
       /* if it's time, or if the directory servers have a wrong service
        * descriptor and ours has been stable for 5 seconds, upload a
        * new one. */
-      upload_service_descriptor(service);
+      upload_service_descriptor(service, 0);
+      /* XXXX011 NM Once directories understand versioned descriptors, enable
+       * this. */
+      // upload_service_descriptor(service, 1);
       service->next_upload_time = now + rendpostperiod;
     }
   }
diff --git a/src/or/test.c b/src/or/test.c
index 6f1ee4f9f6..c365113df1 100644
--- a/src/or/test.c
+++ b/src/or/test.c
@@ -1400,30 +1400,89 @@ test_rend_fns(void)
   rend_service_descriptor_t *d1, *d2;
   char *encoded;
   size_t len;
-  crypto_pk_env_t *pk1;
+  crypto_pk_env_t *pk1, *pk2;
   time_t now;
   pk1 = crypto_new_pk_env();
-
+  pk2 = crypto_new_pk_env();
   test_assert(!crypto_pk_generate_key(pk1));
+  test_assert(!crypto_pk_generate_key(pk2));
+
+  /* Test unversioned descriptor */
   d1 = tor_malloc_zero(sizeof(rend_service_descriptor_t));
-  d1->pk = pk1;
+  d1->pk = crypto_pk_dup_key(pk1);
   now = time(NULL);
   d1->timestamp = now;
   d1->n_intro_points = 3;
+  d1->version = 0;
   d1->intro_points = tor_malloc(sizeof(char*)*3);
   d1->intro_points[0] = tor_strdup("tom");
   d1->intro_points[1] = tor_strdup("crow");
   d1->intro_points[2] = tor_strdup("joel");
-  test_assert(! rend_encode_service_descriptor(d1, pk1, &encoded, &len));
+  test_assert(! rend_encode_service_descriptor(d1, 0, pk1, &encoded, &len));
   d2 = rend_parse_service_descriptor(encoded, len);
   test_assert(d2);
 
   test_assert(!crypto_pk_cmp_keys(d1->pk, d2->pk));
   test_eq(d2->timestamp, now);
+  test_eq(d2->version, 0);
+  test_eq(d2->protocols, 1);
   test_eq(d2->n_intro_points, 3);
   test_streq(d2->intro_points[0], "tom");
   test_streq(d2->intro_points[1], "crow");
   test_streq(d2->intro_points[2], "joel");
+  test_eq(NULL, d2->intro_point_extend_info);
+
+  rend_service_descriptor_free(d1);
+  rend_service_descriptor_free(d2);
+  tor_free(encoded);
+
+  /* Test versioned descriptor. */
+  d1 = tor_malloc_zero(sizeof(rend_service_descriptor_t));
+  d1->pk = crypto_pk_dup_key(pk1);
+  now = time(NULL);
+  d1->timestamp = now;
+  d1->n_intro_points = 2;
+  d1->version = 1;
+  d1->protocols = 60;
+  d1->intro_points = tor_malloc(sizeof(char*)*2);
+  d1->intro_point_extend_info = tor_malloc(sizeof(extend_info_t*)*2);
+  d1->intro_points[0] = tor_strdup("tom");
+  d1->intro_points[1] = tor_strdup("crow");
+  d1->intro_point_extend_info[0] = tor_malloc_zero(sizeof(extend_info_t));
+  strcpy(d1->intro_point_extend_info[0]->nickname, "tom");
+  d1->intro_point_extend_info[0]->addr = 1234;
+  d1->intro_point_extend_info[0]->port = 4567;
+  d1->intro_point_extend_info[0]->onion_key = crypto_pk_dup_key(pk1);
+  memset(d1->intro_point_extend_info[0]->identity_digest, 'a', DIGEST_LEN);
+
+  d1->intro_point_extend_info[1] = tor_malloc_zero(sizeof(extend_info_t));
+  strcpy(d1->intro_point_extend_info[1]->nickname, "crow");
+  d1->intro_point_extend_info[1]->addr = 6060842;
+  d1->intro_point_extend_info[1]->port = 8000;
+  d1->intro_point_extend_info[1]->onion_key = crypto_pk_dup_key(pk2);
+  memset(d1->intro_point_extend_info[1]->identity_digest, 'b', DIGEST_LEN);
+
+  test_assert(! rend_encode_service_descriptor(d1, 1, pk1, &encoded, &len));
+  d2 = rend_parse_service_descriptor(encoded, len);
+  test_assert(d2);
+
+  test_assert(!crypto_pk_cmp_keys(d1->pk, d2->pk));
+  test_eq(d2->timestamp, now);
+  test_eq(d2->version, 1);
+  test_eq(d2->protocols, 60);
+  test_eq(d2->n_intro_points, 2);
+  test_streq(d2->intro_points[0], d2->intro_point_extend_info[0]->nickname);
+  test_streq(d2->intro_points[1], d2->intro_point_extend_info[1]->nickname);
+  test_eq(d2->intro_point_extend_info[0]->addr, 1234);
+  test_eq(d2->intro_point_extend_info[0]->port, 4567);
+  test_assert(!crypto_pk_cmp_keys(pk1,d2->intro_point_extend_info[0]->onion_key));
+  test_memeq(d2->intro_point_extend_info[0]->identity_digest,
+             d1->intro_point_extend_info[0]->identity_digest, DIGEST_LEN);
+  test_eq(d2->intro_point_extend_info[1]->addr, 6060842);
+  test_eq(d2->intro_point_extend_info[1]->port, 8000);
+
+  test_memeq(d2->intro_point_extend_info[1]->identity_digest,
+             d1->intro_point_extend_info[1]->identity_digest, DIGEST_LEN);
 
   test_eq(BAD_HOSTNAME, parse_extended_hostname(address1));
   test_eq(ONION_HOSTNAME, parse_extended_hostname(address2));
@@ -1432,6 +1491,8 @@ test_rend_fns(void)
 
   rend_service_descriptor_free(d1);
   rend_service_descriptor_free(d2);
+  crypto_free_pk_env(pk1);
+  crypto_free_pk_env(pk2);
 }
 
 int