Merge branch 'ed25519_lookup'

18 files changed, 345 insertions, 110 deletions

diff --git a/src/or/addressmap.c b/src/or/addressmap.c
index c92af38254..f278564e80 100644
--- a/src/or/addressmap.c
+++ b/src/or/addressmap.c
@@ -214,7 +214,7 @@ addressmap_clear_excluded_trackexithosts(const or_options_t *options)
       dot--;
     if (*dot == '.') dot++;
     nodename = tor_strndup(dot, len-5-(dot-target));;
-    node = node_get_by_nickname(nodename, 0);
+    node = node_get_by_nickname(nodename, NNF_NO_WARN_UNNAMED);
     tor_free(nodename);
     if (!node ||
         (allow_nodes && !routerset_contains_node(allow_nodes, node)) ||
diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index e5c6767d4a..279308afcb 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -290,14 +290,9 @@ circuit_list_path_impl(origin_circuit_t *circ, int verbose, int verbose_names)
         base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
       }
     } else { /* ! verbose_names */
-      node = node_get_by_id(id);
-      if (node && node_is_named(node)) {
-        elt = tor_strdup(node_get_nickname(node));
-      } else {
-        elt = tor_malloc(HEX_DIGEST_LEN+2);
-        elt[0] = '$';
-        base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
-      }
+      elt = tor_malloc(HEX_DIGEST_LEN+2);
+      elt[0] = '$';
+      base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
     }
     tor_assert(elt);
     if (verbose) {
diff --git a/src/or/circuituse.c b/src/or/circuituse.c
index c229c84d96..7545dea290 100644
--- a/src/or/circuituse.c
+++ b/src/or/circuituse.c
@@ -2121,7 +2121,7 @@ circuit_get_open_circ_or_launch(entry_connection_t *conn,
     } else {
       /* XXXX Duplicates checks in connection_ap_handshake_attach_circuit:
        * refactor into a single function. */
-      const node_t *node = node_get_by_nickname(conn->chosen_exit_name, 1);
+      const node_t *node = node_get_by_nickname(conn->chosen_exit_name, 0);
       int opt = conn->chosen_exit_optional;
       if (node && !connection_ap_can_use_exit(conn, node)) {
         log_fn(opt ? LOG_INFO : LOG_WARN, LD_APP,
@@ -2204,7 +2204,7 @@ circuit_get_open_circ_or_launch(entry_connection_t *conn,
       if (conn->chosen_exit_name) {
         const node_t *r;
         int opt = conn->chosen_exit_optional;
-        r = node_get_by_nickname(conn->chosen_exit_name, 1);
+        r = node_get_by_nickname(conn->chosen_exit_name, 0);
         if (r && node_has_descriptor(r)) {
           /* We might want to connect to an IPv6 bridge for loading
              descriptors so we use the preferred address rather than
@@ -2620,7 +2620,7 @@ connection_ap_handshake_attach_circuit(entry_connection_t *conn)
      * open to that exit. See what exit we meant, and whether we can use it.
      */
     if (conn->chosen_exit_name) {
-      const node_t *node = node_get_by_nickname(conn->chosen_exit_name, 1);
+      const node_t *node = node_get_by_nickname(conn->chosen_exit_name, 0);
       int opt = conn->chosen_exit_optional;
       if (!node && !want_onehop) {
         /* We ran into this warning when trying to extend a circuit to a
diff --git a/src/or/connection_edge.c b/src/or/connection_edge.c
index a9fdeee0ee..c5bd39d172 100644
--- a/src/or/connection_edge.c
+++ b/src/or/connection_edge.c
@@ -1086,7 +1086,8 @@ circuit_discard_optional_exit_enclaves(extend_info_t *info)
     if (!entry_conn->chosen_exit_optional &&
         !entry_conn->chosen_exit_retries)
       continue;
-    r1 = node_get_by_nickname(entry_conn->chosen_exit_name, 0);
+    r1 = node_get_by_nickname(entry_conn->chosen_exit_name,
+                              NNF_NO_WARN_UNNAMED);
     r2 = node_get_by_id(info->identity_digest);
     if (!r1 || !r2 || r1 != r2)
       continue;
@@ -1694,7 +1695,7 @@ connection_ap_handshake_rewrite_and_attach(entry_connection_t *conn,
       if (s[1] != '\0') {
         /* Looks like a real .exit one. */
         conn->chosen_exit_name = tor_strdup(s+1);
-        node = node_get_by_nickname(conn->chosen_exit_name, 1);
+        node = node_get_by_nickname(conn->chosen_exit_name, 0);
 
         if (exit_source == ADDRMAPSRC_TRACKEXIT) {
           /* We 5 tries before it expires the addressmap */
@@ -1715,7 +1716,7 @@ connection_ap_handshake_rewrite_and_attach(entry_connection_t *conn,
        * form that means (foo's address).foo.exit. */
 
       conn->chosen_exit_name = tor_strdup(socks->address);
-      node = node_get_by_nickname(conn->chosen_exit_name, 1);
+      node = node_get_by_nickname(conn->chosen_exit_name, 0);
       if (node) {
         *socks->address = 0;
         node_get_address_string(node, socks->address, sizeof(socks->address));
@@ -3819,7 +3820,7 @@ connection_ap_can_use_exit(const entry_connection_t *conn,
    */
   if (conn->chosen_exit_name) {
     const node_t *chosen_exit =
-      node_get_by_nickname(conn->chosen_exit_name, 1);
+      node_get_by_nickname(conn->chosen_exit_name, 0);
     if (!chosen_exit || tor_memneq(chosen_exit->identity,
                                exit_node->identity, DIGEST_LEN)) {
       /* doesn't match */
diff --git a/src/or/control.c b/src/or/control.c
index a0077b2a6c..c11193f397 100644
--- a/src/or/control.c
+++ b/src/or/control.c
@@ -1898,7 +1898,7 @@ getinfo_helper_dir(control_connection_t *control_conn,
   (void) control_conn;
   if (!strcmpstart(question, "desc/id/")) {
     const routerinfo_t *ri = NULL;
-    const node_t *node = node_get_by_hex_id(question+strlen("desc/id/"));
+    const node_t *node = node_get_by_hex_id(question+strlen("desc/id/"), 0);
     if (node)
       ri = node->ri;
     if (ri) {
@@ -1917,7 +1917,7 @@ getinfo_helper_dir(control_connection_t *control_conn,
     /* XXX Setting 'warn_if_unnamed' here is a bit silly -- the
      * warning goes to the user, not to the controller. */
     const node_t *node =
-      node_get_by_nickname(question+strlen("desc/name/"), 1);
+      node_get_by_nickname(question+strlen("desc/name/"), 0);
     if (node)
       ri = node->ri;
     if (ri) {
@@ -2003,7 +2003,7 @@ getinfo_helper_dir(control_connection_t *control_conn,
       return -1;
     }
   } else if (!strcmpstart(question, "md/id/")) {
-    const node_t *node = node_get_by_hex_id(question+strlen("md/id/"));
+    const node_t *node = node_get_by_hex_id(question+strlen("md/id/"), 0);
     const microdesc_t *md = NULL;
     if (node) md = node->md;
     if (md && md->body) {
@@ -2012,7 +2012,7 @@ getinfo_helper_dir(control_connection_t *control_conn,
   } else if (!strcmpstart(question, "md/name/")) {
     /* XXX Setting 'warn_if_unnamed' here is a bit silly -- the
      * warning goes to the user, not to the controller. */
-    const node_t *node = node_get_by_nickname(question+strlen("md/name/"), 1);
+    const node_t *node = node_get_by_nickname(question+strlen("md/name/"), 0);
     /* XXXX duplicated code */
     const microdesc_t *md = NULL;
     if (node) md = node->md;
@@ -2025,7 +2025,7 @@ getinfo_helper_dir(control_connection_t *control_conn,
   } else if (!strcmpstart(question, "desc-annotations/id/")) {
     const routerinfo_t *ri = NULL;
     const node_t *node =
-      node_get_by_hex_id(question+strlen("desc-annotations/id/"));
+      node_get_by_hex_id(question+strlen("desc-annotations/id/"), 0);
     if (node)
       ri = node->ri;
     if (ri) {
@@ -3406,7 +3406,7 @@ handle_control_extendcircuit(control_connection_t *conn, uint32_t len,
 
   nodes = smartlist_new();
   SMARTLIST_FOREACH_BEGIN(router_nicknames, const char *, n) {
-    const node_t *node = node_get_by_nickname(n, 1);
+    const node_t *node = node_get_by_nickname(n, 0);
     if (!node) {
       connection_printf_to_buf(conn, "552 No such router \"%s\"\r\n", n);
       goto done;
@@ -4173,7 +4173,7 @@ handle_control_hsfetch(control_connection_t *conn, uint32_t len,
       const char *server;
 
       server = arg + strlen(opt_server);
-      node = node_get_by_hex_id(server);
+      node = node_get_by_hex_id(server, 0);
       if (!node) {
         connection_printf_to_buf(conn, "552 Server \"%s\" not found\r\n",
                                  server);
@@ -4259,7 +4259,7 @@ handle_control_hspost(control_connection_t *conn,
     SMARTLIST_FOREACH_BEGIN(args, const char *, arg) {
       if (!strcasecmpstart(arg, opt_server)) {
         const char *server = arg + strlen(opt_server);
-        const node_t *node = node_get_by_hex_id(server);
+        const node_t *node = node_get_by_hex_id(server, 0);
 
         if (!node || !node->rs) {
           connection_printf_to_buf(conn, "552 Server \"%s\" not found\r\n",
diff --git a/src/or/networkstatus.c b/src/or/networkstatus.c
index e25a3d316a..76e8fe792a 100644
--- a/src/or/networkstatus.c
+++ b/src/or/networkstatus.c
@@ -794,21 +794,6 @@ router_get_consensus_status_by_id(const char *digest)
   return router_get_mutable_consensus_status_by_id(digest);
 }
 
-/** Given a nickname (possibly verbose, possibly a hexadecimal digest), return
- * the corresponding routerstatus_t, or NULL if none exists.  Warn the
- * user if <b>warn_if_unnamed</b> is set, and they have specified a router by
- * nickname, but the Named flag isn't set for that router. */
-const routerstatus_t *
-router_get_consensus_status_by_nickname(const char *nickname,
-                                        int warn_if_unnamed)
-{
-  const node_t *node = node_get_by_nickname(nickname, warn_if_unnamed);
-  if (node)
-    return node->rs;
-  else
-    return NULL;
-}
-
 /** Return the identity digest that's mapped to officially by
  * <b>nickname</b>. */
 const char *
@@ -2556,7 +2541,8 @@ getinfo_helper_networkstatus(control_connection_t *conn,
     }
     status = router_get_consensus_status_by_id(d);
   } else if (!strcmpstart(question, "ns/name/")) {
-    status = router_get_consensus_status_by_nickname(question+8, 0);
+    const node_t *n = node_get_by_nickname(question+8, 0);
+    status = n ? n->rs : NULL;
   } else if (!strcmpstart(question, "ns/purpose/")) {
     *answer = networkstatus_getinfo_by_purpose(question+11, time(NULL));
     return *answer ? 0 : -1;
diff --git a/src/or/networkstatus.h b/src/or/networkstatus.h
index f9320747d2..145be37d12 100644
--- a/src/or/networkstatus.h
+++ b/src/or/networkstatus.h
@@ -62,9 +62,6 @@ const routerstatus_t *router_get_consensus_status_by_descriptor_digest(
 MOCK_DECL(routerstatus_t *,
           router_get_mutable_consensus_status_by_descriptor_digest,
           (networkstatus_t *consensus, const char *digest));
-const routerstatus_t *router_get_consensus_status_by_nickname(
-                                   const char *nickname,
-                                   int warn_if_unnamed);
 const char *networkstatus_get_router_digest_by_nickname(const char *nickname);
 int networkstatus_nickname_is_unnamed(const char *nickname);
 int we_want_to_fetch_flavor(const or_options_t *options, int flavor);
diff --git a/src/or/nodelist.c b/src/or/nodelist.c
index 29ef835fba..00b8fb144f 100644
--- a/src/or/nodelist.c
+++ b/src/or/nodelist.c
@@ -94,7 +94,14 @@ typedef struct nodelist_t {
   smartlist_t *nodes;
   /* Hash table to map from node ID digest to node. */
   HT_HEAD(nodelist_map, node_t) nodes_by_id;
-
+  /* Hash table to map from node Ed25519 ID to node.
+   *
+   * Whenever a node's routerinfo or microdescriptor is about to change,
+   * you should remove it from this map with node_remove_from_ed25519_map().
+   * Whenever a node's routerinfo or microdescriptor has just chaned,
+   * you should add it to this map with node_add_to_ed25519_map().
+   */
+  HT_HEAD(nodelist_ed_map, node_t) nodes_by_ed_id;
 } nodelist_t;
 
 static inline unsigned int
@@ -113,6 +120,23 @@ HT_PROTOTYPE(nodelist_map, node_t, ht_ent, node_id_hash, node_id_eq)
 HT_GENERATE2(nodelist_map, node_t, ht_ent, node_id_hash, node_id_eq,
              0.6, tor_reallocarray_, tor_free_)
 
+static inline unsigned int
+node_ed_id_hash(const node_t *node)
+{
+  return (unsigned) siphash24g(node->ed25519_id.pubkey, ED25519_PUBKEY_LEN);
+}
+
+static inline unsigned int
+node_ed_id_eq(const node_t *node1, const node_t *node2)
+{
+  return ed25519_pubkey_eq(&node1->ed25519_id, &node2->ed25519_id);
+}
+
+HT_PROTOTYPE(nodelist_ed_map, node_t, ed_ht_ent, node_ed_id_hash,
+             node_ed_id_eq)
+HT_GENERATE2(nodelist_ed_map, node_t, ed_ht_ent, node_ed_id_hash,
+             node_ed_id_eq, 0.6, tor_reallocarray_, tor_free_)
+
 /** The global nodelist. */
 static nodelist_t *the_nodelist=NULL;
 
@@ -123,6 +147,7 @@ init_nodelist(void)
   if (PREDICT_UNLIKELY(the_nodelist == NULL)) {
     the_nodelist = tor_malloc_zero(sizeof(nodelist_t));
     HT_INIT(nodelist_map, &the_nodelist->nodes_by_id);
+    HT_INIT(nodelist_ed_map, &the_nodelist->nodes_by_ed_id);
     the_nodelist->nodes = smartlist_new();
   }
 }
@@ -140,6 +165,21 @@ node_get_mutable_by_id(const char *identity_digest)
   return node;
 }
 
+/** As node_get_by_ed25519_id, but returns a non-const pointer */
+node_t *
+node_get_mutable_by_ed25519_id(const ed25519_public_key_t *ed_id)
+{
+  node_t search, *node;
+  if (PREDICT_UNLIKELY(the_nodelist == NULL))
+    return NULL;
+  if (BUG(ed_id == NULL) || BUG(ed25519_public_key_is_zero(ed_id)))
+    return NULL;
+
+  memcpy(&search.ed25519_id, ed_id, sizeof(search.ed25519_id));
+  node = HT_FIND(nodelist_ed_map, &the_nodelist->nodes_by_ed_id, &search);
+  return node;
+}
+
 /** Return the node_t whose identity is <b>identity_digest</b>, or NULL
  * if no such node exists. */
 MOCK_IMPL(const node_t *,
@@ -148,6 +188,14 @@ node_get_by_id,(const char *identity_digest))
   return node_get_mutable_by_id(identity_digest);
 }
 
+/** Return the node_t whose ed25519 identity is <b>ed_id</b>, or NULL
+ * if no such node exists. */
+MOCK_IMPL(const node_t *,
+node_get_by_ed25519_id,(const ed25519_public_key_t *ed_id))
+{
+  return node_get_mutable_by_ed25519_id(ed_id);
+}
+
 /** Internal: return the node_t whose identity_digest is
  * <b>identity_digest</b>.  If none exists, create a new one, add it to the
  * nodelist, and return it.
@@ -175,6 +223,67 @@ node_get_or_create(const char *identity_digest)
   return node;
 }
 
+/** Remove <b>node</b> from the ed25519 map (if it present), and
+ * set its ed25519_id field to zero. */
+static int
+node_remove_from_ed25519_map(node_t *node)
+{
+  tor_assert(the_nodelist);
+  tor_assert(node);
+
+  if (ed25519_public_key_is_zero(&node->ed25519_id)) {
+    return 0;
+  }
+
+  int rv = 0;
+  node_t *search =
+    HT_FIND(nodelist_ed_map, &the_nodelist->nodes_by_ed_id, node);
+  if (BUG(search != node)) {
+    goto clear_and_return;
+  }
+
+  search = HT_REMOVE(nodelist_ed_map, &the_nodelist->nodes_by_ed_id, node);
+  tor_assert(search == node);
+  rv = 1;
+
+ clear_and_return:
+  memset(&node->ed25519_id, 0, sizeof(node->ed25519_id));
+  return rv;
+}
+
+/** If <b>node</b> has an ed25519 id, and it is not already in the ed25519 id
+ * map, set its ed25519_id field, and add it to the ed25519 map.
+ */
+static int
+node_add_to_ed25519_map(node_t *node)
+{
+  tor_assert(the_nodelist);
+  tor_assert(node);
+
+  if (! ed25519_public_key_is_zero(&node->ed25519_id)) {
+    return 0;
+  }
+
+  const ed25519_public_key_t *key = node_get_ed25519_id(node);
+  if (!key) {
+    return 0;
+  }
+
+  node_t *old;
+  memcpy(&node->ed25519_id, key, sizeof(node->ed25519_id));
+  old = HT_FIND(nodelist_ed_map, &the_nodelist->nodes_by_ed_id, node);
+  if (BUG(old)) {
+    /* XXXX order matters here, and this may mean that authorities aren't
+     * pinning. */
+    if (old != node)
+      memset(&node->ed25519_id, 0, sizeof(node->ed25519_id));
+    return 0;
+  }
+
+  HT_INSERT(nodelist_ed_map, &the_nodelist->nodes_by_ed_id, node);
+  return 1;
+}
+
 /* For a given <b>node</b> for the consensus <b>ns</b>, set the hsdir index
  * for the node, both current and next if possible. This can only fails if the
  * node_t ed25519 identity key can't be found which would be a bug. */
@@ -304,6 +413,8 @@ nodelist_set_routerinfo(routerinfo_t *ri, routerinfo_t **ri_old_out)
   id_digest = ri->cache_info.identity_digest;
   node = node_get_or_create(id_digest);
 
+  node_remove_from_ed25519_map(node);
+
   if (node->ri) {
     if (!routers_have_same_or_addrs(node->ri, ri)) {
       node_addrs_changed(node);
@@ -317,6 +428,8 @@ nodelist_set_routerinfo(routerinfo_t *ri, routerinfo_t **ri_old_out)
   }
   node->ri = ri;
 
+  node_add_to_ed25519_map(node);
+
   if (node->country == -1)
     node_set_country(node);
 
@@ -360,8 +473,10 @@ nodelist_add_microdesc(microdesc_t *md)
     return NULL;
   node = node_get_mutable_by_id(rs->identity_digest);
   if (node) {
+    node_remove_from_ed25519_map(node);
     if (node->md)
       node->md->held_by_nodes--;
+
     node->md = md;
     md->held_by_nodes++;
     /* Setting the HSDir index requires the ed25519 identity key which can
@@ -370,7 +485,9 @@ nodelist_add_microdesc(microdesc_t *md)
     if (rs->supports_v3_hsdir) {
       node_set_hsdir_index(node, ns);
     }
+    node_add_to_ed25519_map(node);
   }
+
   return node;
 }
 
@@ -398,12 +515,14 @@ nodelist_set_consensus(networkstatus_t *ns)
     if (ns->flavor == FLAV_MICRODESC) {
       if (node->md == NULL ||
           tor_memneq(node->md->digest,rs->descriptor_digest,DIGEST256_LEN)) {
+        node_remove_from_ed25519_map(node);
         if (node->md)
           node->md->held_by_nodes--;
         node->md = microdesc_cache_lookup_by_digest256(NULL,
                                                        rs->descriptor_digest);
         if (node->md)
           node->md->held_by_nodes++;
+        node_add_to_ed25519_map(node);
       }
     }
 
@@ -468,6 +587,9 @@ nodelist_remove_microdesc(const char *identity_digest, microdesc_t *md)
   if (node && node->md == md) {
     node->md = NULL;
     md->held_by_nodes--;
+    if (! node_get_ed25519_id(node)) {
+      node_remove_from_ed25519_map(node);
+    }
   }
 }
 
@@ -496,6 +618,7 @@ nodelist_drop_node(node_t *node, int remove_from_ht)
     tmp = HT_REMOVE(nodelist_map, &the_nodelist->nodes_by_id, node);
     tor_assert(tmp == node);
   }
+  node_remove_from_ed25519_map(node);
 
   idx = node->nodelist_idx;
   tor_assert(idx >= 0);
@@ -579,6 +702,7 @@ nodelist_free_all(void)
     return;
 
   HT_CLEAR(nodelist_map, &the_nodelist->nodes_by_id);
+  HT_CLEAR(nodelist_ed_map, &the_nodelist->nodes_by_ed_id);
   SMARTLIST_FOREACH_BEGIN(the_nodelist->nodes, node_t *, node) {
     node->nodelist_idx = -1;
     node_free(node);
@@ -643,9 +767,27 @@ nodelist_assert_ok(void)
     tor_assert(node_sl_idx == node->nodelist_idx);
   } SMARTLIST_FOREACH_END(node);
 
+  /* Every node listed with an ed25519 identity should be listed by that
+   * identity.
+   */
+  SMARTLIST_FOREACH_BEGIN(the_nodelist->nodes, node_t *, node) {
+    if (!ed25519_public_key_is_zero(&node->ed25519_id)) {
+      tor_assert(node == node_get_by_ed25519_id(&node->ed25519_id));
+    }
+  } SMARTLIST_FOREACH_END(node);
+
+  node_t **idx;
+  HT_FOREACH(idx, nodelist_ed_map, &the_nodelist->nodes_by_ed_id) {
+    node_t *node = *idx;
+    tor_assert(node == node_get_by_ed25519_id(&node->ed25519_id));
+  }
+
   tor_assert((long)smartlist_len(the_nodelist->nodes) ==
              (long)HT_SIZE(&the_nodelist->nodes_by_id));
 
+  tor_assert((long)smartlist_len(the_nodelist->nodes) >=
+             (long)HT_SIZE(&the_nodelist->nodes_by_ed_id));
+
   digestmap_free(dm, NULL);
 }
 
@@ -662,28 +804,23 @@ nodelist_get_list,(void))
 /** Given a hex-encoded nickname of the format DIGEST, $DIGEST, $DIGEST=name,
  * or $DIGEST~name, return the node with the matching identity digest and
  * nickname (if any).  Return NULL if no such node exists, or if <b>hex_id</b>
- * is not well-formed. */
+ * is not well-formed. DOCDOC flags */
 const node_t *
-node_get_by_hex_id(const char *hex_id)
+node_get_by_hex_id(const char *hex_id, unsigned flags)
 {
   char digest_buf[DIGEST_LEN];
   char nn_buf[MAX_NICKNAME_LEN+1];
   char nn_char='\0';
 
+  (void) flags; // XXXX
+
   if (hex_digest_nickname_decode(hex_id, digest_buf, &nn_char, nn_buf)==0) {
     const node_t *node = node_get_by_id(digest_buf);
     if (!node)
       return NULL;
-    if (nn_char) {
-      const char *real_name = node_get_nickname(node);
-      if (!real_name || strcasecmp(real_name, nn_buf))
-        return NULL;
-      if (nn_char == '=') {
-        const char *named_id =
-          networkstatus_get_router_digest_by_nickname(nn_buf);
-        if (!named_id || tor_memneq(named_id, digest_buf, DIGEST_LEN))
-          return NULL;
-      }
+    if (nn_char == '=') {
+      /* "=" indicates a Named relay, but there aren't any of those now. */
+      return NULL;
     }
     return node;
   }
@@ -692,19 +829,21 @@ node_get_by_hex_id(const char *hex_id)
 }
 
 /** Given a nickname (possibly verbose, possibly a hexadecimal digest), return
- * the corresponding node_t, or NULL if none exists.  Warn the user if
- * <b>warn_if_unnamed</b> is set, and they have specified a router by
- * nickname, but the Named flag isn't set for that router. */
+ * the corresponding node_t, or NULL if none exists. Warn the user if they
+ * have specified a router by nickname, unless the NNF_NO_WARN_UNNAMED bit is
+ * set in <b>flags</b>. */
 MOCK_IMPL(const node_t *,
-node_get_by_nickname,(const char *nickname, int warn_if_unnamed))
+node_get_by_nickname,(const char *nickname, unsigned flags))
 {
+  const int warn_if_unnamed = !(flags & NNF_NO_WARN_UNNAMED);
+
   if (!the_nodelist)
     return NULL;
 
   /* Handle these cases: DIGEST, $DIGEST, $DIGEST=name, $DIGEST~name. */
   {
     const node_t *node;
-    if ((node = node_get_by_hex_id(nickname)) != NULL)
+    if ((node = node_get_by_hex_id(nickname, flags)) != NULL)
       return node;
   }
 
@@ -779,22 +918,34 @@ node_get_by_nickname,(const char *nickname, int warn_if_unnamed))
 const ed25519_public_key_t *
 node_get_ed25519_id(const node_t *node)
 {
+  const ed25519_public_key_t *ri_pk = NULL;
+  const ed25519_public_key_t *md_pk = NULL;
   if (node->ri) {
     if (node->ri->cache_info.signing_key_cert) {
-      const ed25519_public_key_t *pk =
-        &node->ri->cache_info.signing_key_cert->signing_key;
-      if (BUG(ed25519_public_key_is_zero(pk)))
-        goto try_the_md;
-      return pk;
+      ri_pk = &node->ri->cache_info.signing_key_cert->signing_key;
+      if (BUG(ed25519_public_key_is_zero(ri_pk)))
+        ri_pk = NULL;
     }
   }
- try_the_md:
+
   if (node->md) {
     if (node->md->ed25519_identity_pkey) {
-      return node->md->ed25519_identity_pkey;
+      md_pk = node->md->ed25519_identity_pkey;
     }
   }
-  return NULL;
+
+  if (ri_pk && md_pk) {
+    if (ed25519_pubkey_eq(ri_pk, md_pk)) {
+      return ri_pk;
+    } else {
+      log_warn(LD_GENERAL, "Inconsistent ed25519 identities in the nodelist");
+      return NULL;
+    }
+  } else if (ri_pk) {
+    return ri_pk;
+  } else {
+    return md_pk;
+  }
 }
 
 /** Return true iff this node's Ed25519 identity matches <b>id</b>.
@@ -927,21 +1078,6 @@ node_get_nickname(const node_t *node)
     return NULL;
 }
 
-/** Return true iff the nickname of <b>node</b> is canonical, based on the
- * latest consensus. */
-int
-node_is_named(const node_t *node)
-{
-  const char *named_id;
-  const char *nickname = node_get_nickname(node);
-  if (!nickname)
-    return 0;
-  named_id = networkstatus_get_router_digest_by_nickname(nickname);
-  if (!named_id)
-    return 0;
-  return tor_memeq(named_id, node->identity, DIGEST_LEN);
-}
-
 /** Return true iff <b>node</b> appears to be a directory authority or
  * directory cache */
 int
@@ -989,13 +1125,12 @@ node_get_verbose_nickname(const node_t *node,
                           char *verbose_name_out)
 {
   const char *nickname = node_get_nickname(node);
-  int is_named = node_is_named(node);
   verbose_name_out[0] = '$';
   base16_encode(verbose_name_out+1, HEX_DIGEST_LEN+1, node->identity,
                 DIGEST_LEN);
   if (!nickname)
     return;
-  verbose_name_out[1+HEX_DIGEST_LEN] = is_named ? '=' : '~';
+  verbose_name_out[1+HEX_DIGEST_LEN] = '~';
   strlcpy(verbose_name_out+1+HEX_DIGEST_LEN+1, nickname, MAX_NICKNAME_LEN+1);
 }
 
@@ -1550,8 +1685,7 @@ node_nickname_matches(const node_t *node, const char *nickname)
     return 1;
   return hex_digest_nickname_matches(nickname,
                                      node->identity,
-                                     n,
-                                     node_is_named(node));
+                                     n);
 }
 
 /** Return true iff <b>node</b> is named by some nickname in <b>lst</b>. */
@@ -1653,7 +1787,7 @@ nodelist_add_node_and_family(smartlist_t *sl, const node_t *node)
     SMARTLIST_FOREACH_BEGIN(declared_family, const char *, name) {
       const node_t *node2;
       const smartlist_t *family2;
-      if (!(node2 = node_get_by_nickname(name, 0)))
+      if (!(node2 = node_get_by_nickname(name, NNF_NO_WARN_UNNAMED)))
         continue;
       if (!(family2 = node_get_declared_family(node2)))
         continue;
diff --git a/src/or/nodelist.h b/src/or/nodelist.h
index 318bf0e794..427e449ad9 100644
--- a/src/or/nodelist.h
+++ b/src/or/nodelist.h
@@ -18,7 +18,14 @@
 
 node_t *node_get_mutable_by_id(const char *identity_digest);
 MOCK_DECL(const node_t *, node_get_by_id, (const char *identity_digest));
-const node_t *node_get_by_hex_id(const char *identity_digest);
+node_t *node_get_mutable_by_ed25519_id(const ed25519_public_key_t *ed_id);
+MOCK_DECL(const node_t *, node_get_by_ed25519_id,
+          (const ed25519_public_key_t *ed_id));
+
+#define NNF_NO_WARN_UNNAMED (1u<<0)
+
+const node_t *node_get_by_hex_id(const char *identity_digest,
+                                 unsigned flags);
 node_t *nodelist_set_routerinfo(routerinfo_t *ri, routerinfo_t **ri_old_out);
 node_t *nodelist_add_microdesc(microdesc_t *md);
 void nodelist_set_consensus(networkstatus_t *ns);
@@ -34,12 +41,11 @@ void nodelist_free_all(void);
 void nodelist_assert_ok(void);
 
 MOCK_DECL(const node_t *, node_get_by_nickname,
-    (const char *nickname, int warn_if_unnamed));
+          (const char *nickname, unsigned flags));
 void node_get_verbose_nickname(const node_t *node,
                                char *verbose_name_out);
 void node_get_verbose_nickname_by_id(const char *id_digest,
                                 char *verbose_name_out);
-int node_is_named(const node_t *node);
 int node_is_dir(const node_t *node);
 int node_has_descriptor(const node_t *node);
 int node_get_purpose(const node_t *node);
diff --git a/src/or/or.h b/src/or/or.h
index 5a543b498c..161d80ed96 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -2459,6 +2459,8 @@ typedef struct node_t {
 
   /** Used to look up the node_t by its identity digest. */
   HT_ENTRY(node_t) ht_ent;
+  /** Used to look up the node_t by its ed25519 identity digest. */
+  HT_ENTRY(node_t) ed_ht_ent;
   /** Position of the node within the list of nodes */
   int nodelist_idx;
 
@@ -2466,6 +2468,13 @@ typedef struct node_t {
    * identity may exist at a time. */
   char identity[DIGEST_LEN];
 
+  /** The ed25519 identity of this node_t. This field is nonzero iff we
+   * currently have an ed25519 identity for this node in either md or ri,
+   * _and_ this node has been inserted to the ed25519-to-node map in the
+   * nodelist.
+   */
+  ed25519_public_key_t ed25519_id;
+
   microdesc_t *md;
   routerinfo_t *ri;
   routerstatus_t *rs;
diff --git a/src/or/rendservice.c b/src/or/rendservice.c
index 0017444b9a..01147c0072 100644
--- a/src/or/rendservice.c
+++ b/src/or/rendservice.c
@@ -2122,7 +2122,7 @@ find_rp_for_intro(const rend_intro_cell_t *intro,
   if (intro->version == 0 || intro->version == 1) {
     rp_nickname = (const char *)(intro->u.v0_v1.rp);
 
-    node = node_get_by_nickname(rp_nickname, 0);
+    node = node_get_by_nickname(rp_nickname, NNF_NO_WARN_UNNAMED);
     if (!node) {
       if (err_msg_out) {
         tor_asprintf(&err_msg,
diff --git a/src/or/router.c b/src/or/router.c
index c8e78659c0..665e95d3aa 100644
--- a/src/or/router.c
+++ b/src/or/router.c
@@ -2287,7 +2287,7 @@ router_build_fresh_descriptor(routerinfo_t **r, extrainfo_t **e)
        if (!strcasecmp(name, options->Nickname))
          continue; /* Don't list ourself, that's redundant */
        else
-         member = node_get_by_nickname(name, 1);
+         member = node_get_by_nickname(name, 0);
        if (!member) {
          int is_legal = is_legal_nickname_or_hexdigest(name);
          if (!smartlist_contains_string(warned_nonexistent_family, name) &&
diff --git a/src/or/routerlist.c b/src/or/routerlist.c
index da2dff600e..cc4c196240 100644
--- a/src/or/routerlist.c
+++ b/src/or/routerlist.c
@@ -2934,7 +2934,7 @@ hex_digest_nickname_decode(const char *hexdigest,
  * <b>hexdigest</b> is malformed, or it doesn't match.  */
 int
 hex_digest_nickname_matches(const char *hexdigest, const char *identity_digest,
-                            const char *nickname, int is_named)
+                            const char *nickname)
 {
   char digest[DIGEST_LEN];
   char nn_char='\0';
@@ -2943,13 +2943,15 @@ hex_digest_nickname_matches(const char *hexdigest, const char *identity_digest,
   if (hex_digest_nickname_decode(hexdigest, digest, &nn_char, nn_buf) == -1)
     return 0;
 
-  if (nn_char == '=' || nn_char == '~') {
-    if (!nickname)
+  if (nn_char == '=') {
+    return 0;
+  }
+
+  if (nn_char == '~') {
+    if (!nickname)     // XXX This seems wrong. -NM
       return 0;
     if (strcasecmp(nn_buf, nickname))
       return 0;
-    if (nn_char == '=' && !is_named)
-      return 0;
   }
 
   return tor_memeq(digest, identity_digest, DIGEST_LEN);
diff --git a/src/or/routerlist.h b/src/or/routerlist.h
index e0ed4e623a..931373f5cd 100644
--- a/src/or/routerlist.h
+++ b/src/or/routerlist.h
@@ -228,7 +228,7 @@ int hex_digest_nickname_decode(const char *hexdigest,
                                char *nickname_out);
 int hex_digest_nickname_matches(const char *hexdigest,
                                 const char *identity_digest,
-                                const char *nickname, int is_named);
+                                const char *nickname);
 
 #ifdef ROUTERLIST_PRIVATE
 STATIC int choose_array_element_by_weight(const uint64_t *entries,
diff --git a/src/or/routerset.c b/src/or/routerset.c
index 4906c6a51d..54e26ef943 100644
--- a/src/or/routerset.c
+++ b/src/or/routerset.c
@@ -362,7 +362,7 @@ routerset_get_all_nodes(smartlist_t *out, const routerset_t *routerset,
     /* No routers are specified by type; all are given by name or digest.
      * we can do a lookup in O(len(routerset)). */
     SMARTLIST_FOREACH(routerset->list, const char *, name, {
-        const node_t *node = node_get_by_nickname(name, 1);
+        const node_t *node = node_get_by_nickname(name, 0);
         if (node) {
           if (!running_only || node->is_running)
             if (!routerset_contains_node(excludeset, node))
diff --git a/src/test/test_hs_service.c b/src/test/test_hs_service.c
index 441c73e807..05ced17ff7 100644
--- a/src/test/test_hs_service.c
+++ b/src/test/test_hs_service.c
@@ -885,6 +885,7 @@ test_service_event(void *arg)
      * times we should retry a circuit. For this, we need to have a node_t
      * that matches the identity of this IP. */
     routerinfo_t ri;
+    memset(&ri, 0, sizeof(ri));
     ip = helper_create_service_ip();
     service_intro_point_add(service->desc_current->intro_points.map, ip);
     memset(ri.cache_info.identity_digest, 'A', DIGEST_LEN);
diff --git a/src/test/test_nodelist.c b/src/test/test_nodelist.c
index 256354415c..db2a8fd02c 100644
--- a/src/test/test_nodelist.c
+++ b/src/test/test_nodelist.c
@@ -7,7 +7,9 @@
  **/
 
 #include "or.h"
+#include "networkstatus.h"
 #include "nodelist.h"
+#include "torcert.h"
 #include "test.h"
 
 /** Test the case when node_get_by_id() returns NULL,
@@ -100,6 +102,107 @@ test_nodelist_node_is_dir(void *arg)
   return;
 }
 
+static networkstatus_t *dummy_ns = NULL;
+static networkstatus_t *
+mock_networkstatus_get_latest_consensus(void)
+{
+  return dummy_ns;
+}
+static networkstatus_t *
+mock_networkstatus_get_latest_consensus_by_flavor(consensus_flavor_t f)
+{
+  tor_assert(f == FLAV_MICRODESC);
+  return dummy_ns;
+}
+
+static void
+test_nodelist_ed_id(void *arg)
+{
+  routerstatus_t *rs[4];
+  microdesc_t *md[4];
+  routerinfo_t *ri[4];
+  networkstatus_t *ns;
+  int i;
+  (void)arg;
+
+  ns = tor_malloc_zero(sizeof(networkstatus_t));
+  ns->flavor = FLAV_MICRODESC;
+  ns->routerstatus_list = smartlist_new();
+  dummy_ns = ns;
+  MOCK(networkstatus_get_latest_consensus,
+       mock_networkstatus_get_latest_consensus);
+  MOCK(networkstatus_get_latest_consensus_by_flavor,
+       mock_networkstatus_get_latest_consensus_by_flavor);
+
+  /* Make a bunch of dummy objects that we can play around with.  Only set the
+     necessary fields */
+
+  for (i = 0; i < 4; ++i) {
+    rs[i] = tor_malloc_zero(sizeof(*rs[i]));
+    md[i] = tor_malloc_zero(sizeof(*md[i]));
+    ri[i] = tor_malloc_zero(sizeof(*ri[i]));
+
+    crypto_rand(md[i]->digest, sizeof(md[i]->digest));
+    md[i]->ed25519_identity_pkey = tor_malloc(sizeof(ed25519_public_key_t));
+    crypto_rand((char*)md[i]->ed25519_identity_pkey,
+                sizeof(ed25519_public_key_t));
+    crypto_rand(rs[i]->identity_digest, sizeof(rs[i]->identity_digest));
+    memcpy(ri[i]->cache_info.identity_digest, rs[i]->identity_digest,
+           DIGEST_LEN);
+    memcpy(rs[i]->descriptor_digest, md[i]->digest, DIGEST256_LEN);
+    ri[i]->cache_info.signing_key_cert = tor_malloc_zero(sizeof(tor_cert_t));
+    memcpy(&ri[i]->cache_info.signing_key_cert->signing_key,
+           md[i]->ed25519_identity_pkey, sizeof(ed25519_public_key_t));
+
+    if (i != 3)
+      smartlist_add(ns->routerstatus_list, rs[i]);
+  }
+
+  tt_int_op(0, OP_EQ, smartlist_len(nodelist_get_list()));
+
+  nodelist_set_consensus(ns);
+
+  tt_int_op(3, OP_EQ, smartlist_len(nodelist_get_list()));
+
+  /* No Ed25519 info yet, so nothing has an ED id. */
+  tt_ptr_op(NULL, OP_EQ, node_get_by_ed25519_id(md[0]->ed25519_identity_pkey));
+
+  /* Register the first one by md, then look it up. */
+  node_t *n = nodelist_add_microdesc(md[0]);
+  tt_ptr_op(n, OP_EQ, node_get_by_ed25519_id(md[0]->ed25519_identity_pkey));
+
+  /* Register the second by ri, then look it up. */
+  routerinfo_t *ri_old = NULL;
+  n = nodelist_set_routerinfo(ri[1], &ri_old);
+  tt_ptr_op(n, OP_EQ, node_get_by_ed25519_id(md[1]->ed25519_identity_pkey));
+  tt_ptr_op(ri_old, OP_EQ, NULL);
+
+  /* Register it by md too. */
+  node_t *n2 = nodelist_add_microdesc(md[1]);
+  tt_ptr_op(n2, OP_EQ, n);
+  tt_ptr_op(n, OP_EQ, node_get_by_ed25519_id(md[1]->ed25519_identity_pkey));
+
+  /* Register the 4th by ri only -- we never put it into the networkstatus,
+   * so it has to be independent */
+  n = nodelist_set_routerinfo(ri[3], &ri_old);
+  tt_ptr_op(n, OP_EQ, node_get_by_ed25519_id(md[3]->ed25519_identity_pkey));
+  tt_ptr_op(ri_old, OP_EQ, NULL);
+  tt_int_op(4, OP_EQ, smartlist_len(nodelist_get_list()));
+
+ done:
+  for (i = 0; i < 4; ++i) {
+    tor_free(rs[i]);
+    tor_free(md[i]->ed25519_identity_pkey);
+    tor_free(md[i]);
+    tor_free(ri[i]->cache_info.signing_key_cert);
+    tor_free(ri[i]);
+  }
+  smartlist_free(ns->routerstatus_list);
+  tor_free(ns);
+  UNMOCK(networkstatus_get_latest_consensus);
+  UNMOCK(networkstatus_get_latest_consensus_by_flavor);
+}
+
 #define NODE(name, flags) \
   { #name, test_nodelist_##name, (flags), NULL, NULL }
 
@@ -107,6 +210,7 @@ struct testcase_t nodelist_tests[] = {
   NODE(node_get_verbose_nickname_by_id_null_node, TT_FORK),
   NODE(node_get_verbose_nickname_not_named, TT_FORK),
   NODE(node_is_dir, TT_FORK),
+  NODE(ed_id, TT_FORK),
   END_OF_TESTCASES
 };
 
diff --git a/src/test/test_routerset.c b/src/test/test_routerset.c
index 7efd042ed5..c9c69911da 100644
--- a/src/test/test_routerset.c
+++ b/src/test/test_routerset.c
@@ -1602,7 +1602,7 @@ NS(test_main)(void *arg)
  */
 
 NS_DECL(const node_t *, node_get_by_nickname,
-    (const char *nickname, int warn_if_unused));
+    (const char *nickname, unsigned flags));
 static const char *NS(mock_nickname);
 
 static void
@@ -1632,11 +1632,11 @@ NS(test_main)(void *arg)
 }
 
 const node_t *
-NS(node_get_by_nickname)(const char *nickname, int warn_if_unused)
+NS(node_get_by_nickname)(const char *nickname, unsigned flags)
 {
   CALLED(node_get_by_nickname)++;
   tt_str_op(nickname, OP_EQ, NS(mock_nickname));
-  tt_int_op(warn_if_unused, OP_EQ, 1);
+  tt_uint_op(flags, OP_EQ, 0);
 
   done:
     return NULL;
@@ -1651,7 +1651,7 @@ NS(node_get_by_nickname)(const char *nickname, int warn_if_unused)
  */
 
 NS_DECL(const node_t *, node_get_by_nickname,
-    (const char *nickname, int warn_if_unused));
+    (const char *nickname, unsigned flags));
 static const char *NS(mock_nickname);
 static node_t NS(mock_node);
 
@@ -1683,11 +1683,11 @@ NS(test_main)(void *arg)
 }
 
 const node_t *
-NS(node_get_by_nickname)(const char *nickname, int warn_if_unused)
+NS(node_get_by_nickname)(const char *nickname, unsigned flags)
 {
   CALLED(node_get_by_nickname)++;
   tt_str_op(nickname, OP_EQ, NS(mock_nickname));
-  tt_int_op(warn_if_unused, OP_EQ, 1);
+  tt_int_op(flags, OP_EQ, 0);
 
   done:
     return &NS(mock_node);
@@ -1701,7 +1701,7 @@ NS(node_get_by_nickname)(const char *nickname, int warn_if_unused)
  */
 
 NS_DECL(const node_t *, node_get_by_nickname,
-    (const char *nickname, int warn_if_unused));
+    (const char *nickname, unsigned flags));
 static char *NS(mock_nickname);
 static node_t NS(mock_node);
 
@@ -1735,11 +1735,11 @@ NS(test_main)(void *arg)
 }
 
 const node_t *
-NS(node_get_by_nickname)(const char *nickname, int warn_if_unused)
+NS(node_get_by_nickname)(const char *nickname, unsigned flags)
 {
   CALLED(node_get_by_nickname)++;
   tt_str_op(nickname, OP_EQ, NS(mock_nickname));
-  tt_int_op(warn_if_unused, OP_EQ, 1);
+  tt_int_op(flags, OP_EQ, 0);
 
   done:
     return &NS(mock_node);