diff options
Diffstat (limited to 'src/or/dirauth')
| -rw-r--r-- | src/or/dirauth/dircollate.c | 324 | ||||
| -rw-r--r-- | src/or/dirauth/dircollate.h | 70 | ||||
| -rw-r--r-- | src/or/dirauth/dirvote.c | 4544 | ||||
| -rw-r--r-- | src/or/dirauth/dirvote.h | 247 | ||||
| -rw-r--r-- | src/or/dirauth/mode.h | 38 | ||||
| -rw-r--r-- | src/or/dirauth/shared_random.c | 1289 | ||||
| -rw-r--r-- | src/or/dirauth/shared_random.h | 194 | ||||
| -rw-r--r-- | src/or/dirauth/shared_random_state.c | 1323 | ||||
| -rw-r--r-- | src/or/dirauth/shared_random_state.h | 147 |
9 files changed, 8176 insertions, 0 deletions
diff --git a/src/or/dirauth/dircollate.c b/src/or/dirauth/dircollate.c new file mode 100644 index 0000000000..dec6f75154 --- /dev/null +++ b/src/or/dirauth/dircollate.c @@ -0,0 +1,324 @@ +/* Copyright (c) 2001-2004, Roger Dingledine. + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2017, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file dircollate.c + * + * \brief Collation code for figuring out which identities to vote for in + * the directory voting process. + * + * During the consensus calculation, when an authority is looking at the vote + * documents from all the authorities, it needs to compute the consensus for + * each relay listed by at least one authority. But the notion of "each + * relay" can be tricky: some relays have Ed25519 keys, and others don't. + * + * Moreover, older consensus methods did RSA-based ID collation alone, and + * ignored Ed25519 keys. We need to support those too until we're completely + * sure that authorities will never downgrade. + * + * This module is invoked exclusively from dirvote.c. + */ + +#define DIRCOLLATE_PRIVATE +#include "dircollate.h" +#include "dirvote.h" + +static void dircollator_collate_by_ed25519(dircollator_t *dc); + +/** Hashtable entry mapping a pair of digests (actually an ed25519 key and an + * RSA SHA1 digest) to an array of vote_routerstatus_t. */ +typedef struct ddmap_entry_s { + HT_ENTRY(ddmap_entry_s) node; + /** A SHA1-RSA1024 identity digest and Ed25519 identity key, + * concatenated. (If there is no ed25519 identity key, there is no + * entry in this table.) */ + uint8_t d[DIGEST_LEN + DIGEST256_LEN]; + /* The nth member of this array corresponds to the vote_routerstatus_t (if + * any) received for this digest pair from the nth voter. */ + vote_routerstatus_t *vrs_lst[FLEXIBLE_ARRAY_MEMBER]; +} ddmap_entry_t; + +#define ddmap_entry_free(e) \ + FREE_AND_NULL(ddmap_entry_t, ddmap_entry_free_, (e)) + +/** Release all storage held by e. */ +static void +ddmap_entry_free_(ddmap_entry_t *e) +{ + tor_free(e); +} + +/** Return a new empty ddmap_entry, with <b>n_votes</b> elements in + * vrs_list. */ +static ddmap_entry_t * +ddmap_entry_new(int n_votes) +{ + return tor_malloc_zero(offsetof(ddmap_entry_t, vrs_lst) + + sizeof(vote_routerstatus_t *) * n_votes); +} + +/** Helper: compute a hash of a single ddmap_entry_t's identity (or + * identities) */ +static unsigned +ddmap_entry_hash(const ddmap_entry_t *ent) +{ + return (unsigned) siphash24g(ent->d, sizeof(ent->d)); +} + +/** Helper: return true if <b>a</b> and <b>b</b> have the same + * identity/identities. */ +static unsigned +ddmap_entry_eq(const ddmap_entry_t *a, const ddmap_entry_t *b) +{ + return fast_memeq(a->d, b->d, sizeof(a->d)); +} + +/** Record the RSA identity of <b>ent</b> as <b>rsa_sha1</b>, and the + * ed25519 identity as <b>ed25519</b>. Both must be provided. */ +static void +ddmap_entry_set_digests(ddmap_entry_t *ent, + const uint8_t *rsa_sha1, + const uint8_t *ed25519) +{ + memcpy(ent->d, rsa_sha1, DIGEST_LEN); + memcpy(ent->d + DIGEST_LEN, ed25519, DIGEST256_LEN); +} + +HT_PROTOTYPE(double_digest_map, ddmap_entry_s, node, ddmap_entry_hash, + ddmap_entry_eq) +HT_GENERATE2(double_digest_map, ddmap_entry_s, node, ddmap_entry_hash, + ddmap_entry_eq, 0.6, tor_reallocarray, tor_free_) + +/** Helper: add a single vote_routerstatus_t <b>vrs</b> to the collator + * <b>dc</b>, indexing it by its RSA key digest, and by the 2-tuple of its RSA + * key digest and Ed25519 key. It must come from the <b>vote_num</b>th + * vote. + * + * Requires that the vote is well-formed -- that is, that it has no duplicate + * routerstatus entries. We already checked for that when parsing the vote. */ +static void +dircollator_add_routerstatus(dircollator_t *dc, + int vote_num, + networkstatus_t *vote, + vote_routerstatus_t *vrs) +{ + const char *id = vrs->status.identity_digest; + + /* Clear this flag; we might set it later during the voting process */ + vrs->ed25519_reflects_consensus = 0; + + (void) vote; // We don't currently need this. + + /* First, add this item to the appropriate RSA-SHA-Id array. */ + vote_routerstatus_t **vrs_lst = digestmap_get(dc->by_rsa_sha1, id); + if (NULL == vrs_lst) { + vrs_lst = tor_calloc(dc->n_votes, sizeof(vote_routerstatus_t *)); + digestmap_set(dc->by_rsa_sha1, id, vrs_lst); + } + tor_assert(vrs_lst[vote_num] == NULL); + vrs_lst[vote_num] = vrs; + + const uint8_t *ed = vrs->ed25519_id; + + if (! vrs->has_ed25519_listing) + return; + + /* Now add it to the appropriate <Ed,RSA-SHA-Id> array. */ + ddmap_entry_t search, *found; + memset(&search, 0, sizeof(search)); + ddmap_entry_set_digests(&search, (const uint8_t *)id, ed); + found = HT_FIND(double_digest_map, &dc->by_both_ids, &search); + if (NULL == found) { + found = ddmap_entry_new(dc->n_votes); + ddmap_entry_set_digests(found, (const uint8_t *)id, ed); + HT_INSERT(double_digest_map, &dc->by_both_ids, found); + } + vrs_lst = found->vrs_lst; + tor_assert(vrs_lst[vote_num] == NULL); + vrs_lst[vote_num] = vrs; +} + +/** Create and return a new dircollator object to use when collating + * <b>n_votes</b> out of a total of <b>n_authorities</b>. */ +dircollator_t * +dircollator_new(int n_votes, int n_authorities) +{ + dircollator_t *dc = tor_malloc_zero(sizeof(dircollator_t)); + + tor_assert(n_votes <= n_authorities); + + dc->n_votes = n_votes; + dc->n_authorities = n_authorities; + + dc->by_rsa_sha1 = digestmap_new(); + HT_INIT(double_digest_map, &dc->by_both_ids); + + return dc; +} + +/** Release all storage held by <b>dc</b>. */ +void +dircollator_free_(dircollator_t *dc) +{ + if (!dc) + return; + + if (dc->by_collated_rsa_sha1 != dc->by_rsa_sha1) + digestmap_free(dc->by_collated_rsa_sha1, NULL); + + digestmap_free(dc->by_rsa_sha1, tor_free_); + smartlist_free(dc->all_rsa_sha1_lst); + + ddmap_entry_t **e, **next, *this; + for (e = HT_START(double_digest_map, &dc->by_both_ids); + e != NULL; e = next) { + this = *e; + next = HT_NEXT_RMV(double_digest_map, &dc->by_both_ids, e); + ddmap_entry_free(this); + } + HT_CLEAR(double_digest_map, &dc->by_both_ids); + + tor_free(dc); +} + +/** Add a single vote <b>v</b> to a dircollator <b>dc</b>. This function must + * be called exactly once for each vote to be used in the consensus. It may + * only be called before dircollator_collate(). + */ +void +dircollator_add_vote(dircollator_t *dc, networkstatus_t *v) +{ + tor_assert(v->type == NS_TYPE_VOTE); + tor_assert(dc->next_vote_num < dc->n_votes); + tor_assert(!dc->is_collated); + + const int votenum = dc->next_vote_num++; + + SMARTLIST_FOREACH_BEGIN(v->routerstatus_list, vote_routerstatus_t *, vrs) { + dircollator_add_routerstatus(dc, votenum, v, vrs); + } SMARTLIST_FOREACH_END(vrs); +} + +/** Sort the entries in <b>dc</b> according to <b>consensus_method</b>, so + * that the consensus process can iterate over them with + * dircollator_n_routers() and dircollator_get_votes_for_router(). */ +void +dircollator_collate(dircollator_t *dc, int consensus_method) +{ + (void) consensus_method; + + tor_assert(!dc->is_collated); + dc->all_rsa_sha1_lst = smartlist_new(); + + dircollator_collate_by_ed25519(dc); + + smartlist_sort_digests(dc->all_rsa_sha1_lst); + dc->is_collated = 1; +} + +/** + * Collation function for ed25519 consensuses: collate the votes for each + * entry in <b>dc</b> by ed25519 key and by RSA key. + * + * The rule is, approximately: + * If a (ed,rsa) identity is listed by more than half of authorities, + * include it. And include all (rsa)-only votes about that node as + * matching. + * + * Otherwise, if an (*,rsa) or (rsa) identity is listed by more than + * half of the authorities, and no (ed,rsa) pair for the same RSA key + * has been already been included based on the rule above, include + * that RSA identity. + */ +static void +dircollator_collate_by_ed25519(dircollator_t *dc) +{ + const int total_authorities = dc->n_authorities; + digestmap_t *rsa_digests = digestmap_new(); + + ddmap_entry_t **iter; + + /* Go over all <ed,rsa> pairs */ + HT_FOREACH(iter, double_digest_map, &dc->by_both_ids) { + ddmap_entry_t *ent = *iter; + int n = 0, i; + for (i = 0; i < dc->n_votes; ++i) { + if (ent->vrs_lst[i] != NULL) + ++n; + } + + /* If not enough authorties listed this exact <ed,rsa> pair, + * don't include it. */ + if (n <= total_authorities / 2) + continue; + + /* Now consider whether there are any other entries with the same + * RSA key (but with possibly different or missing ed value). */ + vote_routerstatus_t **vrs_lst2 = digestmap_get(dc->by_rsa_sha1, + (char*)ent->d); + tor_assert(vrs_lst2); + + for (i = 0; i < dc->n_votes; ++i) { + if (ent->vrs_lst[i] != NULL) { + ent->vrs_lst[i]->ed25519_reflects_consensus = 1; + } else if (vrs_lst2[i] && ! vrs_lst2[i]->has_ed25519_listing) { + ent->vrs_lst[i] = vrs_lst2[i]; + } + } + + /* Record that we have seen this RSA digest. */ + digestmap_set(rsa_digests, (char*)ent->d, ent->vrs_lst); + smartlist_add(dc->all_rsa_sha1_lst, ent->d); + } + + /* Now look over all entries with an RSA digest, looking for RSA digests + * we didn't put in yet. + */ + DIGESTMAP_FOREACH(dc->by_rsa_sha1, k, vote_routerstatus_t **, vrs_lst) { + if (digestmap_get(rsa_digests, k) != NULL) + continue; /* We already included this RSA digest */ + + int n = 0, i; + for (i = 0; i < dc->n_votes; ++i) { + if (vrs_lst[i] != NULL) + ++n; + } + + if (n <= total_authorities / 2) + continue; /* Not enough votes */ + + digestmap_set(rsa_digests, k, vrs_lst); + smartlist_add(dc->all_rsa_sha1_lst, (char *)k); + } DIGESTMAP_FOREACH_END; + + dc->by_collated_rsa_sha1 = rsa_digests; +} + +/** Return the total number of collated router entries. This function may + * only be called after dircollator_collate. */ +int +dircollator_n_routers(dircollator_t *dc) +{ + tor_assert(dc->is_collated); + return smartlist_len(dc->all_rsa_sha1_lst); +} + +/** Return an array of vote_routerstatus_t entries for the <b>idx</b>th router + * in the collation order. Each array contains n_votes elements, where the + * nth element of the array is the vote_routerstatus_t from the nth voter for + * this identity (or NULL if there is no such entry). + * + * The maximum value for <b>idx</b> is dircollator_n_routers(). + * + * This function may only be called after dircollator_collate. */ +vote_routerstatus_t ** +dircollator_get_votes_for_router(dircollator_t *dc, int idx) +{ + tor_assert(dc->is_collated); + tor_assert(idx < smartlist_len(dc->all_rsa_sha1_lst)); + return digestmap_get(dc->by_collated_rsa_sha1, + smartlist_get(dc->all_rsa_sha1_lst, idx)); +} + diff --git a/src/or/dirauth/dircollate.h b/src/or/dirauth/dircollate.h new file mode 100644 index 0000000000..0584b2fe06 --- /dev/null +++ b/src/or/dirauth/dircollate.h @@ -0,0 +1,70 @@ +/* Copyright (c) 2001 Matej Pfajfar. + * Copyright (c) 2001-2004, Roger Dingledine. + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2017, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file dircollate.h + * \brief Header file for dircollate.c. + **/ + +#ifndef TOR_DIRCOLLATE_H +#define TOR_DIRCOLLATE_H + +#include "testsupport.h" +#include "or.h" + +typedef struct dircollator_s dircollator_t; + +dircollator_t *dircollator_new(int n_votes, int n_authorities); +void dircollator_free_(dircollator_t *obj); +#define dircollator_free(c) \ + FREE_AND_NULL(dircollator_t, dircollator_free_, (c)) +void dircollator_add_vote(dircollator_t *dc, networkstatus_t *v); + +void dircollator_collate(dircollator_t *dc, int consensus_method); + +int dircollator_n_routers(dircollator_t *dc); +vote_routerstatus_t **dircollator_get_votes_for_router(dircollator_t *dc, + int idx); + +#ifdef DIRCOLLATE_PRIVATE +struct ddmap_entry_s; +typedef HT_HEAD(double_digest_map, ddmap_entry_s) double_digest_map_t; +/** A dircollator keeps track of all the routerstatus entries in a + * set of networkstatus votes, and matches them by an appropriate rule. */ +struct dircollator_s { + /** True iff we have run the collation algorithm. */ + int is_collated; + /** The total number of votes that we received. */ + int n_votes; + /** The total number of authorities we acknowledge. */ + int n_authorities; + + /** The index which the next vote to be added to this collator should + * receive. */ + int next_vote_num; + /** Map from RSA-SHA1 identity digest to an array of <b>n_votes</b> + * vote_routerstatus_t* pointers, such that the i'th member of the + * array is the i'th vote's entry for that RSA-SHA1 ID.*/ + digestmap_t *by_rsa_sha1; + /** Map from <ed, RSA-SHA1> pair to an array similar to that used in + * by_rsa_sha1 above. We include <NULL,RSA-SHA1> entries for votes that + * say that there is no Ed key. */ + struct double_digest_map by_both_ids; + + /** One of two outputs created by collation: a map from RSA-SHA1 + * identity digest to an array of the vote_routerstatus_t objects. Entries + * only exist in this map for identities that we should include in the + * consensus. */ + digestmap_t *by_collated_rsa_sha1; + + /** One of two outputs created by collation: a sorted array of RSA-SHA1 + * identity digests .*/ + smartlist_t *all_rsa_sha1_lst; +}; +#endif /* defined(DIRCOLLATE_PRIVATE) */ + +#endif /* !defined(TOR_DIRCOLLATE_H) */ + diff --git a/src/or/dirauth/dirvote.c b/src/or/dirauth/dirvote.c new file mode 100644 index 0000000000..cbc3ff7829 --- /dev/null +++ b/src/or/dirauth/dirvote.c @@ -0,0 +1,4544 @@ +/* Copyright (c) 2001-2004, Roger Dingledine. + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2017, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#define DIRVOTE_PRIVATE +#include "or.h" +#include "config.h" +#include "dircollate.h" +#include "directory.h" +#include "dirserv.h" +#include "microdesc.h" +#include "networkstatus.h" +#include "nodelist.h" +#include "parsecommon.h" +#include "policies.h" +#include "protover.h" +#include "rephist.h" +#include "router.h" +#include "routerkeys.h" +#include "routerlist.h" +#include "routerparse.h" +#include "entrynodes.h" /* needed for guardfraction methods */ +#include "torcert.h" +#include "voting_schedule.h" + +#include "dirauth/dirvote.h" +#include "dirauth/mode.h" +#include "dirauth/shared_random_state.h" + +/** + * \file dirvote.c + * \brief Functions to compute directory consensus, and schedule voting. + * + * This module is the center of the consensus-voting based directory + * authority system. With this system, a set of authorities first + * publish vote based on their opinions of the network, and then compute + * a consensus from those votes. Each authority signs the consensus, + * and clients trust the consensus if enough known authorities have + * signed it. + * + * The code in this module is only invoked on directory authorities. It's + * responsible for: + * + * <ul> + * <li>Generating this authority's vote networkstatus, based on the + * authority's view of the network as represented in dirserv.c + * <li>Formatting the vote networkstatus objects. + * <li>Generating the microdescriptors that correspond to our own + * vote. + * <li>Sending votes to all the other authorities. + * <li>Trying to fetch missing votes from other authorities. + * <li>Computing the consensus from a set of votes, as well as + * a "detached signature" object for other authorities to fetch. + * <li>Collecting other authorities' signatures on the same consensus, + * until there are enough. + * <li>Publishing the consensus to the reset of the directory system. + * <li>Scheduling all of the above operations. + * </ul> + * + * The main entry points are in dirvote_act(), which handles scheduled + * actions; and dirvote_add_vote() and dirvote_add_signatures(), which + * handle uploaded and downloaded votes and signatures. + * + * (See dir-spec.txt from torspec.git for a complete specification of + * the directory protocol and voting algorithms.) + **/ + +/** 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; + +/* DOCDOC dirvote_add_signatures_to_all_pending_consensuses */ +static int dirvote_add_signatures_to_all_pending_consensuses( + const char *detached_signatures_body, + const char *source, + const char **msg_out); +static int dirvote_add_signatures_to_pending_consensus( + pending_consensus_t *pc, + ns_detached_signatures_t *sigs, + const char *source, + int severity, + 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); + +/* ===== + * Certificate functions + * ===== */ + +/** Allocate and return a new authority_cert_t with the same contents as + * <b>cert</b>. */ +STATIC authority_cert_t * +authority_cert_dup(authority_cert_t *cert) +{ + authority_cert_t *out = tor_malloc(sizeof(authority_cert_t)); + tor_assert(cert); + + memcpy(out, cert, sizeof(authority_cert_t)); + /* Now copy pointed-to things. */ + out->cache_info.signed_descriptor_body = + tor_strndup(cert->cache_info.signed_descriptor_body, + cert->cache_info.signed_descriptor_len); + out->cache_info.saved_location = SAVED_NOWHERE; + out->identity_key = crypto_pk_dup_key(cert->identity_key); + out->signing_key = crypto_pk_dup_key(cert->signing_key); + + return out; +} + +/* ===== + * Voting + * =====*/ + +/* If <b>opt_value</b> is non-NULL, return "keyword opt_value\n" in a new + * string. Otherwise return a new empty string. */ +static char * +format_line_if_present(const char *keyword, const char *opt_value) +{ + if (opt_value) { + char *result = NULL; + tor_asprintf(&result, "%s %s\n", keyword, opt_value); + return result; + } else { + return tor_strdup(""); + } +} + +/** Format the recommended/required-relay-client protocols lines for a vote in + * a newly allocated string, and return that string. */ +static char * +format_protocols_lines_for_vote(const networkstatus_t *v3_ns) +{ + char *recommended_relay_protocols_line = NULL; + char *recommended_client_protocols_line = NULL; + char *required_relay_protocols_line = NULL; + char *required_client_protocols_line = NULL; + + recommended_relay_protocols_line = + format_line_if_present("recommended-relay-protocols", + v3_ns->recommended_relay_protocols); + recommended_client_protocols_line = + format_line_if_present("recommended-client-protocols", + v3_ns->recommended_client_protocols); + required_relay_protocols_line = + format_line_if_present("required-relay-protocols", + v3_ns->required_relay_protocols); + required_client_protocols_line = + format_line_if_present("required-client-protocols", + v3_ns->required_client_protocols); + + char *result = NULL; + tor_asprintf(&result, "%s%s%s%s", + recommended_relay_protocols_line, + recommended_client_protocols_line, + required_relay_protocols_line, + required_client_protocols_line); + + tor_free(recommended_relay_protocols_line); + tor_free(recommended_client_protocols_line); + tor_free(required_relay_protocols_line); + tor_free(required_client_protocols_line); + + return result; +} + +/** Return a new string containing the string representation of the vote in + * <b>v3_ns</b>, signed with our v3 signing key <b>private_signing_key</b>. + * For v3 authorities. */ +STATIC char * +format_networkstatus_vote(crypto_pk_t *private_signing_key, + networkstatus_t *v3_ns) +{ + smartlist_t *chunks = smartlist_new(); + char *packages = NULL; + char fingerprint[FINGERPRINT_LEN+1]; + char digest[DIGEST_LEN]; + uint32_t addr; + char *protocols_lines = NULL; + char *client_versions_line = NULL, *server_versions_line = NULL; + char *shared_random_vote_str = NULL; + networkstatus_voter_info_t *voter; + char *status = NULL; + + 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; + + base16_encode(fingerprint, sizeof(fingerprint), + v3_ns->cert->cache_info.identity_digest, DIGEST_LEN); + + client_versions_line = format_line_if_present("client-versions", + v3_ns->client_versions); + server_versions_line = format_line_if_present("server-versions", + v3_ns->server_versions); + protocols_lines = format_protocols_lines_for_vote(v3_ns); + + if (v3_ns->package_lines) { + smartlist_t *tmp = smartlist_new(); + SMARTLIST_FOREACH(v3_ns->package_lines, const char *, p, + if (validate_recommended_package_line(p)) + smartlist_add_asprintf(tmp, "package %s\n", p)); + smartlist_sort_strings(tmp); + packages = smartlist_join_strings(tmp, "", 0, NULL); + SMARTLIST_FOREACH(tmp, char *, cp, tor_free(cp)); + smartlist_free(tmp); + } else { + packages = tor_strdup(""); + } + + /* Get shared random commitments/reveals line(s). */ + shared_random_vote_str = sr_get_string_for_vote(); + + { + 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); + /* XXXX Abstraction violation: should be pulling a field out of v3_ns.*/ + char *flag_thresholds = dirserv_get_flag_thresholds_line(); + char *params; + authority_cert_t *cert = v3_ns->cert; + char *methods = + make_consensus_method_list(MIN_SUPPORTED_CONSENSUS_METHOD, + 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); + smartlist_add_asprintf(chunks, + "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%s" /* versions */ + "%s" /* protocols */ + "%s" /* packages */ + "known-flags %s\n" + "flag-thresholds %s\n" + "params %s\n" + "dir-source %s %s %s %s %d %d\n" + "contact %s\n" + "%s", /* shared randomness information */ + v3_ns->type == NS_TYPE_VOTE ? "vote" : "opinion", + methods, + published, va, fu, vu, + v3_ns->vote_seconds, v3_ns->dist_seconds, + client_versions_line, + server_versions_line, + protocols_lines, + packages, + flags, + flag_thresholds, + params, + voter->nickname, fingerprint, voter->address, + fmt_addr32(addr), voter->dir_port, voter->or_port, + voter->contact, + shared_random_vote_str ? + shared_random_vote_str : ""); + + tor_free(params); + tor_free(flags); + tor_free(flag_thresholds); + tor_free(methods); + tor_free(shared_random_vote_str); + + 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); + smartlist_add_asprintf(chunks, "legacy-dir-key %s\n", fpbuf); + } + + smartlist_add(chunks, tor_strndup(cert->cache_info.signed_descriptor_body, + cert->cache_info.signed_descriptor_len)); + } + + SMARTLIST_FOREACH_BEGIN(v3_ns->routerstatus_list, vote_routerstatus_t *, + vrs) { + char *rsf; + vote_microdesc_hash_t *h; + rsf = routerstatus_format_entry(&vrs->status, + vrs->version, vrs->protocols, + NS_V3_VOTE, + ROUTERSTATUS_FORMAT_NO_CONSENSUS_METHOD, + vrs); + if (rsf) + smartlist_add(chunks, rsf); + + for (h = vrs->microdesc; h; h = h->next) { + smartlist_add_strdup(chunks, h->microdesc_hash_line); + } + } SMARTLIST_FOREACH_END(vrs); + + smartlist_add_strdup(chunks, "directory-footer\n"); + + /* The digest includes everything up through the space after + * directory-signature. (Yuck.) */ + crypto_digest_smartlist(digest, DIGEST_LEN, chunks, + "directory-signature ", DIGEST_SHA1); + + { + char signing_key_fingerprint[FINGERPRINT_LEN+1]; + 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; + } + + smartlist_add_asprintf(chunks, "directory-signature %s %s\n", fingerprint, + signing_key_fingerprint); + } + + { + char *sig = router_get_dirobj_signature(digest, DIGEST_LEN, + private_signing_key); + if (!sig) { + log_warn(LD_BUG, "Unable to sign networkstatus vote."); + goto err; + } + smartlist_add(chunks, sig); + } + + status = smartlist_join_strings(chunks, "", 0, NULL); + + { + 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(client_versions_line); + tor_free(server_versions_line); + tor_free(protocols_lines); + tor_free(packages); + + SMARTLIST_FOREACH(chunks, char *, cp, tor_free(cp)); + smartlist_free(chunks); + return status; +} + +/** Set *<b>timing_out</b> to the intervals at which we would like to vote. + * Note that these aren't the intervals we'll use to vote; they're the ones + * that we'll vote to use. */ +static void +dirvote_get_preferred_voting_intervals(vote_timing_t *timing_out) +{ + const or_options_t *options = get_options(); + + tor_assert(timing_out); + + timing_out->vote_interval = options->V3AuthVotingInterval; + timing_out->n_intervals_valid = options->V3AuthNIntervalsValid; + timing_out->vote_delay = options->V3AuthVoteDelay; + timing_out->dist_delay = options->V3AuthDistDelay; +} + +/* ===== + * Consensus generation + * ===== */ + +/** If <b>vrs</b> has a hash made for the consensus method <b>method</b> with + * the digest algorithm <b>alg</b>, decode it and copy it into + * <b>digest256_out</b> and return 0. Otherwise return -1. */ +static int +vote_routerstatus_find_microdesc_hash(char *digest256_out, + const vote_routerstatus_t *vrs, + int method, + digest_algorithm_t alg) +{ + /* XXXX only returns the sha256 method. */ + const vote_microdesc_hash_t *h; + char mstr[64]; + size_t mlen; + char dstr[64]; + + tor_snprintf(mstr, sizeof(mstr), "%d", method); + mlen = strlen(mstr); + tor_snprintf(dstr, sizeof(dstr), " %s=", + crypto_digest_algorithm_get_name(alg)); + + for (h = vrs->microdesc; h; h = h->next) { + const char *cp = h->microdesc_hash_line; + size_t num_len; + /* cp looks like \d+(,\d+)* (digesttype=val )+ . Let's hunt for mstr in + * the first part. */ + while (1) { + num_len = strspn(cp, "1234567890"); + if (num_len == mlen && fast_memeq(mstr, cp, mlen)) { + /* This is the line. */ + char buf[BASE64_DIGEST256_LEN+1]; + /* XXXX ignores extraneous stuff if the digest is too long. This + * seems harmless enough, right? */ + cp = strstr(cp, dstr); + if (!cp) + return -1; + cp += strlen(dstr); + strlcpy(buf, cp, sizeof(buf)); + return digest256_from_base64(digest256_out, buf); + } + if (num_len == 0 || cp[num_len] != ',') + break; + cp += num_len + 1; + } + } + return -1; +} + +/** 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); +} + +/** 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 fast_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 fast_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_BEGIN(in, char *, cp) { + if (cur && !strcmp(cp, cur)) { + ++count; + } else { + if (count > min) + smartlist_add(out, cur); + cur = cp; + count = 1; + } + } SMARTLIST_FOREACH_END(cp); + 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; + tor_assert(a); + tor_assert(b); + + if ((r = fast_memcmp(a->status.identity_digest, b->status.identity_digest, + DIGEST_LEN))) + return r; + if ((r = fast_memcmp(a->status.descriptor_digest, + b->status.descriptor_digest, + DIGEST_LEN))) + return r; + /* If we actually reached this point, then the identities and + * the descriptor digests matched, so somebody is making SHA1 collisions. + */ +#define CMP_FIELD(utype, itype, field) do { \ + utype aval = (utype) (itype) a->status.field; \ + utype bval = (utype) (itype) b->status.field; \ + utype u = bval - aval; \ + itype r2 = (itype) u; \ + if (r2 < 0) { \ + return -1; \ + } else if (r2 > 0) { \ + return 1; \ + } \ + } while (0) + + CMP_FIELD(uint64_t, int64_t, published_on); + + if ((r = strcmp(b->status.nickname, a->status.nickname))) + return r; + + CMP_FIELD(unsigned, int, addr); + CMP_FIELD(unsigned, int, or_port); + CMP_FIELD(unsigned, int, dir_port); + + 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); +} + +/** Helper for sorting OR ports. */ +static int +compare_orports_(const void **_a, const void **_b) +{ + const tor_addr_port_t *a = *_a, *b = *_b; + int r; + + if ((r = tor_addr_compare(&a->addr, &b->addr, CMP_EXACT))) + return r; + if ((r = (((int) b->port) - ((int) a->port)))) + return r; + + return 0; +} + +/** 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, + tor_addr_port_t *best_alt_orport_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 break, we use the descriptor with the smaller digest. + */ + smartlist_sort(votes, compare_vote_rs_); + SMARTLIST_FOREACH_BEGIN(votes, vote_routerstatus_t *, rs) { + if (cur && !compare_vote_rs(cur, rs)) { + ++cur_n; + } else { + if (cur && (cur_n > most_n || + (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; + } + } SMARTLIST_FOREACH_END(rs); + + if (cur_n > most_n || + (cur && cur_n == most_n && cur->status.published_on > most_published)) { + most = cur; + // most_n = cur_n; // unused after this point. + // most_published = cur->status.published_on; // unused after this point. + } + + tor_assert(most); + + /* Vote on potential alternative (sets of) OR port(s) in the winning + * routerstatuses. + * + * XXX prop186 There's at most one alternative OR port (_the_ IPv6 + * port) for now. */ + if (best_alt_orport_out) { + smartlist_t *alt_orports = smartlist_new(); + const tor_addr_port_t *most_alt_orport = NULL; + + SMARTLIST_FOREACH_BEGIN(votes, vote_routerstatus_t *, rs) { + tor_assert(rs); + if (compare_vote_rs(most, rs) == 0 && + !tor_addr_is_null(&rs->status.ipv6_addr) + && rs->status.ipv6_orport) { + smartlist_add(alt_orports, tor_addr_port_new(&rs->status.ipv6_addr, + rs->status.ipv6_orport)); + } + } SMARTLIST_FOREACH_END(rs); + + smartlist_sort(alt_orports, compare_orports_); + most_alt_orport = smartlist_get_most_frequent(alt_orports, + compare_orports_); + if (most_alt_orport) { + memcpy(best_alt_orport_out, most_alt_orport, sizeof(tor_addr_port_t)); + log_debug(LD_DIR, "\"a\" line winner for %s is %s", + most->status.nickname, + fmt_addrport(&most_alt_orport->addr, most_alt_orport->port)); + } + + SMARTLIST_FOREACH(alt_orports, tor_addr_port_t *, ap, tor_free(ap)); + smartlist_free(alt_orports); + } + + if (microdesc_digest256_out) { + smartlist_t *digests = smartlist_new(); + const uint8_t *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; +} + +/** 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_new(); + smartlist_t *acceptable_methods = smartlist_new(); + smartlist_t *tmp = smartlist_new(); + 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 >= MIN_SUPPORTED_CONSENSUS_METHOD) && + (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; + + int i; + smartlist_t *lst; + lst = smartlist_new(); + for (i = low; i <= high; ++i) { + if (!consensus_method_is_supported(i)) + continue; + smartlist_add_asprintf(lst, "%d", i); + } + 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_new(); + 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; +} + +/** Given a list of K=V values, return the int32_t value corresponding to + * KEYWORD=, or default_val if no such value exists, or if the value is + * corrupt. + */ +STATIC int32_t +dirvote_get_intermediate_param_value(const smartlist_t *param_list, + const char *keyword, + int32_t default_val) +{ + unsigned int n_found = 0; + int32_t value = default_val; + + SMARTLIST_FOREACH_BEGIN(param_list, const char *, k_v_pair) { + if (!strcmpstart(k_v_pair, keyword) && k_v_pair[strlen(keyword)] == '=') { + const char *integer_str = &k_v_pair[strlen(keyword)+1]; + int ok; + value = (int32_t) + tor_parse_long(integer_str, 10, INT32_MIN, INT32_MAX, &ok, NULL); + if (BUG(! ok)) + return default_val; + ++n_found; + } + } SMARTLIST_FOREACH_END(k_v_pair); + + if (n_found == 1) { + return value; + } else { + tor_assert_nonfatal(n_found == 0); + return default_val; + } +} + +/** Minimum number of directory authorities voting for a parameter to + * include it in the consensus, if consensus method 12 or later is to be + * used. See proposal 178 for details. */ +#define MIN_VOTES_FOR_PARAM 3 + +/** Helper: given a list of valid networkstatus_t, return a new smartlist + * containing the contents of the consensus network parameter set. + */ +STATIC smartlist_t * +dirvote_compute_params(smartlist_t *votes, int method, int total_authorities) +{ + int i; + int32_t *vals; + + int cur_param_len; + const char *cur_param; + const char *eq; + + const int n_votes = smartlist_len(votes); + smartlist_t *output; + smartlist_t *param_list = smartlist_new(); + (void) method; + + /* 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_calloc(n_votes, sizeof(int)); + + 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); + return param_list; + } + + 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_new(); + + SMARTLIST_FOREACH_BEGIN(param_list, const char *, param) { + /* resolve spurious clang shallow analysis null pointer errors */ + tor_assert(param); + + const char *next_param; + int ok=0; + eq = strchr(param, '='); + tor_assert(i<n_votes); /* Make sure we prevented vote-stuffing. */ + vals[i++] = (int32_t) + tor_parse_long(eq+1, 10, INT32_MIN, INT32_MAX, &ok, NULL); + tor_assert(ok); /* Already checked these when parsing. */ + + 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. */ + /* Make sure enough authorities voted on this param, unless the + * the consensus method we use is too old for that. */ + if (i > total_authorities/2 || + i >= MIN_VOTES_FOR_PARAM) { + 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); + + smartlist_free(param_list); + tor_free(vals); + return output; +} + +#define RANGE_CHECK(a,b,c,d,e,f,g,mx) \ + ((a) >= 0 && (a) <= (mx) && (b) >= 0 && (b) <= (mx) && \ + (c) >= 0 && (c) <= (mx) && (d) >= 0 && (d) <= (mx) && \ + (e) >= 0 && (e) <= (mx) && (f) >= 0 && (f) <= (mx) && \ + (g) >= 0 && (g) <= (mx)) + +#define CHECK_EQ(a, b, margin) \ + ((a)-(b) >= 0 ? (a)-(b) <= (margin) : (b)-(a) <= (margin)) + +typedef enum { + BW_WEIGHTS_NO_ERROR = 0, + BW_WEIGHTS_RANGE_ERROR = 1, + BW_WEIGHTS_SUMG_ERROR = 2, + BW_WEIGHTS_SUME_ERROR = 3, + BW_WEIGHTS_SUMD_ERROR = 4, + BW_WEIGHTS_BALANCE_MID_ERROR = 5, + BW_WEIGHTS_BALANCE_EG_ERROR = 6 +} bw_weights_error_t; + +/** + * Verify that any weightings satisfy the balanced formulas. + */ +static bw_weights_error_t +networkstatus_check_weights(int64_t Wgg, int64_t Wgd, int64_t Wmg, + int64_t Wme, int64_t Wmd, int64_t Wee, + int64_t Wed, int64_t scale, int64_t G, + int64_t M, int64_t E, int64_t D, int64_t T, + int64_t margin, int do_balance) { + bw_weights_error_t berr = BW_WEIGHTS_NO_ERROR; + + // Wed + Wmd + Wgd == 1 + if (!CHECK_EQ(Wed + Wmd + Wgd, scale, margin)) { + berr = BW_WEIGHTS_SUMD_ERROR; + goto out; + } + + // Wmg + Wgg == 1 + if (!CHECK_EQ(Wmg + Wgg, scale, margin)) { + berr = BW_WEIGHTS_SUMG_ERROR; + goto out; + } + + // Wme + Wee == 1 + if (!CHECK_EQ(Wme + Wee, scale, margin)) { + berr = BW_WEIGHTS_SUME_ERROR; + goto out; + } + + // Verify weights within range 0->1 + if (!RANGE_CHECK(Wgg, Wgd, Wmg, Wme, Wmd, Wed, Wee, scale)) { + berr = BW_WEIGHTS_RANGE_ERROR; + goto out; + } + + if (do_balance) { + // Wgg*G + Wgd*D == Wee*E + Wed*D, already scaled + if (!CHECK_EQ(Wgg*G + Wgd*D, Wee*E + Wed*D, (margin*T)/3)) { + berr = BW_WEIGHTS_BALANCE_EG_ERROR; + goto out; + } + + // Wgg*G + Wgd*D == M*scale + Wmd*D + Wme*E + Wmg*G, already scaled + if (!CHECK_EQ(Wgg*G + Wgd*D, M*scale + Wmd*D + Wme*E + Wmg*G, + (margin*T)/3)) { + berr = BW_WEIGHTS_BALANCE_MID_ERROR; + goto out; + } + } + + out: + if (berr) { + log_info(LD_DIR, + "Bw weight mismatch %d. G="I64_FORMAT" M="I64_FORMAT + " E="I64_FORMAT" D="I64_FORMAT" T="I64_FORMAT + " Wmd=%d Wme=%d Wmg=%d Wed=%d Wee=%d" + " Wgd=%d Wgg=%d Wme=%d Wmg=%d", + berr, + I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E), + I64_PRINTF_ARG(D), I64_PRINTF_ARG(T), + (int)Wmd, (int)Wme, (int)Wmg, (int)Wed, (int)Wee, + (int)Wgd, (int)Wgg, (int)Wme, (int)Wmg); + } + + return berr; +} + +/** + * This function computes the bandwidth weights for consensus method 10. + * + * It returns true if weights could be computed, false otherwise. + */ +int +networkstatus_compute_bw_weights_v10(smartlist_t *chunks, int64_t G, + int64_t M, int64_t E, int64_t D, + int64_t T, int64_t weight_scale) +{ + bw_weights_error_t berr = 0; + int64_t Wgg = -1, Wgd = -1; + int64_t Wmg = -1, Wme = -1, Wmd = -1; + int64_t Wed = -1, Wee = -1; + const char *casename; + + if (G <= 0 || M <= 0 || E <= 0 || D <= 0) { + log_warn(LD_DIR, "Consensus with empty bandwidth: " + "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT + " D="I64_FORMAT" T="I64_FORMAT, + I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E), + I64_PRINTF_ARG(D), I64_PRINTF_ARG(T)); + return 0; + } + + /* + * Computed from cases in 3.8.3 of dir-spec.txt + * + * 1. Neither are scarce + * 2. Both Guard and Exit are scarce + * a. R+D <= S + * b. R+D > S + * 3. One of Guard or Exit is scarce + * a. S+D < T/3 + * b. S+D >= T/3 + */ + if (3*E >= T && 3*G >= T) { // E >= T/3 && G >= T/3 + /* Case 1: Neither are scarce. */ + casename = "Case 1 (Wgd=Wmd=Wed)"; + Wgd = weight_scale/3; + Wed = weight_scale/3; + Wmd = weight_scale/3; + Wee = (weight_scale*(E+G+M))/(3*E); + Wme = weight_scale - Wee; + Wmg = (weight_scale*(2*G-E-M))/(3*G); + Wgg = weight_scale - Wmg; + + berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed, + weight_scale, G, M, E, D, T, 10, 1); + + if (berr) { + log_warn(LD_DIR, + "Bw Weights error %d for %s v10. G="I64_FORMAT" M="I64_FORMAT + " E="I64_FORMAT" D="I64_FORMAT" T="I64_FORMAT + " Wmd=%d Wme=%d Wmg=%d Wed=%d Wee=%d" + " Wgd=%d Wgg=%d Wme=%d Wmg=%d weight_scale=%d", + berr, casename, + I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E), + I64_PRINTF_ARG(D), I64_PRINTF_ARG(T), + (int)Wmd, (int)Wme, (int)Wmg, (int)Wed, (int)Wee, + (int)Wgd, (int)Wgg, (int)Wme, (int)Wmg, (int)weight_scale); + return 0; + } + } else if (3*E < T && 3*G < T) { // E < T/3 && G < T/3 + int64_t R = MIN(E, G); + int64_t S = MAX(E, G); + /* + * Case 2: Both Guards and Exits are scarce + * Balance D between E and G, depending upon + * D capacity and scarcity. + */ + if (R+D < S) { // Subcase a + Wgg = weight_scale; + Wee = weight_scale; + Wmg = 0; + Wme = 0; + Wmd = 0; + if (E < G) { + casename = "Case 2a (E scarce)"; + Wed = weight_scale; + Wgd = 0; + } else { /* E >= G */ + casename = "Case 2a (G scarce)"; + Wed = 0; + Wgd = weight_scale; + } + } else { // Subcase b: R+D >= S + casename = "Case 2b1 (Wgg=weight_scale, Wmd=Wgd)"; + Wee = (weight_scale*(E - G + M))/E; + Wed = (weight_scale*(D - 2*E + 4*G - 2*M))/(3*D); + Wme = (weight_scale*(G-M))/E; + Wmg = 0; + Wgg = weight_scale; + Wmd = (weight_scale - Wed)/2; + Wgd = (weight_scale - Wed)/2; + + berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed, + weight_scale, G, M, E, D, T, 10, 1); + + if (berr) { + casename = "Case 2b2 (Wgg=weight_scale, Wee=weight_scale)"; + Wgg = weight_scale; + Wee = weight_scale; + Wed = (weight_scale*(D - 2*E + G + M))/(3*D); + Wmd = (weight_scale*(D - 2*M + G + E))/(3*D); + Wme = 0; + Wmg = 0; + + if (Wmd < 0) { // Can happen if M > T/3 + casename = "Case 2b3 (Wmd=0)"; + Wmd = 0; + log_warn(LD_DIR, + "Too much Middle bandwidth on the network to calculate " + "balanced bandwidth-weights. Consider increasing the " + "number of Guard nodes by lowering the requirements."); + } + Wgd = weight_scale - Wed - Wmd; + berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee, + Wed, weight_scale, G, M, E, D, T, 10, 1); + } + if (berr != BW_WEIGHTS_NO_ERROR && + berr != BW_WEIGHTS_BALANCE_MID_ERROR) { + log_warn(LD_DIR, + "Bw Weights error %d for %s v10. G="I64_FORMAT" M="I64_FORMAT + " E="I64_FORMAT" D="I64_FORMAT" T="I64_FORMAT + " Wmd=%d Wme=%d Wmg=%d Wed=%d Wee=%d" + " Wgd=%d Wgg=%d Wme=%d Wmg=%d weight_scale=%d", + berr, casename, + I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E), + I64_PRINTF_ARG(D), I64_PRINTF_ARG(T), + (int)Wmd, (int)Wme, (int)Wmg, (int)Wed, (int)Wee, + (int)Wgd, (int)Wgg, (int)Wme, (int)Wmg, (int)weight_scale); + return 0; + } + } + } else { // if (E < T/3 || G < T/3) { + int64_t S = MIN(E, G); + // Case 3: Exactly one of Guard or Exit is scarce + if (!(3*E < T || 3*G < T) || !(3*G >= T || 3*E >= T)) { + log_warn(LD_BUG, + "Bw-Weights Case 3 v10 but with G="I64_FORMAT" M=" + I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT" T="I64_FORMAT, + I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E), + I64_PRINTF_ARG(D), I64_PRINTF_ARG(T)); + } + + if (3*(S+D) < T) { // Subcase a: S+D < T/3 + if (G < E) { + casename = "Case 3a (G scarce)"; + Wgg = Wgd = weight_scale; + Wmd = Wed = Wmg = 0; + // Minor subcase, if E is more scarce than M, + // keep its bandwidth in place. + if (E < M) Wme = 0; + else Wme = (weight_scale*(E-M))/(2*E); + Wee = weight_scale-Wme; + } else { // G >= E + casename = "Case 3a (E scarce)"; + Wee = Wed = weight_scale; + Wmd = Wgd = Wme = 0; + // Minor subcase, if G is more scarce than M, + // keep its bandwidth in place. + if (G < M) Wmg = 0; + else Wmg = (weight_scale*(G-M))/(2*G); + Wgg = weight_scale-Wmg; + } + } else { // Subcase b: S+D >= T/3 + // D != 0 because S+D >= T/3 + if (G < E) { + casename = "Case 3bg (G scarce, Wgg=weight_scale, Wmd == Wed)"; + Wgg = weight_scale; + Wgd = (weight_scale*(D - 2*G + E + M))/(3*D); + Wmg = 0; + Wee = (weight_scale*(E+M))/(2*E); + Wme = weight_scale - Wee; + Wmd = (weight_scale - Wgd)/2; + Wed = (weight_scale - Wgd)/2; + + berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee, + Wed, weight_scale, G, M, E, D, T, 10, 1); + } else { // G >= E + casename = "Case 3be (E scarce, Wee=weight_scale, Wmd == Wgd)"; + Wee = weight_scale; + Wed = (weight_scale*(D - 2*E + G + M))/(3*D); + Wme = 0; + Wgg = (weight_scale*(G+M))/(2*G); + Wmg = weight_scale - Wgg; + Wmd = (weight_scale - Wed)/2; + Wgd = (weight_scale - Wed)/2; + + berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee, + Wed, weight_scale, G, M, E, D, T, 10, 1); + } + if (berr) { + log_warn(LD_DIR, + "Bw Weights error %d for %s v10. G="I64_FORMAT" M="I64_FORMAT + " E="I64_FORMAT" D="I64_FORMAT" T="I64_FORMAT + " Wmd=%d Wme=%d Wmg=%d Wed=%d Wee=%d" + " Wgd=%d Wgg=%d Wme=%d Wmg=%d weight_scale=%d", + berr, casename, + I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E), + I64_PRINTF_ARG(D), I64_PRINTF_ARG(T), + (int)Wmd, (int)Wme, (int)Wmg, (int)Wed, (int)Wee, + (int)Wgd, (int)Wgg, (int)Wme, (int)Wmg, (int)weight_scale); + return 0; + } + } + } + + /* We cast down the weights to 32 bit ints on the assumption that + * weight_scale is ~= 10000. We need to ensure a rogue authority + * doesn't break this assumption to rig our weights */ + tor_assert(0 < weight_scale && weight_scale <= INT32_MAX); + + /* + * Provide Wgm=Wgg, Wmm=weight_scale, Wem=Wee, Weg=Wed. May later determine + * that middle nodes need different bandwidth weights for dirport traffic, + * or that weird exit policies need special weight, or that bridges + * need special weight. + * + * NOTE: This list is sorted. + */ + smartlist_add_asprintf(chunks, + "bandwidth-weights Wbd=%d Wbe=%d Wbg=%d Wbm=%d " + "Wdb=%d " + "Web=%d Wed=%d Wee=%d Weg=%d Wem=%d " + "Wgb=%d Wgd=%d Wgg=%d Wgm=%d " + "Wmb=%d Wmd=%d Wme=%d Wmg=%d Wmm=%d\n", + (int)Wmd, (int)Wme, (int)Wmg, (int)weight_scale, + (int)weight_scale, + (int)weight_scale, (int)Wed, (int)Wee, (int)Wed, (int)Wee, + (int)weight_scale, (int)Wgd, (int)Wgg, (int)Wgg, + (int)weight_scale, (int)Wmd, (int)Wme, (int)Wmg, (int)weight_scale); + + log_notice(LD_CIRC, "Computed bandwidth weights for %s with v10: " + "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT + " T="I64_FORMAT, + casename, + I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E), + I64_PRINTF_ARG(D), I64_PRINTF_ARG(T)); + return 1; +} + +/** Update total bandwidth weights (G/M/E/D/T) with the bandwidth of + * the router in <b>rs</b>. */ +static void +update_total_bandwidth_weights(const routerstatus_t *rs, + int is_exit, int is_guard, + int64_t *G, int64_t *M, int64_t *E, int64_t *D, + int64_t *T) +{ + int default_bandwidth = rs->bandwidth_kb; + int guardfraction_bandwidth = 0; + + if (!rs->has_bandwidth) { + log_info(LD_BUG, "Missing consensus bandwidth for router %s", + rs->nickname); + return; + } + + /* If this routerstatus represents a guard that we have + * guardfraction information on, use it to calculate its actual + * bandwidth. From proposal236: + * + * Similarly, when calculating the bandwidth-weights line as in + * section 3.8.3 of dir-spec.txt, directory authorities should treat N + * as if fraction F of its bandwidth has the guard flag and (1-F) does + * not. So when computing the totals G,M,E,D, each relay N with guard + * visibility fraction F and bandwidth B should be added as follows: + * + * G' = G + F*B, if N does not have the exit flag + * M' = M + (1-F)*B, if N does not have the exit flag + * + * or + * + * D' = D + F*B, if N has the exit flag + * E' = E + (1-F)*B, if N has the exit flag + * + * In this block of code, we prepare the bandwidth values by setting + * the default_bandwidth to F*B and guardfraction_bandwidth to (1-F)*B. + */ + if (rs->has_guardfraction) { + guardfraction_bandwidth_t guardfraction_bw; + + tor_assert(is_guard); + + guard_get_guardfraction_bandwidth(&guardfraction_bw, + rs->bandwidth_kb, + rs->guardfraction_percentage); + + default_bandwidth = guardfraction_bw.guard_bw; + guardfraction_bandwidth = guardfraction_bw.non_guard_bw; + } + + /* Now calculate the total bandwidth weights with or without + * guardfraction. Depending on the flags of the relay, add its + * bandwidth to the appropriate weight pool. If it's a guard and + * guardfraction is enabled, add its bandwidth to both pools as + * indicated by the previous comment. + */ + *T += default_bandwidth; + if (is_exit && is_guard) { + + *D += default_bandwidth; + if (rs->has_guardfraction) { + *E += guardfraction_bandwidth; + } + + } else if (is_exit) { + + *E += default_bandwidth; + + } else if (is_guard) { + + *G += default_bandwidth; + if (rs->has_guardfraction) { + *M += guardfraction_bandwidth; + } + + } else { + + *M += default_bandwidth; + } +} + +/** Considering the different recommended/required protocols sets as a + * 4-element array, return the element from <b>vote</b> for that protocol + * set. + */ +static const char * +get_nth_protocol_set_vote(int n, const networkstatus_t *vote) +{ + switch (n) { + case 0: return vote->recommended_client_protocols; + case 1: return vote->recommended_relay_protocols; + case 2: return vote->required_client_protocols; + case 3: return vote->required_relay_protocols; + default: + tor_assert_unreached(); + return NULL; + } +} + +/** Considering the different recommended/required protocols sets as a + * 4-element array, return a newly allocated string for the consensus value + * for the n'th set. + */ +static char * +compute_nth_protocol_set(int n, int n_voters, const smartlist_t *votes) +{ + const char *keyword; + smartlist_t *proto_votes = smartlist_new(); + int threshold; + switch (n) { + case 0: + keyword = "recommended-client-protocols"; + threshold = CEIL_DIV(n_voters, 2); + break; + case 1: + keyword = "recommended-relay-protocols"; + threshold = CEIL_DIV(n_voters, 2); + break; + case 2: + keyword = "required-client-protocols"; + threshold = CEIL_DIV(n_voters * 2, 3); + break; + case 3: + keyword = "required-relay-protocols"; + threshold = CEIL_DIV(n_voters * 2, 3); + break; + default: + tor_assert_unreached(); + return NULL; + } + + SMARTLIST_FOREACH_BEGIN(votes, const networkstatus_t *, ns) { + const char *v = get_nth_protocol_set_vote(n, ns); + if (v) + smartlist_add(proto_votes, (void*)v); + } SMARTLIST_FOREACH_END(ns); + + char *protocols = protover_compute_vote(proto_votes, threshold); + smartlist_free(proto_votes); + + char *result = NULL; + tor_asprintf(&result, "%s %s\n", keyword, protocols); + tor_free(protocols); + + return result; +} + +/** Given a list of vote networkstatus_t in <b>votes</b>, our public + * authority <b>identity_key</b>, our private authority <b>signing_key</b>, + * and the number of <b>total_authorities</b> that we believe exist in our + * voting quorum, generate the text of a new v3 consensus or microdescriptor + * consensus (depending on <b>flavor</b>), 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.) + * + * <strong>WATCH OUT</strong>: You need to think before you change the + * behavior of this function, or of the functions it calls! If some + * authorities compute the consensus with a different algorithm than + * others, they will not reach the same result, and they will not all + * sign the same thing! If you really need to change the algorithm + * here, you should allocate a new "consensus_method" for the new + * behavior, and make the new behavior conditional on a new-enough + * consensus_method. + **/ +STATIC char * +networkstatus_compute_consensus(smartlist_t *votes, + int total_authorities, + crypto_pk_t *identity_key, + crypto_pk_t *signing_key, + const char *legacy_id_key_digest, + crypto_pk_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; + uint32_t max_unmeasured_bw_kb = DEFAULT_MAX_UNMEASURED_BW_KB; + int64_t G, M, E, D, T; /* For bandwidth weights */ + const routerstatus_format_type_t rs_format = + flavor == FLAV_NS ? NS_V3_CONSENSUS : NS_V3_CONSENSUS_MICRODESC; + char *params = NULL; + char *packages = NULL; + int added_weights = 0; + dircollator_t *collator = NULL; + smartlist_t *param_list = NULL; + + tor_assert(flavor == FLAV_NS || flavor == FLAV_MICRODESC); + tor_assert(total_authorities >= smartlist_len(votes)); + tor_assert(total_authorities > 0); + + 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_new(); + + 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 = MAX_SUPPORTED_CONSENSUS_METHOD; + } + + if (consensus_method >= MIN_METHOD_FOR_INIT_BW_WEIGHTS_ONE) { + /* It's smarter to initialize these weights to 1, so that later on, + * we can't accidentally divide by zero. */ + G = M = E = D = 1; + T = 4; + } else { + /* ...but originally, they were set to zero. */ + G = M = E = D = T = 0; + } + + /* 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_calloc(n_votes, sizeof(time_t)); + time_t *fu_times = tor_calloc(n_votes, sizeof(time_t)); + time_t *vu_times = tor_calloc(n_votes, sizeof(time_t)); + int *votesec_list = tor_calloc(n_votes, sizeof(int)); + int *distsec_list = tor_calloc(n_votes, sizeof(int)); + int n_versioning_clients = 0, n_versioning_servers = 0; + smartlist_t *combined_client_versions = smartlist_new(); + smartlist_t *combined_server_versions = smartlist_new(); + + 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_new(); + ++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_new(); + ++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_strdup(flags, 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 + + (get_options()->TestingTorNetwork ? + MIN_VOTE_INTERVAL_TESTING : MIN_VOTE_INTERVAL) <= fresh_until); + tor_assert(fresh_until + + (get_options()->TestingTorNetwork ? + MIN_VOTE_INTERVAL_TESTING : 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); + packages = compute_consensus_package_lines(votes); + + 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_add_strdup(flags, "NoEdConsensus"); + + 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_new(); + + { + 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); + + smartlist_add_asprintf(chunks, "network-status-version 3%s%s\n" + "vote-status consensus\n", + flavor == FLAV_NS ? "" : " ", + flavor == FLAV_NS ? "" : flavor_name); + + smartlist_add_asprintf(chunks, "consensus-method %d\n", + consensus_method); + + smartlist_add_asprintf(chunks, + "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" + "%s" /* packages */ + "known-flags %s\n", + va_buf, fu_buf, vu_buf, + vote_seconds, dist_seconds, + client_versions, server_versions, + packages, + flaglist); + + tor_free(flaglist); + } + + { + int num_dirauth = get_n_authorities(V3_DIRINFO); + int idx; + for (idx = 0; idx < 4; ++idx) { + char *proto_line = compute_nth_protocol_set(idx, num_dirauth, votes); + if (BUG(!proto_line)) + continue; + smartlist_add(chunks, proto_line); + } + } + + param_list = dirvote_compute_params(votes, consensus_method, + total_authorities); + if (smartlist_len(param_list)) { + params = smartlist_join_strings(param_list, " ", 0, NULL); + smartlist_add_strdup(chunks, "params "); + smartlist_add(chunks, params); + smartlist_add_strdup(chunks, "\n"); + } + + { + int num_dirauth = get_n_authorities(V3_DIRINFO); + /* Default value of this is 2/3 of the total number of authorities. For + * instance, if we have 9 dirauth, the default value is 6. The following + * calculation will round it down. */ + int32_t num_srv_agreements = + dirvote_get_intermediate_param_value(param_list, + "AuthDirNumSRVAgreements", + (num_dirauth * 2) / 3); + /* Add the shared random value. */ + char *srv_lines = sr_get_string_for_consensus(votes, num_srv_agreements); + if (srv_lines != NULL) { + smartlist_add(chunks, srv_lines); + } + } + + /* Sort the votes. */ + smartlist_sort(votes, compare_votes_by_authority_id_); + /* Add the authority sections. */ + { + smartlist_t *dir_sources = smartlist_new(); + 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 (!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_BEGIN(dir_sources, const dir_src_ent_t *, e) { + 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); + + base16_encode(fingerprint, sizeof(fingerprint), e->digest, DIGEST_LEN); + base16_encode(votedigest, sizeof(votedigest), voter->vote_digest, + DIGEST_LEN); + + smartlist_add_asprintf(chunks, + "dir-source %s%s %s %s %s %d %d\n", + voter->nickname, e->is_legacy ? "-legacy" : "", + fingerprint, voter->address, fmt_addr32(voter->addr), + voter->dir_port, + voter->or_port); + if (! e->is_legacy) { + smartlist_add_asprintf(chunks, + "contact %s\n" + "vote-digest %s\n", + voter->contact, + votedigest); + } + } SMARTLIST_FOREACH_END(e); + SMARTLIST_FOREACH(dir_sources, dir_src_ent_t *, e, tor_free(e)); + smartlist_free(dir_sources); + } + + { + char *max_unmeasured_param = NULL; + /* XXXX Extract this code into a common function. Or don't! see #19011 */ + if (params) { + if (strcmpstart(params, "maxunmeasuredbw=") == 0) + max_unmeasured_param = params; + else + max_unmeasured_param = strstr(params, " maxunmeasuredbw="); + } + if (max_unmeasured_param) { + int ok = 0; + char *eq = strchr(max_unmeasured_param, '='); + if (eq) { + max_unmeasured_bw_kb = (uint32_t) + tor_parse_ulong(eq+1, 10, 1, UINT32_MAX, &ok, NULL); + if (!ok) { + log_warn(LD_DIR, "Bad element '%s' in max unmeasured bw param", + escaped(max_unmeasured_param)); + max_unmeasured_bw_kb = DEFAULT_MAX_UNMEASURED_BW_KB; + } + } + } + } + + /* Add the actual router entries. */ + { + 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_new(); + smartlist_t *chosen_flags = smartlist_new(); + smartlist_t *versions = smartlist_new(); + smartlist_t *protocols = smartlist_new(); + smartlist_t *exitsummaries = smartlist_new(); + uint32_t *bandwidths_kb = tor_calloc(smartlist_len(votes), + sizeof(uint32_t)); + uint32_t *measured_bws_kb = tor_calloc(smartlist_len(votes), + sizeof(uint32_t)); + uint32_t *measured_guardfraction = tor_calloc(smartlist_len(votes), + sizeof(uint32_t)); + int num_bandwidths; + int num_mbws; + int num_guardfraction_inputs; + + 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 n_authorities_measuring_bandwidth; + + 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)); + + size = tor_calloc(smartlist_len(votes), sizeof(int)); + n_voter_flags = tor_calloc(smartlist_len(votes), sizeof(int)); + n_flag_voters = tor_calloc(smartlist_len(flags), sizeof(int)); + flag_map = tor_calloc(smartlist_len(votes), sizeof(int *)); + named_flag = tor_calloc(smartlist_len(votes), sizeof(int)); + unnamed_flag = tor_calloc(smartlist_len(votes), sizeof(int)); + for (i = 0; i < smartlist_len(votes); ++i) + unnamed_flag[i] = named_flag[i] = -1; + + /* Build the flag indexes. Note that no vote can have more than 64 members + * for known_flags, so no value will be greater than 63, so it's safe to + * do U64_LITERAL(1) << index on these values. But note also that + * named_flag and unnamed_flag are initialized to -1, so we need to check + * that they're actually set before doing U64_LITERAL(1) << index with + * them.*/ + SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) { + flag_map[v_sl_idx] = tor_calloc(smartlist_len(v->known_flags), + sizeof(int)); + if (smartlist_len(v->known_flags) > MAX_KNOWN_FLAGS_IN_VOTE) { + log_warn(LD_BUG, "Somehow, a vote has %d entries in known_flags", + smartlist_len(v->known_flags)); + } + SMARTLIST_FOREACH_BEGIN(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; + } SMARTLIST_FOREACH_END(fl); + n_voter_flags[v_sl_idx] = smartlist_len(v->known_flags); + size[v_sl_idx] = smartlist_len(v->routerstatus_list); + } SMARTLIST_FOREACH_END(v); + + /* Named and Unnamed get treated specially */ + { + SMARTLIST_FOREACH_BEGIN(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_BEGIN(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 && + fast_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_END(rs); + } SMARTLIST_FOREACH_END(v); + + SMARTLIST_FOREACH_BEGIN(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_BEGIN(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 (fast_memeq(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. */ + } + } + } SMARTLIST_FOREACH_END(rs); + } SMARTLIST_FOREACH_END(v); + } + + /* We need to know how many votes measure bandwidth. */ + n_authorities_measuring_bandwidth = 0; + SMARTLIST_FOREACH(votes, const networkstatus_t *, v, + if (v->has_measured_bws) { + ++n_authorities_measuring_bandwidth; + } + ); + + /* Populate the collator */ + collator = dircollator_new(smartlist_len(votes), total_authorities); + SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) { + dircollator_add_vote(collator, v); + } SMARTLIST_FOREACH_END(v); + + dircollator_collate(collator, consensus_method); + + /* Now go through all the votes */ + flag_counts = tor_calloc(smartlist_len(flags), sizeof(int)); + const int num_routers = dircollator_n_routers(collator); + for (i = 0; i < num_routers; ++i) { + vote_routerstatus_t **vrs_lst = + dircollator_get_votes_for_router(collator, i); + + vote_routerstatus_t *rs; + routerstatus_t rs_out; + const char *current_rsa_id = NULL; + const char *chosen_version; + const char *chosen_protocol_list; + const char *chosen_name = NULL; + int exitsummary_disagreement = 0; + int is_named = 0, is_unnamed = 0, is_running = 0, is_valid = 0; + int is_guard = 0, is_exit = 0, is_bad_exit = 0; + int naming_conflict = 0; + int n_listing = 0; + char microdesc_digest[DIGEST256_LEN]; + tor_addr_port_t alt_orport = {TOR_ADDR_NULL, 0}; + + memset(flag_counts, 0, sizeof(int)*smartlist_len(flags)); + smartlist_clear(matching_descs); + smartlist_clear(chosen_flags); + smartlist_clear(versions); + smartlist_clear(protocols); + num_bandwidths = 0; + num_mbws = 0; + num_guardfraction_inputs = 0; + int ed_consensus = 0; + const uint8_t *ed_consensus_val = NULL; + + /* Okay, go through all the entries for this digest. */ + for (int voter_idx = 0; voter_idx < smartlist_len(votes); ++voter_idx) { + if (vrs_lst[voter_idx] == NULL) + continue; /* This voter had nothing to say about this entry. */ + rs = vrs_lst[voter_idx]; + ++n_listing; + + current_rsa_id = rs->status.identity_digest; + + smartlist_add(matching_descs, rs); + if (rs->version && rs->version[0]) + smartlist_add(versions, rs->version); + + if (rs->protocols) { + /* We include this one even if it's empty: voting for an + * empty protocol list actually is meaningful. */ + smartlist_add(protocols, rs->protocols); + } + + /* Tally up all the flags. */ + for (int flag = 0; flag < n_voter_flags[voter_idx]; ++flag) { + if (rs->flags & (U64_LITERAL(1) << flag)) + ++flag_counts[flag_map[voter_idx][flag]]; + } + if (named_flag[voter_idx] >= 0 && + (rs->flags & (U64_LITERAL(1) << named_flag[voter_idx]))) { + if (chosen_name && strcmp(chosen_name, rs->status.nickname)) { + log_notice(LD_DIR, "Conflict on naming for router: %s vs %s", + chosen_name, rs->status.nickname); + naming_conflict = 1; + } + chosen_name = rs->status.nickname; + } + + /* Count guardfraction votes and note down the values. */ + if (rs->status.has_guardfraction) { + measured_guardfraction[num_guardfraction_inputs++] = + rs->status.guardfraction_percentage; + } + + /* count bandwidths */ + if (rs->has_measured_bw) + measured_bws_kb[num_mbws++] = rs->measured_bw_kb; + + if (rs->status.has_bandwidth) + bandwidths_kb[num_bandwidths++] = rs->status.bandwidth_kb; + + /* Count number for which ed25519 is canonical. */ + if (rs->ed25519_reflects_consensus) { + ++ed_consensus; + if (ed_consensus_val) { + tor_assert(fast_memeq(ed_consensus_val, rs->ed25519_id, + ED25519_PUBKEY_LEN)); + } else { + ed_consensus_val = rs->ed25519_id; + } + } + } + + /* We don't include this router at all unless more than half of + * the authorities we believe in list it. */ + if (n_listing <= total_authorities/2) + continue; + + if (ed_consensus > 0) { + if (ed_consensus <= total_authorities / 2) { + log_warn(LD_BUG, "Not enough entries had ed_consensus set; how " + "can we have a consensus of %d?", ed_consensus); + } + } + + /* The clangalyzer can't figure out that this will never be NULL + * if n_listing is at least 1 */ + tor_assert(current_rsa_id); + + /* Figure out the most popular opinion of what the most recent + * routerinfo and its contents are. */ + memset(microdesc_digest, 0, sizeof(microdesc_digest)); + rs = compute_routerstatus_consensus(matching_descs, consensus_method, + microdesc_digest, &alt_orport); + /* Copy bits of that into rs_out. */ + memset(&rs_out, 0, sizeof(rs_out)); + tor_assert(fast_memeq(current_rsa_id, + rs->status.identity_digest,DIGEST_LEN)); + memcpy(rs_out.identity_digest, current_rsa_id, DIGEST_LEN); + memcpy(rs_out.descriptor_digest, rs->status.descriptor_digest, + DIGEST_LEN); + rs_out.addr = rs->status.addr; + rs_out.published_on = rs->status.published_on; + rs_out.dir_port = rs->status.dir_port; + rs_out.or_port = rs->status.or_port; + tor_addr_copy(&rs_out.ipv6_addr, &alt_orport.addr); + rs_out.ipv6_orport = alt_orport.port; + rs_out.has_bandwidth = 0; + rs_out.has_exitsummary = 0; + + if (chosen_name && !naming_conflict) { + strlcpy(rs_out.nickname, chosen_name, sizeof(rs_out.nickname)); + } else { + strlcpy(rs_out.nickname, rs->status.nickname, sizeof(rs_out.nickname)); + } + + { + const char *d = strmap_get_lc(name_to_id_map, rs_out.nickname); + if (!d) { + is_named = is_unnamed = 0; + } else if (fast_memeq(d, current_rsa_id, DIGEST_LEN)) { + is_named = 1; is_unnamed = 0; + } else { + is_named = 0; is_unnamed = 1; + } + } + + /* Set the flags. */ + smartlist_add(chosen_flags, (char*)"s"); /* for the start of the line. */ + SMARTLIST_FOREACH_BEGIN(flags, const char *, fl) { + if (!strcmp(fl, "Named")) { + if (is_named) + smartlist_add(chosen_flags, (char*)fl); + } else if (!strcmp(fl, "Unnamed")) { + if (is_unnamed) + smartlist_add(chosen_flags, (char*)fl); + } else if (!strcmp(fl, "NoEdConsensus")) { + if (ed_consensus <= total_authorities/2) + smartlist_add(chosen_flags, (char*)fl); + } else { + if (flag_counts[fl_sl_idx] > n_flag_voters[fl_sl_idx]/2) { + smartlist_add(chosen_flags, (char*)fl); + if (!strcmp(fl, "Exit")) + is_exit = 1; + else if (!strcmp(fl, "Guard")) + is_guard = 1; + else if (!strcmp(fl, "Running")) + is_running = 1; + else if (!strcmp(fl, "BadExit")) + is_bad_exit = 1; + else if (!strcmp(fl, "Valid")) + is_valid = 1; + } + } + } SMARTLIST_FOREACH_END(fl); + + /* Starting with consensus method 4 we do not list servers + * that are not running in a consensus. See Proposal 138 */ + if (!is_running) + continue; + + /* Starting with consensus method 24, we don't list servers + * that are not valid in a consensus. See Proposal 272 */ + if (!is_valid) + continue; + + /* Pick the version. */ + if (smartlist_len(versions)) { + sort_version_list(versions, 0); + chosen_version = get_most_frequent_member(versions); + } else { + chosen_version = NULL; + } + + /* Pick the protocol list */ + if (smartlist_len(protocols)) { + smartlist_sort_strings(protocols); + chosen_protocol_list = get_most_frequent_member(protocols); + } else { + chosen_protocol_list = NULL; + } + + /* If it's a guard and we have enough guardfraction votes, + calculate its consensus guardfraction value. */ + if (is_guard && num_guardfraction_inputs > 2) { + rs_out.has_guardfraction = 1; + rs_out.guardfraction_percentage = median_uint32(measured_guardfraction, + num_guardfraction_inputs); + /* final value should be an integer percentage! */ + tor_assert(rs_out.guardfraction_percentage <= 100); + } + + /* Pick a bandwidth */ + if (num_mbws > 2) { + rs_out.has_bandwidth = 1; + rs_out.bw_is_unmeasured = 0; + rs_out.bandwidth_kb = median_uint32(measured_bws_kb, num_mbws); + } else if (num_bandwidths > 0) { + rs_out.has_bandwidth = 1; + rs_out.bw_is_unmeasured = 1; + rs_out.bandwidth_kb = median_uint32(bandwidths_kb, num_bandwidths); + if (n_authorities_measuring_bandwidth > 2) { + /* Cap non-measured bandwidths. */ + if (rs_out.bandwidth_kb > max_unmeasured_bw_kb) { + rs_out.bandwidth_kb = max_unmeasured_bw_kb; + } + } + } + + /* Fix bug 2203: Do not count BadExit nodes as Exits for bw weights */ + is_exit = is_exit && !is_bad_exit; + + /* Update total bandwidth weights with the bandwidths of this router. */ + { + update_total_bandwidth_weights(&rs_out, + is_exit, is_guard, + &G, &M, &E, &D, &T); + } + + /* Ok, we already picked a descriptor digest we want to list + * previously. Now we want to use the exit policy summary from + * that descriptor. If everybody plays nice all the voters who + * listed that descriptor will have the same summary. If not then + * something is fishy and we'll use the most common one (breaking + * ties in favor of lexicographically larger one (only because it + * lets me reuse more existing code)). + * + * The other case that can happen is that no authority that voted + * for that descriptor has an exit policy summary. That's + * probably quite unlikely but can happen. In that case we use + * the policy that was most often listed in votes, again breaking + * ties like in the previous case. + */ + { + /* Okay, go through all the votes for this router. We prepared + * that list previously */ + const char *chosen_exitsummary = NULL; + smartlist_clear(exitsummaries); + SMARTLIST_FOREACH_BEGIN(matching_descs, vote_routerstatus_t *, vsr) { + /* Check if the vote where this status comes from had the + * proper descriptor */ + tor_assert(fast_memeq(rs_out.identity_digest, + vsr->status.identity_digest, + DIGEST_LEN)); + if (vsr->status.has_exitsummary && + fast_memeq(rs_out.descriptor_digest, + vsr->status.descriptor_digest, + DIGEST_LEN)) { + tor_assert(vsr->status.exitsummary); + smartlist_add(exitsummaries, vsr->status.exitsummary); + if (!chosen_exitsummary) { + chosen_exitsummary = vsr->status.exitsummary; + } else if (strcmp(chosen_exitsummary, vsr->status.exitsummary)) { + /* Great. There's disagreement among the voters. That + * really shouldn't be */ + exitsummary_disagreement = 1; + } + } + } SMARTLIST_FOREACH_END(vsr); + + if (exitsummary_disagreement) { + char id[HEX_DIGEST_LEN+1]; + char dd[HEX_DIGEST_LEN+1]; + base16_encode(id, sizeof(dd), rs_out.identity_digest, DIGEST_LEN); + base16_encode(dd, sizeof(dd), rs_out.descriptor_digest, DIGEST_LEN); + log_warn(LD_DIR, "The voters disagreed on the exit policy summary " + " for router %s with descriptor %s. This really shouldn't" + " have happened.", id, dd); + + smartlist_sort_strings(exitsummaries); + chosen_exitsummary = get_most_frequent_member(exitsummaries); + } else if (!chosen_exitsummary) { + char id[HEX_DIGEST_LEN+1]; + char dd[HEX_DIGEST_LEN+1]; + base16_encode(id, sizeof(dd), rs_out.identity_digest, DIGEST_LEN); + base16_encode(dd, sizeof(dd), rs_out.descriptor_digest, DIGEST_LEN); + log_warn(LD_DIR, "Not one of the voters that made us select" + "descriptor %s for router %s had an exit policy" + "summary", dd, id); + + /* Ok, none of those voting for the digest we chose had an + * exit policy for us. Well, that kinda sucks. + */ + smartlist_clear(exitsummaries); + SMARTLIST_FOREACH(matching_descs, vote_routerstatus_t *, vsr, { + if (vsr->status.has_exitsummary) + smartlist_add(exitsummaries, vsr->status.exitsummary); + }); + smartlist_sort_strings(exitsummaries); + chosen_exitsummary = get_most_frequent_member(exitsummaries); + + if (!chosen_exitsummary) + log_warn(LD_DIR, "Wow, not one of the voters had an exit " + "policy summary for %s. Wow.", id); + } + + if (chosen_exitsummary) { + rs_out.has_exitsummary = 1; + /* yea, discards the const */ + rs_out.exitsummary = (char *)chosen_exitsummary; + } + } + + if (flavor == FLAV_MICRODESC && + tor_digest256_is_zero(microdesc_digest)) { + /* With no microdescriptor digest, we omit the entry entirely. */ + continue; + } + + { + char *buf; + /* Okay!! Now we can write the descriptor... */ + /* First line goes into "buf". */ + buf = routerstatus_format_entry(&rs_out, NULL, NULL, + rs_format, consensus_method, NULL); + if (buf) + smartlist_add(chunks, buf); + } + /* Now an m line, if applicable. */ + if (flavor == FLAV_MICRODESC && + !tor_digest256_is_zero(microdesc_digest)) { + char m[BASE64_DIGEST256_LEN+1]; + digest256_to_base64(m, microdesc_digest); + smartlist_add_asprintf(chunks, "m %s\n", m); + } + /* Next line is all flags. The "\n" is missing. */ + smartlist_add(chunks, + smartlist_join_strings(chosen_flags, " ", 0, NULL)); + /* Now the version line. */ + if (chosen_version) { + smartlist_add_strdup(chunks, "\nv "); + smartlist_add_strdup(chunks, chosen_version); + } + smartlist_add_strdup(chunks, "\n"); + if (chosen_protocol_list && + consensus_method >= MIN_METHOD_FOR_RS_PROTOCOLS) { + smartlist_add_asprintf(chunks, "pr %s\n", chosen_protocol_list); + } + /* Now the weight line. */ + if (rs_out.has_bandwidth) { + char *guardfraction_str = NULL; + int unmeasured = rs_out.bw_is_unmeasured; + + /* If we have guardfraction info, include it in the 'w' line. */ + if (rs_out.has_guardfraction) { + tor_asprintf(&guardfraction_str, + " GuardFraction=%u", rs_out.guardfraction_percentage); + } + smartlist_add_asprintf(chunks, "w Bandwidth=%d%s%s\n", + rs_out.bandwidth_kb, + unmeasured?" Unmeasured=1":"", + guardfraction_str ? guardfraction_str : ""); + + tor_free(guardfraction_str); + } + + /* Now the exitpolicy summary line. */ + if (rs_out.has_exitsummary && flavor == FLAV_NS) { + smartlist_add_asprintf(chunks, "p %s\n", rs_out.exitsummary); + } + + /* And the loop is over and we move on to the next router */ + } + + tor_free(size); + tor_free(n_voter_flags); + tor_free(n_flag_voters); + for (i = 0; i < smartlist_len(votes); ++i) + tor_free(flag_map[i]); + tor_free(flag_map); + tor_free(flag_counts); + tor_free(named_flag); + tor_free(unnamed_flag); + strmap_free(name_to_id_map, NULL); + smartlist_free(matching_descs); + smartlist_free(chosen_flags); + smartlist_free(versions); + smartlist_free(protocols); + smartlist_free(exitsummaries); + tor_free(bandwidths_kb); + tor_free(measured_bws_kb); + tor_free(measured_guardfraction); + } + + /* Mark the directory footer region */ + smartlist_add_strdup(chunks, "directory-footer\n"); + + { + int64_t weight_scale = BW_WEIGHT_SCALE; + char *bw_weight_param = NULL; + + // Parse params, extract BW_WEIGHT_SCALE if present + // DO NOT use consensus_param_bw_weight_scale() in this code! + // The consensus is not formed yet! + /* XXXX Extract this code into a common function. Or not: #19011. */ + if (params) { + if (strcmpstart(params, "bwweightscale=") == 0) + bw_weight_param = params; + else + bw_weight_param = strstr(params, " bwweightscale="); + } + + if (bw_weight_param) { + int ok=0; + char *eq = strchr(bw_weight_param, '='); + if (eq) { + weight_scale = tor_parse_long(eq+1, 10, 1, INT32_MAX, &ok, + NULL); + if (!ok) { + log_warn(LD_DIR, "Bad element '%s' in bw weight param", + escaped(bw_weight_param)); + weight_scale = BW_WEIGHT_SCALE; + } + } else { + log_warn(LD_DIR, "Bad element '%s' in bw weight param", + escaped(bw_weight_param)); + weight_scale = BW_WEIGHT_SCALE; + } + } + + added_weights = networkstatus_compute_bw_weights_v10(chunks, G, M, E, D, + T, weight_scale); + } + + /* Add a signature. */ + { + char digest[DIGEST256_LEN]; + char fingerprint[HEX_DIGEST_LEN+1]; + char signing_key_fingerprint[HEX_DIGEST_LEN+1]; + digest_algorithm_t digest_alg = + flavor == FLAV_NS ? DIGEST_SHA1 : DIGEST_SHA256; + size_t digest_len = + flavor == FLAV_NS ? DIGEST_LEN : DIGEST256_LEN; + const char *algname = crypto_digest_algorithm_get_name(digest_alg); + char *signature; + + smartlist_add_strdup(chunks, "directory-signature "); + + /* Compute the hash of the chunks. */ + crypto_digest_smartlist(digest, digest_len, chunks, "", digest_alg); + + /* Get the fingerprints */ + crypto_pk_get_fingerprint(identity_key, fingerprint, 0); + crypto_pk_get_fingerprint(signing_key, signing_key_fingerprint, 0); + + /* add the junk that will go at the end of the line. */ + if (flavor == FLAV_NS) { + smartlist_add_asprintf(chunks, "%s %s\n", fingerprint, + signing_key_fingerprint); + } else { + smartlist_add_asprintf(chunks, "%s %s %s\n", + algname, fingerprint, + signing_key_fingerprint); + } + /* And the signature. */ + if (!(signature = router_get_dirobj_signature(digest, digest_len, + signing_key))) { + log_warn(LD_BUG, "Couldn't sign consensus networkstatus."); + goto done; + } + smartlist_add(chunks, signature); + + if (legacy_id_key_digest && legacy_signing_key) { + smartlist_add_strdup(chunks, "directory-signature "); + base16_encode(fingerprint, sizeof(fingerprint), + legacy_id_key_digest, DIGEST_LEN); + crypto_pk_get_fingerprint(legacy_signing_key, + signing_key_fingerprint, 0); + if (flavor == FLAV_NS) { + smartlist_add_asprintf(chunks, "%s %s\n", fingerprint, + signing_key_fingerprint); + } else { + smartlist_add_asprintf(chunks, "%s %s %s\n", + algname, fingerprint, + signing_key_fingerprint); + } + + if (!(signature = router_get_dirobj_signature(digest, digest_len, + legacy_signing_key))) { + log_warn(LD_BUG, "Couldn't sign consensus networkstatus."); + goto done; + } + smartlist_add(chunks, signature); + } + } + + result = smartlist_join_strings(chunks, "", 0, NULL); + + { + networkstatus_t *c; + if (!(c = networkstatus_parse_vote_from_string(result, NULL, + NS_TYPE_CONSENSUS))) { + log_err(LD_BUG, "Generated a networkstatus consensus we couldn't " + "parse."); + tor_free(result); + goto done; + } + // Verify balancing parameters + if (added_weights) { + networkstatus_verify_bw_weights(c, consensus_method); + } + networkstatus_vote_free(c); + } + + done: + + dircollator_free(collator); + tor_free(client_versions); + tor_free(server_versions); + tor_free(packages); + SMARTLIST_FOREACH(flags, char *, cp, tor_free(cp)); + smartlist_free(flags); + SMARTLIST_FOREACH(chunks, char *, cp, tor_free(cp)); + smartlist_free(chunks); + SMARTLIST_FOREACH(param_list, char *, cp, tor_free(cp)); + smartlist_free(param_list); + + return result; +} + +/** Given a list of networkstatus_t for each vote, return a newly allocated + * string containing the "package" lines for the vote. */ +STATIC char * +compute_consensus_package_lines(smartlist_t *votes) +{ + const int n_votes = smartlist_len(votes); + + /* This will be a map from "packagename version" strings to arrays + * of const char *, with the i'th member of the array corresponding to the + * package line from the i'th vote. + */ + strmap_t *package_status = strmap_new(); + + SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) { + if (! v->package_lines) + continue; + SMARTLIST_FOREACH_BEGIN(v->package_lines, const char *, line) { + if (! validate_recommended_package_line(line)) + continue; + + /* Skip 'cp' to the second space in the line. */ + const char *cp = strchr(line, ' '); + if (!cp) continue; + ++cp; + cp = strchr(cp, ' '); + if (!cp) continue; + + char *key = tor_strndup(line, cp - line); + + const char **status = strmap_get(package_status, key); + if (!status) { + status = tor_calloc(n_votes, sizeof(const char *)); + strmap_set(package_status, key, status); + } + status[v_sl_idx] = line; /* overwrite old value */ + tor_free(key); + } SMARTLIST_FOREACH_END(line); + } SMARTLIST_FOREACH_END(v); + + smartlist_t *entries = smartlist_new(); /* temporary */ + smartlist_t *result_list = smartlist_new(); /* output */ + STRMAP_FOREACH(package_status, key, const char **, values) { + int i, count=-1; + for (i = 0; i < n_votes; ++i) { + if (values[i]) + smartlist_add(entries, (void*) values[i]); + } + smartlist_sort_strings(entries); + int n_voting_for_entry = smartlist_len(entries); + const char *most_frequent = + smartlist_get_most_frequent_string_(entries, &count); + + if (n_voting_for_entry >= 3 && count > n_voting_for_entry / 2) { + smartlist_add_asprintf(result_list, "package %s\n", most_frequent); + } + + smartlist_clear(entries); + + } STRMAP_FOREACH_END; + + smartlist_sort_strings(result_list); + + char *result = smartlist_join_strings(result_list, "", 0, NULL); + + SMARTLIST_FOREACH(result_list, char *, cp, tor_free(cp)); + smartlist_free(result_list); + smartlist_free(entries); + strmap_free(package_status, tor_free_); + + return result; +} + +/** Given a consensus vote <b>target</b> and a set of detached signatures in + * <b>sigs</b> that correspond to the same consensus, check whether there are + * any new signatures in <b>src_voter_list</b> that should be added to + * <b>target</b>. (A signature should be added if we have no signature for that + * voter in <b>target</b> yet, or if we have no verifiable signature and the + * new signature is verifiable.) Return the number of signatures added or + * changed, or -1 if the document signed by <b>sigs</b> isn't the same + * document as <b>target</b>. */ +STATIC int +networkstatus_add_detached_signatures(networkstatus_t *target, + ns_detached_signatures_t *sigs, + const char *source, + int severity, + const char **msg_out) +{ + int r = 0; + const char *flavor; + smartlist_t *siglist; + tor_assert(sigs); + tor_assert(target); + tor_assert(target->type == NS_TYPE_CONSENSUS); + + flavor = networkstatus_get_flavor_name(target->flavor); + + /* Do the times seem right? */ + if (target->valid_after != sigs->valid_after) { + *msg_out = "Valid-After times do not match " + "when adding detached signatures to consensus"; + return -1; + } + if (target->fresh_until != sigs->fresh_until) { + *msg_out = "Fresh-until times do not match " + "when adding detached signatures to consensus"; + return -1; + } + if (target->valid_until != sigs->valid_until) { + *msg_out = "Valid-until times do not match " + "when adding detached signatures to consensus"; + return -1; + } + siglist = strmap_get(sigs->signatures, flavor); + if (!siglist) { + *msg_out = "No signatures for given consensus flavor"; + return -1; + } + + /** Make sure all the digests we know match, and at least one matches. */ + { + common_digests_t *digests = strmap_get(sigs->digests, flavor); + int n_matches = 0; + int alg; + if (!digests) { + *msg_out = "No digests for given consensus flavor"; + return -1; + } + for (alg = DIGEST_SHA1; alg < N_COMMON_DIGEST_ALGORITHMS; ++alg) { + if (!tor_mem_is_zero(digests->d[alg], DIGEST256_LEN)) { + if (fast_memeq(target->digests.d[alg], digests->d[alg], + DIGEST256_LEN)) { + ++n_matches; + } else { + *msg_out = "Mismatched digest."; + return -1; + } + } + } + if (!n_matches) { + *msg_out = "No recognized digests for given consensus flavor"; + } + } + + /* For each voter in src... */ + SMARTLIST_FOREACH_BEGIN(siglist, document_signature_t *, sig) { + char voter_identity[HEX_DIGEST_LEN+1]; + networkstatus_voter_info_t *target_voter = + networkstatus_get_voter_by_id(target, sig->identity_digest); + authority_cert_t *cert = NULL; + const char *algorithm; + document_signature_t *old_sig = NULL; + + algorithm = crypto_digest_algorithm_get_name(sig->alg); + + base16_encode(voter_identity, sizeof(voter_identity), + sig->identity_digest, DIGEST_LEN); + log_info(LD_DIR, "Looking at signature from %s using %s", voter_identity, + algorithm); + /* If the target doesn't know about this voter, then forget it. */ + if (!target_voter) { + log_info(LD_DIR, "We do not know any voter with ID %s", voter_identity); + continue; + } + + old_sig = networkstatus_get_voter_sig_by_alg(target_voter, sig->alg); + + /* If the target already has a good signature from this voter, then skip + * this one. */ + if (old_sig && old_sig->good_signature) { + log_info(LD_DIR, "We already have a good signature from %s using %s", + voter_identity, algorithm); + continue; + } + + /* Try checking the signature if we haven't already. */ + if (!sig->good_signature && !sig->bad_signature) { + cert = authority_cert_get_by_digests(sig->identity_digest, + sig->signing_key_digest); + if (cert) { + /* Not checking the return value here, since we are going to look + * at the status of sig->good_signature in a moment. */ + (void) networkstatus_check_document_signature(target, sig, cert); + } + } + + /* If this signature is good, or we don't have any signature yet, + * then maybe add it. */ + if (sig->good_signature || !old_sig || old_sig->bad_signature) { + log_info(LD_DIR, "Adding signature from %s with %s", voter_identity, + algorithm); + tor_log(severity, LD_DIR, "Added a signature for %s from %s.", + target_voter->nickname, source); + ++r; + if (old_sig) { + smartlist_remove(target_voter->sigs, old_sig); + document_signature_free(old_sig); + } + smartlist_add(target_voter->sigs, document_signature_dup(sig)); + } else { + log_info(LD_DIR, "Not adding signature from %s", voter_identity); + } + } SMARTLIST_FOREACH_END(sig); + + return r; +} + +/** Return a newly allocated string containing all the signatures on + * <b>consensus</b> by all voters. If <b>for_detached_signatures</b> is true, + * then the signatures will be put in a detached signatures document, so + * prefix any non-NS-flavored signatures with "additional-signature" rather + * than "directory-signature". */ +static char * +networkstatus_format_signatures(networkstatus_t *consensus, + int for_detached_signatures) +{ + smartlist_t *elements; + char buf[4096]; + char *result = NULL; + int n_sigs = 0; + const consensus_flavor_t flavor = consensus->flavor; + const char *flavor_name = networkstatus_get_flavor_name(flavor); + const char *keyword; + + if (for_detached_signatures && flavor != FLAV_NS) + keyword = "additional-signature"; + else + keyword = "directory-signature"; + + elements = smartlist_new(); + + SMARTLIST_FOREACH_BEGIN(consensus->voters, networkstatus_voter_info_t *, v) { + SMARTLIST_FOREACH_BEGIN(v->sigs, document_signature_t *, sig) { + char sk[HEX_DIGEST_LEN+1]; + char id[HEX_DIGEST_LEN+1]; + if (!sig->signature || sig->bad_signature) + continue; + ++n_sigs; + base16_encode(sk, sizeof(sk), sig->signing_key_digest, DIGEST_LEN); + base16_encode(id, sizeof(id), sig->identity_digest, DIGEST_LEN); + if (flavor == FLAV_NS) { + smartlist_add_asprintf(elements, + "%s %s %s\n-----BEGIN SIGNATURE-----\n", + keyword, id, sk); + } else { + const char *digest_name = + crypto_digest_algorithm_get_name(sig->alg); + smartlist_add_asprintf(elements, + "%s%s%s %s %s %s\n-----BEGIN SIGNATURE-----\n", + keyword, + for_detached_signatures ? " " : "", + for_detached_signatures ? flavor_name : "", + digest_name, id, sk); + } + base64_encode(buf, sizeof(buf), sig->signature, sig->signature_len, + BASE64_ENCODE_MULTILINE); + strlcat(buf, "-----END SIGNATURE-----\n", sizeof(buf)); + smartlist_add_strdup(elements, buf); + } SMARTLIST_FOREACH_END(sig); + } SMARTLIST_FOREACH_END(v); + + result = smartlist_join_strings(elements, "", 0, NULL); + SMARTLIST_FOREACH(elements, char *, cp, tor_free(cp)); + smartlist_free(elements); + if (!n_sigs) + tor_free(result); + return result; +} + +/** Return a newly allocated string holding the detached-signatures document + * corresponding to the signatures on <b>consensuses</b>, which must contain + * exactly one FLAV_NS consensus, and no more than one consensus for each + * other flavor. */ +STATIC char * +networkstatus_get_detached_signatures(smartlist_t *consensuses) +{ + smartlist_t *elements; + char *result = NULL, *sigs = NULL; + networkstatus_t *consensus_ns = NULL; + tor_assert(consensuses); + + SMARTLIST_FOREACH(consensuses, networkstatus_t *, ns, { + tor_assert(ns); + tor_assert(ns->type == NS_TYPE_CONSENSUS); + if (ns && ns->flavor == FLAV_NS) + consensus_ns = ns; + }); + if (!consensus_ns) { + log_warn(LD_BUG, "No NS consensus given."); + return NULL; + } + + elements = smartlist_new(); + + { + char va_buf[ISO_TIME_LEN+1], fu_buf[ISO_TIME_LEN+1], + vu_buf[ISO_TIME_LEN+1]; + char d[HEX_DIGEST_LEN+1]; + + base16_encode(d, sizeof(d), + consensus_ns->digests.d[DIGEST_SHA1], DIGEST_LEN); + format_iso_time(va_buf, consensus_ns->valid_after); + format_iso_time(fu_buf, consensus_ns->fresh_until); + format_iso_time(vu_buf, consensus_ns->valid_until); + + smartlist_add_asprintf(elements, + "consensus-digest %s\n" + "valid-after %s\n" + "fresh-until %s\n" + "valid-until %s\n", d, va_buf, fu_buf, vu_buf); + } + + /* Get all the digests for the non-FLAV_NS consensuses */ + SMARTLIST_FOREACH_BEGIN(consensuses, networkstatus_t *, ns) { + const char *flavor_name = networkstatus_get_flavor_name(ns->flavor); + int alg; + if (ns->flavor == FLAV_NS) + continue; + + /* start with SHA256; we don't include SHA1 for anything but the basic + * consensus. */ + for (alg = DIGEST_SHA256; alg < N_COMMON_DIGEST_ALGORITHMS; ++alg) { + char d[HEX_DIGEST256_LEN+1]; + const char *alg_name = + crypto_digest_algorithm_get_name(alg); + if (tor_mem_is_zero(ns->digests.d[alg], DIGEST256_LEN)) + continue; + base16_encode(d, sizeof(d), ns->digests.d[alg], DIGEST256_LEN); + smartlist_add_asprintf(elements, "additional-digest %s %s %s\n", + flavor_name, alg_name, d); + } + } SMARTLIST_FOREACH_END(ns); + + /* Now get all the sigs for non-FLAV_NS consensuses */ + SMARTLIST_FOREACH_BEGIN(consensuses, networkstatus_t *, ns) { + char *sigs_on_this_consensus; + if (ns->flavor == FLAV_NS) + continue; + sigs_on_this_consensus = networkstatus_format_signatures(ns, 1); + if (!sigs_on_this_consensus) { + log_warn(LD_DIR, "Couldn't format signatures"); + goto err; + } + smartlist_add(elements, sigs_on_this_consensus); + } SMARTLIST_FOREACH_END(ns); + + /* Now add the FLAV_NS consensus signatrures. */ + sigs = networkstatus_format_signatures(consensus_ns, 1); + if (!sigs) + goto err; + smartlist_add(elements, sigs); + + result = smartlist_join_strings(elements, "", 0, NULL); + err: + SMARTLIST_FOREACH(elements, char *, cp, tor_free(cp)); + smartlist_free(elements); + return result; +} + +/** Return a newly allocated string holding a detached-signatures document for + * all of the in-progress consensuses in the <b>n_flavors</b>-element array at + * <b>pending</b>. */ +static char * +get_detached_signatures_from_pending_consensuses(pending_consensus_t *pending, + int n_flavors) +{ + int flav; + char *signatures; + smartlist_t *c = smartlist_new(); + for (flav = 0; flav < n_flavors; ++flav) { + if (pending[flav].consensus) + smartlist_add(c, pending[flav].consensus); + } + signatures = networkstatus_get_detached_signatures(c); + smartlist_free(c); + return signatures; +} + +/** + * Entry point: Take whatever voting actions are pending as of <b>now</b>. + * + * Return the time at which the next action should be taken. + */ +time_t +dirvote_act(const or_options_t *options, time_t now) +{ + if (!authdir_mode_v3(options)) + return TIME_MAX; + tor_assert_nonfatal(voting_schedule.voting_starts); + /* If we haven't initialized this object through this codeflow, we need to + * recalculate the timings to match our vote. The reason to do that is if we + * have a voting schedule initialized 1 minute ago, the voting timings might + * not be aligned to what we should expect with "now". This is especially + * true for TestingTorNetwork using smaller timings. */ + if (voting_schedule.created_on_demand) { + char *keys = list_v3_auth_ids(); + authority_cert_t *c = get_my_v3_authority_cert(); + log_notice(LD_DIR, "Scheduling voting. Known authority IDs are %s. " + "Mine is %s.", + keys, hex_str(c->cache_info.identity_digest, DIGEST_LEN)); + tor_free(keys); + voting_schedule_recalculate_timing(options, now); + } + +#define IF_TIME_FOR_NEXT_ACTION(when_field, done_field) \ + if (! voting_schedule.done_field) { \ + if (voting_schedule.when_field > now) { \ + return voting_schedule.when_field; \ + } else { +#define ENDIF \ + } \ + } + + IF_TIME_FOR_NEXT_ACTION(voting_starts, have_voted) { + log_notice(LD_DIR, "Time to vote."); + dirvote_perform_vote(); + voting_schedule.have_voted = 1; + } ENDIF + IF_TIME_FOR_NEXT_ACTION(fetch_missing_votes, have_fetched_missing_votes) { + log_notice(LD_DIR, "Time to fetch any votes that we're missing."); + dirvote_fetch_missing_votes(); + voting_schedule.have_fetched_missing_votes = 1; + } ENDIF + IF_TIME_FOR_NEXT_ACTION(voting_ends, have_built_consensus) { + log_notice(LD_DIR, "Time to compute a consensus."); + dirvote_compute_consensuses(); + /* XXXX We will want to try again later if we haven't got enough + * votes yet. Implement this if it turns out to ever happen. */ + voting_schedule.have_built_consensus = 1; + } ENDIF + IF_TIME_FOR_NEXT_ACTION(fetch_missing_signatures, + have_fetched_missing_signatures) { + log_notice(LD_DIR, "Time to fetch any signatures that we're missing."); + dirvote_fetch_missing_signatures(); + voting_schedule.have_fetched_missing_signatures = 1; + } ENDIF + IF_TIME_FOR_NEXT_ACTION(interval_starts, + have_published_consensus) { + log_notice(LD_DIR, "Time to publish the consensus and discard old votes"); + dirvote_publish_consensus(); + dirvote_clear_votes(0); + voting_schedule.have_published_consensus = 1; + /* Update our shared random state with the consensus just published. */ + sr_act_post_consensus( + networkstatus_get_latest_consensus_by_flavor(FLAV_NS)); + /* XXXX We will want to try again later if we haven't got enough + * signatures yet. Implement this if it turns out to ever happen. */ + voting_schedule_recalculate_timing(options, now); + return voting_schedule.voting_starts; + } ENDIF + + tor_assert_nonfatal_unreached(); + return now + 1; + +#undef ENDIF +#undef IF_TIME_FOR_NEXT_ACTION +} + +/** A vote networkstatus_t and its unparsed body: held around so we can + * use it to generate a consensus (at voting_ends) and so we can serve it to + * other authorities that might want it. */ +typedef struct pending_vote_t { + cached_dir_t *vote_body; + networkstatus_t *vote; +} pending_vote_t; + +/** List of pending_vote_t for the current vote. Before we've used them to + * build a consensus, the votes go here. */ +static smartlist_t *pending_vote_list = NULL; +/** List of pending_vote_t for the previous vote. After we've used them to + * build a consensus, the votes go here for the next period. */ +static smartlist_t *previous_vote_list = NULL; + +/* DOCDOC pending_consensuses */ +static pending_consensus_t pending_consensuses[N_CONSENSUS_FLAVORS]; + +/** The detached signatures for the consensus that we're currently + * building. */ +static char *pending_consensus_signatures = NULL; + +/** List of ns_detached_signatures_t: hold signatures that get posted to us + * before we have generated the consensus on our own. */ +static smartlist_t *pending_consensus_signature_list = NULL; + +/** Generate a networkstatus vote and post it to all the v3 authorities. + * (V3 Authority only) */ +static int +dirvote_perform_vote(void) +{ + crypto_pk_t *key = get_my_v3_authority_signing_key(); + authority_cert_t *cert = get_my_v3_authority_cert(); + networkstatus_t *ns; + char *contents; + pending_vote_t *pending_vote; + time_t now = time(NULL); + + int status; + const char *msg = ""; + + if (!cert || !key) { + log_warn(LD_NET, "Didn't find key/certificate to generate v3 vote"); + return -1; + } else if (cert->expires < now) { + log_warn(LD_NET, "Can't generate v3 vote with expired certificate"); + return -1; + } + if (!(ns = dirserv_generate_networkstatus_vote_obj(key, cert))) + return -1; + + contents = format_networkstatus_vote(key, ns); + networkstatus_vote_free(ns); + if (!contents) + return -1; + + pending_vote = dirvote_add_vote(contents, &msg, &status); + tor_free(contents); + if (!pending_vote) { + log_warn(LD_DIR, "Couldn't store my own vote! (I told myself, '%s'.)", + msg); + return -1; + } + + directory_post_to_dirservers(DIR_PURPOSE_UPLOAD_VOTE, + ROUTER_PURPOSE_GENERAL, + V3_DIRINFO, + pending_vote->vote_body->dir, + pending_vote->vote_body->dir_len, 0); + log_notice(LD_DIR, "Vote posted."); + return 0; +} + +/** Send an HTTP request to every other v3 authority, for the votes of every + * authority for which we haven't received a vote yet in this period. (V3 + * authority only) */ +static void +dirvote_fetch_missing_votes(void) +{ + smartlist_t *missing_fps = smartlist_new(); + char *resource; + + SMARTLIST_FOREACH_BEGIN(router_get_trusted_dir_servers(), + dir_server_t *, ds) { + if (!(ds->type & V3_DIRINFO)) + continue; + if (!dirvote_get_vote(ds->v3_identity_digest, + DGV_BY_ID|DGV_INCLUDE_PENDING)) { + char *cp = tor_malloc(HEX_DIGEST_LEN+1); + base16_encode(cp, HEX_DIGEST_LEN+1, ds->v3_identity_digest, + DIGEST_LEN); + smartlist_add(missing_fps, cp); + } + } SMARTLIST_FOREACH_END(ds); + + if (!smartlist_len(missing_fps)) { + smartlist_free(missing_fps); + return; + } + { + char *tmp = smartlist_join_strings(missing_fps, " ", 0, NULL); + log_notice(LOG_NOTICE, "We're missing votes from %d authorities (%s). " + "Asking every other authority for a copy.", + smartlist_len(missing_fps), tmp); + tor_free(tmp); + } + resource = smartlist_join_strings(missing_fps, "+", 0, NULL); + directory_get_from_all_authorities(DIR_PURPOSE_FETCH_STATUS_VOTE, + 0, resource); + tor_free(resource); + SMARTLIST_FOREACH(missing_fps, char *, cp, tor_free(cp)); + smartlist_free(missing_fps); +} + +/** Send a request to every other authority for its detached signatures, + * unless we have signatures from all other v3 authorities already. */ +static void +dirvote_fetch_missing_signatures(void) +{ + int need_any = 0; + int i; + for (i=0; i < N_CONSENSUS_FLAVORS; ++i) { + networkstatus_t *consensus = pending_consensuses[i].consensus; + if (!consensus || + networkstatus_check_consensus_signature(consensus, -1) == 1) { + /* We have no consensus, or we have one that's signed by everybody. */ + continue; + } + need_any = 1; + } + if (!need_any) + return; + + directory_get_from_all_authorities(DIR_PURPOSE_FETCH_DETACHED_SIGNATURES, + 0, NULL); +} + +/** Release all storage held by pending consensuses (those waiting for + * signatures). */ +static void +dirvote_clear_pending_consensuses(void) +{ + int i; + for (i = 0; i < N_CONSENSUS_FLAVORS; ++i) { + pending_consensus_t *pc = &pending_consensuses[i]; + tor_free(pc->body); + + networkstatus_vote_free(pc->consensus); + pc->consensus = NULL; + } +} + +/** Drop all currently pending votes, consensus, and detached signatures. */ +static void +dirvote_clear_votes(int all_votes) +{ + if (!previous_vote_list) + previous_vote_list = smartlist_new(); + if (!pending_vote_list) + pending_vote_list = smartlist_new(); + + /* All "previous" votes are now junk. */ + SMARTLIST_FOREACH(previous_vote_list, pending_vote_t *, v, { + cached_dir_decref(v->vote_body); + v->vote_body = NULL; + networkstatus_vote_free(v->vote); + tor_free(v); + }); + smartlist_clear(previous_vote_list); + + if (all_votes) { + /* If we're dumping all the votes, we delete the pending ones. */ + SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, v, { + cached_dir_decref(v->vote_body); + v->vote_body = NULL; + networkstatus_vote_free(v->vote); + tor_free(v); + }); + } else { + /* Otherwise, we move them into "previous". */ + smartlist_add_all(previous_vote_list, pending_vote_list); + } + smartlist_clear(pending_vote_list); + + if (pending_consensus_signature_list) { + SMARTLIST_FOREACH(pending_consensus_signature_list, char *, cp, + tor_free(cp)); + smartlist_clear(pending_consensus_signature_list); + } + tor_free(pending_consensus_signatures); + dirvote_clear_pending_consensuses(); +} + +/** Return a newly allocated string containing the hex-encoded v3 authority + identity digest of every recognized v3 authority. */ +static char * +list_v3_auth_ids(void) +{ + smartlist_t *known_v3_keys = smartlist_new(); + char *keys; + SMARTLIST_FOREACH(router_get_trusted_dir_servers(), + dir_server_t *, ds, + if ((ds->type & V3_DIRINFO) && + !tor_digest_is_zero(ds->v3_identity_digest)) + smartlist_add(known_v3_keys, + tor_strdup(hex_str(ds->v3_identity_digest, DIGEST_LEN)))); + keys = smartlist_join_strings(known_v3_keys, ", ", 0, NULL); + SMARTLIST_FOREACH(known_v3_keys, char *, cp, tor_free(cp)); + smartlist_free(known_v3_keys); + return keys; +} + +/** Called when we have received a networkstatus vote in <b>vote_body</b>. + * Parse and validate it, and on success store it as a pending vote (which we + * then return). Return NULL on failure. Sets *<b>msg_out</b> and + * *<b>status_out</b> to an HTTP response and status code. (V3 authority + * only) */ +pending_vote_t * +dirvote_add_vote(const char *vote_body, const char **msg_out, int *status_out) +{ + networkstatus_t *vote; + networkstatus_voter_info_t *vi; + dir_server_t *ds; + pending_vote_t *pending_vote = NULL; + const char *end_of_vote = NULL; + int any_failed = 0; + tor_assert(vote_body); + tor_assert(msg_out); + tor_assert(status_out); + + if (!pending_vote_list) + pending_vote_list = smartlist_new(); + *status_out = 0; + *msg_out = NULL; + + again: + vote = networkstatus_parse_vote_from_string(vote_body, &end_of_vote, + NS_TYPE_VOTE); + if (!end_of_vote) + end_of_vote = vote_body + strlen(vote_body); + if (!vote) { + log_warn(LD_DIR, "Couldn't parse vote: length was %d", + (int)strlen(vote_body)); + *msg_out = "Unable to parse vote"; + goto err; + } + tor_assert(smartlist_len(vote->voters) == 1); + vi = get_voter(vote); + { + int any_sig_good = 0; + SMARTLIST_FOREACH(vi->sigs, document_signature_t *, sig, + if (sig->good_signature) + any_sig_good = 1); + tor_assert(any_sig_good); + } + ds = trusteddirserver_get_by_v3_auth_digest(vi->identity_digest); + if (!ds) { + char *keys = list_v3_auth_ids(); + log_warn(LD_DIR, "Got a vote from an authority (nickname %s, address %s) " + "with authority key ID %s. " + "This key ID is not recognized. Known v3 key IDs are: %s", + vi->nickname, vi->address, + hex_str(vi->identity_digest, DIGEST_LEN), keys); + tor_free(keys); + *msg_out = "Vote not from a recognized v3 authority"; + goto err; + } + tor_assert(vote->cert); + if (!authority_cert_get_by_digests(vote->cert->cache_info.identity_digest, + vote->cert->signing_key_digest)) { + /* Hey, it's a new cert! */ + trusted_dirs_load_certs_from_string( + vote->cert->cache_info.signed_descriptor_body, + TRUSTED_DIRS_CERTS_SRC_FROM_VOTE, 1 /*flush*/, + NULL); + if (!authority_cert_get_by_digests(vote->cert->cache_info.identity_digest, + vote->cert->signing_key_digest)) { + log_warn(LD_BUG, "We added a cert, but still couldn't find it."); + } + } + + /* Is it for the right period? */ + if (vote->valid_after != voting_schedule.interval_starts) { + char tbuf1[ISO_TIME_LEN+1], tbuf2[ISO_TIME_LEN+1]; + format_iso_time(tbuf1, vote->valid_after); + format_iso_time(tbuf2, voting_schedule.interval_starts); + log_warn(LD_DIR, "Rejecting vote from %s with valid-after time of %s; " + "we were expecting %s", vi->address, tbuf1, tbuf2); + *msg_out = "Bad valid-after time"; + goto err; + } + + /* Fetch any new router descriptors we just learned about */ + update_consensus_router_descriptor_downloads(time(NULL), 1, vote); + + /* Now see whether we already have a vote from this authority. */ + SMARTLIST_FOREACH_BEGIN(pending_vote_list, pending_vote_t *, v) { + if (fast_memeq(v->vote->cert->cache_info.identity_digest, + vote->cert->cache_info.identity_digest, + DIGEST_LEN)) { + networkstatus_voter_info_t *vi_old = get_voter(v->vote); + if (fast_memeq(vi_old->vote_digest, vi->vote_digest, DIGEST_LEN)) { + /* Ah, it's the same vote. Not a problem. */ + log_info(LD_DIR, "Discarding a vote we already have (from %s).", + vi->address); + if (*status_out < 200) + *status_out = 200; + goto discard; + } else if (v->vote->published < vote->published) { + log_notice(LD_DIR, "Replacing an older pending vote from this " + "directory (%s)", vi->address); + cached_dir_decref(v->vote_body); + networkstatus_vote_free(v->vote); + v->vote_body = new_cached_dir(tor_strndup(vote_body, + end_of_vote-vote_body), + vote->published); + v->vote = vote; + if (end_of_vote && + !strcmpstart(end_of_vote, "network-status-version")) + goto again; + + if (*status_out < 200) + *status_out = 200; + if (!*msg_out) + *msg_out = "OK"; + return v; + } else { + *msg_out = "Already have a newer pending vote"; + goto err; + } + } + } SMARTLIST_FOREACH_END(v); + + /* This a valid vote, update our shared random state. */ + sr_handle_received_commits(vote->sr_info.commits, + vote->cert->identity_key); + + pending_vote = tor_malloc_zero(sizeof(pending_vote_t)); + pending_vote->vote_body = new_cached_dir(tor_strndup(vote_body, + end_of_vote-vote_body), + vote->published); + pending_vote->vote = vote; + smartlist_add(pending_vote_list, pending_vote); + + if (!strcmpstart(end_of_vote, "network-status-version ")) { + vote_body = end_of_vote; + goto again; + } + + goto done; + + err: + any_failed = 1; + if (!*msg_out) + *msg_out = "Error adding vote"; + if (*status_out < 400) + *status_out = 400; + + discard: + networkstatus_vote_free(vote); + + if (end_of_vote && !strcmpstart(end_of_vote, "network-status-version ")) { + vote_body = end_of_vote; + goto again; + } + + done: + + if (*status_out < 200) + *status_out = 200; + if (!*msg_out) { + if (!any_failed && !pending_vote) { + *msg_out = "Duplicate discarded"; + } else { + *msg_out = "ok"; + } + } + + return any_failed ? NULL : pending_vote; +} + +/* Write the votes in <b>pending_vote_list</b> to disk. */ +static void +write_v3_votes_to_disk(const smartlist_t *pending_votes) +{ + smartlist_t *votestrings = smartlist_new(); + char *votefile = NULL; + + SMARTLIST_FOREACH(pending_votes, pending_vote_t *, v, + { + sized_chunk_t *c = tor_malloc(sizeof(sized_chunk_t)); + c->bytes = v->vote_body->dir; + c->len = v->vote_body->dir_len; + smartlist_add(votestrings, c); /* collect strings to write to disk */ + }); + + votefile = get_datadir_fname("v3-status-votes"); + write_chunks_to_file(votefile, votestrings, 0, 0); + log_debug(LD_DIR, "Wrote votes to disk (%s)!", votefile); + + tor_free(votefile); + SMARTLIST_FOREACH(votestrings, sized_chunk_t *, c, tor_free(c)); + smartlist_free(votestrings); +} + +/** Try to compute a v3 networkstatus consensus from the currently pending + * votes. Return 0 on success, -1 on failure. Store the consensus in + * pending_consensus: it won't be ready to be published until we have + * everybody else's signatures collected too. (V3 Authority only) */ +static int +dirvote_compute_consensuses(void) +{ + /* Have we got enough votes to try? */ + int n_votes, n_voters, n_vote_running = 0; + smartlist_t *votes = NULL; + char *consensus_body = NULL, *signatures = NULL; + networkstatus_t *consensus = NULL; + authority_cert_t *my_cert; + pending_consensus_t pending[N_CONSENSUS_FLAVORS]; + int flav; + + memset(pending, 0, sizeof(pending)); + + if (!pending_vote_list) + pending_vote_list = smartlist_new(); + + /* Write votes to disk */ + write_v3_votes_to_disk(pending_vote_list); + + /* Setup votes smartlist */ + votes = smartlist_new(); + SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, v, + { + smartlist_add(votes, v->vote); /* collect votes to compute consensus */ + }); + + /* See if consensus managed to achieve majority */ + n_voters = get_n_authorities(V3_DIRINFO); + n_votes = smartlist_len(pending_vote_list); + if (n_votes <= n_voters/2) { + log_warn(LD_DIR, "We don't have enough votes to generate a consensus: " + "%d of %d", n_votes, n_voters/2+1); + goto err; + } + tor_assert(pending_vote_list); + SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, v, { + if (smartlist_contains_string(v->vote->known_flags, "Running")) + n_vote_running++; + }); + if (!n_vote_running) { + /* See task 1066. */ + log_warn(LD_DIR, "Nobody has voted on the Running flag. Generating " + "and publishing a consensus without Running nodes " + "would make many clients stop working. Not " + "generating a consensus!"); + goto err; + } + + if (!(my_cert = get_my_v3_authority_cert())) { + log_warn(LD_DIR, "Can't generate consensus without a certificate."); + goto err; + } + + { + char legacy_dbuf[DIGEST_LEN]; + crypto_pk_t *legacy_sign=NULL; + char *legacy_id_digest = NULL; + int n_generated = 0; + if (get_options()->V3AuthUseLegacyKey) { + authority_cert_t *cert = get_my_v3_legacy_cert(); + legacy_sign = get_my_v3_legacy_signing_key(); + if (cert) { + if (crypto_pk_get_digest(cert->identity_key, legacy_dbuf)) { + log_warn(LD_BUG, + "Unable to compute digest of legacy v3 identity key"); + } else { + legacy_id_digest = legacy_dbuf; + } + } + } + + for (flav = 0; flav < N_CONSENSUS_FLAVORS; ++flav) { + const char *flavor_name = networkstatus_get_flavor_name(flav); + consensus_body = networkstatus_compute_consensus( + votes, n_voters, + my_cert->identity_key, + get_my_v3_authority_signing_key(), legacy_id_digest, legacy_sign, + flav); + + if (!consensus_body) { + log_warn(LD_DIR, "Couldn't generate a %s consensus at all!", + flavor_name); + continue; + } + consensus = networkstatus_parse_vote_from_string(consensus_body, NULL, + NS_TYPE_CONSENSUS); + if (!consensus) { + log_warn(LD_DIR, "Couldn't parse %s consensus we generated!", + flavor_name); + tor_free(consensus_body); + continue; + } + + /* 'Check' our own signature, to mark it valid. */ + networkstatus_check_consensus_signature(consensus, -1); + + pending[flav].body = consensus_body; + pending[flav].consensus = consensus; + n_generated++; + consensus_body = NULL; + consensus = NULL; + } + if (!n_generated) { + log_warn(LD_DIR, "Couldn't generate any consensus flavors at all."); + goto err; + } + } + + signatures = get_detached_signatures_from_pending_consensuses( + pending, N_CONSENSUS_FLAVORS); + + if (!signatures) { + log_warn(LD_DIR, "Couldn't extract signatures."); + goto err; + } + + dirvote_clear_pending_consensuses(); + memcpy(pending_consensuses, pending, sizeof(pending)); + + tor_free(pending_consensus_signatures); + pending_consensus_signatures = signatures; + + if (pending_consensus_signature_list) { + int n_sigs = 0; + /* we may have gotten signatures for this consensus before we built + * it ourself. Add them now. */ + SMARTLIST_FOREACH_BEGIN(pending_consensus_signature_list, char *, sig) { + const char *msg = NULL; + int r = dirvote_add_signatures_to_all_pending_consensuses(sig, + "pending", &msg); + if (r >= 0) + n_sigs += r; + else + log_warn(LD_DIR, + "Could not add queued signature to new consensus: %s", + msg); + tor_free(sig); + } SMARTLIST_FOREACH_END(sig); + if (n_sigs) + log_notice(LD_DIR, "Added %d pending signatures while building " + "consensus.", n_sigs); + smartlist_clear(pending_consensus_signature_list); + } + + log_notice(LD_DIR, "Consensus computed; uploading signature(s)"); + + directory_post_to_dirservers(DIR_PURPOSE_UPLOAD_SIGNATURES, + ROUTER_PURPOSE_GENERAL, + V3_DIRINFO, + pending_consensus_signatures, + strlen(pending_consensus_signatures), 0); + log_notice(LD_DIR, "Signature(s) posted."); + + smartlist_free(votes); + return 0; + err: + smartlist_free(votes); + tor_free(consensus_body); + tor_free(signatures); + networkstatus_vote_free(consensus); + + return -1; +} + +/** Helper: we just got the <b>detached_signatures_body</b> sent to us as + * signatures on the currently pending consensus. Add them to <b>pc</b> + * as appropriate. Return the number of signatures added. (?) */ +static int +dirvote_add_signatures_to_pending_consensus( + pending_consensus_t *pc, + ns_detached_signatures_t *sigs, + const char *source, + int severity, + const char **msg_out) +{ + const char *flavor_name; + int r = -1; + + /* Only call if we have a pending consensus right now. */ + tor_assert(pc->consensus); + tor_assert(pc->body); + tor_assert(pending_consensus_signatures); + + flavor_name = networkstatus_get_flavor_name(pc->consensus->flavor); + *msg_out = NULL; + + { + smartlist_t *sig_list = strmap_get(sigs->signatures, flavor_name); + log_info(LD_DIR, "Have %d signatures for adding to %s consensus.", + sig_list ? smartlist_len(sig_list) : 0, flavor_name); + } + r = networkstatus_add_detached_signatures(pc->consensus, sigs, + source, severity, msg_out); + if (r >= 0) { + log_info(LD_DIR,"Added %d signatures to consensus.", r); + } else { + log_fn(LOG_PROTOCOL_WARN, LD_DIR, + "Unable to add signatures to consensus: %s", + *msg_out ? *msg_out : "(unknown)"); + } + + if (r >= 1) { + char *new_signatures = + networkstatus_format_signatures(pc->consensus, 0); + char *dst, *dst_end; + size_t new_consensus_len; + if (!new_signatures) { + *msg_out = "No signatures to add"; + goto err; + } + new_consensus_len = + strlen(pc->body) + strlen(new_signatures) + 1; + pc->body = tor_realloc(pc->body, new_consensus_len); + dst_end = pc->body + new_consensus_len; + dst = strstr(pc->body, "directory-signature "); + tor_assert(dst); + strlcpy(dst, new_signatures, dst_end-dst); + + /* We remove this block once it has failed to crash for a while. But + * unless it shows up in profiles, we're probably better leaving it in, + * just in case we break detached signature processing at some point. */ + { + networkstatus_t *v = networkstatus_parse_vote_from_string( + pc->body, NULL, + NS_TYPE_CONSENSUS); + tor_assert(v); + networkstatus_vote_free(v); + } + *msg_out = "Signatures added"; + tor_free(new_signatures); + } else if (r == 0) { + *msg_out = "Signatures ignored"; + } else { + goto err; + } + + goto done; + err: + if (!*msg_out) + *msg_out = "Unrecognized error while adding detached signatures."; + done: + return r; +} + +static int +dirvote_add_signatures_to_all_pending_consensuses( + const char *detached_signatures_body, + const char *source, + const char **msg_out) +{ + int r=0, i, n_added = 0, errors = 0; + ns_detached_signatures_t *sigs; + tor_assert(detached_signatures_body); + tor_assert(msg_out); + tor_assert(pending_consensus_signatures); + + if (!(sigs = networkstatus_parse_detached_signatures( + detached_signatures_body, NULL))) { + *msg_out = "Couldn't parse detached signatures."; + goto err; + } + + for (i = 0; i < N_CONSENSUS_FLAVORS; ++i) { + int res; + int severity = i == FLAV_NS ? LOG_NOTICE : LOG_INFO; + pending_consensus_t *pc = &pending_consensuses[i]; + if (!pc->consensus) + continue; + res = dirvote_add_signatures_to_pending_consensus(pc, sigs, source, + severity, msg_out); + if (res < 0) + errors++; + else + n_added += res; + } + + if (errors && !n_added) { + r = -1; + goto err; + } + + if (n_added && pending_consensuses[FLAV_NS].consensus) { + char *new_detached = + get_detached_signatures_from_pending_consensuses( + pending_consensuses, N_CONSENSUS_FLAVORS); + if (new_detached) { + tor_free(pending_consensus_signatures); + pending_consensus_signatures = new_detached; + } + } + + r = n_added; + goto done; + err: + if (!*msg_out) + *msg_out = "Unrecognized error while adding detached signatures."; + done: + ns_detached_signatures_free(sigs); + /* XXXX NM Check how return is used. We can now have an error *and* + signatures added. */ + return r; +} + +/** Helper: we just got the <b>detached_signatures_body</b> sent to us as + * signatures on the currently pending consensus. Add them to the pending + * consensus (if we have one); otherwise queue them until we have a + * consensus. Return negative on failure, nonnegative on success. */ +int +dirvote_add_signatures(const char *detached_signatures_body, + const char *source, + const char **msg) +{ + if (pending_consensuses[FLAV_NS].consensus) { + log_notice(LD_DIR, "Got a signature from %s. " + "Adding it to the pending consensus.", source); + return dirvote_add_signatures_to_all_pending_consensuses( + detached_signatures_body, source, msg); + } else { + log_notice(LD_DIR, "Got a signature from %s. " + "Queuing it for the next consensus.", source); + if (!pending_consensus_signature_list) + pending_consensus_signature_list = smartlist_new(); + smartlist_add_strdup(pending_consensus_signature_list, + detached_signatures_body); + *msg = "Signature queued"; + return 0; + } +} + +/** Replace the consensus that we're currently serving with the one that we've + * been building. (V3 Authority only) */ +static int +dirvote_publish_consensus(void) +{ + int i; + + /* Now remember all the other consensuses as if we were a directory cache. */ + for (i = 0; i < N_CONSENSUS_FLAVORS; ++i) { + pending_consensus_t *pending = &pending_consensuses[i]; + const char *name; + name = networkstatus_get_flavor_name(i); + tor_assert(name); + if (!pending->consensus || + networkstatus_check_consensus_signature(pending->consensus, 1)<0) { + log_warn(LD_DIR, "Not enough info to publish pending %s consensus",name); + continue; + } + + if (networkstatus_set_current_consensus(pending->body, name, 0, NULL)) + log_warn(LD_DIR, "Error publishing %s consensus", name); + else + log_notice(LD_DIR, "Published %s consensus", name); + } + + return 0; +} + +/** Release all static storage held in dirvote.c */ +void +dirvote_free_all(void) +{ + dirvote_clear_votes(1); + /* now empty as a result of dirvote_clear_votes(). */ + smartlist_free(pending_vote_list); + pending_vote_list = NULL; + smartlist_free(previous_vote_list); + previous_vote_list = NULL; + + dirvote_clear_pending_consensuses(); + tor_free(pending_consensus_signatures); + if (pending_consensus_signature_list) { + /* now empty as a result of dirvote_clear_votes(). */ + smartlist_free(pending_consensus_signature_list); + pending_consensus_signature_list = NULL; + } +} + +/* ==== + * Access to pending items. + * ==== */ + +/** Return the body of the consensus that we're currently trying to build. */ +MOCK_IMPL(const char *, +dirvote_get_pending_consensus, (consensus_flavor_t flav)) +{ + tor_assert(((int)flav) >= 0 && (int)flav < N_CONSENSUS_FLAVORS); + return pending_consensuses[flav].body; +} + +/** Return the signatures that we know for the consensus that we're currently + * trying to build. */ +MOCK_IMPL(const char *, +dirvote_get_pending_detached_signatures, (void)) +{ + return pending_consensus_signatures; +} + +/** Return a given vote specified by <b>fp</b>. If <b>by_id</b>, return the + * vote for the authority with the v3 authority identity key digest <b>fp</b>; + * if <b>by_id</b> is false, return the vote whose digest is <b>fp</b>. If + * <b>fp</b> is NULL, return our own vote. If <b>include_previous</b> is + * false, do not consider any votes for a consensus that's already been built. + * If <b>include_pending</b> is false, do not consider any votes for the + * consensus that's in progress. May return NULL if we have no vote for the + * authority in question. */ +const cached_dir_t * +dirvote_get_vote(const char *fp, int flags) +{ + int by_id = flags & DGV_BY_ID; + const int include_pending = flags & DGV_INCLUDE_PENDING; + const int include_previous = flags & DGV_INCLUDE_PREVIOUS; + + if (!pending_vote_list && !previous_vote_list) + return NULL; + if (fp == NULL) { + authority_cert_t *c = get_my_v3_authority_cert(); + if (c) { + fp = c->cache_info.identity_digest; + by_id = 1; + } else + return NULL; + } + if (by_id) { + if (pending_vote_list && include_pending) { + SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, pv, + if (fast_memeq(get_voter(pv->vote)->identity_digest, fp, DIGEST_LEN)) + return pv->vote_body); + } + if (previous_vote_list && include_previous) { + SMARTLIST_FOREACH(previous_vote_list, pending_vote_t *, pv, + if (fast_memeq(get_voter(pv->vote)->identity_digest, fp, DIGEST_LEN)) + return pv->vote_body); + } + } else { + if (pending_vote_list && include_pending) { + SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, pv, + if (fast_memeq(pv->vote->digests.d[DIGEST_SHA1], fp, DIGEST_LEN)) + return pv->vote_body); + } + if (previous_vote_list && include_previous) { + SMARTLIST_FOREACH(previous_vote_list, pending_vote_t *, pv, + if (fast_memeq(pv->vote->digests.d[DIGEST_SHA1], fp, DIGEST_LEN)) + return pv->vote_body); + } + } + return NULL; +} + +/** Construct and return a new microdescriptor from a routerinfo <b>ri</b> + * according to <b>consensus_method</b>. + **/ +STATIC microdesc_t * +dirvote_create_microdescriptor(const routerinfo_t *ri, int consensus_method) +{ + microdesc_t *result = NULL; + char *key = NULL, *summary = NULL, *family = NULL; + size_t keylen; + smartlist_t *chunks = smartlist_new(); + char *output = NULL; + + if (crypto_pk_write_public_key_to_string(ri->onion_pkey, &key, &keylen)<0) + goto done; + summary = policy_summarize(ri->exit_policy, AF_INET); + if (ri->declared_family) + family = smartlist_join_strings(ri->declared_family, " ", 0, NULL); + + smartlist_add_asprintf(chunks, "onion-key\n%s", key); + + if (ri->onion_curve25519_pkey) { + char kbuf[128]; + base64_encode(kbuf, sizeof(kbuf), + (const char*)ri->onion_curve25519_pkey->public_key, + CURVE25519_PUBKEY_LEN, BASE64_ENCODE_MULTILINE); + smartlist_add_asprintf(chunks, "ntor-onion-key %s", kbuf); + } + + /* We originally put a lines in the micrdescriptors, but then we worked out + * that we needed them in the microdesc consensus. See #20916. */ + if (consensus_method < MIN_METHOD_FOR_NO_A_LINES_IN_MICRODESC && + !tor_addr_is_null(&ri->ipv6_addr) && ri->ipv6_orport) + 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 (summary && strcmp(summary, "reject 1-65535")) + smartlist_add_asprintf(chunks, "p %s\n", summary); + + if (ri->ipv6_exit_policy) { + /* XXXX+++ This doesn't match proposal 208, which says these should + * be taken unchanged from the routerinfo. That's bogosity, IMO: + * the proposal should have said to do this instead.*/ + char *p6 = write_short_policy(ri->ipv6_exit_policy); + if (p6 && strcmp(p6, "reject 1-65535")) + smartlist_add_asprintf(chunks, "p6 %s\n", p6); + tor_free(p6); + } + + { + char idbuf[ED25519_BASE64_LEN+1]; + const char *keytype; + if (ri->cache_info.signing_key_cert && + ri->cache_info.signing_key_cert->signing_key_included) { + keytype = "ed25519"; + ed25519_public_to_base64(idbuf, + &ri->cache_info.signing_key_cert->signing_key); + } else { + keytype = "rsa1024"; + digest_to_base64(idbuf, ri->cache_info.identity_digest); + } + smartlist_add_asprintf(chunks, "id %s %s\n", keytype, idbuf); + } + + output = smartlist_join_strings(chunks, "", 0, NULL); + + { + smartlist_t *lst = microdescs_parse_from_string(output, + output+strlen(output), 0, + SAVED_NOWHERE, NULL); + if (smartlist_len(lst) != 1) { + log_warn(LD_DIR, "We generated a microdescriptor we couldn't parse."); + SMARTLIST_FOREACH(lst, microdesc_t *, md, microdesc_free(md)); + smartlist_free(lst); + goto done; + } + result = smartlist_get(lst, 0); + smartlist_free(lst); + } + + done: + tor_free(output); + tor_free(key); + tor_free(summary); + tor_free(family); + if (chunks) { + SMARTLIST_FOREACH(chunks, char *, cp, tor_free(cp)); + smartlist_free(chunks); + } + return result; +} + +/** Format the appropriate vote line to describe the microdescriptor <b>md</b> + * in a consensus vote document. Write it into the <b>out_len</b>-byte buffer + * in <b>out</b>. Return -1 on failure and the number of characters written + * on success. */ +static ssize_t +dirvote_format_microdesc_vote_line(char *out_buf, size_t out_buf_len, + const microdesc_t *md, + int consensus_method_low, + int consensus_method_high) +{ + ssize_t ret = -1; + char d64[BASE64_DIGEST256_LEN+1]; + char *microdesc_consensus_methods = + make_consensus_method_list(consensus_method_low, + consensus_method_high, + ","); + tor_assert(microdesc_consensus_methods); + + if (digest256_to_base64(d64, md->digest)<0) + goto out; + + if (tor_snprintf(out_buf, out_buf_len, "m %s sha256=%s\n", + microdesc_consensus_methods, d64)<0) + goto out; + + ret = strlen(out_buf); + + out: + tor_free(microdesc_consensus_methods); + return ret; +} + +/** Array of start and end of consensus methods used for supported + microdescriptor formats. */ +static const struct consensus_method_range_t { + int low; + 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}, + {-1, -1} +}; + +/** Helper type used when generating the microdescriptor lines in a directory + * vote. */ +typedef struct microdesc_vote_line_t { + int low; + int high; + microdesc_t *md; + struct microdesc_vote_line_t *next; +} microdesc_vote_line_t; + +/** Generate and return a linked list of all the lines that should appear to + * describe a router's microdescriptor versions in a directory vote. + * Add the generated microdescriptors to <b>microdescriptors_out</b>. */ +vote_microdesc_hash_t * +dirvote_format_all_microdesc_vote_lines(const routerinfo_t *ri, time_t now, + smartlist_t *microdescriptors_out) +{ + const struct consensus_method_range_t *cmr; + microdesc_vote_line_t *entries = NULL, *ep; + vote_microdesc_hash_t *result = NULL; + + /* Generate the microdescriptors. */ + for (cmr = microdesc_consensus_methods; + cmr->low != -1 && cmr->high != -1; + cmr++) { + microdesc_t *md = dirvote_create_microdescriptor(ri, cmr->low); + if (md) { + microdesc_vote_line_t *e = + tor_malloc_zero(sizeof(microdesc_vote_line_t)); + e->md = md; + e->low = cmr->low; + e->high = cmr->high; + e->next = entries; + entries = e; + } + } + + /* Compress adjacent identical ones */ + for (ep = entries; ep; ep = ep->next) { + while (ep->next && + fast_memeq(ep->md->digest, ep->next->md->digest, DIGEST256_LEN) && + ep->low == ep->next->high + 1) { + microdesc_vote_line_t *next = ep->next; + ep->low = next->low; + microdesc_free(next->md); + ep->next = next->next; + tor_free(next); + } + } + + /* Format them into vote_microdesc_hash_t, and add to microdescriptors_out.*/ + while ((ep = entries)) { + char buf[128]; + vote_microdesc_hash_t *h; + if (dirvote_format_microdesc_vote_line(buf, sizeof(buf), ep->md, + ep->low, ep->high) >= 0) { + h = tor_malloc_zero(sizeof(vote_microdesc_hash_t)); + h->microdesc_hash_line = tor_strdup(buf); + h->next = result; + result = h; + ep->md->last_listed = now; + smartlist_add(microdescriptors_out, ep->md); + } + entries = ep->next; + tor_free(ep); + } + + return result; +} + +/** Parse and extract all SR commits from <b>tokens</b> and place them in + * <b>ns</b>. */ +static void +extract_shared_random_commits(networkstatus_t *ns, const smartlist_t *tokens) +{ + smartlist_t *chunks = NULL; + + tor_assert(ns); + tor_assert(tokens); + /* Commits are only present in a vote. */ + tor_assert(ns->type == NS_TYPE_VOTE); + + ns->sr_info.commits = smartlist_new(); + + smartlist_t *commits = find_all_by_keyword(tokens, K_COMMIT); + /* It's normal that a vote might contain no commits even if it participates + * in the SR protocol. Don't treat it as an error. */ + if (commits == NULL) { + goto end; + } + + /* Parse the commit. We do NO validation of number of arguments or ordering + * for forward compatibility, it's the parse commit job to inform us if it's + * supported or not. */ + chunks = smartlist_new(); + SMARTLIST_FOREACH_BEGIN(commits, directory_token_t *, tok) { + /* Extract all arguments and put them in the chunks list. */ + for (int i = 0; i < tok->n_args; i++) { + smartlist_add(chunks, tok->args[i]); + } + sr_commit_t *commit = sr_parse_commit(chunks); + smartlist_clear(chunks); + if (commit == NULL) { + /* Get voter identity so we can warn that this dirauth vote contains + * commit we can't parse. */ + networkstatus_voter_info_t *voter = smartlist_get(ns->voters, 0); + tor_assert(voter); + log_warn(LD_DIR, "SR: Unable to parse commit %s from vote of voter %s.", + escaped(tok->object_body), + hex_str(voter->identity_digest, + sizeof(voter->identity_digest))); + /* Commitment couldn't be parsed. Continue onto the next commit because + * this one could be unsupported for instance. */ + continue; + } + /* Add newly created commit object to the vote. */ + smartlist_add(ns->sr_info.commits, commit); + } SMARTLIST_FOREACH_END(tok); + + end: + smartlist_free(chunks); + smartlist_free(commits); +} + +/* Using the given directory tokens in tokens, parse the shared random commits + * and put them in the given vote document ns. + * + * This also sets the SR participation flag if present in the vote. */ +void +dirvote_parse_sr_commits(networkstatus_t *ns, const smartlist_t *tokens) +{ + /* Does this authority participates in the SR protocol? */ + directory_token_t *tok = find_opt_by_keyword(tokens, K_SR_FLAG); + if (tok) { + ns->sr_info.participate = 1; + /* Get the SR commitments and reveals from the vote. */ + extract_shared_random_commits(ns, tokens); + } +} + +/* For the given vote, free the shared random commits if any. */ +void +dirvote_clear_commits(networkstatus_t *ns) +{ + tor_assert(ns->type == NS_TYPE_VOTE); + + if (ns->sr_info.commits) { + SMARTLIST_FOREACH(ns->sr_info.commits, sr_commit_t *, c, + sr_commit_free(c)); + smartlist_free(ns->sr_info.commits); + } +} + +/* The given url is the /tor/status-vote GET directory request. Populates the + * items list with strings that we can compress on the fly and dir_items with + * cached_dir_t objects that have a precompressed deflated version. */ +void +dirvote_dirreq_get_status_vote(const char *url, smartlist_t *items, + smartlist_t *dir_items) +{ + int current; + + url += strlen("/tor/status-vote/"); + current = !strcmpstart(url, "current/"); + url = strchr(url, '/'); + tor_assert(url); + ++url; + if (!strcmp(url, "consensus")) { + const char *item; + tor_assert(!current); /* we handle current consensus specially above, + * since it wants to be spooled. */ + if ((item = dirvote_get_pending_consensus(FLAV_NS))) + smartlist_add(items, (char*)item); + } else if (!current && !strcmp(url, "consensus-signatures")) { + /* XXXX the spec says that we should implement + * current/consensus-signatures too. It doesn't seem to be needed, + * though. */ + const char *item; + if ((item=dirvote_get_pending_detached_signatures())) + smartlist_add(items, (char*)item); + } else if (!strcmp(url, "authority")) { + const cached_dir_t *d; + int flags = DGV_BY_ID | + (current ? DGV_INCLUDE_PREVIOUS : DGV_INCLUDE_PENDING); + if ((d=dirvote_get_vote(NULL, flags))) + smartlist_add(dir_items, (cached_dir_t*)d); + } else { + const cached_dir_t *d; + smartlist_t *fps = smartlist_new(); + int flags; + if (!strcmpstart(url, "d/")) { + url += 2; + flags = DGV_INCLUDE_PENDING | DGV_INCLUDE_PREVIOUS; + } else { + flags = DGV_BY_ID | + (current ? DGV_INCLUDE_PREVIOUS : DGV_INCLUDE_PENDING); + } + dir_split_resource_into_fingerprints(url, fps, NULL, + DSR_HEX|DSR_SORT_UNIQ); + SMARTLIST_FOREACH(fps, char *, fp, { + if ((d = dirvote_get_vote(fp, flags))) + smartlist_add(dir_items, (cached_dir_t*)d); + tor_free(fp); + }); + smartlist_free(fps); + } +} + +/** Get the best estimate of a router's bandwidth for dirauth purposes, + * preferring measured to advertised values if available. */ +static uint32_t +dirserv_get_bandwidth_for_router_kb(const routerinfo_t *ri) +{ + uint32_t bw_kb = 0; + /* + * Yeah, measured bandwidths in measured_bw_line_t are (implicitly + * signed) longs and the ones router_get_advertised_bandwidth() returns + * are uint32_t. + */ + long mbw_kb = 0; + + if (ri) { + /* + * * First try to see if we have a measured bandwidth; don't bother with + * as_of_out here, on the theory that a stale measured bandwidth is still + * better to trust than an advertised one. + */ + if (dirserv_query_measured_bw_cache_kb(ri->cache_info.identity_digest, + &mbw_kb, NULL)) { + /* Got one! */ + bw_kb = (uint32_t)mbw_kb; + } else { + /* If not, fall back to advertised */ + bw_kb = router_get_advertised_bandwidth(ri) / 1000; + } + } + + return bw_kb; +} + +/** Helper for sorting: compares two routerinfos first by address, and then by + * descending order of "usefulness". (An authority is more useful than a + * non-authority; a running router is more useful than a non-running router; + * and a router with more bandwidth is more useful than one with less.) + **/ +static int +compare_routerinfo_by_ip_and_bw_(const void **a, const void **b) +{ + routerinfo_t *first = *(routerinfo_t **)a, *second = *(routerinfo_t **)b; + int first_is_auth, second_is_auth; + uint32_t bw_kb_first, bw_kb_second; + const node_t *node_first, *node_second; + int first_is_running, second_is_running; + + /* we return -1 if first should appear before second... that is, + * if first is a better router. */ + if (first->addr < second->addr) + return -1; + else if (first->addr > second->addr) + return 1; + + /* Potentially, this next bit could cause k n lg n memeq calls. But in + * reality, we will almost never get here, since addresses will usually be + * different. */ + + first_is_auth = + router_digest_is_trusted_dir(first->cache_info.identity_digest); + second_is_auth = + router_digest_is_trusted_dir(second->cache_info.identity_digest); + + if (first_is_auth && !second_is_auth) + return -1; + else if (!first_is_auth && second_is_auth) + return 1; + + node_first = node_get_by_id(first->cache_info.identity_digest); + node_second = node_get_by_id(second->cache_info.identity_digest); + first_is_running = node_first && node_first->is_running; + second_is_running = node_second && node_second->is_running; + + if (first_is_running && !second_is_running) + return -1; + else if (!first_is_running && second_is_running) + return 1; + + bw_kb_first = dirserv_get_bandwidth_for_router_kb(first); + bw_kb_second = dirserv_get_bandwidth_for_router_kb(second); + + if (bw_kb_first > bw_kb_second) + return -1; + else if (bw_kb_first < bw_kb_second) + return 1; + + /* They're equal! Compare by identity digest, so there's a + * deterministic order and we avoid flapping. */ + return fast_memcmp(first->cache_info.identity_digest, + second->cache_info.identity_digest, + DIGEST_LEN); +} + +/** Given a list of routerinfo_t in <b>routers</b>, return a new digestmap_t + * whose keys are the identity digests of those routers that we're going to + * exclude for Sybil-like appearance. */ +static digestmap_t * +get_possible_sybil_list(const smartlist_t *routers) +{ + const or_options_t *options = get_options(); + digestmap_t *omit_as_sybil; + smartlist_t *routers_by_ip = smartlist_new(); + uint32_t last_addr; + int addr_count; + /* Allow at most this number of Tor servers on a single IP address, ... */ + int max_with_same_addr = options->AuthDirMaxServersPerAddr; + if (max_with_same_addr <= 0) + max_with_same_addr = INT_MAX; + + smartlist_add_all(routers_by_ip, routers); + smartlist_sort(routers_by_ip, compare_routerinfo_by_ip_and_bw_); + omit_as_sybil = digestmap_new(); + + last_addr = 0; + addr_count = 0; + SMARTLIST_FOREACH_BEGIN(routers_by_ip, routerinfo_t *, ri) { + if (last_addr != ri->addr) { + last_addr = ri->addr; + addr_count = 1; + } else if (++addr_count > max_with_same_addr) { + digestmap_set(omit_as_sybil, ri->cache_info.identity_digest, ri); + } + } SMARTLIST_FOREACH_END(ri); + + smartlist_free(routers_by_ip); + return omit_as_sybil; +} + +/** Given a platform string as in a routerinfo_t (possibly null), return a + * newly allocated version string for a networkstatus document, or NULL if the + * platform doesn't give a Tor version. */ +static char * +version_from_platform(const char *platform) +{ + if (platform && !strcmpstart(platform, "Tor ")) { + const char *eos = find_whitespace(platform+4); + if (eos && !strcmpstart(eos, " (r")) { + /* XXXX Unify this logic with the other version extraction + * logic in routerparse.c. */ + eos = find_whitespace(eos+1); + } + if (eos) { + return tor_strndup(platform, eos-platform); + } + } + return NULL; +} + +/** Given a (possibly empty) list of config_line_t, each line of which contains + * a list of comma-separated version numbers surrounded by optional space, + * allocate and return a new string containing the version numbers, in order, + * separated by commas. Used to generate Recommended(Client|Server)?Versions + */ +static char * +format_versions_list(config_line_t *ln) +{ + smartlist_t *versions; + char *result; + versions = smartlist_new(); + for ( ; ln; ln = ln->next) { + smartlist_split_string(versions, ln->value, ",", + SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0); + } + sort_version_list(versions, 1); + result = smartlist_join_strings(versions,",",0,NULL); + SMARTLIST_FOREACH(versions,char *,s,tor_free(s)); + smartlist_free(versions); + return result; +} + +/** If there are entries in <b>routers</b> with exactly the same ed25519 keys, + * remove the older one. If they are exactly the same age, remove the one + * with the greater descriptor digest. May alter the order of the list. */ +static void +routers_make_ed_keys_unique(smartlist_t *routers) +{ + routerinfo_t *ri2; + digest256map_t *by_ed_key = digest256map_new(); + + SMARTLIST_FOREACH_BEGIN(routers, routerinfo_t *, ri) { + ri->omit_from_vote = 0; + if (ri->cache_info.signing_key_cert == NULL) + continue; /* No ed key */ + const uint8_t *pk = ri->cache_info.signing_key_cert->signing_key.pubkey; + if ((ri2 = digest256map_get(by_ed_key, pk))) { + /* Duplicate; must omit one. Set the omit_from_vote flag in whichever + * one has the earlier published_on. */ + const time_t ri_pub = ri->cache_info.published_on; + const time_t ri2_pub = ri2->cache_info.published_on; + if (ri2_pub < ri_pub || + (ri2_pub == ri_pub && + fast_memcmp(ri->cache_info.signed_descriptor_digest, + ri2->cache_info.signed_descriptor_digest,DIGEST_LEN)<0)) { + digest256map_set(by_ed_key, pk, ri); + ri2->omit_from_vote = 1; + } else { + ri->omit_from_vote = 1; + } + } else { + /* Add to map */ + digest256map_set(by_ed_key, pk, ri); + } + } SMARTLIST_FOREACH_END(ri); + + digest256map_free(by_ed_key, NULL); + + /* Now remove every router where the omit_from_vote flag got set. */ + SMARTLIST_FOREACH_BEGIN(routers, const routerinfo_t *, ri) { + if (ri->omit_from_vote) { + SMARTLIST_DEL_CURRENT(routers, ri); + } + } SMARTLIST_FOREACH_END(ri); +} + +/** Routerstatus <b>rs</b> is part of a group of routers that are on + * too narrow an IP-space. Clear out its flags since we don't want it be used + * because of its Sybil-like appearance. + * + * Leave its BadExit flag alone though, since if we think it's a bad exit, + * we want to vote that way in case all the other authorities are voting + * Running and Exit. + */ +static void +clear_status_flags_on_sybil(routerstatus_t *rs) +{ + rs->is_authority = rs->is_exit = rs->is_stable = rs->is_fast = + rs->is_flagged_running = rs->is_named = rs->is_valid = + rs->is_hs_dir = rs->is_v2_dir = rs->is_possible_guard = 0; + /* FFFF we might want some mechanism to check later on if we + * missed zeroing any flags: it's easy to add a new flag but + * forget to add it to this clause. */ +} + +/** Return a new networkstatus_t* containing our current opinion. (For v3 + * authorities) */ +networkstatus_t * +dirserv_generate_networkstatus_vote_obj(crypto_pk_t *private_key, + authority_cert_t *cert) +{ + const or_options_t *options = get_options(); + networkstatus_t *v3_out = NULL; + uint32_t addr; + char *hostname = NULL, *client_versions = NULL, *server_versions = NULL; + const char *contact; + smartlist_t *routers, *routerstatuses; + char identity_digest[DIGEST_LEN]; + char signing_key_digest[DIGEST_LEN]; + int listbadexits = options->AuthDirListBadExits; + routerlist_t *rl = router_get_routerlist(); + time_t now = time(NULL); + time_t cutoff = now - ROUTER_MAX_AGE_TO_PUBLISH; + networkstatus_voter_info_t *voter = NULL; + vote_timing_t timing; + digestmap_t *omit_as_sybil = NULL; + const int vote_on_reachability = running_long_enough_to_decide_unreachable(); + smartlist_t *microdescriptors = NULL; + + tor_assert(private_key); + tor_assert(cert); + + if (crypto_pk_get_digest(private_key, signing_key_digest)<0) { + log_err(LD_BUG, "Error computing signing key digest"); + return NULL; + } + if (crypto_pk_get_digest(cert->identity_key, identity_digest)<0) { + log_err(LD_BUG, "Error computing identity key digest"); + return NULL; + } + if (resolve_my_address(LOG_WARN, options, &addr, NULL, &hostname)<0) { + log_warn(LD_NET, "Couldn't resolve my hostname"); + return NULL; + } + if (!hostname || !strchr(hostname, '.')) { + tor_free(hostname); + hostname = tor_dup_ip(addr); + } + + if (options->VersioningAuthoritativeDir) { + client_versions = format_versions_list(options->RecommendedClientVersions); + server_versions = format_versions_list(options->RecommendedServerVersions); + } + + contact = get_options()->ContactInfo; + if (!contact) + contact = "(none)"; + + /* + * Do this so dirserv_compute_performance_thresholds() and + * set_routerstatus_from_routerinfo() see up-to-date bandwidth info. + */ + if (options->V3BandwidthsFile) { + dirserv_read_measured_bandwidths(options->V3BandwidthsFile, NULL); + } else { + /* + * No bandwidths file; clear the measured bandwidth cache in case we had + * one last time around. + */ + if (dirserv_get_measured_bw_cache_size() > 0) { + dirserv_clear_measured_bw_cache(); + } + } + + /* precompute this part, since we need it to decide what "stable" + * means. */ + SMARTLIST_FOREACH(rl->routers, routerinfo_t *, ri, { + dirserv_set_router_is_running(ri, now); + }); + + routers = smartlist_new(); + smartlist_add_all(routers, rl->routers); + routers_make_ed_keys_unique(routers); + /* After this point, don't use rl->routers; use 'routers' instead. */ + routers_sort_by_identity(routers); + omit_as_sybil = get_possible_sybil_list(routers); + + DIGESTMAP_FOREACH(omit_as_sybil, sybil_id, void *, ignore) { + (void) ignore; + rep_hist_make_router_pessimal(sybil_id, now); + } DIGESTMAP_FOREACH_END; + + /* Count how many have measured bandwidths so we know how to assign flags; + * this must come before dirserv_compute_performance_thresholds() */ + dirserv_count_measured_bws(routers); + + dirserv_compute_performance_thresholds(omit_as_sybil); + + routerstatuses = smartlist_new(); + microdescriptors = smartlist_new(); + + SMARTLIST_FOREACH_BEGIN(routers, routerinfo_t *, ri) { + if (ri->cache_info.published_on >= cutoff) { + routerstatus_t *rs; + vote_routerstatus_t *vrs; + node_t *node = node_get_mutable_by_id(ri->cache_info.identity_digest); + if (!node) + continue; + + vrs = tor_malloc_zero(sizeof(vote_routerstatus_t)); + rs = &vrs->status; + set_routerstatus_from_routerinfo(rs, node, ri, now, + listbadexits); + + if (ri->cache_info.signing_key_cert) { + memcpy(vrs->ed25519_id, + ri->cache_info.signing_key_cert->signing_key.pubkey, + ED25519_PUBKEY_LEN); + } + + if (digestmap_get(omit_as_sybil, ri->cache_info.identity_digest)) + clear_status_flags_on_sybil(rs); + + if (!vote_on_reachability) + rs->is_flagged_running = 0; + + vrs->version = version_from_platform(ri->platform); + if (ri->protocol_list) { + vrs->protocols = tor_strdup(ri->protocol_list); + } else { + vrs->protocols = tor_strdup( + protover_compute_for_old_tor(vrs->version)); + } + vrs->microdesc = dirvote_format_all_microdesc_vote_lines(ri, now, + microdescriptors); + + smartlist_add(routerstatuses, vrs); + } + } SMARTLIST_FOREACH_END(ri); + + { + smartlist_t *added = + microdescs_add_list_to_cache(get_microdesc_cache(), + microdescriptors, SAVED_NOWHERE, 0); + smartlist_free(added); + smartlist_free(microdescriptors); + } + + smartlist_free(routers); + digestmap_free(omit_as_sybil, NULL); + + /* Apply guardfraction information to routerstatuses. */ + if (options->GuardfractionFile) { + dirserv_read_guardfraction_file(options->GuardfractionFile, + routerstatuses); + } + + /* This pass through applies the measured bw lines to the routerstatuses */ + if (options->V3BandwidthsFile) { + dirserv_read_measured_bandwidths(options->V3BandwidthsFile, + routerstatuses); + } else { + /* + * No bandwidths file; clear the measured bandwidth cache in case we had + * one last time around. + */ + if (dirserv_get_measured_bw_cache_size() > 0) { + dirserv_clear_measured_bw_cache(); + } + } + + v3_out = tor_malloc_zero(sizeof(networkstatus_t)); + + v3_out->type = NS_TYPE_VOTE; + dirvote_get_preferred_voting_intervals(&timing); + v3_out->published = now; + { + char tbuf[ISO_TIME_LEN+1]; + networkstatus_t *current_consensus = + networkstatus_get_live_consensus(now); + long last_consensus_interval; /* only used to pick a valid_after */ + if (current_consensus) + last_consensus_interval = current_consensus->fresh_until - + current_consensus->valid_after; + else + last_consensus_interval = options->TestingV3AuthInitialVotingInterval; + v3_out->valid_after = + voting_schedule_get_start_of_next_interval(now, + (int)last_consensus_interval, + options->TestingV3AuthVotingStartOffset); + format_iso_time(tbuf, v3_out->valid_after); + log_notice(LD_DIR,"Choosing valid-after time in vote as %s: " + "consensus_set=%d, last_interval=%d", + tbuf, current_consensus?1:0, (int)last_consensus_interval); + } + v3_out->fresh_until = v3_out->valid_after + timing.vote_interval; + v3_out->valid_until = v3_out->valid_after + + (timing.vote_interval * timing.n_intervals_valid); + v3_out->vote_seconds = timing.vote_delay; + v3_out->dist_seconds = timing.dist_delay; + tor_assert(v3_out->vote_seconds > 0); + tor_assert(v3_out->dist_seconds > 0); + tor_assert(timing.n_intervals_valid > 0); + + v3_out->client_versions = client_versions; + v3_out->server_versions = server_versions; + + /* These are hardwired, to avoid disaster. */ + v3_out->recommended_relay_protocols = + tor_strdup("Cons=1-2 Desc=1-2 DirCache=1 HSDir=1 HSIntro=3 HSRend=1 " + "Link=4 LinkAuth=1 Microdesc=1-2 Relay=2"); + v3_out->recommended_client_protocols = + tor_strdup("Cons=1-2 Desc=1-2 DirCache=1 HSDir=1 HSIntro=3 HSRend=1 " + "Link=4 LinkAuth=1 Microdesc=1-2 Relay=2"); + v3_out->required_client_protocols = + tor_strdup("Cons=1-2 Desc=1-2 DirCache=1 HSDir=1 HSIntro=3 HSRend=1 " + "Link=4 LinkAuth=1 Microdesc=1-2 Relay=2"); + v3_out->required_relay_protocols = + tor_strdup("Cons=1 Desc=1 DirCache=1 HSDir=1 HSIntro=3 HSRend=1 " + "Link=3-4 LinkAuth=1 Microdesc=1 Relay=1-2"); + + /* We are not allowed to vote to require anything we don't have. */ + tor_assert(protover_all_supported(v3_out->required_relay_protocols, NULL)); + tor_assert(protover_all_supported(v3_out->required_client_protocols, NULL)); + + /* We should not recommend anything we don't have. */ + tor_assert_nonfatal(protover_all_supported( + v3_out->recommended_relay_protocols, NULL)); + tor_assert_nonfatal(protover_all_supported( + v3_out->recommended_client_protocols, NULL)); + + v3_out->package_lines = smartlist_new(); + { + config_line_t *cl; + for (cl = get_options()->RecommendedPackages; cl; cl = cl->next) { + if (validate_recommended_package_line(cl->value)) + smartlist_add_strdup(v3_out->package_lines, cl->value); + } + } + + v3_out->known_flags = smartlist_new(); + smartlist_split_string(v3_out->known_flags, + "Authority Exit Fast Guard Stable V2Dir Valid HSDir", + 0, SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0); + if (vote_on_reachability) + smartlist_add_strdup(v3_out->known_flags, "Running"); + if (listbadexits) + smartlist_add_strdup(v3_out->known_flags, "BadExit"); + smartlist_sort_strings(v3_out->known_flags); + + if (options->ConsensusParams) { + v3_out->net_params = smartlist_new(); + smartlist_split_string(v3_out->net_params, + options->ConsensusParams, NULL, 0, 0); + smartlist_sort_strings(v3_out->net_params); + } + + voter = tor_malloc_zero(sizeof(networkstatus_voter_info_t)); + voter->nickname = tor_strdup(options->Nickname); + memcpy(voter->identity_digest, identity_digest, DIGEST_LEN); + voter->sigs = smartlist_new(); + voter->address = hostname; + voter->addr = addr; + voter->dir_port = router_get_advertised_dir_port(options, 0); + voter->or_port = router_get_advertised_or_port(options); + voter->contact = tor_strdup(contact); + if (options->V3AuthUseLegacyKey) { + authority_cert_t *c = get_my_v3_legacy_cert(); + if (c) { + if (crypto_pk_get_digest(c->identity_key, voter->legacy_id_digest)) { + log_warn(LD_BUG, "Unable to compute digest of legacy v3 identity key"); + memset(voter->legacy_id_digest, 0, DIGEST_LEN); + } + } + } + + v3_out->voters = smartlist_new(); + smartlist_add(v3_out->voters, voter); + v3_out->cert = authority_cert_dup(cert); + v3_out->routerstatus_list = routerstatuses; + /* Note: networkstatus_digest is unset; it won't get set until we actually + * format the vote. */ + + return v3_out; +} + diff --git a/src/or/dirauth/dirvote.h b/src/or/dirauth/dirvote.h new file mode 100644 index 0000000000..b69bbbf5d9 --- /dev/null +++ b/src/or/dirauth/dirvote.h @@ -0,0 +1,247 @@ +/* Copyright (c) 2001 Matej Pfajfar. + * Copyright (c) 2001-2004, Roger Dingledine. + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2017, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file dirvote.h + * \brief Header file for dirvote.c. + **/ + +#ifndef TOR_DIRVOTE_H +#define TOR_DIRVOTE_H + +/* + * Ideally, assuming synced clocks, we should only need 1 second for each of: + * - Vote + * - Distribute + * - Consensus Publication + * As we can gather descriptors continuously. + * (Could we even go as far as publishing the previous consensus, + * in the same second that we vote for the next one?) + * But we're not there yet: these are the lowest working values at this time. + */ + +/** Lowest allowable value for VoteSeconds. */ +#define MIN_VOTE_SECONDS 2 +/** Lowest allowable value for VoteSeconds when TestingTorNetwork is 1 */ +#define MIN_VOTE_SECONDS_TESTING 2 + +/** Lowest allowable value for DistSeconds. */ +#define MIN_DIST_SECONDS 2 +/** Lowest allowable value for DistSeconds when TestingTorNetwork is 1 */ +#define MIN_DIST_SECONDS_TESTING 2 + +/** Lowest allowable voting interval. */ +#define MIN_VOTE_INTERVAL 300 +/** Lowest allowable voting interval when TestingTorNetwork is 1: + * Voting Interval can be: + * 10, 12, 15, 18, 20, 24, 25, 30, 36, 40, 45, 50, 60, ... + * Testing Initial Voting Interval can be: + * 5, 6, 8, 9, or any of the possible values for Voting Interval, + * as they both need to evenly divide 30 minutes. + * If clock desynchronisation is an issue, use an interval of at least: + * 18 * drift in seconds, to allow for a clock slop factor */ +#define MIN_VOTE_INTERVAL_TESTING \ + (((MIN_VOTE_SECONDS_TESTING)+(MIN_DIST_SECONDS_TESTING)+1)*2) + +#define MIN_VOTE_INTERVAL_TESTING_INITIAL \ + ((MIN_VOTE_SECONDS_TESTING)+(MIN_DIST_SECONDS_TESTING)+1) + +/* A placeholder for routerstatus_format_entry() when the consensus method + * argument is not applicable. */ +#define ROUTERSTATUS_FORMAT_NO_CONSENSUS_METHOD 0 + +/** The lowest consensus method that we currently support. */ +#define MIN_SUPPORTED_CONSENSUS_METHOD 25 + +/** The highest consensus method that we currently support. */ +#define MAX_SUPPORTED_CONSENSUS_METHOD 28 + +/** Lowest consensus method where authorities vote on required/recommended + * protocols. */ +#define MIN_METHOD_FOR_RECOMMENDED_PROTOCOLS 25 + +/** Lowest consensus method where authorities add protocols to routerstatus + * entries. */ +#define MIN_METHOD_FOR_RS_PROTOCOLS 25 + +/** Lowest consensus method where authorities initialize bandwidth weights to 1 + * instead of 0. See #14881 */ +#define MIN_METHOD_FOR_INIT_BW_WEIGHTS_ONE 26 + +/** Lowest consensus method where the microdesc consensus contains relay IPv6 + * addresses. See #23826 and #20916. */ +#define MIN_METHOD_FOR_A_LINES_IN_MICRODESC_CONSENSUS 27 + +/** Lowest consensus method where microdescriptors do not contain relay IPv6 + * addresses. See #23828 and #20916. */ +#define MIN_METHOD_FOR_NO_A_LINES_IN_MICRODESC 28 + +/** 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.) */ +#define DEFAULT_MAX_UNMEASURED_BW_KB 20 + +/* Directory Get Vote (DGV) flags for dirvote_get_vote(). */ +#define DGV_BY_ID 1 +#define DGV_INCLUDE_PENDING 2 +#define DGV_INCLUDE_PREVIOUS 4 + +/* + * Public API. Used outside of the dirauth subsystem. + * + * We need to nullify them if the module is disabled. + */ +#ifdef HAVE_MODULE_DIRAUTH + +time_t dirvote_act(const or_options_t *options, time_t now); +void dirvote_free_all(void); + +void dirvote_parse_sr_commits(networkstatus_t *ns, const smartlist_t *tokens); +void dirvote_clear_commits(networkstatus_t *ns); +void dirvote_dirreq_get_status_vote(const char *url, smartlist_t *items, + smartlist_t *dir_items); + +/* Storing signatures and votes functions */ +struct pending_vote_t * dirvote_add_vote(const char *vote_body, + const char **msg_out, + int *status_out); +int dirvote_add_signatures(const char *detached_signatures_body, + const char *source, + const char **msg_out); + +#else /* HAVE_MODULE_DIRAUTH */ + +static inline time_t +dirvote_act(const or_options_t *options, time_t now) +{ + (void) options; + (void) now; + return TIME_MAX; +} + +static inline void +dirvote_free_all(void) +{ +} + +static inline void +dirvote_parse_sr_commits(networkstatus_t *ns, const smartlist_t *tokens) +{ + (void) ns; + (void) tokens; +} + +static inline void +dirvote_clear_commits(networkstatus_t *ns) +{ + (void) ns; +} + +static inline void +dirvote_dirreq_get_status_vote(const char *url, smartlist_t *items, + smartlist_t *dir_items) +{ + (void) url; + (void) items; + (void) dir_items; +} + +static inline struct pending_vote_t * +dirvote_add_vote(const char *vote_body, const char **msg_out, int *status_out) +{ + (void) vote_body; + /* If the dirauth module is disabled, this should NEVER be called else we + * failed to safeguard the dirauth module. */ + tor_assert_nonfatal_unreached(); + + /* We need to send out an error code. */ + *status_out = 400; + *msg_out = "No directory authority support"; + return NULL; +} + +static inline int +dirvote_add_signatures(const char *detached_signatures_body, const char *source, + const char **msg_out) +{ + (void) detached_signatures_body; + (void) source; + (void) msg_out; + /* If the dirauth module is disabled, this should NEVER be called else we + * failed to safeguard the dirauth module. */ + tor_assert_nonfatal_unreached(); + return 0; +} + +#endif /* HAVE_MODULE_DIRAUTH */ + +/* Item access */ +MOCK_DECL(const char*, dirvote_get_pending_consensus, + (consensus_flavor_t flav)); +MOCK_DECL(const char*, dirvote_get_pending_detached_signatures, (void)); +const cached_dir_t *dirvote_get_vote(const char *fp, int flags); + +/* + * API used _only_ by the dirauth subsystem. + */ + +void set_routerstatus_from_routerinfo(routerstatus_t *rs, + node_t *node, + routerinfo_t *ri, time_t now, + int listbadexits); +networkstatus_t * +dirserv_generate_networkstatus_vote_obj(crypto_pk_t *private_key, + authority_cert_t *cert); + +vote_microdesc_hash_t *dirvote_format_all_microdesc_vote_lines( + const routerinfo_t *ri, + time_t now, + smartlist_t *microdescriptors_out); + +/* + * Exposed functions for unit tests. + */ +#ifdef DIRVOTE_PRIVATE + +/* Cert manipulation */ +STATIC authority_cert_t *authority_cert_dup(authority_cert_t *cert); +STATIC int32_t dirvote_get_intermediate_param_value( + const smartlist_t *param_list, + const char *keyword, + int32_t default_val); +STATIC char *format_networkstatus_vote(crypto_pk_t *private_key, + networkstatus_t *v3_ns); +STATIC smartlist_t *dirvote_compute_params(smartlist_t *votes, int method, + int total_authorities); +STATIC char *compute_consensus_package_lines(smartlist_t *votes); +STATIC char *make_consensus_method_list(int low, int high, const char *sep); +STATIC int +networkstatus_compute_bw_weights_v10(smartlist_t *chunks, int64_t G, + int64_t M, int64_t E, int64_t D, + int64_t T, int64_t weight_scale); +STATIC +char *networkstatus_compute_consensus(smartlist_t *votes, + int total_authorities, + crypto_pk_t *identity_key, + crypto_pk_t *signing_key, + const char *legacy_identity_key_digest, + crypto_pk_t *legacy_signing_key, + consensus_flavor_t flavor); +STATIC +int networkstatus_add_detached_signatures(networkstatus_t *target, + ns_detached_signatures_t *sigs, + const char *source, + int severity, + const char **msg_out); +STATIC +char *networkstatus_get_detached_signatures(smartlist_t *consensuses); +STATIC microdesc_t *dirvote_create_microdescriptor(const routerinfo_t *ri, + int consensus_method); + +#endif /* defined(DIRVOTE_PRIVATE) */ + +#endif /* !defined(TOR_DIRVOTE_H) */ + diff --git a/src/or/dirauth/mode.h b/src/or/dirauth/mode.h new file mode 100644 index 0000000000..8a0d3142f1 --- /dev/null +++ b/src/or/dirauth/mode.h @@ -0,0 +1,38 @@ +/* Copyright (c) 2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file mode.h + * \brief Standalone header file for directory authority mode. + **/ + +#ifndef TOR_DIRAUTH_MODE_H +#define TOR_DIRAUTH_MODE_H + +#ifdef HAVE_MODULE_DIRAUTH + +#include "router.h" + +/* Return true iff we believe ourselves to be a v3 authoritative directory + * server. */ +static inline int +authdir_mode_v3(const or_options_t *options) +{ + return authdir_mode(options) && options->V3AuthoritativeDir != 0; +} + +#else /* HAVE_MODULE_DIRAUTH */ + +/* Without the dirauth module, we can't be a v3 directory authority, ever. */ + +static inline int +authdir_mode_v3(const or_options_t *options) +{ + (void) options; + return 0; +} + +#endif /* HAVE_MODULE_DIRAUTH */ + +#endif /* TOR_MODE_H */ + diff --git a/src/or/dirauth/shared_random.c b/src/or/dirauth/shared_random.c new file mode 100644 index 0000000000..6dd1f330e0 --- /dev/null +++ b/src/or/dirauth/shared_random.c @@ -0,0 +1,1289 @@ +/* Copyright (c) 2016-2017, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file shared_random.c + * + * \brief Functions and data structure needed to accomplish the shared + * random protocol as defined in proposal #250. + * + * \details + * + * This file implements the dirauth-only commit-and-reveal protocol specified + * by proposal #250. The protocol has two phases (sr_phase_t): the commitment + * phase and the reveal phase (see get_sr_protocol_phase()). + * + * During the protocol, directory authorities keep state in memory (using + * sr_state_t) and in disk (using sr_disk_state_t). The synchronization between + * these two data structures happens in disk_state_update() and + * disk_state_parse(). + * + * Here is a rough protocol outline: + * + * 1) In the beginning of the commitment phase, dirauths generate a + * commitment/reveal value for the current protocol run (see + * new_protocol_run() and sr_generate_our_commit()). + * + * 2) During voting, dirauths publish their commits in their votes + * depending on the current phase. Dirauths also include the two + * latest shared random values (SRV) in their votes. + * (see sr_get_string_for_vote()) + * + * 3) Upon receiving a commit from a vote, authorities parse it, verify + * it, and attempt to save any new commitment or reveal information in + * their state file (see extract_shared_random_commits() and + * sr_handle_received_commits()). They also parse SRVs from votes to + * decide which SRV should be included in the final consensus (see + * extract_shared_random_srvs()). + * + * 3) After voting is done, we count the SRVs we extracted from the votes, + * to find the one voted by the majority of dirauths which should be + * included in the final consensus (see get_majority_srv_from_votes()). + * If an appropriate SRV is found, it is embedded in the consensus (see + * sr_get_string_for_consensus()). + * + * 4) At the end of the reveal phase, dirauths compute a fresh SRV for the + * day using the active commits (see sr_compute_srv()). This new SRV + * is embedded in the votes as described above. + * + * Some more notes: + * + * - To support rebooting authorities and to avoid double voting, each dirauth + * saves the current state of the protocol on disk so that it can resume + * normally in case of reboot. The disk state (sr_disk_state_t) is managed by + * shared_random_state.c:state_query() and we go to extra lengths to ensure + * that the state is flushed on disk everytime we receive any useful + * information like commits or SRVs. + * + * - When we receive a commit from a vote, we examine it to see if it's useful + * to us and whether it's appropriate to receive it according to the current + * phase of the protocol (see should_keep_commit()). If the commit is useful + * to us, we save it in our disk state using save_commit_to_state(). When we + * receive the reveal information corresponding to a commitment, we verify + * that they indeed match using verify_commit_and_reveal(). + * + * - We treat consensuses as the ground truth, so everytime we generate a new + * consensus we update our SR state accordingly even if our local view was + * different (see sr_act_post_consensus()). + * + * - After a consensus has been composed, the SR protocol state gets prepared + * for the next voting session using sr_state_update(). That function takes + * care of housekeeping and also rotates the SRVs and commits in case a new + * protocol run is coming up. We also call sr_state_update() on bootup (in + * sr_state_init()), to prepare the state for the very first voting session. + * + * Terminology: + * + * - "Commitment" is the commitment value of the commit-and-reveal protocol. + * + * - "Reveal" is the reveal value of the commit-and-reveal protocol. + * + * - "Commit" is a struct (sr_commit_t) that contains a commitment value and + * optionally also a corresponding reveal value. + * + * - "SRV" is the Shared Random Value that gets generated as the result of the + * commit-and-reveal protocol. + **/ + +#define SHARED_RANDOM_PRIVATE + +#include "or.h" +#include "shared_random.h" +#include "config.h" +#include "confparse.h" +#include "crypto_rand.h" +#include "crypto_util.h" +#include "networkstatus.h" +#include "router.h" +#include "routerkeys.h" +#include "routerlist.h" +#include "shared_random_client.h" +#include "shared_random_state.h" +#include "util.h" +#include "voting_schedule.h" + +#include "dirauth/dirvote.h" +#include "dirauth/mode.h" + +/* String prefix of shared random values in votes/consensuses. */ +static const char previous_srv_str[] = "shared-rand-previous-value"; +static const char current_srv_str[] = "shared-rand-current-value"; +static const char commit_ns_str[] = "shared-rand-commit"; +static const char sr_flag_ns_str[] = "shared-rand-participate"; + +/* The value of the consensus param AuthDirNumSRVAgreements found in the + * vote. This is set once the consensus creation subsystem requests the + * SRV(s) that should be put in the consensus. We use this value to decide + * if we keep or not an SRV. */ +static int32_t num_srv_agreements_from_vote; + +/* Return a heap allocated copy of the SRV <b>orig</b>. */ +STATIC sr_srv_t * +srv_dup(const sr_srv_t *orig) +{ + sr_srv_t *duplicate = NULL; + + if (!orig) { + return NULL; + } + + duplicate = tor_malloc_zero(sizeof(sr_srv_t)); + duplicate->num_reveals = orig->num_reveals; + memcpy(duplicate->value, orig->value, sizeof(duplicate->value)); + return duplicate; +} + +/* Allocate a new commit object and initializing it with <b>rsa_identity</b> + * that MUST be provided. The digest algorithm is set to the default one + * that is supported. The rest is uninitialized. This never returns NULL. */ +static sr_commit_t * +commit_new(const char *rsa_identity) +{ + sr_commit_t *commit; + + tor_assert(rsa_identity); + + commit = tor_malloc_zero(sizeof(*commit)); + commit->alg = SR_DIGEST_ALG; + memcpy(commit->rsa_identity, rsa_identity, sizeof(commit->rsa_identity)); + base16_encode(commit->rsa_identity_hex, sizeof(commit->rsa_identity_hex), + commit->rsa_identity, sizeof(commit->rsa_identity)); + return commit; +} + +/* Issue a log message describing <b>commit</b>. */ +static void +commit_log(const sr_commit_t *commit) +{ + tor_assert(commit); + + log_debug(LD_DIR, "SR: Commit from %s", sr_commit_get_rsa_fpr(commit)); + log_debug(LD_DIR, "SR: Commit: [TS: %" PRIu64 "] [Encoded: %s]", + commit->commit_ts, commit->encoded_commit); + log_debug(LD_DIR, "SR: Reveal: [TS: %" PRIu64 "] [Encoded: %s]", + commit->reveal_ts, safe_str(commit->encoded_reveal)); +} + +/* Make sure that the commitment and reveal information in <b>commit</b> + * match. If they match return 0, return -1 otherwise. This function MUST be + * used everytime we receive a new reveal value. Furthermore, the commit + * object MUST have a reveal value and the hash of the reveal value. */ +STATIC int +verify_commit_and_reveal(const sr_commit_t *commit) +{ + tor_assert(commit); + + log_debug(LD_DIR, "SR: Validating commit from authority %s", + sr_commit_get_rsa_fpr(commit)); + + /* Check that the timestamps match. */ + if (commit->commit_ts != commit->reveal_ts) { + log_warn(LD_BUG, "SR: Commit timestamp %" PRIu64 " doesn't match reveal " + "timestamp %" PRIu64, commit->commit_ts, + commit->reveal_ts); + goto invalid; + } + + /* Verify that the hashed_reveal received in the COMMIT message, matches + * the reveal we just received. */ + { + /* We first hash the reveal we just received. */ + char received_hashed_reveal[sizeof(commit->hashed_reveal)]; + + /* Only sha3-256 is supported. */ + if (commit->alg != SR_DIGEST_ALG) { + goto invalid; + } + + /* Use the invariant length since the encoded reveal variable has an + * extra byte for the NUL terminated byte. */ + if (crypto_digest256(received_hashed_reveal, commit->encoded_reveal, + SR_REVEAL_BASE64_LEN, commit->alg) < 0) { + /* Unable to digest the reveal blob, this is unlikely. */ + goto invalid; + } + + /* Now compare that with the hashed_reveal we received in COMMIT. */ + if (fast_memneq(received_hashed_reveal, commit->hashed_reveal, + sizeof(received_hashed_reveal))) { + log_warn(LD_BUG, "SR: Received reveal value from authority %s " + "doesn't match the commit value.", + sr_commit_get_rsa_fpr(commit)); + goto invalid; + } + } + + return 0; + invalid: + return -1; +} + +/* Return true iff the commit contains an encoded reveal value. */ +STATIC int +commit_has_reveal_value(const sr_commit_t *commit) +{ + return !tor_mem_is_zero(commit->encoded_reveal, + sizeof(commit->encoded_reveal)); +} + +/* Parse the encoded commit. The format is: + * base64-encode( TIMESTAMP || H(REVEAL) ) + * + * If successfully decoded and parsed, commit is updated and 0 is returned. + * On error, return -1. */ +STATIC int +commit_decode(const char *encoded, sr_commit_t *commit) +{ + int decoded_len = 0; + size_t offset = 0; + char b64_decoded[SR_COMMIT_LEN]; + + tor_assert(encoded); + tor_assert(commit); + + if (strlen(encoded) > SR_COMMIT_BASE64_LEN) { + /* This means that if we base64 decode successfully the reveiced commit, + * we'll end up with a bigger decoded commit thus unusable. */ + goto error; + } + + /* Decode our encoded commit. Let's be careful here since _encoded_ is + * coming from the network in a dirauth vote so we expect nothing more + * than the base64 encoded length of a commit. */ + decoded_len = base64_decode(b64_decoded, sizeof(b64_decoded), + encoded, strlen(encoded)); + if (decoded_len < 0) { + log_warn(LD_BUG, "SR: Commit from authority %s can't be decoded.", + sr_commit_get_rsa_fpr(commit)); + goto error; + } + + if (decoded_len != SR_COMMIT_LEN) { + log_warn(LD_BUG, "SR: Commit from authority %s decoded length doesn't " + "match the expected length (%d vs %u).", + sr_commit_get_rsa_fpr(commit), decoded_len, + (unsigned)SR_COMMIT_LEN); + goto error; + } + + /* First is the timestamp (8 bytes). */ + commit->commit_ts = tor_ntohll(get_uint64(b64_decoded)); + offset += sizeof(uint64_t); + /* Next is hashed reveal. */ + memcpy(commit->hashed_reveal, b64_decoded + offset, + sizeof(commit->hashed_reveal)); + /* Copy the base64 blob to the commit. Useful for voting. */ + strlcpy(commit->encoded_commit, encoded, sizeof(commit->encoded_commit)); + + return 0; + + error: + return -1; +} + +/* Parse the b64 blob at <b>encoded</b> containing reveal information and + * store the information in-place in <b>commit</b>. Return 0 on success else + * a negative value. */ +STATIC int +reveal_decode(const char *encoded, sr_commit_t *commit) +{ + int decoded_len = 0; + char b64_decoded[SR_REVEAL_LEN]; + + tor_assert(encoded); + tor_assert(commit); + + if (strlen(encoded) > SR_REVEAL_BASE64_LEN) { + /* This means that if we base64 decode successfully the received reveal + * value, we'll end up with a bigger decoded value thus unusable. */ + goto error; + } + + /* Decode our encoded reveal. Let's be careful here since _encoded_ is + * coming from the network in a dirauth vote so we expect nothing more + * than the base64 encoded length of our reveal. */ + decoded_len = base64_decode(b64_decoded, sizeof(b64_decoded), + encoded, strlen(encoded)); + if (decoded_len < 0) { + log_warn(LD_BUG, "SR: Reveal from authority %s can't be decoded.", + sr_commit_get_rsa_fpr(commit)); + goto error; + } + + if (decoded_len != SR_REVEAL_LEN) { + log_warn(LD_BUG, "SR: Reveal from authority %s decoded length is " + "doesn't match the expected length (%d vs %u)", + sr_commit_get_rsa_fpr(commit), decoded_len, + (unsigned)SR_REVEAL_LEN); + goto error; + } + + commit->reveal_ts = tor_ntohll(get_uint64(b64_decoded)); + /* Copy the last part, the random value. */ + memcpy(commit->random_number, b64_decoded + 8, + sizeof(commit->random_number)); + /* Also copy the whole message to use during verification */ + strlcpy(commit->encoded_reveal, encoded, sizeof(commit->encoded_reveal)); + + return 0; + + error: + return -1; +} + +/* Encode a reveal element using a given commit object to dst which is a + * buffer large enough to put the base64-encoded reveal construction. The + * format is as follow: + * REVEAL = base64-encode( TIMESTAMP || H(RN) ) + * Return base64 encoded length on success else a negative value. + */ +STATIC int +reveal_encode(const sr_commit_t *commit, char *dst, size_t len) +{ + int ret; + size_t offset = 0; + char buf[SR_REVEAL_LEN] = {0}; + + tor_assert(commit); + tor_assert(dst); + + set_uint64(buf, tor_htonll(commit->reveal_ts)); + offset += sizeof(uint64_t); + memcpy(buf + offset, commit->random_number, + sizeof(commit->random_number)); + + /* Let's clean the buffer and then b64 encode it. */ + memset(dst, 0, len); + ret = base64_encode(dst, len, buf, sizeof(buf), 0); + /* Wipe this buffer because it contains our random value. */ + memwipe(buf, 0, sizeof(buf)); + return ret; +} + +/* Encode the given commit object to dst which is a buffer large enough to + * put the base64-encoded commit. The format is as follow: + * COMMIT = base64-encode( TIMESTAMP || H(H(RN)) ) + * Return base64 encoded length on success else a negative value. + */ +STATIC int +commit_encode(const sr_commit_t *commit, char *dst, size_t len) +{ + size_t offset = 0; + char buf[SR_COMMIT_LEN] = {0}; + + tor_assert(commit); + tor_assert(dst); + + /* First is the timestamp (8 bytes). */ + set_uint64(buf, tor_htonll(commit->commit_ts)); + offset += sizeof(uint64_t); + /* and then the hashed reveal. */ + memcpy(buf + offset, commit->hashed_reveal, + sizeof(commit->hashed_reveal)); + + /* Clean the buffer and then b64 encode it. */ + memset(dst, 0, len); + return base64_encode(dst, len, buf, sizeof(buf), 0); +} + +/* Cleanup both our global state and disk state. */ +static void +sr_cleanup(void) +{ + sr_state_free_all(); +} + +/* Using <b>commit</b>, return a newly allocated string containing the commit + * information that should be used during SRV calculation. It's the caller + * responsibility to free the memory. Return NULL if this is not a commit to be + * used for SRV calculation. */ +static char * +get_srv_element_from_commit(const sr_commit_t *commit) +{ + char *element; + tor_assert(commit); + + if (!commit_has_reveal_value(commit)) { + return NULL; + } + + tor_asprintf(&element, "%s%s", sr_commit_get_rsa_fpr(commit), + commit->encoded_reveal); + return element; +} + +/* Return a srv object that is built with the construction: + * SRV = SHA3-256("shared-random" | INT_8(reveal_num) | + * INT_4(version) | HASHED_REVEALS | previous_SRV) + * This function cannot fail. */ +static sr_srv_t * +generate_srv(const char *hashed_reveals, uint64_t reveal_num, + const sr_srv_t *previous_srv) +{ + char msg[DIGEST256_LEN + SR_SRV_MSG_LEN] = {0}; + size_t offset = 0; + sr_srv_t *srv; + + tor_assert(hashed_reveals); + + /* Add the invariant token. */ + memcpy(msg, SR_SRV_TOKEN, SR_SRV_TOKEN_LEN); + offset += SR_SRV_TOKEN_LEN; + set_uint64(msg + offset, tor_htonll(reveal_num)); + offset += sizeof(uint64_t); + set_uint32(msg + offset, htonl(SR_PROTO_VERSION)); + offset += sizeof(uint32_t); + memcpy(msg + offset, hashed_reveals, DIGEST256_LEN); + offset += DIGEST256_LEN; + if (previous_srv != NULL) { + memcpy(msg + offset, previous_srv->value, sizeof(previous_srv->value)); + } + + /* Ok we have our message and key for the HMAC computation, allocate our + * srv object and do the last step. */ + srv = tor_malloc_zero(sizeof(*srv)); + crypto_digest256((char *) srv->value, msg, sizeof(msg), SR_DIGEST_ALG); + srv->num_reveals = reveal_num; + + { + /* Debugging. */ + char srv_hash_encoded[SR_SRV_VALUE_BASE64_LEN + 1]; + sr_srv_encode(srv_hash_encoded, sizeof(srv_hash_encoded), srv); + log_info(LD_DIR, "SR: Generated SRV: %s", srv_hash_encoded); + } + return srv; +} + +/* Compare reveal values and return the result. This should exclusively be + * used by smartlist_sort(). */ +static int +compare_reveal_(const void **_a, const void **_b) +{ + const sr_commit_t *a = *_a, *b = *_b; + return fast_memcmp(a->hashed_reveal, b->hashed_reveal, + sizeof(a->hashed_reveal)); +} + +/* Given <b>commit</b> give the line that we should place in our votes. + * It's the responsibility of the caller to free the string. */ +static char * +get_vote_line_from_commit(const sr_commit_t *commit, sr_phase_t phase) +{ + char *vote_line = NULL; + + switch (phase) { + case SR_PHASE_COMMIT: + tor_asprintf(&vote_line, "%s %u %s %s %s\n", + commit_ns_str, + SR_PROTO_VERSION, + crypto_digest_algorithm_get_name(commit->alg), + sr_commit_get_rsa_fpr(commit), + commit->encoded_commit); + break; + case SR_PHASE_REVEAL: + { + /* Send a reveal value for this commit if we have one. */ + const char *reveal_str = commit->encoded_reveal; + if (tor_mem_is_zero(commit->encoded_reveal, + sizeof(commit->encoded_reveal))) { + reveal_str = ""; + } + tor_asprintf(&vote_line, "%s %u %s %s %s %s\n", + commit_ns_str, + SR_PROTO_VERSION, + crypto_digest_algorithm_get_name(commit->alg), + sr_commit_get_rsa_fpr(commit), + commit->encoded_commit, reveal_str); + break; + } + default: + tor_assert(0); + } + + log_debug(LD_DIR, "SR: Commit vote line: %s", vote_line); + return vote_line; +} + +/* Return a heap allocated string that contains the given <b>srv</b> string + * representation formatted for a networkstatus document using the + * <b>key</b> as the start of the line. This doesn't return NULL. */ +static char * +srv_to_ns_string(const sr_srv_t *srv, const char *key) +{ + char *srv_str; + char srv_hash_encoded[SR_SRV_VALUE_BASE64_LEN + 1]; + tor_assert(srv); + tor_assert(key); + + sr_srv_encode(srv_hash_encoded, sizeof(srv_hash_encoded), srv); + tor_asprintf(&srv_str, "%s %" PRIu64 " %s\n", key, + srv->num_reveals, srv_hash_encoded); + log_debug(LD_DIR, "SR: Consensus SRV line: %s", srv_str); + return srv_str; +} + +/* Given the previous SRV and the current SRV, return a heap allocated + * string with their data that could be put in a vote or a consensus. Caller + * must free the returned string. Return NULL if no SRVs were provided. */ +static char * +get_ns_str_from_sr_values(const sr_srv_t *prev_srv, const sr_srv_t *cur_srv) +{ + smartlist_t *chunks = NULL; + char *srv_str; + + if (!prev_srv && !cur_srv) { + return NULL; + } + + chunks = smartlist_new(); + + if (prev_srv) { + char *srv_line = srv_to_ns_string(prev_srv, previous_srv_str); + smartlist_add(chunks, srv_line); + } + + if (cur_srv) { + char *srv_line = srv_to_ns_string(cur_srv, current_srv_str); + smartlist_add(chunks, srv_line); + } + + /* Join the line(s) here in one string to return. */ + srv_str = smartlist_join_strings(chunks, "", 0, NULL); + SMARTLIST_FOREACH(chunks, char *, s, tor_free(s)); + smartlist_free(chunks); + + return srv_str; +} + +/* Return 1 iff the two commits have the same commitment values. This + * function does not care about reveal values. */ +STATIC int +commitments_are_the_same(const sr_commit_t *commit_one, + const sr_commit_t *commit_two) +{ + tor_assert(commit_one); + tor_assert(commit_two); + + if (strcmp(commit_one->encoded_commit, commit_two->encoded_commit)) { + return 0; + } + return 1; +} + +/* We just received a commit from the vote of authority with + * <b>identity_digest</b>. Return 1 if this commit is authorititative that + * is, it belongs to the authority that voted it. Else return 0 if not. */ +STATIC int +commit_is_authoritative(const sr_commit_t *commit, + const char *voter_key) +{ + tor_assert(commit); + tor_assert(voter_key); + + return fast_memeq(commit->rsa_identity, voter_key, + sizeof(commit->rsa_identity)); +} + +/* Decide if the newly received <b>commit</b> should be kept depending on + * the current phase and state of the protocol. The <b>voter_key</b> is the + * RSA identity key fingerprint of the authority's vote from which the + * commit comes from. The <b>phase</b> is the phase we should be validating + * the commit for. Return 1 if the commit should be added to our state or 0 + * if not. */ +STATIC int +should_keep_commit(const sr_commit_t *commit, const char *voter_key, + sr_phase_t phase) +{ + const sr_commit_t *saved_commit; + + tor_assert(commit); + tor_assert(voter_key); + + log_debug(LD_DIR, "SR: Inspecting commit from %s (voter: %s)?", + sr_commit_get_rsa_fpr(commit), + hex_str(voter_key, DIGEST_LEN)); + + /* For a commit to be considered, it needs to be authoritative (it should + * be the voter's own commit). */ + if (!commit_is_authoritative(commit, voter_key)) { + log_debug(LD_DIR, "SR: Ignoring non-authoritative commit."); + goto ignore; + } + + /* Let's make sure, for extra safety, that this fingerprint is known to + * us. Even though this comes from a vote, doesn't hurt to be + * extracareful. */ + if (trusteddirserver_get_by_v3_auth_digest(commit->rsa_identity) == NULL) { + log_warn(LD_DIR, "SR: Fingerprint %s is not from a recognized " + "authority. Discarding commit.", + escaped(commit->rsa_identity)); + goto ignore; + } + + /* Check if the authority that voted for <b>commit</b> has already posted + * a commit before. */ + saved_commit = sr_state_get_commit(commit->rsa_identity); + + switch (phase) { + case SR_PHASE_COMMIT: + /* Already having a commit for an authority so ignore this one. */ + if (saved_commit) { + /* Receiving known commits should happen naturally since commit phase + lasts multiple rounds. However if the commitment value changes + during commit phase, it might be a bug so log more loudly. */ + if (!commitments_are_the_same(commit, saved_commit)) { + log_info(LD_DIR, + "SR: Received altered commit from %s in commit phase.", + sr_commit_get_rsa_fpr(commit)); + } else { + log_debug(LD_DIR, "SR: Ignoring known commit during commit phase."); + } + goto ignore; + } + + /* A commit with a reveal value during commitment phase is very wrong. */ + if (commit_has_reveal_value(commit)) { + log_warn(LD_DIR, "SR: Commit from authority %s has a reveal value " + "during COMMIT phase. (voter: %s)", + sr_commit_get_rsa_fpr(commit), + hex_str(voter_key, DIGEST_LEN)); + goto ignore; + } + break; + case SR_PHASE_REVEAL: + /* We are now in reveal phase. We keep a commit if and only if: + * + * - We have already seen a commit by this auth, AND + * - the saved commit has the same commitment value as this one, AND + * - the saved commit has no reveal information, AND + * - this commit does have reveal information, AND + * - the reveal & commit information are matching. + * + * If all the above are true, then we are interested in this new commit + * for its reveal information. */ + + if (!saved_commit) { + log_debug(LD_DIR, "SR: Ignoring commit first seen in reveal phase."); + goto ignore; + } + + if (!commitments_are_the_same(commit, saved_commit)) { + log_warn(LD_DIR, "SR: Commit from authority %s is different from " + "previous commit in our state (voter: %s)", + sr_commit_get_rsa_fpr(commit), + hex_str(voter_key, DIGEST_LEN)); + goto ignore; + } + + if (commit_has_reveal_value(saved_commit)) { + log_debug(LD_DIR, "SR: Ignoring commit with known reveal info."); + goto ignore; + } + + if (!commit_has_reveal_value(commit)) { + log_debug(LD_DIR, "SR: Ignoring commit without reveal value."); + goto ignore; + } + + if (verify_commit_and_reveal(commit) < 0) { + log_warn(LD_BUG, "SR: Commit from authority %s has an invalid " + "reveal value. (voter: %s)", + sr_commit_get_rsa_fpr(commit), + hex_str(voter_key, DIGEST_LEN)); + goto ignore; + } + break; + default: + tor_assert(0); + } + + return 1; + + ignore: + return 0; +} + +/* We are in reveal phase and we found a valid and verified <b>commit</b> in + * a vote that contains reveal values that we could use. Update the commit + * we have in our state. Never call this with an unverified commit. */ +STATIC void +save_commit_during_reveal_phase(const sr_commit_t *commit) +{ + sr_commit_t *saved_commit; + + tor_assert(commit); + + /* Get the commit from our state. */ + saved_commit = sr_state_get_commit(commit->rsa_identity); + tor_assert(saved_commit); + /* Safety net. They can not be different commitments at this point. */ + int same_commits = commitments_are_the_same(commit, saved_commit); + tor_assert(same_commits); + + /* Copy reveal information to our saved commit. */ + sr_state_copy_reveal_info(saved_commit, commit); +} + +/* Save <b>commit</b> to our persistent state. Depending on the current + * phase, different actions are taken. Steals reference of <b>commit</b>. + * The commit object MUST be valid and verified before adding it to the + * state. */ +STATIC void +save_commit_to_state(sr_commit_t *commit) +{ + sr_phase_t phase = sr_state_get_phase(); + + ASSERT_COMMIT_VALID(commit); + + switch (phase) { + case SR_PHASE_COMMIT: + /* During commit phase, just save any new authoritative commit */ + sr_state_add_commit(commit); + break; + case SR_PHASE_REVEAL: + save_commit_during_reveal_phase(commit); + sr_commit_free(commit); + break; + default: + tor_assert(0); + } +} + +/* Return 1 if we should we keep an SRV voted by <b>n_agreements</b> auths. + * Return 0 if we should ignore it. */ +static int +should_keep_srv(int n_agreements) +{ + /* Check if the most popular SRV has reached majority. */ + int n_voters = get_n_authorities(V3_DIRINFO); + int votes_required_for_majority = (n_voters / 2) + 1; + + /* We need at the very least majority to keep a value. */ + if (n_agreements < votes_required_for_majority) { + log_notice(LD_DIR, "SR: SRV didn't reach majority [%d/%d]!", + n_agreements, votes_required_for_majority); + return 0; + } + + /* When we just computed a new SRV, we need to have super majority in order + * to keep it. */ + if (sr_state_srv_is_fresh()) { + /* Check if we have super majority for this new SRV value. */ + if (n_agreements < num_srv_agreements_from_vote) { + log_notice(LD_DIR, "SR: New SRV didn't reach agreement [%d/%d]!", + n_agreements, num_srv_agreements_from_vote); + return 0; + } + } + + return 1; +} + +/* Helper: compare two DIGEST256_LEN digests. */ +static int +compare_srvs_(const void **_a, const void **_b) +{ + const sr_srv_t *a = *_a, *b = *_b; + return tor_memcmp(a->value, b->value, sizeof(a->value)); +} + +/* Return the most frequent member of the sorted list of DIGEST256_LEN + * digests in <b>sl</b> with the count of that most frequent element. */ +static sr_srv_t * +smartlist_get_most_frequent_srv(const smartlist_t *sl, int *count_out) +{ + return smartlist_get_most_frequent_(sl, compare_srvs_, count_out); +} + +/** Compare two SRVs. Used in smartlist sorting. */ +static int +compare_srv_(const void **_a, const void **_b) +{ + const sr_srv_t *a = *_a, *b = *_b; + return fast_memcmp(a->value, b->value, + sizeof(a->value)); +} + +/* Using a list of <b>votes</b>, return the SRV object from them that has + * been voted by the majority of dirauths. If <b>current</b> is set, we look + * for the current SRV value else the previous one. The returned pointer is + * an object located inside a vote. NULL is returned if no appropriate value + * could be found. */ +STATIC sr_srv_t * +get_majority_srv_from_votes(const smartlist_t *votes, int current) +{ + int count = 0; + sr_srv_t *most_frequent_srv = NULL; + sr_srv_t *the_srv = NULL; + smartlist_t *srv_list; + + tor_assert(votes); + + srv_list = smartlist_new(); + + /* Walk over votes and register any SRVs found. */ + SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) { + sr_srv_t *srv_tmp = NULL; + + if (!v->sr_info.participate) { + /* Ignore vote that do not participate. */ + continue; + } + /* Do we want previous or current SRV? */ + srv_tmp = current ? v->sr_info.current_srv : v->sr_info.previous_srv; + if (!srv_tmp) { + continue; + } + + smartlist_add(srv_list, srv_tmp); + } SMARTLIST_FOREACH_END(v); + + smartlist_sort(srv_list, compare_srv_); + most_frequent_srv = smartlist_get_most_frequent_srv(srv_list, &count); + if (!most_frequent_srv) { + goto end; + } + + /* Was this SRV voted by enough auths for us to keep it? */ + if (!should_keep_srv(count)) { + goto end; + } + + /* We found an SRV that we can use! Habemus SRV! */ + the_srv = most_frequent_srv; + + { + /* Debugging */ + char encoded[SR_SRV_VALUE_BASE64_LEN + 1]; + sr_srv_encode(encoded, sizeof(encoded), the_srv); + log_debug(LD_DIR, "SR: Chosen SRV by majority: %s (%d votes)", encoded, + count); + } + + end: + /* We do not free any sr_srv_t values, we don't have the ownership. */ + smartlist_free(srv_list); + return the_srv; +} + +/* Free a commit object. */ +void +sr_commit_free_(sr_commit_t *commit) +{ + if (commit == NULL) { + return; + } + /* Make sure we do not leave OUR random number in memory. */ + memwipe(commit->random_number, 0, sizeof(commit->random_number)); + tor_free(commit); +} + +/* Generate the commitment/reveal value for the protocol run starting at + * <b>timestamp</b>. <b>my_rsa_cert</b> is our authority RSA certificate. */ +sr_commit_t * +sr_generate_our_commit(time_t timestamp, const authority_cert_t *my_rsa_cert) +{ + sr_commit_t *commit = NULL; + char digest[DIGEST_LEN]; + + tor_assert(my_rsa_cert); + + /* Get our RSA identity fingerprint */ + if (crypto_pk_get_digest(my_rsa_cert->identity_key, digest) < 0) { + goto error; + } + + /* New commit with our identity key. */ + commit = commit_new(digest); + + /* Generate the reveal random value */ + crypto_strongest_rand(commit->random_number, + sizeof(commit->random_number)); + commit->commit_ts = commit->reveal_ts = timestamp; + + /* Now get the base64 blob that corresponds to our reveal */ + if (reveal_encode(commit, commit->encoded_reveal, + sizeof(commit->encoded_reveal)) < 0) { + log_err(LD_DIR, "SR: Unable to encode our reveal value!"); + goto error; + } + + /* Now let's create the commitment */ + tor_assert(commit->alg == SR_DIGEST_ALG); + /* The invariant length is used here since the encoded reveal variable + * has an extra byte added for the NULL terminated byte. */ + if (crypto_digest256(commit->hashed_reveal, commit->encoded_reveal, + SR_REVEAL_BASE64_LEN, commit->alg) < 0) { + goto error; + } + + /* Now get the base64 blob that corresponds to our commit. */ + if (commit_encode(commit, commit->encoded_commit, + sizeof(commit->encoded_commit)) < 0) { + log_err(LD_DIR, "SR: Unable to encode our commit value!"); + goto error; + } + + log_debug(LD_DIR, "SR: Generated our commitment:"); + commit_log(commit); + /* Our commit better be valid :). */ + commit->valid = 1; + return commit; + + error: + sr_commit_free(commit); + return NULL; +} + +/* Compute the shared random value based on the active commits in our state. */ +void +sr_compute_srv(void) +{ + uint64_t reveal_num = 0; + char *reveals = NULL; + smartlist_t *chunks, *commits; + digestmap_t *state_commits; + + /* Computing a shared random value in the commit phase is very wrong. This + * should only happen at the very end of the reveal phase when a new + * protocol run is about to start. */ + tor_assert(sr_state_get_phase() == SR_PHASE_REVEAL); + state_commits = sr_state_get_commits(); + + commits = smartlist_new(); + chunks = smartlist_new(); + + /* We must make a list of commit ordered by authority fingerprint in + * ascending order as specified by proposal 250. */ + DIGESTMAP_FOREACH(state_commits, key, sr_commit_t *, c) { + /* Extra safety net, make sure we have valid commit before using it. */ + ASSERT_COMMIT_VALID(c); + /* Let's not use a commit from an authority that we don't know. It's + * possible that an authority could be removed during a protocol run so + * that commit value should never be used in the SRV computation. */ + if (trusteddirserver_get_by_v3_auth_digest(c->rsa_identity) == NULL) { + log_warn(LD_DIR, "SR: Fingerprint %s is not from a recognized " + "authority. Discarding commit for the SRV computation.", + sr_commit_get_rsa_fpr(c)); + continue; + } + /* We consider this commit valid. */ + smartlist_add(commits, c); + } DIGESTMAP_FOREACH_END; + smartlist_sort(commits, compare_reveal_); + + /* Now for each commit for that sorted list in ascending order, we'll + * build the element for each authority that needs to go into the srv + * computation. */ + SMARTLIST_FOREACH_BEGIN(commits, const sr_commit_t *, c) { + char *element = get_srv_element_from_commit(c); + if (element) { + smartlist_add(chunks, element); + reveal_num++; + } + } SMARTLIST_FOREACH_END(c); + smartlist_free(commits); + + { + /* Join all reveal values into one giant string that we'll hash so we + * can generated our shared random value. */ + sr_srv_t *current_srv; + char hashed_reveals[DIGEST256_LEN]; + reveals = smartlist_join_strings(chunks, "", 0, NULL); + SMARTLIST_FOREACH(chunks, char *, s, tor_free(s)); + smartlist_free(chunks); + if (crypto_digest256(hashed_reveals, reveals, strlen(reveals), + SR_DIGEST_ALG) < 0) { + goto end; + } + current_srv = generate_srv(hashed_reveals, reveal_num, + sr_state_get_previous_srv()); + sr_state_set_current_srv(current_srv); + /* We have a fresh SRV, flag our state. */ + sr_state_set_fresh_srv(); + } + + end: + tor_free(reveals); +} + +/* Parse a commit from a vote or from our disk state and return a newly + * allocated commit object. NULL is returned on error. + * + * The commit's data is in <b>args</b> and the order matters very much: + * version, algname, RSA fingerprint, commit value[, reveal value] + */ +sr_commit_t * +sr_parse_commit(const smartlist_t *args) +{ + uint32_t version; + char *value, digest[DIGEST_LEN]; + digest_algorithm_t alg; + const char *rsa_identity_fpr; + sr_commit_t *commit = NULL; + + if (smartlist_len(args) < 4) { + goto error; + } + + /* First is the version number of the SR protocol which indicates at which + * version that commit was created. */ + value = smartlist_get(args, 0); + version = (uint32_t) tor_parse_ulong(value, 10, 1, UINT32_MAX, NULL, NULL); + if (version > SR_PROTO_VERSION) { + log_info(LD_DIR, "SR: Commit version %" PRIu32 " (%s) is not supported.", + version, escaped(value)); + goto error; + } + + /* Second is the algorithm. */ + value = smartlist_get(args, 1); + alg = crypto_digest_algorithm_parse_name(value); + if (alg != SR_DIGEST_ALG) { + log_warn(LD_BUG, "SR: Commit algorithm %s is not recognized.", + escaped(value)); + goto error; + } + + /* Third argument is the RSA fingerprint of the auth and turn it into a + * digest value. */ + rsa_identity_fpr = smartlist_get(args, 2); + if (base16_decode(digest, DIGEST_LEN, rsa_identity_fpr, + HEX_DIGEST_LEN) < 0) { + log_warn(LD_DIR, "SR: RSA fingerprint %s not decodable", + escaped(rsa_identity_fpr)); + goto error; + } + + /* Allocate commit since we have a valid identity now. */ + commit = commit_new(digest); + + /* Fourth argument is the commitment value base64-encoded. */ + value = smartlist_get(args, 3); + if (commit_decode(value, commit) < 0) { + goto error; + } + + /* (Optional) Fifth argument is the revealed value. */ + if (smartlist_len(args) > 4) { + value = smartlist_get(args, 4); + if (reveal_decode(value, commit) < 0) { + goto error; + } + } + + return commit; + + error: + sr_commit_free(commit); + return NULL; +} + +/* Called when we are done parsing a vote by <b>voter_key</b> that might + * contain some useful <b>commits</b>. Find if any of them should be kept + * and update our state accordingly. Once done, the list of commitments will + * be empty. */ +void +sr_handle_received_commits(smartlist_t *commits, crypto_pk_t *voter_key) +{ + char rsa_identity[DIGEST_LEN]; + + tor_assert(voter_key); + + /* It's possible that the vote has _NO_ commits. */ + if (commits == NULL) { + return; + } + + /* Get the RSA identity fingerprint of this voter */ + if (crypto_pk_get_digest(voter_key, rsa_identity) < 0) { + return; + } + + SMARTLIST_FOREACH_BEGIN(commits, sr_commit_t *, commit) { + /* We won't need the commit in this list anymore, kept or not. */ + SMARTLIST_DEL_CURRENT(commits, commit); + /* Check if this commit is valid and should be stored in our state. */ + if (!should_keep_commit(commit, rsa_identity, + sr_state_get_phase())) { + sr_commit_free(commit); + continue; + } + /* Ok, we have a valid commit now that we are about to put in our state. + * so flag it valid from now on. */ + commit->valid = 1; + /* Everything lines up: save this commit to state then! */ + save_commit_to_state(commit); + } SMARTLIST_FOREACH_END(commit); +} + +/* Return a heap-allocated string containing commits that should be put in + * the votes. It's the responsibility of the caller to free the string. + * This always return a valid string, either empty or with line(s). */ +char * +sr_get_string_for_vote(void) +{ + char *vote_str = NULL; + digestmap_t *state_commits; + smartlist_t *chunks = smartlist_new(); + const or_options_t *options = get_options(); + + /* Are we participating in the protocol? */ + if (!options->AuthDirSharedRandomness) { + goto end; + } + + log_debug(LD_DIR, "SR: Preparing our vote info:"); + + /* First line, put in the vote the participation flag. */ + { + char *sr_flag_line; + tor_asprintf(&sr_flag_line, "%s\n", sr_flag_ns_str); + smartlist_add(chunks, sr_flag_line); + } + + /* In our vote we include every commitment in our permanent state. */ + state_commits = sr_state_get_commits(); + smartlist_t *state_commit_vote_lines = smartlist_new(); + DIGESTMAP_FOREACH(state_commits, key, const sr_commit_t *, commit) { + char *line = get_vote_line_from_commit(commit, sr_state_get_phase()); + smartlist_add(state_commit_vote_lines, line); + } DIGESTMAP_FOREACH_END; + + /* Sort the commit strings by version (string, not numeric), algorithm, + * and fingerprint. This makes sure the commit lines in votes are in a + * recognisable, stable order. */ + smartlist_sort_strings(state_commit_vote_lines); + + /* Now add the sorted list of commits to the vote */ + smartlist_add_all(chunks, state_commit_vote_lines); + smartlist_free(state_commit_vote_lines); + + /* Add the SRV value(s) if any. */ + { + char *srv_lines = get_ns_str_from_sr_values(sr_state_get_previous_srv(), + sr_state_get_current_srv()); + if (srv_lines) { + smartlist_add(chunks, srv_lines); + } + } + + end: + vote_str = smartlist_join_strings(chunks, "", 0, NULL); + SMARTLIST_FOREACH(chunks, char *, s, tor_free(s)); + smartlist_free(chunks); + return vote_str; +} + +/* Return a heap-allocated string that should be put in the consensus and + * contains the shared randomness values. It's the responsibility of the + * caller to free the string. NULL is returned if no SRV(s) available. + * + * This is called when a consensus (any flavor) is bring created thus it + * should NEVER change the state nor the state should be changed in between + * consensus creation. + * + * <b>num_srv_agreements</b> is taken from the votes thus the voted value + * that should be used. + * */ +char * +sr_get_string_for_consensus(const smartlist_t *votes, + int32_t num_srv_agreements) +{ + char *srv_str; + const or_options_t *options = get_options(); + + tor_assert(votes); + + /* Not participating, avoid returning anything. */ + if (!options->AuthDirSharedRandomness) { + log_info(LD_DIR, "SR: Support disabled (AuthDirSharedRandomness %d)", + options->AuthDirSharedRandomness); + goto end; + } + + /* Set the global value of AuthDirNumSRVAgreements found in the votes. */ + num_srv_agreements_from_vote = num_srv_agreements; + + /* Check the votes and figure out if SRVs should be included in the final + * consensus. */ + sr_srv_t *prev_srv = get_majority_srv_from_votes(votes, 0); + sr_srv_t *cur_srv = get_majority_srv_from_votes(votes, 1); + srv_str = get_ns_str_from_sr_values(prev_srv, cur_srv); + if (!srv_str) { + goto end; + } + + return srv_str; + end: + return NULL; +} + +/* We just computed a new <b>consensus</b>. Update our state with the SRVs + * from the consensus (might be NULL as well). Register the SRVs in our SR + * state and prepare for the upcoming protocol round. */ +void +sr_act_post_consensus(const networkstatus_t *consensus) +{ + const or_options_t *options = get_options(); + + /* Don't act if our state hasn't been initialized. We can be called during + * boot time when loading consensus from disk which is prior to the + * initialization of the SR subsystem. We also should not be doing + * anything if we are _not_ a directory authority and if we are a bridge + * authority. */ + if (!sr_state_is_initialized() || !authdir_mode_v3(options) || + authdir_mode_bridge(options)) { + return; + } + + /* Set the majority voted SRVs in our state even if both are NULL. It + * doesn't matter this is what the majority has decided. Obviously, we can + * only do that if we have a consensus. */ + if (consensus) { + /* Start by freeing the current SRVs since the SRVs we believed during + * voting do not really matter. Now that all the votes are in, we use the + * majority's opinion on which are the active SRVs. */ + sr_state_clean_srvs(); + /* Reset the fresh flag of the SRV so we know that from now on we don't + * have a new SRV to vote for. We just used the one from the consensus + * decided by the majority. */ + sr_state_unset_fresh_srv(); + /* Set the SR values from the given consensus. */ + sr_state_set_previous_srv(srv_dup(consensus->sr_info.previous_srv)); + sr_state_set_current_srv(srv_dup(consensus->sr_info.current_srv)); + } + + /* Prepare our state so that it's ready for the next voting period. */ + sr_state_update(voting_schedule_get_next_valid_after_time()); +} + +/* Initialize shared random subsystem. This MUST be called early in the boot + * process of tor. Return 0 on success else -1 on error. */ +int +sr_init(int save_to_disk) +{ + return sr_state_init(save_to_disk, 1); +} + +/* Save our state to disk and cleanup everything. */ +void +sr_save_and_cleanup(void) +{ + sr_state_save(); + sr_cleanup(); +} + +#ifdef TOR_UNIT_TESTS + +/* Set the global value of number of SRV agreements so the test can play + * along by calling specific functions that don't parse the votes prior for + * the AuthDirNumSRVAgreements value. */ +void +set_num_srv_agreements(int32_t value) +{ + num_srv_agreements_from_vote = value; +} + +#endif /* defined(TOR_UNIT_TESTS) */ + diff --git a/src/or/dirauth/shared_random.h b/src/or/dirauth/shared_random.h new file mode 100644 index 0000000000..1778ce8f09 --- /dev/null +++ b/src/or/dirauth/shared_random.h @@ -0,0 +1,194 @@ +/* Copyright (c) 2016-2017, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#ifndef TOR_SHARED_RANDOM_H +#define TOR_SHARED_RANDOM_H + +/* + * This file contains ABI/API of the shared random protocol defined in + * proposal #250. Every public functions and data structure are namespaced + * with "sr_" which stands for shared random. + */ + +#include "or.h" + +/* Protocol version */ +#define SR_PROTO_VERSION 1 +/* Default digest algorithm. */ +#define SR_DIGEST_ALG DIGEST_SHA3_256 +/* Invariant token in the SRV calculation. */ +#define SR_SRV_TOKEN "shared-random" +/* Don't count the NUL terminated byte even though the TOKEN has it. */ +#define SR_SRV_TOKEN_LEN (sizeof(SR_SRV_TOKEN) - 1) + +/* Length of the random number (in bytes). */ +#define SR_RANDOM_NUMBER_LEN 32 +/* Size of a decoded commit value in a vote or state. It's a hash and a + * timestamp. It adds up to 40 bytes. */ +#define SR_COMMIT_LEN (sizeof(uint64_t) + DIGEST256_LEN) +/* Size of a decoded reveal value from a vote or state. It's a 64 bit + * timestamp and the hashed random number. This adds up to 40 bytes. */ +#define SR_REVEAL_LEN (sizeof(uint64_t) + DIGEST256_LEN) +/* Size of SRV message length. The construction is has follow: + * "shared-random" | INT_8(reveal_num) | INT_4(version) | PREV_SRV */ +#define SR_SRV_MSG_LEN \ + (SR_SRV_TOKEN_LEN + sizeof(uint64_t) + sizeof(uint32_t) + DIGEST256_LEN) + +/* Length of base64 encoded commit NOT including the NUL terminated byte. + * Formula is taken from base64_encode_size. This adds up to 56 bytes. */ +#define SR_COMMIT_BASE64_LEN (BASE64_LEN(SR_COMMIT_LEN)) +/* Length of base64 encoded reveal NOT including the NUL terminated byte. + * Formula is taken from base64_encode_size. This adds up to 56 bytes. */ +#define SR_REVEAL_BASE64_LEN (BASE64_LEN(SR_REVEAL_LEN)) +/* Length of base64 encoded shared random value. It's 32 bytes long so 44 + * bytes from the base64_encode_size formula. That includes the '=' + * character at the end. */ +#define SR_SRV_VALUE_BASE64_LEN (BASE64_LEN(DIGEST256_LEN)) + +/* Assert if commit valid flag is not set. */ +#define ASSERT_COMMIT_VALID(c) tor_assert((c)->valid) + +/* Protocol phase. */ +typedef enum { + /* Commitment phase */ + SR_PHASE_COMMIT = 1, + /* Reveal phase */ + SR_PHASE_REVEAL = 2, +} sr_phase_t; + +/* A shared random value (SRV). */ +typedef struct sr_srv_t { + /* The number of reveal values used to derive this SRV. */ + uint64_t num_reveals; + /* The actual value. This is the stored result of SHA3-256. */ + uint8_t value[DIGEST256_LEN]; +} sr_srv_t; + +/* A commit (either ours or from another authority). */ +typedef struct sr_commit_t { + /* Hashing algorithm used. */ + digest_algorithm_t alg; + /* Indicate if this commit has been verified thus valid. */ + unsigned int valid:1; + + /* Commit owner info */ + + /* The RSA identity key of the authority and its base16 representation, + * which includes the NUL terminated byte. */ + char rsa_identity[DIGEST_LEN]; + char rsa_identity_hex[HEX_DIGEST_LEN + 1]; + + /* Commitment information */ + + /* Timestamp of reveal. Correspond to TIMESTAMP. */ + uint64_t reveal_ts; + /* H(REVEAL) as found in COMMIT message. */ + char hashed_reveal[DIGEST256_LEN]; + /* Base64 encoded COMMIT. We use this to put it in our vote. */ + char encoded_commit[SR_COMMIT_BASE64_LEN + 1]; + + /* Reveal information */ + + /* H(RN) which is what we used as the random value for this commit. We + * don't use the raw bytes since those are sent on the network thus + * avoiding possible information leaks of our PRNG. */ + uint8_t random_number[SR_RANDOM_NUMBER_LEN]; + /* Timestamp of commit. Correspond to TIMESTAMP. */ + uint64_t commit_ts; + /* This is the whole reveal message. We use it during verification */ + char encoded_reveal[SR_REVEAL_BASE64_LEN + 1]; +} sr_commit_t; + +/* API */ + +/* Public methods used _outside_ of the module. + * + * We need to nullify them if the module is disabled. */ +#ifdef HAVE_MODULE_DIRAUTH + +int sr_init(int save_to_disk); +void sr_save_and_cleanup(void); +void sr_act_post_consensus(const networkstatus_t *consensus); + +#else /* HAVE_MODULE_DIRAUTH */ + +static inline int +sr_init(int save_to_disk) +{ + (void) save_to_disk; + /* Always return success. */ + return 0; +} + +static inline void +sr_save_and_cleanup(void) +{ +} + +static inline void +sr_act_post_consensus(const networkstatus_t *consensus) +{ + (void) consensus; +} + +#endif /* HAVE_MODULE_DIRAUTH */ + +/* Public methods used only by dirauth code. */ + +void sr_handle_received_commits(smartlist_t *commits, + crypto_pk_t *voter_key); +sr_commit_t *sr_parse_commit(const smartlist_t *args); +char *sr_get_string_for_vote(void); +char *sr_get_string_for_consensus(const smartlist_t *votes, + int32_t num_srv_agreements); +void sr_commit_free_(sr_commit_t *commit); +#define sr_commit_free(sr) FREE_AND_NULL(sr_commit_t, sr_commit_free_, (sr)) + +/* Private methods (only used by shared_random_state.c): */ +static inline +const char *sr_commit_get_rsa_fpr(const sr_commit_t *commit) +{ + return commit->rsa_identity_hex; +} + +void sr_compute_srv(void); +sr_commit_t *sr_generate_our_commit(time_t timestamp, + const authority_cert_t *my_rsa_cert); + +#ifdef SHARED_RANDOM_PRIVATE + +/* Encode */ +STATIC int reveal_encode(const sr_commit_t *commit, char *dst, size_t len); +STATIC int commit_encode(const sr_commit_t *commit, char *dst, size_t len); +/* Decode. */ +STATIC int commit_decode(const char *encoded, sr_commit_t *commit); +STATIC int reveal_decode(const char *encoded, sr_commit_t *commit); + +STATIC int commit_has_reveal_value(const sr_commit_t *commit); + +STATIC int verify_commit_and_reveal(const sr_commit_t *commit); + +STATIC sr_srv_t *get_majority_srv_from_votes(const smartlist_t *votes, + int current); + +STATIC void save_commit_to_state(sr_commit_t *commit); +STATIC sr_srv_t *srv_dup(const sr_srv_t *orig); +STATIC int commitments_are_the_same(const sr_commit_t *commit_one, + const sr_commit_t *commit_two); +STATIC int commit_is_authoritative(const sr_commit_t *commit, + const char *voter_key); +STATIC int should_keep_commit(const sr_commit_t *commit, + const char *voter_key, + sr_phase_t phase); +STATIC void save_commit_during_reveal_phase(const sr_commit_t *commit); + +#endif /* defined(SHARED_RANDOM_PRIVATE) */ + +#ifdef TOR_UNIT_TESTS + +void set_num_srv_agreements(int32_t value); + +#endif /* TOR_UNIT_TESTS */ + +#endif /* !defined(TOR_SHARED_RANDOM_H) */ + diff --git a/src/or/dirauth/shared_random_state.c b/src/or/dirauth/shared_random_state.c new file mode 100644 index 0000000000..245fb99ce7 --- /dev/null +++ b/src/or/dirauth/shared_random_state.c @@ -0,0 +1,1323 @@ +/* Copyright (c) 2016-2017, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file shared_random_state.c + * + * \brief Functions and data structures for the state of the random protocol + * as defined in proposal #250. + **/ + +#define SHARED_RANDOM_STATE_PRIVATE + +#include "or.h" +#include "config.h" +#include "confparse.h" +#include "crypto_util.h" +#include "dirauth/dirvote.h" +#include "networkstatus.h" +#include "router.h" +#include "shared_random.h" +#include "shared_random_client.h" +#include "shared_random_state.h" +#include "voting_schedule.h" + +/* Default filename of the shared random state on disk. */ +static const char default_fname[] = "sr-state"; + +/* String representation of a protocol phase. */ +static const char *phase_str[] = { "unknown", "commit", "reveal" }; + +/* Our shared random protocol state. There is only one possible state per + * protocol run so this is the global state which is reset at every run once + * the shared random value has been computed. */ +static sr_state_t *sr_state = NULL; + +/* Representation of our persistent state on disk. The sr_state above + * contains the data parsed from this state. When we save to disk, we + * translate the sr_state to this sr_disk_state. */ +static sr_disk_state_t *sr_disk_state = NULL; + +/* Disk state file keys. */ +static const char dstate_commit_key[] = "Commit"; +static const char dstate_prev_srv_key[] = "SharedRandPreviousValue"; +static const char dstate_cur_srv_key[] = "SharedRandCurrentValue"; + +/** dummy instance of sr_disk_state_t, used for type-checking its + * members with CONF_CHECK_VAR_TYPE. */ +DUMMY_TYPECHECK_INSTANCE(sr_disk_state_t); + +/* These next two are duplicates or near-duplicates from config.c */ +#define VAR(name, conftype, member, initvalue) \ + { name, CONFIG_TYPE_ ## conftype, offsetof(sr_disk_state_t, member), \ + initvalue CONF_TEST_MEMBERS(sr_disk_state_t, conftype, member) } +/* As VAR, but the option name and member name are the same. */ +#define V(member, conftype, initvalue) \ + VAR(#member, conftype, member, initvalue) +/* Our persistent state magic number. */ +#define SR_DISK_STATE_MAGIC 0x98AB1254 + +static int +disk_state_validate_cb(void *old_state, void *state, void *default_state, + int from_setconf, char **msg); + +/* Array of variables that are saved to disk as a persistent state. */ +static config_var_t state_vars[] = { + V(Version, UINT, "0"), + V(TorVersion, STRING, NULL), + V(ValidAfter, ISOTIME, NULL), + V(ValidUntil, ISOTIME, NULL), + + V(Commit, LINELIST, NULL), + + V(SharedRandValues, LINELIST_V, NULL), + VAR("SharedRandPreviousValue",LINELIST_S, SharedRandValues, NULL), + VAR("SharedRandCurrentValue", LINELIST_S, SharedRandValues, NULL), + END_OF_CONFIG_VARS +}; + +/* "Extra" variable in the state that receives lines we can't parse. This + * lets us preserve options from versions of Tor newer than us. */ +static config_var_t state_extra_var = { + "__extra", CONFIG_TYPE_LINELIST, + offsetof(sr_disk_state_t, ExtraLines), NULL + CONF_TEST_MEMBERS(sr_disk_state_t, LINELIST, ExtraLines) +}; + +/* Configuration format of sr_disk_state_t. */ +static const config_format_t state_format = { + sizeof(sr_disk_state_t), + SR_DISK_STATE_MAGIC, + offsetof(sr_disk_state_t, magic_), + NULL, + NULL, + state_vars, + disk_state_validate_cb, + &state_extra_var, +}; + +/* Return a string representation of a protocol phase. */ +STATIC const char * +get_phase_str(sr_phase_t phase) +{ + const char *the_string = NULL; + + switch (phase) { + case SR_PHASE_COMMIT: + case SR_PHASE_REVEAL: + the_string = phase_str[phase]; + break; + default: + /* Unknown phase shouldn't be possible. */ + tor_assert(0); + } + + return the_string; +} +/* Return the time we should expire the state file created at <b>now</b>. + * We expire the state file in the beginning of the next protocol run. */ +STATIC time_t +get_state_valid_until_time(time_t now) +{ + int total_rounds = SHARED_RANDOM_N_ROUNDS * SHARED_RANDOM_N_PHASES; + int current_round, voting_interval, rounds_left; + time_t valid_until, beginning_of_current_round; + + voting_interval = get_voting_interval(); + /* Find the time the current round started. */ + beginning_of_current_round = get_start_time_of_current_round(); + + /* Find how many rounds are left till the end of the protocol run */ + current_round = (now / voting_interval) % total_rounds; + rounds_left = total_rounds - current_round; + + /* To find the valid-until time now, take the start time of the current + * round and add to it the time it takes for the leftover rounds to + * complete. */ + valid_until = beginning_of_current_round + (rounds_left * voting_interval); + + { /* Logging */ + char tbuf[ISO_TIME_LEN + 1]; + format_iso_time(tbuf, valid_until); + log_debug(LD_DIR, "SR: Valid until time for state set to %s.", tbuf); + } + + return valid_until; +} + +/* Given the consensus 'valid-after' time, return the protocol phase we should + * be in. */ +STATIC sr_phase_t +get_sr_protocol_phase(time_t valid_after) +{ + /* Shared random protocol has two phases, commit and reveal. */ + int total_periods = SHARED_RANDOM_N_ROUNDS * SHARED_RANDOM_N_PHASES; + int current_slot; + + /* Split time into slots of size 'voting_interval'. See which slot we are + * currently into, and find which phase it corresponds to. */ + current_slot = (valid_after / get_voting_interval()) % total_periods; + + if (current_slot < SHARED_RANDOM_N_ROUNDS) { + return SR_PHASE_COMMIT; + } else { + return SR_PHASE_REVEAL; + } +} + +/* Add the given <b>commit</b> to <b>state</b>. It MUST be a valid commit + * and there shouldn't be a commit from the same authority in the state + * already else verification hasn't been done prior. This takes ownership of + * the commit once in our state. */ +static void +commit_add_to_state(sr_commit_t *commit, sr_state_t *state) +{ + sr_commit_t *saved_commit; + + tor_assert(commit); + tor_assert(state); + + saved_commit = digestmap_set(state->commits, commit->rsa_identity, + commit); + if (saved_commit != NULL) { + /* This means we already have that commit in our state so adding twice + * the same commit is either a code flow error, a corrupted disk state + * or some new unknown issue. */ + log_warn(LD_DIR, "SR: Commit from %s exists in our state while " + "adding it: '%s'", sr_commit_get_rsa_fpr(commit), + commit->encoded_commit); + sr_commit_free(saved_commit); + } +} + +/* Helper: deallocate a commit object. (Used with digestmap_free(), which + * requires a function pointer whose argument is void *). */ +static void +commit_free_(void *p) +{ + sr_commit_free_(p); +} + +#define state_free(val) \ + FREE_AND_NULL(sr_state_t, state_free_, (val)) + +/* Free a state that was allocated with state_new(). */ +static void +state_free_(sr_state_t *state) +{ + if (state == NULL) { + return; + } + tor_free(state->fname); + digestmap_free(state->commits, commit_free_); + tor_free(state->current_srv); + tor_free(state->previous_srv); + tor_free(state); +} + +/* Allocate an sr_state_t object and returns it. If no <b>fname</b>, the + * default file name is used. This function does NOT initialize the state + * timestamp, phase or shared random value. NULL is never returned. */ +static sr_state_t * +state_new(const char *fname, time_t now) +{ + sr_state_t *new_state = tor_malloc_zero(sizeof(*new_state)); + /* If file name is not provided, use default. */ + if (fname == NULL) { + fname = default_fname; + } + new_state->fname = tor_strdup(fname); + new_state->version = SR_PROTO_VERSION; + new_state->commits = digestmap_new(); + new_state->phase = get_sr_protocol_phase(now); + new_state->valid_until = get_state_valid_until_time(now); + return new_state; +} + +/* Set our global state pointer with the one given. */ +static void +state_set(sr_state_t *state) +{ + tor_assert(state); + if (sr_state != NULL) { + state_free(sr_state); + } + sr_state = state; +} + +#define disk_state_free(val) \ + FREE_AND_NULL(sr_disk_state_t, disk_state_free_, (val)) + +/* Free an allocated disk state. */ +static void +disk_state_free_(sr_disk_state_t *state) +{ + if (state == NULL) { + return; + } + config_free(&state_format, state); +} + +/* Allocate a new disk state, initialize it and return it. */ +static sr_disk_state_t * +disk_state_new(time_t now) +{ + sr_disk_state_t *new_state = tor_malloc_zero(sizeof(*new_state)); + + new_state->magic_ = SR_DISK_STATE_MAGIC; + new_state->Version = SR_PROTO_VERSION; + new_state->TorVersion = tor_strdup(get_version()); + new_state->ValidUntil = get_state_valid_until_time(now); + new_state->ValidAfter = now; + + /* Init config format. */ + config_init(&state_format, new_state); + return new_state; +} + +/* Set our global disk state with the given state. */ +static void +disk_state_set(sr_disk_state_t *state) +{ + tor_assert(state); + if (sr_disk_state != NULL) { + disk_state_free(sr_disk_state); + } + sr_disk_state = state; +} + +/* Return -1 if the disk state is invalid (something in there that we can't or + * shouldn't use). Return 0 if everything checks out. */ +static int +disk_state_validate(const sr_disk_state_t *state) +{ + time_t now; + + tor_assert(state); + + /* Do we support the protocol version in the state or is it 0 meaning + * Version wasn't found in the state file or bad anyway ? */ + if (state->Version == 0 || state->Version > SR_PROTO_VERSION) { + goto invalid; + } + + /* If the valid until time is before now, we shouldn't use that state. */ + now = time(NULL); + if (state->ValidUntil < now) { + log_info(LD_DIR, "SR: Disk state has expired. Ignoring it."); + goto invalid; + } + + /* Make sure we don't have a valid after time that is earlier than a valid + * until time which would make things not work well. */ + if (state->ValidAfter >= state->ValidUntil) { + log_info(LD_DIR, "SR: Disk state valid after/until times are invalid."); + goto invalid; + } + + return 0; + + invalid: + return -1; +} + +/* Validate the disk state (NOP for now). */ +static int +disk_state_validate_cb(void *old_state, void *state, void *default_state, + int from_setconf, char **msg) +{ + /* We don't use these; only options do. */ + (void) from_setconf; + (void) default_state; + (void) old_state; + + /* This is called by config_dump which is just before we are about to + * write it to disk. At that point, our global memory state has been + * copied to the disk state so it's fair to assume it's trustable. */ + (void) state; + (void) msg; + return 0; +} + +/* Parse the Commit line(s) in the disk state and translate them to the + * the memory state. Return 0 on success else -1 on error. */ +static int +disk_state_parse_commits(sr_state_t *state, + const sr_disk_state_t *disk_state) +{ + config_line_t *line; + smartlist_t *args = NULL; + + tor_assert(state); + tor_assert(disk_state); + + for (line = disk_state->Commit; line; line = line->next) { + sr_commit_t *commit = NULL; + + /* Extra safety. */ + if (strcasecmp(line->key, dstate_commit_key) || + line->value == NULL) { + /* Ignore any lines that are not commits. */ + tor_fragile_assert(); + continue; + } + args = smartlist_new(); + smartlist_split_string(args, line->value, " ", + SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0); + if (smartlist_len(args) < 3) { + log_warn(LD_BUG, "SR: Too few arguments in Commit Line: %s", + escaped(line->value)); + goto error; + } + commit = sr_parse_commit(args); + if (commit == NULL) { + /* Ignore badly formed commit. It could also be a authority + * fingerprint that we don't know about so it shouldn't be used. */ + continue; + } + /* We consider parseable commit from our disk state to be valid because + * they need to be in the first place to get in there. */ + commit->valid = 1; + /* Add commit to our state pointer. */ + commit_add_to_state(commit, state); + + SMARTLIST_FOREACH(args, char *, cp, tor_free(cp)); + smartlist_free(args); + } + + return 0; + + error: + SMARTLIST_FOREACH(args, char *, cp, tor_free(cp)); + smartlist_free(args); + return -1; +} + +/* Parse a share random value line from the disk state and save it to dst + * which is an allocated srv object. Return 0 on success else -1. */ +static int +disk_state_parse_srv(const char *value, sr_srv_t *dst) +{ + int ret = -1; + smartlist_t *args; + sr_srv_t *srv; + + tor_assert(value); + tor_assert(dst); + + args = smartlist_new(); + smartlist_split_string(args, value, " ", + SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0); + if (smartlist_len(args) < 2) { + log_warn(LD_BUG, "SR: Too few arguments in shared random value. " + "Line: %s", escaped(value)); + goto error; + } + srv = sr_parse_srv(args); + if (srv == NULL) { + goto error; + } + dst->num_reveals = srv->num_reveals; + memcpy(dst->value, srv->value, sizeof(dst->value)); + tor_free(srv); + ret = 0; + + error: + SMARTLIST_FOREACH(args, char *, s, tor_free(s)); + smartlist_free(args); + return ret; +} + +/* Parse both SharedRandCurrentValue and SharedRandPreviousValue line from + * the state. Return 0 on success else -1. */ +static int +disk_state_parse_sr_values(sr_state_t *state, + const sr_disk_state_t *disk_state) +{ + /* Only one value per type (current or previous) is allowed so we keep + * track of it with these flag. */ + unsigned int seen_previous = 0, seen_current = 0; + config_line_t *line; + sr_srv_t *srv = NULL; + + tor_assert(state); + tor_assert(disk_state); + + for (line = disk_state->SharedRandValues; line; line = line->next) { + if (line->value == NULL) { + continue; + } + srv = tor_malloc_zero(sizeof(*srv)); + if (disk_state_parse_srv(line->value, srv) < 0) { + log_warn(LD_BUG, "SR: Broken current SRV line in state %s", + escaped(line->value)); + goto bad; + } + if (!strcasecmp(line->key, dstate_prev_srv_key)) { + if (seen_previous) { + log_warn(LD_DIR, "SR: Second previous SRV value seen. Bad state"); + goto bad; + } + state->previous_srv = srv; + seen_previous = 1; + } else if (!strcasecmp(line->key, dstate_cur_srv_key)) { + if (seen_current) { + log_warn(LD_DIR, "SR: Second current SRV value seen. Bad state"); + goto bad; + } + state->current_srv = srv; + seen_current = 1; + } else { + /* Unknown key. Ignoring. */ + tor_free(srv); + } + } + + return 0; + bad: + tor_free(srv); + return -1; +} + +/* Parse the given disk state and set a newly allocated state. On success, + * return that state else NULL. */ +static sr_state_t * +disk_state_parse(const sr_disk_state_t *new_disk_state) +{ + sr_state_t *new_state = state_new(default_fname, time(NULL)); + + tor_assert(new_disk_state); + + new_state->version = new_disk_state->Version; + new_state->valid_until = new_disk_state->ValidUntil; + new_state->valid_after = new_disk_state->ValidAfter; + + /* Set our current phase according to the valid-after time in our disk + * state. The disk state we are parsing contains everything for the phase + * starting at valid_after so make sure our phase reflects that. */ + new_state->phase = get_sr_protocol_phase(new_state->valid_after); + + /* Parse the shared random values. */ + if (disk_state_parse_sr_values(new_state, new_disk_state) < 0) { + goto error; + } + /* Parse the commits. */ + if (disk_state_parse_commits(new_state, new_disk_state) < 0) { + goto error; + } + /* Great! This new state contains everything we had on disk. */ + return new_state; + + error: + state_free(new_state); + return NULL; +} + +/* From a valid commit object and an allocated config line, set the line's + * value to the state string representation of a commit. */ +static void +disk_state_put_commit_line(const sr_commit_t *commit, config_line_t *line) +{ + char *reveal_str = NULL; + + tor_assert(commit); + tor_assert(line); + + if (!tor_mem_is_zero(commit->encoded_reveal, + sizeof(commit->encoded_reveal))) { + /* Add extra whitespace so we can format the line correctly. */ + tor_asprintf(&reveal_str, " %s", commit->encoded_reveal); + } + tor_asprintf(&line->value, "%u %s %s %s%s", + SR_PROTO_VERSION, + crypto_digest_algorithm_get_name(commit->alg), + sr_commit_get_rsa_fpr(commit), + commit->encoded_commit, + reveal_str != NULL ? reveal_str : ""); + if (reveal_str != NULL) { + memwipe(reveal_str, 0, strlen(reveal_str)); + tor_free(reveal_str); + } +} + +/* From a valid srv object and an allocated config line, set the line's + * value to the state string representation of a shared random value. */ +static void +disk_state_put_srv_line(const sr_srv_t *srv, config_line_t *line) +{ + char encoded[SR_SRV_VALUE_BASE64_LEN + 1]; + + tor_assert(line); + + /* No SRV value thus don't add the line. This is possible since we might + * not have a current or previous SRV value in our state. */ + if (srv == NULL) { + return; + } + sr_srv_encode(encoded, sizeof(encoded), srv); + tor_asprintf(&line->value, "%" PRIu64 " %s", srv->num_reveals, encoded); +} + +/* Reset disk state that is free allocated memory and zeroed the object. */ +static void +disk_state_reset(void) +{ + /* Free allocated memory */ + config_free_lines(sr_disk_state->Commit); + config_free_lines(sr_disk_state->SharedRandValues); + config_free_lines(sr_disk_state->ExtraLines); + tor_free(sr_disk_state->TorVersion); + + /* Clean up the struct */ + memset(sr_disk_state, 0, sizeof(*sr_disk_state)); + + /* Reset it with useful data */ + sr_disk_state->magic_ = SR_DISK_STATE_MAGIC; + sr_disk_state->TorVersion = tor_strdup(get_version()); +} + +/* Update our disk state based on our global SR state. */ +static void +disk_state_update(void) +{ + config_line_t **next, *line; + + tor_assert(sr_disk_state); + tor_assert(sr_state); + + /* Reset current disk state. */ + disk_state_reset(); + + /* First, update elements that we don't need to do a construction. */ + sr_disk_state->Version = sr_state->version; + sr_disk_state->ValidUntil = sr_state->valid_until; + sr_disk_state->ValidAfter = sr_state->valid_after; + + /* Shared random values. */ + next = &sr_disk_state->SharedRandValues; + if (sr_state->previous_srv != NULL) { + *next = line = tor_malloc_zero(sizeof(config_line_t)); + line->key = tor_strdup(dstate_prev_srv_key); + disk_state_put_srv_line(sr_state->previous_srv, line); + /* Go to the next shared random value. */ + next = &(line->next); + } + if (sr_state->current_srv != NULL) { + *next = line = tor_malloc_zero(sizeof(*line)); + line->key = tor_strdup(dstate_cur_srv_key); + disk_state_put_srv_line(sr_state->current_srv, line); + } + + /* Parse the commits and construct config line(s). */ + next = &sr_disk_state->Commit; + DIGESTMAP_FOREACH(sr_state->commits, key, sr_commit_t *, commit) { + *next = line = tor_malloc_zero(sizeof(*line)); + line->key = tor_strdup(dstate_commit_key); + disk_state_put_commit_line(commit, line); + next = &(line->next); + } DIGESTMAP_FOREACH_END; +} + +/* Load state from disk and put it into our disk state. If the state passes + * validation, our global state will be updated with it. Return 0 on + * success. On error, -EINVAL is returned if the state on disk did contained + * something malformed or is unreadable. -ENOENT is returned indicating that + * the state file is either empty of non existing. */ +static int +disk_state_load_from_disk(void) +{ + int ret; + char *fname; + + fname = get_datadir_fname(default_fname); + ret = disk_state_load_from_disk_impl(fname); + tor_free(fname); + + return ret; +} + +/* Helper for disk_state_load_from_disk(). */ +STATIC int +disk_state_load_from_disk_impl(const char *fname) +{ + int ret; + char *content = NULL; + sr_state_t *parsed_state = NULL; + sr_disk_state_t *disk_state = NULL; + + /* Read content of file so we can parse it. */ + if ((content = read_file_to_str(fname, 0, NULL)) == NULL) { + log_warn(LD_FS, "SR: Unable to read SR state file %s", + escaped(fname)); + ret = -errno; + goto error; + } + + { + config_line_t *lines = NULL; + char *errmsg = NULL; + + /* Every error in this code path will return EINVAL. */ + ret = -EINVAL; + if (config_get_lines(content, &lines, 0) < 0) { + config_free_lines(lines); + goto error; + } + + disk_state = disk_state_new(time(NULL)); + config_assign(&state_format, disk_state, lines, 0, &errmsg); + config_free_lines(lines); + if (errmsg) { + log_warn(LD_DIR, "SR: Reading state error: %s", errmsg); + tor_free(errmsg); + goto error; + } + } + + /* So far so good, we've loaded our state file into our disk state. Let's + * validate it and then parse it. */ + if (disk_state_validate(disk_state) < 0) { + ret = -EINVAL; + goto error; + } + + parsed_state = disk_state_parse(disk_state); + if (parsed_state == NULL) { + ret = -EINVAL; + goto error; + } + state_set(parsed_state); + disk_state_set(disk_state); + tor_free(content); + log_info(LD_DIR, "SR: State loaded successfully from file %s", fname); + return 0; + + error: + disk_state_free(disk_state); + tor_free(content); + return ret; +} + +/* Save the disk state to disk but before that update it from the current + * state so we always have the latest. Return 0 on success else -1. */ +static int +disk_state_save_to_disk(void) +{ + int ret; + char *state, *content = NULL, *fname = NULL; + char tbuf[ISO_TIME_LEN + 1]; + time_t now = time(NULL); + + /* If we didn't have the opportunity to setup an internal disk state, + * don't bother saving something to disk. */ + if (sr_disk_state == NULL) { + ret = 0; + goto done; + } + + /* Make sure that our disk state is up to date with our memory state + * before saving it to disk. */ + disk_state_update(); + state = config_dump(&state_format, NULL, sr_disk_state, 0, 0); + format_local_iso_time(tbuf, now); + tor_asprintf(&content, + "# Tor shared random state file last generated on %s " + "local time\n" + "# Other times below are in UTC\n" + "# Please *do not* edit this file.\n\n%s", + tbuf, state); + tor_free(state); + fname = get_datadir_fname(default_fname); + if (write_str_to_file(fname, content, 0) < 0) { + log_warn(LD_FS, "SR: Unable to write SR state to file %s", fname); + ret = -1; + goto done; + } + ret = 0; + log_debug(LD_DIR, "SR: Saved state to file %s", fname); + + done: + tor_free(fname); + tor_free(content); + return ret; +} + +/* Reset our state to prepare for a new protocol run. Once this returns, all + * commits in the state will be removed and freed. */ +STATIC void +reset_state_for_new_protocol_run(time_t valid_after) +{ + tor_assert(sr_state); + + /* Keep counters in track */ + sr_state->n_reveal_rounds = 0; + sr_state->n_commit_rounds = 0; + sr_state->n_protocol_runs++; + + /* Reset valid-until */ + sr_state->valid_until = get_state_valid_until_time(valid_after); + sr_state->valid_after = valid_after; + + /* We are in a new protocol run so cleanup commits. */ + sr_state_delete_commits(); +} + +/* This is the first round of the new protocol run starting at + * <b>valid_after</b>. Do the necessary housekeeping. */ +STATIC void +new_protocol_run(time_t valid_after) +{ + sr_commit_t *our_commitment = NULL; + + /* Only compute the srv at the end of the reveal phase. */ + if (sr_state->phase == SR_PHASE_REVEAL) { + /* We are about to compute a new shared random value that will be set in + * our state as the current value so rotate values. */ + state_rotate_srv(); + /* Compute the shared randomness value of the day. */ + sr_compute_srv(); + } + + /* Prepare for the new protocol run by reseting the state */ + reset_state_for_new_protocol_run(valid_after); + + /* Do some logging */ + log_info(LD_DIR, "SR: Protocol run #%" PRIu64 " starting!", + sr_state->n_protocol_runs); + + /* Generate fresh commitments for this protocol run */ + our_commitment = sr_generate_our_commit(valid_after, + get_my_v3_authority_cert()); + if (our_commitment) { + /* Add our commitment to our state. In case we are unable to create one + * (highly unlikely), we won't vote for this protocol run since our + * commitment won't be in our state. */ + sr_state_add_commit(our_commitment); + } +} + +/* Return 1 iff the <b>next_phase</b> is a phase transition from the current + * phase that is it's different. */ +STATIC int +is_phase_transition(sr_phase_t next_phase) +{ + return sr_state->phase != next_phase; +} + +/* Helper function: return a commit using the RSA fingerprint of the + * authority or NULL if no such commit is known. */ +static sr_commit_t * +state_query_get_commit(const char *rsa_fpr) +{ + tor_assert(rsa_fpr); + return digestmap_get(sr_state->commits, rsa_fpr); +} + +/* Helper function: This handles the GET state action using an + * <b>obj_type</b> and <b>data</b> needed for the action. */ +static void * +state_query_get_(sr_state_object_t obj_type, const void *data) +{ + void *obj = NULL; + + switch (obj_type) { + case SR_STATE_OBJ_COMMIT: + { + obj = state_query_get_commit(data); + break; + } + case SR_STATE_OBJ_COMMITS: + obj = sr_state->commits; + break; + case SR_STATE_OBJ_CURSRV: + obj = sr_state->current_srv; + break; + case SR_STATE_OBJ_PREVSRV: + obj = sr_state->previous_srv; + break; + case SR_STATE_OBJ_PHASE: + obj = &sr_state->phase; + break; + case SR_STATE_OBJ_VALID_AFTER: + default: + tor_assert(0); + } + return obj; +} + +/* Helper function: This handles the PUT state action using an + * <b>obj_type</b> and <b>data</b> needed for the action. */ +static void +state_query_put_(sr_state_object_t obj_type, void *data) +{ + switch (obj_type) { + case SR_STATE_OBJ_COMMIT: + { + sr_commit_t *commit = data; + tor_assert(commit); + commit_add_to_state(commit, sr_state); + break; + } + case SR_STATE_OBJ_CURSRV: + sr_state->current_srv = (sr_srv_t *) data; + break; + case SR_STATE_OBJ_PREVSRV: + sr_state->previous_srv = (sr_srv_t *) data; + break; + case SR_STATE_OBJ_VALID_AFTER: + sr_state->valid_after = *((time_t *) data); + break; + /* It's not allowed to change the phase nor the full commitments map from + * the state. The phase is decided during a strict process post voting and + * the commits should be put individually. */ + case SR_STATE_OBJ_PHASE: + case SR_STATE_OBJ_COMMITS: + default: + tor_assert(0); + } +} + +/* Helper function: This handles the DEL_ALL state action using an + * <b>obj_type</b> and <b>data</b> needed for the action. */ +static void +state_query_del_all_(sr_state_object_t obj_type) +{ + switch (obj_type) { + case SR_STATE_OBJ_COMMIT: + { + /* We are in a new protocol run so cleanup commitments. */ + DIGESTMAP_FOREACH_MODIFY(sr_state->commits, key, sr_commit_t *, c) { + sr_commit_free(c); + MAP_DEL_CURRENT(key); + } DIGESTMAP_FOREACH_END; + break; + } + /* The following object are _NOT_ suppose to be removed. */ + case SR_STATE_OBJ_CURSRV: + case SR_STATE_OBJ_PREVSRV: + case SR_STATE_OBJ_PHASE: + case SR_STATE_OBJ_COMMITS: + case SR_STATE_OBJ_VALID_AFTER: + default: + tor_assert(0); + } +} + +/* Helper function: This handles the DEL state action using an + * <b>obj_type</b> and <b>data</b> needed for the action. */ +static void +state_query_del_(sr_state_object_t obj_type, void *data) +{ + (void) data; + + switch (obj_type) { + case SR_STATE_OBJ_PREVSRV: + tor_free(sr_state->previous_srv); + break; + case SR_STATE_OBJ_CURSRV: + tor_free(sr_state->current_srv); + break; + case SR_STATE_OBJ_COMMIT: + case SR_STATE_OBJ_COMMITS: + case SR_STATE_OBJ_PHASE: + case SR_STATE_OBJ_VALID_AFTER: + default: + tor_assert(0); + } +} + +/* Query state using an <b>action</b> for an object type <b>obj_type</b>. + * The <b>data</b> pointer needs to point to an object that the action needs + * to use and if anything is required to be returned, it is stored in + * <b>out</b>. + * + * This mechanism exists so we have one single point where we synchronized + * our memory state with our disk state for every actions that changes it. + * We then trigger a write on disk immediately. + * + * This should be the only entry point to our memory state. It's used by all + * our state accessors and should be in the future. */ +static void +state_query(sr_state_action_t action, sr_state_object_t obj_type, + void *data, void **out) +{ + switch (action) { + case SR_STATE_ACTION_GET: + *out = state_query_get_(obj_type, data); + break; + case SR_STATE_ACTION_PUT: + state_query_put_(obj_type, data); + break; + case SR_STATE_ACTION_DEL: + state_query_del_(obj_type, data); + break; + case SR_STATE_ACTION_DEL_ALL: + state_query_del_all_(obj_type); + break; + case SR_STATE_ACTION_SAVE: + /* Only trigger a disk state save. */ + break; + default: + tor_assert(0); + } + + /* If the action actually changes the state, immediately save it to disk. + * The following will sync the state -> disk state and then save it. */ + if (action != SR_STATE_ACTION_GET) { + disk_state_save_to_disk(); + } +} + +/* Delete the current SRV value from the state freeing it and the value is set + * to NULL meaning empty. */ +static void +state_del_current_srv(void) +{ + state_query(SR_STATE_ACTION_DEL, SR_STATE_OBJ_CURSRV, NULL, NULL); +} + +/* Delete the previous SRV value from the state freeing it and the value is + * set to NULL meaning empty. */ +static void +state_del_previous_srv(void) +{ + state_query(SR_STATE_ACTION_DEL, SR_STATE_OBJ_PREVSRV, NULL, NULL); +} + +/* Rotate SRV value by freeing the previous value, assigning the current + * value to the previous one and nullifying the current one. */ +STATIC void +state_rotate_srv(void) +{ + /* First delete previous SRV from the state. Object will be freed. */ + state_del_previous_srv(); + /* Set previous SRV with the current one. */ + sr_state_set_previous_srv(sr_state_get_current_srv()); + /* Nullify the current srv. */ + sr_state_set_current_srv(NULL); +} + +/* Set valid after time in the our state. */ +void +sr_state_set_valid_after(time_t valid_after) +{ + state_query(SR_STATE_ACTION_PUT, SR_STATE_OBJ_VALID_AFTER, + (void *) &valid_after, NULL); +} + +/* Return the phase we are currently in according to our state. */ +sr_phase_t +sr_state_get_phase(void) +{ + void *ptr; + state_query(SR_STATE_ACTION_GET, SR_STATE_OBJ_PHASE, NULL, &ptr); + return *(sr_phase_t *) ptr; +} + +/* Return the previous SRV value from our state. Value CAN be NULL. */ +const sr_srv_t * +sr_state_get_previous_srv(void) +{ + const sr_srv_t *srv; + state_query(SR_STATE_ACTION_GET, SR_STATE_OBJ_PREVSRV, NULL, + (void *) &srv); + return srv; +} + +/* Set the current SRV value from our state. Value CAN be NULL. The srv + * object ownership is transferred to the state object. */ +void +sr_state_set_previous_srv(const sr_srv_t *srv) +{ + state_query(SR_STATE_ACTION_PUT, SR_STATE_OBJ_PREVSRV, (void *) srv, + NULL); +} + +/* Return the current SRV value from our state. Value CAN be NULL. */ +const sr_srv_t * +sr_state_get_current_srv(void) +{ + const sr_srv_t *srv; + state_query(SR_STATE_ACTION_GET, SR_STATE_OBJ_CURSRV, NULL, + (void *) &srv); + return srv; +} + +/* Set the current SRV value from our state. Value CAN be NULL. The srv + * object ownership is transferred to the state object. */ +void +sr_state_set_current_srv(const sr_srv_t *srv) +{ + state_query(SR_STATE_ACTION_PUT, SR_STATE_OBJ_CURSRV, (void *) srv, + NULL); +} + +/* Clean all the SRVs in our state. */ +void +sr_state_clean_srvs(void) +{ + /* Remove SRVs from state. They will be set to NULL as "empty". */ + state_del_previous_srv(); + state_del_current_srv(); +} + +/* Return a pointer to the commits map from our state. CANNOT be NULL. */ +digestmap_t * +sr_state_get_commits(void) +{ + digestmap_t *commits; + state_query(SR_STATE_ACTION_GET, SR_STATE_OBJ_COMMITS, + NULL, (void *) &commits); + tor_assert(commits); + return commits; +} + +/* Update the current SR state as needed for the upcoming voting round at + * <b>valid_after</b>. */ +void +sr_state_update(time_t valid_after) +{ + sr_phase_t next_phase; + + tor_assert(sr_state); + + /* Don't call this function twice in the same voting period. */ + if (valid_after <= sr_state->valid_after) { + log_info(LD_DIR, "SR: Asked to update state twice. Ignoring."); + return; + } + + /* Get phase of upcoming round. */ + next_phase = get_sr_protocol_phase(valid_after); + + /* If we are transitioning to a new protocol phase, prepare the stage. */ + if (is_phase_transition(next_phase)) { + if (next_phase == SR_PHASE_COMMIT) { + /* Going into commit phase means we are starting a new protocol run. */ + new_protocol_run(valid_after); + } + /* Set the new phase for this round */ + sr_state->phase = next_phase; + } else if (sr_state->phase == SR_PHASE_COMMIT && + digestmap_size(sr_state->commits) == 0) { + /* We are _NOT_ in a transition phase so if we are in the commit phase + * and have no commit, generate one. Chances are that we are booting up + * so let's have a commit in our state for the next voting period. */ + sr_commit_t *our_commit = + sr_generate_our_commit(valid_after, get_my_v3_authority_cert()); + if (our_commit) { + /* Add our commitment to our state. In case we are unable to create one + * (highly unlikely), we won't vote for this protocol run since our + * commitment won't be in our state. */ + sr_state_add_commit(our_commit); + } + } + + sr_state_set_valid_after(valid_after); + + /* Count the current round */ + if (sr_state->phase == SR_PHASE_COMMIT) { + /* invariant check: we've not entered reveal phase yet */ + tor_assert(sr_state->n_reveal_rounds == 0); + sr_state->n_commit_rounds++; + } else { + sr_state->n_reveal_rounds++; + } + + { /* Debugging. */ + char tbuf[ISO_TIME_LEN + 1]; + format_iso_time(tbuf, valid_after); + log_info(LD_DIR, "SR: State prepared for upcoming voting period (%s). " + "Upcoming phase is %s (counters: %d commit & %d reveal rounds).", + tbuf, get_phase_str(sr_state->phase), + sr_state->n_commit_rounds, sr_state->n_reveal_rounds); + } +} + +/* Return commit object from the given authority digest <b>rsa_identity</b>. + * Return NULL if not found. */ +sr_commit_t * +sr_state_get_commit(const char *rsa_identity) +{ + sr_commit_t *commit; + + tor_assert(rsa_identity); + + state_query(SR_STATE_ACTION_GET, SR_STATE_OBJ_COMMIT, + (void *) rsa_identity, (void *) &commit); + return commit; +} + +/* Add <b>commit</b> to the permanent state. The commit object ownership is + * transferred to the state so the caller MUST not free it. */ +void +sr_state_add_commit(sr_commit_t *commit) +{ + tor_assert(commit); + + /* Put the commit to the global state. */ + state_query(SR_STATE_ACTION_PUT, SR_STATE_OBJ_COMMIT, + (void *) commit, NULL); + + log_debug(LD_DIR, "SR: Commit from %s has been added to our state.", + sr_commit_get_rsa_fpr(commit)); +} + +/* Remove all commits from our state. */ +void +sr_state_delete_commits(void) +{ + state_query(SR_STATE_ACTION_DEL_ALL, SR_STATE_OBJ_COMMIT, NULL, NULL); +} + +/* Copy the reveal information from <b>commit</b> into <b>saved_commit</b>. + * This <b>saved_commit</b> MUST come from our current SR state. Once modified, + * the disk state is updated. */ +void +sr_state_copy_reveal_info(sr_commit_t *saved_commit, const sr_commit_t *commit) +{ + tor_assert(saved_commit); + tor_assert(commit); + + saved_commit->reveal_ts = commit->reveal_ts; + memcpy(saved_commit->random_number, commit->random_number, + sizeof(saved_commit->random_number)); + + strlcpy(saved_commit->encoded_reveal, commit->encoded_reveal, + sizeof(saved_commit->encoded_reveal)); + state_query(SR_STATE_ACTION_SAVE, 0, NULL, NULL); + log_debug(LD_DIR, "SR: Reveal value learned %s (for commit %s) from %s", + saved_commit->encoded_reveal, saved_commit->encoded_commit, + sr_commit_get_rsa_fpr(saved_commit)); +} + +/* Set the fresh SRV flag from our state. This doesn't need to trigger a + * disk state synchronization so we directly change the state. */ +void +sr_state_set_fresh_srv(void) +{ + sr_state->is_srv_fresh = 1; +} + +/* Unset the fresh SRV flag from our state. This doesn't need to trigger a + * disk state synchronization so we directly change the state. */ +void +sr_state_unset_fresh_srv(void) +{ + sr_state->is_srv_fresh = 0; +} + +/* Return the value of the fresh SRV flag. */ +unsigned int +sr_state_srv_is_fresh(void) +{ + return sr_state->is_srv_fresh; +} + +/* Cleanup and free our disk and memory state. */ +void +sr_state_free_all(void) +{ + state_free(sr_state); + disk_state_free(sr_disk_state); + /* Nullify our global state. */ + sr_state = NULL; + sr_disk_state = NULL; +} + +/* Save our current state in memory to disk. */ +void +sr_state_save(void) +{ + /* Query a SAVE action on our current state so it's synced and saved. */ + state_query(SR_STATE_ACTION_SAVE, 0, NULL, NULL); +} + +/* Return 1 iff the state has been initialized that is it exists in memory. + * Return 0 otherwise. */ +int +sr_state_is_initialized(void) +{ + return sr_state == NULL ? 0 : 1; +} + +/* Initialize the disk and memory state. + * + * If save_to_disk is set to 1, the state is immediately saved to disk after + * creation else it's not thus only kept in memory. + * If read_from_disk is set to 1, we try to load the state from the disk and + * if not found, a new state is created. + * + * Return 0 on success else a negative value on error. */ +int +sr_state_init(int save_to_disk, int read_from_disk) +{ + int ret = -ENOENT; + time_t now = time(NULL); + + /* We shouldn't have those assigned. */ + tor_assert(sr_disk_state == NULL); + tor_assert(sr_state == NULL); + + /* First, try to load the state from disk. */ + if (read_from_disk) { + ret = disk_state_load_from_disk(); + } + + if (ret < 0) { + switch (-ret) { + case EINVAL: + /* We have a state on disk but it contains something we couldn't parse + * or an invalid entry in the state file. Let's remove it since it's + * obviously unusable and replace it by an new fresh state below. */ + case ENOENT: + { + /* No state on disk so allocate our states for the first time. */ + sr_state_t *new_state = state_new(default_fname, now); + sr_disk_state_t *new_disk_state = disk_state_new(now); + state_set(new_state); + /* It's important to set our disk state pointer since the save call + * below uses it to synchronized it with our memory state. */ + disk_state_set(new_disk_state); + /* No entry, let's save our new state to disk. */ + if (save_to_disk && disk_state_save_to_disk() < 0) { + goto error; + } + break; + } + default: + /* Big problem. Not possible. */ + tor_assert(0); + } + } + /* We have a state in memory, let's make sure it's updated for the current + * and next voting round. */ + { + time_t valid_after = voting_schedule_get_next_valid_after_time(); + sr_state_update(valid_after); + } + return 0; + + error: + return -1; +} + +#ifdef TOR_UNIT_TESTS + +/* Set the current phase of the protocol. Used only by unit tests. */ +void +set_sr_phase(sr_phase_t phase) +{ + tor_assert(sr_state); + sr_state->phase = phase; +} + +/* Get the SR state. Used only by unit tests */ +sr_state_t * +get_sr_state(void) +{ + return sr_state; +} + +#endif /* defined(TOR_UNIT_TESTS) */ + diff --git a/src/or/dirauth/shared_random_state.h b/src/or/dirauth/shared_random_state.h new file mode 100644 index 0000000000..60a326f86c --- /dev/null +++ b/src/or/dirauth/shared_random_state.h @@ -0,0 +1,147 @@ +/* Copyright (c) 2016-2017, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#ifndef TOR_SHARED_RANDOM_STATE_H +#define TOR_SHARED_RANDOM_STATE_H + +#include "shared_random.h" + +/* Action that can be performed on the state for any objects. */ +typedef enum { + SR_STATE_ACTION_GET = 1, + SR_STATE_ACTION_PUT = 2, + SR_STATE_ACTION_DEL = 3, + SR_STATE_ACTION_DEL_ALL = 4, + SR_STATE_ACTION_SAVE = 5, +} sr_state_action_t; + +/* Object in the state that can be queried through the state API. */ +typedef enum { + /* Will return a single commit using an authority identity key. */ + SR_STATE_OBJ_COMMIT, + /* Returns the entire list of commits from the state. */ + SR_STATE_OBJ_COMMITS, + /* Return the current SRV object pointer. */ + SR_STATE_OBJ_CURSRV, + /* Return the previous SRV object pointer. */ + SR_STATE_OBJ_PREVSRV, + /* Return the phase. */ + SR_STATE_OBJ_PHASE, + /* Get or Put the valid after time. */ + SR_STATE_OBJ_VALID_AFTER, +} sr_state_object_t; + +/* State of the protocol. It's also saved on disk in fname. This data + * structure MUST be synchronized at all time with the one on disk. */ +typedef struct sr_state_t { + /* Filename of the state file on disk. */ + char *fname; + /* Version of the protocol. */ + uint32_t version; + /* The valid-after of the voting period we have prepared the state for. */ + time_t valid_after; + /* Until when is this state valid? */ + time_t valid_until; + /* Protocol phase. */ + sr_phase_t phase; + + /* Number of runs completed. */ + uint64_t n_protocol_runs; + /* The number of commitment rounds we've performed in this protocol run. */ + unsigned int n_commit_rounds; + /* The number of reveal rounds we've performed in this protocol run. */ + unsigned int n_reveal_rounds; + + /* A map of all the received commitments for this protocol run. This is + * indexed by authority RSA identity digest. */ + digestmap_t *commits; + + /* Current and previous shared random value. */ + sr_srv_t *previous_srv; + sr_srv_t *current_srv; + + /* Indicate if the state contains an SRV that was _just_ generated. This is + * used during voting so that we know whether to use the super majority rule + * or not when deciding on keeping it for the consensus. It is _always_ set + * to 0 post consensus. + * + * EDGE CASE: if an authority computes a new SRV then immediately reboots + * and, once back up, votes for the current round, it won't know if the + * SRV is fresh or not ultimately making it _NOT_ use the super majority + * when deciding to put or not the SRV in the consensus. This is for now + * an acceptable very rare edge case. */ + unsigned int is_srv_fresh:1; +} sr_state_t; + +/* Persistent state of the protocol, as saved to disk. */ +typedef struct sr_disk_state_t { + uint32_t magic_; + /* Version of the protocol. */ + int Version; + /* Version of our running tor. */ + char *TorVersion; + /* Creation time of this state */ + time_t ValidAfter; + /* State valid until? */ + time_t ValidUntil; + /* All commits seen that are valid. */ + config_line_t *Commit; + /* Previous and current shared random value. */ + config_line_t *SharedRandValues; + /* Extra Lines for configuration we might not know. */ + config_line_t *ExtraLines; +} sr_disk_state_t; + +/* API */ + +/* Public methods: */ + +void sr_state_update(time_t valid_after); + +/* Private methods (only used by shared-random.c): */ + +void sr_state_set_valid_after(time_t valid_after); +sr_phase_t sr_state_get_phase(void); +const sr_srv_t *sr_state_get_previous_srv(void); +const sr_srv_t *sr_state_get_current_srv(void); +void sr_state_set_previous_srv(const sr_srv_t *srv); +void sr_state_set_current_srv(const sr_srv_t *srv); +void sr_state_clean_srvs(void); +digestmap_t *sr_state_get_commits(void); +sr_commit_t *sr_state_get_commit(const char *rsa_fpr); +void sr_state_add_commit(sr_commit_t *commit); +void sr_state_delete_commits(void); +void sr_state_copy_reveal_info(sr_commit_t *saved_commit, + const sr_commit_t *commit); +unsigned int sr_state_srv_is_fresh(void); +void sr_state_set_fresh_srv(void); +void sr_state_unset_fresh_srv(void); +int sr_state_init(int save_to_disk, int read_from_disk); +int sr_state_is_initialized(void); +void sr_state_save(void); +void sr_state_free_all(void); + +#ifdef SHARED_RANDOM_STATE_PRIVATE + +STATIC int disk_state_load_from_disk_impl(const char *fname); + +STATIC sr_phase_t get_sr_protocol_phase(time_t valid_after); + +STATIC time_t get_state_valid_until_time(time_t now); +STATIC const char *get_phase_str(sr_phase_t phase); +STATIC void reset_state_for_new_protocol_run(time_t valid_after); +STATIC void new_protocol_run(time_t valid_after); +STATIC void state_rotate_srv(void); +STATIC int is_phase_transition(sr_phase_t next_phase); + +#endif /* defined(SHARED_RANDOM_STATE_PRIVATE) */ + +#ifdef TOR_UNIT_TESTS + +STATIC void set_sr_phase(sr_phase_t phase); +STATIC sr_state_t *get_sr_state(void); + +#endif /* defined(TOR_UNIT_TESTS) */ + +#endif /* !defined(TOR_SHARED_RANDOM_STATE_H) */ + |