commit d4a6b1a4209f0b3995c0f61ad9cbe687e09a6fb0 Author: Nick Mathewson <nickm@torproject.org> Date: Thu Nov 13 10:03:55 2014 -0500 Implement ed25519 identity collation for voting. This is a new collator type that follows proposal 220 for deciding which identities to include. The rule is (approximately): If a <ed,rsa> identity is listed by more than half of authorities, include it. And include all <rsa> 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> has been listed, include it. --- src/or/dircollate.c | 149 ++++++++++++++++++++++++++++++++++++++++++++++++--- src/or/dircollate.h | 7 ++- src/or/dirvote.c | 2 +- src/or/or.h | 1 + 4 files changed, 150 insertions(+), 9 deletions(-) diff --git a/src/or/dircollate.c b/src/or/dircollate.c index 92f3dcc..20dfb35 100644 --- a/src/or/dircollate.c +++ b/src/or/dircollate.c @@ -12,9 +12,55 @@ #define DIRCOLLATE_PRIVATE #include "dircollate.h" +#include "dirvote.h" static void dircollator_collate_by_rsa(dircollator_t *dc); +static void dircollator_collate_by_ed25519(dircollator_t *dc); +typedef struct ddmap_entry_s { + HT_ENTRY(ddmap_entry_s) node; + uint8_t d[DIGEST_LEN + DIGEST256_LEN]; + vote_routerstatus_t *vrs_lst[FLEXIBLE_ARRAY_MEMBER]; +} ddmap_entry_t; + +struct double_digest_map_s *by_both_ids; + +static void +ddmap_entry_free(ddmap_entry_t *e) +{ + tor_free(e); +} + +static ddmap_entry_t * +ddmap_entry_new(int n_votes) +{ + return tor_malloc_zero(STRUCT_OFFSET(ddmap_entry_t, vrs_lst) + + sizeof(vote_routerstatus_t *) * n_votes); +} + +static unsigned +ddmap_entry_hash(const ddmap_entry_t *ent) +{ + return (unsigned) siphash24g(ent->d, sizeof(ent->d)); +} + +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)); +} + +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_); static void dircollator_add_routerstatus(dircollator_t *dc, int vote_num, @@ -29,7 +75,24 @@ dircollator_add_routerstatus(dircollator_t *dc, vrs_lst = tor_calloc(sizeof(vote_routerstatus_t *), dc->n_votes); 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 (tor_mem_is_zero((char*)ed, DIGEST256_LEN)) + return; + + 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; } @@ -45,6 +108,7 @@ dircollator_new(int n_votes, int n_authorities) dc->n_authorities = n_authorities; dc->by_rsa_sha1 = digestmap_new(); + HT_INIT(double_digest_map, &dc->by_both_ids); return dc; } @@ -55,8 +119,20 @@ 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_); + 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); } @@ -75,21 +151,80 @@ dircollator_add_vote(dircollator_t *dc, networkstatus_t *v) } void -dircollator_collate(dircollator_t *dc) +dircollator_collate(dircollator_t *dc, int consensus_method) { - dircollator_collate_by_rsa(dc); + tor_assert(!dc->is_collated); + dc->all_rsa_sha1_lst = smartlist_new(); + + if (consensus_method < MIN_METHOD_FOR_ED25519_ID_VOTING + 10/*XXX*/) + dircollator_collate_by_rsa(dc); + else + dircollator_collate_by_ed25519(dc); + + smartlist_sort_digests(dc->all_rsa_sha1_lst); + dc->is_collated = 1; } static void dircollator_collate_by_rsa(dircollator_t *dc) { - tor_assert(!dc->is_collated); + const int total_authorities = dc->n_authorities; - dc->all_rsa_sha1_lst = smartlist_new(); + DIGESTMAP_FOREACH(dc->by_rsa_sha1, k, vote_routerstatus_t **, vrs_lst) { + int n = 0, i; + for (i = 0; i < dc->n_votes; ++i) { + if (vrs_lst[i] != NULL) + ++n; + } + + if (n <= total_authorities / 2) + continue; + smartlist_add(dc->all_rsa_sha1_lst, (char *)k); + } DIGESTMAP_FOREACH_END; + + dc->by_collated_rsa_sha1 = dc->by_rsa_sha1; +} + +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; + + 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 (n <= total_authorities / 2) + continue; + + 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]; + } + } + + digestmap_set(rsa_digests, (char*)ent->d, ent->vrs_lst); + smartlist_add(dc->all_rsa_sha1_lst, ent->d); + } DIGESTMAP_FOREACH(dc->by_rsa_sha1, k, vote_routerstatus_t **, vrs_lst) { + if (digestmap_get(rsa_digests, k) != NULL) + continue; + int n = 0, i; for (i = 0; i < dc->n_votes; ++i) { if (vrs_lst[i] != NULL) @@ -99,11 +234,11 @@ dircollator_collate_by_rsa(dircollator_t *dc) if (n <= total_authorities / 2) continue; + digestmap_set(rsa_digests, k, vrs_lst); smartlist_add(dc->all_rsa_sha1_lst, (char *)k); } DIGESTMAP_FOREACH_END; - smartlist_sort_digests(dc->all_rsa_sha1_lst); - dc->is_collated = 1; + dc->by_collated_rsa_sha1 = rsa_digests; } int @@ -116,7 +251,7 @@ vote_routerstatus_t ** dircollator_get_votes_for_router(dircollator_t *dc, int idx) { tor_assert(idx < smartlist_len(dc->all_rsa_sha1_lst)); - return digestmap_get(dc->by_rsa_sha1, + return digestmap_get(dc->by_collated_rsa_sha1, smartlist_get(dc->all_rsa_sha1_lst, idx)); } diff --git a/src/or/dircollate.h b/src/or/dircollate.h index 073b611..9eba37a 100644 --- a/src/or/dircollate.h +++ b/src/or/dircollate.h @@ -21,13 +21,15 @@ dircollator_t *dircollator_new(int n_votes, int n_authorities); void dircollator_free(dircollator_t *obj); void dircollator_add_vote(dircollator_t *dc, networkstatus_t *v); -void dircollator_collate(dircollator_t *dc); +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; struct dircollator_s { /**DOCDOC */ int is_collated; @@ -36,6 +38,9 @@ struct dircollator_s { int next_vote_num; digestmap_t *by_rsa_sha1; + struct double_digest_map by_both_ids; + + digestmap_t *by_collated_rsa_sha1; smartlist_t *all_rsa_sha1_lst; }; diff --git a/src/or/dirvote.c b/src/or/dirvote.c index 6a70c13..549dec1 100644 --- a/src/or/dirvote.c +++ b/src/or/dirvote.c @@ -1502,7 +1502,7 @@ networkstatus_compute_consensus(smartlist_t *votes, dircollator_add_vote(collator, v); } SMARTLIST_FOREACH_END(v); - dircollator_collate(collator); + dircollator_collate(collator, consensus_method); /* Now go through all the votes */ flag_counts = tor_calloc(smartlist_len(flags), sizeof(int)); diff --git a/src/or/or.h b/src/or/or.h index a41a14e..b07a596 100644 --- a/src/or/or.h +++ b/src/or/or.h @@ -2357,6 +2357,7 @@ typedef struct vote_routerstatus_t { * running. */ unsigned int has_measured_bw:1; /**< The vote had a measured bw */ unsigned int has_ed25519_listing:1; /** DOCDOC */ + unsigned int ed25519_reflects_consensus:1; /** DOCDOC */ uint32_t measured_bw_kb; /**< Measured bandwidth (capacity) of the router */ /** The hash or hashes that the authority claims this microdesc has. */ vote_microdesc_hash_t *microdesc;