src/feature/dirauth/dircollate.c

   1 /* Copyright (c) 2001-2004, Roger Dingledine.
   2  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
   3  * Copyright (c) 2007-2021, 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
  25 #include "feature/dirauth/dircollate.h"
  26 #include "feature/dirauth/dirvote.h"
  27
  28 #include "feature/nodelist/networkstatus_st.h"
  29 #include "feature/nodelist/vote_routerstatus_st.h"
  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];
  44 } ddmap_entry_t;
  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
  51 ddmap_entry_free_(ddmap_entry_t *e)
  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
  68 ddmap_entry_hash(const ddmap_entry_t *ent)
  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
  76 ddmap_entry_eq(const ddmap_entry_t *a, const ddmap_entry_t *b)
  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
  84 ddmap_entry_set_digests(ddmap_entry_t *ent,
  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,
  93              ddmap_entry_eq);
  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
 105 dircollator_add_routerstatus(dircollator_t *dc,
 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 */
 113   vrs->ed25519_reflects_consensus = 0;
 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
 218   dircollator_collate_by_ed25519(dc);
 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
 239 dircollator_collate_by_ed25519(dircollator_t *dc)
 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);
 297   } DIGESTMAP_FOREACH_END;
 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. */
 319 vote_routerstatus_t **
 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 }