dircollate.c 9.9 KB

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