Merge branch 'prop140_complete_rebased'

13 files changed, 536 insertions, 202 deletions

diff --git a/changes/prop140 b/changes/prop140
new file mode 100644
index 0000000000..04a30dcb57
--- /dev/null
+++ b/changes/prop140
@@ -0,0 +1,9 @@
+  o Major features (directory protocol):
+    - Tor relays and authorities are now able to serve clients an
+      abbreviated version of the networkstatus consensus document,
+      containing only the changes since the an older consensus document that
+      the client holds. Clients now request these documents when
+      available. When this new protocol is in use by both client and server,
+      they will use far less bandwidth (up to 94% less) to keep an up-to-date
+      consensus. Implements proposal 140; closes ticket 13339.
+
diff --git a/src/or/consdiff.c b/src/or/consdiff.c
index 3c2140b642..1baa11897c 100644
--- a/src/or/consdiff.c
+++ b/src/or/consdiff.c
@@ -1401,3 +1401,12 @@ consensus_diff_apply(const char *consensus,
   return result;
 }
 
+/** Return true iff, based on its header, <b>document</b> is likely
+ * to be a consensus diff. */
+int
+looks_like_a_consensus_diff(const char *document, size_t len)
+{
+  return (len >= strlen(ns_diff_version) &&
+          fast_memeq(document, ns_diff_version, strlen(ns_diff_version)));
+}
+
diff --git a/src/or/consdiff.h b/src/or/consdiff.h
index 284a576525..d05df74b75 100644
--- a/src/or/consdiff.h
+++ b/src/or/consdiff.h
@@ -12,6 +12,8 @@ char *consensus_diff_generate(const char *cons1,
 char *consensus_diff_apply(const char *consensus,
                            const char *diff);
 
+int looks_like_a_consensus_diff(const char *document, size_t len);
+
 #ifdef CONSDIFF_PRIVATE
 struct memarea_t;
 
diff --git a/src/or/consdiffmgr.c b/src/or/consdiffmgr.c
index 96b0bba900..d478101c6b 100644
--- a/src/or/consdiffmgr.c
+++ b/src/or/consdiffmgr.c
@@ -858,9 +858,12 @@ consdiffmgr_rescan_flavor_(consensus_flavor_t flavor)
       continue; // LCOV_EXCL_LINE
 
     uint8_t this_sha3[DIGEST256_LEN];
-    if (BUG(cdm_entry_get_sha3_value(this_sha3, c,
-                                     LABEL_SHA3_DIGEST_AS_SIGNED)<0))
-      continue; // LCOV_EXCL_LINE
+    if (cdm_entry_get_sha3_value(this_sha3, c,
+                                 LABEL_SHA3_DIGEST_AS_SIGNED)<0) {
+      // Not actually a bug, since we might be running with a directory
+      // with stale files from before the #22143 fixes.
+      continue;
+    }
     if (cdm_diff_ht_check_and_note_pending(flavor,
                                            this_sha3, most_recent_sha3)) {
       // This is already pending, or we encountered an error.
diff --git a/src/or/directory.c b/src/or/directory.c
index 48bada21bd..8b63e4df1f 100644
--- a/src/or/directory.c
+++ b/src/or/directory.c
@@ -13,6 +13,8 @@
 #include "config.h"
 #include "connection.h"
 #include "connection_edge.h"
+#include "consdiff.h"
+#include "consdiffmgr.h"
 #include "control.h"
 #include "compat.h"
 #define DIRECTORY_PRIVATE
@@ -129,6 +131,7 @@ static void directory_request_set_guard_state(directory_request_t *req,
 #define ALLOW_DIRECTORY_TIME_SKEW (30*60)
 
 #define X_ADDRESS_HEADER "X-Your-Address-Is: "
+#define X_OR_DIFF_FROM_CONSENSUS_HEADER "X-Or-Diff-From-Consensus: "
 
 /** HTTP cache control: how long do we tell proxies they can cache each
  * kind of document we serve? */
@@ -476,6 +479,70 @@ directory_pick_generic_dirserver(dirinfo_type_t type, int pds_flags,
   return rs;
 }
 
+/**
+ * Set the extra fields in <b>req</b> that are used when requesting a
+ * consensus of type <b>resource</b>.
+ *
+ * Right now, these fields are if-modified-since and x-or-diff-from-consensus.
+ */
+static void
+dir_consensus_request_set_additional_headers(directory_request_t *req,
+                                             const char *resource)
+{
+  time_t if_modified_since = 0;
+  uint8_t or_diff_from[DIGEST256_LEN];
+  int or_diff_from_is_set = 0;
+
+  /* DEFAULT_IF_MODIFIED_SINCE_DELAY is 1/20 of the default consensus
+   * period of 1 hour.
+   */
+  const int DEFAULT_IF_MODIFIED_SINCE_DELAY = 180;
+
+  int flav = FLAV_NS;
+  if (resource)
+    flav = networkstatus_parse_flavor_name(resource);
+
+  if (flav != -1) {
+    /* IF we have a parsed consensus of this type, we can do an
+     * if-modified-time based on it. */
+    networkstatus_t *v;
+    v = networkstatus_get_latest_consensus_by_flavor(flav);
+    if (v) {
+      /* In networks with particularly short V3AuthVotingIntervals,
+       * ask for the consensus if it's been modified since half the
+       * V3AuthVotingInterval of the most recent consensus. */
+      time_t ims_delay = DEFAULT_IF_MODIFIED_SINCE_DELAY;
+      if (v->fresh_until > v->valid_after
+          && ims_delay > (v->fresh_until - v->valid_after)/2) {
+        ims_delay = (v->fresh_until - v->valid_after)/2;
+      }
+      if_modified_since = v->valid_after + ims_delay;
+      memcpy(or_diff_from, v->digest_sha3_as_signed, DIGEST256_LEN);
+      or_diff_from_is_set = 1;
+    }
+  } else {
+    /* Otherwise it might be a consensus we don't parse, but which we
+     * do cache.  Look at the cached copy, perhaps. */
+    cached_dir_t *cd = dirserv_get_consensus(resource);
+    /* We have no method of determining the voting interval from an
+     * unparsed consensus, so we use the default. */
+    if (cd) {
+      if_modified_since = cd->published + DEFAULT_IF_MODIFIED_SINCE_DELAY;
+      memcpy(or_diff_from, cd->digest_sha3_as_signed, DIGEST256_LEN);
+      or_diff_from_is_set = 1;
+    }
+  }
+
+  if (if_modified_since > 0)
+    directory_request_set_if_modified_since(req, if_modified_since);
+  if (or_diff_from_is_set) {
+    char hex[HEX_DIGEST256_LEN + 1];
+    base16_encode(hex, sizeof(hex),
+                  (const char*)or_diff_from, sizeof(or_diff_from));
+    directory_request_add_header(req, X_OR_DIFF_FROM_CONSENSUS_HEADER, hex);
+  }
+}
+
 /** Start a connection to a random running directory server, using
  * connection purpose <b>dir_purpose</b>, intending to fetch descriptors
  * of purpose <b>router_purpose</b>, and requesting <b>resource</b>.
@@ -497,47 +564,10 @@ MOCK_IMPL(void, directory_get_from_dirserver, (
   int get_via_tor = purpose_needs_anonymity(dir_purpose, router_purpose,
                                             resource);
   dirinfo_type_t type = dir_fetch_type(dir_purpose, router_purpose, resource);
-  time_t if_modified_since = 0;
 
   if (type == NO_DIRINFO)
     return;
 
-  if (dir_purpose == DIR_PURPOSE_FETCH_CONSENSUS) {
-    int flav = FLAV_NS;
-    networkstatus_t *v;
-    if (resource)
-      flav = networkstatus_parse_flavor_name(resource);
-
-    /* DEFAULT_IF_MODIFIED_SINCE_DELAY is 1/20 of the default consensus
-     * period of 1 hour.
-     */
-#define DEFAULT_IF_MODIFIED_SINCE_DELAY (180)
-    if (flav != -1) {
-      /* IF we have a parsed consensus of this type, we can do an
-       * if-modified-time based on it. */
-      v = networkstatus_get_latest_consensus_by_flavor(flav);
-      if (v) {
-        /* In networks with particularly short V3AuthVotingIntervals,
-         * ask for the consensus if it's been modified since half the
-         * V3AuthVotingInterval of the most recent consensus. */
-        time_t ims_delay = DEFAULT_IF_MODIFIED_SINCE_DELAY;
-        if (v->fresh_until > v->valid_after
-            && ims_delay > (v->fresh_until - v->valid_after)/2) {
-          ims_delay = (v->fresh_until - v->valid_after)/2;
-        }
-        if_modified_since = v->valid_after + ims_delay;
-      }
-    } else {
-      /* Otherwise it might be a consensus we don't parse, but which we
-       * do cache.  Look at the cached copy, perhaps. */
-      cached_dir_t *cd = dirserv_get_consensus(resource);
-      /* We have no method of determining the voting interval from an
-       * unparsed consensus, so we use the default. */
-      if (cd)
-        if_modified_since = cd->published + DEFAULT_IF_MODIFIED_SINCE_DELAY;
-    }
-  }
-
   if (!options->FetchServerDescriptors)
     return;
 
@@ -565,7 +595,8 @@ MOCK_IMPL(void, directory_get_from_dirserver, (
                                             ri->cache_info.identity_digest);
         directory_request_set_router_purpose(req, router_purpose);
         directory_request_set_resource(req, resource);
-        directory_request_set_if_modified_since(req, if_modified_since);
+        if (dir_purpose == DIR_PURPOSE_FETCH_CONSENSUS)
+          dir_consensus_request_set_additional_headers(req, resource);
         directory_request_set_guard_state(req, guard_state);
         directory_initiate_request(req);
         directory_request_free(req);
@@ -633,7 +664,8 @@ MOCK_IMPL(void, directory_get_from_dirserver, (
     directory_request_set_router_purpose(req, router_purpose);
     directory_request_set_indirection(req, indirection);
     directory_request_set_resource(req, resource);
-    directory_request_set_if_modified_since(req, if_modified_since);
+    if (dir_purpose == DIR_PURPOSE_FETCH_CONSENSUS)
+      dir_consensus_request_set_additional_headers(req, resource);
     if (guard_state)
       directory_request_set_guard_state(req, guard_state);
     directory_initiate_request(req);
@@ -988,6 +1020,9 @@ struct directory_request_t {
   time_t if_modified_since;
   /** Hidden-service-specific information */
   const rend_data_t *rend_query;
+  /** Extra headers to append to the request */
+  config_line_t *additional_headers;
+  /** */
   /** Used internally to directory.c: gets informed when the attempt to
    * connect to the directory succeeds or fails, if that attempt bears on the
    * directory's usability as a directory guard. */
@@ -1086,6 +1121,7 @@ directory_request_free(directory_request_t *req)
 {
   if (req == NULL)
     return;
+  config_free_lines(req->additional_headers);
   tor_free(req);
 }
 /**
@@ -1186,6 +1222,21 @@ directory_request_set_if_modified_since(directory_request_t *req,
 {
   req->if_modified_since = if_modified_since;
 }
+
+/** Include a header of name <b>key</b> with content <b>val</b> in the
+ * request. Neither may include newlines or other odd characters. Their
+ * ordering is not currently guaranteed.
+ *
+ * Note that, as elsewhere in this module, header keys include a trailing
+ * colon and space.
+ */
+void
+directory_request_add_header(directory_request_t *req,
+                             const char *key,
+                             const char *val)
+{
+  config_line_prepend(&req->additional_headers, key, val);
+}
 /**
  * Set an object containing HS data to be associated with this request.  Note
  * that only an alias to <b>query</b> is stored, so the <b>query</b> object
@@ -1672,6 +1723,14 @@ directory_send_command(dir_connection_t *conn,
     proxystring[0] = 0;
   }
 
+  /* Add additional headers, if any */
+  {
+    config_line_t *h;
+    for (h = req->additional_headers; h; h = h->next) {
+      smartlist_add_asprintf(headers, "%s%s\r\n", h->key, h->value);
+    }
+  }
+
   switch (purpose) {
     case DIR_PURPOSE_FETCH_CONSENSUS:
       /* resource is optional.  If present, it's a flavor name */
@@ -2363,6 +2422,10 @@ handle_response_fetch_consensus(dir_connection_t *conn,
   const char *reason = args->reason;
   const time_t now = approx_time();
 
+  const char *consensus;
+  char *new_consensus = NULL;
+  const char *sourcename;
+
   int r;
   const char *flavname = conn->requested_resource;
   if (status_code != 200) {
@@ -2375,15 +2438,57 @@ handle_response_fetch_consensus(dir_connection_t *conn,
     networkstatus_consensus_download_failed(status_code, flavname);
     return -1;
   }
-  log_info(LD_DIR,"Received consensus directory (body size %d) from server "
-           "'%s:%d'", (int)body_len, conn->base_.address, conn->base_.port);
-  if ((r=networkstatus_set_current_consensus(body, flavname, 0,
+
+  if (looks_like_a_consensus_diff(body, body_len)) {
+    /* First find our previous consensus. Maybe it's in ram, maybe not. */
+    cached_dir_t *cd = dirserv_get_consensus(flavname);
+    const char *consensus_body;
+    char *owned_consensus = NULL;
+    if (cd) {
+      consensus_body = cd->dir;
+    } else {
+      owned_consensus = networkstatus_read_cached_consensus(flavname);
+      consensus_body = owned_consensus;
+    }
+    if (!consensus_body) {
+      log_warn(LD_DIR, "Received a consensus diff, but we can't find "
+               "any %s-flavored consensus in our current cache.",flavname);
+      networkstatus_consensus_download_failed(0, flavname);
+      // XXXX if this happens too much, see below
+      return -1;
+    }
+
+    new_consensus = consensus_diff_apply(consensus_body, body);
+    tor_free(owned_consensus);
+    if (new_consensus == NULL) {
+      log_warn(LD_DIR, "Could not apply consensus diff received from server "
+               "'%s:%d'", conn->base_.address, conn->base_.port);
+      // XXXX If this happens too many times, we should maybe not use
+      // XXXX this directory for diffs any more?
+      networkstatus_consensus_download_failed(0, flavname);
+      return -1;
+    }
+    log_info(LD_DIR, "Applied consensus diff (size %d) from server "
+             "'%s:%d', resulting in a new consensus document (size %d).",
+             (int)body_len, conn->base_.address, conn->base_.port,
+             (int)strlen(new_consensus));
+    consensus = new_consensus;
+    sourcename = "generated based on a diff";
+  } else {
+    log_info(LD_DIR,"Received consensus directory (body size %d) from server "
+             "'%s:%d'", (int)body_len, conn->base_.address, conn->base_.port);
+    consensus = body;
+    sourcename = "downloaded";
+  }
+
+  if ((r=networkstatus_set_current_consensus(consensus, flavname, 0,
                                              conn->identity_digest))<0) {
     log_fn(r<-1?LOG_WARN:LOG_INFO, LD_DIR,
-           "Unable to load %s consensus directory downloaded from "
+           "Unable to load %s consensus directory %s from "
            "server '%s:%d'. I'll try again soon.",
-           flavname, conn->base_.address, conn->base_.port);
+           flavname, sourcename, conn->base_.address, conn->base_.port);
     networkstatus_consensus_download_failed(0, flavname);
+    tor_free(new_consensus);
     return -1;
   }
 
@@ -2401,6 +2506,7 @@ handle_response_fetch_consensus(dir_connection_t *conn,
   }
   log_info(LD_DIR, "Successfully loaded consensus.");
 
+  tor_free(new_consensus);
   return 0;
 }
 
@@ -3165,15 +3271,31 @@ write_http_response_header_impl(dir_connection_t *conn, ssize_t length,
  * based on whether the response will be <b>compressed</b> or not. */
 static void
 write_http_response_header(dir_connection_t *conn, ssize_t length,
-                           int compressed, long cache_lifetime)
+                           compress_method_t method, long cache_lifetime)
 {
+  const char *methodname = compression_method_get_name(method);
+  const char *doctype;
+  if (method == NO_METHOD)
+    doctype = "text/plain";
+  else
+    doctype = "application/octet-stream";
   write_http_response_header_impl(conn, length,
-                          compressed?"application/octet-stream":"text/plain",
-                          compressed?"deflate":"identity",
-                             NULL,
-                             cache_lifetime);
+                                  doctype,
+                                  methodname,
+                                  NULL,
+                                  cache_lifetime);
 }
 
+/** Array of compression methods to use (if supported) for serving
+ * precompressed data, ordered from best to worst. */
+static compress_method_t srv_meth_pref_precompressed[] = {
+  LZMA_METHOD,
+  ZSTD_METHOD,
+  ZLIB_METHOD,
+  GZIP_METHOD,
+  NO_METHOD
+};
+
 /** Parse the compression methods listed in an Accept-Encoding header <b>h</b>,
  * and convert them to a bitfield where compression method x is supported if
  * and only if 1 &lt;&lt; x is set in the bitfield. */
@@ -3389,7 +3511,7 @@ directory_handle_command_get,(dir_connection_t *conn, const char *headers,
     url_len -= 2;
   }
 
-  if ((header = http_get_header(headers, "Accept-Encoding"))) {
+  if ((header = http_get_header(headers, "Accept-Encoding: "))) {
     compression_methods_supported = parse_accept_encoding_header(header);
     tor_free(header);
   } else {
@@ -3477,6 +3599,69 @@ warn_consensus_is_too_old(networkstatus_t *v, const char *flavor, time_t now)
   }
 }
 
+/** If there is an X-Or-Diff-From-Consensus header included in <b>headers</b>,
+ * set <b>digest_out<b> to a new smartlist containing every 256-bit
+ * hex-encoded digest listed in that header and return 0.  Otherwise return
+ * -1.  */
+static int
+parse_or_diff_from_header(smartlist_t **digests_out, const char *headers)
+{
+  char *hdr = http_get_header(headers, X_OR_DIFF_FROM_CONSENSUS_HEADER);
+  if (hdr == NULL) {
+    return -1;
+  }
+  smartlist_t *hex_digests = smartlist_new();
+  *digests_out = smartlist_new();
+  smartlist_split_string(hex_digests, hdr, " ",
+                         SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, -1);
+  SMARTLIST_FOREACH_BEGIN(hex_digests, const char *, hex) {
+    uint8_t digest[DIGEST256_LEN];
+    if (base16_decode((char*)digest, sizeof(digest), hex, strlen(hex)) ==
+        DIGEST256_LEN) {
+      smartlist_add(*digests_out, tor_memdup(digest, sizeof(digest)));
+    } else {
+      log_fn(LOG_PROTOCOL_WARN, LD_DIR,
+             "X-Or-Diff-From-Consensus header contained bogus digest %s; "
+             "ignoring.", escaped(hex));
+    }
+  } SMARTLIST_FOREACH_END(hex);
+  SMARTLIST_FOREACH(hex_digests, char *, cp, tor_free(cp));
+  smartlist_free(hex_digests);
+  return 0;
+}
+
+/**
+ * Try to find the best consensus diff possible in order to serve a client
+ * request for a diff from one of the consensuses in <b>digests</b> to the
+ * current consensus of flavor <b>flav</b>.  The client supports the
+ * compression methods listed in the <b>compression_methods</b> bitfield:
+ * place the method chosen (if any) into <b>compression_used_out</b>.
+ */
+static struct consensus_cache_entry_t *
+find_best_diff(const smartlist_t *digests, int flav,
+               unsigned compression_methods,
+               compress_method_t *compression_used_out)
+{
+  struct consensus_cache_entry_t *result = NULL;
+
+  SMARTLIST_FOREACH_BEGIN(digests, const uint8_t *, diff_from) {
+    unsigned u;
+    for (u = 0; u < ARRAY_LENGTH(srv_meth_pref_precompressed); ++u) {
+      compress_method_t method = srv_meth_pref_precompressed[u];
+      if (0 == (compression_methods & (1u<<method)))
+        continue; // client doesn't like this one, or we don't have it.
+      if (consdiffmgr_find_diff_from(&result, flav, DIGEST_SHA3_256,
+                                     diff_from, DIGEST256_LEN,
+                                     method) == CONSDIFF_AVAILABLE) {
+        tor_assert_nonfatal(result);
+        *compression_used_out = method;
+        return result;
+      }
+    }
+  } SMARTLIST_FOREACH_END(diff_from);
+  return NULL;
+}
+
 /** Helper function for GET /tor/status-vote/current/consensus
  */
 static int
@@ -3488,130 +3673,146 @@ handle_get_current_consensus(dir_connection_t *conn,
   const time_t if_modified_since = args->if_modified_since;
   int clear_spool = 0;
 
-  {
-    /* v3 network status fetch. */
-    long lifetime = NETWORKSTATUS_CACHE_LIFETIME;
+  /* v3 network status fetch. */
+  long lifetime = NETWORKSTATUS_CACHE_LIFETIME;
 
-    networkstatus_t *v;
-    time_t now = time(NULL);
-    const char *want_fps = NULL;
-    char *flavor = NULL;
-    int flav = FLAV_NS;
+  networkstatus_t *v;
+  time_t now = time(NULL);
+  const char *want_fps = NULL;
+  char *flavor = NULL;
+  int flav = FLAV_NS;
 #define CONSENSUS_URL_PREFIX "/tor/status-vote/current/consensus/"
 #define CONSENSUS_FLAVORED_PREFIX "/tor/status-vote/current/consensus-"
-    /* figure out the flavor if any, and who we wanted to sign the thing */
-    if (!strcmpstart(url, CONSENSUS_FLAVORED_PREFIX)) {
-      const char *f, *cp;
-      f = url + strlen(CONSENSUS_FLAVORED_PREFIX);
-      cp = strchr(f, '/');
-      if (cp) {
-        want_fps = cp+1;
-        flavor = tor_strndup(f, cp-f);
-      } else {
-        flavor = tor_strdup(f);
-      }
-      flav = networkstatus_parse_flavor_name(flavor);
-      if (flav < 0)
-        flav = FLAV_NS;
+  /* figure out the flavor if any, and who we wanted to sign the thing */
+  if (!strcmpstart(url, CONSENSUS_FLAVORED_PREFIX)) {
+    const char *f, *cp;
+    f = url + strlen(CONSENSUS_FLAVORED_PREFIX);
+    cp = strchr(f, '/');
+    if (cp) {
+      want_fps = cp+1;
+      flavor = tor_strndup(f, cp-f);
     } else {
-      if (!strcmpstart(url, CONSENSUS_URL_PREFIX))
-        want_fps = url+strlen(CONSENSUS_URL_PREFIX);
-    }
-
-    v = networkstatus_get_latest_consensus_by_flavor(flav);
-
-    if (v && !networkstatus_consensus_reasonably_live(v, now)) {
-      write_http_status_line(conn, 404, "Consensus is too old");
-      warn_consensus_is_too_old(v, flavor, now);
-      geoip_note_ns_response(GEOIP_REJECT_NOT_FOUND);
-      tor_free(flavor);
-      goto done;
+      flavor = tor_strdup(f);
     }
+    flav = networkstatus_parse_flavor_name(flavor);
+    if (flav < 0)
+      flav = FLAV_NS;
+  } else {
+    if (!strcmpstart(url, CONSENSUS_URL_PREFIX))
+      want_fps = url+strlen(CONSENSUS_URL_PREFIX);
+  }
 
-    if (v && want_fps &&
-        !client_likes_consensus(v, want_fps)) {
-      write_http_status_line(conn, 404, "Consensus not signed by sufficient "
-                             "number of requested authorities");
-      geoip_note_ns_response(GEOIP_REJECT_NOT_ENOUGH_SIGS);
-      tor_free(flavor);
-      goto done;
-    }
+  v = networkstatus_get_latest_consensus_by_flavor(flav);
 
-    conn->spool = smartlist_new();
-    clear_spool = 1;
-    {
-      spooled_resource_t *spooled;
-      if (flavor)
-        spooled = spooled_resource_new(DIR_SPOOL_NETWORKSTATUS,
-                                       (uint8_t*)flavor, strlen(flavor));
-      else
-        spooled = spooled_resource_new(DIR_SPOOL_NETWORKSTATUS,
-                                       NULL, 0);
-      tor_free(flavor);
-      smartlist_add(conn->spool, spooled);
-    }
-    lifetime = (v && v->fresh_until > now) ? v->fresh_until - now : 0;
+  if (v && !networkstatus_consensus_reasonably_live(v, now)) {
+    write_http_status_line(conn, 404, "Consensus is too old");
+    warn_consensus_is_too_old(v, flavor, now);
+    geoip_note_ns_response(GEOIP_REJECT_NOT_FOUND);
+    tor_free(flavor);
+    goto done;
+  }
 
-    if (!smartlist_len(conn->spool)) { /* we failed to create/cache cp */
-      write_http_status_line(conn, 503, "Network status object unavailable");
-      geoip_note_ns_response(GEOIP_REJECT_UNAVAILABLE);
-      goto done;
-    }
+  if (v && want_fps &&
+      !client_likes_consensus(v, want_fps)) {
+    write_http_status_line(conn, 404, "Consensus not signed by sufficient "
+                           "number of requested authorities");
+    geoip_note_ns_response(GEOIP_REJECT_NOT_ENOUGH_SIGS);
+    tor_free(flavor);
+    goto done;
+  }
 
-    size_t size_guess = 0;
-    int n_expired = 0;
-    dirserv_spool_remove_missing_and_guess_size(conn, if_modified_since,
-                                                compressed,
-                                                &size_guess,
-                                                &n_expired);
+  struct consensus_cache_entry_t *cached_diff = NULL;
+  smartlist_t *diff_from_digests = NULL;
+  compress_method_t compression_used = NO_METHOD;
+  if (!parse_or_diff_from_header(&diff_from_digests, args->headers)) {
+    tor_assert(diff_from_digests);
+    cached_diff = find_best_diff(diff_from_digests, flav,
+                                 args->compression_supported,
+                                 &compression_used);
+    SMARTLIST_FOREACH(diff_from_digests, uint8_t *, d, tor_free(d));
+    smartlist_free(diff_from_digests);
+  }
 
-    if (!smartlist_len(conn->spool) && !n_expired) {
-      write_http_status_line(conn, 404, "Not found");
-      geoip_note_ns_response(GEOIP_REJECT_NOT_FOUND);
-      goto done;
-    } else if (!smartlist_len(conn->spool)) {
-      write_http_status_line(conn, 304, "Not modified");
-      geoip_note_ns_response(GEOIP_REJECT_NOT_MODIFIED);
-      goto done;
+  conn->spool = smartlist_new();
+  clear_spool = 1;
+  {
+    spooled_resource_t *spooled;
+    if (cached_diff) {
+      spooled = spooled_resource_new_from_cache_entry(cached_diff);
+    } else if (flavor) {
+      spooled = spooled_resource_new(DIR_SPOOL_NETWORKSTATUS,
+                                     (uint8_t*)flavor, strlen(flavor));
+      compression_used = compressed ? ZLIB_METHOD : NO_METHOD;
+    } else {
+      spooled = spooled_resource_new(DIR_SPOOL_NETWORKSTATUS,
+                                     NULL, 0);
+      compression_used = compressed ? ZLIB_METHOD : NO_METHOD;
     }
+    tor_free(flavor);
+    smartlist_add(conn->spool, spooled);
+  }
+  lifetime = (v && v->fresh_until > now) ? v->fresh_until - now : 0;
 
-    if (global_write_bucket_low(TO_CONN(conn), size_guess, 2)) {
-      log_debug(LD_DIRSERV,
-               "Client asked for network status lists, but we've been "
-               "writing too many bytes lately. Sending 503 Dir busy.");
-      write_http_status_line(conn, 503, "Directory busy, try again later");
-      geoip_note_ns_response(GEOIP_REJECT_BUSY);
-      goto done;
-    }
+  if (!smartlist_len(conn->spool)) { /* we failed to create/cache cp */
+    write_http_status_line(conn, 503, "Network status object unavailable");
+    geoip_note_ns_response(GEOIP_REJECT_UNAVAILABLE);
+    goto done;
+  }
 
-    tor_addr_t addr;
-    if (tor_addr_parse(&addr, (TO_CONN(conn))->address) >= 0) {
-      geoip_note_client_seen(GEOIP_CLIENT_NETWORKSTATUS,
-                             &addr, NULL,
-                             time(NULL));
-      geoip_note_ns_response(GEOIP_SUCCESS);
-      /* Note that a request for a network status has started, so that we
-       * can measure the download time later on. */
-      if (conn->dirreq_id)
-        geoip_start_dirreq(conn->dirreq_id, size_guess, DIRREQ_TUNNELED);
-      else
-        geoip_start_dirreq(TO_CONN(conn)->global_identifier, size_guess,
-                           DIRREQ_DIRECT);
-    }
+  size_t size_guess = 0;
+  int n_expired = 0;
+  dirserv_spool_remove_missing_and_guess_size(conn, if_modified_since,
+                                              compressed,
+                                              &size_guess,
+                                              &n_expired);
 
-    clear_spool = 0;
-    write_http_response_header(conn, -1, compressed,
-                               smartlist_len(conn->spool) == 1 ? lifetime : 0);
-    if (! compressed)
-      conn->compress_state = tor_compress_new(0, ZLIB_METHOD,
-                                              HIGH_COMPRESSION);
+  if (!smartlist_len(conn->spool) && !n_expired) {
+    write_http_status_line(conn, 404, "Not found");
+    geoip_note_ns_response(GEOIP_REJECT_NOT_FOUND);
+    goto done;
+  } else if (!smartlist_len(conn->spool)) {
+    write_http_status_line(conn, 304, "Not modified");
+    geoip_note_ns_response(GEOIP_REJECT_NOT_MODIFIED);
+    goto done;
+  }
 
-    /* Prime the connection with some data. */
-    const int initial_flush_result = connection_dirserv_flushed_some(conn);
-    tor_assert_nonfatal(initial_flush_result == 0);
+  if (global_write_bucket_low(TO_CONN(conn), size_guess, 2)) {
+    log_debug(LD_DIRSERV,
+              "Client asked for network status lists, but we've been "
+              "writing too many bytes lately. Sending 503 Dir busy.");
+    write_http_status_line(conn, 503, "Directory busy, try again later");
+    geoip_note_ns_response(GEOIP_REJECT_BUSY);
     goto done;
   }
 
+  tor_addr_t addr;
+  if (tor_addr_parse(&addr, (TO_CONN(conn))->address) >= 0) {
+    geoip_note_client_seen(GEOIP_CLIENT_NETWORKSTATUS,
+                           &addr, NULL,
+                           time(NULL));
+    geoip_note_ns_response(GEOIP_SUCCESS);
+    /* Note that a request for a network status has started, so that we
+     * can measure the download time later on. */
+    if (conn->dirreq_id)
+      geoip_start_dirreq(conn->dirreq_id, size_guess, DIRREQ_TUNNELED);
+    else
+      geoip_start_dirreq(TO_CONN(conn)->global_identifier, size_guess,
+                         DIRREQ_DIRECT);
+  }
+
+  clear_spool = 0;
+  write_http_response_header(conn, -1,
+                             compression_used,
+                             smartlist_len(conn->spool) == 1 ? lifetime : 0);
+  if (! compressed)
+    conn->compress_state = tor_compress_new(0, ZLIB_METHOD,
+                                            HIGH_COMPRESSION);
+
+  /* Prime the connection with some data. */
+  const int initial_flush_result = connection_dirserv_flushed_some(conn);
+  tor_assert_nonfatal(initial_flush_result == 0);
+  goto done;
+
  done:
   if (clear_spool) {
     dir_conn_clear_spool(conn);
@@ -3697,7 +3898,8 @@ handle_get_status_vote(dir_connection_t *conn, const get_handler_args_t *args)
       write_http_status_line(conn, 503, "Directory busy, try again later");
       goto vote_done;
     }
-    write_http_response_header(conn, body_len ? body_len : -1, compressed,
+    write_http_response_header(conn, body_len ? body_len : -1,
+                 compressed ? ZLIB_METHOD : NO_METHOD,
                  lifetime);
 
     if (smartlist_len(items)) {
@@ -3758,7 +3960,9 @@ handle_get_microdesc(dir_connection_t *conn, const get_handler_args_t *args)
     }
 
     clear_spool = 0;
-    write_http_response_header(conn, -1, compressed, MICRODESC_CACHE_LIFETIME);
+    write_http_response_header(conn, -1,
+                               compressed ? ZLIB_METHOD : NO_METHOD,
+                               MICRODESC_CACHE_LIFETIME);
 
     if (compressed)
       conn->compress_state = tor_compress_new(1, ZLIB_METHOD,
@@ -3852,7 +4056,9 @@ handle_get_descriptor(dir_connection_t *conn, const get_handler_args_t *args)
         dir_conn_clear_spool(conn);
         goto done;
       }
-      write_http_response_header(conn, -1, compressed, cache_lifetime);
+      write_http_response_header(conn, -1,
+                                 compressed ? ZLIB_METHOD : NO_METHOD,
+                                 cache_lifetime);
       if (compressed)
         conn->compress_state = tor_compress_new(1, ZLIB_METHOD,
                                         choose_compression_level(size_guess));
@@ -3943,7 +4149,9 @@ handle_get_keys(dir_connection_t *conn, const get_handler_args_t *args)
       goto keys_done;
     }
 
-    write_http_response_header(conn, compressed?-1:len, compressed, 60*60);
+    write_http_response_header(conn, compressed?-1:len,
+                               compressed ? ZLIB_METHOD : NO_METHOD,
+                               60*60);
     if (compressed) {
       conn->compress_state = tor_compress_new(1, ZLIB_METHOD,
                                               choose_compression_level(len));
@@ -3983,7 +4191,7 @@ handle_get_hs_descriptor_v2(dir_connection_t *conn,
                safe_str(escaped(query)));
       switch (rend_cache_lookup_v2_desc_as_dir(query, &descp)) {
         case 1: /* valid */
-          write_http_response_header(conn, strlen(descp), 0, 0);
+          write_http_response_header(conn, strlen(descp), NO_METHOD, 0);
           connection_write_to_buf(descp, strlen(descp), TO_CONN(conn));
           break;
         case 0: /* well-formed but not present */
@@ -4035,7 +4243,7 @@ handle_get_hs_descriptor_v3(dir_connection_t *conn,
   }
 
   /* Found requested descriptor! Pass it to this nice client. */
-  write_http_response_header(conn, strlen(desc_str), 0, 0);
+  write_http_response_header(conn, strlen(desc_str), NO_METHOD, 0);
   connection_write_to_buf(desc_str, strlen(desc_str), TO_CONN(conn));
 
  done:
@@ -4074,7 +4282,7 @@ handle_get_networkstatus_bridges(dir_connection_t *conn,
     /* all happy now. send an answer. */
     status = networkstatus_getinfo_by_purpose("bridge", time(NULL));
     size_t dlen = strlen(status);
-    write_http_response_header(conn, dlen, 0, 0);
+    write_http_response_header(conn, dlen, NO_METHOD, 0);
     connection_write_to_buf(status, dlen, TO_CONN(conn));
     tor_free(status);
     goto done;
@@ -4091,7 +4299,7 @@ handle_get_robots(dir_connection_t *conn, const get_handler_args_t *args)
   {
     const char robots[] = "User-agent: *\r\nDisallow: /\r\n";
     size_t len = strlen(robots);
-    write_http_response_header(conn, len, 0, ROBOTS_CACHE_LIFETIME);
+    write_http_response_header(conn, len, NO_METHOD, ROBOTS_CACHE_LIFETIME);
     connection_write_to_buf(robots, len, TO_CONN(conn));
   }
   return 0;
diff --git a/src/or/directory.h b/src/or/directory.h
index 8473d39e85..125333da37 100644
--- a/src/or/directory.h
+++ b/src/or/directory.h
@@ -72,7 +72,9 @@ void directory_request_set_rend_query(directory_request_t *req,
 
 void directory_request_set_routerstatus(directory_request_t *req,
                                         const routerstatus_t *rs);
-
+void directory_request_add_header(directory_request_t *req,
+                                  const char *key,
+                                  const char *val);
 MOCK_DECL(void, directory_initiate_request, (directory_request_t *request));
 
 int parse_http_response(const char *headers, int *code, time_t *date,
diff --git a/src/or/dirserv.c b/src/or/dirserv.c
index e76fd932ca..7de72df9eb 100644
--- a/src/or/dirserv.c
+++ b/src/or/dirserv.c
@@ -13,6 +13,7 @@
 #include "command.h"
 #include "connection.h"
 #include "connection_or.h"
+#include "conscache.h"
 #include "control.h"
 #include "directory.h"
 #include "dirserv.h"
@@ -1211,6 +1212,7 @@ void
 dirserv_set_cached_consensus_networkstatus(const char *networkstatus,
                                            const char *flavor_name,
                                            const common_digests_t *digests,
+                                           const uint8_t *sha3_as_signed,
                                            time_t published)
 {
   cached_dir_t *new_networkstatus;
@@ -1220,6 +1222,8 @@ dirserv_set_cached_consensus_networkstatus(const char *networkstatus,
 
   new_networkstatus = new_cached_dir(tor_strdup(networkstatus), published);
   memcpy(&new_networkstatus->digests, digests, sizeof(common_digests_t));
+  memcpy(&new_networkstatus->digest_sha3_as_signed, sha3_as_signed,
+         DIGEST256_LEN);
   old_networkstatus = strmap_set(cached_consensuses, flavor_name,
                                  new_networkstatus);
   if (old_networkstatus)
@@ -3392,6 +3396,9 @@ spooled_resource_new(dir_spool_source_t source,
     default:
       spooled->spool_eagerly = 1;
       break;
+    case DIR_SPOOL_CONSENSUS_CACHE_ENTRY:
+      tor_assert_unreached();
+      break;
   }
   tor_assert(digestlen <= sizeof(spooled->digest));
   if (digest)
@@ -3399,6 +3406,33 @@ spooled_resource_new(dir_spool_source_t source,
   return spooled;
 }
 
+/**
+ * Create a new spooled_resource_t to spool the contents of <b>entry</b> to
+ * the user.  Return the spooled object on success, or NULL on failure (which
+ * is probably caused by a failure to map the body of the item from disk).
+ *
+ * Adds a reference to entry's reference counter.
+ */
+spooled_resource_t *
+spooled_resource_new_from_cache_entry(consensus_cache_entry_t *entry)
+{
+  spooled_resource_t *spooled = tor_malloc_zero(sizeof(spooled_resource_t));
+  spooled->spool_source = DIR_SPOOL_CONSENSUS_CACHE_ENTRY;
+  spooled->spool_eagerly = 0;
+  consensus_cache_entry_incref(entry);
+  spooled->consensus_cache_entry = entry;
+
+  int r = consensus_cache_entry_get_body(entry,
+                                         &spooled->cce_body,
+                                         &spooled->cce_len);
+  if (r == 0) {
+    return spooled;
+  } else {
+    spooled_resource_free(spooled);
+    return NULL;
+  }
+}
+
 /** Release all storage held by <b>spooled</b>. */
 void
 spooled_resource_free(spooled_resource_t *spooled)
@@ -3410,6 +3444,10 @@ spooled_resource_free(spooled_resource_t *spooled)
     cached_dir_decref(spooled->cached_dir_ref);
   }
 
+  if (spooled->consensus_cache_entry) {
+    consensus_cache_entry_decref(spooled->consensus_cache_entry);
+  }
+
   tor_free(spooled);
 }
 
@@ -3456,6 +3494,9 @@ spooled_resource_estimate_size(const spooled_resource_t *spooled,
     return bodylen;
   } else {
     cached_dir_t *cached;
+    if (spooled->consensus_cache_entry) {
+      return spooled->cce_len;
+    }
     if (spooled->cached_dir_ref) {
       cached = spooled->cached_dir_ref;
     } else {
@@ -3505,7 +3546,8 @@ spooled_resource_flush_some(spooled_resource_t *spooled,
     return SRFS_DONE;
   } else {
     cached_dir_t *cached = spooled->cached_dir_ref;
-    if (cached == NULL) {
+    consensus_cache_entry_t *cce = spooled->consensus_cache_entry;
+    if (cached == NULL && cce == NULL) {
       /* The cached_dir_t hasn't been materialized yet. So let's look it up. */
       cached = spooled->cached_dir_ref =
         spooled_resource_lookup_cached_dir(spooled, NULL);
@@ -3517,22 +3559,34 @@ spooled_resource_flush_some(spooled_resource_t *spooled,
       tor_assert_nonfatal(spooled->cached_dir_offset == 0);
     }
 
+    if (BUG(!cached && !cce))
+      return SRFS_DONE;
+
+    int64_t total_len;
+    const char *ptr;
+    if (cached) {
+      total_len = cached->dir_z_len;
+      ptr = cached->dir_z;
+    } else {
+      total_len = spooled->cce_len;
+      ptr = (const char *)spooled->cce_body;
+    }
     /* How many bytes left to flush? */
-    int64_t remaining = 0;
-    remaining = cached->dir_z_len - spooled->cached_dir_offset;
+    int64_t remaining;
+    remaining = total_len - spooled->cached_dir_offset;
     if (BUG(remaining < 0))
       return SRFS_ERR;
     ssize_t bytes = (ssize_t) MIN(DIRSERV_CACHED_DIR_CHUNK_SIZE, remaining);
     if (conn->compress_state) {
       connection_write_to_buf_compress(
-              cached->dir_z + spooled->cached_dir_offset,
+              ptr + spooled->cached_dir_offset,
               bytes, conn, 0);
     } else {
-      connection_write_to_buf(cached->dir_z + spooled->cached_dir_offset,
+      connection_write_to_buf(ptr + spooled->cached_dir_offset,
                               bytes, TO_CONN(conn));
     }
     spooled->cached_dir_offset += bytes;
-    if (spooled->cached_dir_offset >= (off_t)cached->dir_z_len) {
+    if (spooled->cached_dir_offset >= (off_t)total_len) {
       return SRFS_DONE;
     } else {
       return SRFS_MORE;
@@ -3608,6 +3662,7 @@ spooled_resource_lookup_body(const spooled_resource_t *spooled,
       return 0;
     }
     case DIR_SPOOL_NETWORKSTATUS:
+    case DIR_SPOOL_CONSENSUS_CACHE_ENTRY:
     default:
       /* LCOV_EXCL_START */
       tor_assert_nonfatal_unreached();
diff --git a/src/or/dirserv.h b/src/or/dirserv.h
index f707237ed1..480174d5bb 100644
--- a/src/or/dirserv.h
+++ b/src/or/dirserv.h
@@ -38,6 +38,7 @@ typedef enum dir_spool_source_t {
     DIR_SPOOL_EXTRA_BY_DIGEST, DIR_SPOOL_EXTRA_BY_FP,
     DIR_SPOOL_MICRODESC,
     DIR_SPOOL_NETWORKSTATUS,
+    DIR_SPOOL_CONSENSUS_CACHE_ENTRY,
 } dir_spool_source_t;
 #define dir_spool_source_bitfield_t ENUM_BF(dir_spool_source_t)
 
@@ -74,8 +75,15 @@ typedef struct spooled_resource_t {
    */
   struct cached_dir_t *cached_dir_ref;
   /**
-   * The current offset into cached_dir. Only used when spool_eagerly is
-   * false */
+   * A different kind of large object that we might be spooling. Also
+   * reference-counted.  Also only used when spool_eagerly is false.
+   */
+  struct consensus_cache_entry_t *consensus_cache_entry;
+  const uint8_t *cce_body;
+  size_t cce_len;
+  /**
+   * The current offset into cached_dir or cce_body. Only used when
+   * spool_eagerly is false */
   off_t cached_dir_offset;
 } spooled_resource_t;
 
@@ -110,6 +118,7 @@ cached_dir_t *dirserv_get_consensus(const char *flavor_name);
 void dirserv_set_cached_consensus_networkstatus(const char *consensus,
                                               const char *flavor_name,
                                               const common_digests_t *digests,
+                                              const uint8_t *sha3_as_signed,
                                               time_t published);
 void dirserv_clear_old_networkstatuses(time_t cutoff);
 int dirserv_get_routerdesc_spool(smartlist_t *spools_out, const char *key,
@@ -184,6 +193,8 @@ int dirserv_read_guardfraction_file(const char *fname,
 spooled_resource_t *spooled_resource_new(dir_spool_source_t source,
                                          const uint8_t *digest,
                                          size_t digestlen);
+spooled_resource_t *spooled_resource_new_from_cache_entry(
+                                      struct consensus_cache_entry_t *entry);
 void spooled_resource_free(spooled_resource_t *spooled);
 void dirserv_spool_remove_missing_and_guess_size(dir_connection_t *conn,
                                                  time_t cutoff,
diff --git a/src/or/networkstatus.c b/src/or/networkstatus.c
index 188e7531f8..1b21dd7b45 100644
--- a/src/or/networkstatus.c
+++ b/src/or/networkstatus.c
@@ -179,53 +179,74 @@ networkstatus_reset_download_failures(void)
     download_status_reset(&consensus_bootstrap_dl_status[i]);
 }
 
+/**
+ * Read and and return the cached consensus of type <b>flavorname</b>.  If
+ * <b>unverified</b> is false, get the one we haven't verified. Return NULL if
+ * the file isn't there. */
+static char *
+networkstatus_read_cached_consensus_impl(int flav,
+                                         const char *flavorname,
+                                         int unverified_consensus)
+{
+  char buf[128];
+  const char *prefix;
+  if (unverified_consensus) {
+    prefix = "unverified";
+  } else {
+    prefix = "cached";
+  }
+  if (flav == FLAV_NS) {
+    tor_snprintf(buf, sizeof(buf), "%s-consensus", prefix);
+  } else {
+    tor_snprintf(buf, sizeof(buf), "%s-%s-consensus", prefix, flavorname);
+  }
+
+  char *filename = get_datadir_fname(buf);
+  char *result = read_file_to_str(filename, RFTS_IGNORE_MISSING, NULL);
+  tor_free(filename);
+  return result;
+}
+
+/** Return a new string containing the current cached consensus of flavor
+ * <b>flavorname</b>. */
+char *
+networkstatus_read_cached_consensus(const char *flavorname)
+ {
+  int flav = networkstatus_parse_flavor_name(flavorname);
+  if (flav < 0)
+    return NULL;
+  return networkstatus_read_cached_consensus_impl(flav, flavorname, 0);
+}
+
 /** Read every cached v3 consensus networkstatus from the disk. */
 int
 router_reload_consensus_networkstatus(void)
 {
-  char *filename;
-  char *s;
   const unsigned int flags = NSSET_FROM_CACHE | NSSET_DONT_DOWNLOAD_CERTS;
   int flav;
 
   /* FFFF Suppress warnings if cached consensus is bad? */
   for (flav = 0; flav < N_CONSENSUS_FLAVORS; ++flav) {
-    char buf[128];
     const char *flavor = networkstatus_get_flavor_name(flav);
-    if (flav == FLAV_NS) {
-      filename = get_datadir_fname("cached-consensus");
-    } else {
-      tor_snprintf(buf, sizeof(buf), "cached-%s-consensus", flavor);
-      filename = get_datadir_fname(buf);
-    }
-    s = read_file_to_str(filename, RFTS_IGNORE_MISSING, NULL);
+    char *s = networkstatus_read_cached_consensus_impl(flav, flavor, 0);
     if (s) {
       if (networkstatus_set_current_consensus(s, flavor, flags, NULL) < -1) {
-        log_warn(LD_FS, "Couldn't load consensus %s networkstatus from \"%s\"",
-                 flavor, filename);
+        log_warn(LD_FS, "Couldn't load consensus %s networkstatus from cache",
+                 flavor);
       }
       tor_free(s);
     }
-    tor_free(filename);
 
-    if (flav == FLAV_NS) {
-      filename = get_datadir_fname("unverified-consensus");
-    } else {
-      tor_snprintf(buf, sizeof(buf), "unverified-%s-consensus", flavor);
-      filename = get_datadir_fname(buf);
-    }
-
-    s = read_file_to_str(filename, RFTS_IGNORE_MISSING, NULL);
+    s = networkstatus_read_cached_consensus_impl(flav, flavor, 1);
     if (s) {
       if (networkstatus_set_current_consensus(s, flavor,
                                      flags|NSSET_WAS_WAITING_FOR_CERTS,
                                      NULL)) {
-      log_info(LD_FS, "Couldn't load consensus %s networkstatus from \"%s\"",
-               flavor, filename);
-    }
+        log_info(LD_FS, "Couldn't load unverified consensus %s networkstatus "
+                 "from cache", flavor);
+      }
       tor_free(s);
     }
-    tor_free(filename);
   }
 
   if (!networkstatus_get_latest_consensus()) {
@@ -1981,6 +2002,7 @@ networkstatus_set_current_consensus(const char *consensus,
     dirserv_set_cached_consensus_networkstatus(consensus,
                                                flavor,
                                                &c->digests,
+                                               c->digest_sha3_as_signed,
                                                c->valid_after);
     if (server_mode(get_options())) {
       consdiffmgr_add_consensus(consensus, c);
diff --git a/src/or/networkstatus.h b/src/or/networkstatus.h
index 8a9f5f0b09..6a90d706c5 100644
--- a/src/or/networkstatus.h
+++ b/src/or/networkstatus.h
@@ -16,6 +16,7 @@
 
 void networkstatus_reset_warnings(void);
 void networkstatus_reset_download_failures(void);
+char *networkstatus_read_cached_consensus(const char *flavorname);
 int router_reload_consensus_networkstatus(void);
 void routerstatus_free(routerstatus_t *rs);
 void networkstatus_vote_free(networkstatus_t *ns);
diff --git a/src/or/or.h b/src/or/or.h
index e30a1d24c8..423f66cdd5 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -1938,6 +1938,8 @@ typedef struct cached_dir_t {
   size_t dir_z_len; /**< Length of <b>dir_z</b>. */
   time_t published; /**< When was this object published. */
   common_digests_t digests; /**< Digests of this object (networkstatus only) */
+  /** Sha3 digest (also ns only) */
+  uint8_t digest_sha3_as_signed[DIGEST256_LEN];
   int refcnt; /**< Reference count for this cached_dir_t. */
 } cached_dir_t;
 
@@ -2638,6 +2640,9 @@ typedef struct networkstatus_t {
 
   /** Digests of this document, as signed. */
   common_digests_t digests;
+  /** A SHA3-256 digest of the document, not including signatures: used for
+   * consensus diffs */
+  uint8_t digest_sha3_as_signed[DIGEST256_LEN];
 
   /** List of router statuses, sorted by identity digest.  For a vote,
    * the elements are vote_routerstatus_t; for a consensus, the elements
diff --git a/src/or/routerparse.c b/src/or/routerparse.c
index f39c33261f..fa79cf7132 100644
--- a/src/or/routerparse.c
+++ b/src/or/routerparse.c
@@ -3384,6 +3384,7 @@ networkstatus_parse_vote_from_string(const char *s, const char **eos_out,
   networkstatus_voter_info_t *voter = NULL;
   networkstatus_t *ns = NULL;
   common_digests_t ns_digests;
+  uint8_t sha3_as_signed[DIGEST256_LEN];
   const char *cert, *end_of_header, *end_of_footer, *s_dup = s;
   directory_token_t *tok;
   struct in_addr in;
@@ -3397,7 +3398,8 @@ networkstatus_parse_vote_from_string(const char *s, const char **eos_out,
   if (eos_out)
     *eos_out = NULL;
 
-  if (router_get_networkstatus_v3_hashes(s, &ns_digests)) {
+  if (router_get_networkstatus_v3_hashes(s, &ns_digests) ||
+      router_get_networkstatus_v3_sha3_as_signed(sha3_as_signed, s)<0) {
     log_warn(LD_DIR, "Unable to compute digest of network-status");
     goto err;
   }
@@ -3414,6 +3416,7 @@ networkstatus_parse_vote_from_string(const char *s, const char **eos_out,
 
   ns = tor_malloc_zero(sizeof(networkstatus_t));
   memcpy(&ns->digests, &ns_digests, sizeof(ns_digests));
+  memcpy(&ns->digest_sha3_as_signed, sha3_as_signed, sizeof(sha3_as_signed));
 
   tok = find_by_keyword(tokens, K_NETWORK_STATUS_VERSION);
   tor_assert(tok);
diff --git a/src/test/test_dir_handle_get.c b/src/test/test_dir_handle_get.c
index 6e963913d1..c98938b2db 100644
--- a/src/test/test_dir_handle_get.c
+++ b/src/test/test_dir_handle_get.c
@@ -1773,10 +1773,14 @@ status_vote_current_consensus_ns_test(char **header, char **body,
                                       size_t *body_len)
 {
   common_digests_t digests;
+  uint8_t sha3[DIGEST256_LEN];
   dir_connection_t *conn = NULL;
 
   #define NETWORK_STATUS "some network status string"
+  memset(&digests, 0x60, sizeof(digests));
+  memset(sha3, 0x06, sizeof(sha3));
   dirserv_set_cached_consensus_networkstatus(NETWORK_STATUS, "ns", &digests,
+                                             sha3,
                                              time(NULL));
 
   MOCK(connection_write_to_buf_impl_, connection_write_to_buf_mock);