dircollate.c 11 KB

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