Functions and data structure needed to accomplish the shared random protocol as defined in proposal #250. More...

#include "core/or/or.h"
#include "feature/dirauth/shared_random.h"
#include "app/config/config.h"
#include "lib/confmgt/confmgt.h"
#include "lib/crypt_ops/crypto_rand.h"
#include "lib/crypt_ops/crypto_util.h"
#include "feature/nodelist/networkstatus.h"
#include "feature/relay/router.h"
#include "feature/relay/routerkeys.h"
#include "feature/nodelist/dirlist.h"
#include "feature/hs_common/shared_random_client.h"
#include "feature/dirauth/shared_random_state.h"
#include "feature/dirauth/voting_schedule.h"
#include "feature/dirauth/dirvote.h"
#include "feature/dirauth/authmode.h"
#include "feature/dirauth/dirauth_sys.h"
#include "feature/dirauth/dirauth_options_st.h"
#include "feature/nodelist/authority_cert_st.h"
#include "feature/nodelist/networkstatus_st.h"

Functions
sr_srv_t *	sr_srv_dup (const sr_srv_t *orig)

static sr_commit_t *	commit_new (const char *rsa_identity)

static void	commit_log (const sr_commit_t *commit)

STATIC int	verify_commit_and_reveal (const sr_commit_t *commit)

STATIC int	commit_has_reveal_value (const sr_commit_t *commit)

STATIC int	commit_decode (const char encoded, sr_commit_t commit)

STATIC int	reveal_decode (const char encoded, sr_commit_t commit)

STATIC int	reveal_encode (const sr_commit_t commit, char dst, size_t len)

STATIC int	commit_encode (const sr_commit_t commit, char dst, size_t len)

static void	sr_cleanup (void)

static char *	get_srv_element_from_commit (const sr_commit_t *commit)

static sr_srv_t *	generate_srv (const char hashed_reveals, uint64_t reveal_num, const sr_srv_t previous_srv)

static int	compare_reveal_ (const void _a, const void _b)

static char *	get_vote_line_from_commit (const sr_commit_t *commit, sr_phase_t phase)

static char *	srv_to_ns_string (const sr_srv_t srv, const char key)

static char *	get_ns_str_from_sr_values (const sr_srv_t prev_srv, const sr_srv_t cur_srv)

STATIC int	commitments_are_the_same (const sr_commit_t commit_one, const sr_commit_t commit_two)

STATIC int	commit_is_authoritative (const sr_commit_t commit, const char voter_key)

STATIC int	should_keep_commit (const sr_commit_t commit, const char voter_key, sr_phase_t phase)

STATIC void	save_commit_during_reveal_phase (const sr_commit_t *commit)

STATIC void	save_commit_to_state (sr_commit_t *commit)

static int	should_keep_srv (int n_agreements)

static int	compare_srvs_ (const void _a, const void _b)

static sr_srv_t *	smartlist_get_most_frequent_srv (const smartlist_t sl, int count_out)

static int	compare_srv_ (const void _a, const void _b)

STATIC sr_srv_t *	get_majority_srv_from_votes (const smartlist_t *votes, int current)

void	sr_commit_free_ (sr_commit_t *commit)

sr_commit_t *	sr_generate_our_commit (time_t timestamp, const authority_cert_t *my_rsa_cert)

void	sr_compute_srv (void)

sr_commit_t *	sr_parse_commit (const smartlist_t *args)

void	sr_handle_received_commits (smartlist_t commits, crypto_pk_t voter_key)

char *	sr_get_string_for_vote (void)

char *	sr_get_string_for_consensus (const smartlist_t *votes, int32_t num_srv_agreements)

void	sr_act_post_consensus (const networkstatus_t *consensus)

int	sr_init (int save_to_disk)

void	sr_save_and_cleanup (void)

Variables
static const char	previous_srv_str [] = "shared-rand-previous-value"

static const char	current_srv_str [] = "shared-rand-current-value"

static const char	commit_ns_str [] = "shared-rand-commit"

static const char	sr_flag_ns_str [] = "shared-rand-participate"

static int32_t	num_srv_agreements_from_vote

Detailed Description

Functions and data structure needed to accomplish the shared random protocol as defined in proposal #250.

This file implements the dirauth-only commit-and-reveal protocol specified by proposal #250. The protocol has two phases (sr_phase_t): the commitment phase and the reveal phase (see get_sr_protocol_phase()).

During the protocol, directory authorities keep state in memory (using sr_state_t) and in disk (using sr_disk_state_t). The synchronization between these two data structures happens in disk_state_update() and disk_state_parse().

Here is a rough protocol outline:

 1) In the beginning of the commitment phase, dirauths generate a
    commitment/reveal value for the current protocol run (see
    new_protocol_run() and sr_generate_our_commit()).

 2) During voting, dirauths publish their commits in their votes
    depending on the current phase.  Dirauths also include the two
    latest shared random values (SRV) in their votes.
    (see sr_get_string_for_vote())

 3) Upon receiving a commit from a vote, authorities parse it, verify
    it, and attempt to save any new commitment or reveal information in
    their state file (see extract_shared_random_commits() and
    sr_handle_received_commits()).  They also parse SRVs from votes to
    decide which SRV should be included in the final consensus (see
    extract_shared_random_srvs()).

 3) After voting is done, we count the SRVs we extracted from the votes,
    to find the one voted by the majority of dirauths which should be
    included in the final consensus (see get_majority_srv_from_votes()).
    If an appropriate SRV is found, it is embedded in the consensus (see
    sr_get_string_for_consensus()).

 4) At the end of the reveal phase, dirauths compute a fresh SRV for the
    day using the active commits (see sr_compute_srv()).  This new SRV
    is embedded in the votes as described above.

Some more notes:

To support rebooting authorities and to avoid double voting, each dirauth saves the current state of the protocol on disk so that it can resume normally in case of reboot. The disk state (sr_disk_state_t) is managed by shared_random_state.c:state_query() and we go to extra lengths to ensure that the state is flushed on disk every time we receive any useful information like commits or SRVs.
When we receive a commit from a vote, we examine it to see if it's useful to us and whether it's appropriate to receive it according to the current phase of the protocol (see should_keep_commit()). If the commit is useful to us, we save it in our disk state using save_commit_to_state(). When we receive the reveal information corresponding to a commitment, we verify that they indeed match using verify_commit_and_reveal().
We treat consensuses as the ground truth, so every time we generate a new consensus we update our SR state accordingly even if our local view was different (see sr_act_post_consensus()).
After a consensus has been composed, the SR protocol state gets prepared for the next voting session using sr_state_update(). That function takes care of housekeeping and also rotates the SRVs and commits in case a new protocol run is coming up. We also call sr_state_update() on bootup (in sr_state_init()), to prepare the state for the very first voting session.

Terminology:

"Commitment" is the commitment value of the commit-and-reveal protocol.
"Reveal" is the reveal value of the commit-and-reveal protocol.
"Commit" is a struct (sr_commit_t) that contains a commitment value and optionally also a corresponding reveal value.
"SRV" is the Shared Random Value that gets generated as the result of the commit-and-reveal protocol.

Definition in file shared_random.c.

Function Documentation

◆ commit_decode()

STATIC int commit_decode	(	const char *	encoded,
		sr_commit_t *	commit
	)

Parse the encoded commit. The format is: base64-encode( TIMESTAMP || H(REVEAL) )

If successfully decoded and parsed, commit is updated and 0 is returned. On error, return -1.

Definition at line 239 of file shared_random.c.

◆ commit_encode()

STATIC int commit_encode	(	const sr_commit_t *	commit,
		char *	dst,
		size_t	len
	)

Encode the given commit object to dst which is a buffer large enough to put the base64-encoded commit. The format is as follow: COMMIT = base64-encode( TIMESTAMP || H(H(RN)) ) Return base64 encoded length on success else a negative value.

Definition at line 373 of file shared_random.c.

◆ commit_has_reveal_value()

STATIC int commit_has_reveal_value ( const sr_commit_t * commit )

Return true iff the commit contains an encoded reveal value.

Definition at line 227 of file shared_random.c.

Referenced by get_srv_element_from_commit().

◆ commit_is_authoritative()

STATIC int commit_is_authoritative	(	const sr_commit_t *	commit,
		const char *	voter_key
	)

We just received a commit from the vote of authority with identity_digest. Return 1 if this commit is authorititative that is, it belongs to the authority that voted it. Else return 0 if not.

Definition at line 581 of file shared_random.c.

◆ commit_log()

static void commit_log ( const sr_commit_t * commit )

static

Issue a log message describing commit.

Definition at line 160 of file shared_random.c.

◆ commit_new()

static sr_commit_t* commit_new ( const char * rsa_identity )

static

Allocate a new commit object and initializing it with rsa_identity that MUST be provided. The digest algorithm is set to the default one that is supported. The rest is uninitialized. This never returns NULL.

Definition at line 144 of file shared_random.c.

Referenced by sr_generate_our_commit().

◆ commitments_are_the_same()

STATIC int commitments_are_the_same	(	const sr_commit_t *	commit_one,
		const sr_commit_t *	commit_two
	)

Return 1 iff the two commits have the same commitment values. This function does not care about reveal values.

Definition at line 565 of file shared_random.c.

Referenced by save_commit_during_reveal_phase().

◆ compare_reveal_()

static int compare_reveal_	(	const void **	_a,
		const void **	_b
	)

static

Compare reveal values and return the result. This should exclusively be used by smartlist_sort().

Definition at line 464 of file shared_random.c.

◆ compare_srv_()

static int compare_srv_	(	const void **	_a,
		const void **	_b
	)

static

Compare two SRVs. Used in smartlist sorting.

Definition at line 804 of file shared_random.c.

◆ compare_srvs_()

static int compare_srvs_	(	const void **	_a,
		const void **	_b
	)

static

Helper: compare two DIGEST256_LEN digests.

Definition at line 788 of file shared_random.c.

Referenced by smartlist_get_most_frequent_srv().

◆ generate_srv()

static sr_srv_t* generate_srv	(	const char *	hashed_reveals,
		uint64_t	reveal_num,
		const sr_srv_t *	previous_srv
	)

static

Return a srv object that is built with the construction: SRV = SHA3-256("shared-random" | INT_8(reveal_num) | INT_4(version) | HASHED_REVEALS | previous_SRV) This function cannot fail.

Definition at line 424 of file shared_random.c.

◆ get_majority_srv_from_votes()

STATIC sr_srv_t* get_majority_srv_from_votes	(	const smartlist_t *	votes,
		int	current
	)

Using a list of votes, return the SRV object from them that has been voted by the majority of dirauths. If current is set, we look for the current SRV value else the previous one. The returned pointer is an object located inside a vote. NULL is returned if no appropriate value could be found.

Definition at line 817 of file shared_random.c.

◆ get_ns_str_from_sr_values()

static char* get_ns_str_from_sr_values	(	const sr_srv_t *	prev_srv,
		const sr_srv_t *	cur_srv
	)

static

Given the previous SRV and the current SRV, return a heap allocated string with their data that could be put in a vote or a consensus. Caller must free the returned string. Return NULL if no SRVs were provided.

Definition at line 533 of file shared_random.c.

◆ get_srv_element_from_commit()

static char* get_srv_element_from_commit ( const sr_commit_t * commit )

static

Using commit, return a newly allocated string containing the commit information that should be used during SRV calculation. It's the caller responsibility to free the memory. Return NULL if this is not a commit to be used for SRV calculation.

Definition at line 405 of file shared_random.c.

◆ get_vote_line_from_commit()

static char* get_vote_line_from_commit	(	const sr_commit_t *	commit,
		sr_phase_t	phase
	)

static

Given commit give the line that we should place in our votes. It's the responsibility of the caller to free the string.

Definition at line 474 of file shared_random.c.

◆ reveal_decode()

STATIC int reveal_decode	(	const char *	encoded,
		sr_commit_t *	commit
	)

Parse the b64 blob at encoded containing reveal information and store the information in-place in commit. Return 0 on success else a negative value.

Definition at line 292 of file shared_random.c.

◆ reveal_encode()

STATIC int reveal_encode	(	const sr_commit_t *	commit,
		char *	dst,
		size_t	len
	)

Encode a reveal element using a given commit object to dst which is a buffer large enough to put the base64-encoded reveal construction. The format is as follow: REVEAL = base64-encode( TIMESTAMP || H(RN) ) Return base64 encoded length on success else a negative value.

Definition at line 345 of file shared_random.c.

Referenced by sr_generate_our_commit().

◆ save_commit_during_reveal_phase()

STATIC void save_commit_during_reveal_phase ( const sr_commit_t * commit )

We are in reveal phase and we found a valid and verified commit in a vote that contains reveal values that we could use. Update the commit we have in our state. Never call this with an unverified commit.

Definition at line 714 of file shared_random.c.

Referenced by save_commit_to_state().

◆ save_commit_to_state()

STATIC void save_commit_to_state ( sr_commit_t * commit )

Save commit to our persistent state. Depending on the current phase, different actions are taken. Steals reference of commit. The commit object MUST be valid and verified before adding it to the state.

Definition at line 736 of file shared_random.c.

◆ should_keep_commit()

STATIC int should_keep_commit	(	const sr_commit_t *	commit,
		const char *	voter_key,
		sr_phase_t	phase
	)

Decide if the newly received commit should be kept depending on the current phase and state of the protocol. The voter_key is the RSA identity key fingerprint of the authority's vote from which the commit comes from. The phase is the phase we should be validating the commit for. Return 1 if the commit should be added to our state or 0 if not.

Definition at line 598 of file shared_random.c.

Referenced by sr_handle_received_commits().

◆ should_keep_srv()

static int should_keep_srv ( int n_agreements )

static

Return 1 if we should we keep an SRV voted by n_agreements auths. Return 0 if we should ignore it.

Definition at line 759 of file shared_random.c.

◆ smartlist_get_most_frequent_srv()

static sr_srv_t* smartlist_get_most_frequent_srv	(	const smartlist_t *	sl,
		int *	count_out
	)

static

Return the most frequent member of the sorted list of DIGEST256_LEN digests in sl with the count of that most frequent element.

Definition at line 797 of file shared_random.c.

◆ sr_act_post_consensus()

void sr_act_post_consensus ( const networkstatus_t * consensus )

We just computed a new consensus. Update our state with the SRVs from the consensus (might be NULL as well). Register the SRVs in our SR state and prepare for the upcoming protocol round.

Definition at line 1232 of file shared_random.c.

◆ sr_cleanup()

static void sr_cleanup ( void )

static

Cleanup both our global state and disk state.

Definition at line 395 of file shared_random.c.

Referenced by sr_save_and_cleanup().

◆ sr_commit_free_()

void sr_commit_free_ ( sr_commit_t * commit )

Free a commit object.

Definition at line 875 of file shared_random.c.

Referenced by commit_free_().

◆ sr_compute_srv()

void sr_compute_srv ( void )

Compute the shared random value based on the active commits in our state.

Definition at line 945 of file shared_random.c.

Referenced by new_protocol_run().

◆ sr_generate_our_commit()

sr_commit_t* sr_generate_our_commit	(	time_t	timestamp,
		const authority_cert_t *	my_rsa_cert
	)

Generate the commitment/reveal value for the protocol run starting at timestamp. my_rsa_cert is our authority RSA certificate.

Definition at line 888 of file shared_random.c.

◆ sr_get_string_for_consensus()

char* sr_get_string_for_consensus	(	const smartlist_t *	votes,
		int32_t	num_srv_agreements
	)

Return a heap-allocated string that should be put in the consensus and contains the shared randomness values. It's the responsibility of the caller to free the string. NULL is returned if no SRV(s) available.

This is called when a consensus (any flavor) is bring created thus it should NEVER change the state nor the state should be changed in between consensus creation.

num_srv_agreements is taken from the votes thus the voted value that should be used.

Definition at line 1196 of file shared_random.c.

◆ sr_get_string_for_vote()

char* sr_get_string_for_vote ( void )

Return a heap-allocated string containing commits that should be put in the votes. It's the responsibility of the caller to free the string. This always return a valid string, either empty or with line(s).

Definition at line 1130 of file shared_random.c.

◆ sr_handle_received_commits()

void sr_handle_received_commits	(	smartlist_t *	commits,
		crypto_pk_t *	voter_key
	)

Called when we are done parsing a vote by voter_key that might contain some useful commits. Find if any of them should be kept and update our state accordingly. Once done, the list of commitments will be empty.

Definition at line 1093 of file shared_random.c.

◆ sr_init()

int sr_init ( int save_to_disk )

Initialize shared random subsystem. This MUST be called early in the boot process of tor. Return 0 on success else -1 on error.

Definition at line 1270 of file shared_random.c.

◆ sr_parse_commit()

sr_commit_t* sr_parse_commit ( const smartlist_t * args )

Parse a commit from a vote or from our disk state and return a newly allocated commit object. NULL is returned on error.

The commit's data is in args and the order matters very much: version, algname, RSA fingerprint, commit value[, reveal value]

Definition at line 1023 of file shared_random.c.

◆ sr_save_and_cleanup()

void sr_save_and_cleanup ( void )

Save our state to disk and cleanup everything.

Definition at line 1277 of file shared_random.c.

Referenced by tor_cleanup().

◆ sr_srv_dup()

sr_srv_t* sr_srv_dup ( const sr_srv_t * orig )

Return a heap allocated copy of the SRV orig.

Definition at line 126 of file shared_random.c.

Referenced by state_rotate_srv().

◆ srv_to_ns_string()

static char* srv_to_ns_string	(	const sr_srv_t *	srv,
		const char *	key
	)

static

Return a heap allocated string that contains the given srv string representation formatted for a networkstatus document using the key as the start of the line. This doesn't return NULL.

Definition at line 515 of file shared_random.c.

Referenced by get_ns_str_from_sr_values().

◆ verify_commit_and_reveal()

STATIC int verify_commit_and_reveal ( const sr_commit_t * commit )

Make sure that the commitment and reveal information in commit match. If they match return 0, return -1 otherwise. This function MUST be used every time we receive a new reveal value. Furthermore, the commit object MUST have a reveal value and the hash of the reveal value.

Definition at line 176 of file shared_random.c.

Variable Documentation

◆ num_srv_agreements_from_vote

int32_t num_srv_agreements_from_vote

static

The value of the consensus param AuthDirNumSRVAgreements found in the vote. This is set once the consensus creation subsystem requests the SRV(s) that should be put in the consensus. We use this value to decide if we keep or not an SRV.

Definition at line 122 of file shared_random.c.

◆ previous_srv_str

const char previous_srv_str[] = "shared-rand-previous-value"

static

String prefix of shared random values in votes/consensuses.

Definition at line 113 of file shared_random.c.

Referenced by get_ns_str_from_sr_values().

Functions

Variables

Detailed Description

Function Documentation

◆ commit_decode()

◆ commit_encode()

◆ commit_has_reveal_value()

◆ commit_is_authoritative()

◆ commit_log()

◆ commit_new()

◆ commitments_are_the_same()

◆ compare_reveal_()

◆ compare_srv_()

◆ compare_srvs_()

◆ generate_srv()

◆ get_majority_srv_from_votes()

◆ get_ns_str_from_sr_values()

◆ get_srv_element_from_commit()

◆ get_vote_line_from_commit()

◆ reveal_decode()

◆ reveal_encode()

◆ save_commit_during_reveal_phase()

◆ save_commit_to_state()

◆ should_keep_commit()

◆ should_keep_srv()

◆ smartlist_get_most_frequent_srv()

◆ sr_act_post_consensus()

◆ sr_cleanup()

◆ sr_commit_free_()

◆ sr_compute_srv()

◆ sr_generate_our_commit()

◆ sr_get_string_for_consensus()

◆ sr_get_string_for_vote()

◆ sr_handle_received_commits()

◆ sr_init()

◆ sr_parse_commit()

◆ sr_save_and_cleanup()

◆ sr_srv_dup()

◆ srv_to_ns_string()

◆ verify_commit_and_reveal()

Variable Documentation

◆ num_srv_agreements_from_vote

◆ previous_srv_str