Merge branch 'maint-0.2.7' into release-0.2.7

13 files changed, 239 insertions, 45 deletions

diff --git a/changes/bug17668 b/changes/bug17668
new file mode 100644
index 0000000000..fa5c1c8081
--- /dev/null
+++ b/changes/bug17668
@@ -0,0 +1,5 @@
+  o Major bugfixes (voting):
+    - When collating votes by Ed25519 identities, authorities now
+      include a "NoEdConsensus" flag if the ed25519 value (or lack thereof)
+      for a server does not reflect the majority consensus. Related to bug
+      17668; bugfix on 0.2.7.2-alpha.
diff --git a/changes/bug17702 b/changes/bug17702
new file mode 100644
index 0000000000..4fda36f736
--- /dev/null
+++ b/changes/bug17702
@@ -0,0 +1,6 @@
+  o Major bugfixes:
+    - Actually enable Ed25519-based directory collation.
+      Previously, the code had been written, but some debugging code that had
+      accidentally been left in the codebase made it stay turned off.
+      Fixes bug 17702; bugfix on 0.2.7.2-alpha.
+
diff --git a/changes/bug18318_ed b/changes/bug18318_ed
new file mode 100644
index 0000000000..af39234d53
--- /dev/null
+++ b/changes/bug18318_ed
@@ -0,0 +1,7 @@
+  o Major bugfixes:
+    - When generating a vote with keypinning disabled, never include two
+      entries for the same ed25519 identity.  This bug was causing
+      authorities to generate votes that they could not parse when a router
+      violated key pinning by changing its RSA identity but keeping its
+      Ed25519 identity.  Fixes bug 17668; fixes part of bug 18318.  Bugfix on
+      0.2.7.2-alpha.
diff --git a/changes/bug18368 b/changes/bug18368
new file mode 100644
index 0000000000..17218d432f
--- /dev/null
+++ b/changes/bug18368
@@ -0,0 +1,5 @@
+  o Minor bugfixes:
+    - When logging information about an unparseable networkstatus vote or
+      consensus, do not say "vote" when we mean consensus. Fixes bug
+      18368; bugfix on 0.2.0.8-alpha.
+
diff --git a/src/or/dircollate.c b/src/or/dircollate.c
index 4c812c40e6..43cf27f489 100644
--- a/src/or/dircollate.c
+++ b/src/or/dircollate.c
@@ -17,20 +17,24 @@
 static void dircollator_collate_by_rsa(dircollator_t *dc);
 static void dircollator_collate_by_ed25519(dircollator_t *dc);
 
+/** Hashtable entry mapping a pair of digests (actually an ed25519 key and an
+ * RSA SHA1 digest) to an array of vote_routerstatus_t. */
 typedef struct ddmap_entry_s {
   HT_ENTRY(ddmap_entry_s) node;
   uint8_t d[DIGEST_LEN + DIGEST256_LEN];
+  /* The nth member of this array corresponds to the vote_routerstatus_t (if
+   * any) received for this digest pair from the nth voter. */
   vote_routerstatus_t *vrs_lst[FLEXIBLE_ARRAY_MEMBER];
 } ddmap_entry_t;
 
-double_digest_map_t *by_both_ids;
-
+/** Release all storage held by e. */
 static void
 ddmap_entry_free(ddmap_entry_t *e)
 {
   tor_free(e);
 }
 
+/** Return a new empty ddmap_entry, with <b>n_votes</b> elements in vrs_list. */
 static ddmap_entry_t *
 ddmap_entry_new(int n_votes)
 {
@@ -50,6 +54,8 @@ ddmap_entry_eq(const ddmap_entry_t *a, const ddmap_entry_t *b)
   return fast_memeq(a->d, b->d, sizeof(a->d));
 }
 
+/** Record the RSA identity of <b>ent</b> as <b>rsa_sha1</b>, and the
+ * ed25519 identity as <b>ed25519</b>. */
 static void
 ddmap_entry_set_digests(ddmap_entry_t *ent,
                         const uint8_t *rsa_sha1,
@@ -63,6 +69,10 @@ HT_PROTOTYPE(double_digest_map, ddmap_entry_s, node, ddmap_entry_hash,
              ddmap_entry_eq);
 HT_GENERATE2(double_digest_map, ddmap_entry_s, node, ddmap_entry_hash,
              ddmap_entry_eq, 0.6, tor_reallocarray, tor_free_);
+
+/** Helper: add a single vote_routerstatus_t <b>vrs</b> to the collator
+ * <b>dc</b>, indexing it by its RSA key digest, and by the 2-tuple of
+ * its RSA key digest and Ed25519 key.  */
 static void
 dircollator_add_routerstatus(dircollator_t *dc,
                              int vote_num,
@@ -71,6 +81,8 @@ dircollator_add_routerstatus(dircollator_t *dc,
 {
   const char *id = vrs->status.identity_digest;
 
+  vrs->ed25519_reflects_consensus = 0;
+
   (void) vote;
   vote_routerstatus_t **vrs_lst = digestmap_get(dc->by_rsa_sha1, id);
   if (NULL == vrs_lst) {
@@ -82,7 +94,7 @@ dircollator_add_routerstatus(dircollator_t *dc,
 
   const uint8_t *ed = vrs->ed25519_id;
 
-  if (tor_mem_is_zero((char*)ed, DIGEST256_LEN))
+  if (! vrs->has_ed25519_listing)
     return;
 
   ddmap_entry_t search, *found;
@@ -99,6 +111,8 @@ dircollator_add_routerstatus(dircollator_t *dc,
   vrs_lst[vote_num] = vrs;
 }
 
+/** Create and return a new dircollator object to use when collating
+ * <b>n_votes</b> out of a total of <b>n_authorities</b>. */
 dircollator_t *
 dircollator_new(int n_votes, int n_authorities)
 {
@@ -115,6 +129,7 @@ dircollator_new(int n_votes, int n_authorities)
   return dc;
 }
 
+/** Release all storage held by <b>dc</b>. */
 void
 dircollator_free(dircollator_t *dc)
 {
@@ -139,6 +154,10 @@ dircollator_free(dircollator_t *dc)
   tor_free(dc);
 }
 
+/** Add a single vote <b>v</b> to a dircollator <b>dc</b>.  This function must
+ * be called exactly once for each vote to be used in the consensus. It may
+ * only be called before dircollator_collate().
+ */
 void
 dircollator_add_vote(dircollator_t *dc, networkstatus_t *v)
 {
@@ -153,13 +172,16 @@ dircollator_add_vote(dircollator_t *dc, networkstatus_t *v)
   } SMARTLIST_FOREACH_END(vrs);
 }
 
+/** Sort the entries in <b>dc</b> according to <b>consensus_method</b>, so
+ * that the consensus process can iterate over them with
+ * dircollator_n_routers() and dircollator_get_votes_for_router(). */
 void
 dircollator_collate(dircollator_t *dc, int consensus_method)
 {
   tor_assert(!dc->is_collated);
   dc->all_rsa_sha1_lst = smartlist_new();
 
-  if (consensus_method < MIN_METHOD_FOR_ED25519_ID_VOTING + 10/*XXX*/)
+  if (consensus_method < MIN_METHOD_FOR_ED25519_ID_VOTING)
     dircollator_collate_by_rsa(dc);
   else
     dircollator_collate_by_ed25519(dc);
@@ -168,6 +190,15 @@ dircollator_collate(dircollator_t *dc, int consensus_method)
   dc->is_collated = 1;
 }
 
+/**
+ * Collation function for RSA-only consensuses: collate the votes for each
+ * entry in <b>dc</b> by their RSA keys.
+ *
+ * The rule is:
+ *    If an RSA identity key is listed by more than half of the authorities,
+ *    include that identity, and treat all descriptors with that RSA identity
+ *    as describing the same router.
+ */
 static void
 dircollator_collate_by_rsa(dircollator_t *dc)
 {
@@ -189,6 +220,20 @@ dircollator_collate_by_rsa(dircollator_t *dc)
   dc->by_collated_rsa_sha1 = dc->by_rsa_sha1;
 }
 
+/**
+ * Collation function for ed25519 consensuses: collate the votes for each
+ * entry in <b>dc</b> by ed25519 key and by RSA key.
+ *
+ * The rule is, approximately:
+ *    If a <ed,rsa> identity is listed by more than half of authorities,
+ *    include it.  And include all <rsa>-only votes about that node as
+ *    matching.
+ *
+ *    Otherwise, if an <*,rsa> or <rsa> identity is listed by more than
+ *    half of the authorities, and no <ed,rsa> pair for the same RSA key
+ *    has been already been included based on the rule above, include
+ *    that RSA identity.
+ */
 static void
 dircollator_collate_by_ed25519(dircollator_t *dc)
 {
@@ -197,6 +242,7 @@ dircollator_collate_by_ed25519(dircollator_t *dc)
 
   ddmap_entry_t **iter;
 
+  /* Go over all <ed,rsa> pairs */
   HT_FOREACH(iter, double_digest_map, &dc->by_both_ids) {
     ddmap_entry_t *ent = *iter;
     int n = 0, i;
@@ -205,9 +251,13 @@ dircollator_collate_by_ed25519(dircollator_t *dc)
         ++n;
     }
 
+    /* If not enough authorties listed this exact <ed,rsa> pair,
+     * don't include it. */
     if (n <= total_authorities / 2)
       continue;
 
+    /* Now consider whether there are any other entries with the same
+     * RSA key (but with possibly different or missing ed value). */
     vote_routerstatus_t **vrs_lst2 = digestmap_get(dc->by_rsa_sha1,
                                                    (char*)ent->d);
     tor_assert(vrs_lst2);
@@ -220,13 +270,17 @@ dircollator_collate_by_ed25519(dircollator_t *dc)
       }
     }
 
+    /* Record that we have seen this RSA digest. */
     digestmap_set(rsa_digests, (char*)ent->d, ent->vrs_lst);
     smartlist_add(dc->all_rsa_sha1_lst, ent->d);
   }
 
+  /* Now look over all entries with an RSA digest, looking for RSA digests
+   * we didn't put in yet.
+   */
   DIGESTMAP_FOREACH(dc->by_rsa_sha1, k, vote_routerstatus_t **, vrs_lst) {
     if (digestmap_get(rsa_digests, k) != NULL)
-      continue;
+      continue; /* We already included this RSA digest */
 
     int n = 0, i;
     for (i = 0; i < dc->n_votes; ++i) {
@@ -235,7 +289,7 @@ dircollator_collate_by_ed25519(dircollator_t *dc)
     }
 
     if (n <= total_authorities / 2)
-      continue;
+      continue; /* Not enough votes */
 
     digestmap_set(rsa_digests, k, vrs_lst);
     smartlist_add(dc->all_rsa_sha1_lst, (char *)k);
@@ -244,15 +298,27 @@ dircollator_collate_by_ed25519(dircollator_t *dc)
   dc->by_collated_rsa_sha1 = rsa_digests;
 }
 
+/** Return the total number of collated router entries.  This function may
+ * only be called after dircollator_collate. */
 int
 dircollator_n_routers(dircollator_t *dc)
 {
+  tor_assert(dc->is_collated);
   return smartlist_len(dc->all_rsa_sha1_lst);
 }
 
+/** Return an array of vote_routerstatus_t entries for the <b>idx</b>th router
+ * in the collation order.  Each array contains n_votes elements, where the
+ * nth element of the array is the vote_routerstatus_t from the nth voter for
+ * this identity (or NULL if there is no such entry).
+ *
+ * The maximum value for <b>idx</b> is dircollator_n_routers().
+ *
+ * This function may only be called after dircollator_collate. */
 vote_routerstatus_t **
 dircollator_get_votes_for_router(dircollator_t *dc, int idx)
 {
+  tor_assert(dc->is_collated);
   tor_assert(idx < smartlist_len(dc->all_rsa_sha1_lst));
   return digestmap_get(dc->by_collated_rsa_sha1,
                        smartlist_get(dc->all_rsa_sha1_lst, idx));
diff --git a/src/or/dircollate.h b/src/or/dircollate.h
index cd1e8ac96d..d7f17ef757 100644
--- a/src/or/dircollate.h
+++ b/src/or/dircollate.h
@@ -5,8 +5,8 @@
 /* See LICENSE for licensing information */
 
 /**
- * \file dirvote.h
- * \brief Header file for dirvote.c.
+ * \file dircollate.h
+ * \brief Header file for dircollate.c.
  **/
 
 #ifndef TOR_DIRCOLLATE_H
@@ -30,18 +30,36 @@ vote_routerstatus_t **dircollator_get_votes_for_router(dircollator_t *dc,
 #ifdef DIRCOLLATE_PRIVATE
 struct ddmap_entry_s;
 typedef HT_HEAD(double_digest_map, ddmap_entry_s) double_digest_map_t;
+/** A dircollator keeps track of all the routerstatus entries in a
+ * set of networkstatus votes, and matches them by an appropriate rule. */
 struct dircollator_s {
-  /**DOCDOC */
+  /** True iff we have run the collation algorithm. */
   int is_collated;
+  /** The total number of votes that we received. */
   int n_votes;
+  /** The total number of authorities we acknowledge. */
   int n_authorities;
 
+  /** The index which the next vote to be added to this collator should
+   * receive. */
   int next_vote_num;
+  /** Map from RSA-SHA1 identity digest to an array of <b>n_votes</b>
+   * vote_routerstatus_t* pointers, such that the i'th member of the
+   * array is the i'th vote's entry for that RSA-SHA1 ID.*/
   digestmap_t *by_rsa_sha1;
+  /** Map from <ed, RSA-SHA1> pair to an array similar to that used in
+   * by_rsa_sha1 above. We include <NULL,RSA-SHA1> entries for votes that
+   * say that there is no Ed key. */
   struct double_digest_map by_both_ids;
 
+  /** One of two outputs created by collation: a map from RSA-SHA1
+   * identity digest to an array of the vote_routerstatus_t objects.  Entries
+   * only exist in this map for identities that we should include in the
+   * consensus. */
   digestmap_t *by_collated_rsa_sha1;
 
+  /** One of two outputs created by collation: a sorted array of RSA-SHA1
+   * identity digests .*/
   smartlist_t *all_rsa_sha1_lst;
 };
 #endif
diff --git a/src/or/dirserv.c b/src/or/dirserv.c
index 8d9f166556..ae67e8edb7 100644
--- a/src/or/dirserv.c
+++ b/src/or/dirserv.c
@@ -1422,7 +1422,7 @@ router_counts_toward_thresholds(const node_t *node, time_t now,
  *
  * Also, set the is_exit flag of each router appropriately. */
 static void
-dirserv_compute_performance_thresholds(routerlist_t *rl,
+dirserv_compute_performance_thresholds(const smartlist_t *routers,
                                        digestmap_t *omit_as_sybil)
 {
   int n_active, n_active_nonexit, n_familiar;
@@ -1450,18 +1450,18 @@ dirserv_compute_performance_thresholds(routerlist_t *rl,
    * sort them and use that to compute thresholds. */
   n_active = n_active_nonexit = 0;
   /* Uptime for every active router. */
-  uptimes = tor_calloc(smartlist_len(rl->routers), sizeof(uint32_t));
+  uptimes = tor_calloc(smartlist_len(routers), sizeof(uint32_t));
   /* Bandwidth for every active router. */
-  bandwidths_kb = tor_calloc(smartlist_len(rl->routers), sizeof(uint32_t));
+  bandwidths_kb = tor_calloc(smartlist_len(routers), sizeof(uint32_t));
   /* Bandwidth for every active non-exit router. */
   bandwidths_excluding_exits_kb =
-    tor_calloc(smartlist_len(rl->routers), sizeof(uint32_t));
+    tor_calloc(smartlist_len(routers), sizeof(uint32_t));
   /* Weighted mean time between failure for each active router. */
-  mtbfs = tor_calloc(smartlist_len(rl->routers), sizeof(double));
+  mtbfs = tor_calloc(smartlist_len(routers), sizeof(double));
   /* Time-known for each active router. */
-  tks = tor_calloc(smartlist_len(rl->routers), sizeof(long));
+  tks = tor_calloc(smartlist_len(routers), sizeof(long));
   /* Weighted fractional uptime for each active router. */
-  wfus = tor_calloc(smartlist_len(rl->routers), sizeof(double));
+  wfus = tor_calloc(smartlist_len(routers), sizeof(double));
 
   nodelist_assert_ok();
 
@@ -1596,11 +1596,11 @@ dirserv_compute_performance_thresholds(routerlist_t *rl,
  * networkstatus_getinfo_by_purpose().
  */
 void
-dirserv_compute_bridge_flag_thresholds(routerlist_t *rl)
+dirserv_compute_bridge_flag_thresholds(const smartlist_t *routers)
 {
 
   digestmap_t *omit_as_sybil = digestmap_new();
-  dirserv_compute_performance_thresholds(rl, omit_as_sybil);
+  dirserv_compute_performance_thresholds(routers, omit_as_sybil);
   digestmap_free(omit_as_sybil, NULL);
 }
 
@@ -1753,16 +1753,13 @@ dirserv_get_bandwidth_for_router_kb(const routerinfo_t *ri)
  * how many measured bandwidths we know.  This is used to decide whether we
  * ever trust advertised bandwidths for purposes of assigning flags. */
 static void
-dirserv_count_measured_bws(routerlist_t *rl)
+dirserv_count_measured_bws(const smartlist_t *routers)
 {
   /* Initialize this first */
   routers_with_measured_bw = 0;
 
-  tor_assert(rl);
-  tor_assert(rl->routers);
-
   /* Iterate over the routerlist and count measured bandwidths */
-  SMARTLIST_FOREACH_BEGIN(rl->routers, routerinfo_t *, ri) {
+  SMARTLIST_FOREACH_BEGIN(routers, const routerinfo_t *, ri) {
     /* Check if we know a measured bandwidth for this one */
     if (dirserv_has_measured_bw(ri->cache_info.identity_digest)) {
       ++routers_with_measured_bw;
@@ -2126,6 +2123,50 @@ get_possible_sybil_list(const smartlist_t *routers)
   return omit_as_sybil;
 }
 
+/** If there are entries in <b>routers</b> with exactly the same ed25519 keys,
+ * remove the older one.  If they are exactly the same age, remove the one
+ * with the greater descriptor digest. May alter the order of the list. */
+static void
+routers_make_ed_keys_unique(smartlist_t *routers)
+{
+  routerinfo_t *ri2;
+  digest256map_t *by_ed_key = digest256map_new();
+
+  SMARTLIST_FOREACH_BEGIN(routers, routerinfo_t *, ri) {
+    ri->omit_from_vote = 0;
+    if (ri->signing_key_cert == NULL)
+      continue; /* No ed key */
+    const uint8_t *pk = ri->signing_key_cert->signing_key.pubkey;
+    if ((ri2 = digest256map_get(by_ed_key, pk))) {
+      /* Duplicate; must omit one.  Set the omit_from_vote flag in whichever
+       * one has the earlier published_on. */
+      const time_t ri_pub = ri->cache_info.published_on;
+      const time_t ri2_pub = ri2->cache_info.published_on;
+      if (ri2_pub < ri_pub ||
+          (ri2_pub == ri_pub &&
+           memcmp(ri->cache_info.signed_descriptor_digest,
+                  ri2->cache_info.signed_descriptor_digest,DIGEST_LEN)<0)) {
+        digest256map_set(by_ed_key, pk, ri);
+        ri2->omit_from_vote = 1;
+      } else {
+        ri->omit_from_vote = 1;
+      }
+    } else {
+      /* Add to map */
+      digest256map_set(by_ed_key, pk, ri);
+    }
+  } SMARTLIST_FOREACH_END(ri);
+
+  digest256map_free(by_ed_key, NULL);
+
+  /* Now remove every router where the omit_from_vote flag got set. */
+  SMARTLIST_FOREACH_BEGIN(routers, const routerinfo_t *, ri) {
+    if (ri->omit_from_vote) {
+      SMARTLIST_DEL_CURRENT(routers, ri);
+    }
+  } SMARTLIST_FOREACH_END(ri);
+}
+
 /** Extract status information from <b>ri</b> and from other authority
  * functions and store it in <b>rs</b>>.
  *
@@ -2815,6 +2856,8 @@ dirserv_generate_networkstatus_vote_obj(crypto_pk_t *private_key,
 
   routers = smartlist_new();
   smartlist_add_all(routers, rl->routers);
+  routers_make_ed_keys_unique(routers);
+  /* After this point, don't use rl->routers; use 'routers' instead. */
   routers_sort_by_identity(routers);
   omit_as_sybil = get_possible_sybil_list(routers);
 
@@ -2825,9 +2868,9 @@ dirserv_generate_networkstatus_vote_obj(crypto_pk_t *private_key,
 
   /* Count how many have measured bandwidths so we know how to assign flags;
    * this must come before dirserv_compute_performance_thresholds() */
-  dirserv_count_measured_bws(rl);
+  dirserv_count_measured_bws(routers);
 
-  dirserv_compute_performance_thresholds(rl, omit_as_sybil);
+  dirserv_compute_performance_thresholds(routers, omit_as_sybil);
 
   routerstatuses = smartlist_new();
   microdescriptors = smartlist_new();
diff --git a/src/or/dirserv.h b/src/or/dirserv.h
index d07339bc12..b16a67c081 100644
--- a/src/or/dirserv.h
+++ b/src/or/dirserv.h
@@ -50,7 +50,7 @@ int list_server_status_v1(smartlist_t *routers, char **router_status_out,
 int dirserv_dump_directory_to_string(char **dir_out,
                                      crypto_pk_t *private_key);
 char *dirserv_get_flag_thresholds_line(void);
-void dirserv_compute_bridge_flag_thresholds(routerlist_t *rl);
+void dirserv_compute_bridge_flag_thresholds(const smartlist_t *routers);
 
 int directory_fetches_from_authorities(const or_options_t *options);
 int directory_fetches_dir_info_early(const or_options_t *options);
diff --git a/src/or/dirvote.c b/src/or/dirvote.c
index d8e6ee2229..654d461dd6 100644
--- a/src/or/dirvote.c
+++ b/src/or/dirvote.c
@@ -558,6 +558,13 @@ compute_consensus_method(smartlist_t *votes)
 static int
 consensus_method_is_supported(int method)
 {
+  if (method == MIN_METHOD_FOR_ED25519_ID_IN_MD) {
+    /* This method was broken due to buggy code accidently left in
+     * dircollate.c; do not actually use it.
+     */
+    return 0;
+  }
+
   return (method >= MIN_SUPPORTED_CONSENSUS_METHOD) &&
     (method <= MAX_SUPPORTED_CONSENSUS_METHOD);
 }
@@ -1235,6 +1242,9 @@ networkstatus_compute_consensus(smartlist_t *votes,
     smartlist_free(combined_server_versions);
     smartlist_free(combined_client_versions);
 
+    if (consensus_method >= MIN_METHOD_FOR_ED25519_ID_VOTING)
+      smartlist_add(flags, tor_strdup("NoEdConsensus"));
+
     smartlist_sort_strings(flags);
     smartlist_uniq_strings(flags);
 
@@ -1532,6 +1542,8 @@ networkstatus_compute_consensus(smartlist_t *votes,
       num_bandwidths = 0;
       num_mbws = 0;
       num_guardfraction_inputs = 0;
+      int ed_consensus = 0;
+      const uint8_t *ed_consensus_val = NULL;
 
       /* Okay, go through all the entries for this digest. */
       for (int voter_idx = 0; voter_idx < smartlist_len(votes); ++voter_idx) {
@@ -1573,6 +1585,17 @@ networkstatus_compute_consensus(smartlist_t *votes,
 
         if (rs->status.has_bandwidth)
           bandwidths_kb[num_bandwidths++] = rs->status.bandwidth_kb;
+
+        /* Count number for which ed25519 is canonical. */
+        if (rs->ed25519_reflects_consensus) {
+          ++ed_consensus;
+          if (ed_consensus_val) {
+            tor_assert(fast_memeq(ed_consensus_val, rs->ed25519_id,
+                                  ED25519_PUBKEY_LEN));
+          } else {
+            ed_consensus_val = rs->ed25519_id;
+          }
+        }
       }
 
       /* We don't include this router at all unless more than half of
@@ -1580,6 +1603,14 @@ networkstatus_compute_consensus(smartlist_t *votes,
       if (n_listing <= total_authorities/2)
         continue;
 
+      if (ed_consensus > 0) {
+        tor_assert(consensus_method >= MIN_METHOD_FOR_ED25519_ID_VOTING);
+        if (ed_consensus <= total_authorities / 2) {
+          log_warn(LD_BUG, "Not enough entries had ed_consensus set; how "
+                   "can we have a consensus of %d?", ed_consensus);
+        }
+      }
+
       /* The clangalyzer can't figure out that this will never be NULL
        * if n_listing is at least 1 */
       tor_assert(current_rsa_id);
@@ -1633,6 +1664,10 @@ networkstatus_compute_consensus(smartlist_t *votes,
         } else if (!strcmp(fl, "Unnamed")) {
           if (is_unnamed)
             smartlist_add(chosen_flags, (char*)fl);
+        } else if (!strcmp(fl, "NoEdConsensus") &&
+                   consensus_method >= MIN_METHOD_FOR_ED25519_ID_VOTING) {
+          if (ed_consensus <= total_authorities/2)
+            smartlist_add(chosen_flags, (char*)fl);
         } else {
           if (flag_counts[fl_sl_idx] > n_flag_voters[fl_sl_idx]/2) {
             smartlist_add(chosen_flags, (char*)fl);
diff --git a/src/or/dirvote.h b/src/or/dirvote.h
index dca8540870..50c2496bb0 100644
--- a/src/or/dirvote.h
+++ b/src/or/dirvote.h
@@ -55,7 +55,7 @@
 #define MIN_SUPPORTED_CONSENSUS_METHOD 13
 
 /** The highest consensus method that we currently support. */
-#define MAX_SUPPORTED_CONSENSUS_METHOD 21
+#define MAX_SUPPORTED_CONSENSUS_METHOD 22
 
 /** Lowest consensus method where microdesc consensuses omit any entry
  * with no microdesc. */
@@ -87,11 +87,12 @@
 #define MIN_METHOD_FOR_GUARDFRACTION 20
 
 /** Lowest consensus method where authorities may include an "id" line for
- * ed25519 identities in microdescriptors. */
+ * ed25519 identities in microdescriptors. (Broken; see
+ * consensus_method_is_supported() for more info.) */
 #define MIN_METHOD_FOR_ED25519_ID_IN_MD 21
 /** Lowest consensus method where authorities vote on ed25519 ids and ensure
  * ed25519 id consistency. */
-#define MIN_METHOD_FOR_ED25519_ID_VOTING MIN_METHOD_FOR_ED25519_ID_IN_MD
+#define MIN_METHOD_FOR_ED25519_ID_VOTING 22
 
 /** Default bandwidth to clip unmeasured bandwidths to using method >=
  * MIN_METHOD_TO_CLIP_UNMEASURED_BW.  (This is not a consensus method; do not
diff --git a/src/or/networkstatus.c b/src/or/networkstatus.c
index 71a2c0f121..a9b22ed1cc 100644
--- a/src/or/networkstatus.c
+++ b/src/or/networkstatus.c
@@ -1701,7 +1701,7 @@ networkstatus_dump_bridge_status_to_file(time_t now)
   char published[ISO_TIME_LEN+1];
 
   format_iso_time(published, now);
-  dirserv_compute_bridge_flag_thresholds(rl);
+  dirserv_compute_bridge_flag_thresholds(rl->routers);
   thresholds = dirserv_get_flag_thresholds_line();
   tor_asprintf(&published_thresholds_and_status,
                "published %s\nflag-thresholds %s\n%s",
diff --git a/src/or/or.h b/src/or/or.h
index 4496cbcec3..431927c7e7 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -2081,6 +2081,10 @@ typedef struct {
    * tests for it. */
   unsigned int needs_retest_if_added:1;
 
+  /** Used during voting to indicate that we should not include an entry for
+   * this routerinfo. Used only during voting. */
+  unsigned int omit_from_vote:1;
+
 /** Tor can use this router for general positions in circuits; we got it
  * from a directory server as usual, or we're an authority and a server
  * uploaded it. */
@@ -2373,8 +2377,13 @@ typedef struct vote_routerstatus_t {
   char *version; /**< The version that the authority says this router is
                   * running. */
   unsigned int has_measured_bw:1; /**< The vote had a measured bw */
-  unsigned int has_ed25519_listing:1; /** DOCDOC */
-  unsigned int ed25519_reflects_consensus:1; /** DOCDOC */
+  /** True iff the vote included an entry for ed25519 ID, or included
+   * "id ed25519 none" to indicate that there was no ed25519 ID. */
+  unsigned int has_ed25519_listing:1;
+  /** True if the Ed25519 listing here is the consensus-opinion for the
+   * Ed25519 listing; false if there was no consensus on Ed25519 key status,
+   * or if this VRS doesn't reflect it. */
+  unsigned int ed25519_reflects_consensus:1;
   uint32_t measured_bw_kb; /**< Measured bandwidth (capacity) of the router */
   /** The hash or hashes that the authority claims this microdesc has. */
   vote_microdesc_hash_t *microdesc;
diff --git a/src/or/routerparse.c b/src/or/routerparse.c
index f898ef8aef..6b6e21d5d0 100644
--- a/src/or/routerparse.c
+++ b/src/or/routerparse.c
@@ -2862,7 +2862,7 @@ networkstatus_parse_vote_from_string(const char *s, const char **eos_out,
                       (ns_type == NS_TYPE_CONSENSUS) ?
                       networkstatus_consensus_token_table :
                       networkstatus_token_table, 0)) {
-    log_warn(LD_DIR, "Error tokenizing network-status vote header");
+    log_warn(LD_DIR, "Error tokenizing network-status header");
     goto err;
   }
 
@@ -3085,7 +3085,7 @@ networkstatus_parse_vote_from_string(const char *s, const char **eos_out,
           base16_decode(voter->identity_digest, sizeof(voter->identity_digest),
                         tok->args[1], HEX_DIGEST_LEN) < 0) {
         log_warn(LD_DIR, "Error decoding identity digest %s in "
-                 "network-status vote.", escaped(tok->args[1]));
+                 "network-status document.", escaped(tok->args[1]));
         goto err;
       }
       if (ns->type != NS_TYPE_CONSENSUS &&
@@ -3144,7 +3144,7 @@ networkstatus_parse_vote_from_string(const char *s, const char **eos_out,
     voter = NULL;
   }
   if (smartlist_len(ns->voters) == 0) {
-    log_warn(LD_DIR, "Missing dir-source elements in a vote networkstatus.");
+    log_warn(LD_DIR, "Missing dir-source elements in a networkstatus.");
     goto err;
   } else if (ns->type != NS_TYPE_CONSENSUS && smartlist_len(ns->voters) != 1) {
     log_warn(LD_DIR, "Too many dir-source elements in a vote networkstatus.");
@@ -3205,8 +3205,7 @@ networkstatus_parse_vote_from_string(const char *s, const char **eos_out,
     }
     if (fast_memcmp(rs1->identity_digest, rs2->identity_digest, DIGEST_LEN)
         >= 0) {
-      log_warn(LD_DIR, "Vote networkstatus entries not sorted by identity "
-               "digest");
+      log_warn(LD_DIR, "Networkstatus entries not sorted by identity digest");
       goto err;
     }
   }
@@ -3319,12 +3318,12 @@ networkstatus_parse_vote_from_string(const char *s, const char **eos_out,
         base16_decode(declared_identity, sizeof(declared_identity),
                       id_hexdigest, HEX_DIGEST_LEN) < 0) {
       log_warn(LD_DIR, "Error decoding declared identity %s in "
-               "network-status vote.", escaped(id_hexdigest));
+               "network-status document.", escaped(id_hexdigest));
       goto err;
     }
     if (!(v = networkstatus_get_voter_by_id(ns, declared_identity))) {
-      log_warn(LD_DIR, "ID on signature on network-status vote does not match "
-               "any declared directory source.");
+      log_warn(LD_DIR, "ID on signature on network-status document does "
+               "not match any declared directory source.");
       goto err;
     }
     sig = tor_malloc_zero(sizeof(document_signature_t));
@@ -3334,7 +3333,7 @@ networkstatus_parse_vote_from_string(const char *s, const char **eos_out,
         base16_decode(sig->signing_key_digest, sizeof(sig->signing_key_digest),
                       sk_hexdigest, HEX_DIGEST_LEN) < 0) {
       log_warn(LD_DIR, "Error decoding declared signing key digest %s in "
-               "network-status vote.", escaped(sk_hexdigest));
+               "network-status document.", escaped(sk_hexdigest));
       tor_free(sig);
       goto err;
     }
@@ -3353,8 +3352,8 @@ networkstatus_parse_vote_from_string(const char *s, const char **eos_out,
       /* We already parsed a vote with this algorithm from this voter. Use the
          first one. */
       log_fn(LOG_PROTOCOL_WARN, LD_DIR, "We received a networkstatus "
-             "that contains two votes from the same voter with the same "
-             "algorithm. Ignoring the second vote.");
+             "that contains two signatures from the same voter with the same "
+             "algorithm. Ignoring the second signature.");
       tor_free(sig);
       continue;
     }
@@ -3362,7 +3361,7 @@ networkstatus_parse_vote_from_string(const char *s, const char **eos_out,
     if (ns->type != NS_TYPE_CONSENSUS) {
       if (check_signature_token(ns_digests.d[DIGEST_SHA1], DIGEST_LEN,
                                 tok, ns->cert->signing_key, 0,
-                                "network-status vote")) {
+                                "network-status document")) {
         tor_free(sig);
         goto err;
       }
@@ -3381,7 +3380,7 @@ networkstatus_parse_vote_from_string(const char *s, const char **eos_out,
   } SMARTLIST_FOREACH_END(_tok);
 
   if (! n_signatures) {
-    log_warn(LD_DIR, "No signatures on networkstatus vote.");
+    log_warn(LD_DIR, "No signatures on networkstatus document.");
     goto err;
   } else if (ns->type == NS_TYPE_VOTE && n_signatures != 1) {
     log_warn(LD_DIR, "Received more than one signature on a "