dirvote.c File Reference

Functions to compute directory consensus, and schedule voting. More...

#include "or.h"
#include "config.h"
#include "dircollate.h"
#include "directory.h"
#include "dirserv.h"
#include "microdesc.h"
#include "networkstatus.h"
#include "nodelist.h"
#include "parsecommon.h"
#include "policies.h"
#include "protover.h"
#include "rephist.h"
#include "router.h"
#include "routerkeys.h"
#include "routerlist.h"
#include "routerparse.h"
#include "entrynodes.h"
#include "torcert.h"
#include "voting_schedule.h"
#include "dirauth/dirvote.h"
#include "dirauth/mode.h"
#include "dirauth/shared_random_state.h"

Include dependency graph for dirvote.c:

Data Structures
struct	pending_consensus_t
struct	dir_src_ent_t
struct	pending_vote_t
struct	consensus_method_range_t
struct	microdesc_vote_line_t

Macros
#define	DIRVOTE_PRIVATE
#define	get_most_frequent_member(lst)   smartlist_get_most_frequent_string(lst)
#define	CMP_FIELD(utype, itype, field)
#define	MIN_VOTES_FOR_PARAM   3
#define	RANGE_CHECK(a, b, c, d, e, f, g, mx)
#define	CHECK_EQ(a, b, margin)   ((a)-(b) >= 0 ? (a)-(b) <= (margin) : (b)-(a) <= (margin))
#define	IF_TIME_FOR_NEXT_ACTION(when_field, done_field)
#define	ENDIF

Typedefs
typedef struct pending_consensus_t	pending_consensus_t
typedef struct dir_src_ent_t	dir_src_ent_t
typedef struct pending_vote_t	pending_vote_t
typedef struct microdesc_vote_line_t	microdesc_vote_line_t

Enumerations
enum	bw_weights_error_t {   BW_WEIGHTS_NO_ERROR = 0, BW_WEIGHTS_RANGE_ERROR = 1, BW_WEIGHTS_SUMG_ERROR = 2, BW_WEIGHTS_SUME_ERROR = 3,   BW_WEIGHTS_SUMD_ERROR = 4, BW_WEIGHTS_BALANCE_MID_ERROR = 5, BW_WEIGHTS_BALANCE_EG_ERROR = 6 }

Functions
STATIC authority_cert_t *	authority_cert_dup (authority_cert_t *cert)
STATIC char *	format_networkstatus_vote (crypto_pk_t *private_signing_key, networkstatus_t *v3_ns)
STATIC char *	make_consensus_method_list (int low, int high, const char *separator)
STATIC int32_t	dirvote_get_intermediate_param_value (const smartlist_t *param_list, const char *keyword, int32_t default_val)
STATIC smartlist_t *	dirvote_compute_params (smartlist_t *votes, int method, int total_authorities)
int	networkstatus_compute_bw_weights_v10 (smartlist_t *chunks, int64_t G, int64_t M, int64_t E, int64_t D, int64_t T, int64_t weight_scale)
STATIC char *	networkstatus_compute_consensus (smartlist_t *votes, int total_authorities, crypto_pk_t *identity_key, crypto_pk_t *signing_key, const char *legacy_id_key_digest, crypto_pk_t *legacy_signing_key, consensus_flavor_t flavor)
STATIC char *	compute_consensus_package_lines (smartlist_t *votes)
STATIC int	networkstatus_add_detached_signatures (networkstatus_t *target, ns_detached_signatures_t *sigs, const char *source, int severity, const char **msg_out)
STATIC char *	networkstatus_get_detached_signatures (smartlist_t *consensuses)
time_t	dirvote_act (const or_options_t *options, time_t now)
pending_vote_t *	dirvote_add_vote (const char *vote_body, const char **msg_out, int *status_out)
int	dirvote_add_signatures (const char *detached_signatures_body, const char *source, const char **msg)
void	dirvote_free_all (void)
	MOCK_IMPL (const char *, dirvote_get_pending_consensus,(consensus_flavor_t flav))
	MOCK_IMPL (const char *, dirvote_get_pending_detached_signatures,(void))
const cached_dir_t *	dirvote_get_vote (const char *fp, int flags)
STATIC microdesc_t *	dirvote_create_microdescriptor (const routerinfo_t *ri, int consensus_method)
vote_microdesc_hash_t *	dirvote_format_all_microdesc_vote_lines (const routerinfo_t *ri, time_t now, smartlist_t *microdescriptors_out)
void	dirvote_parse_sr_commits (networkstatus_t *ns, const smartlist_t *tokens)
void	dirvote_clear_commits (networkstatus_t *ns)
void	dirvote_dirreq_get_status_vote (const char *url, smartlist_t *items, smartlist_t *dir_items)
networkstatus_t *	dirserv_generate_networkstatus_vote_obj (crypto_pk_t *private_key, authority_cert_t *cert)

Detailed Description

Functions to compute directory consensus, and schedule voting.

This module is the center of the consensus-voting based directory authority system. With this system, a set of authorities first publish vote based on their opinions of the network, and then compute a consensus from those votes. Each authority signs the consensus, and clients trust the consensus if enough known authorities have signed it.

The code in this module is only invoked on directory authorities. It's responsible for:

• Generating this authority's vote networkstatus, based on the authority's view of the network as represented in dirserv.c
• Formatting the vote networkstatus objects.
• Generating the microdescriptors that correspond to our own vote.
• Sending votes to all the other authorities.
• Trying to fetch missing votes from other authorities.
• Computing the consensus from a set of votes, as well as a "detached signature" object for other authorities to fetch.
• Collecting other authorities' signatures on the same consensus, until there are enough.
• Publishing the consensus to the reset of the directory system.
• Scheduling all of the above operations.

The main entry points are in dirvote_act(), which handles scheduled actions; and dirvote_add_vote() and dirvote_add_signatures(), which handle uploaded and downloaded votes and signatures.

(See dir-spec.txt from torspec.git for a complete specification of the directory protocol and voting algorithms.)

Macro Definition Documentation

CMP_FIELD

#define CMP_FIELD	(		utype,
			itype,
			field
	)

Value:

do {                             \
    utype aval = (utype) (itype) a->status.field;                       \
    utype bval = (utype) (itype) b->status.field;                       \
    utype u = bval - aval;                                              \
    itype r2 = (itype) u;                                               \
    if (r2 < 0) {                                                       \
      return -1;                                                        \
    } else if (r2 > 0) {                                                \
      return 1;                                                         \
    }                                                                   \
  } while (0)

ENDIF

#define ENDIF

Value:

}           \
  }

get_most_frequent_member

#define get_most_frequent_member

(

lst

)

smartlist_get_most_frequent_string(lst)

Given a sorted list of strings lst, return the member that appears most. Break ties in favor of later-occurring members.

IF_TIME_FOR_NEXT_ACTION

#define IF_TIME_FOR_NEXT_ACTION	(		when_field,
			done_field
	)

Value:

if (! voting_schedule.done_field) {                   \
    if (voting_schedule.when_field > now) {             \
      return voting_schedule.when_field;                \
    } else {

MIN_VOTES_FOR_PARAM

#define MIN_VOTES_FOR_PARAM   3

Minimum number of directory authorities voting for a parameter to include it in the consensus, if consensus method 12 or later is to be used. See proposal 178 for details.

RANGE_CHECK

#define RANGE_CHECK	(		a,
			b,
			c,
			d,
			e,
			f,
			g,
			mx
	)

Value:

((a) >= 0 && (a) <= (mx) && (b) >= 0 && (b) <= (mx) && \
        (c) >= 0 && (c) <= (mx) && (d) >= 0 && (d) <= (mx) && \
        (e) >= 0 && (e) <= (mx) && (f) >= 0 && (f) <= (mx) && \
        (g) >= 0 && (g) <= (mx))

Typedef Documentation

dir_src_ent_t

typedef struct dir_src_ent_t dir_src_ent_t

Temporary structure used in constructing a list of dir-source entries for a consensus. One of these is generated for every vote, and one more for every legacy key in each vote.

microdesc_vote_line_t

typedef struct microdesc_vote_line_t microdesc_vote_line_t

Helper type used when generating the microdescriptor lines in a directory vote.

pending_consensus_t

typedef struct pending_consensus_t pending_consensus_t

A consensus that we have built and are appending signatures to. Once it's time to publish it, it will become an active consensus if it accumulates enough signatures.

pending_vote_t

typedef struct pending_vote_t pending_vote_t

A vote networkstatus_t and its unparsed body: held around so we can use it to generate a consensus (at voting_ends) and so we can serve it to other authorities that might want it.

Function Documentation

authority_cert_dup()

STATIC authority_cert_t* authority_cert_dup

(

authority_cert_t *

cert

)

Allocate and return a new authority_cert_t with the same contents as cert.

compute_consensus_package_lines()

STATIC char* compute_consensus_package_lines

(

smartlist_t *

votes

)

Given a list of networkstatus_t for each vote, return a newly allocated string containing the "package" lines for the vote.

Here is the call graph for this function:

dirserv_generate_networkstatus_vote_obj()

networkstatus_t* dirserv_generate_networkstatus_vote_obj	(	crypto_pk_t *	private_key,
		authority_cert_t *	cert
	)

Return a new networkstatus_t* containing our current opinion. (For v3 authorities)

Here is the call graph for this function:

dirvote_act()

time_t dirvote_act	(	const or_options_t *	options,
		time_t	now
	)

Entry point: Take whatever voting actions are pending as of now.

Return the time at which the next action should be taken.

dirvote_add_signatures()

int dirvote_add_signatures	(	const char *	detached_signatures_body,
		const char *	source,
		const char **	msg
	)

Helper: we just got the detached_signatures_body sent to us as signatures on the currently pending consensus. Add them to the pending consensus (if we have one); otherwise queue them until we have a consensus. Return negative on failure, nonnegative on success.

dirvote_add_vote()

pending_vote_t* dirvote_add_vote	(	const char *	vote_body,
		const char **	msg_out,
		int *	status_out
	)

Called when we have received a networkstatus vote in vote_body. Parse and validate it, and on success store it as a pending vote (which we then return). Return NULL on failure. Sets *msg_out and *status_out to an HTTP response and status code. (V3 authority only)

Here is the call graph for this function:

dirvote_compute_params()

STATIC smartlist_t* dirvote_compute_params	(	smartlist_t *	votes,
		int	method,
		int	total_authorities
	)

Helper: given a list of valid networkstatus_t, return a new smartlist containing the contents of the consensus network parameter set.

dirvote_create_microdescriptor()

STATIC microdesc_t* dirvote_create_microdescriptor	(	const routerinfo_t *	ri,
		int	consensus_method
	)

Construct and return a new microdescriptor from a routerinfo ri according to consensus_method.

Here is the call graph for this function:

dirvote_format_all_microdesc_vote_lines()

vote_microdesc_hash_t* dirvote_format_all_microdesc_vote_lines	(	const routerinfo_t *	ri,
		time_t	now,
		smartlist_t *	microdescriptors_out
	)

Generate and return a linked list of all the lines that should appear to describe a router's microdescriptor versions in a directory vote. Add the generated microdescriptors to microdescriptors_out.

dirvote_free_all()

void dirvote_free_all

(

void

)

Release all static storage held in dirvote.c

dirvote_get_intermediate_param_value()

STATIC int32_t dirvote_get_intermediate_param_value	(	const smartlist_t *	param_list,
		const char *	keyword,
		int32_t	default_val
	)

Given a list of K=V values, return the int32_t value corresponding to KEYWORD=, or default_val if no such value exists, or if the value is corrupt.

Here is the call graph for this function:

dirvote_get_vote()

const cached_dir_t* dirvote_get_vote	(	const char *	fp,
		int	flags
	)

Return a given vote specified by fp. If by_id, return the vote for the authority with the v3 authority identity key digest fp; if by_id is false, return the vote whose digest is fp. If fp is NULL, return our own vote. If include_previous is false, do not consider any votes for a consensus that's already been built. If include_pending is false, do not consider any votes for the consensus that's in progress. May return NULL if we have no vote for the authority in question.

format_networkstatus_vote()

STATIC char* format_networkstatus_vote	(	crypto_pk_t *	private_signing_key,
		networkstatus_t *	v3_ns
	)

Return a new string containing the string representation of the vote in v3_ns, signed with our v3 signing key private_signing_key. For v3 authorities.

make_consensus_method_list()

STATIC char* make_consensus_method_list	(	int	low,
		int	high,
		const char *	separator
	)

Return a newly allocated string holding the numbers between low and high (inclusive) that are supported consensus methods.

MOCK_IMPL() [1/2]

MOCK_IMPL	(	const char *	,
		dirvote_get_pending_consensus	,
		(consensus_flavor_t flav)
	)

Return the body of the consensus that we're currently trying to build.

MOCK_IMPL() [2/2]

MOCK_IMPL	(	const char *	,
		dirvote_get_pending_detached_signatures	,
		(void)
	)

Return the signatures that we know for the consensus that we're currently trying to build.

networkstatus_add_detached_signatures()

STATIC int networkstatus_add_detached_signatures	(	networkstatus_t *	target,
		ns_detached_signatures_t *	sigs,
		const char *	source,
		int	severity,
		const char **	msg_out
	)

Given a consensus vote target and a set of detached signatures in sigs that correspond to the same consensus, check whether there are any new signatures in src_voter_list that should be added to target. (A signature should be added if we have no signature for that voter in target yet, or if we have no verifiable signature and the new signature is verifiable.) Return the number of signatures added or changed, or -1 if the document signed by sigs isn't the same document as target.

Make sure all the digests we know match, and at least one matches.

networkstatus_compute_bw_weights_v10()

int networkstatus_compute_bw_weights_v10	(	smartlist_t *	chunks,
		int64_t	G,
		int64_t	M,
		int64_t	E,
		int64_t	D,
		int64_t	T,
		int64_t	weight_scale
	)

This function computes the bandwidth weights for consensus method 10.

It returns true if weights could be computed, false otherwise.

networkstatus_compute_consensus()

STATIC char* networkstatus_compute_consensus	(	smartlist_t *	votes,
		int	total_authorities,
		crypto_pk_t *	identity_key,
		crypto_pk_t *	signing_key,
		const char *	legacy_id_key_digest,
		crypto_pk_t *	legacy_signing_key,
		consensus_flavor_t	flavor
	)

Given a list of vote networkstatus_t in votes, our public authority identity_key, our private authority signing_key, and the number of total_authorities that we believe exist in our voting quorum, generate the text of a new v3 consensus or microdescriptor consensus (depending on flavor), and return the value in a newly allocated string.

Note: this function DOES NOT check whether the votes are from recognized authorities. (dirvote_add_vote does that.)

WATCH OUT: You need to think before you change the behavior of this function, or of the functions it calls! If some authorities compute the consensus with a different algorithm than others, they will not reach the same result, and they will not all sign the same thing! If you really need to change the algorithm here, you should allocate a new "consensus_method" for the new behavior, and make the new behavior conditional on a new-enough consensus_method.

networkstatus_get_detached_signatures()

STATIC char* networkstatus_get_detached_signatures

(

smartlist_t *

consensuses

)

Return a newly allocated string holding the detached-signatures document corresponding to the signatures on consensuses, which must contain exactly one FLAV_NS consensus, and no more than one consensus for each other flavor.