Merge branch 'protover_v2_squashed'

18 files changed, 1425 insertions, 39 deletions

diff --git a/src/or/dirserv.c b/src/or/dirserv.c
index ff50ca4417..e8d60d0db8 100644
--- a/src/or/dirserv.c
+++ b/src/or/dirserv.c
@@ -24,6 +24,7 @@
 #include "networkstatus.h"
 #include "nodelist.h"
 #include "policies.h"
+#include "protover.h"
 #include "rephist.h"
 #include "router.h"
 #include "routerlist.h"
@@ -1795,6 +1796,7 @@ version_from_platform(const char *platform)
  */
 char *
 routerstatus_format_entry(const routerstatus_t *rs, const char *version,
+                          const char *protocols,
                           routerstatus_format_type_t format,
                           const vote_routerstatus_t *vrs)
 {
@@ -1858,6 +1860,9 @@ routerstatus_format_entry(const routerstatus_t *rs, const char *version,
   if (version && strlen(version) < MAX_V_LINE_LEN - V_LINE_OVERHEAD) {
     smartlist_add_asprintf(chunks, "v %s\n", version);
   }
+  if (protocols) {
+    smartlist_add_asprintf(chunks, "pr %s\n", protocols);
+  }
 
   if (format != NS_V2) {
     const routerinfo_t* desc = router_get_by_id_digest(rs->identity_digest);
@@ -2836,6 +2841,12 @@ dirserv_generate_networkstatus_vote_obj(crypto_pk_t *private_key,
         rs->is_flagged_running = 0;
 
       vrs->version = version_from_platform(ri->platform);
+      if (ri->protocol_list) {
+        vrs->protocols = tor_strdup(ri->protocol_list);
+      } else {
+        vrs->protocols = tor_strdup(
+                              protover_compute_for_old_tor(vrs->version));
+      }
       vrs->microdesc = dirvote_format_all_microdesc_vote_lines(ri, now,
                                                         microdescriptors);
 
@@ -2908,6 +2919,31 @@ dirserv_generate_networkstatus_vote_obj(crypto_pk_t *private_key,
 
   v3_out->client_versions = client_versions;
   v3_out->server_versions = server_versions;
+
+  /* These are hardwired, to avoid disaster. */
+  v3_out->recommended_relay_protocols =
+    tor_strdup("Cons=1-2 Desc=1-2 DirCache=1 HSDir=1 HSIntro=3 HSRend=1 "
+               "Link=4 LinkAuth=1 Microdesc=1-2 Relay=2");
+  v3_out->recommended_client_protocols =
+    tor_strdup("Cons=1-2 Desc=1-2 DirCache=1 HSDir=1 HSIntro=3 HSRend=1 "
+               "Link=4 LinkAuth=1 Microdesc=1-2 Relay=2");
+  v3_out->required_client_protocols =
+    tor_strdup("Cons=1-2 Desc=1-2 DirCache=1 HSDir=1 HSIntro=3 HSRend=1 "
+               "Link=4 LinkAuth=1 Microdesc=1-2 Relay=2");
+  v3_out->required_relay_protocols =
+    tor_strdup("Cons=1 Desc=1 DirCache=1 HSDir=1 HSIntro=3 HSRend=1 "
+               "Link=3-4 LinkAuth=1 Microdesc=1 Relay=1-2");
+
+  /* We are not allowed to vote to require anything we don't have. */
+  tor_assert(protover_all_supported(v3_out->required_relay_protocols, NULL));
+  tor_assert(protover_all_supported(v3_out->required_client_protocols, NULL));
+
+  /* We should not recommend anything we don't have. */
+  tor_assert_nonfatal(protover_all_supported(
+                         v3_out->recommended_relay_protocols, NULL));
+  tor_assert_nonfatal(protover_all_supported(
+                         v3_out->recommended_client_protocols, NULL));
+
   v3_out->package_lines = smartlist_new();
   {
     config_line_t *cl;
diff --git a/src/or/dirserv.h b/src/or/dirserv.h
index 3c914e9311..1e4f27e3d7 100644
--- a/src/or/dirserv.h
+++ b/src/or/dirserv.h
@@ -96,7 +96,9 @@ size_t dirserv_estimate_data_size(smartlist_t *fps, int is_serverdescs,
 size_t dirserv_estimate_microdesc_size(const smartlist_t *fps, int compressed);
 
 char *routerstatus_format_entry(
-                              const routerstatus_t *rs, const char *platform,
+                              const routerstatus_t *rs,
+                              const char *version,
+                              const char *protocols,
                               routerstatus_format_type_t format,
                               const vote_routerstatus_t *vrs);
 void dirserv_free_all(void);
diff --git a/src/or/dirvote.c b/src/or/dirvote.c
index ae869c9064..8b195f8914 100644
--- a/src/or/dirvote.c
+++ b/src/or/dirvote.c
@@ -13,6 +13,7 @@
 #include "microdesc.h"
 #include "networkstatus.h"
 #include "policies.h"
+#include "protover.h"
 #include "rephist.h"
 #include "router.h"
 #include "routerkeys.h"
@@ -61,6 +62,58 @@ static int dirvote_publish_consensus(void);
  * Voting
  * =====*/
 
+/* If <b>opt_value</b> is non-NULL, return "keyword opt_value\n" in a new
+ * string. Otherwise return a new empty string. */
+static char *
+format_line_if_present(const char *keyword, const char *opt_value)
+{
+  if (opt_value) {
+    char *result = NULL;
+    tor_asprintf(&result, "%s %s\n", keyword, opt_value);
+    return result;
+  } else {
+    return tor_strdup("");
+  }
+}
+
+/** Format the recommended/required-relay-client protocols lines for a vote in
+ * a newly allocated string, and return that string. */
+static char *
+format_protocols_lines_for_vote(const networkstatus_t *v3_ns)
+{
+  char *recommended_relay_protocols_line = NULL;
+  char *recommended_client_protocols_line = NULL;
+  char *required_relay_protocols_line = NULL;
+  char *required_client_protocols_line = NULL;
+
+  recommended_relay_protocols_line =
+    format_line_if_present("recommended-relay-protocols",
+                           v3_ns->recommended_relay_protocols);
+  recommended_client_protocols_line =
+    format_line_if_present("recommended-client-protocols",
+                           v3_ns->recommended_client_protocols);
+  required_relay_protocols_line =
+    format_line_if_present("required-relay-protocols",
+                           v3_ns->required_relay_protocols);
+  required_client_protocols_line =
+    format_line_if_present("required-client-protocols",
+                           v3_ns->required_client_protocols);
+
+  char *result = NULL;
+  tor_asprintf(&result, "%s%s%s%s",
+               recommended_relay_protocols_line,
+               recommended_client_protocols_line,
+               required_relay_protocols_line,
+               required_client_protocols_line);
+
+  tor_free(recommended_relay_protocols_line);
+  tor_free(recommended_client_protocols_line);
+  tor_free(required_relay_protocols_line);
+  tor_free(required_client_protocols_line);
+
+  return result;
+}
+
 /** Return a new string containing the string representation of the vote in
  * <b>v3_ns</b>, signed with our v3 signing key <b>private_signing_key</b>.
  * For v3 authorities. */
@@ -69,11 +122,11 @@ format_networkstatus_vote(crypto_pk_t *private_signing_key,
                           networkstatus_t *v3_ns)
 {
   smartlist_t *chunks = smartlist_new();
-  const char *client_versions = NULL, *server_versions = NULL;
   char *packages = NULL;
   char fingerprint[FINGERPRINT_LEN+1];
   char digest[DIGEST_LEN];
   uint32_t addr;
+  char *protocols_lines = NULL;
   char *client_versions_line = NULL, *server_versions_line = NULL;
   char *shared_random_vote_str = NULL;
   networkstatus_voter_info_t *voter;
@@ -88,21 +141,12 @@ format_networkstatus_vote(crypto_pk_t *private_signing_key,
 
   base16_encode(fingerprint, sizeof(fingerprint),
                 v3_ns->cert->cache_info.identity_digest, DIGEST_LEN);
-  client_versions = v3_ns->client_versions;
-  server_versions = v3_ns->server_versions;
 
-  if (client_versions) {
-    tor_asprintf(&client_versions_line, "client-versions %s\n",
-                 client_versions);
-  } else {
-    client_versions_line = tor_strdup("");
-  }
-  if (server_versions) {
-    tor_asprintf(&server_versions_line, "server-versions %s\n",
-                 server_versions);
-  } else {
-    server_versions_line = tor_strdup("");
-  }
+  client_versions_line = format_line_if_present("client-versions",
+                                                v3_ns->client_versions);
+  server_versions_line = format_line_if_present("server-versions",
+                                                v3_ns->server_versions);
+  protocols_lines = format_protocols_lines_for_vote(v3_ns);
 
   if (v3_ns->package_lines) {
     smartlist_t *tmp = smartlist_new();
@@ -154,6 +198,7 @@ format_networkstatus_vote(crypto_pk_t *private_signing_key,
                  "valid-until %s\n"
                  "voting-delay %d %d\n"
                  "%s%s" /* versions */
+                 "%s" /* protocols */
                  "%s" /* packages */
                  "known-flags %s\n"
                  "flag-thresholds %s\n"
@@ -167,6 +212,7 @@ format_networkstatus_vote(crypto_pk_t *private_signing_key,
                  v3_ns->vote_seconds, v3_ns->dist_seconds,
                  client_versions_line,
                  server_versions_line,
+                 protocols_lines,
                  packages,
                  flags,
                  flag_thresholds,
@@ -198,7 +244,8 @@ format_networkstatus_vote(crypto_pk_t *private_signing_key,
     char *rsf;
     vote_microdesc_hash_t *h;
     rsf = routerstatus_format_entry(&vrs->status,
-                                    vrs->version, NS_V3_VOTE, vrs);
+                                    vrs->version, vrs->protocols,
+                                    NS_V3_VOTE, vrs);
     if (rsf)
       smartlist_add(chunks, rsf);
 
@@ -258,6 +305,7 @@ format_networkstatus_vote(crypto_pk_t *private_signing_key,
  done:
   tor_free(client_versions_line);
   tor_free(server_versions_line);
+  tor_free(protocols_lines);
   tor_free(packages);
 
   SMARTLIST_FOREACH(chunks, char *, cp, tor_free(cp));
@@ -1152,6 +1200,72 @@ update_total_bandwidth_weights(const routerstatus_t *rs,
   }
 }
 
+/** Considering the different recommended/required protocols sets as a
+ * 4-element array, return the element from <b>vote</b> for that protocol
+ * set.
+ */
+static const char *
+get_nth_protocol_set_vote(int n, const networkstatus_t *vote)
+{
+  switch (n) {
+    case 0: return vote->recommended_client_protocols;
+    case 1: return vote->recommended_relay_protocols;
+    case 2: return vote->required_client_protocols;
+    case 3: return vote->required_relay_protocols;
+    default:
+      tor_assert_unreached();
+      return NULL;
+  }
+}
+
+/** Considering the different recommended/required protocols sets as a
+ * 4-element array, return a newly allocated string for the consensus value
+ * for the n'th set.
+ */
+static char *
+compute_nth_protocol_set(int n, int n_voters, const smartlist_t *votes)
+{
+  const char *keyword;
+  smartlist_t *proto_votes = smartlist_new();
+  int threshold;
+  switch (n) {
+    case 0:
+      keyword = "recommended-client-protocols";
+      threshold = CEIL_DIV(n_voters, 2);
+      break;
+    case 1:
+      keyword = "recommended-relay-protocols";
+      threshold = CEIL_DIV(n_voters, 2);
+      break;
+    case 2:
+      keyword = "required-client-protocols";
+      threshold = CEIL_DIV(n_voters * 2, 3);
+      break;
+    case 3:
+      keyword = "required-relay-protocols";
+      threshold = CEIL_DIV(n_voters * 2, 3);
+      break;
+    default:
+      tor_assert_unreached();
+      return NULL;
+  }
+
+  SMARTLIST_FOREACH_BEGIN(votes, const networkstatus_t *, ns) {
+    const char *v = get_nth_protocol_set_vote(n, ns);
+    if (v)
+      smartlist_add(proto_votes, (void*)v);
+  } SMARTLIST_FOREACH_END(ns);
+
+  char *protocols = protover_compute_vote(proto_votes, threshold);
+  smartlist_free(proto_votes);
+
+  char *result = NULL;
+  tor_asprintf(&result, "%s %s\n", keyword, protocols);
+  tor_free(protocols);
+
+  return result;
+}
+
 /** Given a list of vote networkstatus_t in <b>votes</b>, our public
  * authority <b>identity_key</b>, our private authority <b>signing_key</b>,
  * and the number of <b>total_authorities</b> that we believe exist in our
@@ -1331,6 +1445,17 @@ networkstatus_compute_consensus(smartlist_t *votes,
     tor_free(flaglist);
   }
 
+  if (consensus_method >= MIN_METHOD_FOR_RECOMMENDED_PROTOCOLS) {
+    int num_dirauth = get_n_authorities(V3_DIRINFO);
+    int idx;
+    for (idx = 0; idx < 4; ++idx) {
+      char *proto_line = compute_nth_protocol_set(idx, num_dirauth, votes);
+      if (BUG(!proto_line))
+        continue;
+      smartlist_add(chunks, proto_line);
+    }
+  }
+
   param_list = dirvote_compute_params(votes, consensus_method,
                                       total_authorities);
   if (smartlist_len(param_list)) {
@@ -1438,6 +1563,7 @@ networkstatus_compute_consensus(smartlist_t *votes,
     smartlist_t *matching_descs = smartlist_new();
     smartlist_t *chosen_flags = smartlist_new();
     smartlist_t *versions = smartlist_new();
+    smartlist_t *protocols = smartlist_new();
     smartlist_t *exitsummaries = smartlist_new();
     uint32_t *bandwidths_kb = tor_calloc(smartlist_len(votes),
                                          sizeof(uint32_t));
@@ -1580,6 +1706,7 @@ networkstatus_compute_consensus(smartlist_t *votes,
       routerstatus_t rs_out;
       const char *current_rsa_id = NULL;
       const char *chosen_version;
+      const char *chosen_protocol_list;
       const char *chosen_name = NULL;
       int exitsummary_disagreement = 0;
       int is_named = 0, is_unnamed = 0, is_running = 0, is_valid = 0;
@@ -1593,6 +1720,7 @@ networkstatus_compute_consensus(smartlist_t *votes,
       smartlist_clear(matching_descs);
       smartlist_clear(chosen_flags);
       smartlist_clear(versions);
+      smartlist_clear(protocols);
       num_bandwidths = 0;
       num_mbws = 0;
       num_guardfraction_inputs = 0;
@@ -1612,6 +1740,12 @@ networkstatus_compute_consensus(smartlist_t *votes,
         if (rs->version && rs->version[0])
           smartlist_add(versions, rs->version);
 
+        if (rs->protocols) {
+          /* We include this one even if it's empty: voting for an
+           * empty protocol list actually is meaningful. */
+          smartlist_add(protocols, rs->protocols);
+        }
+
         /* Tally up all the flags. */
         for (int flag = 0; flag < n_voter_flags[voter_idx]; ++flag) {
           if (rs->flags & (U64_LITERAL(1) << flag))
@@ -1758,6 +1892,14 @@ networkstatus_compute_consensus(smartlist_t *votes,
         chosen_version = NULL;
       }
 
+      /* Pick the protocol list */
+      if (smartlist_len(protocols)) {
+        smartlist_sort_strings(protocols);
+        chosen_protocol_list = get_most_frequent_member(protocols);
+      } else {
+        chosen_protocol_list = NULL;
+      }
+
       /* If it's a guard and we have enough guardfraction votes,
          calculate its consensus guardfraction value. */
       if (is_guard && num_guardfraction_inputs > 2 &&
@@ -1891,7 +2033,7 @@ networkstatus_compute_consensus(smartlist_t *votes,
         char *buf;
         /* Okay!! Now we can write the descriptor... */
         /*     First line goes into "buf". */
-        buf = routerstatus_format_entry(&rs_out, NULL, rs_format, NULL);
+        buf = routerstatus_format_entry(&rs_out, NULL, NULL, rs_format, NULL);
         if (buf)
           smartlist_add(chunks, buf);
       }
@@ -1911,6 +2053,10 @@ networkstatus_compute_consensus(smartlist_t *votes,
         smartlist_add(chunks, tor_strdup(chosen_version));
       }
       smartlist_add(chunks, tor_strdup("\n"));
+      if (chosen_protocol_list &&
+          consensus_method >= MIN_METHOD_FOR_RS_PROTOCOLS) {
+        smartlist_add_asprintf(chunks, "pr %s\n", chosen_protocol_list);
+      }
       /*     Now the weight line. */
       if (rs_out.has_bandwidth) {
         char *guardfraction_str = NULL;
@@ -1951,6 +2097,7 @@ networkstatus_compute_consensus(smartlist_t *votes,
     smartlist_free(matching_descs);
     smartlist_free(chosen_flags);
     smartlist_free(versions);
+    smartlist_free(protocols);
     smartlist_free(exitsummaries);
     tor_free(bandwidths_kb);
     tor_free(measured_bws_kb);
diff --git a/src/or/dirvote.h b/src/or/dirvote.h
index 06bfe671bd..efd233ef5f 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 24
+#define MAX_SUPPORTED_CONSENSUS_METHOD 25
 
 /** Lowest consensus method where microdesc consensuses omit any entry
  * with no microdesc. */
@@ -103,6 +103,14 @@
  * the Valid flag. */
 #define MIN_METHOD_FOR_EXCLUDING_INVALID_NODES 24
 
+/** Lowest consensus method where authorities vote on required/recommended
+ * protocols. */
+#define MIN_METHOD_FOR_RECOMMENDED_PROTOCOLS 25
+
+/** Lowest consensus method where authorities add protocols to routerstatus
+ * entries. */
+#define MIN_METHOD_FOR_RS_PROTOCOLS 25
+
 /** Default bandwidth to clip unmeasured bandwidths to using method >=
  * MIN_METHOD_TO_CLIP_UNMEASURED_BW.  (This is not a consensus method; do not
  * get confused with the above macros.) */
diff --git a/src/or/include.am b/src/or/include.am
index 3988eefb94..b4554aadb9 100644
--- a/src/or/include.am
+++ b/src/or/include.am
@@ -60,6 +60,7 @@ LIBTOR_A_SOURCES = \
 	src/or/shared_random_state.c		\
 	src/or/transports.c				\
 	src/or/periodic.c				\
+	src/or/protover.c				\
 	src/or/policies.c				\
 	src/or/reasons.c				\
 	src/or/relay.c					\
@@ -172,6 +173,7 @@ ORHEADERS = \
 	src/or/transports.h				\
 	src/or/periodic.h				\
 	src/or/policies.h				\
+	src/or/protover.h				\
 	src/or/reasons.h				\
 	src/or/relay.h					\
 	src/or/rendcache.h				\
diff --git a/src/or/main.c b/src/or/main.c
index 7ac1c1c4f2..013e301aff 100644
--- a/src/or/main.c
+++ b/src/or/main.c
@@ -46,6 +46,7 @@
 #include "onion.h"
 #include "periodic.h"
 #include "policies.h"
+#include "protover.h"
 #include "transports.h"
 #include "relay.h"
 #include "rendclient.h"
@@ -2972,6 +2973,7 @@ tor_free_all(int postfork)
   ext_orport_free_all();
   control_free_all();
   sandbox_free_getaddrinfo_cache();
+  protover_free_all();
   if (!postfork) {
     config_free_all();
     or_state_free_all();
diff --git a/src/or/networkstatus.c b/src/or/networkstatus.c
index 28f5b42799..dd8d5789e3 100644
--- a/src/or/networkstatus.c
+++ b/src/or/networkstatus.c
@@ -28,6 +28,7 @@
 #include "microdesc.h"
 #include "networkstatus.h"
 #include "nodelist.h"
+#include "protover.h"
 #include "relay.h"
 #include "router.h"
 #include "routerlist.h"
@@ -124,6 +125,9 @@ static void routerstatus_list_update_named_server_map(void);
 static void update_consensus_bootstrap_multiple_downloads(
                                                   time_t now,
                                                   const or_options_t *options);
+static int networkstatus_check_required_protocols(const networkstatus_t *ns,
+                                                  int client_mode,
+                                                  char **warning_out);
 
 /** Forget that we've warned about anything networkstatus-related, so we will
  * give fresh warnings if the same behavior happens again. */
@@ -229,6 +233,7 @@ vote_routerstatus_free(vote_routerstatus_t *rs)
   if (!rs)
     return;
   tor_free(rs->version);
+  tor_free(rs->protocols);
   tor_free(rs->status.exitsummary);
   for (h = rs->microdesc; h; h = next) {
     tor_free(h->microdesc_hash_line);
@@ -275,6 +280,11 @@ networkstatus_vote_free(networkstatus_t *ns)
 
   tor_free(ns->client_versions);
   tor_free(ns->server_versions);
+  tor_free(ns->recommended_client_protocols);
+  tor_free(ns->recommended_relay_protocols);
+  tor_free(ns->required_client_protocols);
+  tor_free(ns->required_relay_protocols);
+
   if (ns->known_flags) {
     SMARTLIST_FOREACH(ns->known_flags, char *, c, tor_free(c));
     smartlist_free(ns->known_flags);
@@ -1446,8 +1456,9 @@ routerstatus_has_changed(const routerstatus_t *a, const routerstatus_t *b)
          a->is_valid != b->is_valid ||
          a->is_possible_guard != b->is_possible_guard ||
          a->is_bad_exit != b->is_bad_exit ||
-         a->is_hs_dir != b->is_hs_dir ||
-         a->version_known != b->version_known;
+         a->is_hs_dir != b->is_hs_dir;
+  // XXXX this function needs a huge refactoring; it has gotten out
+  // XXXX of sync with routerstatus_t, and it will do so again.
 }
 
 /** Notify controllers of any router status entries that changed between
@@ -1546,6 +1557,66 @@ networkstatus_set_current_consensus_from_ns(networkstatus_t *c,
 }
 #endif //TOR_UNIT_TESTS
 
+/**
+ * Return true if any option is set in <b>options</b> to make us behave
+ * as a client.
+ *
+ * XXXX If we need this elsewhere at any point, we should make it nonstatic
+ * XXXX and move it into another file.
+ */
+static int
+any_client_port_set(const or_options_t *options)
+{
+  return (options->SocksPort_set ||
+          options->TransPort_set ||
+          options->NATDPort_set ||
+          options->ControlPort_set ||
+          options->DNSPort_set);
+}
+
+/**
+ * Helper for handle_missing_protocol_warning: handles either the
+ * client case (if <b>is_client</b> is set) or the server case otherwise.
+ */
+static void
+handle_missing_protocol_warning_impl(const networkstatus_t *c,
+                                     int is_client)
+{
+  char *protocol_warning = NULL;
+
+  int should_exit = networkstatus_check_required_protocols(c,
+                                                   is_client,
+                                                   &protocol_warning);
+  if (protocol_warning) {
+    tor_log(should_exit ? LOG_ERR : LOG_WARN,
+            LD_GENERAL,
+            "%s", protocol_warning);
+  }
+  if (should_exit) {
+    tor_assert_nonfatal(protocol_warning);
+  }
+  tor_free(protocol_warning);
+  if (should_exit)
+    exit(1);
+}
+
+/** Called when we have received a networkstatus <b>c</b>. If there are
+ * any _required_ protocols we are missing, log an error and exit
+ * immediately. If there are any _recommended_ protocols we are missing,
+ * warn. */
+static void
+handle_missing_protocol_warning(const networkstatus_t *c,
+                                const or_options_t *options)
+{
+  const int is_server = server_mode(options);
+  const int is_client = any_client_port_set(options) || !is_server;
+
+  if (is_server)
+    handle_missing_protocol_warning_impl(c, 0);
+  if (is_client)
+    handle_missing_protocol_warning_impl(c, 1);
+}
+
 /** Try to replace the current cached v3 networkstatus with the one in
  * <b>consensus</b>.  If we don't have enough certificates to validate it,
  * store it in consensus_waiting_for_certs and launch a certificate fetch.
@@ -1589,6 +1660,7 @@ networkstatus_set_current_consensus(const char *consensus,
   time_t current_valid_after = 0;
   int free_consensus = 1; /* Free 'c' at the end of the function */
   int old_ewma_enabled;
+  int checked_protocols_already = 0;
 
   if (flav < 0) {
     /* XXXX we don't handle unrecognized flavors yet. */
@@ -1604,6 +1676,16 @@ networkstatus_set_current_consensus(const char *consensus,
     goto done;
   }
 
+  if (from_cache && !was_waiting_for_certs) {
+    /* We previously stored this; check _now_ to make sure that version-kills
+     * really work.  This happens even before we check signatures: we did so
+     * before when we stored this to disk. This does mean an attacker who can
+     * write to the datadir can make us not start: such an attacker could
+     * already harm us by replacing our guards, which would be worse. */
+    checked_protocols_already = 1;
+    handle_missing_protocol_warning(c, options);
+  }
+
   if ((int)c->flavor != flav) {
     /* This wasn't the flavor we thought we were getting. */
     if (require_flavor) {
@@ -1729,6 +1811,10 @@ networkstatus_set_current_consensus(const char *consensus,
   if (!from_cache && flav == usable_consensus_flavor())
     control_event_client_status(LOG_NOTICE, "CONSENSUS_ARRIVED");
 
+  if (!checked_protocols_already) {
+    handle_missing_protocol_warning(c, options);
+  }
+
   /* Are we missing any certificates at all? */
   if (r != 1 && dl_certs)
     authority_certs_fetch_missing(c, now, source_dir);
@@ -2051,7 +2137,7 @@ signed_descs_update_status_from_consensus_networkstatus(smartlist_t *descs)
 char *
 networkstatus_getinfo_helper_single(const routerstatus_t *rs)
 {
-  return routerstatus_format_entry(rs, NULL, NS_CONTROL_PORT, NULL);
+  return routerstatus_format_entry(rs, NULL, NULL, NS_CONTROL_PORT, NULL);
 }
 
 /** Alloc and return a string describing routerstatuses for the most
@@ -2366,6 +2452,56 @@ getinfo_helper_networkstatus(control_connection_t *conn,
   return 0;
 }
 
+/** Check whether the networkstatus <b>ns</b> lists any protocol
+ * versions as "required" or "recommended" that we do not support.  If
+ * so, set *<b>warning_out</b> to a newly allocated string describing
+ * the problem.
+ *
+ * Return 1 if we should exit, 0 if we should not. */
+int
+networkstatus_check_required_protocols(const networkstatus_t *ns,
+                                       int client_mode,
+                                       char **warning_out)
+{
+  const char *func = client_mode ? "client" : "relay";
+  const char *required, *recommended;
+  char *missing = NULL;
+
+  tor_assert(warning_out);
+
+  if (client_mode) {
+    required = ns->required_client_protocols;
+    recommended = ns->recommended_client_protocols;
+  } else {
+    required = ns->required_relay_protocols;
+    recommended = ns->recommended_relay_protocols;
+  }
+
+  if (!protover_all_supported(required, &missing)) {
+    tor_asprintf(warning_out, "At least one protocol listed as required in "
+                 "the consensus is not supported by this version of Tor. "
+                 "You should upgrade. This version of Tor will not work as a "
+                 "%s on the Tor network. The missing protocols are: %s",
+                 func, missing);
+    tor_free(missing);
+    return 1;
+  }
+
+  if (! protover_all_supported(recommended, &missing)) {
+    tor_asprintf(warning_out, "At least one protocol listed as recommended in "
+                 "the consensus is not supported by this version of Tor. "
+                 "You should upgrade. This version of Tor will eventually "
+                 "stop working as a %s on the Tor network. The missing "
+                 "protocols are: %s",
+                 func, missing);
+    tor_free(missing);
+  }
+
+  tor_assert_nonfatal(missing == NULL);
+
+  return 0;
+}
+
 /** Free all storage held locally in this module. */
 void
 networkstatus_free_all(void)
diff --git a/src/or/or.h b/src/or/or.h
index 88e06fcaaf..66717792b4 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -2075,6 +2075,9 @@ typedef struct {
 
   char *platform; /**< What software/operating system is this OR using? */
 
+  char *protocol_list; /**< Encoded list of subprotocol versions supported
+                        * by this OR */
+
   /* link info */
   uint32_t bandwidthrate; /**< How many bytes does this OR add to its token
                            * bucket per second? */
@@ -2192,14 +2195,13 @@ typedef struct routerstatus_t {
   unsigned int is_v2_dir:1; /** True iff this router publishes an open DirPort
                              * or it claims to accept tunnelled dir requests.
                              */
-  /** True iff we know version info for this router. (i.e., a "v" entry was
-   * included.)  We'll replace all these with a big tor_version_t or a char[]
-   * if the number of traits we care about ever becomes incredibly big. */
-  unsigned int version_known:1;
+  /** True iff we have a proto line for this router, or a versions line
+   * from which we could infer the protocols. */
+  unsigned int protocols_known:1;
 
-  /** True iff this router has a version that allows it to accept EXTEND2
-   * cells */
-  unsigned int version_supports_extend2_cells:1;
+  /** True iff this router has a version or protocol list that allows it to
+   * accept EXTEND2 cells */
+  unsigned int supports_extend2_cells:1;
 
   unsigned int has_bandwidth:1; /**< The vote/consensus had bw info */
   unsigned int has_exitsummary:1; /**< The vote/consensus had exit summaries */
@@ -2407,6 +2409,8 @@ typedef struct vote_routerstatus_t {
                    * networkstatus_t.known_flags. */
   char *version; /**< The version that the authority says this router is
                   * running. */
+  char *protocols; /**< The protocols that this authority says this router
+                    * provides. */
   unsigned int has_measured_bw:1; /**< The vote had a measured bw */
   /** True iff the vote included an entry for ed25519 ID, or included
    * "id ed25519 none" to indicate that there was no ed25519 ID. */
@@ -2524,6 +2528,16 @@ typedef struct networkstatus_t {
    * voter has no opinion. */
   char *client_versions;
   char *server_versions;
+
+  /** Lists of subprotocol versions which are _recommended_ for relays and
+   * clients, or which are _require_ for relays and clients. Tor shouldn't
+   * make any more network connections if a required protocol is missing.
+   */
+  char *recommended_relay_protocols;
+  char *recommended_client_protocols;
+  char *required_relay_protocols;
+  char *required_client_protocols;
+
   /** List of flags that this vote/consensus applies to routers.  If a flag is
    * not listed here, the voter has no opinion on what its value should be. */
   smartlist_t *known_flags;
diff --git a/src/or/protover.c b/src/or/protover.c
new file mode 100644
index 0000000000..74fc3d0f74
--- /dev/null
+++ b/src/or/protover.c
@@ -0,0 +1,712 @@
+
+#define PROTOVER_PRIVATE
+
+#include "or.h"
+#include "protover.h"
+#include "routerparse.h"
+
+static const smartlist_t *get_supported_protocol_list(void);
+static int protocol_list_contains(const smartlist_t *protos,
+                                  protocol_type_t pr, uint32_t ver);
+
+/** Mapping between protocol type string and protocol type. */
+static const struct {
+  protocol_type_t protover_type;
+  const char *name;
+} PROTOCOL_NAMES[] = {
+  { PRT_LINK, "Link" },
+  { PRT_LINKAUTH, "LinkAuth" },
+  { PRT_RELAY, "Relay" },
+  { PRT_DIRCACHE, "DirCache" },
+  { PRT_HSDIR, "HSDir" },
+  { PRT_HSINTRO, "HSIntro" },
+  { PRT_HSREND, "HSRend" },
+  { PRT_DESC, "Desc" },
+  { PRT_MICRODESC, "Microdesc"},
+  { PRT_CONS, "Cons" }
+};
+
+#define N_PROTOCOL_NAMES ARRAY_LENGTH(PROTOCOL_NAMES)
+
+/**
+ * Given a protocol_type_t, return the corresponding string used in
+ * descriptors.
+ */
+STATIC const char *
+protocol_type_to_str(protocol_type_t pr)
+{
+  unsigned i;
+  for (i=0; i < N_PROTOCOL_NAMES; ++i) {
+    if (PROTOCOL_NAMES[i].protover_type == pr)
+      return PROTOCOL_NAMES[i].name;
+  }
+  /* LCOV_EXCL_START */
+  tor_assert_nonfatal_unreached_once();
+  return "UNKNOWN";
+  /* LCOV_EXCL_STOP */
+}
+
+/**
+ * Given a string, find the corresponding protocol type and store it in
+ * <b>pr_out</b>. Return 0 on success, -1 on failure.
+ */
+STATIC int
+str_to_protocol_type(const char *s, protocol_type_t *pr_out)
+{
+  if (BUG(!pr_out))
+    return -1;
+
+  unsigned i;
+  for (i=0; i < N_PROTOCOL_NAMES; ++i) {
+    if (0 == strcmp(s, PROTOCOL_NAMES[i].name)) {
+      *pr_out = PROTOCOL_NAMES[i].protover_type;
+      return 0;
+    }
+  }
+
+  return -1;
+}
+
+/**
+ * Release all space held by a single proto_entry_t structure
+ */
+STATIC void
+proto_entry_free(proto_entry_t *entry)
+{
+  if (!entry)
+    return;
+  tor_free(entry->name);
+  SMARTLIST_FOREACH(entry->ranges, proto_range_t *, r, tor_free(r));
+  smartlist_free(entry->ranges);
+  tor_free(entry);
+}
+
+/**
+ * Given a string <b>s</b> and optional end-of-string pointer
+ * <b>end_of_range</b>, parse the protocol range and store it in
+ * <b>low_out</b> and <b>high_out</b>.  A protocol range has the format U, or
+ * U-U, where U is an unsigned 32-bit integer.
+ */
+static int
+parse_version_range(const char *s, const char *end_of_range,
+                    uint32_t *low_out, uint32_t *high_out)
+{
+  uint32_t low, high;
+  char *next = NULL;
+  int ok;
+
+  tor_assert(high_out);
+  tor_assert(low_out);
+
+  if (BUG(!end_of_range))
+    end_of_range = s + strlen(s); // LCOV_EXCL_LINE
+
+  /* Note that this wouldn't be safe if we didn't know that eventually,
+   * we'd hit a NUL */
+  low = (uint32_t) tor_parse_ulong(s, 10, 0, UINT32_MAX, &ok, &next);
+  if (!ok)
+    goto error;
+  if (next > end_of_range)
+    goto error;
+  if (next == end_of_range) {
+    high = low;
+    goto done;
+  }
+
+  if (*next != '-')
+    goto error;
+  s = next+1;
+  /* ibid */
+  high = (uint32_t) tor_parse_ulong(s, 10, 0, UINT32_MAX, &ok, &next);
+  if (!ok)
+    goto error;
+  if (next != end_of_range)
+    goto error;
+
+ done:
+  *high_out = high;
+  *low_out = low;
+  return 0;
+
+ error:
+  return -1;
+}
+
+/** Parse a single protocol entry from <b>s</b> up to an optional
+ * <b>end_of_entry</b> pointer, and return that protocol entry. Return NULL
+ * on error.
+ *
+ * A protocol entry has a keyword, an = sign, and zero or more ranges. */
+static proto_entry_t *
+parse_single_entry(const char *s, const char *end_of_entry)
+{
+  proto_entry_t *out = tor_malloc_zero(sizeof(proto_entry_t));
+  const char *equals;
+
+  out->ranges = smartlist_new();
+
+  if (BUG (!end_of_entry))
+    end_of_entry = s + strlen(s); // LCOV_EXCL_LINE
+
+  /* There must be an =. */
+  equals = memchr(s, '=', end_of_entry - s);
+  if (!equals)
+    goto error;
+
+  /* The name must be nonempty */
+  if (equals == s)
+    goto error;
+
+  out->name = tor_strndup(s, equals-s);
+
+  tor_assert(equals < end_of_entry);
+
+  s = equals + 1;
+  while (s < end_of_entry) {
+    const char *comma = memchr(s, ',', end_of_entry-s);
+    proto_range_t *range = tor_malloc_zero(sizeof(proto_range_t));
+    if (! comma)
+      comma = end_of_entry;
+
+    smartlist_add(out->ranges, range);
+    if (parse_version_range(s, comma, &range->low, &range->high) < 0) {
+      goto error;
+    }
+
+    if (range->low > range->high) {
+      goto error;
+    }
+
+    s = comma;
+    while (*s == ',' && s < end_of_entry)
+      ++s;
+  }
+
+  return out;
+
+ error:
+  proto_entry_free(out);
+  return NULL;
+}
+
+/**
+ * Parse the protocol list from <b>s</b> and return it as a smartlist of
+ * proto_entry_t
+ */
+STATIC smartlist_t *
+parse_protocol_list(const char *s)
+{
+  smartlist_t *entries = smartlist_new();
+
+  while (*s) {
+    /* Find the next space or the NUL. */
+    const char *end_of_entry = strchr(s, ' ');
+    proto_entry_t *entry;
+    if (!end_of_entry)
+      end_of_entry = s + strlen(s);
+
+    entry = parse_single_entry(s, end_of_entry);
+
+    if (! entry)
+      goto error;
+
+    smartlist_add(entries, entry);
+
+    s = end_of_entry;
+    while (*s == ' ')
+      ++s;
+  }
+
+  return entries;
+
+ error:
+  SMARTLIST_FOREACH(entries, proto_entry_t *, ent, proto_entry_free(ent));
+  smartlist_free(entries);
+  return NULL;
+}
+
+/**
+ * Given a protocol type and version number, return true iff we know
+ * how to speak that protocol.
+ */
+int
+protover_is_supported_here(protocol_type_t pr, uint32_t ver)
+{
+  const smartlist_t *ours = get_supported_protocol_list();
+  return protocol_list_contains(ours, pr, ver);
+}
+
+/**
+ * Return true iff "list" encodes a protocol list that includes support for
+ * the indicated protocol and version.
+ */
+int
+protocol_list_supports_protocol(const char *list, protocol_type_t tp,
+                                uint32_t version)
+{
+  /* NOTE: This is a pretty inefficient implementation. If it ever shows
+   * up in profiles, we should memoize it.
+   */
+  smartlist_t *protocols = parse_protocol_list(list);
+  if (!protocols) {
+    return 0;
+  }
+  int contains = protocol_list_contains(protocols, tp, version);
+
+  SMARTLIST_FOREACH(protocols, proto_entry_t *, ent, proto_entry_free(ent));
+  smartlist_free(protocols);
+  return contains;
+}
+
+/** Return the canonical string containing the list of protocols
+ * that we support. */
+const char *
+protover_get_supported_protocols(void)
+{
+  return
+    "Cons=1-2 "
+    "Desc=1-2 "
+    "DirCache=1 "
+    "HSDir=1 "
+    "HSIntro=3 "
+    "HSRend=1-2 "
+    "Link=1-4 "
+    "LinkAuth=1 "
+    "Microdesc=1-2 "
+    "Relay=1-2";
+}
+
+/** The protocols from protover_get_supported_protocols(), as parsed into a
+ * list of proto_entry_t values. Access this via
+ * get_supported_protocol_list. */
+static smartlist_t *supported_protocol_list = NULL;
+
+/** Return a pointer to a smartlist of proto_entry_t for the protocols
+ * we support. */
+static const smartlist_t *
+get_supported_protocol_list(void)
+{
+  if (PREDICT_UNLIKELY(supported_protocol_list == NULL)) {
+    supported_protocol_list =
+      parse_protocol_list(protover_get_supported_protocols());
+  }
+  return supported_protocol_list;
+}
+
+/**
+ * Given a protocol entry, encode it at the end of the smartlist <b>chunks</b>
+ * as one or more newly allocated strings.
+ */
+static void
+proto_entry_encode_into(smartlist_t *chunks, const proto_entry_t *entry)
+{
+  smartlist_add_asprintf(chunks, "%s=", entry->name);
+
+  SMARTLIST_FOREACH_BEGIN(entry->ranges, proto_range_t *, range) {
+    const char *comma = "";
+    if (range_sl_idx != 0)
+      comma = ",";
+
+    if (range->low == range->high) {
+      smartlist_add_asprintf(chunks, "%s%lu",
+                             comma, (unsigned long)range->low);
+    } else {
+      smartlist_add_asprintf(chunks, "%s%lu-%lu",
+                             comma, (unsigned long)range->low,
+                             (unsigned long)range->high);
+    }
+  } SMARTLIST_FOREACH_END(range);
+}
+
+/** Given a list of space-separated proto_entry_t items,
+ * encode it into a newly allocated space-separated string. */
+STATIC char *
+encode_protocol_list(const smartlist_t *sl)
+{
+  const char *separator = "";
+  smartlist_t *chunks = smartlist_new();
+  SMARTLIST_FOREACH_BEGIN(sl, const proto_entry_t *, ent) {
+    smartlist_add(chunks, tor_strdup(separator));
+
+    proto_entry_encode_into(chunks, ent);
+
+    separator = " ";
+  } SMARTLIST_FOREACH_END(ent);
+
+  char *result = smartlist_join_strings(chunks, "", 0, NULL);
+
+  SMARTLIST_FOREACH(chunks, char *, cp, tor_free(cp));
+  smartlist_free(chunks);
+
+  return result;
+}
+
+/* We treat any protocol list with more than this many subprotocols in it
+ * as a DoS attempt. */
+const int MAX_PROTOCOLS_TO_EXPAND = (1<<16);
+
+/** Voting helper: Given a list of proto_entry_t, return a newly allocated
+ * smartlist of newly allocated strings, one for each included protocol
+ * version. (So 'Foo=3,5-7' expands to a list of 'Foo=3', 'Foo=5', 'Foo=6',
+ * 'Foo=7'.)
+ *
+ * Do not list any protocol version more than once.
+ *
+ * Return NULL if the list would be too big.
+ */
+static smartlist_t *
+expand_protocol_list(const smartlist_t *protos)
+{
+  smartlist_t *expanded = smartlist_new();
+  if (!protos)
+    return expanded;
+
+  SMARTLIST_FOREACH_BEGIN(protos, const proto_entry_t *, ent) {
+    const char *name = ent->name;
+    SMARTLIST_FOREACH_BEGIN(ent->ranges, const proto_range_t *, range) {
+      uint32_t u;
+      for (u = range->low; u <= range->high; ++u) {
+        smartlist_add_asprintf(expanded, "%s=%lu", name, (unsigned long)u);
+        if (smartlist_len(expanded) > MAX_PROTOCOLS_TO_EXPAND)
+          goto too_many;
+      }
+    } SMARTLIST_FOREACH_END(range);
+  } SMARTLIST_FOREACH_END(ent);
+
+  smartlist_sort_strings(expanded);
+  smartlist_uniq_strings(expanded); // This makes voting work. do not remove
+  return expanded;
+
+ too_many:
+  SMARTLIST_FOREACH(expanded, char *, cp, tor_free(cp));
+  smartlist_free(expanded);
+  return NULL;
+}
+
+/** Voting helper: compare two singleton proto_entry_t items by version
+ * alone. (A singleton item is one with a single range entry where
+ * low==high.) */
+static int
+cmp_single_ent_by_version(const void **a_, const void **b_)
+{
+  const proto_entry_t *ent_a = *a_;
+  const proto_entry_t *ent_b = *b_;
+
+  tor_assert(smartlist_len(ent_a->ranges) == 1);
+  tor_assert(smartlist_len(ent_b->ranges) == 1);
+
+  const proto_range_t *a = smartlist_get(ent_a->ranges, 0);
+  const proto_range_t *b = smartlist_get(ent_b->ranges, 0);
+
+  tor_assert(a->low == a->high);
+  tor_assert(b->low == b->high);
+
+  if (a->low < b->low) {
+    return -1;
+  } else if (a->low == b->low) {
+    return 0;
+  } else {
+    return 1;
+  }
+}
+
+/** Voting helper: Given a list of singleton protocol strings (of the form
+ * Foo=7), return a canonical listing of all the protocol versions listed,
+ * with as few ranges as possible, with protocol versions sorted lexically and
+ * versions sorted in numerically increasing order, using as few range entries
+ * as possible.
+ **/
+static char *
+contract_protocol_list(const smartlist_t *proto_strings)
+{
+  // map from name to list of single-version entries
+  strmap_t *entry_lists_by_name = strmap_new();
+  // list of protocol names
+  smartlist_t *all_names = smartlist_new();
+  // list of strings for the output we're building
+  smartlist_t *chunks = smartlist_new();
+
+  // Parse each item and stick it entry_lists_by_name. Build
+  // 'all_names' at the same time.
+  SMARTLIST_FOREACH_BEGIN(proto_strings, const char *, s) {
+    if (BUG(!s))
+      continue;// LCOV_EXCL_LINE
+    proto_entry_t *ent = parse_single_entry(s, s+strlen(s));
+    if (BUG(!ent))
+      continue; // LCOV_EXCL_LINE
+    smartlist_t *lst = strmap_get(entry_lists_by_name, ent->name);
+    if (!lst) {
+      smartlist_add(all_names, ent->name);
+      lst = smartlist_new();
+      strmap_set(entry_lists_by_name, ent->name, lst);
+    }
+    smartlist_add(lst, ent);
+  } SMARTLIST_FOREACH_END(s);
+
+  // We want to output the protocols sorted by their name.
+  smartlist_sort_strings(all_names);
+
+  SMARTLIST_FOREACH_BEGIN(all_names, const char *, name) {
+    const int first_entry = (name_sl_idx == 0);
+    smartlist_t *lst = strmap_get(entry_lists_by_name, name);
+    tor_assert(lst);
+    // Sort every entry with this name by version. They are
+    // singletons, so there can't be overlap.
+    smartlist_sort(lst, cmp_single_ent_by_version);
+
+    if (! first_entry)
+      smartlist_add(chunks, tor_strdup(" "));
+
+    /* We're going to construct this entry from the ranges. */
+    proto_entry_t *entry = tor_malloc_zero(sizeof(proto_entry_t));
+    entry->ranges = smartlist_new();
+    entry->name = tor_strdup(name);
+
+    // Now, find all the ranges of versions start..end where
+    // all of start, start+1, start+2, ..end are included.
+    int start_of_cur_series = 0;
+    while (start_of_cur_series < smartlist_len(lst)) {
+      const proto_entry_t *ent = smartlist_get(lst, start_of_cur_series);
+      const proto_range_t *range = smartlist_get(ent->ranges, 0);
+      const uint32_t ver_low = range->low;
+      uint32_t ver_high = ver_low;
+
+      int idx;
+      for (idx = start_of_cur_series+1; idx < smartlist_len(lst); ++idx) {
+        ent = smartlist_get(lst, idx);
+        range = smartlist_get(ent->ranges, 0);
+        if (range->low != ver_high + 1)
+          break;
+        ver_high += 1;
+      }
+
+      // Now idx is either off the end of the list, or the first sequence
+      // break in the list.
+      start_of_cur_series = idx;
+
+      proto_range_t *new_range = tor_malloc_zero(sizeof(proto_range_t));
+      new_range->low = ver_low;
+      new_range->high = ver_high;
+      smartlist_add(entry->ranges, new_range);
+    }
+    proto_entry_encode_into(chunks, entry);
+    proto_entry_free(entry);
+
+  } SMARTLIST_FOREACH_END(name);
+
+  // Build the result...
+  char *result = smartlist_join_strings(chunks, "", 0, NULL);
+
+  // And free all the stuff we allocated.
+  SMARTLIST_FOREACH_BEGIN(all_names, const char *, name) {
+    smartlist_t *lst = strmap_get(entry_lists_by_name, name);
+    tor_assert(lst);
+    SMARTLIST_FOREACH(lst, proto_entry_t *, e, proto_entry_free(e));
+    smartlist_free(lst);
+  } SMARTLIST_FOREACH_END(name);
+
+  strmap_free(entry_lists_by_name, NULL);
+  smartlist_free(all_names);
+  SMARTLIST_FOREACH(chunks, char *, cp, tor_free(cp));
+  smartlist_free(chunks);
+
+  return result;
+}
+
+/**
+ * Protocol voting implementation.
+ *
+ * Given a list of strings describing protocol versions, return a newly
+ * allocated string encoding all of the protocols that are listed by at
+ * least <b>threshold</b> of the inputs.
+ *
+ * The string is minimal and sorted according to the rules of
+ * contract_protocol_list above.
+ */
+char *
+protover_compute_vote(const smartlist_t *list_of_proto_strings,
+                      int threshold)
+{
+  smartlist_t *all_entries = smartlist_new();
+
+  // First, parse the inputs and break them into singleton entries.
+  SMARTLIST_FOREACH_BEGIN(list_of_proto_strings, const char *, vote) {
+    smartlist_t *unexpanded = parse_protocol_list(vote);
+    smartlist_t *this_vote = expand_protocol_list(unexpanded);
+    if (this_vote == NULL) {
+      log_warn(LD_NET, "When expanding a protocol list from an authority, I "
+               "got too many protocols. This is possibly an attack or a bug, "
+               "unless the Tor network truly has expanded to support over %d "
+               "different subprotocol versions. The offending string was: %s",
+               MAX_PROTOCOLS_TO_EXPAND, escaped(vote));
+    } else {
+      smartlist_add_all(all_entries, this_vote);
+      smartlist_free(this_vote);
+    }
+    SMARTLIST_FOREACH(unexpanded, proto_entry_t *, e, proto_entry_free(e));
+    smartlist_free(unexpanded);
+  } SMARTLIST_FOREACH_END(vote);
+
+  // Now sort the singleton entries
+  smartlist_sort_strings(all_entries);
+
+  // Now find all the strings that appear at least 'threshold' times.
+  smartlist_t *include_entries = smartlist_new();
+  const char *cur_entry = smartlist_get(all_entries, 0);
+  int n_times = 0;
+  SMARTLIST_FOREACH_BEGIN(all_entries, const char *, ent) {
+    if (!strcmp(ent, cur_entry)) {
+      n_times++;
+    } else {
+      if (n_times >= threshold && cur_entry)
+        smartlist_add(include_entries, (void*)cur_entry);
+      cur_entry = ent;
+      n_times = 1 ;
+    }
+  } SMARTLIST_FOREACH_END(ent);
+
+  if (n_times >= threshold && cur_entry)
+    smartlist_add(include_entries, (void*)cur_entry);
+
+  // Finally, compress that list.
+  char *result = contract_protocol_list(include_entries);
+  smartlist_free(include_entries);
+  SMARTLIST_FOREACH(all_entries, char *, cp, tor_free(cp));
+  smartlist_free(all_entries);
+
+  return result;
+}
+
+/** Return true if every protocol version described in the string <b>s</b> is
+ * one that we support, and false otherwise.  If <b>missing_out</b> is
+ * provided, set it to the list of protocols we do not support.
+ *
+ * NOTE: This is quadratic, but we don't do it much: only a few times per
+ * consensus. Checking signatures should be way more expensive than this
+ * ever would be.
+ **/
+int
+protover_all_supported(const char *s, char **missing_out)
+{
+  int all_supported = 1;
+  smartlist_t *missing;
+
+  if (!s) {
+    return 1;
+  }
+
+  smartlist_t *entries = parse_protocol_list(s);
+
+  missing = smartlist_new();
+
+  SMARTLIST_FOREACH_BEGIN(entries, const proto_entry_t *, ent) {
+    protocol_type_t tp;
+    if (str_to_protocol_type(ent->name, &tp) < 0) {
+      if (smartlist_len(ent->ranges)) {
+        goto unsupported;
+      }
+      continue;
+    }
+
+    SMARTLIST_FOREACH_BEGIN(ent->ranges, const proto_range_t *, range) {
+      uint32_t i;
+      for (i = range->low; i <= range->high; ++i) {
+        if (!protover_is_supported_here(tp, i)) {
+          goto unsupported;
+        }
+      }
+    } SMARTLIST_FOREACH_END(range);
+
+    continue;
+
+  unsupported:
+    all_supported = 0;
+    smartlist_add(missing, (void*) ent);
+  } SMARTLIST_FOREACH_END(ent);
+
+  if (missing_out && !all_supported) {
+    tor_assert(0 != smartlist_len(missing));
+    *missing_out = encode_protocol_list(missing);
+  }
+  smartlist_free(missing);
+
+  SMARTLIST_FOREACH(entries, proto_entry_t *, ent, proto_entry_free(ent));
+  smartlist_free(entries);
+
+  return all_supported;
+}
+
+/** Helper: Given a list of proto_entry_t, return true iff
+ * <b>pr</b>=<b>ver</b> is included in that list. */
+static int
+protocol_list_contains(const smartlist_t *protos,
+                       protocol_type_t pr, uint32_t ver)
+{
+  if (BUG(protos == NULL)) {
+    return 0; // LCOV_EXCL_LINE
+  }
+  const char *pr_name = protocol_type_to_str(pr);
+  if (BUG(pr_name == NULL)) {
+    return 0; // LCOV_EXCL_LINE
+  }
+
+  SMARTLIST_FOREACH_BEGIN(protos, const proto_entry_t *, ent) {
+    if (strcasecmp(ent->name, pr_name))
+      continue;
+    /* name matches; check the ranges */
+    SMARTLIST_FOREACH_BEGIN(ent->ranges, const proto_range_t *, range) {
+      if (ver >= range->low && ver <= range->high)
+        return 1;
+    } SMARTLIST_FOREACH_END(range);
+  } SMARTLIST_FOREACH_END(ent);
+
+  return 0;
+}
+
+/** Return a string describing the protocols supported by tor version
+ * <b>version</b>, or an empty string if we cannot tell.
+ *
+ * Note that this is only used to infer protocols for Tor versions that
+ * can't declare their own.
+ **/
+const char *
+protover_compute_for_old_tor(const char *version)
+{
+  if (tor_version_as_new_as(version,
+                            FIRST_TOR_VERSION_TO_ADVERTISE_PROTOCOLS)) {
+    return "";
+  } else if (tor_version_as_new_as(version, "0.2.7.5")) {
+    /* 0.2.9.1-alpha HSRend=2 */
+    return "Cons=1-2 Desc=1-2 DirCache=1 HSDir=1 HSIntro=3 HSRend=1-2 "
+      "Link=1-4 LinkAuth=1 "
+      "Microdesc=1-2 Relay=1-2";
+  } else if (tor_version_as_new_as(version, "0.2.7.5")) {
+    /* 0.2.7-stable added Desc=2, Microdesc=2, Cons=2, which indicate
+     * ed25519 support.  We'll call them present only in "stable" 027,
+     * though. */
+    return "Cons=1-2 Desc=1-2 DirCache=1 HSDir=1 HSIntro=3 HSRend=1 "
+      "Link=1-4 LinkAuth=1 "
+      "Microdesc=1-2 Relay=1-2";
+  } else if (tor_version_as_new_as(version, "0.2.4.19")) {
+    /* No currently supported Tor server versions are older than this, or
+     * lack these protocols. */
+    return "Cons=1 Desc=1 DirCache=1 HSDir=1 HSIntro=3 HSRend=1 "
+      "Link=1-4 LinkAuth=1 "
+      "Microdesc=1 Relay=1-2";
+  } else {
+    /* Cannot infer protocols. */
+    return "";
+  }
+}
+
+void
+protover_free_all(void)
+{
+  if (supported_protocol_list) {
+    smartlist_t *entries = supported_protocol_list;
+    SMARTLIST_FOREACH(entries, proto_entry_t *, ent, proto_entry_free(ent));
+    smartlist_free(entries);
+    supported_protocol_list = NULL;
+  }
+}
+
diff --git a/src/or/protover.h b/src/or/protover.h
new file mode 100644
index 0000000000..075405e7ca
--- /dev/null
+++ b/src/or/protover.h
@@ -0,0 +1,67 @@
+
+#ifndef TOR_PROTOVER_H
+#define TOR_PROTOVER_H
+
+#include "container.h"
+
+/** The first version of Tor that included "proto" entries in its
+ * descriptors.  Authorities should use this to decide whether to
+ * guess proto lines. */
+/* This is a guess. */
+#define FIRST_TOR_VERSION_TO_ADVERTISE_PROTOCOLS "0.2.9.3-alpha"
+
+/** List of recognized subprotocols. */
+typedef enum protocol_type_t {
+  PRT_LINK,
+  PRT_LINKAUTH,
+  PRT_RELAY,
+  PRT_DIRCACHE,
+  PRT_HSDIR,
+  PRT_HSINTRO,
+  PRT_HSREND,
+  PRT_DESC,
+  PRT_MICRODESC,
+  PRT_CONS,
+} protocol_type_t;
+
+int protover_all_supported(const char *s, char **missing);
+int protover_is_supported_here(protocol_type_t pr, uint32_t ver);
+const char *protover_get_supported_protocols(void);
+
+char *protover_compute_vote(const smartlist_t *list_of_proto_strings,
+                            int threshold);
+const char *protover_compute_for_old_tor(const char *version);
+int protocol_list_supports_protocol(const char *list, protocol_type_t tp,
+                                    uint32_t version);
+
+void protover_free_all(void);
+
+#ifdef PROTOVER_PRIVATE
+/** Represents a range of subprotocols of a given type. All subprotocols
+ * between <b>low</b> and <b>high</b> inclusive are included. */
+typedef struct proto_range_t {
+  uint32_t low;
+  uint32_t high;
+} proto_range_t;
+
+/** Represents a set of ranges of subprotocols of a given type. */
+typedef struct proto_entry_t {
+  /** The name of the protocol.
+   *
+   * (This needs to handle voting on protocols which
+   * we don't recognize yet, so it's a char* rather than a protocol_type_t.)
+   */
+  char *name;
+  /** Smartlist of proto_range_t */
+  smartlist_t *ranges;
+} proto_entry_t;
+
+STATIC smartlist_t *parse_protocol_list(const char *s);
+STATIC void proto_entry_free(proto_entry_t *entry);
+STATIC char *encode_protocol_list(const smartlist_t *sl);
+STATIC const char *protocol_type_to_str(protocol_type_t pr);
+STATIC int str_to_protocol_type(const char *s, protocol_type_t *pr_out);
+#endif
+
+#endif
+
diff --git a/src/or/router.c b/src/or/router.c
index 8fa5799896..a74a2a9a3b 100644
--- a/src/or/router.c
+++ b/src/or/router.c
@@ -23,6 +23,7 @@
 #include "networkstatus.h"
 #include "nodelist.h"
 #include "policies.h"
+#include "protover.h"
 #include "relay.h"
 #include "rephist.h"
 #include "router.h"
@@ -2125,6 +2126,8 @@ router_build_fresh_descriptor(routerinfo_t **r, extrainfo_t **e)
   get_platform_str(platform, sizeof(platform));
   ri->platform = tor_strdup(platform);
 
+  ri->protocol_list = tor_strdup(protover_get_supported_protocols());
+
   /* compute ri->bandwidthrate as the min of various options */
   ri->bandwidthrate = get_effective_bwrate(options);
 
@@ -2617,6 +2620,7 @@ router_dump_router_to_string(routerinfo_t *router,
   char *ed_cert_line = NULL;
   char *rsa_tap_cc_line = NULL;
   char *ntor_cc_line = NULL;
+  char *proto_line = NULL;
 
   /* Make sure the identity key matches the one in the routerinfo. */
   if (!crypto_pk_eq_keys(ident_key, router->identity_pkey)) {
@@ -2781,6 +2785,12 @@ router_dump_router_to_string(routerinfo_t *router,
     }
   }
 
+  if (router->protocol_list) {
+    tor_asprintf(&proto_line, "proto %s\n", router->protocol_list);
+  } else {
+    proto_line = tor_strdup("");
+  }
+
   address = tor_dup_ip(router->addr);
   chunks = smartlist_new();
 
@@ -2790,7 +2800,7 @@ router_dump_router_to_string(routerinfo_t *router,
                     "%s"
                     "%s"
                     "platform %s\n"
-                    "protocols Link 1 2 Circuit 1\n"
+                    "%s"
                     "published %s\n"
                     "fingerprint %s\n"
                     "uptime %ld\n"
@@ -2807,6 +2817,7 @@ router_dump_router_to_string(routerinfo_t *router,
     ed_cert_line ? ed_cert_line : "",
     extra_or_address ? extra_or_address : "",
     router->platform,
+    proto_line,
     published,
     fingerprint,
     stats_n_seconds_working,
diff --git a/src/or/routerlist.c b/src/or/routerlist.c
index 74b8d1b1d3..0e637f4833 100644
--- a/src/or/routerlist.c
+++ b/src/or/routerlist.c
@@ -3102,6 +3102,7 @@ routerinfo_free(routerinfo_t *router)
   tor_free(router->cache_info.signed_descriptor_body);
   tor_free(router->nickname);
   tor_free(router->platform);
+  tor_free(router->protocol_list);
   tor_free(router->contact_info);
   if (router->onion_pkey)
     crypto_pk_free(router->onion_pkey);
@@ -5525,7 +5526,8 @@ routerinfo_has_curve25519_onion_key(const routerinfo_t *ri)
 }
 
 /* Is rs running a tor version known to support ntor?
- * If allow_unknown_versions is true, return true if the version is unknown.
+ * If allow_unknown_versions is true, return true if we can't tell
+ * (from a versions line or a protocols line) whether it supports ntor.
  * Otherwise, return false if the version is unknown. */
 int
 routerstatus_version_supports_ntor(const routerstatus_t *rs,
@@ -5535,11 +5537,11 @@ routerstatus_version_supports_ntor(const routerstatus_t *rs,
     return allow_unknown_versions;
   }
 
-  if (!rs->version_known) {
+  if (!rs->protocols_known) {
     return allow_unknown_versions;
   }
 
-  return rs->version_supports_extend2_cells;
+  return rs->supports_extend2_cells;
 }
 
 /** Assert that the internal representation of <b>rl</b> is
diff --git a/src/or/routerparse.c b/src/or/routerparse.c
index 03f8f4eded..d5690c1101 100644
--- a/src/or/routerparse.c
+++ b/src/or/routerparse.c
@@ -17,6 +17,7 @@
 #include "dirserv.h"
 #include "dirvote.h"
 #include "policies.h"
+#include "protover.h"
 #include "rendcommon.h"
 #include "router.h"
 #include "routerlist.h"
@@ -58,6 +59,7 @@ typedef enum {
   K_RUNNING_ROUTERS,
   K_ROUTER_STATUS,
   K_PLATFORM,
+  K_PROTO,
   K_OPT,
   K_BANDWIDTH,
   K_CONTACT,
@@ -74,6 +76,10 @@ typedef enum {
   K_DIR_OPTIONS,
   K_CLIENT_VERSIONS,
   K_SERVER_VERSIONS,
+  K_RECOMMENDED_CLIENT_PROTOCOLS,
+  K_RECOMMENDED_RELAY_PROTOCOLS,
+  K_REQUIRED_CLIENT_PROTOCOLS,
+  K_REQUIRED_RELAY_PROTOCOLS,
   K_OR_ADDRESS,
   K_ID,
   K_P,
@@ -306,6 +312,7 @@ static token_rule_t routerdesc_token_table[] = {
   T01("fingerprint",         K_FINGERPRINT,     CONCAT_ARGS, NO_OBJ ),
   T01("hibernating",         K_HIBERNATING,         GE(1),   NO_OBJ ),
   T01("platform",            K_PLATFORM,        CONCAT_ARGS, NO_OBJ ),
+  T01("proto",               K_PROTO,           CONCAT_ARGS, NO_OBJ ),
   T01("contact",             K_CONTACT,         CONCAT_ARGS, NO_OBJ ),
   T01("read-history",        K_READ_HISTORY,        ARGS,    NO_OBJ ),
   T01("write-history",       K_WRITE_HISTORY,       ARGS,    NO_OBJ ),
@@ -382,6 +389,7 @@ static token_rule_t rtrstatus_token_table[] = {
   T01("w",                   K_W,                   ARGS,    NO_OBJ ),
   T0N("m",                   K_M,               CONCAT_ARGS, NO_OBJ ),
   T0N("id",                  K_ID,                  GE(2),   NO_OBJ ),
+  T01("pr",                  K_PROTO,           CONCAT_ARGS, NO_OBJ ),
   T0N("opt",                 K_OPT,             CONCAT_ARGS, OBJ_OK ),
   END_OF_TABLE
 };
@@ -459,6 +467,14 @@ static token_rule_t networkstatus_token_table[] = {
   T01("shared-rand-previous-value", K_PREVIOUS_SRV,EQ(2),       NO_OBJ ),
   T01("shared-rand-current-value",  K_CURRENT_SRV, EQ(2),       NO_OBJ ),
   T0N("package",               K_PACKAGE,          CONCAT_ARGS, NO_OBJ ),
+  T01("recommended-client-protocols", K_RECOMMENDED_CLIENT_PROTOCOLS,
+      CONCAT_ARGS, NO_OBJ ),
+  T01("recommended-relay-protocols", K_RECOMMENDED_RELAY_PROTOCOLS,
+      CONCAT_ARGS, NO_OBJ ),
+  T01("required-client-protocols",    K_REQUIRED_CLIENT_PROTOCOLS,
+      CONCAT_ARGS, NO_OBJ ),
+  T01("required-relay-protocols",    K_REQUIRED_RELAY_PROTOCOLS,
+      CONCAT_ARGS, NO_OBJ ),
 
   CERTIFICATE_MEMBERS
 
@@ -500,6 +516,15 @@ static token_rule_t networkstatus_consensus_token_table[] = {
   T01("shared-rand-previous-value", K_PREVIOUS_SRV, EQ(2),   NO_OBJ ),
   T01("shared-rand-current-value",  K_CURRENT_SRV,  EQ(2),   NO_OBJ ),
 
+  T01("recommended-client-protocols", K_RECOMMENDED_CLIENT_PROTOCOLS,
+      CONCAT_ARGS, NO_OBJ ),
+  T01("recommended-relay-protocols", K_RECOMMENDED_RELAY_PROTOCOLS,
+      CONCAT_ARGS, NO_OBJ ),
+  T01("required-client-protocols",    K_REQUIRED_CLIENT_PROTOCOLS,
+      CONCAT_ARGS, NO_OBJ ),
+  T01("required-relay-protocols",    K_REQUIRED_RELAY_PROTOCOLS,
+      CONCAT_ARGS, NO_OBJ ),
+
   END_OF_TABLE
 };
 
@@ -2092,6 +2117,10 @@ router_parse_entry_from_string(const char *s, const char *end,
     router->platform = tor_strdup(tok->args[0]);
   }
 
+  if ((tok = find_opt_by_keyword(tokens, K_PROTO))) {
+    router->protocol_list = tor_strdup(tok->args[0]);
+  }
+
   if ((tok = find_opt_by_keyword(tokens, K_CONTACT))) {
     router->contact_info = tor_strdup(tok->args[0]);
   }
@@ -2876,13 +2905,22 @@ routerstatus_parse_entry_from_string(memarea_t *area,
       }
     }
   }
+  int found_protocol_list = 0;
+  if ((tok = find_opt_by_keyword(tokens, K_PROTO))) {
+    found_protocol_list = 1;
+    rs->protocols_known = 1;
+    rs->supports_extend2_cells =
+      protocol_list_supports_protocol(tok->args[0], PRT_RELAY, 2);
+  }
   if ((tok = find_opt_by_keyword(tokens, K_V))) {
     tor_assert(tok->n_args == 1);
-    rs->version_known = 1;
-    if (strcmpstart(tok->args[0], "Tor ")) {
-    } else {
-      rs->version_supports_extend2_cells =
+    if (!strcmpstart(tok->args[0], "Tor ") && !found_protocol_list) {
+      /* We only do version checks like this in the case where
+       * the version is a "Tor" version, and where there is no
+       * list of protocol versions that we should be looking at instead. */
+      rs->supports_extend2_cells =
         tor_version_as_new_as(tok->args[0], "0.2.4.8-alpha");
+      rs->protocols_known = 1;
     }
     if (vote_rs) {
       vote_rs->version = tor_strdup(tok->args[0]);
@@ -2965,6 +3003,10 @@ routerstatus_parse_entry_from_string(memarea_t *area,
           }
         }
       }
+      if (t->tp == K_PROTO) {
+        tor_assert(t->n_args == 1);
+        vote_rs->protocols = tor_strdup(t->args[0]);
+      }
     } SMARTLIST_FOREACH_END(t);
   } else if (flav == FLAV_MICRODESC) {
     tok = find_opt_by_keyword(tokens, K_M);
@@ -3645,6 +3687,15 @@ networkstatus_parse_vote_from_string(const char *s, const char **eos_out,
     }
   }
 
+  if ((tok = find_opt_by_keyword(tokens, K_RECOMMENDED_CLIENT_PROTOCOLS)))
+    ns->recommended_client_protocols = tor_strdup(tok->args[0]);
+  if ((tok = find_opt_by_keyword(tokens, K_RECOMMENDED_RELAY_PROTOCOLS)))
+    ns->recommended_relay_protocols = tor_strdup(tok->args[0]);
+  if ((tok = find_opt_by_keyword(tokens, K_REQUIRED_CLIENT_PROTOCOLS)))
+    ns->required_client_protocols = tor_strdup(tok->args[0]);
+  if ((tok = find_opt_by_keyword(tokens, K_REQUIRED_RELAY_PROTOCOLS)))
+    ns->required_relay_protocols = tor_strdup(tok->args[0]);
+
   tok = find_by_keyword(tokens, K_VALID_AFTER);
   if (parse_iso_time(tok->args[0], &ns->valid_after))
     goto err;
diff --git a/src/test/include.am b/src/test/include.am
index 5bcc969cf0..8ecfaf10c6 100644
--- a/src/test/include.am
+++ b/src/test/include.am
@@ -108,6 +108,7 @@ src_test_test_SOURCES = \
 	src/test/test_options.c \
 	src/test/test_policy.c \
 	src/test/test_procmon.c \
+	src/test/test_protover.c \
 	src/test/test_pt.c \
 	src/test/test_pubsub.c \
 	src/test/test_relay.c \
diff --git a/src/test/test.c b/src/test/test.c
index 2f10c7e90b..9a41b976b8 100644
--- a/src/test/test.c
+++ b/src/test/test.c
@@ -1214,6 +1214,7 @@ struct testgroup_t testgroups[] = {
   { "options/", options_tests },
   { "policy/" , policy_tests },
   { "procmon/", procmon_tests },
+  { "protover/", protover_tests },
   { "pt/", pt_tests },
   { "relay/" , relay_tests },
   { "relaycell/", relaycell_tests },
diff --git a/src/test/test.h b/src/test/test.h
index bf1f53d207..770f403cee 100644
--- a/src/test/test.h
+++ b/src/test/test.h
@@ -207,6 +207,7 @@ extern struct testcase_t oos_tests[];
 extern struct testcase_t options_tests[];
 extern struct testcase_t policy_tests[];
 extern struct testcase_t procmon_tests[];
+extern struct testcase_t protover_tests[];
 extern struct testcase_t pubsub_tests[];
 extern struct testcase_t pt_tests[];
 extern struct testcase_t relay_tests[];
diff --git a/src/test/test_dir.c b/src/test/test_dir.c
index 4a6c5a9b5a..7610ddc399 100644
--- a/src/test/test_dir.c
+++ b/src/test/test_dir.c
@@ -232,7 +232,6 @@ test_dir_formats(void *arg)
           "platform Tor "VERSION" on ", sizeof(buf2));
   strlcat(buf2, get_uname(), sizeof(buf2));
   strlcat(buf2, "\n"
-          "protocols Link 1 2 Circuit 1\n"
           "published 1970-01-01 00:00:00\n"
           "fingerprint ", sizeof(buf2));
   tt_assert(!crypto_pk_get_fingerprint(pk2, fingerprint, 1));
@@ -301,7 +300,6 @@ test_dir_formats(void *arg)
   strlcat(buf2, "platform Tor "VERSION" on ", sizeof(buf2));
   strlcat(buf2, get_uname(), sizeof(buf2));
   strlcat(buf2, "\n"
-          "protocols Link 1 2 Circuit 1\n"
           "published 1970-01-01 00:00:05\n"
           "fingerprint ", sizeof(buf2));
   tt_assert(!crypto_pk_get_fingerprint(pk1, fingerprint, 1));
diff --git a/src/test/test_protover.c b/src/test/test_protover.c
new file mode 100644
index 0000000000..f00955d1b4
--- /dev/null
+++ b/src/test/test_protover.c
@@ -0,0 +1,195 @@
+/* Copyright (c) 2016, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#define PROTOVER_PRIVATE
+
+#include "orconfig.h"
+#include "test.h"
+
+#include "protover.h"
+
+static void
+test_protover_parse(void *arg)
+{
+  (void) arg;
+  char *re_encoded = NULL;
+
+  const char *orig = "Foo=1,3 Bar=3 Baz= Quux=9-12,14,15-16,900";
+  smartlist_t *elts = parse_protocol_list(orig);
+
+  tt_assert(elts);
+  tt_int_op(smartlist_len(elts), OP_EQ, 4);
+
+  const proto_entry_t *e;
+  const proto_range_t *r;
+  e = smartlist_get(elts, 0);
+  tt_str_op(e->name, OP_EQ, "Foo");
+  tt_int_op(smartlist_len(e->ranges), OP_EQ, 2);
+  {
+    r = smartlist_get(e->ranges, 0);
+    tt_int_op(r->low, OP_EQ, 1);
+    tt_int_op(r->high, OP_EQ, 1);
+
+    r = smartlist_get(e->ranges, 1);
+    tt_int_op(r->low, OP_EQ, 3);
+    tt_int_op(r->high, OP_EQ, 3);
+  }
+
+  e = smartlist_get(elts, 1);
+  tt_str_op(e->name, OP_EQ, "Bar");
+  tt_int_op(smartlist_len(e->ranges), OP_EQ, 1);
+  {
+    r = smartlist_get(e->ranges, 0);
+    tt_int_op(r->low, OP_EQ, 3);
+    tt_int_op(r->high, OP_EQ, 3);
+  }
+
+  e = smartlist_get(elts, 2);
+  tt_str_op(e->name, OP_EQ, "Baz");
+  tt_int_op(smartlist_len(e->ranges), OP_EQ, 0);
+
+  e = smartlist_get(elts, 3);
+  tt_str_op(e->name, OP_EQ, "Quux");
+  tt_int_op(smartlist_len(e->ranges), OP_EQ, 4);
+  {
+    r = smartlist_get(e->ranges, 0);
+    tt_int_op(r->low, OP_EQ, 9);
+    tt_int_op(r->high, OP_EQ, 12);
+
+    r = smartlist_get(e->ranges, 1);
+    tt_int_op(r->low, OP_EQ, 14);
+    tt_int_op(r->high, OP_EQ, 14);
+
+    r = smartlist_get(e->ranges, 2);
+    tt_int_op(r->low, OP_EQ, 15);
+    tt_int_op(r->high, OP_EQ, 16);
+
+    r = smartlist_get(e->ranges, 3);
+    tt_int_op(r->low, OP_EQ, 900);
+    tt_int_op(r->high, OP_EQ, 900);
+  }
+
+  re_encoded = encode_protocol_list(elts);
+  tt_assert(re_encoded);
+  tt_str_op(re_encoded, OP_EQ, orig);
+
+ done:
+  if (elts)
+    SMARTLIST_FOREACH(elts, proto_entry_t *, ent, proto_entry_free(ent));
+  smartlist_free(elts);
+  tor_free(re_encoded);
+}
+
+static void
+test_protover_parse_fail(void *arg)
+{
+  (void)arg;
+  smartlist_t *elts;
+
+  /* random junk */
+  elts = parse_protocol_list("!!3@*");
+  tt_assert(elts == NULL);
+
+  /* Missing equals sign in an entry */
+  elts = parse_protocol_list("Link=4 Haprauxymatyve Desc=9");
+  tt_assert(elts == NULL);
+
+  /* Missing word. */
+  elts = parse_protocol_list("Link=4 =3 Desc=9");
+  tt_assert(elts == NULL);
+
+  /* Broken numbers */
+  elts = parse_protocol_list("Link=fred");
+  tt_assert(elts == NULL);
+  elts = parse_protocol_list("Link=1,fred");
+  tt_assert(elts == NULL);
+  elts = parse_protocol_list("Link=1,fred,3");
+  tt_assert(elts == NULL);
+
+  /* Broken range */
+  elts = parse_protocol_list("Link=1,9-8,3");
+  tt_assert(elts == NULL);
+
+ done:
+  ;
+}
+
+static void
+test_protover_vote(void *arg)
+{
+  (void) arg;
+
+  smartlist_t *lst = smartlist_new();
+  char *result = protover_compute_vote(lst, 1);
+
+  tt_str_op(result, OP_EQ, "");
+  tor_free(result);
+
+  smartlist_add(lst, (void*) "Foo=1-10,500 Bar=1,3-7,8");
+  result = protover_compute_vote(lst, 1);
+  tt_str_op(result, OP_EQ, "Bar=1,3-8 Foo=1-10,500");
+  tor_free(result);
+
+  smartlist_add(lst, (void*) "Quux=123-456,78 Bar=2-6,8 Foo=9");
+  result = protover_compute_vote(lst, 1);
+  tt_str_op(result, OP_EQ, "Bar=1-8 Foo=1-10,500 Quux=78,123-456");
+  tor_free(result);
+
+  result = protover_compute_vote(lst, 2);
+  tt_str_op(result, OP_EQ, "Bar=3-6,8 Foo=9");
+  tor_free(result);
+
+ done:
+  tor_free(result);
+  smartlist_free(lst);
+}
+
+static void
+test_protover_all_supported(void *arg)
+{
+  (void)arg;
+  char *msg = NULL;
+
+  tt_assert(protover_all_supported(NULL, &msg));
+  tt_assert(msg == NULL);
+
+  tt_assert(protover_all_supported("", &msg));
+  tt_assert(msg == NULL);
+
+  // Some things that we do support
+  tt_assert(protover_all_supported("Link=3-4", &msg));
+  tt_assert(msg == NULL);
+  tt_assert(protover_all_supported("Link=3-4 Desc=2", &msg));
+  tt_assert(msg == NULL);
+
+  // Some things we don't support
+  tt_assert(! protover_all_supported("Wombat=9", &msg));
+  tt_str_op(msg, OP_EQ, "Wombat=9");
+  tor_free(msg);
+  tt_assert(! protover_all_supported("Link=999", &msg));
+  tt_str_op(msg, OP_EQ, "Link=999");
+  tor_free(msg);
+
+  // Mix of things we support and things we don't
+  tt_assert(! protover_all_supported("Link=3-4 Wombat=9", &msg));
+  tt_str_op(msg, OP_EQ, "Wombat=9");
+  tor_free(msg);
+  tt_assert(! protover_all_supported("Link=3-999", &msg));
+  tt_str_op(msg, OP_EQ, "Link=3-999");
+  tor_free(msg);
+
+ done:
+  tor_free(msg);
+}
+
+#define PV_TEST(name, flags)                       \
+  { #name, test_protover_ ##name, (flags), NULL, NULL }
+
+struct testcase_t protover_tests[] = {
+  PV_TEST(parse, 0),
+  PV_TEST(parse_fail, 0),
+  PV_TEST(vote, 0),
+  PV_TEST(all_supported, 0),
+  END_OF_TESTCASES
+};
+