dircollate.c (10754B)
1 /* Copyright (c) 2001-2004, Roger Dingledine. 2 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. 3 * Copyright (c) 2007-2021, The Tor Project, Inc. */ 4 /* See LICENSE for licensing information */ 5 6 /** 7 * \file dircollate.c 8 * 9 * \brief Collation code for figuring out which identities to vote for in 10 * the directory voting process. 11 * 12 * During the consensus calculation, when an authority is looking at the vote 13 * documents from all the authorities, it needs to compute the consensus for 14 * each relay listed by at least one authority. But the notion of "each 15 * relay" can be tricky: some relays have Ed25519 keys, and others don't. 16 * 17 * Moreover, older consensus methods did RSA-based ID collation alone, and 18 * ignored Ed25519 keys. We need to support those too until we're completely 19 * sure that authorities will never downgrade. 20 * 21 * This module is invoked exclusively from dirvote.c. 22 */ 23 24 #define DIRCOLLATE_PRIVATE 25 #include "feature/dirauth/dircollate.h" 26 #include "feature/dirauth/dirvote.h" 27 28 #include "feature/nodelist/networkstatus_st.h" 29 #include "feature/nodelist/vote_routerstatus_st.h" 30 31 static void dircollator_collate_by_ed25519(dircollator_t *dc); 32 33 /** Hashtable entry mapping a pair of digests (actually an ed25519 key and an 34 * RSA SHA1 digest) to an array of vote_routerstatus_t. */ 35 typedef struct ddmap_entry_t { 36 HT_ENTRY(ddmap_entry_t) node; 37 /** A SHA1-RSA1024 identity digest and Ed25519 identity key, 38 * concatenated. (If there is no ed25519 identity key, there is no 39 * entry in this table.) */ 40 uint8_t d[DIGEST_LEN + DIGEST256_LEN]; 41 /* The nth member of this array corresponds to the vote_routerstatus_t (if 42 * any) received for this digest pair from the nth voter. */ 43 vote_routerstatus_t *vrs_lst[FLEXIBLE_ARRAY_MEMBER]; 44 } ddmap_entry_t; 45 46 #define ddmap_entry_free(e) \ 47 FREE_AND_NULL(ddmap_entry_t, ddmap_entry_free_, (e)) 48 49 /** Release all storage held by e. */ 50 static void 51 ddmap_entry_free_(ddmap_entry_t *e) 52 { 53 tor_free(e); 54 } 55 56 /** Return a new empty ddmap_entry, with <b>n_votes</b> elements in 57 * vrs_list. */ 58 static ddmap_entry_t * 59 ddmap_entry_new(int n_votes) 60 { 61 return tor_malloc_zero(offsetof(ddmap_entry_t, vrs_lst) + 62 sizeof(vote_routerstatus_t *) * n_votes); 63 } 64 65 /** Helper: compute a hash of a single ddmap_entry_t's identity (or 66 * identities) */ 67 static unsigned 68 ddmap_entry_hash(const ddmap_entry_t *ent) 69 { 70 return (unsigned) siphash24g(ent->d, sizeof(ent->d)); 71 } 72 73 /** Helper: return true if <b>a</b> and <b>b</b> have the same 74 * identity/identities. */ 75 static unsigned 76 ddmap_entry_eq(const ddmap_entry_t *a, const ddmap_entry_t *b) 77 { 78 return fast_memeq(a->d, b->d, sizeof(a->d)); 79 } 80 81 /** Record the RSA identity of <b>ent</b> as <b>rsa_sha1</b>, and the 82 * ed25519 identity as <b>ed25519</b>. Both must be provided. */ 83 static void 84 ddmap_entry_set_digests(ddmap_entry_t *ent, 85 const uint8_t *rsa_sha1, 86 const uint8_t *ed25519) 87 { 88 memcpy(ent->d, rsa_sha1, DIGEST_LEN); 89 memcpy(ent->d + DIGEST_LEN, ed25519, DIGEST256_LEN); 90 } 91 92 HT_PROTOTYPE(double_digest_map, ddmap_entry_t, node, ddmap_entry_hash, 93 ddmap_entry_eq); 94 HT_GENERATE2(double_digest_map, ddmap_entry_t, node, ddmap_entry_hash, 95 ddmap_entry_eq, 0.6, tor_reallocarray, tor_free_); 96 97 /** Helper: add a single vote_routerstatus_t <b>vrs</b> to the collator 98 * <b>dc</b>, indexing it by its RSA key digest, and by the 2-tuple of its RSA 99 * key digest and Ed25519 key. It must come from the <b>vote_num</b>th 100 * vote. 101 * 102 * Requires that the vote is well-formed -- that is, that it has no duplicate 103 * routerstatus entries. We already checked for that when parsing the vote. */ 104 static void 105 dircollator_add_routerstatus(dircollator_t *dc, 106 int vote_num, 107 networkstatus_t *vote, 108 vote_routerstatus_t *vrs) 109 { 110 const char *id = vrs->status.identity_digest; 111 112 /* Clear this flag; we might set it later during the voting process */ 113 vrs->ed25519_reflects_consensus = 0; 114 115 (void) vote; // We don't currently need this. 116 117 /* First, add this item to the appropriate RSA-SHA-Id array. */ 118 vote_routerstatus_t **vrs_lst = digestmap_get(dc->by_rsa_sha1, id); 119 if (NULL == vrs_lst) { 120 vrs_lst = tor_calloc(dc->n_votes, sizeof(vote_routerstatus_t *)); 121 digestmap_set(dc->by_rsa_sha1, id, vrs_lst); 122 } 123 tor_assert(vrs_lst[vote_num] == NULL); 124 vrs_lst[vote_num] = vrs; 125 126 const uint8_t *ed = vrs->ed25519_id; 127 128 if (! vrs->has_ed25519_listing) 129 return; 130 131 /* Now add it to the appropriate <Ed,RSA-SHA-Id> array. */ 132 ddmap_entry_t search, *found; 133 memset(&search, 0, sizeof(search)); 134 ddmap_entry_set_digests(&search, (const uint8_t *)id, ed); 135 found = HT_FIND(double_digest_map, &dc->by_both_ids, &search); 136 if (NULL == found) { 137 found = ddmap_entry_new(dc->n_votes); 138 ddmap_entry_set_digests(found, (const uint8_t *)id, ed); 139 HT_INSERT(double_digest_map, &dc->by_both_ids, found); 140 } 141 vrs_lst = found->vrs_lst; 142 tor_assert(vrs_lst[vote_num] == NULL); 143 vrs_lst[vote_num] = vrs; 144 } 145 146 /** Create and return a new dircollator object to use when collating 147 * <b>n_votes</b> out of a total of <b>n_authorities</b>. */ 148 dircollator_t * 149 dircollator_new(int n_votes, int n_authorities) 150 { 151 dircollator_t *dc = tor_malloc_zero(sizeof(dircollator_t)); 152 153 tor_assert(n_votes <= n_authorities); 154 155 dc->n_votes = n_votes; 156 dc->n_authorities = n_authorities; 157 158 dc->by_rsa_sha1 = digestmap_new(); 159 HT_INIT(double_digest_map, &dc->by_both_ids); 160 161 return dc; 162 } 163 164 /** Release all storage held by <b>dc</b>. */ 165 void 166 dircollator_free_(dircollator_t *dc) 167 { 168 if (!dc) 169 return; 170 171 if (dc->by_collated_rsa_sha1 != dc->by_rsa_sha1) 172 digestmap_free(dc->by_collated_rsa_sha1, NULL); 173 174 digestmap_free(dc->by_rsa_sha1, tor_free_); 175 smartlist_free(dc->all_rsa_sha1_lst); 176 177 ddmap_entry_t **e, **next, *this; 178 for (e = HT_START(double_digest_map, &dc->by_both_ids); 179 e != NULL; e = next) { 180 this = *e; 181 next = HT_NEXT_RMV(double_digest_map, &dc->by_both_ids, e); 182 ddmap_entry_free(this); 183 } 184 HT_CLEAR(double_digest_map, &dc->by_both_ids); 185 186 tor_free(dc); 187 } 188 189 /** Add a single vote <b>v</b> to a dircollator <b>dc</b>. This function must 190 * be called exactly once for each vote to be used in the consensus. It may 191 * only be called before dircollator_collate(). 192 */ 193 void 194 dircollator_add_vote(dircollator_t *dc, networkstatus_t *v) 195 { 196 tor_assert(v->type == NS_TYPE_VOTE); 197 tor_assert(dc->next_vote_num < dc->n_votes); 198 tor_assert(!dc->is_collated); 199 200 const int votenum = dc->next_vote_num++; 201 202 SMARTLIST_FOREACH_BEGIN(v->routerstatus_list, vote_routerstatus_t *, vrs) { 203 dircollator_add_routerstatus(dc, votenum, v, vrs); 204 } SMARTLIST_FOREACH_END(vrs); 205 } 206 207 /** Sort the entries in <b>dc</b> according to <b>consensus_method</b>, so 208 * that the consensus process can iterate over them with 209 * dircollator_n_routers() and dircollator_get_votes_for_router(). */ 210 void 211 dircollator_collate(dircollator_t *dc, int consensus_method) 212 { 213 (void) consensus_method; 214 215 tor_assert(!dc->is_collated); 216 dc->all_rsa_sha1_lst = smartlist_new(); 217 218 dircollator_collate_by_ed25519(dc); 219 220 smartlist_sort_digests(dc->all_rsa_sha1_lst); 221 dc->is_collated = 1; 222 } 223 224 /** 225 * Collation function for ed25519 consensuses: collate the votes for each 226 * entry in <b>dc</b> by ed25519 key and by RSA key. 227 * 228 * The rule is, approximately: 229 * If a (ed,rsa) identity is listed by more than half of authorities, 230 * include it. And include all (rsa)-only votes about that node as 231 * matching. 232 * 233 * Otherwise, if an (*,rsa) or (rsa) identity is listed by more than 234 * half of the authorities, and no (ed,rsa) pair for the same RSA key 235 * has been already been included based on the rule above, include 236 * that RSA identity. 237 */ 238 static void 239 dircollator_collate_by_ed25519(dircollator_t *dc) 240 { 241 const int total_authorities = dc->n_authorities; 242 digestmap_t *rsa_digests = digestmap_new(); 243 244 ddmap_entry_t **iter; 245 246 /* Go over all <ed,rsa> pairs */ 247 HT_FOREACH(iter, double_digest_map, &dc->by_both_ids) { 248 ddmap_entry_t *ent = *iter; 249 int n = 0, i; 250 for (i = 0; i < dc->n_votes; ++i) { 251 if (ent->vrs_lst[i] != NULL) 252 ++n; 253 } 254 255 /* If not enough authorties listed this exact <ed,rsa> pair, 256 * don't include it. */ 257 if (n <= total_authorities / 2) 258 continue; 259 260 /* Now consider whether there are any other entries with the same 261 * RSA key (but with possibly different or missing ed value). */ 262 vote_routerstatus_t **vrs_lst2 = digestmap_get(dc->by_rsa_sha1, 263 (char*)ent->d); 264 tor_assert(vrs_lst2); 265 266 for (i = 0; i < dc->n_votes; ++i) { 267 if (ent->vrs_lst[i] != NULL) { 268 ent->vrs_lst[i]->ed25519_reflects_consensus = 1; 269 } else if (vrs_lst2[i] && ! vrs_lst2[i]->has_ed25519_listing) { 270 ent->vrs_lst[i] = vrs_lst2[i]; 271 } 272 } 273 274 /* Record that we have seen this RSA digest. */ 275 digestmap_set(rsa_digests, (char*)ent->d, ent->vrs_lst); 276 smartlist_add(dc->all_rsa_sha1_lst, ent->d); 277 } 278 279 /* Now look over all entries with an RSA digest, looking for RSA digests 280 * we didn't put in yet. 281 */ 282 DIGESTMAP_FOREACH(dc->by_rsa_sha1, k, vote_routerstatus_t **, vrs_lst) { 283 if (digestmap_get(rsa_digests, k) != NULL) 284 continue; /* We already included this RSA digest */ 285 286 int n = 0, i; 287 for (i = 0; i < dc->n_votes; ++i) { 288 if (vrs_lst[i] != NULL) 289 ++n; 290 } 291 292 if (n <= total_authorities / 2) 293 continue; /* Not enough votes */ 294 295 digestmap_set(rsa_digests, k, vrs_lst); 296 smartlist_add(dc->all_rsa_sha1_lst, (char *)k); 297 } DIGESTMAP_FOREACH_END; 298 299 dc->by_collated_rsa_sha1 = rsa_digests; 300 } 301 302 /** Return the total number of collated router entries. This function may 303 * only be called after dircollator_collate. */ 304 int 305 dircollator_n_routers(dircollator_t *dc) 306 { 307 tor_assert(dc->is_collated); 308 return smartlist_len(dc->all_rsa_sha1_lst); 309 } 310 311 /** Return an array of vote_routerstatus_t entries for the <b>idx</b>th router 312 * in the collation order. Each array contains n_votes elements, where the 313 * nth element of the array is the vote_routerstatus_t from the nth voter for 314 * this identity (or NULL if there is no such entry). 315 * 316 * The maximum value for <b>idx</b> is dircollator_n_routers(). 317 * 318 * This function may only be called after dircollator_collate. */ 319 vote_routerstatus_t ** 320 dircollator_get_votes_for_router(dircollator_t *dc, int idx) 321 { 322 tor_assert(dc->is_collated); 323 tor_assert(idx < smartlist_len(dc->all_rsa_sha1_lst)); 324 return digestmap_get(dc->by_collated_rsa_sha1, 325 smartlist_get(dc->all_rsa_sha1_lst, idx)); 326 }