Tor  0.4.5.0-alpha-dev
dircollate.c
Go to the documentation of this file.
1 /* Copyright (c) 2001-2004, Roger Dingledine.
2  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
3  * Copyright (c) 2007-2020, 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
27 
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];
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
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
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
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
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,
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
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 */
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 
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
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);
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. */
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 }
tor_free
#define tor_free(p)
Definition: malloc.h:52
tor_free_
void tor_free_(void *mem)
Definition: malloc.c:227
dircollate.h
Header file for dircollate.c.
tor_assert
#define tor_assert(expr)
Definition: util_bug.h:102
ddmap_entry_set_digests
static void ddmap_entry_set_digests(ddmap_entry_t *ent, const uint8_t *rsa_sha1, const uint8_t *ed25519)
Definition: dircollate.c:84
ddmap_entry_t
Definition: dircollate.c:35
DIGESTMAP_FOREACH_END
#define DIGESTMAP_FOREACH_END
Definition: map.h:168
smartlist_add
void smartlist_add(smartlist_t *sl, void *element)
Definition: smartlist_core.c:117
smartlist_new
smartlist_t * smartlist_new(void)
Definition: smartlist_core.c:26
DIGEST_LEN
#define DIGEST_LEN
Definition: digest_sizes.h:20
ddmap_entry_new
static ddmap_entry_t * ddmap_entry_new(int n_votes)
Definition: dircollate.c:59
dirvote.h
Header file for dirvote.c.
dircollator_n_routers
int dircollator_n_routers(dircollator_t *dc)
Definition: dircollate.c:305
vote_routerstatus_st.h
Routerstatus (vote entry) structure.
dircollator_add_routerstatus
static void dircollator_add_routerstatus(dircollator_t *dc, int vote_num, networkstatus_t *vote, vote_routerstatus_t *vrs)
Definition: dircollate.c:105
vote_routerstatus_t::ed25519_id
uint8_t ed25519_id[ED25519_PUBKEY_LEN]
Definition: vote_routerstatus_st.h:42
vote_routerstatus_t
Definition: vote_routerstatus_st.h:18
dircollator_add_vote
void dircollator_add_vote(dircollator_t *dc, networkstatus_t *v)
Definition: dircollate.c:194
dircollator_free_
void dircollator_free_(dircollator_t *dc)
Definition: dircollate.c:166
dircollator_new
dircollator_t * dircollator_new(int n_votes, int n_authorities)
Definition: dircollate.c:149
DIGEST256_LEN
#define DIGEST256_LEN
Definition: digest_sizes.h:23
vote_routerstatus_t::has_ed25519_listing
unsigned int has_ed25519_listing
Definition: vote_routerstatus_st.h:33
ddmap_entry_hash
static unsigned ddmap_entry_hash(const ddmap_entry_t *ent)
Definition: dircollate.c:68
ddmap_entry_eq
static unsigned ddmap_entry_eq(const ddmap_entry_t *a, const ddmap_entry_t *b)
Definition: dircollate.c:76
smartlist_sort_digests
void smartlist_sort_digests(smartlist_t *sl)
Definition: smartlist.c:824
SMARTLIST_FOREACH_BEGIN
#define SMARTLIST_FOREACH_BEGIN(sl, type, var)
Definition: smartlist_foreach.h:78
ddmap_entry_free_
static void ddmap_entry_free_(ddmap_entry_t *e)
Definition: dircollate.c:51
dircollator_collate_by_ed25519
static void dircollator_collate_by_ed25519(dircollator_t *dc)
Definition: dircollate.c:239
vote_routerstatus_t::status
routerstatus_t status
Definition: vote_routerstatus_st.h:19
HT_PROTOTYPE
HT_PROTOTYPE(hs_circuitmap_ht, circuit_t, hs_circuitmap_node, hs_circuit_hash_token, hs_circuits_have_same_token)
dircollator_collate
void dircollator_collate(dircollator_t *dc, int consensus_method)
Definition: dircollate.c:211
vote_routerstatus_t::ed25519_reflects_consensus
unsigned int ed25519_reflects_consensus
Definition: vote_routerstatus_st.h:37
dircollator_get_votes_for_router
vote_routerstatus_t ** dircollator_get_votes_for_router(dircollator_t *dc, int idx)
Definition: dircollate.c:320
networkstatus_st.h
Networkstatus consensus/vote structure.
routerstatus_t::identity_digest
char identity_digest[DIGEST_LEN]
Definition: routerstatus_st.h:27
networkstatus_t
Definition: networkstatus_st.h:26
fast_memeq
#define fast_memeq(a, b, c)
Definition: di_ops.h:35
DIGESTMAP_FOREACH
#define DIGESTMAP_FOREACH(map, keyvar, valtype, valvar)
Definition: map.h:154