Merge remote-tracking branch 'public/prop298'

7 files changed, 224 insertions, 69 deletions

diff --git a/src/feature/dirauth/dirvote.c b/src/feature/dirauth/dirvote.c
index c6a2193087..d8a18835f2 100644
--- a/src/feature/dirauth/dirvote.c
+++ b/src/feature/dirauth/dirvote.c
@@ -28,6 +28,7 @@
 #include "feature/nodelist/fmt_routerstatus.h"
 #include "feature/nodelist/microdesc.h"
 #include "feature/nodelist/networkstatus.h"
+#include "feature/nodelist/nodefamily.h"
 #include "feature/nodelist/nodelist.h"
 #include "feature/nodelist/routerlist.h"
 #include "feature/relay/router.h"
@@ -3799,8 +3800,16 @@ dirvote_create_microdescriptor(const routerinfo_t *ri, int consensus_method)
     smartlist_add_asprintf(chunks, "a %s\n",
                            fmt_addrport(&ri->ipv6_addr, ri->ipv6_orport));
 
-  if (family)
-    smartlist_add_asprintf(chunks, "family %s\n", family);
+  if (family) {
+    if (consensus_method < MIN_METHOD_FOR_CANONICAL_FAMILIES_IN_MICRODESCS) {
+      smartlist_add_asprintf(chunks, "family %s\n", family);
+    } else {
+      const uint8_t *id = (const uint8_t *)ri->cache_info.identity_digest;
+      char *canonical_family = nodefamily_canonicalize(family, id, 0);
+      smartlist_add_asprintf(chunks, "family %s\n", canonical_family);
+      tor_free(canonical_family);
+    }
+  }
 
   if (summary && strcmp(summary, "reject 1-65535"))
     smartlist_add_asprintf(chunks, "p %s\n", summary);
@@ -3898,7 +3907,10 @@ static const struct consensus_method_range_t {
   int high;
 } microdesc_consensus_methods[] = {
   {MIN_SUPPORTED_CONSENSUS_METHOD, MIN_METHOD_FOR_NO_A_LINES_IN_MICRODESC - 1},
-  {MIN_METHOD_FOR_NO_A_LINES_IN_MICRODESC, MAX_SUPPORTED_CONSENSUS_METHOD},
+  {MIN_METHOD_FOR_NO_A_LINES_IN_MICRODESC,
+   MIN_METHOD_FOR_CANONICAL_FAMILIES_IN_MICRODESCS - 1},
+  {MIN_METHOD_FOR_CANONICAL_FAMILIES_IN_MICRODESCS,
+   MAX_SUPPORTED_CONSENSUS_METHOD},
   {-1, -1}
 };
 
diff --git a/src/feature/dirauth/dirvote.h b/src/feature/dirauth/dirvote.h
index f99cc2d2bf..85f4800700 100644
--- a/src/feature/dirauth/dirvote.h
+++ b/src/feature/dirauth/dirvote.h
@@ -57,7 +57,7 @@
 #define MIN_SUPPORTED_CONSENSUS_METHOD 25
 
 /** The highest consensus method that we currently support. */
-#define MAX_SUPPORTED_CONSENSUS_METHOD 28
+#define MAX_SUPPORTED_CONSENSUS_METHOD 29
 
 /** Lowest consensus method where authorities vote on required/recommended
  * protocols. */
@@ -79,6 +79,12 @@
  * addresses. See #23828 and #20916. */
 #define MIN_METHOD_FOR_NO_A_LINES_IN_MICRODESC 28
 
+/**
+ * Lowest consensus method where microdescriptor lines are put in canonical
+ * form for improved compressibility and ease of storage. See proposal 298.
+ **/
+#define MIN_METHOD_FOR_CANONICAL_FAMILIES_IN_MICRODESCS 29
+
 /** 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/feature/nodelist/nodefamily.c b/src/feature/nodelist/nodefamily.c
index 6b504c0ac4..944ad54755 100644
--- a/src/feature/nodelist/nodefamily.c
+++ b/src/feature/nodelist/nodefamily.c
@@ -93,13 +93,47 @@ nodefamily_parse(const char *s, const uint8_t *rsa_id_self,
 {
   smartlist_t *sl = smartlist_new();
   smartlist_split_string(sl, s, NULL, SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
-  nodefamily_t *result = nodefamily_from_members(sl, rsa_id_self, flags);
+  nodefamily_t *result = nodefamily_from_members(sl, rsa_id_self, flags, NULL);
   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
   smartlist_free(sl);
   return result;
 }
 
 /**
+ * Canonicalize the family list <b>s</b>, returning a newly allocated string.
+ *
+ * The canonicalization rules are fully specified in dir-spec.txt, but,
+ * briefly: $hexid entries are put in caps, $hexid[=~]foo entries are
+ * truncated, nicknames are put into lowercase, unrecognized entries are left
+ * alone, and everything is sorted.
+ **/
+char *
+nodefamily_canonicalize(const char *s, const uint8_t *rsa_id_self,
+                        unsigned flags)
+{
+  smartlist_t *sl = smartlist_new();
+  smartlist_t *result_members = smartlist_new();
+  smartlist_split_string(sl, s, NULL, SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
+  nodefamily_t *nf = nodefamily_from_members(sl, rsa_id_self, flags,
+                                             result_members);
+
+  char *formatted = nodefamily_format(nf);
+  smartlist_split_string(result_members, formatted, NULL,
+                         SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
+  smartlist_sort_strings(result_members);
+  char *combined = smartlist_join_strings(result_members, " ", 0, NULL);
+
+  nodefamily_free(nf);
+  SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
+  smartlist_free(sl);
+  SMARTLIST_FOREACH(result_members, char *, cp, tor_free(cp));
+  smartlist_free(result_members);
+  tor_free(formatted);
+
+  return combined;
+}
+
+/**
  * qsort helper for encoded nodefamily elements.
  **/
 static int
@@ -117,11 +151,15 @@ compare_members(const void *a, const void *b)
  * family declaration if it is not there already.
  *
  * The <b>flags</b> element is interpreted as in nodefamily_parse().
+ *
+ * If <b>unrecognized</b> is provided, fill it copies of any unrecognized
+ * members.  (Note that malformed $hexids are not considered unrecognized.)
  **/
 nodefamily_t *
 nodefamily_from_members(const smartlist_t *members,
                         const uint8_t *rsa_id_self,
-                        unsigned flags)
+                        unsigned flags,
+                        smartlist_t *unrecognized_out)
 {
   const int n_self = rsa_id_self ? 1 : 0;
   int n_bad_elements = 0;
@@ -135,6 +173,7 @@ nodefamily_from_members(const smartlist_t *members,
       ptr[0] = NODEFAMILY_BY_NICKNAME;
       tor_assert(strlen(cp) < DIGEST_LEN); // guaranteed by is_legal_nickname
       memcpy(ptr+1, cp, strlen(cp));
+      tor_strlower((char*) ptr+1);
       bad_element = false;
     } else if (is_legal_hexdigest(cp)) {
       char digest_buf[DIGEST_LEN];
@@ -145,6 +184,9 @@ nodefamily_from_members(const smartlist_t *members,
         ptr[0] = NODEFAMILY_BY_RSA_ID;
         memcpy(ptr+1, digest_buf, DIGEST_LEN);
       }
+    } else {
+      if (unrecognized_out)
+        smartlist_add_strdup(unrecognized_out, cp);
     }
 
     if (bad_element) {
@@ -346,6 +388,7 @@ nodefamily_format(const nodefamily_t *family)
         char buf[HEX_DIGEST_LEN+2];
         buf[0]='$';
         base16_encode(buf+1, sizeof(buf)-1, (char*)ptr+1, DIGEST_LEN);
+        tor_strupper(buf);
         smartlist_add_strdup(sl, buf);
         break;
       }
diff --git a/src/feature/nodelist/nodefamily.h b/src/feature/nodelist/nodefamily.h
index 342f161a07..ea1076876d 100644
--- a/src/feature/nodelist/nodefamily.h
+++ b/src/feature/nodelist/nodefamily.h
@@ -27,7 +27,8 @@ nodefamily_t *nodefamily_parse(const char *s,
                                unsigned flags);
 nodefamily_t *nodefamily_from_members(const struct smartlist_t *members,
                                       const uint8_t *rsa_id_self,
-                                      unsigned flags);
+                                      unsigned flags,
+                                      smartlist_t *unrecognized_out);
 void nodefamily_free_(nodefamily_t *family);
 #define nodefamily_free(family) \
   FREE_AND_NULL(nodefamily_t, nodefamily_free_, (family))
@@ -41,6 +42,8 @@ bool nodefamily_contains_node(const nodefamily_t *family,
 void nodefamily_add_nodes_to_smartlist(const nodefamily_t *family,
                                        struct smartlist_t *out);
 char *nodefamily_format(const nodefamily_t *family);
+char *nodefamily_canonicalize(const char *s, const uint8_t *rsa_id_self,
+                              unsigned flags);
 
 void nodefamily_free_all(void);
 
diff --git a/src/feature/nodelist/nodefamily_st.h b/src/feature/nodelist/nodefamily_st.h
index f88ada494a..a498b4b3b9 100644
--- a/src/feature/nodelist/nodefamily_st.h
+++ b/src/feature/nodelist/nodefamily_st.h
@@ -26,12 +26,12 @@ struct nodefamily_t {
 
 #define NODEFAMILY_MEMBER_LEN (1+DIGEST_LEN)
 
-/** Tag byte, indicates that the following bytes are a NUL-padded nickname.
- */
-#define NODEFAMILY_BY_NICKNAME 0
 /** Tag byte, indicates that the following bytes are a RSA1024 SHA1 ID.
  */
-#define NODEFAMILY_BY_RSA_ID 1
+#define NODEFAMILY_BY_RSA_ID 0
+/** Tag byte, indicates that the following bytes are a NUL-padded nickname.
+ */
+#define NODEFAMILY_BY_NICKNAME 1
 
 /**
  * Number of bytes to allocate in the array for a nodefamily_t with N members.
diff --git a/src/feature/relay/router.c b/src/feature/relay/router.c
index ef433db8bc..be9ef3d2f3 100644
--- a/src/feature/relay/router.c
+++ b/src/feature/relay/router.c
@@ -30,6 +30,7 @@
 #include "feature/nodelist/dirlist.h"
 #include "feature/nodelist/networkstatus.h"
 #include "feature/nodelist/nickname.h"
+#include "feature/nodelist/nodefamily.h"
 #include "feature/nodelist/nodelist.h"
 #include "feature/nodelist/routerlist.h"
 #include "feature/nodelist/torcert.h"
@@ -341,6 +342,16 @@ set_server_identity_key(crypto_pk_t *k)
   }
 }
 
+#ifdef TOR_UNIT_TESTS
+/** Testing only -- set the server's RSA identity digest to
+ * be <b>digest</b> */
+void
+set_server_identity_key_digest_testing(const uint8_t *digest)
+{
+  memcpy(server_identitykey_digest, digest, DIGEST_LEN);
+}
+#endif
+
 /** Make sure that we have set up our identity keys to match or not match as
  * appropriate, and die with an assertion if we have not. */
 static void
@@ -1692,10 +1703,6 @@ router_get_descriptor_gen_reason(void)
   return desc_gen_reason;
 }
 
-/** A list of nicknames that we've warned about including in our family
- * declaration verbatim rather than as digests. */
-static smartlist_t *warned_nonexistent_family = NULL;
-
 static int router_guess_address_from_dir_headers(uint32_t *guess);
 
 /** Make a current best guess at our address, either because
@@ -1808,6 +1815,132 @@ router_check_descriptor_address_consistency(uint32_t ipv4h_desc_addr)
                                                    CONN_TYPE_DIR_LISTENER);
 }
 
+/** A list of nicknames that we've warned about including in our family,
+ * for one reason or another. */
+static smartlist_t *warned_family = NULL;
+
+/**
+ * Return a new smartlist containing the family members configured in
+ * <b>options</b>.  Warn about invalid or missing entries.  Return NULL
+ * if this relay should not declare a family.
+ **/
+STATIC smartlist_t *
+get_my_declared_family(const or_options_t *options)
+{
+  if (!options->MyFamily)
+    return NULL;
+
+  if (options->BridgeRelay)
+    return NULL;
+
+  if (!warned_family)
+    warned_family = smartlist_new();
+
+  smartlist_t *declared_family = smartlist_new();
+  config_line_t *family;
+
+  /* First we try to get the whole family in the form of hexdigests. */
+  for (family = options->MyFamily; family; family = family->next) {
+    char *name = family->value;
+    const node_t *member;
+    if (options->Nickname && !strcasecmp(name, options->Nickname))
+      continue; /* Don't list ourself by nickname, that's redundant */
+    else
+      member = node_get_by_nickname(name, 0);
+
+    if (!member) {
+      /* This node doesn't seem to exist, so warn about it if it is not
+       * a hexdigest. */
+      int is_legal = is_legal_nickname_or_hexdigest(name);
+      if (!smartlist_contains_string(warned_family, name) &&
+          !is_legal_hexdigest(name)) {
+        if (is_legal)
+          log_warn(LD_CONFIG,
+                   "There is a router named %s in my declared family, but "
+                   "I have no descriptor for it. I'll use the nickname "
+                   "as is, but this may confuse clients. Please list it "
+                   "by identity digest instead.", escaped(name));
+        else
+          log_warn(LD_CONFIG, "There is a router named %s in my declared "
+                   "family, but that isn't a legal digest or nickname. "
+                   "Skipping it.", escaped(name));
+        smartlist_add_strdup(warned_family, name);
+      }
+      if (is_legal) {
+        smartlist_add_strdup(declared_family, name);
+      }
+    } else {
+      /* List the node by digest. */
+      char *fp = tor_malloc(HEX_DIGEST_LEN+2);
+      fp[0] = '$';
+      base16_encode(fp+1,HEX_DIGEST_LEN+1,
+                    member->identity, DIGEST_LEN);
+      smartlist_add(declared_family, fp);
+
+      if (! is_legal_hexdigest(name) &&
+          !smartlist_contains_string(warned_family, name)) {
+        /* Warn if this node was not specified by hexdigest. */
+        log_warn(LD_CONFIG, "There is a router named %s in my declared "
+                 "family, but it wasn't listed by digest. Please consider "
+                 "saying %s instead, if that's what you meant.",
+                 escaped(name), fp);
+        smartlist_add_strdup(warned_family, name);
+      }
+    }
+  }
+
+  /* Now declared_family should have the closest we can come to the
+   * identities that the user wanted.
+   *
+   * Unlike older versions of Tor, we _do_ include our own identity: this
+   * helps microdescriptor compression, and helps in-memory compression
+   * on clients. */
+  nodefamily_t *nf = nodefamily_from_members(declared_family,
+                                     router_get_my_id_digest(),
+                                     NF_WARN_MALFORMED,
+                                     NULL);
+  SMARTLIST_FOREACH(declared_family, char *, s, tor_free(s));
+  smartlist_free(declared_family);
+  if (!nf) {
+    return NULL;
+  }
+
+  char *s = nodefamily_format(nf);
+  nodefamily_free(nf);
+
+  smartlist_t *result = smartlist_new();
+  smartlist_split_string(result, s, NULL,
+                         SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
+  tor_free(s);
+
+  if (smartlist_len(result) == 1) {
+    /* This is a one-element list containing only ourself; instead return
+     * nothing */
+    const char *singleton = smartlist_get(result, 0);
+    bool is_me = false;
+    if (singleton[0] == '$') {
+      char d[DIGEST_LEN];
+      int n = base16_decode(d, sizeof(d), singleton+1, strlen(singleton+1));
+      if (n == DIGEST_LEN &&
+          fast_memeq(d, router_get_my_id_digest(), DIGEST_LEN)) {
+        is_me = true;
+      }
+    }
+    if (!is_me) {
+      // LCOV_EXCL_START
+      log_warn(LD_BUG, "Found a singleton family list with an element "
+               "that wasn't us! Element was %s", escaped(singleton));
+      // LCOV_EXCL_STOP
+    } else {
+      SMARTLIST_FOREACH(result, char *, cp, tor_free(cp));
+      smartlist_free(result);
+      return NULL;
+    }
+  }
+
+  return result;
+}
+
 /** Build a fresh routerinfo, signed server descriptor, and extra-info document
  * for this OR. Set r to the generated routerinfo, e to the generated
  * extra-info document. Return 0 on success, -1 on temporary error. Failure to
@@ -1922,54 +2055,7 @@ router_build_fresh_descriptor(routerinfo_t **r, extrainfo_t **e)
     tor_free(p_tmp);
   }
 
-  if (options->MyFamily && ! options->BridgeRelay) {
-    if (!warned_nonexistent_family)
-      warned_nonexistent_family = smartlist_new();
-    ri->declared_family = smartlist_new();
-    config_line_t *family;
-    for (family = options->MyFamily; family; family = family->next) {
-       char *name = family->value;
-       const node_t *member;
-       if (!strcasecmp(name, options->Nickname))
-         continue; /* Don't list ourself, that's redundant */
-       else
-         member = node_get_by_nickname(name, 0);
-       if (!member) {
-         int is_legal = is_legal_nickname_or_hexdigest(name);
-         if (!smartlist_contains_string(warned_nonexistent_family, name) &&
-             !is_legal_hexdigest(name)) {
-           if (is_legal)
-             log_warn(LD_CONFIG,
-                      "I have no descriptor for the router named \"%s\" in my "
-                      "declared family; I'll use the nickname as is, but "
-                      "this may confuse clients.", name);
-           else
-             log_warn(LD_CONFIG, "There is a router named \"%s\" in my "
-                      "declared family, but that isn't a legal nickname. "
-                      "Skipping it.", escaped(name));
-           smartlist_add_strdup(warned_nonexistent_family, name);
-         }
-         if (is_legal) {
-           smartlist_add_strdup(ri->declared_family, name);
-         }
-       } else if (router_digest_is_me(member->identity)) {
-         /* Don't list ourself in our own family; that's redundant */
-         /* XXX shouldn't be possible */
-       } else {
-         char *fp = tor_malloc(HEX_DIGEST_LEN+2);
-         fp[0] = '$';
-         base16_encode(fp+1,HEX_DIGEST_LEN+1,
-                       member->identity, DIGEST_LEN);
-         smartlist_add(ri->declared_family, fp);
-         if (smartlist_contains_string(warned_nonexistent_family, name))
-           smartlist_string_remove(warned_nonexistent_family, name);
-       }
-    }
-
-    /* remove duplicates from the list */
-    smartlist_sort_strings(ri->declared_family);
-    smartlist_uniq_strings(ri->declared_family);
-  }
+  ri->declared_family = get_my_declared_family(options);
 
   /* Now generate the extrainfo. */
   ei = tor_malloc_zero(sizeof(extrainfo_t));
@@ -3064,9 +3150,9 @@ extrainfo_dump_to_string(char **s_out, extrainfo_t *extrainfo,
 void
 router_reset_warnings(void)
 {
-  if (warned_nonexistent_family) {
-    SMARTLIST_FOREACH(warned_nonexistent_family, char *, cp, tor_free(cp));
-    smartlist_clear(warned_nonexistent_family);
+  if (warned_family) {
+    SMARTLIST_FOREACH(warned_family, char *, cp, tor_free(cp));
+    smartlist_clear(warned_family);
   }
 }
 
@@ -3090,11 +3176,12 @@ router_free_all(void)
   memwipe(&curve25519_onion_key, 0, sizeof(curve25519_onion_key));
   memwipe(&last_curve25519_onion_key, 0, sizeof(last_curve25519_onion_key));
 
-  if (warned_nonexistent_family) {
-    SMARTLIST_FOREACH(warned_nonexistent_family, char *, cp, tor_free(cp));
-    smartlist_free(warned_nonexistent_family);
+  if (warned_family) {
+    SMARTLIST_FOREACH(warned_family, char *, cp, tor_free(cp));
+    smartlist_free(warned_family);
   }
 }
+
 /* From the given RSA key object, convert it to ASN-1 encoded format and set
  * the newly allocated object in onion_pkey_out. The length of the key is set
  * in onion_pkey_len_out. */
diff --git a/src/feature/relay/router.h b/src/feature/relay/router.h
index 217511df9f..7a63c33d32 100644
--- a/src/feature/relay/router.h
+++ b/src/feature/relay/router.h
@@ -117,10 +117,14 @@ void router_free_all(void);
 /* Used only by router.c and test.c */
 STATIC void get_platform_str(char *platform, size_t len);
 STATIC int router_write_fingerprint(int hashed);
+STATIC smartlist_t *get_my_declared_family(const or_options_t *options);
+
 #ifdef TOR_UNIT_TESTS
 extern time_t desc_clean_since;
 extern const char *desc_dirty_reason;
+void set_server_identity_key_digest_testing(const uint8_t *digest);
 #endif
+
 #endif
 
 #endif /* !defined(TOR_ROUTER_H) */