1 /* Copyright (c) 2001-2004, Roger Dingledine.
2 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
3 * Copyright (c) 2007-2011, The Tor Project, Inc. */
4 /* See LICENSE for licensing information */
6 #define DIRVOTE_PRIVATE
12 #include "microdesc.h"
13 #include "networkstatus.h"
17 #include "routerlist.h"
18 #include "routerparse.h"
22 * \brief Functions to compute directory consensus, and schedule voting.
25 /** A consensus that we have built and are appending signatures to. Once it's
26 * time to publish it, it will become an active consensus if it accumulates
27 * enough signatures. */
28 typedef struct pending_consensus_t
{
29 /** The body of the consensus that we're currently building. Once we
30 * have it built, it goes into dirserv.c */
32 /** The parsed in-progress consensus document. */
33 networkstatus_t
*consensus
;
34 } pending_consensus_t
;
36 static int dirvote_add_signatures_to_all_pending_consensuses(
37 const char *detached_signatures_body
,
38 const char **msg_out
);
39 static int dirvote_add_signatures_to_pending_consensus(
40 pending_consensus_t
*pc
,
41 ns_detached_signatures_t
*sigs
,
42 const char **msg_out
);
43 static char *list_v3_auth_ids(void);
44 static void dirvote_fetch_missing_votes(void);
45 static void dirvote_fetch_missing_signatures(void);
46 static int dirvote_perform_vote(void);
47 static void dirvote_clear_votes(int all_votes
);
48 static int dirvote_compute_consensuses(void);
49 static int dirvote_publish_consensus(void);
50 static char *make_consensus_method_list(int low
, int high
, const char *sep
);
52 /** The highest consensus method that we currently support. */
53 #define MAX_SUPPORTED_CONSENSUS_METHOD 11
55 /** Lowest consensus method that contains a 'directory-footer' marker */
56 #define MIN_METHOD_FOR_FOOTER 9
58 /** Lowest consensus method that contains bandwidth weights */
59 #define MIN_METHOD_FOR_BW_WEIGHTS 9
61 /** Lowest consensus method that contains consensus params */
62 #define MIN_METHOD_FOR_PARAMS 7
64 /** Lowest consensus method that generates microdescriptors */
65 #define MIN_METHOD_FOR_MICRODESC 8
72 #define MICRODESC_LINE_LEN 80
74 /** Return a new string containing the string representation of the vote in
75 * <b>v3_ns</b>, signed with our v3 signing key <b>private_signing_key</b>.
76 * For v3 authorities. */
78 format_networkstatus_vote(crypto_pk_env_t
*private_signing_key
,
79 networkstatus_t
*v3_ns
)
83 const char *client_versions
= NULL
, *server_versions
= NULL
;
85 char fingerprint
[FINGERPRINT_LEN
+1];
86 char ipaddr
[INET_NTOA_BUF_LEN
];
87 char digest
[DIGEST_LEN
];
90 routerlist_t
*rl
= router_get_routerlist();
91 char *version_lines
= NULL
;
93 networkstatus_voter_info_t
*voter
;
95 tor_assert(private_signing_key
);
96 tor_assert(v3_ns
->type
== NS_TYPE_VOTE
|| v3_ns
->type
== NS_TYPE_OPINION
);
98 voter
= smartlist_get(v3_ns
->voters
, 0);
101 in
.s_addr
= htonl(addr
);
102 tor_inet_ntoa(&in
, ipaddr
, sizeof(ipaddr
));
104 base16_encode(fingerprint
, sizeof(fingerprint
),
105 v3_ns
->cert
->cache_info
.identity_digest
, DIGEST_LEN
);
106 client_versions
= v3_ns
->client_versions
;
107 server_versions
= v3_ns
->server_versions
;
109 if (client_versions
|| server_versions
) {
113 v_len
+= strlen(client_versions
);
115 v_len
+= strlen(server_versions
);
116 version_lines
= tor_malloc(v_len
);
118 if (client_versions
) {
119 r
= tor_snprintf(cp
, v_len
-(cp
-version_lines
),
120 "client-versions %s\n", client_versions
);
122 log_err(LD_BUG
, "Insufficient memory for client-versions line");
127 if (server_versions
) {
128 r
= tor_snprintf(cp
, v_len
-(cp
-version_lines
),
129 "server-versions %s\n", server_versions
);
131 log_err(LD_BUG
, "Insufficient memory for server-versions line");
136 version_lines
= tor_strdup("");
140 len
+= strlen(version_lines
);
141 len
+= (RS_ENTRY_LEN
+MICRODESC_LINE_LEN
)*smartlist_len(rl
->routers
);
142 len
+= strlen("\ndirectory-footer\n");
143 len
+= v3_ns
->cert
->cache_info
.signed_descriptor_len
;
145 status
= tor_malloc(len
);
147 char published
[ISO_TIME_LEN
+1];
148 char va
[ISO_TIME_LEN
+1];
149 char fu
[ISO_TIME_LEN
+1];
150 char vu
[ISO_TIME_LEN
+1];
151 char *flags
= smartlist_join_strings(v3_ns
->known_flags
, " ", 0, NULL
);
153 authority_cert_t
*cert
= v3_ns
->cert
;
155 make_consensus_method_list(1, MAX_SUPPORTED_CONSENSUS_METHOD
, " ");
156 format_iso_time(published
, v3_ns
->published
);
157 format_iso_time(va
, v3_ns
->valid_after
);
158 format_iso_time(fu
, v3_ns
->fresh_until
);
159 format_iso_time(vu
, v3_ns
->valid_until
);
161 if (v3_ns
->net_params
)
162 params
= smartlist_join_strings(v3_ns
->net_params
, " ", 0, NULL
);
164 params
= tor_strdup("");
167 r
= tor_snprintf(status
, len
,
168 "network-status-version 3\n"
170 "consensus-methods %s\n"
175 "voting-delay %d %d\n"
179 "dir-source %s %s %s %s %d %d\n"
181 v3_ns
->type
== NS_TYPE_VOTE
? "vote" : "opinion",
183 published
, va
, fu
, vu
,
184 v3_ns
->vote_seconds
, v3_ns
->dist_seconds
,
188 voter
->nickname
, fingerprint
, voter
->address
,
189 ipaddr
, voter
->dir_port
, voter
->or_port
, voter
->contact
);
192 log_err(LD_BUG
, "Insufficient memory for network status line");
199 outp
= status
+ strlen(status
);
202 if (!tor_digest_is_zero(voter
->legacy_id_digest
)) {
203 char fpbuf
[HEX_DIGEST_LEN
+1];
204 base16_encode(fpbuf
, sizeof(fpbuf
), voter
->legacy_id_digest
, DIGEST_LEN
);
205 r
= tor_snprintf(outp
, endp
-outp
, "legacy-dir-key %s\n", fpbuf
);
207 log_err(LD_BUG
, "Insufficient memory for legacy-dir-key line");
210 outp
+= strlen(outp
);
213 tor_assert(outp
+ cert
->cache_info
.signed_descriptor_len
< endp
);
214 memcpy(outp
, cert
->cache_info
.signed_descriptor_body
,
215 cert
->cache_info
.signed_descriptor_len
);
217 outp
+= cert
->cache_info
.signed_descriptor_len
;
220 SMARTLIST_FOREACH_BEGIN(v3_ns
->routerstatus_list
, vote_routerstatus_t
*,
222 vote_microdesc_hash_t
*h
;
223 if (routerstatus_format_entry(outp
, endp
-outp
, &vrs
->status
,
224 vrs
->version
, NS_V3_VOTE
) < 0) {
225 log_warn(LD_BUG
, "Unable to print router status.");
228 outp
+= strlen(outp
);
230 for (h
= vrs
->microdesc
; h
; h
= h
->next
) {
231 size_t mlen
= strlen(h
->microdesc_hash_line
);
232 if (outp
+mlen
>= endp
) {
233 log_warn(LD_BUG
, "Can't fit microdesc line in vote.");
235 memcpy(outp
, h
->microdesc_hash_line
, mlen
+1);
236 outp
+= strlen(outp
);
238 } SMARTLIST_FOREACH_END(vrs
);
240 r
= tor_snprintf(outp
, endp
-outp
, "directory-footer\n");
242 log_err(LD_BUG
, "Insufficient memory for directory-footer line");
245 outp
+= strlen(outp
);
248 char signing_key_fingerprint
[FINGERPRINT_LEN
+1];
249 if (tor_snprintf(outp
, endp
-outp
, "directory-signature ")<0) {
250 log_warn(LD_BUG
, "Unable to start signature line.");
253 outp
+= strlen(outp
);
255 if (crypto_pk_get_fingerprint(private_signing_key
,
256 signing_key_fingerprint
, 0)<0) {
257 log_warn(LD_BUG
, "Unable to get fingerprint for signing key");
260 if (tor_snprintf(outp
, endp
-outp
, "%s %s\n", fingerprint
,
261 signing_key_fingerprint
)<0) {
262 log_warn(LD_BUG
, "Unable to end signature line.");
265 outp
+= strlen(outp
);
268 if (router_get_networkstatus_v3_hash(status
, digest
, DIGEST_SHA1
)<0)
270 note_crypto_pk_op(SIGN_DIR
);
271 if (router_append_dirobj_signature(outp
,endp
-outp
,digest
, DIGEST_LEN
,
272 private_signing_key
)<0) {
273 log_warn(LD_BUG
, "Unable to sign networkstatus vote.");
279 if (!(v
= networkstatus_parse_vote_from_string(status
, NULL
,
281 log_err(LD_BUG
,"Generated a networkstatus %s we couldn't parse: "
283 v3_ns
->type
== NS_TYPE_VOTE
? "vote" : "opinion", status
);
286 networkstatus_vote_free(v
);
294 tor_free(version_lines
);
299 * Consensus generation
302 /** Given a vote <b>vote</b> (not a consensus!), return its associated
303 * networkstatus_voter_info_t. */
304 static networkstatus_voter_info_t
*
305 get_voter(const networkstatus_t
*vote
)
308 tor_assert(vote
->type
== NS_TYPE_VOTE
);
309 tor_assert(vote
->voters
);
310 tor_assert(smartlist_len(vote
->voters
) == 1);
311 return smartlist_get(vote
->voters
, 0);
314 /** Return the signature made by <b>voter</b> using the algorithm
315 * <b>alg</b>, or NULL if none is found. */
316 document_signature_t
*
317 voter_get_sig_by_algorithm(const networkstatus_voter_info_t
*voter
,
318 digest_algorithm_t alg
)
322 SMARTLIST_FOREACH(voter
->sigs
, document_signature_t
*, sig
,
328 /** Temporary structure used in constructing a list of dir-source entries
329 * for a consensus. One of these is generated for every vote, and one more
330 * for every legacy key in each vote. */
331 typedef struct dir_src_ent_t
{
337 /** Helper for sorting networkstatus_t votes (not consensuses) by the
338 * hash of their voters' identity digests. */
340 _compare_votes_by_authority_id(const void **_a
, const void **_b
)
342 const networkstatus_t
*a
= *_a
, *b
= *_b
;
343 return memcmp(get_voter(a
)->identity_digest
,
344 get_voter(b
)->identity_digest
, DIGEST_LEN
);
347 /** Helper: Compare the dir_src_ent_ts in *<b>_a</b> and *<b>_b</b> by
348 * their identity digests, and return -1, 0, or 1 depending on their
351 _compare_dir_src_ents_by_authority_id(const void **_a
, const void **_b
)
353 const dir_src_ent_t
*a
= *_a
, *b
= *_b
;
354 const networkstatus_voter_info_t
*a_v
= get_voter(a
->v
),
355 *b_v
= get_voter(b
->v
);
356 const char *a_id
, *b_id
;
357 a_id
= a
->is_legacy
? a_v
->legacy_id_digest
: a_v
->identity_digest
;
358 b_id
= b
->is_legacy
? b_v
->legacy_id_digest
: b_v
->identity_digest
;
360 return memcmp(a_id
, b_id
, DIGEST_LEN
);
363 /** Given a sorted list of strings <b>in</b>, add every member to <b>out</b>
364 * that occurs more than <b>min</b> times. */
366 get_frequent_members(smartlist_t
*out
, smartlist_t
*in
, int min
)
370 SMARTLIST_FOREACH(in
, char *, cp
,
372 if (cur
&& !strcmp(cp
, cur
)) {
376 smartlist_add(out
, cur
);
382 smartlist_add(out
, cur
);
385 /** Given a sorted list of strings <b>lst</b>, return the member that appears
386 * most. Break ties in favor of later-occurring members. */
387 #define get_most_frequent_member(lst) \
388 smartlist_get_most_frequent_string(lst)
390 /** Return 0 if and only if <b>a</b> and <b>b</b> are routerstatuses
391 * that come from the same routerinfo, with the same derived elements.
394 compare_vote_rs(const vote_routerstatus_t
*a
, const vote_routerstatus_t
*b
)
397 if ((r
= memcmp(a
->status
.identity_digest
, b
->status
.identity_digest
,
400 if ((r
= memcmp(a
->status
.descriptor_digest
, b
->status
.descriptor_digest
,
403 if ((r
= (int)(b
->status
.published_on
- a
->status
.published_on
)))
405 if ((r
= strcmp(b
->status
.nickname
, a
->status
.nickname
)))
407 if ((r
= (((int)b
->status
.addr
) - ((int)a
->status
.addr
))))
409 if ((r
= (((int)b
->status
.or_port
) - ((int)a
->status
.or_port
))))
411 if ((r
= (((int)b
->status
.dir_port
) - ((int)a
->status
.dir_port
))))
416 /** Helper for sorting routerlists based on compare_vote_rs. */
418 _compare_vote_rs(const void **_a
, const void **_b
)
420 const vote_routerstatus_t
*a
= *_a
, *b
= *_b
;
421 return compare_vote_rs(a
,b
);
424 /** Given a list of vote_routerstatus_t, all for the same router identity,
425 * return whichever is most frequent, breaking ties in favor of more
426 * recently published vote_routerstatus_t and in case of ties there,
427 * in favor of smaller descriptor digest.
429 static vote_routerstatus_t
*
430 compute_routerstatus_consensus(smartlist_t
*votes
, int consensus_method
,
431 char *microdesc_digest256_out
)
433 vote_routerstatus_t
*most
= NULL
, *cur
= NULL
;
434 int most_n
= 0, cur_n
= 0;
435 time_t most_published
= 0;
437 /* _compare_vote_rs() sorts the items by identity digest (all the same),
438 * then by SD digest. That way, if we have a tie that the published_on
439 * date cannot tie, we use the descriptor with the smaller digest.
441 smartlist_sort(votes
, _compare_vote_rs
);
442 SMARTLIST_FOREACH(votes
, vote_routerstatus_t
*, rs
,
444 if (cur
&& !compare_vote_rs(cur
, rs
)) {
447 if (cur_n
> most_n
||
448 (cur
&& cur_n
== most_n
&&
449 cur
->status
.published_on
> most_published
)) {
452 most_published
= cur
->status
.published_on
;
459 if (cur_n
> most_n
||
460 (cur
&& cur_n
== most_n
&& cur
->status
.published_on
> most_published
)) {
463 most_published
= cur
->status
.published_on
;
468 if (consensus_method
>= MIN_METHOD_FOR_MICRODESC
&&
469 microdesc_digest256_out
) {
470 smartlist_t
*digests
= smartlist_create();
471 const char *best_microdesc_digest
;
472 SMARTLIST_FOREACH_BEGIN(votes
, vote_routerstatus_t
*, rs
) {
473 char d
[DIGEST256_LEN
];
474 if (compare_vote_rs(rs
, most
))
476 if (!vote_routerstatus_find_microdesc_hash(d
, rs
, consensus_method
,
478 smartlist_add(digests
, tor_memdup(d
, sizeof(d
)));
479 } SMARTLIST_FOREACH_END(rs
);
480 smartlist_sort_digests256(digests
);
481 best_microdesc_digest
= smartlist_get_most_frequent_digest256(digests
);
482 if (best_microdesc_digest
)
483 memcpy(microdesc_digest256_out
, best_microdesc_digest
, DIGEST256_LEN
);
484 SMARTLIST_FOREACH(digests
, char *, cp
, tor_free(cp
));
485 smartlist_free(digests
);
491 /** Given a list of strings in <b>lst</b>, set the <b>len_out</b>-byte digest
492 * at <b>digest_out</b> to the hash of the concatenation of those strings,
493 * computed with the algorithm <b>alg</b>. */
495 hash_list_members(char *digest_out
, size_t len_out
,
496 smartlist_t
*lst
, digest_algorithm_t alg
)
498 crypto_digest_env_t
*d
;
499 if (alg
== DIGEST_SHA1
)
500 d
= crypto_new_digest_env();
502 d
= crypto_new_digest256_env(alg
);
503 SMARTLIST_FOREACH(lst
, const char *, cp
,
504 crypto_digest_add_bytes(d
, cp
, strlen(cp
)));
505 crypto_digest_get_digest(d
, digest_out
, len_out
);
506 crypto_free_digest_env(d
);
509 /** Sorting helper: compare two strings based on their values as base-ten
510 * positive integers. (Non-integers are treated as prior to all integers, and
511 * compared lexically.) */
513 _cmp_int_strings(const void **_a
, const void **_b
)
515 const char *a
= *_a
, *b
= *_b
;
516 int ai
= (int)tor_parse_long(a
, 10, 1, INT_MAX
, NULL
, NULL
);
517 int bi
= (int)tor_parse_long(b
, 10, 1, INT_MAX
, NULL
, NULL
);
521 if (ai
== 0) /* Parsing failed. */
529 /** Given a list of networkstatus_t votes, determine and return the number of
530 * the highest consensus method that is supported by 2/3 of the voters. */
532 compute_consensus_method(smartlist_t
*votes
)
534 smartlist_t
*all_methods
= smartlist_create();
535 smartlist_t
*acceptable_methods
= smartlist_create();
536 smartlist_t
*tmp
= smartlist_create();
537 int min
= (smartlist_len(votes
) * 2) / 3;
540 SMARTLIST_FOREACH(votes
, networkstatus_t
*, vote
,
542 tor_assert(vote
->supported_methods
);
543 smartlist_add_all(tmp
, vote
->supported_methods
);
544 smartlist_sort(tmp
, _cmp_int_strings
);
545 smartlist_uniq(tmp
, _cmp_int_strings
, NULL
);
546 smartlist_add_all(all_methods
, tmp
);
547 smartlist_clear(tmp
);
550 smartlist_sort(all_methods
, _cmp_int_strings
);
551 get_frequent_members(acceptable_methods
, all_methods
, min
);
552 n_ok
= smartlist_len(acceptable_methods
);
554 const char *best
= smartlist_get(acceptable_methods
, n_ok
-1);
555 result
= (int)tor_parse_long(best
, 10, 1, INT_MAX
, NULL
, NULL
);
560 smartlist_free(all_methods
);
561 smartlist_free(acceptable_methods
);
565 /** Return true iff <b>method</b> is a consensus method that we support. */
567 consensus_method_is_supported(int method
)
569 return (method
>= 1) && (method
<= MAX_SUPPORTED_CONSENSUS_METHOD
);
572 /** Return a newly allocated string holding the numbers between low and high
573 * (inclusive) that are supported consensus methods. */
575 make_consensus_method_list(int low
, int high
, const char *separator
)
582 lst
= smartlist_create();
583 for (i
= low
; i
<= high
; ++i
) {
584 if (!consensus_method_is_supported(i
))
586 tor_snprintf(b
, sizeof(b
), "%d", i
);
587 smartlist_add(lst
, tor_strdup(b
));
589 list
= smartlist_join_strings(lst
, separator
, 0, NULL
);
591 SMARTLIST_FOREACH(lst
, char *, cp
, tor_free(cp
));
596 /** Helper: given <b>lst</b>, a list of version strings such that every
597 * version appears once for every versioning voter who recommends it, return a
598 * newly allocated string holding the resulting client-versions or
599 * server-versions list. May change contents of <b>lst</b> */
601 compute_consensus_versions_list(smartlist_t
*lst
, int n_versioning
)
603 int min
= n_versioning
/ 2;
604 smartlist_t
*good
= smartlist_create();
606 sort_version_list(lst
, 0);
607 get_frequent_members(good
, lst
, min
);
608 result
= smartlist_join_strings(good
, ",", 0, NULL
);
609 smartlist_free(good
);
613 /** Helper: given a list of valid networkstatus_t, return a new string
614 * containing the contents of the consensus network parameter set.
617 dirvote_compute_params(smartlist_t
*votes
)
623 const char *cur_param
;
627 const int n_votes
= smartlist_len(votes
);
629 smartlist_t
*param_list
= smartlist_create();
631 /* We require that the parameter lists in the votes are well-formed: that
632 is, that their keywords are unique and sorted, and that their values are
633 between INT32_MIN and INT32_MAX inclusive. This should be guaranteed by
636 vals
= tor_malloc(sizeof(int)*n_votes
);
638 SMARTLIST_FOREACH_BEGIN(votes
, networkstatus_t
*, v
) {
641 smartlist_add_all(param_list
, v
->net_params
);
642 } SMARTLIST_FOREACH_END(v
);
644 if (smartlist_len(param_list
) == 0) {
646 smartlist_free(param_list
);
650 smartlist_sort_strings(param_list
);
652 cur_param
= smartlist_get(param_list
, 0);
653 eq
= strchr(cur_param
, '=');
655 cur_param_len
= (int)(eq
+1 - cur_param
);
657 output
= smartlist_create();
659 SMARTLIST_FOREACH_BEGIN(param_list
, const char *, param
) {
660 const char *next_param
;
662 eq
= strchr(param
, '=');
663 tor_assert(i
<n_votes
);
664 vals
[i
++] = (int32_t)
665 tor_parse_long(eq
+1, 10, INT32_MIN
, INT32_MAX
, &ok
, NULL
);
668 if (param_sl_idx
+1 == smartlist_len(param_list
))
671 next_param
= smartlist_get(param_list
, param_sl_idx
+1);
672 if (!next_param
|| strncmp(next_param
, param
, cur_param_len
)) {
673 /* We've reached the end of a series. */
674 int32_t median
= median_int32(vals
, i
);
675 char *out_string
= tor_malloc(64+cur_param_len
);
676 memcpy(out_string
, param
, cur_param_len
);
677 tor_snprintf(out_string
+cur_param_len
,64, "%ld", (long)median
);
678 smartlist_add(output
, out_string
);
682 eq
= strchr(next_param
, '=');
683 cur_param_len
= (int)(eq
+1 - next_param
);
686 } SMARTLIST_FOREACH_END(param
);
688 result
= smartlist_join_strings(output
, " ", 0, NULL
);
689 SMARTLIST_FOREACH(output
, char *, cp
, tor_free(cp
));
690 smartlist_free(output
);
691 smartlist_free(param_list
);
696 #define RANGE_CHECK(a,b,c,d,e,f,g,mx) \
697 ((a) >= 0 && (a) <= (mx) && (b) >= 0 && (b) <= (mx) && \
698 (c) >= 0 && (c) <= (mx) && (d) >= 0 && (d) <= (mx) && \
699 (e) >= 0 && (e) <= (mx) && (f) >= 0 && (f) <= (mx) && \
700 (g) >= 0 && (g) <= (mx))
702 #define CHECK_EQ(a, b, margin) \
703 ((a)-(b) >= 0 ? (a)-(b) <= (margin) : (b)-(a) <= (margin))
706 BW_WEIGHTS_NO_ERROR
= 0,
707 BW_WEIGHTS_RANGE_ERROR
= 1,
708 BW_WEIGHTS_SUMG_ERROR
= 2,
709 BW_WEIGHTS_SUME_ERROR
= 3,
710 BW_WEIGHTS_SUMD_ERROR
= 4,
711 BW_WEIGHTS_BALANCE_MID_ERROR
= 5,
712 BW_WEIGHTS_BALANCE_EG_ERROR
= 6
713 } bw_weights_error_t
;
716 * Verify that any weightings satisfy the balanced formulas.
718 static bw_weights_error_t
719 networkstatus_check_weights(int64_t Wgg
, int64_t Wgd
, int64_t Wmg
,
720 int64_t Wme
, int64_t Wmd
, int64_t Wee
,
721 int64_t Wed
, int64_t scale
, int64_t G
,
722 int64_t M
, int64_t E
, int64_t D
, int64_t T
,
723 int64_t margin
, int do_balance
) {
724 bw_weights_error_t berr
= BW_WEIGHTS_NO_ERROR
;
726 // Wed + Wmd + Wgd == 1
727 if (!CHECK_EQ(Wed
+ Wmd
+ Wgd
, scale
, margin
)) {
728 berr
= BW_WEIGHTS_SUMD_ERROR
;
733 if (!CHECK_EQ(Wmg
+ Wgg
, scale
, margin
)) {
734 berr
= BW_WEIGHTS_SUMG_ERROR
;
739 if (!CHECK_EQ(Wme
+ Wee
, scale
, margin
)) {
740 berr
= BW_WEIGHTS_SUME_ERROR
;
744 // Verify weights within range 0->1
745 if (!RANGE_CHECK(Wgg
, Wgd
, Wmg
, Wme
, Wmd
, Wed
, Wee
, scale
)) {
746 berr
= BW_WEIGHTS_RANGE_ERROR
;
751 // Wgg*G + Wgd*D == Wee*E + Wed*D, already scaled
752 if (!CHECK_EQ(Wgg
*G
+ Wgd
*D
, Wee
*E
+ Wed
*D
, (margin
*T
)/3)) {
753 berr
= BW_WEIGHTS_BALANCE_EG_ERROR
;
757 // Wgg*G + Wgd*D == M*scale + Wmd*D + Wme*E + Wmg*G, already scaled
758 if (!CHECK_EQ(Wgg
*G
+ Wgd
*D
, M
*scale
+ Wmd
*D
+ Wme
*E
+ Wmg
*G
,
760 berr
= BW_WEIGHTS_BALANCE_MID_ERROR
;
768 "Bw weight mismatch %d. G="I64_FORMAT
" M="I64_FORMAT
769 " E="I64_FORMAT
" D="I64_FORMAT
" T="I64_FORMAT
770 " Wmd=%d Wme=%d Wmg=%d Wed=%d Wee=%d"
771 " Wgd=%d Wgg=%d Wme=%d Wmg=%d",
773 I64_PRINTF_ARG(G
), I64_PRINTF_ARG(M
), I64_PRINTF_ARG(E
),
774 I64_PRINTF_ARG(D
), I64_PRINTF_ARG(T
),
775 (int)Wmd
, (int)Wme
, (int)Wmg
, (int)Wed
, (int)Wee
,
776 (int)Wgd
, (int)Wgg
, (int)Wme
, (int)Wmg
);
783 * This function computes the bandwidth weights for consensus method 10.
785 * It returns true if weights could be computed, false otherwise.
788 networkstatus_compute_bw_weights_v10(smartlist_t
*chunks
, int64_t G
,
789 int64_t M
, int64_t E
, int64_t D
,
790 int64_t T
, int64_t weight_scale
)
792 bw_weights_error_t berr
= 0;
793 int64_t Wgg
= -1, Wgd
= -1;
794 int64_t Wmg
= -1, Wme
= -1, Wmd
= -1;
795 int64_t Wed
= -1, Wee
= -1;
796 const char *casename
;
800 if (G
<= 0 || M
<= 0 || E
<= 0 || D
<= 0) {
801 log_warn(LD_DIR
, "Consensus with empty bandwidth: "
802 "G="I64_FORMAT
" M="I64_FORMAT
" E="I64_FORMAT
803 " D="I64_FORMAT
" T="I64_FORMAT
,
804 I64_PRINTF_ARG(G
), I64_PRINTF_ARG(M
), I64_PRINTF_ARG(E
),
805 I64_PRINTF_ARG(D
), I64_PRINTF_ARG(T
));
810 * Computed from cases in 3.4.3 of dir-spec.txt
812 * 1. Neither are scarce
813 * 2. Both Guard and Exit are scarce
816 * 3. One of Guard or Exit is scarce
820 if (3*E
>= T
&& 3*G
>= T
) { // E >= T/3 && G >= T/3
821 /* Case 1: Neither are scarce. */
822 casename
= "Case 1 (Wgd=Wmd=Wed)";
823 Wgd
= weight_scale
/3;
824 Wed
= weight_scale
/3;
825 Wmd
= weight_scale
/3;
826 Wee
= (weight_scale
*(E
+G
+M
))/(3*E
);
827 Wme
= weight_scale
- Wee
;
828 Wmg
= (weight_scale
*(2*G
-E
-M
))/(3*G
);
829 Wgg
= weight_scale
- Wmg
;
831 berr
= networkstatus_check_weights(Wgg
, Wgd
, Wmg
, Wme
, Wmd
, Wee
, Wed
,
832 weight_scale
, G
, M
, E
, D
, T
, 10, 1);
836 "Bw Weights error %d for %s v10. G="I64_FORMAT
" M="I64_FORMAT
837 " E="I64_FORMAT
" D="I64_FORMAT
" T="I64_FORMAT
838 " Wmd=%d Wme=%d Wmg=%d Wed=%d Wee=%d"
839 " Wgd=%d Wgg=%d Wme=%d Wmg=%d weight_scale=%d",
841 I64_PRINTF_ARG(G
), I64_PRINTF_ARG(M
), I64_PRINTF_ARG(E
),
842 I64_PRINTF_ARG(D
), I64_PRINTF_ARG(T
),
843 (int)Wmd
, (int)Wme
, (int)Wmg
, (int)Wed
, (int)Wee
,
844 (int)Wgd
, (int)Wgg
, (int)Wme
, (int)Wmg
, (int)weight_scale
);
847 } else if (3*E
< T
&& 3*G
< T
) { // E < T/3 && G < T/3
848 int64_t R
= MIN(E
, G
);
849 int64_t S
= MAX(E
, G
);
851 * Case 2: Both Guards and Exits are scarce
852 * Balance D between E and G, depending upon
853 * D capacity and scarcity.
855 if (R
+D
< S
) { // Subcase a
862 casename
= "Case 2a (E scarce)";
865 } else { /* E >= G */
866 casename
= "Case 2a (G scarce)";
870 } else { // Subcase b: R+D >= S
871 casename
= "Case 2b1 (Wgg=1, Wmd=Wgd)";
872 Wee
= (weight_scale
*(E
- G
+ M
))/E
;
873 Wed
= (weight_scale
*(D
- 2*E
+ 4*G
- 2*M
))/(3*D
);
874 Wme
= (weight_scale
*(G
-M
))/E
;
877 Wmd
= (weight_scale
- Wed
)/2;
878 Wgd
= (weight_scale
- Wed
)/2;
880 berr
= networkstatus_check_weights(Wgg
, Wgd
, Wmg
, Wme
, Wmd
, Wee
, Wed
,
881 weight_scale
, G
, M
, E
, D
, T
, 10, 1);
884 casename
= "Case 2b2 (Wgg=1, Wee=1)";
887 Wed
= (weight_scale
*(D
- 2*E
+ G
+ M
))/(3*D
);
888 Wmd
= (weight_scale
*(D
- 2*M
+ G
+ E
))/(3*D
);
892 if (Wmd
< 0) { // Can happen if M > T/3
893 casename
= "Case 2b3 (Wmd=0)";
896 "Too much Middle bandwidth on the network to calculate "
897 "balanced bandwidth-weights. Consider increasing the "
898 "number of Guard nodes by lowering the requirements.");
900 Wgd
= weight_scale
- Wed
- Wmd
;
901 berr
= networkstatus_check_weights(Wgg
, Wgd
, Wmg
, Wme
, Wmd
, Wee
,
902 Wed
, weight_scale
, G
, M
, E
, D
, T
, 10, 1);
904 if (berr
!= BW_WEIGHTS_NO_ERROR
&&
905 berr
!= BW_WEIGHTS_BALANCE_MID_ERROR
) {
907 "Bw Weights error %d for %s v10. G="I64_FORMAT
" M="I64_FORMAT
908 " E="I64_FORMAT
" D="I64_FORMAT
" T="I64_FORMAT
909 " Wmd=%d Wme=%d Wmg=%d Wed=%d Wee=%d"
910 " Wgd=%d Wgg=%d Wme=%d Wmg=%d weight_scale=%d",
912 I64_PRINTF_ARG(G
), I64_PRINTF_ARG(M
), I64_PRINTF_ARG(E
),
913 I64_PRINTF_ARG(D
), I64_PRINTF_ARG(T
),
914 (int)Wmd
, (int)Wme
, (int)Wmg
, (int)Wed
, (int)Wee
,
915 (int)Wgd
, (int)Wgg
, (int)Wme
, (int)Wmg
, (int)weight_scale
);
919 } else { // if (E < T/3 || G < T/3) {
920 int64_t S
= MIN(E
, G
);
921 // Case 3: Exactly one of Guard or Exit is scarce
922 if (!(3*E
< T
|| 3*G
< T
) || !(3*G
>= T
|| 3*E
>= T
)) {
924 "Bw-Weights Case 3 v10 but with G="I64_FORMAT
" M="
925 I64_FORMAT
" E="I64_FORMAT
" D="I64_FORMAT
" T="I64_FORMAT
,
926 I64_PRINTF_ARG(G
), I64_PRINTF_ARG(M
), I64_PRINTF_ARG(E
),
927 I64_PRINTF_ARG(D
), I64_PRINTF_ARG(T
));
930 if (3*(S
+D
) < T
) { // Subcase a: S+D < T/3
932 casename
= "Case 3a (G scarce)";
933 Wgg
= Wgd
= weight_scale
;
935 // Minor subcase, if E is more scarce than M,
936 // keep its bandwidth in place.
938 else Wme
= (weight_scale
*(E
-M
))/(2*E
);
939 Wee
= weight_scale
-Wme
;
941 casename
= "Case 3a (E scarce)";
942 Wee
= Wed
= weight_scale
;
944 // Minor subcase, if G is more scarce than M,
945 // keep its bandwidth in place.
947 else Wmg
= (weight_scale
*(G
-M
))/(2*G
);
948 Wgg
= weight_scale
-Wmg
;
950 } else { // Subcase b: S+D >= T/3
951 // D != 0 because S+D >= T/3
953 casename
= "Case 3bg (G scarce, Wgg=1, Wmd == Wed)";
955 Wgd
= (weight_scale
*(D
- 2*G
+ E
+ M
))/(3*D
);
957 Wee
= (weight_scale
*(E
+M
))/(2*E
);
958 Wme
= weight_scale
- Wee
;
959 Wmd
= (weight_scale
- Wgd
)/2;
960 Wed
= (weight_scale
- Wgd
)/2;
962 berr
= networkstatus_check_weights(Wgg
, Wgd
, Wmg
, Wme
, Wmd
, Wee
,
963 Wed
, weight_scale
, G
, M
, E
, D
, T
, 10, 1);
965 casename
= "Case 3be (E scarce, Wee=1, Wmd == Wgd)";
967 Wed
= (weight_scale
*(D
- 2*E
+ G
+ M
))/(3*D
);
969 Wgg
= (weight_scale
*(G
+M
))/(2*G
);
970 Wmg
= weight_scale
- Wgg
;
971 Wmd
= (weight_scale
- Wed
)/2;
972 Wgd
= (weight_scale
- Wed
)/2;
974 berr
= networkstatus_check_weights(Wgg
, Wgd
, Wmg
, Wme
, Wmd
, Wee
,
975 Wed
, weight_scale
, G
, M
, E
, D
, T
, 10, 1);
979 "Bw Weights error %d for %s v10. G="I64_FORMAT
" M="I64_FORMAT
980 " E="I64_FORMAT
" D="I64_FORMAT
" T="I64_FORMAT
981 " Wmd=%d Wme=%d Wmg=%d Wed=%d Wee=%d"
982 " Wgd=%d Wgg=%d Wme=%d Wmg=%d weight_scale=%d",
984 I64_PRINTF_ARG(G
), I64_PRINTF_ARG(M
), I64_PRINTF_ARG(E
),
985 I64_PRINTF_ARG(D
), I64_PRINTF_ARG(T
),
986 (int)Wmd
, (int)Wme
, (int)Wmg
, (int)Wed
, (int)Wee
,
987 (int)Wgd
, (int)Wgg
, (int)Wme
, (int)Wmg
, (int)weight_scale
);
993 /* We cast down the weights to 32 bit ints on the assumption that
994 * weight_scale is ~= 10000. We need to ensure a rogue authority
995 * doesn't break this assumption to rig our weights */
996 tor_assert(0 < weight_scale
&& weight_scale
< INT32_MAX
);
999 * Provide Wgm=Wgg, Wmm=1, Wem=Wee, Weg=Wed. May later determine
1000 * that middle nodes need different bandwidth weights for dirport traffic,
1001 * or that weird exit policies need special weight, or that bridges
1002 * need special weight.
1004 * NOTE: This list is sorted.
1006 r
= tor_snprintf(buf
, sizeof(buf
),
1007 "bandwidth-weights Wbd=%d Wbe=%d Wbg=%d Wbm=%d "
1009 "Web=%d Wed=%d Wee=%d Weg=%d Wem=%d "
1010 "Wgb=%d Wgd=%d Wgg=%d Wgm=%d "
1011 "Wmb=%d Wmd=%d Wme=%d Wmg=%d Wmm=%d\n",
1012 (int)Wmd
, (int)Wme
, (int)Wmg
, (int)weight_scale
,
1014 (int)weight_scale
, (int)Wed
, (int)Wee
, (int)Wed
, (int)Wee
,
1015 (int)weight_scale
, (int)Wgd
, (int)Wgg
, (int)Wgg
,
1016 (int)weight_scale
, (int)Wmd
, (int)Wme
, (int)Wmg
, (int)weight_scale
);
1019 "Not enough space in buffer for bandwidth-weights line.");
1023 smartlist_add(chunks
, tor_strdup(buf
));
1025 log_notice(LD_CIRC
, "Computed bandwidth weights for %s with v10: "
1026 "G="I64_FORMAT
" M="I64_FORMAT
" E="I64_FORMAT
" D="I64_FORMAT
1029 I64_PRINTF_ARG(G
), I64_PRINTF_ARG(M
), I64_PRINTF_ARG(E
),
1030 I64_PRINTF_ARG(D
), I64_PRINTF_ARG(T
));
1034 * This function computes the bandwidth weights for consensus method 9.
1036 * It has been obsoleted in favor of consensus method 10.
1039 networkstatus_compute_bw_weights_v9(smartlist_t
*chunks
, int64_t G
, int64_t M
,
1040 int64_t E
, int64_t D
, int64_t T
,
1041 int64_t weight_scale
)
1043 int64_t Wgg
= -1, Wgd
= -1;
1044 int64_t Wmg
= -1, Wme
= -1, Wmd
= -1;
1045 int64_t Wed
= -1, Wee
= -1;
1046 const char *casename
;
1050 if (G
<= 0 || M
<= 0 || E
<= 0 || D
<= 0) {
1051 log_warn(LD_DIR
, "Consensus with empty bandwidth: "
1052 "G="I64_FORMAT
" M="I64_FORMAT
" E="I64_FORMAT
1053 " D="I64_FORMAT
" T="I64_FORMAT
,
1054 I64_PRINTF_ARG(G
), I64_PRINTF_ARG(M
), I64_PRINTF_ARG(E
),
1055 I64_PRINTF_ARG(D
), I64_PRINTF_ARG(T
));
1060 * Computed from cases in 3.4.3 of dir-spec.txt
1062 * 1. Neither are scarce
1063 * 2. Both Guard and Exit are scarce
1066 * 3. One of Guard or Exit is scarce
1070 if (3*E
>= T
&& 3*G
>= T
) { // E >= T/3 && G >= T/3
1071 bw_weights_error_t berr
= 0;
1072 /* Case 1: Neither are scarce.
1074 * Attempt to ensure that we have a large amount of exit bandwidth
1075 * in the middle position.
1077 casename
= "Case 1 (Wme*E = Wmd*D)";
1078 Wgg
= (weight_scale
*(D
+E
+G
+M
))/(3*G
);
1080 else Wmd
= (weight_scale
*(2*D
+ 2*E
- G
- M
))/(6*D
);
1081 Wme
= (weight_scale
*(2*D
+ 2*E
- G
- M
))/(6*E
);
1082 Wee
= (weight_scale
*(-2*D
+ 4*E
+ G
+ M
))/(6*E
);
1084 Wmg
= weight_scale
- Wgg
;
1085 Wed
= weight_scale
- Wmd
;
1087 berr
= networkstatus_check_weights(Wgg
, Wgd
, Wmg
, Wme
, Wmd
, Wee
, Wed
,
1088 weight_scale
, G
, M
, E
, D
, T
, 10, 1);
1091 log_warn(LD_DIR
, "Bw Weights error %d for case %s. "
1092 "G="I64_FORMAT
" M="I64_FORMAT
" E="I64_FORMAT
1093 " D="I64_FORMAT
" T="I64_FORMAT
,
1095 I64_PRINTF_ARG(G
), I64_PRINTF_ARG(M
), I64_PRINTF_ARG(E
),
1096 I64_PRINTF_ARG(D
), I64_PRINTF_ARG(T
));
1098 } else if (3*E
< T
&& 3*G
< T
) { // E < T/3 && G < T/3
1099 int64_t R
= MIN(E
, G
);
1100 int64_t S
= MAX(E
, G
);
1102 * Case 2: Both Guards and Exits are scarce
1103 * Balance D between E and G, depending upon
1104 * D capacity and scarcity.
1106 if (R
+D
< S
) { // Subcase a
1113 casename
= "Case 2a (E scarce)";
1116 } else { /* E >= G */
1117 casename
= "Case 2a (G scarce)";
1121 } else { // Subcase b: R+D > S
1122 bw_weights_error_t berr
= 0;
1123 casename
= "Case 2b (Wme*E == Wmd*D)";
1126 Wgd
= (weight_scale
*(D
+ E
- 2*G
+ M
))/(3*D
); // T/3 >= G (Ok)
1127 Wmd
= (weight_scale
*(D
+ E
+ G
- 2*M
))/(6*D
); // T/3 >= M
1128 Wme
= (weight_scale
*(D
+ E
+ G
- 2*M
))/(6*E
);
1129 Wee
= (weight_scale
*(-D
+ 5*E
- G
+ 2*M
))/(6*E
); // 2E+M >= T/3
1131 Wed
= weight_scale
- Wgd
- Wmd
;
1133 berr
= networkstatus_check_weights(Wgg
, Wgd
, Wmg
, Wme
, Wmd
, Wee
, Wed
,
1134 weight_scale
, G
, M
, E
, D
, T
, 10, 1);
1137 if (D
== 0 || berr
) { // Can happen if M > T/3
1138 casename
= "Case 2b (E=G)";
1144 if (D
== 0) Wgd
= 0;
1145 else Wgd
= (weight_scale
*(D
+E
-G
))/(2*D
);
1146 Wed
= weight_scale
- Wgd
;
1147 berr
= networkstatus_check_weights(Wgg
, Wgd
, Wmg
, Wme
, Wmd
, Wee
,
1148 Wed
, weight_scale
, G
, M
, E
, D
, T
, 10, 1);
1150 if (berr
!= BW_WEIGHTS_NO_ERROR
&&
1151 berr
!= BW_WEIGHTS_BALANCE_MID_ERROR
) {
1152 log_warn(LD_DIR
, "Bw Weights error %d for case %s. "
1153 "G="I64_FORMAT
" M="I64_FORMAT
" E="I64_FORMAT
1154 " D="I64_FORMAT
" T="I64_FORMAT
,
1156 I64_PRINTF_ARG(G
), I64_PRINTF_ARG(M
), I64_PRINTF_ARG(E
),
1157 I64_PRINTF_ARG(D
), I64_PRINTF_ARG(T
));
1160 } else { // if (E < T/3 || G < T/3) {
1161 int64_t S
= MIN(E
, G
);
1162 // Case 3: Exactly one of Guard or Exit is scarce
1163 if (!(3*E
< T
|| 3*G
< T
) || !(3*G
>= T
|| 3*E
>= T
)) {
1165 "Bw-Weights Case 3 but with G="I64_FORMAT
" M="
1166 I64_FORMAT
" E="I64_FORMAT
" D="I64_FORMAT
" T="I64_FORMAT
,
1167 I64_PRINTF_ARG(G
), I64_PRINTF_ARG(M
), I64_PRINTF_ARG(E
),
1168 I64_PRINTF_ARG(D
), I64_PRINTF_ARG(T
));
1171 if (3*(S
+D
) < T
) { // Subcase a: S+D < T/3
1173 casename
= "Case 3a (G scarce)";
1174 Wgg
= Wgd
= weight_scale
;
1175 Wmd
= Wed
= Wmg
= 0;
1176 // Minor subcase, if E is more scarce than M,
1177 // keep its bandwidth in place.
1179 else Wme
= (weight_scale
*(E
-M
))/(2*E
);
1180 Wee
= weight_scale
-Wme
;
1182 casename
= "Case 3a (E scarce)";
1183 Wee
= Wed
= weight_scale
;
1184 Wmd
= Wgd
= Wme
= 0;
1185 // Minor subcase, if G is more scarce than M,
1186 // keep its bandwidth in place.
1188 else Wmg
= (weight_scale
*(G
-M
))/(2*G
);
1189 Wgg
= weight_scale
-Wmg
;
1191 } else { // Subcase b: S+D >= T/3
1192 bw_weights_error_t berr
= 0;
1193 // D != 0 because S+D >= T/3
1195 casename
= "Case 3b (G scarce, Wme*E == Wmd*D)";
1196 Wgd
= (weight_scale
*(D
+ E
- 2*G
+ M
))/(3*D
);
1197 Wmd
= (weight_scale
*(D
+ E
+ G
- 2*M
))/(6*D
);
1198 Wme
= (weight_scale
*(D
+ E
+ G
- 2*M
))/(6*E
);
1199 Wee
= (weight_scale
*(-D
+ 5*E
- G
+ 2*M
))/(6*E
);
1202 Wed
= weight_scale
- Wgd
- Wmd
;
1204 berr
= networkstatus_check_weights(Wgg
, Wgd
, Wmg
, Wme
, Wmd
, Wee
,
1205 Wed
, weight_scale
, G
, M
, E
, D
, T
, 10, 1);
1207 casename
= "Case 3b (E scarce, Wme*E == Wmd*D)";
1208 Wgg
= (weight_scale
*(D
+ E
+ G
+ M
))/(3*G
);
1209 Wmd
= (weight_scale
*(2*D
+ 2*E
- G
- M
))/(6*D
);
1210 Wme
= (weight_scale
*(2*D
+ 2*E
- G
- M
))/(6*E
);
1211 Wee
= (weight_scale
*(-2*D
+ 4*E
+ G
+ M
))/(6*E
);
1213 Wmg
= weight_scale
- Wgg
;
1214 Wed
= weight_scale
- Wmd
;
1216 berr
= networkstatus_check_weights(Wgg
, Wgd
, Wmg
, Wme
, Wmd
, Wee
,
1217 Wed
, weight_scale
, G
, M
, E
, D
, T
, 10, 1);
1220 log_warn(LD_DIR
, "Bw Weights error %d for case %s. "
1221 "G="I64_FORMAT
" M="I64_FORMAT
1222 " E="I64_FORMAT
" D="I64_FORMAT
" T="I64_FORMAT
,
1224 I64_PRINTF_ARG(G
), I64_PRINTF_ARG(M
), I64_PRINTF_ARG(E
),
1225 I64_PRINTF_ARG(D
), I64_PRINTF_ARG(T
));
1230 /* We cast down the weights to 32 bit ints on the assumption that
1231 * weight_scale is ~= 10000. We need to ensure a rogue authority
1232 * doesn't break this assumption to rig our weights */
1233 tor_assert(0 < weight_scale
&& weight_scale
< INT32_MAX
);
1235 if (Wgg
< 0 || Wgg
> weight_scale
) {
1236 log_warn(LD_DIR
, "Bw %s: Wgg="I64_FORMAT
"! G="I64_FORMAT
1237 " M="I64_FORMAT
" E="I64_FORMAT
" D="I64_FORMAT
1239 casename
, I64_PRINTF_ARG(Wgg
),
1240 I64_PRINTF_ARG(G
), I64_PRINTF_ARG(M
), I64_PRINTF_ARG(E
),
1241 I64_PRINTF_ARG(D
), I64_PRINTF_ARG(T
));
1243 Wgg
= MAX(MIN(Wgg
, weight_scale
), 0);
1245 if (Wgd
< 0 || Wgd
> weight_scale
) {
1246 log_warn(LD_DIR
, "Bw %s: Wgd="I64_FORMAT
"! G="I64_FORMAT
1247 " M="I64_FORMAT
" E="I64_FORMAT
" D="I64_FORMAT
1249 casename
, I64_PRINTF_ARG(Wgd
),
1250 I64_PRINTF_ARG(G
), I64_PRINTF_ARG(M
), I64_PRINTF_ARG(E
),
1251 I64_PRINTF_ARG(D
), I64_PRINTF_ARG(T
));
1252 Wgd
= MAX(MIN(Wgd
, weight_scale
), 0);
1254 if (Wmg
< 0 || Wmg
> weight_scale
) {
1255 log_warn(LD_DIR
, "Bw %s: Wmg="I64_FORMAT
"! G="I64_FORMAT
1256 " M="I64_FORMAT
" E="I64_FORMAT
" D="I64_FORMAT
1258 casename
, I64_PRINTF_ARG(Wmg
),
1259 I64_PRINTF_ARG(G
), I64_PRINTF_ARG(M
), I64_PRINTF_ARG(E
),
1260 I64_PRINTF_ARG(D
), I64_PRINTF_ARG(T
));
1261 Wmg
= MAX(MIN(Wmg
, weight_scale
), 0);
1263 if (Wme
< 0 || Wme
> weight_scale
) {
1264 log_warn(LD_DIR
, "Bw %s: Wme="I64_FORMAT
"! G="I64_FORMAT
1265 " M="I64_FORMAT
" E="I64_FORMAT
" D="I64_FORMAT
1267 casename
, I64_PRINTF_ARG(Wme
),
1268 I64_PRINTF_ARG(G
), I64_PRINTF_ARG(M
), I64_PRINTF_ARG(E
),
1269 I64_PRINTF_ARG(D
), I64_PRINTF_ARG(T
));
1270 Wme
= MAX(MIN(Wme
, weight_scale
), 0);
1272 if (Wmd
< 0 || Wmd
> weight_scale
) {
1273 log_warn(LD_DIR
, "Bw %s: Wmd="I64_FORMAT
"! G="I64_FORMAT
1274 " M="I64_FORMAT
" E="I64_FORMAT
" D="I64_FORMAT
1276 casename
, I64_PRINTF_ARG(Wmd
),
1277 I64_PRINTF_ARG(G
), I64_PRINTF_ARG(M
), I64_PRINTF_ARG(E
),
1278 I64_PRINTF_ARG(D
), I64_PRINTF_ARG(T
));
1279 Wmd
= MAX(MIN(Wmd
, weight_scale
), 0);
1281 if (Wee
< 0 || Wee
> weight_scale
) {
1282 log_warn(LD_DIR
, "Bw %s: Wee="I64_FORMAT
"! G="I64_FORMAT
1283 " M="I64_FORMAT
" E="I64_FORMAT
" D="I64_FORMAT
1285 casename
, I64_PRINTF_ARG(Wee
),
1286 I64_PRINTF_ARG(G
), I64_PRINTF_ARG(M
), I64_PRINTF_ARG(E
),
1287 I64_PRINTF_ARG(D
), I64_PRINTF_ARG(T
));
1288 Wee
= MAX(MIN(Wee
, weight_scale
), 0);
1290 if (Wed
< 0 || Wed
> weight_scale
) {
1291 log_warn(LD_DIR
, "Bw %s: Wed="I64_FORMAT
"! G="I64_FORMAT
1292 " M="I64_FORMAT
" E="I64_FORMAT
" D="I64_FORMAT
1294 casename
, I64_PRINTF_ARG(Wed
),
1295 I64_PRINTF_ARG(G
), I64_PRINTF_ARG(M
), I64_PRINTF_ARG(E
),
1296 I64_PRINTF_ARG(D
), I64_PRINTF_ARG(T
));
1297 Wed
= MAX(MIN(Wed
, weight_scale
), 0);
1300 // Add consensus weight keywords
1301 smartlist_add(chunks
, tor_strdup("bandwidth-weights "));
1303 * Provide Wgm=Wgg, Wmm=1, Wem=Wee, Weg=Wed. May later determine
1304 * that middle nodes need different bandwidth weights for dirport traffic,
1305 * or that weird exit policies need special weight, or that bridges
1306 * need special weight.
1308 * NOTE: This list is sorted.
1310 r
= tor_snprintf(buf
, sizeof(buf
),
1311 "Wbd=%d Wbe=%d Wbg=%d Wbm=%d "
1313 "Web=%d Wed=%d Wee=%d Weg=%d Wem=%d "
1314 "Wgb=%d Wgd=%d Wgg=%d Wgm=%d "
1315 "Wmb=%d Wmd=%d Wme=%d Wmg=%d Wmm=%d\n",
1316 (int)Wmd
, (int)Wme
, (int)Wmg
, (int)weight_scale
,
1318 (int)weight_scale
, (int)Wed
, (int)Wee
, (int)Wed
, (int)Wee
,
1319 (int)weight_scale
, (int)Wgd
, (int)Wgg
, (int)Wgg
,
1320 (int)weight_scale
, (int)Wmd
, (int)Wme
, (int)Wmg
, (int)weight_scale
);
1323 "Not enough space in buffer for bandwidth-weights line.");
1326 smartlist_add(chunks
, tor_strdup(buf
));
1327 log_notice(LD_CIRC
, "Computed bandwidth weights for %s with v9: "
1328 "G="I64_FORMAT
" M="I64_FORMAT
" E="I64_FORMAT
" D="I64_FORMAT
1331 I64_PRINTF_ARG(G
), I64_PRINTF_ARG(M
), I64_PRINTF_ARG(E
),
1332 I64_PRINTF_ARG(D
), I64_PRINTF_ARG(T
));
1335 /** Given a list of vote networkstatus_t in <b>votes</b>, our public
1336 * authority <b>identity_key</b>, our private authority <b>signing_key</b>,
1337 * and the number of <b>total_authorities</b> that we believe exist in our
1338 * voting quorum, generate the text of a new v3 consensus vote, and return the
1339 * value in a newly allocated string.
1341 * Note: this function DOES NOT check whether the votes are from
1342 * recognized authorities. (dirvote_add_vote does that.) */
1344 networkstatus_compute_consensus(smartlist_t
*votes
,
1345 int total_authorities
,
1346 crypto_pk_env_t
*identity_key
,
1347 crypto_pk_env_t
*signing_key
,
1348 const char *legacy_id_key_digest
,
1349 crypto_pk_env_t
*legacy_signing_key
,
1350 consensus_flavor_t flavor
)
1352 smartlist_t
*chunks
;
1353 char *result
= NULL
;
1354 int consensus_method
;
1355 time_t valid_after
, fresh_until
, valid_until
;
1356 int vote_seconds
, dist_seconds
;
1357 char *client_versions
= NULL
, *server_versions
= NULL
;
1359 const char *flavor_name
;
1360 int64_t G
=0, M
=0, E
=0, D
=0, T
=0; /* For bandwidth weights */
1361 const routerstatus_format_type_t rs_format
=
1362 flavor
== FLAV_NS
? NS_V3_CONSENSUS
: NS_V3_CONSENSUS_MICRODESC
;
1363 char *params
= NULL
;
1364 int added_weights
= 0;
1365 tor_assert(flavor
== FLAV_NS
|| flavor
== FLAV_MICRODESC
);
1366 tor_assert(total_authorities
>= smartlist_len(votes
));
1368 flavor_name
= networkstatus_get_flavor_name(flavor
);
1370 if (!smartlist_len(votes
)) {
1371 log_warn(LD_DIR
, "Can't compute a consensus from no votes.");
1374 flags
= smartlist_create();
1376 consensus_method
= compute_consensus_method(votes
);
1377 if (consensus_method_is_supported(consensus_method
)) {
1378 log_info(LD_DIR
, "Generating consensus using method %d.",
1381 log_warn(LD_DIR
, "The other authorities will use consensus method %d, "
1382 "which I don't support. Maybe I should upgrade!",
1384 consensus_method
= 1;
1387 /* Compute medians of time-related things, and figure out how many
1388 * routers we might need to talk about. */
1390 int n_votes
= smartlist_len(votes
);
1391 time_t *va_times
= tor_malloc(n_votes
* sizeof(time_t));
1392 time_t *fu_times
= tor_malloc(n_votes
* sizeof(time_t));
1393 time_t *vu_times
= tor_malloc(n_votes
* sizeof(time_t));
1394 int *votesec_list
= tor_malloc(n_votes
* sizeof(int));
1395 int *distsec_list
= tor_malloc(n_votes
* sizeof(int));
1396 int n_versioning_clients
= 0, n_versioning_servers
= 0;
1397 smartlist_t
*combined_client_versions
= smartlist_create();
1398 smartlist_t
*combined_server_versions
= smartlist_create();
1400 SMARTLIST_FOREACH_BEGIN(votes
, networkstatus_t
*, v
) {
1401 tor_assert(v
->type
== NS_TYPE_VOTE
);
1402 va_times
[v_sl_idx
] = v
->valid_after
;
1403 fu_times
[v_sl_idx
] = v
->fresh_until
;
1404 vu_times
[v_sl_idx
] = v
->valid_until
;
1405 votesec_list
[v_sl_idx
] = v
->vote_seconds
;
1406 distsec_list
[v_sl_idx
] = v
->dist_seconds
;
1407 if (v
->client_versions
) {
1408 smartlist_t
*cv
= smartlist_create();
1409 ++n_versioning_clients
;
1410 smartlist_split_string(cv
, v
->client_versions
, ",",
1411 SPLIT_SKIP_SPACE
|SPLIT_IGNORE_BLANK
, 0);
1412 sort_version_list(cv
, 1);
1413 smartlist_add_all(combined_client_versions
, cv
);
1414 smartlist_free(cv
); /* elements get freed later. */
1416 if (v
->server_versions
) {
1417 smartlist_t
*sv
= smartlist_create();
1418 ++n_versioning_servers
;
1419 smartlist_split_string(sv
, v
->server_versions
, ",",
1420 SPLIT_SKIP_SPACE
|SPLIT_IGNORE_BLANK
, 0);
1421 sort_version_list(sv
, 1);
1422 smartlist_add_all(combined_server_versions
, sv
);
1423 smartlist_free(sv
); /* elements get freed later. */
1425 SMARTLIST_FOREACH(v
->known_flags
, const char *, cp
,
1426 smartlist_add(flags
, tor_strdup(cp
)));
1427 } SMARTLIST_FOREACH_END(v
);
1428 valid_after
= median_time(va_times
, n_votes
);
1429 fresh_until
= median_time(fu_times
, n_votes
);
1430 valid_until
= median_time(vu_times
, n_votes
);
1431 vote_seconds
= median_int(votesec_list
, n_votes
);
1432 dist_seconds
= median_int(distsec_list
, n_votes
);
1434 tor_assert(valid_after
+MIN_VOTE_INTERVAL
<= fresh_until
);
1435 tor_assert(fresh_until
+MIN_VOTE_INTERVAL
<= valid_until
);
1436 tor_assert(vote_seconds
>= MIN_VOTE_SECONDS
);
1437 tor_assert(dist_seconds
>= MIN_DIST_SECONDS
);
1439 server_versions
= compute_consensus_versions_list(combined_server_versions
,
1440 n_versioning_servers
);
1441 client_versions
= compute_consensus_versions_list(combined_client_versions
,
1442 n_versioning_clients
);
1444 SMARTLIST_FOREACH(combined_server_versions
, char *, cp
, tor_free(cp
));
1445 SMARTLIST_FOREACH(combined_client_versions
, char *, cp
, tor_free(cp
));
1446 smartlist_free(combined_server_versions
);
1447 smartlist_free(combined_client_versions
);
1449 smartlist_sort_strings(flags
);
1450 smartlist_uniq_strings(flags
);
1455 tor_free(votesec_list
);
1456 tor_free(distsec_list
);
1459 chunks
= smartlist_create();
1463 char va_buf
[ISO_TIME_LEN
+1], fu_buf
[ISO_TIME_LEN
+1],
1464 vu_buf
[ISO_TIME_LEN
+1];
1466 format_iso_time(va_buf
, valid_after
);
1467 format_iso_time(fu_buf
, fresh_until
);
1468 format_iso_time(vu_buf
, valid_until
);
1469 flaglist
= smartlist_join_strings(flags
, " ", 0, NULL
);
1471 tor_asprintf(&buf
, "network-status-version 3%s%s\n"
1472 "vote-status consensus\n",
1473 flavor
== FLAV_NS
? "" : " ",
1474 flavor
== FLAV_NS
? "" : flavor_name
);
1476 smartlist_add(chunks
, buf
);
1478 if (consensus_method
>= 2) {
1479 tor_asprintf(&buf
, "consensus-method %d\n",
1481 smartlist_add(chunks
, buf
);
1488 "voting-delay %d %d\n"
1489 "client-versions %s\n"
1490 "server-versions %s\n"
1492 va_buf
, fu_buf
, vu_buf
,
1493 vote_seconds
, dist_seconds
,
1494 client_versions
, server_versions
, flaglist
);
1495 smartlist_add(chunks
, buf
);
1500 if (consensus_method
>= MIN_METHOD_FOR_PARAMS
) {
1501 params
= dirvote_compute_params(votes
);
1503 smartlist_add(chunks
, tor_strdup("params "));
1504 smartlist_add(chunks
, params
);
1505 smartlist_add(chunks
, tor_strdup("\n"));
1509 /* Sort the votes. */
1510 smartlist_sort(votes
, _compare_votes_by_authority_id
);
1511 /* Add the authority sections. */
1513 smartlist_t
*dir_sources
= smartlist_create();
1514 SMARTLIST_FOREACH_BEGIN(votes
, networkstatus_t
*, v
) {
1515 dir_src_ent_t
*e
= tor_malloc_zero(sizeof(dir_src_ent_t
));
1517 e
->digest
= get_voter(v
)->identity_digest
;
1519 smartlist_add(dir_sources
, e
);
1520 if (consensus_method
>= 3 &&
1521 !tor_digest_is_zero(get_voter(v
)->legacy_id_digest
)) {
1522 dir_src_ent_t
*e_legacy
= tor_malloc_zero(sizeof(dir_src_ent_t
));
1524 e_legacy
->digest
= get_voter(v
)->legacy_id_digest
;
1525 e_legacy
->is_legacy
= 1;
1526 smartlist_add(dir_sources
, e_legacy
);
1528 } SMARTLIST_FOREACH_END(v
);
1529 smartlist_sort(dir_sources
, _compare_dir_src_ents_by_authority_id
);
1531 SMARTLIST_FOREACH_BEGIN(dir_sources
, const dir_src_ent_t
*, e
) {
1533 char ip
[INET_NTOA_BUF_LEN
];
1534 char fingerprint
[HEX_DIGEST_LEN
+1];
1535 char votedigest
[HEX_DIGEST_LEN
+1];
1536 networkstatus_t
*v
= e
->v
;
1537 networkstatus_voter_info_t
*voter
= get_voter(v
);
1541 tor_assert(consensus_method
>= 2);
1543 in
.s_addr
= htonl(voter
->addr
);
1544 tor_inet_ntoa(&in
, ip
, sizeof(ip
));
1545 base16_encode(fingerprint
, sizeof(fingerprint
), e
->digest
, DIGEST_LEN
);
1546 base16_encode(votedigest
, sizeof(votedigest
), voter
->vote_digest
,
1550 "dir-source %s%s %s %s %s %d %d\n",
1551 voter
->nickname
, e
->is_legacy
? "-legacy" : "",
1552 fingerprint
, voter
->address
, ip
,
1555 smartlist_add(chunks
, buf
);
1556 if (! e
->is_legacy
) {
1562 smartlist_add(chunks
, buf
);
1564 } SMARTLIST_FOREACH_END(e
);
1565 SMARTLIST_FOREACH(dir_sources
, dir_src_ent_t
*, e
, tor_free(e
));
1566 smartlist_free(dir_sources
);
1569 /* Add the actual router entries. */
1571 int *index
; /* index[j] is the current index into votes[j]. */
1572 int *size
; /* size[j] is the number of routerstatuses in votes[j]. */
1573 int *flag_counts
; /* The number of voters that list flag[j] for the
1574 * currently considered router. */
1576 smartlist_t
*matching_descs
= smartlist_create();
1577 smartlist_t
*chosen_flags
= smartlist_create();
1578 smartlist_t
*versions
= smartlist_create();
1579 smartlist_t
*exitsummaries
= smartlist_create();
1580 uint32_t *bandwidths
= tor_malloc(sizeof(uint32_t) * smartlist_len(votes
));
1581 uint32_t *measured_bws
= tor_malloc(sizeof(uint32_t) *
1582 smartlist_len(votes
));
1586 int *n_voter_flags
; /* n_voter_flags[j] is the number of flags that
1587 * votes[j] knows about. */
1588 int *n_flag_voters
; /* n_flag_voters[f] is the number of votes that care
1589 * about flags[f]. */
1590 int **flag_map
; /* flag_map[j][b] is an index f such that flag_map[f]
1591 * is the same flag as votes[j]->known_flags[b]. */
1592 int *named_flag
; /* Index of the flag "Named" for votes[j] */
1593 int *unnamed_flag
; /* Index of the flag "Unnamed" for votes[j] */
1594 int chosen_named_idx
, chosen_unnamed_idx
;
1596 strmap_t
*name_to_id_map
= strmap_new();
1597 char conflict
[DIGEST_LEN
];
1598 char unknown
[DIGEST_LEN
];
1599 memset(conflict
, 0, sizeof(conflict
));
1600 memset(unknown
, 0xff, sizeof(conflict
));
1602 index
= tor_malloc_zero(sizeof(int)*smartlist_len(votes
));
1603 size
= tor_malloc_zero(sizeof(int)*smartlist_len(votes
));
1604 n_voter_flags
= tor_malloc_zero(sizeof(int) * smartlist_len(votes
));
1605 n_flag_voters
= tor_malloc_zero(sizeof(int) * smartlist_len(flags
));
1606 flag_map
= tor_malloc_zero(sizeof(int*) * smartlist_len(votes
));
1607 named_flag
= tor_malloc_zero(sizeof(int) * smartlist_len(votes
));
1608 unnamed_flag
= tor_malloc_zero(sizeof(int) * smartlist_len(votes
));
1609 for (i
= 0; i
< smartlist_len(votes
); ++i
)
1610 unnamed_flag
[i
] = named_flag
[i
] = -1;
1611 chosen_named_idx
= smartlist_string_pos(flags
, "Named");
1612 chosen_unnamed_idx
= smartlist_string_pos(flags
, "Unnamed");
1614 /* Build the flag index. */
1615 SMARTLIST_FOREACH(votes
, networkstatus_t
*, v
,
1617 flag_map
[v_sl_idx
] = tor_malloc_zero(
1618 sizeof(int)*smartlist_len(v
->known_flags
));
1619 SMARTLIST_FOREACH(v
->known_flags
, const char *, fl
,
1621 int p
= smartlist_string_pos(flags
, fl
);
1623 flag_map
[v_sl_idx
][fl_sl_idx
] = p
;
1625 if (!strcmp(fl
, "Named"))
1626 named_flag
[v_sl_idx
] = fl_sl_idx
;
1627 if (!strcmp(fl
, "Unnamed"))
1628 unnamed_flag
[v_sl_idx
] = fl_sl_idx
;
1630 n_voter_flags
[v_sl_idx
] = smartlist_len(v
->known_flags
);
1631 size
[v_sl_idx
] = smartlist_len(v
->routerstatus_list
);
1634 /* Named and Unnamed get treated specially */
1635 if (consensus_method
>= 2) {
1636 SMARTLIST_FOREACH(votes
, networkstatus_t
*, v
,
1639 if (named_flag
[v_sl_idx
]<0)
1641 nf
= U64_LITERAL(1) << named_flag
[v_sl_idx
];
1642 SMARTLIST_FOREACH(v
->routerstatus_list
, vote_routerstatus_t
*, rs
,
1644 if ((rs
->flags
& nf
) != 0) {
1645 const char *d
= strmap_get_lc(name_to_id_map
, rs
->status
.nickname
);
1647 /* We have no name officially mapped to this digest. */
1648 strmap_set_lc(name_to_id_map
, rs
->status
.nickname
,
1649 rs
->status
.identity_digest
);
1650 } else if (d
!= conflict
&&
1651 memcmp(d
, rs
->status
.identity_digest
, DIGEST_LEN
)) {
1652 /* Authorities disagree about this nickname. */
1653 strmap_set_lc(name_to_id_map
, rs
->status
.nickname
, conflict
);
1655 /* It's already a conflict, or it's already this ID. */
1660 SMARTLIST_FOREACH(votes
, networkstatus_t
*, v
,
1663 if (unnamed_flag
[v_sl_idx
]<0)
1665 uf
= U64_LITERAL(1) << unnamed_flag
[v_sl_idx
];
1666 SMARTLIST_FOREACH(v
->routerstatus_list
, vote_routerstatus_t
*, rs
,
1668 if ((rs
->flags
& uf
) != 0) {
1669 const char *d
= strmap_get_lc(name_to_id_map
, rs
->status
.nickname
);
1670 if (d
== conflict
|| d
== unknown
) {
1671 /* Leave it alone; we know what it is. */
1673 /* We have no name officially mapped to this digest. */
1674 strmap_set_lc(name_to_id_map
, rs
->status
.nickname
, unknown
);
1675 } else if (!memcmp(d
, rs
->status
.identity_digest
, DIGEST_LEN
)) {
1676 /* Authorities disagree about this nickname. */
1677 strmap_set_lc(name_to_id_map
, rs
->status
.nickname
, conflict
);
1679 /* It's mapped to a different name. */
1686 /* Now go through all the votes */
1687 flag_counts
= tor_malloc(sizeof(int) * smartlist_len(flags
));
1689 vote_routerstatus_t
*rs
;
1690 routerstatus_t rs_out
;
1691 const char *lowest_id
= NULL
;
1692 const char *chosen_version
;
1693 const char *chosen_name
= NULL
;
1694 int exitsummary_disagreement
= 0;
1695 int is_named
= 0, is_unnamed
= 0, is_running
= 0;
1696 int is_guard
= 0, is_exit
= 0, is_bad_exit
= 0;
1697 int naming_conflict
= 0;
1701 char microdesc_digest
[DIGEST256_LEN
];
1703 /* Of the next-to-be-considered digest in each voter, which is first? */
1704 SMARTLIST_FOREACH(votes
, networkstatus_t
*, v
, {
1705 if (index
[v_sl_idx
] < size
[v_sl_idx
]) {
1706 rs
= smartlist_get(v
->routerstatus_list
, index
[v_sl_idx
]);
1708 memcmp(rs
->status
.identity_digest
, lowest_id
, DIGEST_LEN
) < 0)
1709 lowest_id
= rs
->status
.identity_digest
;
1712 if (!lowest_id
) /* we're out of routers. */
1715 memset(flag_counts
, 0, sizeof(int)*smartlist_len(flags
));
1716 smartlist_clear(matching_descs
);
1717 smartlist_clear(chosen_flags
);
1718 smartlist_clear(versions
);
1722 /* Okay, go through all the entries for this digest. */
1723 SMARTLIST_FOREACH_BEGIN(votes
, networkstatus_t
*, v
) {
1724 if (index
[v_sl_idx
] >= size
[v_sl_idx
])
1725 continue; /* out of entries. */
1726 rs
= smartlist_get(v
->routerstatus_list
, index
[v_sl_idx
]);
1727 if (memcmp(rs
->status
.identity_digest
, lowest_id
, DIGEST_LEN
))
1728 continue; /* doesn't include this router. */
1729 /* At this point, we know that we're looking at a routerstatus with
1730 * identity "lowest".
1735 smartlist_add(matching_descs
, rs
);
1736 if (rs
->version
&& rs
->version
[0])
1737 smartlist_add(versions
, rs
->version
);
1739 /* Tally up all the flags. */
1740 for (i
= 0; i
< n_voter_flags
[v_sl_idx
]; ++i
) {
1741 if (rs
->flags
& (U64_LITERAL(1) << i
))
1742 ++flag_counts
[flag_map
[v_sl_idx
][i
]];
1744 if (rs
->flags
& (U64_LITERAL(1) << named_flag
[v_sl_idx
])) {
1745 if (chosen_name
&& strcmp(chosen_name
, rs
->status
.nickname
)) {
1746 log_notice(LD_DIR
, "Conflict on naming for router: %s vs %s",
1747 chosen_name
, rs
->status
.nickname
);
1748 naming_conflict
= 1;
1750 chosen_name
= rs
->status
.nickname
;
1753 /* count bandwidths */
1754 if (rs
->status
.has_measured_bw
)
1755 measured_bws
[num_mbws
++] = rs
->status
.measured_bw
;
1757 if (rs
->status
.has_bandwidth
)
1758 bandwidths
[num_bandwidths
++] = rs
->status
.bandwidth
;
1759 } SMARTLIST_FOREACH_END(v
);
1761 /* We don't include this router at all unless more than half of
1762 * the authorities we believe in list it. */
1763 if (n_listing
<= total_authorities
/2)
1766 /* Figure out the most popular opinion of what the most recent
1767 * routerinfo and its contents are. */
1768 memset(microdesc_digest
, 0, sizeof(microdesc_digest
));
1769 rs
= compute_routerstatus_consensus(matching_descs
, consensus_method
,
1771 /* Copy bits of that into rs_out. */
1772 tor_assert(!memcmp(lowest_id
, rs
->status
.identity_digest
, DIGEST_LEN
));
1773 memcpy(rs_out
.identity_digest
, lowest_id
, DIGEST_LEN
);
1774 memcpy(rs_out
.descriptor_digest
, rs
->status
.descriptor_digest
,
1776 rs_out
.addr
= rs
->status
.addr
;
1777 rs_out
.published_on
= rs
->status
.published_on
;
1778 rs_out
.dir_port
= rs
->status
.dir_port
;
1779 rs_out
.or_port
= rs
->status
.or_port
;
1780 rs_out
.has_bandwidth
= 0;
1781 rs_out
.has_exitsummary
= 0;
1783 if (chosen_name
&& !naming_conflict
) {
1784 strlcpy(rs_out
.nickname
, chosen_name
, sizeof(rs_out
.nickname
));
1786 strlcpy(rs_out
.nickname
, rs
->status
.nickname
, sizeof(rs_out
.nickname
));
1789 if (consensus_method
== 1) {
1790 is_named
= chosen_named_idx
>= 0 &&
1791 (!naming_conflict
&& flag_counts
[chosen_named_idx
]);
1793 const char *d
= strmap_get_lc(name_to_id_map
, rs_out
.nickname
);
1795 is_named
= is_unnamed
= 0;
1796 } else if (!memcmp(d
, lowest_id
, DIGEST_LEN
)) {
1797 is_named
= 1; is_unnamed
= 0;
1799 is_named
= 0; is_unnamed
= 1;
1803 /* Set the flags. */
1804 smartlist_add(chosen_flags
, (char*)"s"); /* for the start of the line. */
1805 SMARTLIST_FOREACH(flags
, const char *, fl
,
1807 if (!strcmp(fl
, "Named")) {
1809 smartlist_add(chosen_flags
, (char*)fl
);
1810 } else if (!strcmp(fl
, "Unnamed") && consensus_method
>= 2) {
1812 smartlist_add(chosen_flags
, (char*)fl
);
1814 if (flag_counts
[fl_sl_idx
] > n_flag_voters
[fl_sl_idx
]/2) {
1815 smartlist_add(chosen_flags
, (char*)fl
);
1816 if (!strcmp(fl
, "Exit"))
1818 else if (!strcmp(fl
, "Guard"))
1820 else if (!strcmp(fl
, "Running"))
1822 else if (!strcmp(fl
, "BadExit"))
1828 /* Starting with consensus method 4 we do not list servers
1829 * that are not running in a consensus. See Proposal 138 */
1830 if (consensus_method
>= 4 && !is_running
)
1833 /* Pick the version. */
1834 if (smartlist_len(versions
)) {
1835 sort_version_list(versions
, 0);
1836 chosen_version
= get_most_frequent_member(versions
);
1838 chosen_version
= NULL
;
1841 /* Pick a bandwidth */
1842 if (consensus_method
>= 6 && num_mbws
> 2) {
1843 rs_out
.has_bandwidth
= 1;
1844 rs_out
.bandwidth
= median_uint32(measured_bws
, num_mbws
);
1845 } else if (consensus_method
>= 5 && num_bandwidths
> 0) {
1846 rs_out
.has_bandwidth
= 1;
1847 rs_out
.bandwidth
= median_uint32(bandwidths
, num_bandwidths
);
1850 /* Fix bug 2203: Do not count BadExit nodes as Exits for bw weights */
1851 if (consensus_method
>= 11) {
1852 is_exit
= is_exit
&& !is_bad_exit
;
1855 if (consensus_method
>= MIN_METHOD_FOR_BW_WEIGHTS
) {
1856 if (rs_out
.has_bandwidth
) {
1857 T
+= rs_out
.bandwidth
;
1858 if (is_exit
&& is_guard
)
1859 D
+= rs_out
.bandwidth
;
1861 E
+= rs_out
.bandwidth
;
1863 G
+= rs_out
.bandwidth
;
1865 M
+= rs_out
.bandwidth
;
1867 log_warn(LD_BUG
, "Missing consensus bandwidth for router %s",
1872 /* Ok, we already picked a descriptor digest we want to list
1873 * previously. Now we want to use the exit policy summary from
1874 * that descriptor. If everybody plays nice all the voters who
1875 * listed that descriptor will have the same summary. If not then
1876 * something is fishy and we'll use the most common one (breaking
1877 * ties in favor of lexicographically larger one (only because it
1878 * lets me reuse more existing code.
1880 * The other case that can happen is that no authority that voted
1881 * for that descriptor has an exit policy summary. That's
1882 * probably quite unlikely but can happen. In that case we use
1883 * the policy that was most often listed in votes, again breaking
1884 * ties like in the previous case.
1886 if (consensus_method
>= 5) {
1887 /* Okay, go through all the votes for this router. We prepared
1888 * that list previously */
1889 const char *chosen_exitsummary
= NULL
;
1890 smartlist_clear(exitsummaries
);
1891 SMARTLIST_FOREACH(matching_descs
, vote_routerstatus_t
*, vsr
, {
1892 /* Check if the vote where this status comes from had the
1893 * proper descriptor */
1894 tor_assert(!memcmp(rs_out
.identity_digest
,
1895 vsr
->status
.identity_digest
,
1897 if (vsr
->status
.has_exitsummary
&&
1898 !memcmp(rs_out
.descriptor_digest
,
1899 vsr
->status
.descriptor_digest
,
1901 tor_assert(vsr
->status
.exitsummary
);
1902 smartlist_add(exitsummaries
, vsr
->status
.exitsummary
);
1903 if (!chosen_exitsummary
) {
1904 chosen_exitsummary
= vsr
->status
.exitsummary
;
1905 } else if (strcmp(chosen_exitsummary
, vsr
->status
.exitsummary
)) {
1906 /* Great. There's disagreement among the voters. That
1907 * really shouldn't be */
1908 exitsummary_disagreement
= 1;
1913 if (exitsummary_disagreement
) {
1914 char id
[HEX_DIGEST_LEN
+1];
1915 char dd
[HEX_DIGEST_LEN
+1];
1916 base16_encode(id
, sizeof(dd
), rs_out
.identity_digest
, DIGEST_LEN
);
1917 base16_encode(dd
, sizeof(dd
), rs_out
.descriptor_digest
, DIGEST_LEN
);
1918 log_warn(LD_DIR
, "The voters disagreed on the exit policy summary "
1919 " for router %s with descriptor %s. This really shouldn't"
1920 " have happened.", id
, dd
);
1922 smartlist_sort_strings(exitsummaries
);
1923 chosen_exitsummary
= get_most_frequent_member(exitsummaries
);
1924 } else if (!chosen_exitsummary
) {
1925 char id
[HEX_DIGEST_LEN
+1];
1926 char dd
[HEX_DIGEST_LEN
+1];
1927 base16_encode(id
, sizeof(dd
), rs_out
.identity_digest
, DIGEST_LEN
);
1928 base16_encode(dd
, sizeof(dd
), rs_out
.descriptor_digest
, DIGEST_LEN
);
1929 log_warn(LD_DIR
, "Not one of the voters that made us select"
1930 "descriptor %s for router %s had an exit policy"
1933 /* Ok, none of those voting for the digest we chose had an
1934 * exit policy for us. Well, that kinda sucks.
1936 smartlist_clear(exitsummaries
);
1937 SMARTLIST_FOREACH(matching_descs
, vote_routerstatus_t
*, vsr
, {
1938 if (vsr
->status
.has_exitsummary
)
1939 smartlist_add(exitsummaries
, vsr
->status
.exitsummary
);
1941 smartlist_sort_strings(exitsummaries
);
1942 chosen_exitsummary
= get_most_frequent_member(exitsummaries
);
1944 if (!chosen_exitsummary
)
1945 log_warn(LD_DIR
, "Wow, not one of the voters had an exit "
1946 "policy summary for %s. Wow.", id
);
1949 if (chosen_exitsummary
) {
1950 rs_out
.has_exitsummary
= 1;
1951 /* yea, discards the const */
1952 rs_out
.exitsummary
= (char *)chosen_exitsummary
;
1958 /* Okay!! Now we can write the descriptor... */
1959 /* First line goes into "buf". */
1960 routerstatus_format_entry(buf
, sizeof(buf
), &rs_out
, NULL
,
1962 smartlist_add(chunks
, tor_strdup(buf
));
1964 /* Now an m line, if applicable. */
1965 if (flavor
== FLAV_MICRODESC
&&
1966 !tor_digest256_is_zero(microdesc_digest
)) {
1967 char m
[BASE64_DIGEST256_LEN
+1], *cp
;
1968 digest256_to_base64(m
, microdesc_digest
);
1969 tor_asprintf(&cp
, "m %s\n", m
);
1970 smartlist_add(chunks
, cp
);
1972 /* Next line is all flags. The "\n" is missing. */
1973 smartlist_add(chunks
,
1974 smartlist_join_strings(chosen_flags
, " ", 0, NULL
));
1975 /* Now the version line. */
1976 if (chosen_version
) {
1977 smartlist_add(chunks
, tor_strdup("\nv "));
1978 smartlist_add(chunks
, tor_strdup(chosen_version
));
1980 smartlist_add(chunks
, tor_strdup("\n"));
1981 /* Now the weight line. */
1982 if (rs_out
.has_bandwidth
) {
1984 tor_asprintf(&cp
, "w Bandwidth=%d\n", rs_out
.bandwidth
);
1985 smartlist_add(chunks
, cp
);
1988 /* Now the exitpolicy summary line. */
1989 if (rs_out
.has_exitsummary
&& flavor
== FLAV_NS
) {
1990 tor_asprintf(&buf
, "p %s\n", rs_out
.exitsummary
);
1991 smartlist_add(chunks
, buf
);
1994 /* And the loop is over and we move on to the next router */
1999 tor_free(n_voter_flags
);
2000 tor_free(n_flag_voters
);
2001 for (i
= 0; i
< smartlist_len(votes
); ++i
)
2002 tor_free(flag_map
[i
]);
2004 tor_free(flag_counts
);
2005 tor_free(named_flag
);
2006 tor_free(unnamed_flag
);
2007 strmap_free(name_to_id_map
, NULL
);
2008 smartlist_free(matching_descs
);
2009 smartlist_free(chosen_flags
);
2010 smartlist_free(versions
);
2011 smartlist_free(exitsummaries
);
2012 tor_free(bandwidths
);
2013 tor_free(measured_bws
);
2016 if (consensus_method
>= MIN_METHOD_FOR_FOOTER
) {
2017 /* Starting with consensus method 9, we clearly mark the directory
2019 smartlist_add(chunks
, tor_strdup("directory-footer\n"));
2022 if (consensus_method
>= MIN_METHOD_FOR_BW_WEIGHTS
) {
2023 int64_t weight_scale
= BW_WEIGHT_SCALE
;
2024 char *bw_weight_param
= NULL
;
2026 // Parse params, extract BW_WEIGHT_SCALE if present
2027 // DO NOT use consensus_param_bw_weight_scale() in this code!
2028 // The consensus is not formed yet!
2030 if (strcmpstart(params
, "bwweightscale=") == 0)
2031 bw_weight_param
= params
;
2033 bw_weight_param
= strstr(params
, " bwweightscale=");
2036 if (bw_weight_param
) {
2038 char *eq
= strchr(bw_weight_param
, '=');
2040 weight_scale
= tor_parse_long(eq
+1, 10, INT32_MIN
, INT32_MAX
, &ok
,
2043 log_warn(LD_DIR
, "Bad element '%s' in bw weight param",
2044 escaped(bw_weight_param
));
2045 weight_scale
= BW_WEIGHT_SCALE
;
2048 log_warn(LD_DIR
, "Bad element '%s' in bw weight param",
2049 escaped(bw_weight_param
));
2050 weight_scale
= BW_WEIGHT_SCALE
;
2054 if (consensus_method
< 10) {
2055 networkstatus_compute_bw_weights_v9(chunks
, G
, M
, E
, D
, T
, weight_scale
);
2058 added_weights
= networkstatus_compute_bw_weights_v10(chunks
, G
, M
, E
, D
,
2063 /* Add a signature. */
2065 char digest
[DIGEST256_LEN
];
2066 char fingerprint
[HEX_DIGEST_LEN
+1];
2067 char signing_key_fingerprint
[HEX_DIGEST_LEN
+1];
2068 digest_algorithm_t digest_alg
=
2069 flavor
== FLAV_NS
? DIGEST_SHA1
: DIGEST_SHA256
;
2071 flavor
== FLAV_NS
? DIGEST_LEN
: DIGEST256_LEN
;
2072 const char *algname
= crypto_digest_algorithm_get_name(digest_alg
);
2076 smartlist_add(chunks
, tor_strdup("directory-signature "));
2078 /* Compute the hash of the chunks. */
2079 hash_list_members(digest
, digest_len
, chunks
, digest_alg
);
2081 /* Get the fingerprints */
2082 crypto_pk_get_fingerprint(identity_key
, fingerprint
, 0);
2083 crypto_pk_get_fingerprint(signing_key
, signing_key_fingerprint
, 0);
2085 /* add the junk that will go at the end of the line. */
2086 if (flavor
== FLAV_NS
) {
2087 tor_asprintf(&buf
, "%s %s\n", fingerprint
,
2088 signing_key_fingerprint
);
2090 tor_asprintf(&buf
, "%s %s %s\n",
2091 algname
, fingerprint
,
2092 signing_key_fingerprint
);
2094 smartlist_add(chunks
, buf
);
2095 /* And the signature. */
2097 if (router_append_dirobj_signature(sigbuf
, sizeof(sigbuf
),
2100 log_warn(LD_BUG
, "Couldn't sign consensus networkstatus.");
2101 return NULL
; /* This leaks, but it should never happen. */
2103 smartlist_add(chunks
, tor_strdup(sigbuf
));
2105 if (legacy_id_key_digest
&& legacy_signing_key
&& consensus_method
>= 3) {
2106 smartlist_add(chunks
, tor_strdup("directory-signature "));
2107 base16_encode(fingerprint
, sizeof(fingerprint
),
2108 legacy_id_key_digest
, DIGEST_LEN
);
2109 crypto_pk_get_fingerprint(legacy_signing_key
,
2110 signing_key_fingerprint
, 0);
2111 if (flavor
== FLAV_NS
) {
2112 tor_asprintf(&buf
, "%s %s\n", fingerprint
,
2113 signing_key_fingerprint
);
2115 tor_asprintf(&buf
, "%s %s %s\n",
2116 algname
, fingerprint
,
2117 signing_key_fingerprint
);
2119 smartlist_add(chunks
, buf
);
2121 if (router_append_dirobj_signature(sigbuf
, sizeof(sigbuf
),
2123 legacy_signing_key
)) {
2124 log_warn(LD_BUG
, "Couldn't sign consensus networkstatus.");
2125 return NULL
; /* This leaks, but it should never happen. */
2127 smartlist_add(chunks
, tor_strdup(sigbuf
));
2131 result
= smartlist_join_strings(chunks
, "", 0, NULL
);
2133 tor_free(client_versions
);
2134 tor_free(server_versions
);
2135 SMARTLIST_FOREACH(flags
, char *, cp
, tor_free(cp
));
2136 smartlist_free(flags
);
2137 SMARTLIST_FOREACH(chunks
, char *, cp
, tor_free(cp
));
2138 smartlist_free(chunks
);
2142 if (!(c
= networkstatus_parse_vote_from_string(result
, NULL
,
2143 NS_TYPE_CONSENSUS
))) {
2144 log_err(LD_BUG
, "Generated a networkstatus consensus we couldn't "
2149 // Verify balancing parameters
2150 if (consensus_method
>= MIN_METHOD_FOR_BW_WEIGHTS
&& added_weights
) {
2151 networkstatus_verify_bw_weights(c
);
2153 networkstatus_vote_free(c
);
2159 /** Given a consensus vote <b>target</b> and a set of detached signatures in
2160 * <b>sigs</b> that correspond to the same consensus, check whether there are
2161 * any new signatures in <b>src_voter_list</b> that should be added to
2162 * <b>target</b>. (A signature should be added if we have no signature for that
2163 * voter in <b>target</b> yet, or if we have no verifiable signature and the
2164 * new signature is verifiable.) Return the number of signatures added or
2165 * changed, or -1 if the document signed by <b>sigs</b> isn't the same
2166 * document as <b>target</b>. */
2168 networkstatus_add_detached_signatures(networkstatus_t
*target
,
2169 ns_detached_signatures_t
*sigs
,
2170 const char **msg_out
)
2174 smartlist_t
*siglist
;
2177 tor_assert(target
->type
== NS_TYPE_CONSENSUS
);
2179 flavor
= networkstatus_get_flavor_name(target
->flavor
);
2181 /* Do the times seem right? */
2182 if (target
->valid_after
!= sigs
->valid_after
) {
2183 *msg_out
= "Valid-After times do not match "
2184 "when adding detached signatures to consensus";
2187 if (target
->fresh_until
!= sigs
->fresh_until
) {
2188 *msg_out
= "Fresh-until times do not match "
2189 "when adding detached signatures to consensus";
2192 if (target
->valid_until
!= sigs
->valid_until
) {
2193 *msg_out
= "Valid-until times do not match "
2194 "when adding detached signatures to consensus";
2197 siglist
= strmap_get(sigs
->signatures
, flavor
);
2199 *msg_out
= "No signatures for given consensus flavor";
2203 /** Make sure all the digests we know match, and at least one matches. */
2205 digests_t
*digests
= strmap_get(sigs
->digests
, flavor
);
2207 digest_algorithm_t alg
;
2209 *msg_out
= "No digests for given consensus flavor";
2212 for (alg
= DIGEST_SHA1
; alg
< N_DIGEST_ALGORITHMS
; ++alg
) {
2213 if (!tor_mem_is_zero(digests
->d
[alg
], DIGEST256_LEN
)) {
2214 if (!memcmp(target
->digests
.d
[alg
], digests
->d
[alg
], DIGEST256_LEN
)) {
2217 *msg_out
= "Mismatched digest.";
2223 *msg_out
= "No regognized digests for given consensus flavor";
2227 /* For each voter in src... */
2228 SMARTLIST_FOREACH_BEGIN(siglist
, document_signature_t
*, sig
) {
2229 char voter_identity
[HEX_DIGEST_LEN
+1];
2230 networkstatus_voter_info_t
*target_voter
=
2231 networkstatus_get_voter_by_id(target
, sig
->identity_digest
);
2232 authority_cert_t
*cert
= NULL
;
2233 const char *algorithm
;
2234 document_signature_t
*old_sig
= NULL
;
2236 algorithm
= crypto_digest_algorithm_get_name(sig
->alg
);
2238 base16_encode(voter_identity
, sizeof(voter_identity
),
2239 sig
->identity_digest
, DIGEST_LEN
);
2240 log_info(LD_DIR
, "Looking at signature from %s using %s", voter_identity
,
2242 /* If the target doesn't know about this voter, then forget it. */
2243 if (!target_voter
) {
2244 log_info(LD_DIR
, "We do not know any voter with ID %s", voter_identity
);
2248 old_sig
= voter_get_sig_by_algorithm(target_voter
, sig
->alg
);
2250 /* If the target already has a good signature from this voter, then skip
2252 if (old_sig
&& old_sig
->good_signature
) {
2253 log_info(LD_DIR
, "We already have a good signature from %s using %s",
2254 voter_identity
, algorithm
);
2258 /* Try checking the signature if we haven't already. */
2259 if (!sig
->good_signature
&& !sig
->bad_signature
) {
2260 cert
= authority_cert_get_by_digests(sig
->identity_digest
,
2261 sig
->signing_key_digest
);
2263 networkstatus_check_document_signature(target
, sig
, cert
);
2266 /* If this signature is good, or we don't have any signature yet,
2267 * then maybe add it. */
2268 if (sig
->good_signature
|| !old_sig
|| old_sig
->bad_signature
) {
2269 log_info(LD_DIR
, "Adding signature from %s with %s", voter_identity
,
2273 smartlist_remove(target_voter
->sigs
, old_sig
);
2274 document_signature_free(old_sig
);
2276 smartlist_add(target_voter
->sigs
, document_signature_dup(sig
));
2278 log_info(LD_DIR
, "Not adding signature from %s", voter_identity
);
2280 } SMARTLIST_FOREACH_END(sig
);
2285 /** Return a newly allocated string containing all the signatures on
2286 * <b>consensus</b> by all voters. If <b>for_detached_signatures</b> is true,
2287 * then the signatures will be put in a detached signatures document, so
2288 * prefix any non-NS-flavored signatures with "additional-signature" rather
2289 * than "directory-signature". */
2291 networkstatus_format_signatures(networkstatus_t
*consensus
,
2292 int for_detached_signatures
)
2294 smartlist_t
*elements
;
2296 char *result
= NULL
;
2298 const consensus_flavor_t flavor
= consensus
->flavor
;
2299 const char *flavor_name
= networkstatus_get_flavor_name(flavor
);
2300 const char *keyword
;
2302 if (for_detached_signatures
&& flavor
!= FLAV_NS
)
2303 keyword
= "additional-signature";
2305 keyword
= "directory-signature";
2307 elements
= smartlist_create();
2309 SMARTLIST_FOREACH_BEGIN(consensus
->voters
, networkstatus_voter_info_t
*, v
) {
2310 SMARTLIST_FOREACH_BEGIN(v
->sigs
, document_signature_t
*, sig
) {
2311 char sk
[HEX_DIGEST_LEN
+1];
2312 char id
[HEX_DIGEST_LEN
+1];
2313 if (!sig
->signature
|| sig
->bad_signature
)
2316 base16_encode(sk
, sizeof(sk
), sig
->signing_key_digest
, DIGEST_LEN
);
2317 base16_encode(id
, sizeof(id
), sig
->identity_digest
, DIGEST_LEN
);
2318 if (flavor
== FLAV_NS
) {
2319 tor_snprintf(buf
, sizeof(buf
),
2320 "%s %s %s\n-----BEGIN SIGNATURE-----\n",
2323 const char *digest_name
=
2324 crypto_digest_algorithm_get_name(sig
->alg
);
2325 tor_snprintf(buf
, sizeof(buf
),
2326 "%s%s%s %s %s %s\n-----BEGIN SIGNATURE-----\n",
2328 for_detached_signatures
? " " : "",
2329 for_detached_signatures
? flavor_name
: "",
2330 digest_name
, id
, sk
);
2332 smartlist_add(elements
, tor_strdup(buf
));
2333 base64_encode(buf
, sizeof(buf
), sig
->signature
, sig
->signature_len
);
2334 strlcat(buf
, "-----END SIGNATURE-----\n", sizeof(buf
));
2335 smartlist_add(elements
, tor_strdup(buf
));
2336 } SMARTLIST_FOREACH_END(sig
);
2337 } SMARTLIST_FOREACH_END(v
);
2339 result
= smartlist_join_strings(elements
, "", 0, NULL
);
2340 SMARTLIST_FOREACH(elements
, char *, cp
, tor_free(cp
));
2341 smartlist_free(elements
);
2347 /** Return a newly allocated string holding the detached-signatures document
2348 * corresponding to the signatures on <b>consensuses</b>, which must contain
2349 * exactly one FLAV_NS consensus, and no more than one consensus for each
2352 networkstatus_get_detached_signatures(smartlist_t
*consensuses
)
2354 smartlist_t
*elements
;
2356 char *result
= NULL
, *sigs
= NULL
;
2357 networkstatus_t
*consensus_ns
= NULL
;
2358 tor_assert(consensuses
);
2360 SMARTLIST_FOREACH(consensuses
, networkstatus_t
*, ns
, {
2362 tor_assert(ns
->type
== NS_TYPE_CONSENSUS
);
2363 if (ns
&& ns
->flavor
== FLAV_NS
)
2366 if (!consensus_ns
) {
2367 log_warn(LD_BUG
, "No NS consensus given.");
2371 elements
= smartlist_create();
2374 char va_buf
[ISO_TIME_LEN
+1], fu_buf
[ISO_TIME_LEN
+1],
2375 vu_buf
[ISO_TIME_LEN
+1];
2376 char d
[HEX_DIGEST_LEN
+1];
2378 base16_encode(d
, sizeof(d
),
2379 consensus_ns
->digests
.d
[DIGEST_SHA1
], DIGEST_LEN
);
2380 format_iso_time(va_buf
, consensus_ns
->valid_after
);
2381 format_iso_time(fu_buf
, consensus_ns
->fresh_until
);
2382 format_iso_time(vu_buf
, consensus_ns
->valid_until
);
2384 tor_snprintf(buf
, sizeof(buf
),
2385 "consensus-digest %s\n"
2388 "valid-until %s\n", d
, va_buf
, fu_buf
, vu_buf
);
2389 smartlist_add(elements
, tor_strdup(buf
));
2392 /* Get all the digests for the non-FLAV_NS consensuses */
2393 SMARTLIST_FOREACH_BEGIN(consensuses
, networkstatus_t
*, ns
) {
2394 const char *flavor_name
= networkstatus_get_flavor_name(ns
->flavor
);
2396 if (ns
->flavor
== FLAV_NS
)
2399 /* start with SHA256; we don't include SHA1 for anything but the basic
2401 for (alg
= DIGEST_SHA256
; alg
< N_DIGEST_ALGORITHMS
; ++alg
) {
2402 char d
[HEX_DIGEST256_LEN
+1];
2403 const char *alg_name
=
2404 crypto_digest_algorithm_get_name(alg
);
2405 if (tor_mem_is_zero(ns
->digests
.d
[alg
], DIGEST256_LEN
))
2407 base16_encode(d
, sizeof(d
), ns
->digests
.d
[alg
], DIGEST256_LEN
);
2408 tor_snprintf(buf
, sizeof(buf
), "additional-digest %s %s %s\n",
2409 flavor_name
, alg_name
, d
);
2410 smartlist_add(elements
, tor_strdup(buf
));
2412 } SMARTLIST_FOREACH_END(ns
);
2414 /* Now get all the sigs for non-FLAV_NS consensuses */
2415 SMARTLIST_FOREACH_BEGIN(consensuses
, networkstatus_t
*, ns
) {
2417 if (ns
->flavor
== FLAV_NS
)
2419 sigs
= networkstatus_format_signatures(ns
, 1);
2421 log_warn(LD_DIR
, "Couldn't format signatures");
2424 smartlist_add(elements
, sigs
);
2425 } SMARTLIST_FOREACH_END(ns
);
2427 /* Now add the FLAV_NS consensus signatrures. */
2428 sigs
= networkstatus_format_signatures(consensus_ns
, 1);
2431 smartlist_add(elements
, sigs
);
2433 result
= smartlist_join_strings(elements
, "", 0, NULL
);
2435 SMARTLIST_FOREACH(elements
, char *, cp
, tor_free(cp
));
2436 smartlist_free(elements
);
2440 /** Return a newly allocated string holding a detached-signatures document for
2441 * all of the in-progress consensuses in the <b>n_flavors</b>-element array at
2442 * <b>pending</b>. */
2444 get_detached_signatures_from_pending_consensuses(pending_consensus_t
*pending
,
2449 smartlist_t
*c
= smartlist_create();
2450 for (flav
= 0; flav
< n_flavors
; ++flav
) {
2451 if (pending
[flav
].consensus
)
2452 smartlist_add(c
, pending
[flav
].consensus
);
2454 signatures
= networkstatus_get_detached_signatures(c
);
2459 /** Release all storage held in <b>s</b>. */
2461 ns_detached_signatures_free(ns_detached_signatures_t
*s
)
2465 if (s
->signatures
) {
2466 STRMAP_FOREACH(s
->signatures
, flavor
, smartlist_t
*, sigs
) {
2467 SMARTLIST_FOREACH(sigs
, document_signature_t
*, sig
,
2468 document_signature_free(sig
));
2469 smartlist_free(sigs
);
2470 } STRMAP_FOREACH_END
;
2471 strmap_free(s
->signatures
, NULL
);
2472 strmap_free(s
->digests
, _tor_free
);
2479 * Certificate functions
2482 /** Allocate and return a new authority_cert_t with the same contents as
2485 authority_cert_dup(authority_cert_t
*cert
)
2487 authority_cert_t
*out
= tor_malloc(sizeof(authority_cert_t
));
2490 memcpy(out
, cert
, sizeof(authority_cert_t
));
2491 /* Now copy pointed-to things. */
2492 out
->cache_info
.signed_descriptor_body
=
2493 tor_strndup(cert
->cache_info
.signed_descriptor_body
,
2494 cert
->cache_info
.signed_descriptor_len
);
2495 out
->cache_info
.saved_location
= SAVED_NOWHERE
;
2496 out
->identity_key
= crypto_pk_dup_key(cert
->identity_key
);
2497 out
->signing_key
= crypto_pk_dup_key(cert
->signing_key
);
2506 /** Set *<b>timing_out</b> to the intervals at which we would like to vote.
2507 * Note that these aren't the intervals we'll use to vote; they're the ones
2508 * that we'll vote to use. */
2510 dirvote_get_preferred_voting_intervals(vote_timing_t
*timing_out
)
2512 or_options_t
*options
= get_options();
2514 tor_assert(timing_out
);
2516 timing_out
->vote_interval
= options
->V3AuthVotingInterval
;
2517 timing_out
->n_intervals_valid
= options
->V3AuthNIntervalsValid
;
2518 timing_out
->vote_delay
= options
->V3AuthVoteDelay
;
2519 timing_out
->dist_delay
= options
->V3AuthDistDelay
;
2522 /** Return the start of the next interval of size <b>interval</b> (in seconds)
2523 * after <b>now</b>. Midnight always starts a fresh interval, and if the last
2524 * interval of a day would be truncated to less than half its size, it is
2525 * rolled into the previous interval. */
2527 dirvote_get_start_of_next_interval(time_t now
, int interval
)
2530 time_t midnight_today
;
2531 time_t midnight_tomorrow
;
2534 tor_gmtime_r(&now
, &tm
);
2539 midnight_today
= tor_timegm(&tm
);
2540 midnight_tomorrow
= midnight_today
+ (24*60*60);
2542 next
= midnight_today
+ ((now
-midnight_today
)/interval
+ 1)*interval
;
2544 /* Intervals never cross midnight. */
2545 if (next
> midnight_tomorrow
)
2546 next
= midnight_tomorrow
;
2548 /* If the interval would only last half as long as it's supposed to, then
2549 * skip over to the next day. */
2550 if (next
+ interval
/2 > midnight_tomorrow
)
2551 next
= midnight_tomorrow
;
2556 /** Scheduling information for a voting interval. */
2558 /** When do we generate and distribute our vote for this interval? */
2559 time_t voting_starts
;
2560 /** When do we send an HTTP request for any votes that we haven't
2561 * been posted yet?*/
2562 time_t fetch_missing_votes
;
2563 /** When do we give up on getting more votes and generate a consensus? */
2565 /** When do we send an HTTP request for any signatures we're expecting to
2566 * see on the consensus? */
2567 time_t fetch_missing_signatures
;
2568 /** When do we publish the consensus? */
2569 time_t interval_starts
;
2571 /* True iff we have generated and distributed our vote. */
2573 /* True iff we've requested missing votes. */
2574 int have_fetched_missing_votes
;
2575 /* True iff we have built a consensus and sent the signatures around. */
2576 int have_built_consensus
;
2577 /* True iff we've fetched missing signatures. */
2578 int have_fetched_missing_signatures
;
2579 /* True iff we have published our consensus. */
2580 int have_published_consensus
;
2581 } voting_schedule
= {0,0,0,0,0,0,0,0,0,0};
2583 /** Set voting_schedule to hold the timing for the next vote we should be
2586 dirvote_recalculate_timing(or_options_t
*options
, time_t now
)
2588 int interval
, vote_delay
, dist_delay
;
2591 networkstatus_t
*consensus
;
2593 if (!authdir_mode_v3(options
))
2596 consensus
= networkstatus_get_live_consensus(now
);
2598 memset(&voting_schedule
, 0, sizeof(voting_schedule
));
2601 interval
= (int)( consensus
->fresh_until
- consensus
->valid_after
);
2602 vote_delay
= consensus
->vote_seconds
;
2603 dist_delay
= consensus
->dist_seconds
;
2605 interval
= options
->TestingV3AuthInitialVotingInterval
;
2606 vote_delay
= options
->TestingV3AuthInitialVoteDelay
;
2607 dist_delay
= options
->TestingV3AuthInitialDistDelay
;
2610 tor_assert(interval
> 0);
2612 if (vote_delay
+ dist_delay
> interval
/2)
2613 vote_delay
= dist_delay
= interval
/ 4;
2615 start
= voting_schedule
.interval_starts
=
2616 dirvote_get_start_of_next_interval(now
,interval
);
2617 end
= dirvote_get_start_of_next_interval(start
+1, interval
);
2619 tor_assert(end
> start
);
2621 voting_schedule
.fetch_missing_signatures
= start
- (dist_delay
/2);
2622 voting_schedule
.voting_ends
= start
- dist_delay
;
2623 voting_schedule
.fetch_missing_votes
= start
- dist_delay
- (vote_delay
/2);
2624 voting_schedule
.voting_starts
= start
- dist_delay
- vote_delay
;
2627 char tbuf
[ISO_TIME_LEN
+1];
2628 format_iso_time(tbuf
, voting_schedule
.interval_starts
);
2629 log_notice(LD_DIR
,"Choosing expected valid-after time as %s: "
2630 "consensus_set=%d, interval=%d",
2631 tbuf
, consensus
?1:0, interval
);
2635 /** Entry point: Take whatever voting actions are pending as of <b>now</b>. */
2637 dirvote_act(or_options_t
*options
, time_t now
)
2639 if (!authdir_mode_v3(options
))
2641 if (!voting_schedule
.voting_starts
) {
2642 char *keys
= list_v3_auth_ids();
2643 authority_cert_t
*c
= get_my_v3_authority_cert();
2644 log_notice(LD_DIR
, "Scheduling voting. Known authority IDs are %s. "
2646 keys
, hex_str(c
->cache_info
.identity_digest
, DIGEST_LEN
));
2648 dirvote_recalculate_timing(options
, now
);
2650 if (voting_schedule
.voting_starts
< now
&& !voting_schedule
.have_voted
) {
2651 log_notice(LD_DIR
, "Time to vote.");
2652 dirvote_perform_vote();
2653 voting_schedule
.have_voted
= 1;
2655 if (voting_schedule
.fetch_missing_votes
< now
&&
2656 !voting_schedule
.have_fetched_missing_votes
) {
2657 log_notice(LD_DIR
, "Time to fetch any votes that we're missing.");
2658 dirvote_fetch_missing_votes();
2659 voting_schedule
.have_fetched_missing_votes
= 1;
2661 if (voting_schedule
.voting_ends
< now
&&
2662 !voting_schedule
.have_built_consensus
) {
2663 log_notice(LD_DIR
, "Time to compute a consensus.");
2664 dirvote_compute_consensuses();
2665 /* XXXX We will want to try again later if we haven't got enough
2666 * votes yet. Implement this if it turns out to ever happen. */
2667 voting_schedule
.have_built_consensus
= 1;
2669 if (voting_schedule
.fetch_missing_signatures
< now
&&
2670 !voting_schedule
.have_fetched_missing_signatures
) {
2671 log_notice(LD_DIR
, "Time to fetch any signatures that we're missing.");
2672 dirvote_fetch_missing_signatures();
2673 voting_schedule
.have_fetched_missing_signatures
= 1;
2675 if (voting_schedule
.interval_starts
< now
&&
2676 !voting_schedule
.have_published_consensus
) {
2677 log_notice(LD_DIR
, "Time to publish the consensus and discard old votes");
2678 dirvote_publish_consensus();
2679 dirvote_clear_votes(0);
2680 voting_schedule
.have_published_consensus
= 1;
2681 /* XXXX We will want to try again later if we haven't got enough
2682 * signatures yet. Implement this if it turns out to ever happen. */
2683 dirvote_recalculate_timing(options
, now
);
2687 /** A vote networkstatus_t and its unparsed body: held around so we can
2688 * use it to generate a consensus (at voting_ends) and so we can serve it to
2689 * other authorities that might want it. */
2690 typedef struct pending_vote_t
{
2691 cached_dir_t
*vote_body
;
2692 networkstatus_t
*vote
;
2695 /** List of pending_vote_t for the current vote. Before we've used them to
2696 * build a consensus, the votes go here. */
2697 static smartlist_t
*pending_vote_list
= NULL
;
2698 /** List of pending_vote_t for the previous vote. After we've used them to
2699 * build a consensus, the votes go here for the next period. */
2700 static smartlist_t
*previous_vote_list
= NULL
;
2702 static pending_consensus_t pending_consensuses
[N_CONSENSUS_FLAVORS
];
2704 /** The detached signatures for the consensus that we're currently
2706 static char *pending_consensus_signatures
= NULL
;
2708 /** List of ns_detached_signatures_t: hold signatures that get posted to us
2709 * before we have generated the consensus on our own. */
2710 static smartlist_t
*pending_consensus_signature_list
= NULL
;
2712 /** Generate a networkstatus vote and post it to all the v3 authorities.
2713 * (V3 Authority only) */
2715 dirvote_perform_vote(void)
2717 crypto_pk_env_t
*key
= get_my_v3_authority_signing_key();
2718 authority_cert_t
*cert
= get_my_v3_authority_cert();
2719 networkstatus_t
*ns
;
2721 pending_vote_t
*pending_vote
;
2722 time_t now
= time(NULL
);
2725 const char *msg
= "";
2727 if (!cert
|| !key
) {
2728 log_warn(LD_NET
, "Didn't find key/certificate to generate v3 vote");
2730 } else if (cert
->expires
< now
) {
2731 log_warn(LD_NET
, "Can't generate v3 vote with expired certificate");
2734 if (!(ns
= dirserv_generate_networkstatus_vote_obj(key
, cert
)))
2737 contents
= format_networkstatus_vote(key
, ns
);
2738 networkstatus_vote_free(ns
);
2742 pending_vote
= dirvote_add_vote(contents
, &msg
, &status
);
2744 if (!pending_vote
) {
2745 log_warn(LD_DIR
, "Couldn't store my own vote! (I told myself, '%s'.)",
2750 directory_post_to_dirservers(DIR_PURPOSE_UPLOAD_VOTE
,
2751 ROUTER_PURPOSE_GENERAL
,
2753 pending_vote
->vote_body
->dir
,
2754 pending_vote
->vote_body
->dir_len
, 0);
2755 log_notice(LD_DIR
, "Vote posted.");
2759 /** Send an HTTP request to every other v3 authority, for the votes of every
2760 * authority for which we haven't received a vote yet in this period. (V3
2761 * authority only) */
2763 dirvote_fetch_missing_votes(void)
2765 smartlist_t
*missing_fps
= smartlist_create();
2768 SMARTLIST_FOREACH(router_get_trusted_dir_servers(),
2769 trusted_dir_server_t
*, ds
,
2771 if (!(ds
->type
& V3_AUTHORITY
))
2773 if (!dirvote_get_vote(ds
->v3_identity_digest
,
2774 DGV_BY_ID
|DGV_INCLUDE_PENDING
)) {
2775 char *cp
= tor_malloc(HEX_DIGEST_LEN
+1);
2776 base16_encode(cp
, HEX_DIGEST_LEN
+1, ds
->v3_identity_digest
,
2778 smartlist_add(missing_fps
, cp
);
2782 if (!smartlist_len(missing_fps
)) {
2783 smartlist_free(missing_fps
);
2786 log_notice(LOG_NOTICE
, "We're missing votes from %d authorities. Asking "
2787 "every other authority for a copy.", smartlist_len(missing_fps
));
2788 resource
= smartlist_join_strings(missing_fps
, "+", 0, NULL
);
2789 directory_get_from_all_authorities(DIR_PURPOSE_FETCH_STATUS_VOTE
,
2792 SMARTLIST_FOREACH(missing_fps
, char *, cp
, tor_free(cp
));
2793 smartlist_free(missing_fps
);
2796 /** Send a request to every other authority for its detached signatures,
2797 * unless we have signatures from all other v3 authorities already. */
2799 dirvote_fetch_missing_signatures(void)
2803 for (i
=0; i
< N_CONSENSUS_FLAVORS
; ++i
) {
2804 networkstatus_t
*consensus
= pending_consensuses
[i
].consensus
;
2806 networkstatus_check_consensus_signature(consensus
, -1) == 1) {
2807 /* We have no consensus, or we have one that's signed by everybody. */
2815 directory_get_from_all_authorities(DIR_PURPOSE_FETCH_DETACHED_SIGNATURES
,
2819 /** Release all storage held by pending consensuses (those waiting for
2822 dirvote_clear_pending_consensuses(void)
2825 for (i
= 0; i
< N_CONSENSUS_FLAVORS
; ++i
) {
2826 pending_consensus_t
*pc
= &pending_consensuses
[i
];
2829 networkstatus_vote_free(pc
->consensus
);
2830 pc
->consensus
= NULL
;
2834 /** Drop all currently pending votes, consensus, and detached signatures. */
2836 dirvote_clear_votes(int all_votes
)
2838 if (!previous_vote_list
)
2839 previous_vote_list
= smartlist_create();
2840 if (!pending_vote_list
)
2841 pending_vote_list
= smartlist_create();
2843 /* All "previous" votes are now junk. */
2844 SMARTLIST_FOREACH(previous_vote_list
, pending_vote_t
*, v
, {
2845 cached_dir_decref(v
->vote_body
);
2846 v
->vote_body
= NULL
;
2847 networkstatus_vote_free(v
->vote
);
2850 smartlist_clear(previous_vote_list
);
2853 /* If we're dumping all the votes, we delete the pending ones. */
2854 SMARTLIST_FOREACH(pending_vote_list
, pending_vote_t
*, v
, {
2855 cached_dir_decref(v
->vote_body
);
2856 v
->vote_body
= NULL
;
2857 networkstatus_vote_free(v
->vote
);
2861 /* Otherwise, we move them into "previous". */
2862 smartlist_add_all(previous_vote_list
, pending_vote_list
);
2864 smartlist_clear(pending_vote_list
);
2866 if (pending_consensus_signature_list
) {
2867 SMARTLIST_FOREACH(pending_consensus_signature_list
, char *, cp
,
2869 smartlist_clear(pending_consensus_signature_list
);
2871 tor_free(pending_consensus_signatures
);
2872 dirvote_clear_pending_consensuses();
2875 /** Return a newly allocated string containing the hex-encoded v3 authority
2876 identity digest of every recognized v3 authority. */
2878 list_v3_auth_ids(void)
2880 smartlist_t
*known_v3_keys
= smartlist_create();
2882 SMARTLIST_FOREACH(router_get_trusted_dir_servers(),
2883 trusted_dir_server_t
*, ds
,
2884 if ((ds
->type
& V3_AUTHORITY
) &&
2885 !tor_digest_is_zero(ds
->v3_identity_digest
))
2886 smartlist_add(known_v3_keys
,
2887 tor_strdup(hex_str(ds
->v3_identity_digest
, DIGEST_LEN
))));
2888 keys
= smartlist_join_strings(known_v3_keys
, ", ", 0, NULL
);
2889 SMARTLIST_FOREACH(known_v3_keys
, char *, cp
, tor_free(cp
));
2890 smartlist_free(known_v3_keys
);
2894 /** Called when we have received a networkstatus vote in <b>vote_body</b>.
2895 * Parse and validate it, and on success store it as a pending vote (which we
2896 * then return). Return NULL on failure. Sets *<b>msg_out</b> and
2897 * *<b>status_out</b> to an HTTP response and status code. (V3 authority
2900 dirvote_add_vote(const char *vote_body
, const char **msg_out
, int *status_out
)
2902 networkstatus_t
*vote
;
2903 networkstatus_voter_info_t
*vi
;
2904 trusted_dir_server_t
*ds
;
2905 pending_vote_t
*pending_vote
= NULL
;
2906 const char *end_of_vote
= NULL
;
2908 tor_assert(vote_body
);
2909 tor_assert(msg_out
);
2910 tor_assert(status_out
);
2912 if (!pending_vote_list
)
2913 pending_vote_list
= smartlist_create();
2918 vote
= networkstatus_parse_vote_from_string(vote_body
, &end_of_vote
,
2921 end_of_vote
= vote_body
+ strlen(vote_body
);
2923 log_warn(LD_DIR
, "Couldn't parse vote: length was %d",
2924 (int)strlen(vote_body
));
2925 *msg_out
= "Unable to parse vote";
2928 tor_assert(smartlist_len(vote
->voters
) == 1);
2929 vi
= get_voter(vote
);
2931 int any_sig_good
= 0;
2932 SMARTLIST_FOREACH(vi
->sigs
, document_signature_t
*, sig
,
2933 if (sig
->good_signature
)
2935 tor_assert(any_sig_good
);
2937 ds
= trusteddirserver_get_by_v3_auth_digest(vi
->identity_digest
);
2939 char *keys
= list_v3_auth_ids();
2940 log_warn(LD_DIR
, "Got a vote from an authority (nickname %s, address %s) "
2941 "with authority key ID %s. "
2942 "This key ID is not recognized. Known v3 key IDs are: %s",
2943 vi
->nickname
, vi
->address
,
2944 hex_str(vi
->identity_digest
, DIGEST_LEN
), keys
);
2946 *msg_out
= "Vote not from a recognized v3 authority";
2949 tor_assert(vote
->cert
);
2950 if (!authority_cert_get_by_digests(vote
->cert
->cache_info
.identity_digest
,
2951 vote
->cert
->signing_key_digest
)) {
2952 /* Hey, it's a new cert! */
2953 trusted_dirs_load_certs_from_string(
2954 vote
->cert
->cache_info
.signed_descriptor_body
,
2955 0 /* from_store */, 1 /*flush*/);
2956 if (!authority_cert_get_by_digests(vote
->cert
->cache_info
.identity_digest
,
2957 vote
->cert
->signing_key_digest
)) {
2958 log_warn(LD_BUG
, "We added a cert, but still couldn't find it.");
2962 /* Is it for the right period? */
2963 if (vote
->valid_after
!= voting_schedule
.interval_starts
) {
2964 char tbuf1
[ISO_TIME_LEN
+1], tbuf2
[ISO_TIME_LEN
+1];
2965 format_iso_time(tbuf1
, vote
->valid_after
);
2966 format_iso_time(tbuf2
, voting_schedule
.interval_starts
);
2967 log_warn(LD_DIR
, "Rejecting vote from %s with valid-after time of %s; "
2968 "we were expecting %s", vi
->address
, tbuf1
, tbuf2
);
2969 *msg_out
= "Bad valid-after time";
2973 /* Fetch any new router descriptors we just learned about */
2974 update_consensus_router_descriptor_downloads(time(NULL
), 1, vote
);
2976 /* Now see whether we already have a vote from this authority. */
2977 SMARTLIST_FOREACH(pending_vote_list
, pending_vote_t
*, v
, {
2978 if (! memcmp(v
->vote
->cert
->cache_info
.identity_digest
,
2979 vote
->cert
->cache_info
.identity_digest
,
2981 networkstatus_voter_info_t
*vi_old
= get_voter(v
->vote
);
2982 if (!memcmp(vi_old
->vote_digest
, vi
->vote_digest
, DIGEST_LEN
)) {
2983 /* Ah, it's the same vote. Not a problem. */
2984 log_info(LD_DIR
, "Discarding a vote we already have (from %s).",
2986 if (*status_out
< 200)
2989 } else if (v
->vote
->published
< vote
->published
) {
2990 log_notice(LD_DIR
, "Replacing an older pending vote from this "
2992 cached_dir_decref(v
->vote_body
);
2993 networkstatus_vote_free(v
->vote
);
2994 v
->vote_body
= new_cached_dir(tor_strndup(vote_body
,
2995 end_of_vote
-vote_body
),
2999 !strcmpstart(end_of_vote
, "network-status-version"))
3002 if (*status_out
< 200)
3008 *msg_out
= "Already have a newer pending vote";
3014 pending_vote
= tor_malloc_zero(sizeof(pending_vote_t
));
3015 pending_vote
->vote_body
= new_cached_dir(tor_strndup(vote_body
,
3016 end_of_vote
-vote_body
),
3018 pending_vote
->vote
= vote
;
3019 smartlist_add(pending_vote_list
, pending_vote
);
3021 if (!strcmpstart(end_of_vote
, "network-status-version ")) {
3022 vote_body
= end_of_vote
;
3031 *msg_out
= "Error adding vote";
3032 if (*status_out
< 400)
3036 networkstatus_vote_free(vote
);
3038 if (end_of_vote
&& !strcmpstart(end_of_vote
, "network-status-version ")) {
3039 vote_body
= end_of_vote
;
3045 if (*status_out
< 200)
3048 if (!any_failed
&& !pending_vote
) {
3049 *msg_out
= "Duplicate discarded";
3055 return any_failed
? NULL
: pending_vote
;
3058 /** Try to compute a v3 networkstatus consensus from the currently pending
3059 * votes. Return 0 on success, -1 on failure. Store the consensus in
3060 * pending_consensus: it won't be ready to be published until we have
3061 * everybody else's signatures collected too. (V3 Authority only) */
3063 dirvote_compute_consensuses(void)
3065 /* Have we got enough votes to try? */
3066 int n_votes
, n_voters
, n_vote_running
= 0;
3067 smartlist_t
*votes
= NULL
, *votestrings
= NULL
;
3068 char *consensus_body
= NULL
, *signatures
= NULL
, *votefile
;
3069 networkstatus_t
*consensus
= NULL
;
3070 authority_cert_t
*my_cert
;
3071 pending_consensus_t pending
[N_CONSENSUS_FLAVORS
];
3074 memset(pending
, 0, sizeof(pending
));
3076 if (!pending_vote_list
)
3077 pending_vote_list
= smartlist_create();
3079 n_voters
= get_n_authorities(V3_AUTHORITY
);
3080 n_votes
= smartlist_len(pending_vote_list
);
3081 if (n_votes
<= n_voters
/2) {
3082 log_warn(LD_DIR
, "We don't have enough votes to generate a consensus: "
3083 "%d of %d", n_votes
, n_voters
/2);
3086 tor_assert(pending_vote_list
);
3087 SMARTLIST_FOREACH(pending_vote_list
, pending_vote_t
*, v
, {
3088 if (smartlist_string_isin(v
->vote
->known_flags
, "Running"))
3091 if (!n_vote_running
) {
3092 /* See task 1066. */
3093 log_warn(LD_DIR
, "Nobody has voted on the Running flag. Generating "
3094 "and publishing a consensus without Running nodes "
3095 "would make many clients stop working. Not "
3096 "generating a consensus!");
3100 if (!(my_cert
= get_my_v3_authority_cert())) {
3101 log_warn(LD_DIR
, "Can't generate consensus without a certificate.");
3105 votes
= smartlist_create();
3106 votestrings
= smartlist_create();
3107 SMARTLIST_FOREACH(pending_vote_list
, pending_vote_t
*, v
,
3109 sized_chunk_t
*c
= tor_malloc(sizeof(sized_chunk_t
));
3110 c
->bytes
= v
->vote_body
->dir
;
3111 c
->len
= v
->vote_body
->dir_len
;
3112 smartlist_add(votestrings
, c
); /* collect strings to write to disk */
3114 smartlist_add(votes
, v
->vote
); /* collect votes to compute consensus */
3117 votefile
= get_datadir_fname("v3-status-votes");
3118 write_chunks_to_file(votefile
, votestrings
, 0);
3120 SMARTLIST_FOREACH(votestrings
, sized_chunk_t
*, c
, tor_free(c
));
3121 smartlist_free(votestrings
);
3124 char legacy_dbuf
[DIGEST_LEN
];
3125 crypto_pk_env_t
*legacy_sign
=NULL
;
3126 char *legacy_id_digest
= NULL
;
3127 int n_generated
= 0;
3128 if (get_options()->V3AuthUseLegacyKey
) {
3129 authority_cert_t
*cert
= get_my_v3_legacy_cert();
3130 legacy_sign
= get_my_v3_legacy_signing_key();
3132 crypto_pk_get_digest(cert
->identity_key
, legacy_dbuf
);
3133 legacy_id_digest
= legacy_dbuf
;
3137 for (flav
= 0; flav
< N_CONSENSUS_FLAVORS
; ++flav
) {
3138 const char *flavor_name
= networkstatus_get_flavor_name(flav
);
3139 consensus_body
= networkstatus_compute_consensus(
3141 my_cert
->identity_key
,
3142 get_my_v3_authority_signing_key(), legacy_id_digest
, legacy_sign
,
3145 if (!consensus_body
) {
3146 log_warn(LD_DIR
, "Couldn't generate a %s consensus at all!",
3150 consensus
= networkstatus_parse_vote_from_string(consensus_body
, NULL
,
3153 log_warn(LD_DIR
, "Couldn't parse %s consensus we generated!",
3155 tor_free(consensus_body
);
3159 /* 'Check' our own signature, to mark it valid. */
3160 networkstatus_check_consensus_signature(consensus
, -1);
3162 pending
[flav
].body
= consensus_body
;
3163 pending
[flav
].consensus
= consensus
;
3165 consensus_body
= NULL
;
3169 log_warn(LD_DIR
, "Couldn't generate any consensus flavors at all.");
3174 signatures
= get_detached_signatures_from_pending_consensuses(
3175 pending
, N_CONSENSUS_FLAVORS
);
3178 log_warn(LD_DIR
, "Couldn't extract signatures.");
3182 dirvote_clear_pending_consensuses();
3183 memcpy(pending_consensuses
, pending
, sizeof(pending
));
3185 tor_free(pending_consensus_signatures
);
3186 pending_consensus_signatures
= signatures
;
3188 if (pending_consensus_signature_list
) {
3190 /* we may have gotten signatures for this consensus before we built
3191 * it ourself. Add them now. */
3192 SMARTLIST_FOREACH(pending_consensus_signature_list
, char *, sig
,
3194 const char *msg
= NULL
;
3195 int r
= dirvote_add_signatures_to_all_pending_consensuses(sig
, &msg
);
3200 "Could not add queued signature to new consensus: %s",
3205 log_notice(LD_DIR
, "Added %d pending signatures while building "
3206 "consensus.", n_sigs
);
3207 smartlist_clear(pending_consensus_signature_list
);
3210 log_notice(LD_DIR
, "Consensus computed; uploading signature(s)");
3212 directory_post_to_dirservers(DIR_PURPOSE_UPLOAD_SIGNATURES
,
3213 ROUTER_PURPOSE_GENERAL
,
3215 pending_consensus_signatures
,
3216 strlen(pending_consensus_signatures
), 0);
3217 log_notice(LD_DIR
, "Signature(s) posted.");
3219 smartlist_free(votes
);
3222 smartlist_free(votes
);
3223 tor_free(consensus_body
);
3224 tor_free(signatures
);
3225 networkstatus_vote_free(consensus
);
3230 /** Helper: we just got the <b>detached_signatures_body</b> sent to us as
3231 * signatures on the currently pending consensus. Add them to <b>pc</b>
3232 * as appropriate. Return the number of signatures added. (?) */
3234 dirvote_add_signatures_to_pending_consensus(
3235 pending_consensus_t
*pc
,
3236 ns_detached_signatures_t
*sigs
,
3237 const char **msg_out
)
3239 const char *flavor_name
;
3242 /* Only call if we have a pending consensus right now. */
3243 tor_assert(pc
->consensus
);
3244 tor_assert(pc
->body
);
3245 tor_assert(pending_consensus_signatures
);
3247 flavor_name
= networkstatus_get_flavor_name(pc
->consensus
->flavor
);
3251 smartlist_t
*sig_list
= strmap_get(sigs
->signatures
, flavor_name
);
3252 log_info(LD_DIR
, "Have %d signatures for adding to %s consensus.",
3253 sig_list
? smartlist_len(sig_list
) : 0, flavor_name
);
3255 r
= networkstatus_add_detached_signatures(pc
->consensus
, sigs
, msg_out
);
3256 log_info(LD_DIR
,"Added %d signatures to consensus.", r
);
3259 char *new_signatures
=
3260 networkstatus_format_signatures(pc
->consensus
, 0);
3261 char *dst
, *dst_end
;
3262 size_t new_consensus_len
;
3263 if (!new_signatures
) {
3264 *msg_out
= "No signatures to add";
3268 strlen(pc
->body
) + strlen(new_signatures
) + 1;
3269 pc
->body
= tor_realloc(pc
->body
, new_consensus_len
);
3270 dst_end
= pc
->body
+ new_consensus_len
;
3271 dst
= strstr(pc
->body
, "directory-signature ");
3273 strlcpy(dst
, new_signatures
, dst_end
-dst
);
3275 /* We remove this block once it has failed to crash for a while. But
3276 * unless it shows up in profiles, we're probably better leaving it in,
3277 * just in case we break detached signature processing at some point. */
3279 networkstatus_t
*v
= networkstatus_parse_vote_from_string(
3283 networkstatus_vote_free(v
);
3285 *msg_out
= "Signatures added";
3286 tor_free(new_signatures
);
3287 } else if (r
== 0) {
3288 *msg_out
= "Signatures ignored";
3296 *msg_out
= "Unrecognized error while adding detached signatures.";
3302 dirvote_add_signatures_to_all_pending_consensuses(
3303 const char *detached_signatures_body
,
3304 const char **msg_out
)
3306 int r
=0, i
, n_added
= 0, errors
= 0;
3307 ns_detached_signatures_t
*sigs
;
3308 tor_assert(detached_signatures_body
);
3309 tor_assert(msg_out
);
3310 tor_assert(pending_consensus_signatures
);
3312 if (!(sigs
= networkstatus_parse_detached_signatures(
3313 detached_signatures_body
, NULL
))) {
3314 *msg_out
= "Couldn't parse detached signatures.";
3318 for (i
= 0; i
< N_CONSENSUS_FLAVORS
; ++i
) {
3320 pending_consensus_t
*pc
= &pending_consensuses
[i
];
3323 res
= dirvote_add_signatures_to_pending_consensus(pc
, sigs
, msg_out
);
3330 if (errors
&& !n_added
) {
3335 if (n_added
&& pending_consensuses
[FLAV_NS
].consensus
) {
3336 char *new_detached
=
3337 get_detached_signatures_from_pending_consensuses(
3338 pending_consensuses
, N_CONSENSUS_FLAVORS
);
3340 tor_free(pending_consensus_signatures
);
3341 pending_consensus_signatures
= new_detached
;
3349 *msg_out
= "Unrecognized error while adding detached signatures.";
3351 ns_detached_signatures_free(sigs
);
3352 /* XXXX NM Check how return is used. We can now have an error *and*
3353 signatures added. */
3357 /** Helper: we just got the <b>detached_signatures_body</b> sent to us as
3358 * signatures on the currently pending consensus. Add them to the pending
3359 * consensus (if we have one); otherwise queue them until we have a
3360 * consensus. Return negative on failure, nonnegative on success. */
3362 dirvote_add_signatures(const char *detached_signatures_body
,
3366 if (pending_consensuses
[FLAV_NS
].consensus
) {
3367 log_notice(LD_DIR
, "Got a signature from %s. "
3368 "Adding it to the pending consensus.", source
);
3369 return dirvote_add_signatures_to_all_pending_consensuses(
3370 detached_signatures_body
, msg
);
3372 log_notice(LD_DIR
, "Got a signature from %s. "
3373 "Queuing it for the next consensus.", source
);
3374 if (!pending_consensus_signature_list
)
3375 pending_consensus_signature_list
= smartlist_create();
3376 smartlist_add(pending_consensus_signature_list
,
3377 tor_strdup(detached_signatures_body
));
3378 *msg
= "Signature queued";
3383 /** Replace the consensus that we're currently serving with the one that we've
3384 * been building. (V3 Authority only) */
3386 dirvote_publish_consensus(void)
3390 /* Now remember all the other consensuses as if we were a directory cache. */
3391 for (i
= 0; i
< N_CONSENSUS_FLAVORS
; ++i
) {
3392 pending_consensus_t
*pending
= &pending_consensuses
[i
];
3394 name
= networkstatus_get_flavor_name(i
);
3396 if (!pending
->consensus
||
3397 networkstatus_check_consensus_signature(pending
->consensus
, 1)<0) {
3398 log_warn(LD_DIR
, "Not enough info to publish pending %s consensus",name
);
3402 if (networkstatus_set_current_consensus(pending
->body
, name
, 0))
3403 log_warn(LD_DIR
, "Error publishing %s consensus", name
);
3405 log_notice(LD_DIR
, "Published %s consensus", name
);
3411 /** Release all static storage held in dirvote.c */
3413 dirvote_free_all(void)
3415 dirvote_clear_votes(1);
3416 /* now empty as a result of dirvote_clear_votes(). */
3417 smartlist_free(pending_vote_list
);
3418 pending_vote_list
= NULL
;
3419 smartlist_free(previous_vote_list
);
3420 previous_vote_list
= NULL
;
3422 dirvote_clear_pending_consensuses();
3423 tor_free(pending_consensus_signatures
);
3424 if (pending_consensus_signature_list
) {
3425 /* now empty as a result of dirvote_clear_votes(). */
3426 smartlist_free(pending_consensus_signature_list
);
3427 pending_consensus_signature_list
= NULL
;
3432 * Access to pending items.
3435 /** Return the body of the consensus that we're currently trying to build. */
3437 dirvote_get_pending_consensus(consensus_flavor_t flav
)
3439 tor_assert(((int)flav
) >= 0 && flav
< N_CONSENSUS_FLAVORS
);
3440 return pending_consensuses
[flav
].body
;
3443 /** Return the signatures that we know for the consensus that we're currently
3444 * trying to build. */
3446 dirvote_get_pending_detached_signatures(void)
3448 return pending_consensus_signatures
;
3451 /** Return a given vote specified by <b>fp</b>. If <b>by_id</b>, return the
3452 * vote for the authority with the v3 authority identity key digest <b>fp</b>;
3453 * if <b>by_id</b> is false, return the vote whose digest is <b>fp</b>. If
3454 * <b>fp</b> is NULL, return our own vote. If <b>include_previous</b> is
3455 * false, do not consider any votes for a consensus that's already been built.
3456 * If <b>include_pending</b> is false, do not consider any votes for the
3457 * consensus that's in progress. May return NULL if we have no vote for the
3458 * authority in question. */
3459 const cached_dir_t
*
3460 dirvote_get_vote(const char *fp
, int flags
)
3462 int by_id
= flags
& DGV_BY_ID
;
3463 const int include_pending
= flags
& DGV_INCLUDE_PENDING
;
3464 const int include_previous
= flags
& DGV_INCLUDE_PREVIOUS
;
3466 if (!pending_vote_list
&& !previous_vote_list
)
3469 authority_cert_t
*c
= get_my_v3_authority_cert();
3471 fp
= c
->cache_info
.identity_digest
;
3477 if (pending_vote_list
&& include_pending
) {
3478 SMARTLIST_FOREACH(pending_vote_list
, pending_vote_t
*, pv
,
3479 if (!memcmp(get_voter(pv
->vote
)->identity_digest
, fp
, DIGEST_LEN
))
3480 return pv
->vote_body
);
3482 if (previous_vote_list
&& include_previous
) {
3483 SMARTLIST_FOREACH(previous_vote_list
, pending_vote_t
*, pv
,
3484 if (!memcmp(get_voter(pv
->vote
)->identity_digest
, fp
, DIGEST_LEN
))
3485 return pv
->vote_body
);
3488 if (pending_vote_list
&& include_pending
) {
3489 SMARTLIST_FOREACH(pending_vote_list
, pending_vote_t
*, pv
,
3490 if (!memcmp(pv
->vote
->digests
.d
[DIGEST_SHA1
], fp
, DIGEST_LEN
))
3491 return pv
->vote_body
);
3493 if (previous_vote_list
&& include_previous
) {
3494 SMARTLIST_FOREACH(previous_vote_list
, pending_vote_t
*, pv
,
3495 if (!memcmp(pv
->vote
->digests
.d
[DIGEST_SHA1
], fp
, DIGEST_LEN
))
3496 return pv
->vote_body
);
3502 /** Construct and return a new microdescriptor from a routerinfo <b>ri</b>.
3504 * XXX Right now, there is only one way to generate microdescriptors from
3505 * router descriptors. This may change in future consensus methods. If so,
3506 * we'll need an internal way to remember which method we used, and ask for a
3507 * particular method.
3510 dirvote_create_microdescriptor(const routerinfo_t
*ri
)
3512 microdesc_t
*result
= NULL
;
3513 char *key
= NULL
, *summary
= NULL
, *family
= NULL
;
3516 char *out
= buf
, *end
= buf
+sizeof(buf
);
3518 if (crypto_pk_write_public_key_to_string(ri
->onion_pkey
, &key
, &keylen
)<0)
3520 summary
= policy_summarize(ri
->exit_policy
);
3521 if (ri
->declared_family
)
3522 family
= smartlist_join_strings(ri
->declared_family
, " ", 0, NULL
);
3524 if (tor_snprintf(out
, end
-out
, "onion-key\n%s", key
)<0)
3528 if (tor_snprintf(out
, end
-out
, "family %s\n", family
)<0)
3532 if (summary
&& strcmp(summary
, "reject 1-65535")) {
3533 if (tor_snprintf(out
, end
-out
, "p %s\n", summary
)<0)
3537 *out
= '\0'; /* Make sure it's nul-terminated. This should be a no-op */
3540 smartlist_t
*lst
= microdescs_parse_from_string(buf
, out
, 0, 1);
3541 if (smartlist_len(lst
) != 1) {
3542 log_warn(LD_DIR
, "We generated a microdescriptor we couldn't parse.");
3543 SMARTLIST_FOREACH(lst
, microdesc_t
*, md
, microdesc_free(md
));
3544 smartlist_free(lst
);
3547 result
= smartlist_get(lst
, 0);
3548 smartlist_free(lst
);
3558 /** Cached space-separated string to hold */
3559 static char *microdesc_consensus_methods
= NULL
;
3561 /** Format the appropriate vote line to describe the microdescriptor <b>md</b>
3562 * in a consensus vote document. Write it into the <b>out_len</b>-byte buffer
3563 * in <b>out</b>. Return -1 on failure and the number of characters written
3566 dirvote_format_microdesc_vote_line(char *out
, size_t out_len
,
3567 const microdesc_t
*md
)
3569 char d64
[BASE64_DIGEST256_LEN
+1];
3570 if (!microdesc_consensus_methods
) {
3571 microdesc_consensus_methods
=
3572 make_consensus_method_list(MIN_METHOD_FOR_MICRODESC
,
3573 MAX_SUPPORTED_CONSENSUS_METHOD
,
3575 tor_assert(microdesc_consensus_methods
);
3577 if (digest256_to_base64(d64
, md
->digest
)<0)
3580 if (tor_snprintf(out
, out_len
, "m %s sha256=%s\n",
3581 microdesc_consensus_methods
, d64
)<0)
3587 /** If <b>vrs</b> has a hash made for the consensus method <b>method</b> with
3588 * the digest algorithm <b>alg</b>, decode it and copy it into
3589 * <b>digest256_out</b> and return 0. Otherwise return -1. */
3591 vote_routerstatus_find_microdesc_hash(char *digest256_out
,
3592 const vote_routerstatus_t
*vrs
,
3594 digest_algorithm_t alg
)
3596 /* XXXX only returns the sha256 method. */
3597 const vote_microdesc_hash_t
*h
;
3602 tor_snprintf(mstr
, sizeof(mstr
), "%d", method
);
3603 mlen
= strlen(mstr
);
3604 tor_snprintf(dstr
, sizeof(dstr
), " %s=",
3605 crypto_digest_algorithm_get_name(alg
));
3607 for (h
= vrs
->microdesc
; h
; h
= h
->next
) {
3608 const char *cp
= h
->microdesc_hash_line
;
3610 /* cp looks like \d+(,\d+)* (digesttype=val )+ . Let's hunt for mstr in
3611 * the first part. */
3613 num_len
= strspn(cp
, "1234567890");
3614 if (num_len
== mlen
&& !memcmp(mstr
, cp
, mlen
)) {
3615 /* This is the line. */
3616 char buf
[BASE64_DIGEST256_LEN
+1];
3617 /* XXXX ignores extraneous stuff if the digest is too long. This
3618 * seems harmless enough, right? */
3619 cp
= strstr(cp
, dstr
);
3623 strlcpy(buf
, cp
, sizeof(buf
));
3624 return digest256_from_base64(digest256_out
, buf
);
3626 if (num_len
== 0 || cp
[num_len
] != ',')