dirvote.c

/* Copyright (c) 2001-2004, Roger Dingledine.
 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
 * Copyright (c) 2007-2009, The Tor Project, Inc. */
/* See LICENSE for licensing information */

#define DIRVOTE_PRIVATE
#include "or.h"

/**
 * \file dirvote.c
 * \brief Functions to compute directory consensus, and schedule voting.
 **/

/** A consensus that we have built and are appending signatures to.  Once it's
 * time to publish it, it will become an active consensus if it accumulates
 * enough signatures. */
typedef struct pending_consensus_t {
  /** The body of the consensus that we're currently building.  Once we
   * have it built, it goes into dirserv.c */
  char *body;
  /** The parsed in-progress consensus document. */
  networkstatus_t *consensus;
} pending_consensus_t;

static int dirvote_add_signatures_to_all_pending_consensuses(
                       const char *detached_signatures_body,
                       const char **msg_out);
static int dirvote_add_signatures_to_pending_consensus(
                       pending_consensus_t *pc,
                       ns_detached_signatures_t *sigs,
                       const char **msg_out);
static char *list_v3_auth_ids(void);
static void dirvote_fetch_missing_votes(void);
static void dirvote_fetch_missing_signatures(void);
static int dirvote_perform_vote(void);
static void dirvote_clear_votes(int all_votes);
static int dirvote_compute_consensuses(void);
static int dirvote_publish_consensus(void);
static char *make_consensus_method_list(int low, int high, const char *sep);

/** The highest consensus method that we currently support. */
#define MAX_SUPPORTED_CONSENSUS_METHOD 8

#define MIN_METHOD_FOR_PARAMS 7

/** Lowest consensus method that generates microdescriptors */
#define MIN_METHOD_FOR_MICRODESC 8

/* =====
 * Voting
 * =====*/

/* Overestimated. */
#define MICRODESC_LINE_LEN 80

/** 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. */
char *
format_networkstatus_vote(crypto_pk_env_t *private_signing_key,
                          networkstatus_t *v3_ns)
{
  size_t len;
  char *status = NULL;
  const char *client_versions = NULL, *server_versions = NULL;
  char *outp, *endp;
  char fingerprint[FINGERPRINT_LEN+1];
  char ipaddr[INET_NTOA_BUF_LEN];
  char digest[DIGEST_LEN];
  struct in_addr in;
  uint32_t addr;
  routerlist_t *rl = router_get_routerlist();
  char *version_lines = NULL;
  networkstatus_voter_info_t *voter;

  tor_assert(private_signing_key);
  tor_assert(v3_ns->type == NS_TYPE_VOTE || v3_ns->type == NS_TYPE_OPINION);

  voter = smartlist_get(v3_ns->voters, 0);

  addr = voter->addr;
  in.s_addr = htonl(addr);
  tor_inet_ntoa(&in, ipaddr, sizeof(ipaddr));

  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 || server_versions) {
    size_t v_len = 64;
    char *cp;
    if (client_versions)
      v_len += strlen(client_versions);
    if (server_versions)
      v_len += strlen(server_versions);
    version_lines = tor_malloc(v_len);
    cp = version_lines;
    if (client_versions) {
      tor_snprintf(cp, v_len-(cp-version_lines),
                   "client-versions %s\n", client_versions);
      cp += strlen(cp);
    }
    if (server_versions)
      tor_snprintf(cp, v_len-(cp-version_lines),
                   "server-versions %s\n", server_versions);
  } else {
    version_lines = tor_strdup("");
  }

  len = 8192;
  len += strlen(version_lines);
  len += (RS_ENTRY_LEN+MICRODESC_LINE_LEN)*smartlist_len(rl->routers);
  len += v3_ns->cert->cache_info.signed_descriptor_len;

  status = tor_malloc(len);
  {
    char published[ISO_TIME_LEN+1];
    char va[ISO_TIME_LEN+1];
    char fu[ISO_TIME_LEN+1];
    char vu[ISO_TIME_LEN+1];
    char *flags = smartlist_join_strings(v3_ns->known_flags, " ", 0, NULL);
    char *params;
    authority_cert_t *cert = v3_ns->cert;
    char *methods =
      make_consensus_method_list(1, MAX_SUPPORTED_CONSENSUS_METHOD, " ");
    format_iso_time(published, v3_ns->published);
    format_iso_time(va, v3_ns->valid_after);
    format_iso_time(fu, v3_ns->fresh_until);
    format_iso_time(vu, v3_ns->valid_until);

    if (v3_ns->net_params)
      params = smartlist_join_strings(v3_ns->net_params, " ", 0, NULL);
    else
      params = tor_strdup("");

    tor_assert(cert);
    tor_snprintf(status, len,
                 "network-status-version 3\n"
                 "vote-status %s\n"
                 "consensus-methods %s\n"
                 "published %s\n"
                 "valid-after %s\n"
                 "fresh-until %s\n"
                 "valid-until %s\n"
                 "voting-delay %d %d\n"
                 "%s" /* versions */
                 "known-flags %s\n"
                 "params %s\n"
                 "dir-source %s %s %s %s %d %d\n"
                 "contact %s\n",
                 v3_ns->type == NS_TYPE_VOTE ? "vote" : "opinion",
                 methods,
                 published, va, fu, vu,
                 v3_ns->vote_seconds, v3_ns->dist_seconds,
                 version_lines,
                 flags,
                 params,
                 voter->nickname, fingerprint, voter->address,
                 ipaddr, voter->dir_port, voter->or_port, voter->contact);

    tor_free(params);
    tor_free(flags);
    tor_free(methods);
    outp = status + strlen(status);
    endp = status + len;

    if (!tor_digest_is_zero(voter->legacy_id_digest)) {
      char fpbuf[HEX_DIGEST_LEN+1];
      base16_encode(fpbuf, sizeof(fpbuf), voter->legacy_id_digest, DIGEST_LEN);
      tor_snprintf(outp, endp-outp, "legacy-dir-key %s\n", fpbuf);
      outp += strlen(outp);
    }

    tor_assert(outp + cert->cache_info.signed_descriptor_len < endp);
    memcpy(outp, cert->cache_info.signed_descriptor_body,
           cert->cache_info.signed_descriptor_len);

    outp += cert->cache_info.signed_descriptor_len;
  }

  SMARTLIST_FOREACH_BEGIN(v3_ns->routerstatus_list, vote_routerstatus_t *,
                          vrs) {
    vote_microdesc_hash_t *h;
    if (routerstatus_format_entry(outp, endp-outp, &vrs->status,
                                  vrs->version, NS_V3_VOTE) < 0) {
      log_warn(LD_BUG, "Unable to print router status.");
      goto err;
    }
    outp += strlen(outp);

    for (h = vrs->microdesc; h; h = h->next) {
      size_t mlen = strlen(h->microdesc_hash_line);
      if (outp+mlen >= endp) {
        log_warn(LD_BUG, "Can't fit microdesc line in vote.");
      }
      memcpy(outp, h->microdesc_hash_line, mlen+1);
      outp += strlen(outp);
    }
  } SMARTLIST_FOREACH_END(vrs);

  {
    char signing_key_fingerprint[FINGERPRINT_LEN+1];
    if (tor_snprintf(outp, endp-outp, "directory-signature ")<0) {
      log_warn(LD_BUG, "Unable to start signature line.");
      goto err;
    }
    outp += strlen(outp);

    if (crypto_pk_get_fingerprint(private_signing_key,
                                  signing_key_fingerprint, 0)<0) {
      log_warn(LD_BUG, "Unable to get fingerprint for signing key");
      goto err;
    }
    if (tor_snprintf(outp, endp-outp, "%s %s\n", fingerprint,
                     signing_key_fingerprint)<0) {
      log_warn(LD_BUG, "Unable to end signature line.");
      goto err;
    }
    outp += strlen(outp);
  }

  if (router_get_networkstatus_v3_hash(status, digest, DIGEST_SHA1)<0)
    goto err;
  note_crypto_pk_op(SIGN_DIR);
  if (router_append_dirobj_signature(outp,endp-outp,digest, DIGEST_LEN,
                                     private_signing_key)<0) {
    log_warn(LD_BUG, "Unable to sign networkstatus vote.");
    goto err;
  }

  {
    networkstatus_t *v;
    if (!(v = networkstatus_parse_vote_from_string(status, NULL,
                                                   v3_ns->type))) {
      log_err(LD_BUG,"Generated a networkstatus %s we couldn't parse: "
              "<<%s>>",
              v3_ns->type == NS_TYPE_VOTE ? "vote" : "opinion", status);
      goto err;
    }
    networkstatus_vote_free(v);
  }

  goto done;

 err:
  tor_free(status);
 done:
  tor_free(version_lines);
  return status;
}

/* =====
 * Consensus generation
 * ===== */

/** Given a vote <b>vote</b> (not a consensus!), return its associated
 * networkstatus_voter_info_t. */
static networkstatus_voter_info_t *
get_voter(const networkstatus_t *vote)
{
  tor_assert(vote);
  tor_assert(vote->type == NS_TYPE_VOTE);
  tor_assert(vote->voters);
  tor_assert(smartlist_len(vote->voters) == 1);
  return smartlist_get(vote->voters, 0);
}

/** Return the signature made by <b>voter</b> using the algorithm
 * <b>alg</b>, or NULL if none is found. */
document_signature_t *
voter_get_sig_by_algorithm(const networkstatus_voter_info_t *voter,
                           digest_algorithm_t alg)
{
  if (!voter->sigs)
    return NULL;
  SMARTLIST_FOREACH(voter->sigs, document_signature_t *, sig,
    if (sig->alg == alg)
      return sig);
  return NULL;
}

/** Temporary structure used in constructing a list of dir-source entries
 * for a consensus.  One of these is generated for every vote, and one more
 * for every legacy key in each vote. */
typedef struct dir_src_ent_t {
  networkstatus_t *v;
  const char *digest;
  int is_legacy;
} dir_src_ent_t;

/** Helper for sorting networkstatus_t votes (not consensuses) by the
 * hash of their voters' identity digests. */
static int
_compare_votes_by_authority_id(const void **_a, const void **_b)
{
  const networkstatus_t *a = *_a, *b = *_b;
  return memcmp(get_voter(a)->identity_digest,
                get_voter(b)->identity_digest, DIGEST_LEN);
}

/** Helper: Compare the dir_src_ent_ts in *<b>_a</b> and *<b>_b</b> by
 * their identity digests, and return -1, 0, or 1 depending on their
 * ordering */
static int
_compare_dir_src_ents_by_authority_id(const void **_a, const void **_b)
{
  const dir_src_ent_t *a = *_a, *b = *_b;
  const networkstatus_voter_info_t *a_v = get_voter(a->v),
    *b_v = get_voter(b->v);
  const char *a_id, *b_id;
  a_id = a->is_legacy ? a_v->legacy_id_digest : a_v->identity_digest;
  b_id = b->is_legacy ? b_v->legacy_id_digest : b_v->identity_digest;

  return memcmp(a_id, b_id, DIGEST_LEN);
}

/** Given a sorted list of strings <b>in</b>, add every member to <b>out</b>
 * that occurs more than <b>min</b> times. */
static void
get_frequent_members(smartlist_t *out, smartlist_t *in, int min)
{
  char *cur = NULL;
  int count = 0;
  SMARTLIST_FOREACH(in, char *, cp,
  {
    if (cur && !strcmp(cp, cur)) {
      ++count;
    } else {
      if (count > min)
        smartlist_add(out, cur);
      cur = cp;
      count = 1;
    }
  });
  if (count > min)
    smartlist_add(out, cur);
}

/** Given a sorted list of strings <b>lst</b>, return the member that appears
 * most.  Break ties in favor of later-occurring members. */
#define get_most_frequent_member(lst)           \
  smartlist_get_most_frequent_string(lst)

/** Return 0 if and only if <b>a</b> and <b>b</b> are routerstatuses
 * that come from the same routerinfo, with the same derived elements.
 */
static int
compare_vote_rs(const vote_routerstatus_t *a, const vote_routerstatus_t *b)
{
  int r;
  if ((r = memcmp(a->status.identity_digest, b->status.identity_digest,
                  DIGEST_LEN)))
    return r;
  if ((r = memcmp(a->status.descriptor_digest, b->status.descriptor_digest,
                  DIGEST_LEN)))
    return r;
  if ((r = (int)(b->status.published_on - a->status.published_on)))
    return r;
  if ((r = strcmp(b->status.nickname, a->status.nickname)))
    return r;
  if ((r = (((int)b->status.addr) - ((int)a->status.addr))))
    return r;
  if ((r = (((int)b->status.or_port) - ((int)a->status.or_port))))
    return r;
  if ((r = (((int)b->status.dir_port) - ((int)a->status.dir_port))))
    return r;
  return 0;
}

/** Helper for sorting routerlists based on compare_vote_rs. */
static int
_compare_vote_rs(const void **_a, const void **_b)
{
  const vote_routerstatus_t *a = *_a, *b = *_b;
  return compare_vote_rs(a,b);
}

/** Given a list of vote_routerstatus_t, all for the same router identity,
 * return whichever is most frequent, breaking ties in favor of more
 * recently published vote_routerstatus_t and in case of ties there,
 * in favor of smaller descriptor digest.
 */
static vote_routerstatus_t *
compute_routerstatus_consensus(smartlist_t *votes, int consensus_method,
                               char *microdesc_digest256_out)
{
  vote_routerstatus_t *most = NULL, *cur = NULL;
  int most_n = 0, cur_n = 0;
  time_t most_published = 0;

  /* _compare_vote_rs() sorts the items by identity digest (all the same),
   * then by SD digest.  That way, if we have a tie that the published_on
   * date cannot tie, we use the descriptor with the smaller digest.
   */
  smartlist_sort(votes, _compare_vote_rs);
  SMARTLIST_FOREACH(votes, vote_routerstatus_t *, rs,
  {
    if (cur && !compare_vote_rs(cur, rs)) {
      ++cur_n;
    } else {
      if (cur_n > most_n ||
          (cur && cur_n == most_n &&
           cur->status.published_on > most_published)) {
        most = cur;
        most_n = cur_n;
        most_published = cur->status.published_on;
      }
      cur_n = 1;
      cur = rs;
    }
  });

  if (cur_n > most_n ||
      (cur && cur_n == most_n && cur->status.published_on > most_published)) {
    most = cur;
    most_n = cur_n;
    most_published = cur->status.published_on;
  }

  tor_assert(most);

  if (consensus_method >= MIN_METHOD_FOR_MICRODESC &&
      microdesc_digest256_out) {
    smartlist_t *digests = smartlist_create();
    const char *best_microdesc_digest;
    SMARTLIST_FOREACH_BEGIN(votes, vote_routerstatus_t *, rs) {
        char d[DIGEST256_LEN];
        if (compare_vote_rs(rs, most))
          continue;
        if (!vote_routerstatus_find_microdesc_hash(d, rs, consensus_method,
                                                   DIGEST_SHA256))
          smartlist_add(digests, tor_memdup(d, sizeof(d)));
    } SMARTLIST_FOREACH_END(rs);
    smartlist_sort_digests256(digests);
    best_microdesc_digest = smartlist_get_most_frequent_digest256(digests);
    if (best_microdesc_digest)
      memcpy(microdesc_digest256_out, best_microdesc_digest, DIGEST256_LEN);
    SMARTLIST_FOREACH(digests, char *, cp, tor_free(cp));
    smartlist_free(digests);
  }

  return most;
}

/** Given a list of strings in <b>lst</b>, set the <b>len_out</b>-byte digest
 * at <b>digest_out</b> to the hash of the concatenation of those strings,
 * computed with the algorithm <b>alg</b>. */
static void
hash_list_members(char *digest_out, size_t len_out,
                  smartlist_t *lst, digest_algorithm_t alg)
{
  crypto_digest_env_t *d;
  if (alg == DIGEST_SHA1)
    d = crypto_new_digest_env();
  else
    d = crypto_new_digest256_env(alg);
  SMARTLIST_FOREACH(lst, const char *, cp,
                    crypto_digest_add_bytes(d, cp, strlen(cp)));
  crypto_digest_get_digest(d, digest_out, len_out);
  crypto_free_digest_env(d);
}

/** Sorting helper: compare two strings based on their values as base-ten
 * positive integers. (Non-integers are treated as prior to all integers, and
 * compared lexically.) */
static int
_cmp_int_strings(const void **_a, const void **_b)
{
  const char *a = *_a, *b = *_b;
  int ai = (int)tor_parse_long(a, 10, 1, INT_MAX, NULL, NULL);
  int bi = (int)tor_parse_long(b, 10, 1, INT_MAX, NULL, NULL);
  if (ai<bi) {
    return -1;
  } else if (ai==bi) {
    if (ai == 0) /* Parsing failed. */
      return strcmp(a, b);
    return 0;
  } else {
    return 1;
  }
}

/** Given a list of networkstatus_t votes, determine and return the number of
 * the highest consensus method that is supported by 2/3 of the voters. */
static int
compute_consensus_method(smartlist_t *votes)
{
  smartlist_t *all_methods = smartlist_create();
  smartlist_t *acceptable_methods = smartlist_create();
  smartlist_t *tmp = smartlist_create();
  int min = (smartlist_len(votes) * 2) / 3;
  int n_ok;
  int result;
  SMARTLIST_FOREACH(votes, networkstatus_t *, vote,
  {
    tor_assert(vote->supported_methods);
    smartlist_add_all(tmp, vote->supported_methods);
    smartlist_sort(tmp, _cmp_int_strings);
    smartlist_uniq(tmp, _cmp_int_strings, NULL);
    smartlist_add_all(all_methods, tmp);
    smartlist_clear(tmp);
  });

  smartlist_sort(all_methods, _cmp_int_strings);
  get_frequent_members(acceptable_methods, all_methods, min);
  n_ok = smartlist_len(acceptable_methods);
  if (n_ok) {
    const char *best = smartlist_get(acceptable_methods, n_ok-1);
    result = (int)tor_parse_long(best, 10, 1, INT_MAX, NULL, NULL);
  } else {
    result = 1;
  }
  smartlist_free(tmp);
  smartlist_free(all_methods);
  smartlist_free(acceptable_methods);
  return result;
}

/** Return true iff <b>method</b> is a consensus method that we support. */
static int
consensus_method_is_supported(int method)
{
  return (method >= 1) && (method <= MAX_SUPPORTED_CONSENSUS_METHOD);
}

/** Return a newly allocated string holding the numbers between low and high
 * (inclusive) that are supported consensus methods. */
static char *
make_consensus_method_list(int low, int high, const char *separator)
{
  char *list;

  char b[32];
  int i;
  smartlist_t *lst;
  lst = smartlist_create();
  for (i = low; i <= high; ++i) {
    if (!consensus_method_is_supported(i))
      continue;
    tor_snprintf(b, sizeof(b), "%d", i);
    smartlist_add(lst, tor_strdup(b));
  }
  list = smartlist_join_strings(lst, separator, 0, NULL);
  tor_assert(list);
  SMARTLIST_FOREACH(lst, char *, cp, tor_free(cp));
  smartlist_free(lst);
  return list;
}

/** Helper: given <b>lst</b>, a list of version strings such that every
 * version appears once for every versioning voter who recommends it, return a
 * newly allocated string holding the resulting client-versions or
 * server-versions list. May change contents of <b>lst</b> */
static char *
compute_consensus_versions_list(smartlist_t *lst, int n_versioning)
{
  int min = n_versioning / 2;
  smartlist_t *good = smartlist_create();
  char *result;
  sort_version_list(lst, 0);
  get_frequent_members(good, lst, min);
  result = smartlist_join_strings(good, ",", 0, NULL);
  smartlist_free(good);
  return result;
}

/** Helper: given a list of valid networkstatus_t, return a new string
 * containing the contents of the consensus network parameter set.
 */
/* private */ char *
dirvote_compute_params(smartlist_t *votes)
{
  int i;
  int32_t *vals;

  int cur_param_len;
  const char *cur_param;
  const char *eq;
  char *result;

  const int n_votes = smartlist_len(votes);
  smartlist_t *output;
  smartlist_t *param_list = smartlist_create();

  /* We require that the parameter lists in the votes are well-formed: that
     is, that their keywords are unique and sorted, and that their values are
     between INT32_MIN and INT32_MAX inclusive.  This should be guaranteed by
     the parsing code. */

  vals = tor_malloc(sizeof(int)*n_votes);

  SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
    if (!v->net_params)
      continue;
    smartlist_add_all(param_list, v->net_params);
  } SMARTLIST_FOREACH_END(v);

  if (smartlist_len(param_list) == 0) {
    tor_free(vals);
    smartlist_free(param_list);
    return NULL;
  }

  smartlist_sort_strings(param_list);
  i = 0;
  cur_param = smartlist_get(param_list, 0);
  eq = strchr(cur_param, '=');
  tor_assert(eq);
  cur_param_len = (int)(eq+1 - cur_param);

  output = smartlist_create();

  SMARTLIST_FOREACH_BEGIN(param_list, const char *, param) {
    const char *next_param;
    int ok=0;
    eq = strchr(param, '=');
    tor_assert(i<n_votes);
    vals[i++] = (int32_t)
      tor_parse_long(eq+1, 10, INT32_MIN, INT32_MAX, &ok, NULL);
    tor_assert(ok);

    if (param_sl_idx+1 == smartlist_len(param_list))
      next_param = NULL;
    else
      next_param = smartlist_get(param_list, param_sl_idx+1);
    if (!next_param || strncmp(next_param, param, cur_param_len)) {
      /* We've reached the end of a series. */
      int32_t median = median_int32(vals, i);
      char *out_string = tor_malloc(64+cur_param_len);
      memcpy(out_string, param, cur_param_len);
      tor_snprintf(out_string+cur_param_len,64, "%ld", (long)median);
      smartlist_add(output, out_string);

      i = 0;
      if (next_param) {
        eq = strchr(next_param, '=');
        cur_param_len = (int)(eq+1 - next_param);
      }
    }
  } SMARTLIST_FOREACH_END(param);

  result = smartlist_join_strings(output, " ", 0, NULL);
  SMARTLIST_FOREACH(output, char *, cp, tor_free(cp));
  smartlist_free(output);
  smartlist_free(param_list);
  tor_free(vals);
  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
 * voting quorum, generate the text of a new v3 consensus vote, and return the
 * value in a newly allocated string.
 *
 * Note: this function DOES NOT check whether the votes are from
 * recognized authorities.   (dirvote_add_vote does that.) */
char *
networkstatus_compute_consensus(smartlist_t *votes,
                                int total_authorities,
                                crypto_pk_env_t *identity_key,
                                crypto_pk_env_t *signing_key,
                                const char *legacy_id_key_digest,
                                crypto_pk_env_t *legacy_signing_key,
                                consensus_flavor_t flavor)
{
  smartlist_t *chunks;
  char *result = NULL;
  int consensus_method;
  time_t valid_after, fresh_until, valid_until;
  int vote_seconds, dist_seconds;
  char *client_versions = NULL, *server_versions = NULL;
  smartlist_t *flags;
  const char *flavor_name;
  const routerstatus_format_type_t rs_format =
    flavor == FLAV_NS ? NS_V3_CONSENSUS : NS_V3_CONSENSUS_MICRODESC;

  tor_assert(flavor == FLAV_NS || flavor == FLAV_MICRODESC);
  tor_assert(total_authorities >= smartlist_len(votes));

  flavor_name = networkstatus_get_flavor_name(flavor);

  if (!smartlist_len(votes)) {
    log_warn(LD_DIR, "Can't compute a consensus from no votes.");
    return NULL;
  }
  flags = smartlist_create();

  consensus_method = compute_consensus_method(votes);
  if (consensus_method_is_supported(consensus_method)) {
    log_info(LD_DIR, "Generating consensus using method %d.",
             consensus_method);
  } else {
    log_warn(LD_DIR, "The other authorities will use consensus method %d, "
             "which I don't support.  Maybe I should upgrade!",
             consensus_method);
    consensus_method = 1;
  }

  /* Compute medians of time-related things, and figure out how many
   * routers we might need to talk about. */
  {
    int n_votes = smartlist_len(votes);
    time_t *va_times = tor_malloc(n_votes * sizeof(time_t));
    time_t *fu_times = tor_malloc(n_votes * sizeof(time_t));
    time_t *vu_times = tor_malloc(n_votes * sizeof(time_t));
    int *votesec_list = tor_malloc(n_votes * sizeof(int));
    int *distsec_list = tor_malloc(n_votes * sizeof(int));
    int n_versioning_clients = 0, n_versioning_servers = 0;
    smartlist_t *combined_client_versions = smartlist_create();
    smartlist_t *combined_server_versions = smartlist_create();

    SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
      tor_assert(v->type == NS_TYPE_VOTE);
      va_times[v_sl_idx] = v->valid_after;
      fu_times[v_sl_idx] = v->fresh_until;
      vu_times[v_sl_idx] = v->valid_until;
      votesec_list[v_sl_idx] = v->vote_seconds;
      distsec_list[v_sl_idx] = v->dist_seconds;
      if (v->client_versions) {
        smartlist_t *cv = smartlist_create();
        ++n_versioning_clients;
        smartlist_split_string(cv, v->client_versions, ",",
                               SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
        sort_version_list(cv, 1);
        smartlist_add_all(combined_client_versions, cv);
        smartlist_free(cv); /* elements get freed later. */
      }
      if (v->server_versions) {
        smartlist_t *sv = smartlist_create();
        ++n_versioning_servers;
        smartlist_split_string(sv, v->server_versions, ",",
                               SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
        sort_version_list(sv, 1);
        smartlist_add_all(combined_server_versions, sv);
        smartlist_free(sv); /* elements get freed later. */
      }
      SMARTLIST_FOREACH(v->known_flags, const char *, cp,
                        smartlist_add(flags, tor_strdup(cp)));
    } SMARTLIST_FOREACH_END(v);
    valid_after = median_time(va_times, n_votes);
    fresh_until = median_time(fu_times, n_votes);
    valid_until = median_time(vu_times, n_votes);
    vote_seconds = median_int(votesec_list, n_votes);
    dist_seconds = median_int(distsec_list, n_votes);

    tor_assert(valid_after+MIN_VOTE_INTERVAL <= fresh_until);
    tor_assert(fresh_until+MIN_VOTE_INTERVAL <= valid_until);
    tor_assert(vote_seconds >= MIN_VOTE_SECONDS);
    tor_assert(dist_seconds >= MIN_DIST_SECONDS);

    server_versions = compute_consensus_versions_list(combined_server_versions,
                                                      n_versioning_servers);
    client_versions = compute_consensus_versions_list(combined_client_versions,
                                                      n_versioning_clients);

    SMARTLIST_FOREACH(combined_server_versions, char *, cp, tor_free(cp));
    SMARTLIST_FOREACH(combined_client_versions, char *, cp, tor_free(cp));
    smartlist_free(combined_server_versions);
    smartlist_free(combined_client_versions);

    smartlist_sort_strings(flags);
    smartlist_uniq_strings(flags);

    tor_free(va_times);
    tor_free(fu_times);
    tor_free(vu_times);
    tor_free(votesec_list);
    tor_free(distsec_list);
  }

  chunks = smartlist_create();

  {
    char buf[1024];
    char va_buf[ISO_TIME_LEN+1], fu_buf[ISO_TIME_LEN+1],
      vu_buf[ISO_TIME_LEN+1];
    char *flaglist;
    format_iso_time(va_buf, valid_after);
    format_iso_time(fu_buf, fresh_until);
    format_iso_time(vu_buf, valid_until);
    flaglist = smartlist_join_strings(flags, " ", 0, NULL);

    tor_snprintf(buf, sizeof(buf), "network-status-version 3%s%s\n"
                 "vote-status consensus\n",
                 flavor == FLAV_NS ? "" : " ",
                 flavor == FLAV_NS ? "" : flavor_name);

    smartlist_add(chunks, tor_strdup(buf));

    if (consensus_method >= 2) {
      tor_snprintf(buf, sizeof(buf), "consensus-method %d\n",
                   consensus_method);
      smartlist_add(chunks, tor_strdup(buf));
    }

    tor_snprintf(buf, sizeof(buf),
                 "valid-after %s\n"
                 "fresh-until %s\n"
                 "valid-until %s\n"
                 "voting-delay %d %d\n"
                 "client-versions %s\n"
                 "server-versions %s\n"
                 "known-flags %s\n",
                 va_buf, fu_buf, vu_buf,
                 vote_seconds, dist_seconds,
                 client_versions, server_versions, flaglist);
    smartlist_add(chunks, tor_strdup(buf));

    tor_free(flaglist);
  }

  if (consensus_method >= MIN_METHOD_FOR_PARAMS) {
    char *params = dirvote_compute_params(votes);
    if (params) {
      smartlist_add(chunks, tor_strdup("params "));
      smartlist_add(chunks, params);
      smartlist_add(chunks, tor_strdup("\n"));
    }
  }

  /* Sort the votes. */
  smartlist_sort(votes, _compare_votes_by_authority_id);
  /* Add the authority sections. */
  {
    smartlist_t *dir_sources = smartlist_create();
    SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
      dir_src_ent_t *e = tor_malloc_zero(sizeof(dir_src_ent_t));
      e->v = v;
      e->digest = get_voter(v)->identity_digest;
      e->is_legacy = 0;
      smartlist_add(dir_sources, e);
      if (consensus_method >= 3 &&
          !tor_digest_is_zero(get_voter(v)->legacy_id_digest)) {
        dir_src_ent_t *e_legacy = tor_malloc_zero(sizeof(dir_src_ent_t));
        e_legacy->v = v;
        e_legacy->digest = get_voter(v)->legacy_id_digest;
        e_legacy->is_legacy = 1;
        smartlist_add(dir_sources, e_legacy);
      }
    } SMARTLIST_FOREACH_END(v);
    smartlist_sort(dir_sources, _compare_dir_src_ents_by_authority_id);

    SMARTLIST_FOREACH(dir_sources, const dir_src_ent_t *, e,
    {
      char buf[1024];
      struct in_addr in;
      char ip[INET_NTOA_BUF_LEN];
      char fingerprint[HEX_DIGEST_LEN+1];
      char votedigest[HEX_DIGEST_LEN+1];
      networkstatus_t *v = e->v;
      networkstatus_voter_info_t *voter = get_voter(v);

      if (e->is_legacy)
        tor_assert(consensus_method >= 2);

      in.s_addr = htonl(voter->addr);
      tor_inet_ntoa(&in, ip, sizeof(ip));
      base16_encode(fingerprint, sizeof(fingerprint), e->digest, DIGEST_LEN);
      base16_encode(votedigest, sizeof(votedigest), voter->vote_digest,
                    DIGEST_LEN);

      tor_snprintf(buf, sizeof(buf),
                   "dir-source %s%s %s %s %s %d %d\n",
                   voter->nickname, e->is_legacy ? "-legacy" : "",
                   fingerprint, voter->address, ip,
                   voter->dir_port,
                   voter->or_port);
      smartlist_add(chunks, tor_strdup(buf));
      if (! e->is_legacy) {
        tor_snprintf(buf, sizeof(buf),
                     "contact %s\n"
                     "vote-digest %s\n",
                     voter->contact,
                     votedigest);
        smartlist_add(chunks, tor_strdup(buf));
      }
    });
    SMARTLIST_FOREACH(dir_sources, dir_src_ent_t *, e, tor_free(e));
    smartlist_free(dir_sources);
  }

  /* Add the actual router entries. */
  {
    int *index; /* index[j] is the current index into votes[j]. */
    int *size; /* size[j] is the number of routerstatuses in votes[j]. */
    int *flag_counts; /* The number of voters that list flag[j] for the
                       * currently considered router. */
    int i;
    smartlist_t *matching_descs = smartlist_create();
    smartlist_t *chosen_flags = smartlist_create();
    smartlist_t *versions = smartlist_create();
    smartlist_t *exitsummaries = smartlist_create();
    uint32_t *bandwidths = tor_malloc(sizeof(uint32_t) * smartlist_len(votes));
    uint32_t *measured_bws = tor_malloc(sizeof(uint32_t) *
                                        smartlist_len(votes));
    int num_bandwidths;
    int num_mbws;

    int *n_voter_flags; /* n_voter_flags[j] is the number of flags that
                         * votes[j] knows about. */
    int *n_flag_voters; /* n_flag_voters[f] is the number of votes that care
                         * about flags[f]. */
    int **flag_map; /* flag_map[j][b] is an index f such that flag_map[f]
                     * is the same flag as votes[j]->known_flags[b]. */
    int *named_flag; /* Index of the flag "Named" for votes[j] */
    int *unnamed_flag; /* Index of the flag "Unnamed" for votes[j] */
    int chosen_named_idx, chosen_unnamed_idx;

    strmap_t *name_to_id_map = strmap_new();
    char conflict[DIGEST_LEN];
    char unknown[DIGEST_LEN];
    memset(conflict, 0, sizeof(conflict));
    memset(unknown, 0xff, sizeof(conflict));

    index = tor_malloc_zero(sizeof(int)*smartlist_len(votes));
    size = tor_malloc_zero(sizeof(int)*smartlist_len(votes));
    n_voter_flags = tor_malloc_zero(sizeof(int) * smartlist_len(votes));
    n_flag_voters = tor_malloc_zero(sizeof(int) * smartlist_len(flags));
    flag_map = tor_malloc_zero(sizeof(int*) * smartlist_len(votes));
    named_flag = tor_malloc_zero(sizeof(int) * smartlist_len(votes));
    unnamed_flag = tor_malloc_zero(sizeof(int) * smartlist_len(votes));
    for (i = 0; i < smartlist_len(votes); ++i)
      unnamed_flag[i] = named_flag[i] = -1;
    chosen_named_idx = smartlist_string_pos(flags, "Named");
    chosen_unnamed_idx = smartlist_string_pos(flags, "Unnamed");

    /* Build the flag index. */
    SMARTLIST_FOREACH(votes, networkstatus_t *, v,
    {
      flag_map[v_sl_idx] = tor_malloc_zero(
                           sizeof(int)*smartlist_len(v->known_flags));
      SMARTLIST_FOREACH(v->known_flags, const char *, fl,
      {
        int p = smartlist_string_pos(flags, fl);
        tor_assert(p >= 0);
        flag_map[v_sl_idx][fl_sl_idx] = p;
        ++n_flag_voters[p];
        if (!strcmp(fl, "Named"))
          named_flag[v_sl_idx] = fl_sl_idx;
        if (!strcmp(fl, "Unnamed"))
          unnamed_flag[v_sl_idx] = fl_sl_idx;
      });
      n_voter_flags[v_sl_idx] = smartlist_len(v->known_flags);
      size[v_sl_idx] = smartlist_len(v->routerstatus_list);
    });

    /* Named and Unnamed get treated specially */
    if (consensus_method >= 2) {
      SMARTLIST_FOREACH(votes, networkstatus_t *, v,
      {
        uint64_t nf;
        if (named_flag[v_sl_idx]<0)
          continue;
        nf = U64_LITERAL(1) << named_flag[v_sl_idx];
        SMARTLIST_FOREACH(v->routerstatus_list, vote_routerstatus_t *, rs,
        {
          if ((rs->flags & nf) != 0) {
            const char *d = strmap_get_lc(name_to_id_map, rs->status.nickname);
            if (!d) {
              /* We have no name officially mapped to this digest. */
              strmap_set_lc(name_to_id_map, rs->status.nickname,
                            rs->status.identity_digest);
            } else if (d != conflict &&
                memcmp(d, rs->status.identity_digest, DIGEST_LEN)) {
              /* Authorities disagree about this nickname. */
              strmap_set_lc(name_to_id_map, rs->status.nickname, conflict);
            } else {
              /* It's already a conflict, or it's already this ID. */
            }
          }
        });
      });
      SMARTLIST_FOREACH(votes, networkstatus_t *, v,
      {
        uint64_t uf;
        if (unnamed_flag[v_sl_idx]<0)
          continue;
        uf = U64_LITERAL(1) << unnamed_flag[v_sl_idx];
        SMARTLIST_FOREACH(v->routerstatus_list, vote_routerstatus_t *, rs,
        {
          if ((rs->flags & uf) != 0) {
            const char *d = strmap_get_lc(name_to_id_map, rs->status.nickname);
            if (d == conflict || d == unknown) {
              /* Leave it alone; we know what it is. */
            } else if (!d) {
              /* We have no name officially mapped to this digest. */
              strmap_set_lc(name_to_id_map, rs->status.nickname, unknown);
            } else if (!memcmp(d, rs->status.identity_digest, DIGEST_LEN)) {
              /* Authorities disagree about this nickname. */
              strmap_set_lc(name_to_id_map, rs->status.nickname, conflict);
            } else {
              /* It's mapped to a different name. */
            }
          }
        });
      });
    }