dircollate.c 11 KB

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