Line data Source code
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 96 : ddmap_entry_free_(ddmap_entry_t *e)
52 : {
53 96 : tor_free(e);
54 96 : }
55 :
56 : /** Return a new empty ddmap_entry, with <b>n_votes</b> elements in
57 : * vrs_list. */
58 : static ddmap_entry_t *
59 96 : ddmap_entry_new(int n_votes)
60 : {
61 96 : 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 366 : ddmap_entry_hash(const ddmap_entry_t *ent)
69 : {
70 366 : 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 174 : ddmap_entry_eq(const ddmap_entry_t *a, const ddmap_entry_t *b)
77 : {
78 174 : 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 366 : ddmap_entry_set_digests(ddmap_entry_t *ent,
85 : const uint8_t *rsa_sha1,
86 : const uint8_t *ed25519)
87 : {
88 366 : memcpy(ent->d, rsa_sha1, DIGEST_LEN);
89 366 : memcpy(ent->d + DIGEST_LEN, ed25519, DIGEST256_LEN);
90 366 : }
91 :
92 3276 : HT_PROTOTYPE(double_digest_map, ddmap_entry_t, node, ddmap_entry_hash,
93 : ddmap_entry_eq);
94 48 : 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 270 : dircollator_add_routerstatus(dircollator_t *dc,
106 : int vote_num,
107 : networkstatus_t *vote,
108 : vote_routerstatus_t *vrs)
109 : {
110 270 : const char *id = vrs->status.identity_digest;
111 :
112 : /* Clear this flag; we might set it later during the voting process */
113 270 : vrs->ed25519_reflects_consensus = 0;
114 :
115 270 : (void) vote; // We don't currently need this.
116 :
117 : /* First, add this item to the appropriate RSA-SHA-Id array. */
118 270 : vote_routerstatus_t **vrs_lst = digestmap_get(dc->by_rsa_sha1, id);
119 270 : if (NULL == vrs_lst) {
120 96 : vrs_lst = tor_calloc(dc->n_votes, sizeof(vote_routerstatus_t *));
121 96 : digestmap_set(dc->by_rsa_sha1, id, vrs_lst);
122 : }
123 270 : tor_assert(vrs_lst[vote_num] == NULL);
124 270 : vrs_lst[vote_num] = vrs;
125 :
126 270 : const uint8_t *ed = vrs->ed25519_id;
127 :
128 270 : if (! vrs->has_ed25519_listing)
129 0 : return;
130 :
131 : /* Now add it to the appropriate <Ed,RSA-SHA-Id> array. */
132 270 : ddmap_entry_t search, *found;
133 270 : memset(&search, 0, sizeof(search));
134 270 : ddmap_entry_set_digests(&search, (const uint8_t *)id, ed);
135 270 : found = HT_FIND(double_digest_map, &dc->by_both_ids, &search);
136 270 : if (NULL == found) {
137 96 : found = ddmap_entry_new(dc->n_votes);
138 96 : ddmap_entry_set_digests(found, (const uint8_t *)id, ed);
139 96 : HT_INSERT(double_digest_map, &dc->by_both_ids, found);
140 : }
141 270 : vrs_lst = found->vrs_lst;
142 270 : tor_assert(vrs_lst[vote_num] == NULL);
143 270 : 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 24 : dircollator_new(int n_votes, int n_authorities)
150 : {
151 24 : dircollator_t *dc = tor_malloc_zero(sizeof(dircollator_t));
152 :
153 24 : tor_assert(n_votes <= n_authorities);
154 :
155 24 : dc->n_votes = n_votes;
156 24 : dc->n_authorities = n_authorities;
157 :
158 24 : dc->by_rsa_sha1 = digestmap_new();
159 24 : HT_INIT(double_digest_map, &dc->by_both_ids);
160 :
161 24 : return dc;
162 : }
163 :
164 : /** Release all storage held by <b>dc</b>. */
165 : void
166 24 : dircollator_free_(dircollator_t *dc)
167 : {
168 24 : if (!dc)
169 24 : return;
170 :
171 24 : if (dc->by_collated_rsa_sha1 != dc->by_rsa_sha1)
172 24 : digestmap_free(dc->by_collated_rsa_sha1, NULL);
173 :
174 24 : digestmap_free(dc->by_rsa_sha1, tor_free_);
175 24 : smartlist_free(dc->all_rsa_sha1_lst);
176 :
177 24 : ddmap_entry_t **e, **next, *this;
178 24 : for (e = HT_START(double_digest_map, &dc->by_both_ids);
179 120 : e != NULL; e = next) {
180 96 : this = *e;
181 96 : next = HT_NEXT_RMV(double_digest_map, &dc->by_both_ids, e);
182 96 : ddmap_entry_free(this);
183 : }
184 24 : HT_CLEAR(double_digest_map, &dc->by_both_ids);
185 :
186 24 : 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 72 : dircollator_add_vote(dircollator_t *dc, networkstatus_t *v)
195 : {
196 72 : tor_assert(v->type == NS_TYPE_VOTE);
197 72 : tor_assert(dc->next_vote_num < dc->n_votes);
198 72 : tor_assert(!dc->is_collated);
199 :
200 72 : const int votenum = dc->next_vote_num++;
201 :
202 342 : SMARTLIST_FOREACH_BEGIN(v->routerstatus_list, vote_routerstatus_t *, vrs) {
203 270 : dircollator_add_routerstatus(dc, votenum, v, vrs);
204 270 : } SMARTLIST_FOREACH_END(vrs);
205 72 : }
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 24 : dircollator_collate(dircollator_t *dc, int consensus_method)
212 : {
213 24 : (void) consensus_method;
214 :
215 24 : tor_assert(!dc->is_collated);
216 24 : dc->all_rsa_sha1_lst = smartlist_new();
217 :
218 24 : dircollator_collate_by_ed25519(dc);
219 :
220 24 : smartlist_sort_digests(dc->all_rsa_sha1_lst);
221 24 : dc->is_collated = 1;
222 24 : }
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 24 : dircollator_collate_by_ed25519(dircollator_t *dc)
240 : {
241 24 : const int total_authorities = dc->n_authorities;
242 24 : digestmap_t *rsa_digests = digestmap_new();
243 :
244 24 : ddmap_entry_t **iter;
245 :
246 : /* Go over all <ed,rsa> pairs */
247 120 : HT_FOREACH(iter, double_digest_map, &dc->by_both_ids) {
248 96 : ddmap_entry_t *ent = *iter;
249 96 : int n = 0, i;
250 384 : for (i = 0; i < dc->n_votes; ++i) {
251 288 : if (ent->vrs_lst[i] != NULL)
252 270 : ++n;
253 : }
254 :
255 : /* If not enough authorties listed this exact <ed,rsa> pair,
256 : * don't include it. */
257 96 : if (n <= total_authorities / 2)
258 6 : 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 180 : vote_routerstatus_t **vrs_lst2 = digestmap_get(dc->by_rsa_sha1,
263 90 : (char*)ent->d);
264 90 : tor_assert(vrs_lst2);
265 :
266 360 : for (i = 0; i < dc->n_votes; ++i) {
267 270 : if (ent->vrs_lst[i] != NULL) {
268 264 : ent->vrs_lst[i]->ed25519_reflects_consensus = 1;
269 6 : } else if (vrs_lst2[i] && ! vrs_lst2[i]->has_ed25519_listing) {
270 0 : ent->vrs_lst[i] = vrs_lst2[i];
271 : }
272 : }
273 :
274 : /* Record that we have seen this RSA digest. */
275 90 : digestmap_set(rsa_digests, (char*)ent->d, ent->vrs_lst);
276 90 : 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 120 : DIGESTMAP_FOREACH(dc->by_rsa_sha1, k, vote_routerstatus_t **, vrs_lst) {
283 96 : if (digestmap_get(rsa_digests, k) != NULL)
284 96 : continue; /* We already included this RSA digest */
285 :
286 : int n = 0, i;
287 24 : for (i = 0; i < dc->n_votes; ++i) {
288 18 : if (vrs_lst[i] != NULL)
289 6 : ++n;
290 : }
291 :
292 6 : if (n <= total_authorities / 2)
293 6 : continue; /* Not enough votes */
294 :
295 0 : digestmap_set(rsa_digests, k, vrs_lst);
296 0 : smartlist_add(dc->all_rsa_sha1_lst, (char *)k);
297 24 : } DIGESTMAP_FOREACH_END;
298 :
299 24 : dc->by_collated_rsa_sha1 = rsa_digests;
300 24 : }
301 :
302 : /** Return the total number of collated router entries. This function may
303 : * only be called after dircollator_collate. */
304 : int
305 24 : dircollator_n_routers(dircollator_t *dc)
306 : {
307 24 : tor_assert(dc->is_collated);
308 24 : 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 90 : dircollator_get_votes_for_router(dircollator_t *dc, int idx)
321 : {
322 90 : tor_assert(dc->is_collated);
323 90 : tor_assert(idx < smartlist_len(dc->all_rsa_sha1_lst));
324 180 : return digestmap_get(dc->by_collated_rsa_sha1,
325 90 : smartlist_get(dc->all_rsa_sha1_lst, idx));
326 : }
|
