dirvote.c 97.6 KB
Newer Older
1
2
/* Copyright (c) 2001-2004, Roger Dingledine.
 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
Karsten Loesing's avatar
Karsten Loesing committed
3
 * Copyright (c) 2007-2009, The Tor Project, Inc. */
4
5
/* See LICENSE for licensing information */

6
#define DIRVOTE_PRIVATE
7
8
9
10
#include "or.h"

/**
 * \file dirvote.c
11
 * \brief Functions to compute directory consensus, and schedule voting.
12
13
 **/

14
15
16
/** A consensus that we have built and are appending signatures to.  Once it's
 * time to publish it, it will become an active consensus if it accumulates
 * enough signatures. */
17
18
19
20
21
22
23
typedef struct pending_consensus_t {
  /** The body of the consensus that we're currently building.  Once we
   * have it built, it goes into dirserv.c */
  char *body;
  /** The parsed in-progress consensus document. */
  networkstatus_t *consensus;
} pending_consensus_t;
24
25

static int dirvote_add_signatures_to_all_pending_consensuses(
26
27
                       const char *detached_signatures_body,
                       const char **msg_out);
28
29
30
31
static int dirvote_add_signatures_to_pending_consensus(
                       pending_consensus_t *pc,
                       ns_detached_signatures_t *sigs,
                       const char **msg_out);
32
static char *list_v3_auth_ids(void);
33
34
static void dirvote_fetch_missing_votes(void);
static void dirvote_fetch_missing_signatures(void);
35
static int dirvote_perform_vote(void);
36
static void dirvote_clear_votes(int all_votes);
37
static int dirvote_compute_consensuses(void);
38
static int dirvote_publish_consensus(void);
39
static char *make_consensus_method_list(int low, int high, const char *sep);
40
41

/** The highest consensus method that we currently support. */
42
#define MAX_SUPPORTED_CONSENSUS_METHOD 8
43
44

#define MIN_METHOD_FOR_PARAMS 7
45

46
47
48
/** Lowest consensus method that generates microdescriptors */
#define MIN_METHOD_FOR_MICRODESC 8

49
/* =====
50
51
 * Voting
 * =====*/
52

53
54
55
/* Overestimated. */
#define MICRODESC_LINE_LEN 80

Roger Dingledine's avatar
emo teh    
Roger Dingledine committed
56
/** Return a new string containing the string representation of the vote in
57
58
59
60
 * <b>v3_ns</b>, signed with our v3 signing key <b>private_signing_key</b>.
 * For v3 authorities. */
char *
format_networkstatus_vote(crypto_pk_env_t *private_signing_key,
61
                          networkstatus_t *v3_ns)
62
{
63
64
65
66
67
68
69
70
71
72
73
74
75
76
  size_t len;
  char *status = NULL;
  const char *client_versions = NULL, *server_versions = NULL;
  char *outp, *endp;
  char fingerprint[FINGERPRINT_LEN+1];
  char ipaddr[INET_NTOA_BUF_LEN];
  char digest[DIGEST_LEN];
  struct in_addr in;
  uint32_t addr;
  routerlist_t *rl = router_get_routerlist();
  char *version_lines = NULL;
  networkstatus_voter_info_t *voter;

  tor_assert(private_signing_key);
77
  tor_assert(v3_ns->type == NS_TYPE_VOTE || v3_ns->type == NS_TYPE_OPINION);
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

  voter = smartlist_get(v3_ns->voters, 0);

  addr = voter->addr;
  in.s_addr = htonl(addr);
  tor_inet_ntoa(&in, ipaddr, sizeof(ipaddr));

  base16_encode(fingerprint, sizeof(fingerprint),
                v3_ns->cert->cache_info.identity_digest, DIGEST_LEN);
  client_versions = v3_ns->client_versions;
  server_versions = v3_ns->server_versions;

  if (client_versions || server_versions) {
    size_t v_len = 64;
    char *cp;
    if (client_versions)
      v_len += strlen(client_versions);
95
    if (server_versions)
96
97
98
99
100
101
102
103
104
105
106
107
108
      v_len += strlen(server_versions);
    version_lines = tor_malloc(v_len);
    cp = version_lines;
    if (client_versions) {
      tor_snprintf(cp, v_len-(cp-version_lines),
                   "client-versions %s\n", client_versions);
      cp += strlen(cp);
    }
    if (server_versions)
      tor_snprintf(cp, v_len-(cp-version_lines),
                   "server-versions %s\n", server_versions);
  } else {
    version_lines = tor_strdup("");
109
  }
110
111
112

  len = 8192;
  len += strlen(version_lines);
113
  len += (RS_ENTRY_LEN+MICRODESC_LINE_LEN)*smartlist_len(rl->routers);
114
115
116
117
118
119
120
121
122
  len += v3_ns->cert->cache_info.signed_descriptor_len;

  status = tor_malloc(len);
  {
    char published[ISO_TIME_LEN+1];
    char va[ISO_TIME_LEN+1];
    char fu[ISO_TIME_LEN+1];
    char vu[ISO_TIME_LEN+1];
    char *flags = smartlist_join_strings(v3_ns->known_flags, " ", 0, NULL);
123
    char *params;
124
    authority_cert_t *cert = v3_ns->cert;
125
    char *methods =
126
      make_consensus_method_list(1, MAX_SUPPORTED_CONSENSUS_METHOD, " ");
127
128
129
130
131
    format_iso_time(published, v3_ns->published);
    format_iso_time(va, v3_ns->valid_after);
    format_iso_time(fu, v3_ns->fresh_until);
    format_iso_time(vu, v3_ns->valid_until);

132
133
134
135
136
    if (v3_ns->net_params)
      params = smartlist_join_strings(v3_ns->net_params, " ", 0, NULL);
    else
      params = tor_strdup("");

137
138
139
    tor_assert(cert);
    tor_snprintf(status, len,
                 "network-status-version 3\n"
140
                 "vote-status %s\n"
141
                 "consensus-methods %s\n"
142
143
144
145
146
147
148
                 "published %s\n"
                 "valid-after %s\n"
                 "fresh-until %s\n"
                 "valid-until %s\n"
                 "voting-delay %d %d\n"
                 "%s" /* versions */
                 "known-flags %s\n"
149
                 "params %s\n"
150
151
                 "dir-source %s %s %s %s %d %d\n"
                 "contact %s\n",
152
                 v3_ns->type == NS_TYPE_VOTE ? "vote" : "opinion",
153
                 methods,
154
155
156
157
                 published, va, fu, vu,
                 v3_ns->vote_seconds, v3_ns->dist_seconds,
                 version_lines,
                 flags,
158
                 params,
159
                 voter->nickname, fingerprint, voter->address,
160
                 ipaddr, voter->dir_port, voter->or_port, voter->contact);
161

162
    tor_free(params);
163
    tor_free(flags);
164
    tor_free(methods);
165
166
    outp = status + strlen(status);
    endp = status + len;
167
168
169
170
171
172
173
174

    if (!tor_digest_is_zero(voter->legacy_id_digest)) {
      char fpbuf[HEX_DIGEST_LEN+1];
      base16_encode(fpbuf, sizeof(fpbuf), voter->legacy_id_digest, DIGEST_LEN);
      tor_snprintf(outp, endp-outp, "legacy-dir-key %s\n", fpbuf);
      outp += strlen(outp);
    }

175
176
177
178
179
    tor_assert(outp + cert->cache_info.signed_descriptor_len < endp);
    memcpy(outp, cert->cache_info.signed_descriptor_body,
           cert->cache_info.signed_descriptor_len);

    outp += cert->cache_info.signed_descriptor_len;
180
  }
181

182
183
184
  SMARTLIST_FOREACH_BEGIN(v3_ns->routerstatus_list, vote_routerstatus_t *,
                          vrs) {
    vote_microdesc_hash_t *h;
185
    if (routerstatus_format_entry(outp, endp-outp, &vrs->status,
186
                                  vrs->version, NS_V3_VOTE) < 0) {
187
188
189
190
      log_warn(LD_BUG, "Unable to print router status.");
      goto err;
    }
    outp += strlen(outp);
191
192
193
194
195
196
197
198
199
200

    for (h = vrs->microdesc; h; h = h->next) {
      size_t mlen = strlen(h->microdesc_hash_line);
      if (outp+mlen >= endp) {
        log_warn(LD_BUG, "Can't fit microdesc line in vote.");
      }
      memcpy(outp, h->microdesc_hash_line, mlen+1);
      outp += strlen(outp);
    }
  } SMARTLIST_FOREACH_END(vrs);
201
202
203
204
205
206

  {
    char signing_key_fingerprint[FINGERPRINT_LEN+1];
    if (tor_snprintf(outp, endp-outp, "directory-signature ")<0) {
      log_warn(LD_BUG, "Unable to start signature line.");
      goto err;
207
    }
208
    outp += strlen(outp);
209

210
211
212
213
214
215
216
217
218
219
220
    if (crypto_pk_get_fingerprint(private_signing_key,
                                  signing_key_fingerprint, 0)<0) {
      log_warn(LD_BUG, "Unable to get fingerprint for signing key");
      goto err;
    }
    if (tor_snprintf(outp, endp-outp, "%s %s\n", fingerprint,
                     signing_key_fingerprint)<0) {
      log_warn(LD_BUG, "Unable to end signature line.");
      goto err;
    }
    outp += strlen(outp);
221
222
  }

223
  if (router_get_networkstatus_v3_hash(status, digest, DIGEST_SHA1)<0)
224
225
    goto err;
  note_crypto_pk_op(SIGN_DIR);
226
  if (router_append_dirobj_signature(outp,endp-outp,digest, DIGEST_LEN,
227
228
229
230
                                     private_signing_key)<0) {
    log_warn(LD_BUG, "Unable to sign networkstatus vote.");
    goto err;
  }
231

232
  {
233
    networkstatus_t *v;
234
235
236
237
238
    if (!(v = networkstatus_parse_vote_from_string(status, NULL,
                                                   v3_ns->type))) {
      log_err(LD_BUG,"Generated a networkstatus %s we couldn't parse: "
              "<<%s>>",
              v3_ns->type == NS_TYPE_VOTE ? "vote" : "opinion", status);
239
240
241
242
243
244
245
246
247
248
249
250
      goto err;
    }
    networkstatus_vote_free(v);
  }

  goto done;

 err:
  tor_free(status);
 done:
  tor_free(version_lines);
  return status;
251
252
}

253
254
255
256
/* =====
 * Consensus generation
 * ===== */

257
/** Given a vote <b>vote</b> (not a consensus!), return its associated
258
 * networkstatus_voter_info_t. */
259
static networkstatus_voter_info_t *
260
get_voter(const networkstatus_t *vote)
261
262
{
  tor_assert(vote);
263
  tor_assert(vote->type == NS_TYPE_VOTE);
264
265
266
267
268
  tor_assert(vote->voters);
  tor_assert(smartlist_len(vote->voters) == 1);
  return smartlist_get(vote->voters, 0);
}

269
270
/** Return the signature made by <b>voter</b> using the algorithm
 * <b>alg</b>, or NULL if none is found. */
271
272
273
274
275
276
277
278
279
280
281
282
document_signature_t *
voter_get_sig_by_algorithm(const networkstatus_voter_info_t *voter,
                           digest_algorithm_t alg)
{
  if (!voter->sigs)
    return NULL;
  SMARTLIST_FOREACH(voter->sigs, document_signature_t *, sig,
    if (sig->alg == alg)
      return sig);
  return NULL;
}

283
284
285
/** Temporary structure used in constructing a list of dir-source entries
 * for a consensus.  One of these is generated for every vote, and one more
 * for every legacy key in each vote. */
286
typedef struct dir_src_ent_t {
287
288
289
290
291
  networkstatus_t *v;
  const char *digest;
  int is_legacy;
} dir_src_ent_t;

292
/** Helper for sorting networkstatus_t votes (not consensuses) by the
293
 * hash of their voters' identity digests. */
294
295
296
static int
_compare_votes_by_authority_id(const void **_a, const void **_b)
{
297
  const networkstatus_t *a = *_a, *b = *_b;
298
299
  return memcmp(get_voter(a)->identity_digest,
                get_voter(b)->identity_digest, DIGEST_LEN);
300
301
}

302
303
304
/** Helper: Compare the dir_src_ent_ts in *<b>_a</b> and *<b>_b</b> by
 * their identity digests, and return -1, 0, or 1 depending on their
 * ordering */
305
306
307
308
309
310
311
312
313
314
315
316
317
static int
_compare_dir_src_ents_by_authority_id(const void **_a, const void **_b)
{
  const dir_src_ent_t *a = *_a, *b = *_b;
  const networkstatus_voter_info_t *a_v = get_voter(a->v),
    *b_v = get_voter(b->v);
  const char *a_id, *b_id;
  a_id = a->is_legacy ? a_v->legacy_id_digest : a_v->identity_digest;
  b_id = b->is_legacy ? b_v->legacy_id_digest : b_v->identity_digest;

  return memcmp(a_id, b_id, DIGEST_LEN);
}

318
319
/** Given a sorted list of strings <b>in</b>, add every member to <b>out</b>
 * that occurs more than <b>min</b> times. */
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
static void
get_frequent_members(smartlist_t *out, smartlist_t *in, int min)
{
  char *cur = NULL;
  int count = 0;
  SMARTLIST_FOREACH(in, char *, cp,
  {
    if (cur && !strcmp(cp, cur)) {
      ++count;
    } else {
      if (count > min)
        smartlist_add(out, cur);
      cur = cp;
      count = 1;
    }
  });
  if (count > min)
    smartlist_add(out, cur);
}

340
/** Given a sorted list of strings <b>lst</b>, return the member that appears
341
 * most.  Break ties in favor of later-occurring members. */
342
343
#define get_most_frequent_member(lst)           \
  smartlist_get_most_frequent_string(lst)
344

345
346
347
/** Return 0 if and only if <b>a</b> and <b>b</b> are routerstatuses
 * that come from the same routerinfo, with the same derived elements.
 */
348
static int
349
compare_vote_rs(const vote_routerstatus_t *a, const vote_routerstatus_t *b)
350
351
{
  int r;
352
353
354
  if ((r = memcmp(a->status.identity_digest, b->status.identity_digest,
                  DIGEST_LEN)))
    return r;
355
356
357
  if ((r = memcmp(a->status.descriptor_digest, b->status.descriptor_digest,
                  DIGEST_LEN)))
    return r;
358
  if ((r = (int)(b->status.published_on - a->status.published_on)))
359
    return r;
360
361
  if ((r = strcmp(b->status.nickname, a->status.nickname)))
    return r;
362
363
  if ((r = (((int)b->status.addr) - ((int)a->status.addr))))
    return r;
364
365
366
367
368
369
370
  if ((r = (((int)b->status.or_port) - ((int)a->status.or_port))))
    return r;
  if ((r = (((int)b->status.dir_port) - ((int)a->status.dir_port))))
    return r;
  return 0;
}

371
/** Helper for sorting routerlists based on compare_vote_rs. */
372
static int
373
_compare_vote_rs(const void **_a, const void **_b)
374
375
{
  const vote_routerstatus_t *a = *_a, *b = *_b;
376
  return compare_vote_rs(a,b);
377
378
}

379
380
/** Given a list of vote_routerstatus_t, all for the same router identity,
 * return whichever is most frequent, breaking ties in favor of more
381
 * recently published vote_routerstatus_t and in case of ties there,
Nick Mathewson's avatar
Nick Mathewson committed
382
 * in favor of smaller descriptor digest.
383
 */
384
static vote_routerstatus_t *
385
386
compute_routerstatus_consensus(smartlist_t *votes, int consensus_method,
                               char *microdesc_digest256_out)
387
388
389
390
391
{
  vote_routerstatus_t *most = NULL, *cur = NULL;
  int most_n = 0, cur_n = 0;
  time_t most_published = 0;

392
393
394
395
  /* _compare_vote_rs() sorts the items by identity digest (all the same),
   * then by SD digest.  That way, if we have a tie that the published_on
   * date cannot tie, we use the descriptor with the smaller digest.
   */
396
  smartlist_sort(votes, _compare_vote_rs);
397
398
  SMARTLIST_FOREACH(votes, vote_routerstatus_t *, rs,
  {
399
    if (cur && !compare_vote_rs(cur, rs)) {
400
401
402
      ++cur_n;
    } else {
      if (cur_n > most_n ||
403
404
          (cur && cur_n == most_n &&
           cur->status.published_on > most_published)) {
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
        most = cur;
        most_n = cur_n;
        most_published = cur->status.published_on;
      }
      cur_n = 1;
      cur = rs;
    }
  });

  if (cur_n > most_n ||
      (cur && cur_n == most_n && cur->status.published_on > most_published)) {
    most = cur;
    most_n = cur_n;
    most_published = cur->status.published_on;
  }

  tor_assert(most);
422
423
424
425
426

  if (consensus_method >= MIN_METHOD_FOR_MICRODESC &&
      microdesc_digest256_out) {
    smartlist_t *digests = smartlist_create();
    const char *best_microdesc_digest;
427
    SMARTLIST_FOREACH_BEGIN(votes, vote_routerstatus_t *, rs) {
428
429
430
        char d[DIGEST256_LEN];
        if (compare_vote_rs(rs, most))
          continue;
431
432
        if (!vote_routerstatus_find_microdesc_hash(d, rs, consensus_method,
                                                   DIGEST_SHA256))
433
          smartlist_add(digests, tor_memdup(d, sizeof(d)));
434
    } SMARTLIST_FOREACH_END(rs);
435
436
437
438
439
440
441
442
    smartlist_sort_digests256(digests);
    best_microdesc_digest = smartlist_get_most_frequent_digest256(digests);
    if (best_microdesc_digest)
      memcpy(microdesc_digest256_out, best_microdesc_digest, DIGEST256_LEN);
    SMARTLIST_FOREACH(digests, char *, cp, tor_free(cp));
    smartlist_free(digests);
  }

443
444
445
  return most;
}

446
447
448
/** Given a list of strings in <b>lst</b>, set the <b>len_out</b>-byte digest
 * at <b>digest_out</b> to the hash of the concatenation of those strings,
 * computed with the algorithm <b>alg</b>. */
449
static void
450
451
hash_list_members(char *digest_out, size_t len_out,
                  smartlist_t *lst, digest_algorithm_t alg)
452
{
453
454
455
456
457
  crypto_digest_env_t *d;
  if (alg == DIGEST_SHA1)
    d = crypto_new_digest_env();
  else
    d = crypto_new_digest256_env(alg);
458
459
  SMARTLIST_FOREACH(lst, const char *, cp,
                    crypto_digest_add_bytes(d, cp, strlen(cp)));
460
  crypto_digest_get_digest(d, digest_out, len_out);
461
462
  crypto_free_digest_env(d);
}
463

464
465
466
/** Sorting helper: compare two strings based on their values as base-ten
 * positive integers. (Non-integers are treated as prior to all integers, and
 * compared lexically.) */
467
468
469
470
471
472
static int
_cmp_int_strings(const void **_a, const void **_b)
{
  const char *a = *_a, *b = *_b;
  int ai = (int)tor_parse_long(a, 10, 1, INT_MAX, NULL, NULL);
  int bi = (int)tor_parse_long(b, 10, 1, INT_MAX, NULL, NULL);
473
  if (ai<bi) {
474
    return -1;
475
476
477
  } else if (ai==bi) {
    if (ai == 0) /* Parsing failed. */
      return strcmp(a, b);
478
    return 0;
479
  } else {
480
    return 1;
481
  }
482
483
}

484
485
/** Given a list of networkstatus_t votes, determine and return the number of
 * the highest consensus method that is supported by 2/3 of the voters. */
486
487
488
489
490
491
492
493
494
static int
compute_consensus_method(smartlist_t *votes)
{
  smartlist_t *all_methods = smartlist_create();
  smartlist_t *acceptable_methods = smartlist_create();
  smartlist_t *tmp = smartlist_create();
  int min = (smartlist_len(votes) * 2) / 3;
  int n_ok;
  int result;
495
  SMARTLIST_FOREACH(votes, networkstatus_t *, vote,
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
  {
    tor_assert(vote->supported_methods);
    smartlist_add_all(tmp, vote->supported_methods);
    smartlist_sort(tmp, _cmp_int_strings);
    smartlist_uniq(tmp, _cmp_int_strings, NULL);
    smartlist_add_all(all_methods, tmp);
    smartlist_clear(tmp);
  });

  smartlist_sort(all_methods, _cmp_int_strings);
  get_frequent_members(acceptable_methods, all_methods, min);
  n_ok = smartlist_len(acceptable_methods);
  if (n_ok) {
    const char *best = smartlist_get(acceptable_methods, n_ok-1);
    result = (int)tor_parse_long(best, 10, 1, INT_MAX, NULL, NULL);
  } else {
    result = 1;
  }
  smartlist_free(tmp);
  smartlist_free(all_methods);
  smartlist_free(acceptable_methods);
  return result;
}

520
/** Return true iff <b>method</b> is a consensus method that we support. */
521
522
523
static int
consensus_method_is_supported(int method)
{
524
525
526
527
528
529
  return (method >= 1) && (method <= MAX_SUPPORTED_CONSENSUS_METHOD);
}

/** Return a newly allocated string holding the numbers between low and high
 * (inclusive) that are supported consensus methods. */
static char *
530
make_consensus_method_list(int low, int high, const char *separator)
531
532
533
534
535
536
537
538
539
540
541
542
543
{
  char *list;

  char b[32];
  int i;
  smartlist_t *lst;
  lst = smartlist_create();
  for (i = low; i <= high; ++i) {
    if (!consensus_method_is_supported(i))
      continue;
    tor_snprintf(b, sizeof(b), "%d", i);
    smartlist_add(lst, tor_strdup(b));
  }
544
  list = smartlist_join_strings(lst, separator, 0, NULL);
545
546
547
548
  tor_assert(list);
  SMARTLIST_FOREACH(lst, char *, cp, tor_free(cp));
  smartlist_free(lst);
  return list;
549
550
}

551
/** Helper: given <b>lst</b>, a list of version strings such that every
Nick Mathewson's avatar
Nick Mathewson committed
552
 * version appears once for every versioning voter who recommends it, return a
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
 * newly allocated string holding the resulting client-versions or
 * server-versions list. May change contents of <b>lst</b> */
static char *
compute_consensus_versions_list(smartlist_t *lst, int n_versioning)
{
  int min = n_versioning / 2;
  smartlist_t *good = smartlist_create();
  char *result;
  sort_version_list(lst, 0);
  get_frequent_members(good, lst, min);
  result = smartlist_join_strings(good, ",", 0, NULL);
  smartlist_free(good);
  return result;
}

568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
/** Helper: given a list of valid networkstatus_t, return a new string
 * containing the contents of the consensus network parameter set.
 */
/* private */ char *
dirvote_compute_params(smartlist_t *votes)
{
  int i;
  int32_t *vals;

  int cur_param_len;
  const char *cur_param;
  const char *eq;
  char *result;

  const int n_votes = smartlist_len(votes);
  smartlist_t *output;
  smartlist_t *param_list = smartlist_create();

  /* We require that the parameter lists in the votes are well-formed: that
     is, that their keywords are unique and sorted, and that their values are
     between INT32_MIN and INT32_MAX inclusive.  This should be guaranteed by
     the parsing code. */

  vals = tor_malloc(sizeof(int)*n_votes);

  SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
    if (!v->net_params)
      continue;
    smartlist_add_all(param_list, v->net_params);
  } SMARTLIST_FOREACH_END(v);

  if (smartlist_len(param_list) == 0) {
    tor_free(vals);
    smartlist_free(param_list);
    return NULL;
  }

  smartlist_sort_strings(param_list);
  i = 0;
  cur_param = smartlist_get(param_list, 0);
  eq = strchr(cur_param, '=');
  tor_assert(eq);
Sebastian Hahn's avatar
Sebastian Hahn committed
610
  cur_param_len = (int)(eq+1 - cur_param);
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637

  output = smartlist_create();

  SMARTLIST_FOREACH_BEGIN(param_list, const char *, param) {
    const char *next_param;
    int ok=0;
    eq = strchr(param, '=');
    tor_assert(i<n_votes);
    vals[i++] = (int32_t)
      tor_parse_long(eq+1, 10, INT32_MIN, INT32_MAX, &ok, NULL);
    tor_assert(ok);

    if (param_sl_idx+1 == smartlist_len(param_list))
      next_param = NULL;
    else
      next_param = smartlist_get(param_list, param_sl_idx+1);
    if (!next_param || strncmp(next_param, param, cur_param_len)) {
      /* We've reached the end of a series. */
      int32_t median = median_int32(vals, i);
      char *out_string = tor_malloc(64+cur_param_len);
      memcpy(out_string, param, cur_param_len);
      tor_snprintf(out_string+cur_param_len,64, "%ld", (long)median);
      smartlist_add(output, out_string);

      i = 0;
      if (next_param) {
        eq = strchr(next_param, '=');
Sebastian Hahn's avatar
Sebastian Hahn committed
638
        cur_param_len = (int)(eq+1 - next_param);
639
640
641
642
643
644
645
646
647
648
649
650
      }
    }
  } SMARTLIST_FOREACH_END(param);

  result = smartlist_join_strings(output, " ", 0, NULL);
  SMARTLIST_FOREACH(output, char *, cp, tor_free(cp));
  smartlist_free(output);
  smartlist_free(param_list);
  tor_free(vals);
  return result;
}

651
/** Given a list of vote networkstatus_t in <b>votes</b>, our public
652
653
654
 * authority <b>identity_key</b>, our private authority <b>signing_key</b>,
 * and the number of <b>total_authorities</b> that we believe exist in our
 * voting quorum, generate the text of a new v3 consensus vote, and return the
655
656
657
658
 * value in a newly allocated string.
 *
 * Note: this function DOES NOT check whether the votes are from
 * recognized authorities.   (dirvote_add_vote does that.) */
659
char *
660
networkstatus_compute_consensus(smartlist_t *votes,
661
                                int total_authorities,
662
                                crypto_pk_env_t *identity_key,
663
664
                                crypto_pk_env_t *signing_key,
                                const char *legacy_id_key_digest,
665
666
                                crypto_pk_env_t *legacy_signing_key,
                                consensus_flavor_t flavor)
667
668
{
  smartlist_t *chunks;
669
  char *result = NULL;
670
  int consensus_method;
671
672
673
674
  time_t valid_after, fresh_until, valid_until;
  int vote_seconds, dist_seconds;
  char *client_versions = NULL, *server_versions = NULL;
  smartlist_t *flags;
675
  const char *flavor_name;
676
677
678
679
  const routerstatus_format_type_t rs_format =
    flavor == FLAV_NS ? NS_V3_CONSENSUS : NS_V3_CONSENSUS_MICRODESC;

  tor_assert(flavor == FLAV_NS || flavor == FLAV_MICRODESC);
680
  tor_assert(total_authorities >= smartlist_len(votes));
681

682
683
  flavor_name = networkstatus_get_flavor_name(flavor);

684
685
686
687
688
689
  if (!smartlist_len(votes)) {
    log_warn(LD_DIR, "Can't compute a consensus from no votes.");
    return NULL;
  }
  flags = smartlist_create();

690
691
692
693
694
695
696
697
698
699
700
  consensus_method = compute_consensus_method(votes);
  if (consensus_method_is_supported(consensus_method)) {
    log_info(LD_DIR, "Generating consensus using method %d.",
             consensus_method);
  } else {
    log_warn(LD_DIR, "The other authorities will use consensus method %d, "
             "which I don't support.  Maybe I should upgrade!",
             consensus_method);
    consensus_method = 1;
  }

701
702
703
  /* Compute medians of time-related things, and figure out how many
   * routers we might need to talk about. */
  {
704
705
706
707
708
709
    int n_votes = smartlist_len(votes);
    time_t *va_times = tor_malloc(n_votes * sizeof(time_t));
    time_t *fu_times = tor_malloc(n_votes * sizeof(time_t));
    time_t *vu_times = tor_malloc(n_votes * sizeof(time_t));
    int *votesec_list = tor_malloc(n_votes * sizeof(int));
    int *distsec_list = tor_malloc(n_votes * sizeof(int));
710
711
712
    int n_versioning_clients = 0, n_versioning_servers = 0;
    smartlist_t *combined_client_versions = smartlist_create();
    smartlist_t *combined_server_versions = smartlist_create();
713

714
    SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
715
      tor_assert(v->type == NS_TYPE_VOTE);
716
717
718
719
720
      va_times[v_sl_idx] = v->valid_after;
      fu_times[v_sl_idx] = v->fresh_until;
      vu_times[v_sl_idx] = v->valid_until;
      votesec_list[v_sl_idx] = v->vote_seconds;
      distsec_list[v_sl_idx] = v->dist_seconds;
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
      if (v->client_versions) {
        smartlist_t *cv = smartlist_create();
        ++n_versioning_clients;
        smartlist_split_string(cv, v->client_versions, ",",
                               SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
        sort_version_list(cv, 1);
        smartlist_add_all(combined_client_versions, cv);
        smartlist_free(cv); /* elements get freed later. */
      }
      if (v->server_versions) {
        smartlist_t *sv = smartlist_create();
        ++n_versioning_servers;
        smartlist_split_string(sv, v->server_versions, ",",
                               SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
        sort_version_list(sv, 1);
        smartlist_add_all(combined_server_versions, sv);
        smartlist_free(sv); /* elements get freed later. */
      }
739
740
      SMARTLIST_FOREACH(v->known_flags, const char *, cp,
                        smartlist_add(flags, tor_strdup(cp)));
741
    } SMARTLIST_FOREACH_END(v);
742
743
744
745
746
    valid_after = median_time(va_times, n_votes);
    fresh_until = median_time(fu_times, n_votes);
    valid_until = median_time(vu_times, n_votes);
    vote_seconds = median_int(votesec_list, n_votes);
    dist_seconds = median_int(distsec_list, n_votes);
747

748
749
750
751
752
    tor_assert(valid_after+MIN_VOTE_INTERVAL <= fresh_until);
    tor_assert(fresh_until+MIN_VOTE_INTERVAL <= valid_until);
    tor_assert(vote_seconds >= MIN_VOTE_SECONDS);
    tor_assert(dist_seconds >= MIN_DIST_SECONDS);

753
754
755
756
757
758
759
760
761
    server_versions = compute_consensus_versions_list(combined_server_versions,
                                                      n_versioning_servers);
    client_versions = compute_consensus_versions_list(combined_client_versions,
                                                      n_versioning_clients);

    SMARTLIST_FOREACH(combined_server_versions, char *, cp, tor_free(cp));
    SMARTLIST_FOREACH(combined_client_versions, char *, cp, tor_free(cp));
    smartlist_free(combined_server_versions);
    smartlist_free(combined_client_versions);
762
763
764
765

    smartlist_sort_strings(flags);
    smartlist_uniq_strings(flags);

766
767
768
769
770
    tor_free(va_times);
    tor_free(fu_times);
    tor_free(vu_times);
    tor_free(votesec_list);
    tor_free(distsec_list);
771
772
773
774
775
776
777
778
779
780
781
782
783
784
  }

  chunks = smartlist_create();

  {
    char buf[1024];
    char va_buf[ISO_TIME_LEN+1], fu_buf[ISO_TIME_LEN+1],
      vu_buf[ISO_TIME_LEN+1];
    char *flaglist;
    format_iso_time(va_buf, valid_after);
    format_iso_time(fu_buf, fresh_until);
    format_iso_time(vu_buf, valid_until);
    flaglist = smartlist_join_strings(flags, " ", 0, NULL);

785
786
787
788
789
790
    tor_snprintf(buf, sizeof(buf), "network-status-version 3%s%s\n"
                 "vote-status consensus\n",
                 flavor == FLAV_NS ? "" : " ",
                 flavor == FLAV_NS ? "" : flavor_name);

    smartlist_add(chunks, tor_strdup(buf));
791
792
793
794
795
796
797

    if (consensus_method >= 2) {
      tor_snprintf(buf, sizeof(buf), "consensus-method %d\n",
                   consensus_method);
      smartlist_add(chunks, tor_strdup(buf));
    }

798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
    tor_snprintf(buf, sizeof(buf),
                 "valid-after %s\n"
                 "fresh-until %s\n"
                 "valid-until %s\n"
                 "voting-delay %d %d\n"
                 "client-versions %s\n"
                 "server-versions %s\n"
                 "known-flags %s\n",
                 va_buf, fu_buf, vu_buf,
                 vote_seconds, dist_seconds,
                 client_versions, server_versions, flaglist);
    smartlist_add(chunks, tor_strdup(buf));

    tor_free(flaglist);
  }

814
815
816
817
818
819
820
821
822
  if (consensus_method >= MIN_METHOD_FOR_PARAMS) {
    char *params = dirvote_compute_params(votes);
    if (params) {
      smartlist_add(chunks, tor_strdup("params "));
      smartlist_add(chunks, params);
      smartlist_add(chunks, tor_strdup("\n"));
    }
  }

823
824
825
826
  /* Sort the votes. */
  smartlist_sort(votes, _compare_votes_by_authority_id);
  /* Add the authority sections. */
  {
827
    smartlist_t *dir_sources = smartlist_create();
828
    SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
829
830
831
832
833
834
835
836
837
838
839
      dir_src_ent_t *e = tor_malloc_zero(sizeof(dir_src_ent_t));
      e->v = v;
      e->digest = get_voter(v)->identity_digest;
      e->is_legacy = 0;
      smartlist_add(dir_sources, e);
      if (consensus_method >= 3 &&
          !tor_digest_is_zero(get_voter(v)->legacy_id_digest)) {
        dir_src_ent_t *e_legacy = tor_malloc_zero(sizeof(dir_src_ent_t));
        e_legacy->v = v;
        e_legacy->digest = get_voter(v)->legacy_id_digest;
        e_legacy->is_legacy = 1;
840
        smartlist_add(dir_sources, e_legacy);
841
      }
842
    } SMARTLIST_FOREACH_END(v);
843
    smartlist_sort(dir_sources, _compare_dir_src_ents_by_authority_id);
844

845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
    SMARTLIST_FOREACH(dir_sources, const dir_src_ent_t *, e,
    {
      char buf[1024];
      struct in_addr in;
      char ip[INET_NTOA_BUF_LEN];
      char fingerprint[HEX_DIGEST_LEN+1];
      char votedigest[HEX_DIGEST_LEN+1];
      networkstatus_t *v = e->v;
      networkstatus_voter_info_t *voter = get_voter(v);

      if (e->is_legacy)
        tor_assert(consensus_method >= 2);

      in.s_addr = htonl(voter->addr);
      tor_inet_ntoa(&in, ip, sizeof(ip));
      base16_encode(fingerprint, sizeof(fingerprint), e->digest, DIGEST_LEN);
      base16_encode(votedigest, sizeof(votedigest), voter->vote_digest,
                    DIGEST_LEN);

      tor_snprintf(buf, sizeof(buf),
                   "dir-source %s%s %s %s %s %d %d\n",
                   voter->nickname, e->is_legacy ? "-legacy" : "",
                   fingerprint, voter->address, ip,
                   voter->dir_port,
                   voter->or_port);
      smartlist_add(chunks, tor_strdup(buf));
      if (! e->is_legacy) {
        tor_snprintf(buf, sizeof(buf),
                     "contact %s\n"
                     "vote-digest %s\n",
                     voter->contact,
                     votedigest);
        smartlist_add(chunks, tor_strdup(buf));
      }
    });
    SMARTLIST_FOREACH(dir_sources, dir_src_ent_t *, e, tor_free(e));
    smartlist_free(dir_sources);
  }
883
884
885

  /* Add the actual router entries. */
  {
886
887
888
889
    int *index; /* index[j] is the current index into votes[j]. */
    int *size; /* size[j] is the number of routerstatuses in votes[j]. */
    int *flag_counts; /* The number of voters that list flag[j] for the
                       * currently considered router. */
890
891
892
893
    int i;
    smartlist_t *matching_descs = smartlist_create();
    smartlist_t *chosen_flags = smartlist_create();
    smartlist_t *versions = smartlist_create();
894
    smartlist_t *exitsummaries = smartlist_create();
Peter Palfrader's avatar
Peter Palfrader committed
895
    uint32_t *bandwidths = tor_malloc(sizeof(uint32_t) * smartlist_len(votes));
896
897
    uint32_t *measured_bws = tor_malloc(sizeof(uint32_t) *
                                        smartlist_len(votes));
Peter Palfrader's avatar
Peter Palfrader committed
898
    int num_bandwidths;
899
    int num_mbws;
900
901
902
903
904
905
906

    int *n_voter_flags; /* n_voter_flags[j] is the number of flags that
                         * votes[j] knows about. */
    int *n_flag_voters; /* n_flag_voters[f] is the number of votes that care
                         * about flags[f]. */
    int **flag_map; /* flag_map[j][b] is an index f such that flag_map[f]
                     * is the same flag as votes[j]->known_flags[b]. */
907
    int *named_flag; /* Index of the flag "Named" for votes[j] */
908
    int *unnamed_flag; /* Index of the flag "Unnamed" for votes[j] */
909
910
911
912
913
914
915
    int chosen_named_idx, chosen_unnamed_idx;

    strmap_t *name_to_id_map = strmap_new();
    char conflict[DIGEST_LEN];
    char unknown[DIGEST_LEN];
    memset(conflict, 0, sizeof(conflict));
    memset(unknown, 0xff, sizeof(conflict));
916
917
918
919
920
921

    index = tor_malloc_zero(sizeof(int)*smartlist_len(votes));
    size = tor_malloc_zero(sizeof(int)*smartlist_len(votes));
    n_voter_flags = tor_malloc_zero(sizeof(int) * smartlist_len(votes));
    n_flag_voters = tor_malloc_zero(sizeof(int) * smartlist_len(flags));
    flag_map = tor_malloc_zero(sizeof(int*) * smartlist_len(votes));
922
923
    named_flag = tor_malloc_zero(sizeof(int) * smartlist_len(votes));
    unnamed_flag = tor_malloc_zero(sizeof(int) * smartlist_len(votes));
924
    for (i = 0; i < smartlist_len(votes); ++i)
925
      unnamed_flag[i] = named_flag[i] = -1;
926
927
928
929
    chosen_named_idx = smartlist_string_pos(flags, "Named");
    chosen_unnamed_idx = smartlist_string_pos(flags, "Unnamed");

    /* Build the flag index. */
930
    SMARTLIST_FOREACH(votes, networkstatus_t *, v,
931
    {
932
933
      flag_map[v_sl_idx] = tor_malloc_zero(
                           sizeof(int)*smartlist_len(v->known_flags));
934
935
936
      SMARTLIST_FOREACH(v->known_flags, const char *, fl,
      {
        int p = smartlist_string_pos(flags, fl);
937
        tor_assert(p >= 0);
938
        flag_map[v_sl_idx][fl_sl_idx] = p;
939
        ++n_flag_voters[p];
940
941
        if (!strcmp(fl, "Named"))
          named_flag[v_sl_idx] = fl_sl_idx;
942
        if (!strcmp(fl, "Unnamed"))
943
          unnamed_flag[v_sl_idx] = fl_sl_idx;
944
945
      });
      n_voter_flags[v_sl_idx] = smartlist_len(v->known_flags);
946
947
948
      size[v_sl_idx] = smartlist_len(v->routerstatus_list);
    });

949
950
    /* Named and Unnamed get treated specially */
    if (consensus_method >= 2) {
951
      SMARTLIST_FOREACH(votes, networkstatus_t *, v,
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
      {
        uint64_t nf;
        if (named_flag[v_sl_idx]<0)
          continue;
        nf = U64_LITERAL(1) << named_flag[v_sl_idx];
        SMARTLIST_FOREACH(v->routerstatus_list, vote_routerstatus_t *, rs,
        {
          if ((rs->flags & nf) != 0) {
            const char *d = strmap_get_lc(name_to_id_map, rs->status.nickname);
            if (!d) {
              /* We have no name officially mapped to this digest. */
              strmap_set_lc(name_to_id_map, rs->status.nickname,
                            rs->status.identity_digest);
            } else if (d != conflict &&
                memcmp(d, rs->status.identity_digest, DIGEST_LEN)) {
              /* Authorities disagree about this nickname. */
              strmap_set_lc(name_to_id_map, rs->status.nickname, conflict);
            } else {
              /* It's already a conflict, or it's already this ID. */
            }
          }
        });
      });
975
      SMARTLIST_FOREACH(votes, networkstatus_t *, v,
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
      {
        uint64_t uf;
        if (unnamed_flag[v_sl_idx]<0)
          continue;
        uf = U64_LITERAL(1) << unnamed_flag[v_sl_idx];
        SMARTLIST_FOREACH(v->routerstatus_list, vote_routerstatus_t *, rs,
        {
          if ((rs->flags & uf) != 0) {
            const char *d = strmap_get_lc(name_to_id_map, rs->status.nickname);
            if (d == conflict || d == unknown) {
              /* Leave it alone; we know what it is. */
            } else if (!d) {
              /* We have no name officially mapped to this digest. */
              strmap_set_lc(name_to_id_map, rs->status.nickname, unknown);
            } else if (!memcmp(d, rs->status.identity_digest, DIGEST_LEN)) {
              /* Authorities disagree about this nickname. */
              strmap_set_lc(name_to_id_map, rs->status.nickname, conflict);
            } else {
              /* It's mapped to a different name. */
            }
          }
        });
      });
    }