commit ca6ceec112f05ce68097429089ee428010c8b8d0 Author: David Goulet dgoulet@torproject.org Date: Tue May 3 11:21:17 2016 -0400
prop250: Put commits and SRVs in votes/consensus
This commit adds the commit(s) line in the vote as well as the SR values. It also has the mechanism to add the majority SRVs in the consensus.
Signed-off-by: George Kadianakis desnacked@riseup.net Signed-off-by: David Goulet dgoulet@torproject.org --- doc/tor.1.txt | 6 + src/or/config.c | 1 + src/or/dirvote.c | 22 +++- src/or/dirvote.h | 7 +- src/or/networkstatus.c | 10 ++ src/or/or.h | 21 ++++ src/or/shared_random.c | 301 +++++++++++++++++++++++++++++++++++++++++++++++++ src/or/shared_random.h | 9 +- 8 files changed, 372 insertions(+), 5 deletions(-)
diff --git a/doc/tor.1.txt b/doc/tor.1.txt index 65d3c2d..8508aaa 100644 --- a/doc/tor.1.txt +++ b/doc/tor.1.txt @@ -2225,6 +2225,12 @@ on the public Tor network. in a journal if it is new, or if it differs from the most recently accepted pinning for one of the keys it contains. (Default: 0)
+[[AuthDirSharedRandomness]] **AuthDirSharedRandomness** **0**|**1**:: + Authoritative directories only. Switch for the shared random protocol. + If zero, the authority won't participate in the protocol. If non-zero + (default), the flag "shared-rand-participate" is added to the authority + vote indicating participation in the protocol. (Default: 1) + [[BridgePassword]] **BridgePassword** __Password__:: If set, contains an HTTP authenticator that tells a bridge authority to serve all requested bridge information. Used by the (only partially diff --git a/src/or/config.c b/src/or/config.c index cdd4f10..e1a4473 100644 --- a/src/or/config.c +++ b/src/or/config.c @@ -439,6 +439,7 @@ static config_var_t option_vars_[] = { V(UseNTorHandshake, AUTOBOOL, "1"), V(User, STRING, NULL), V(UserspaceIOCPBuffers, BOOL, "0"), + V(AuthDirSharedRandomness, BOOL, "1"), OBSOLETE("V1AuthoritativeDirectory"), OBSOLETE("V2AuthoritativeDirectory"), VAR("V3AuthoritativeDirectory",BOOL, V3AuthoritativeDir, "0"), diff --git a/src/or/dirvote.c b/src/or/dirvote.c index a08f6ec..af093de 100644 --- a/src/or/dirvote.c +++ b/src/or/dirvote.c @@ -15,10 +15,12 @@ #include "policies.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 "shared_random_state.h"
/** * \file dirvote.c @@ -73,6 +75,7 @@ format_networkstatus_vote(crypto_pk_t *private_signing_key, char digest[DIGEST_LEN]; uint32_t addr; char *client_versions_line = NULL, *server_versions_line = NULL; + char *shared_random_vote_str = NULL; networkstatus_voter_info_t *voter; char *status = NULL;
@@ -114,6 +117,9 @@ format_networkstatus_vote(crypto_pk_t *private_signing_key, 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]; @@ -153,7 +159,8 @@ format_networkstatus_vote(crypto_pk_t *private_signing_key, "flag-thresholds %s\n" "params %s\n" "dir-source %s %s %s %s %d %d\n" - "contact %s\n", + "contact %s\n" + "%s", /* shared randomness information */ v3_ns->type == NS_TYPE_VOTE ? "vote" : "opinion", methods, published, va, fu, vu, @@ -166,12 +173,15 @@ format_networkstatus_vote(crypto_pk_t *private_signing_key, params, voter->nickname, fingerprint, voter->address, fmt_addr32(addr), voter->dir_port, voter->or_port, - voter->contact); + 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]; @@ -1300,6 +1310,14 @@ networkstatus_compute_consensus(smartlist_t *votes, smartlist_add(chunks, tor_strdup("\n")); }
+ if (consensus_method >= MIN_METHOD_FOR_SHARED_RANDOM) { + /* Add the shared random value. */ + char *srv_lines = sr_get_string_for_consensus(votes); + if (srv_lines != NULL) { + smartlist_add(chunks, srv_lines); + } + } + /* Sort the votes. */ smartlist_sort(votes, compare_votes_by_authority_id_); /* Add the authority sections. */ diff --git a/src/or/dirvote.h b/src/or/dirvote.h index f2080a5..4c563aa 100644 --- a/src/or/dirvote.h +++ b/src/or/dirvote.h @@ -55,7 +55,7 @@ #define MIN_SUPPORTED_CONSENSUS_METHOD 13
/** The highest consensus method that we currently support. */ -#define MAX_SUPPORTED_CONSENSUS_METHOD 22 +#define MAX_SUPPORTED_CONSENSUS_METHOD 23
/** Lowest consensus method where microdesc consensuses omit any entry * with no microdesc. */ @@ -90,10 +90,15 @@ * ed25519 identities in microdescriptors. (Broken; see * consensus_method_is_supported() for more info.) */ #define MIN_METHOD_FOR_ED25519_ID_IN_MD 21 + /** Lowest consensus method where authorities vote on ed25519 ids and ensure * ed25519 id consistency. */ #define MIN_METHOD_FOR_ED25519_ID_VOTING 22
+/** Lowest consensus method where authorities may include a shared random + * value(s). */ +#define MIN_METHOD_FOR_SHARED_RANDOM 23 + /** Default bandwidth to clip unmeasured bandwidths to using method >= * MIN_METHOD_TO_CLIP_UNMEASURED_BW. (This is not a consensus method; do not * get confused with the above macros.) */ diff --git a/src/or/networkstatus.c b/src/or/networkstatus.c index da51698..aabbfff 100644 --- a/src/or/networkstatus.c +++ b/src/or/networkstatus.c @@ -32,7 +32,9 @@ #include "router.h" #include "routerlist.h" #include "routerparse.h" +#include "shared_random.h" #include "transports.h" +#include "torcert.h"
/** Map from lowercase nickname to identity digest of named server, if any. */ static strmap_t *named_server_map = NULL; @@ -320,6 +322,14 @@ networkstatus_vote_free(networkstatus_t *ns)
digestmap_free(ns->desc_digest_map, NULL);
+ 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); + } + tor_free(ns->sr_info.previous_srv); + tor_free(ns->sr_info.current_srv); + memwipe(ns, 11, sizeof(*ns)); tor_free(ns); } diff --git a/src/or/or.h b/src/or/or.h index 5a19f9a..1b7f1a8 100644 --- a/src/or/or.h +++ b/src/or/or.h @@ -2505,6 +2505,18 @@ typedef struct networkstatus_voter_info_t { smartlist_t *sigs; } networkstatus_voter_info_t;
+typedef struct networkstatus_sr_info_t { + /* Indicate if the dirauth partitipates in the SR protocol with its vote. + * This is tied to the SR flag in the vote. */ + unsigned int participate:1; + /* Both vote and consensus: Current and previous SRV. If list is empty, + * this means none were found in either the consensus or vote. */ + struct sr_srv_t *previous_srv; + struct sr_srv_t *current_srv; + /* Vote only: List of commitments. */ + smartlist_t *commits; +} networkstatus_sr_info_t; + /** Enumerates the possible seriousness values of a networkstatus document. */ typedef enum { NS_TYPE_VOTE, @@ -2587,6 +2599,9 @@ typedef struct networkstatus_t { /** If present, a map from descriptor digest to elements of * routerstatus_list. */ digestmap_t *desc_digest_map; + + /** Contains the shared random protocol data from a vote or consensus. */ + networkstatus_sr_info_t sr_info; } networkstatus_t;
/** A set of signatures for a networkstatus consensus. Unless otherwise @@ -4480,6 +4495,12 @@ typedef struct {
/** Autobool: Do we try to retain capabilities if we can? */ int KeepBindCapabilities; + + /** Bool (default: 1): Switch for the shared random protocol. Only + * relevant to a directory authority. If off, the authority won't + * participate in the protocol. If on (default), a flag is added to the + * vote indicating participation. */ + int AuthDirSharedRandomness; } or_options_t;
/** Persistent state for an onion router, as saved to disk. */ diff --git a/src/or/shared_random.c b/src/or/shared_random.c index dd567bc..0f988af 100644 --- a/src/or/shared_random.c +++ b/src/or/shared_random.c @@ -14,12 +14,19 @@ #include "shared_random.h" #include "config.h" #include "confparse.h" +#include "dirvote.h" #include "networkstatus.h" #include "routerkeys.h" #include "router.h" #include "routerlist.h" #include "shared_random_state.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"; + /* Allocate a new commit object and initializing it with <b>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. */ @@ -307,6 +314,216 @@ compare_reveal_(const void **_a, const void **_b) 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 %s %s %s\n", + commit_ns_str, + crypto_digest_algorithm_get_name(commit->alg), + commit->rsa_identity_fpr, + 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 %s %s %s %s\n", + commit_ns_str, + crypto_digest_algorithm_get_name(commit->alg), + commit->rsa_identity_fpr, + 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, srv); + tor_asprintf(&srv_str, "%s %d %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 the number of required participants of the SR protocol. This is + * based on a consensus params. */ +static int +get_n_voters_for_srv_agreement(void) +{ + int num_dirauths = get_n_authorities(V3_DIRINFO); + /* If the params is not found, default value should always be the maximum + * number of trusted authorities. Let's not take any chances. */ + return networkstatus_get_param(NULL, "AuthDirNumSRVAgreements", + num_dirauths, 1, num_dirauths); +} + +/* 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. */ + int num_required_agreements = get_n_voters_for_srv_agreement(); + + if (n_agreements < num_required_agreements) { + log_notice(LD_DIR, "SR: New SRV didn't reach agreement [%d/%d]!", + n_agreements, num_required_agreements); + 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); +} + +/* 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); + + 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, 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; +} + /* Encode the given shared random value and put it in dst. Destination * buffer must be at least SR_SRV_VALUE_BASE64_LEN plus the NULL byte. */ void @@ -572,6 +789,90 @@ sr_parse_commit(const smartlist_t *args) return NULL; }
+/* 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(); + DIGESTMAP_FOREACH(state_commits, key, const sr_commit_t *, commit) { + char *line = get_vote_line_from_commit(commit, sr_state_get_phase()); + smartlist_add(chunks, line); + } DIGESTMAP_FOREACH_END; + + /* 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. */ +char * +sr_get_string_for_consensus(const smartlist_t *votes) +{ + 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; + } + + /* 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; +} + /* Initialize shared random subsystem. This MUST be called early in the boot * process of tor. Return 0 on success else -1 on error. */ int diff --git a/src/or/shared_random.h b/src/or/shared_random.h index 878bfbf..f1fbe27 100644 --- a/src/or/shared_random.h +++ b/src/or/shared_random.h @@ -101,13 +101,15 @@ typedef struct sr_commit_t {
int sr_init(int save_to_disk); void sr_save_and_cleanup(void); +sr_commit_t *sr_parse_commit(const smartlist_t *args); +sr_srv_t *sr_parse_srv(const smartlist_t *args); +char *sr_get_string_for_vote(void); +char *sr_get_string_for_consensus(const smartlist_t *votes); void sr_commit_free(sr_commit_t *commit); void sr_srv_encode(char *dst, const sr_srv_t *srv);
/* Private methods (only used by shared_random_state.c): */
-sr_commit_t *sr_parse_commit(const smartlist_t *args); -sr_srv_t *sr_parse_srv(const smartlist_t *args); void sr_compute_srv(void); sr_commit_t *sr_generate_our_commit(time_t timestamp, const authority_cert_t *my_rsa_cert); @@ -123,6 +125,9 @@ STATIC int reveal_decode(const char *encoded, sr_commit_t *commit);
STATIC int commit_has_reveal_value(const sr_commit_t *commit);
+STATIC sr_srv_t *get_majority_srv_from_votes(const smartlist_t *votes, + int current); + #endif /* SHARED_RANDOM_PRIVATE */
#endif /* TOR_SHARED_RANDOM_H */