dircollate.c 11 KB

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