Protocol

In this section we give a detailed specification of the protocol. We describe the protocol participants' logic and the messages they send. The encoding of the messages is specified in the next section ([SPEC]).

Now we go through the phases of the protocol:

Commitment Phase

The commit phase lasts from 00:00UTC to 12:00UTC.

During this phase, an authority commits a value in its vote and saves it to the permanent state as well.

Authorities also save any received authoritative commits by other authorities in their permanent state. We call a commit by Alice "authoritative" if it was included in Alice's vote.

Voting During Commitment Phase

During the commit phase, each authority includes in its votes:

    - The commitment value for this protocol run.
    - Any authoritative commitments received from other authorities.
    - The two previous shared random values produced by the protocol (if any).

The commit phase lasts for 12 hours, so authorities have multiple chances to commit their values. An authority MUST NOT commit a second value during a subsequent round of the commit phase.

If an authority publishes a second commitment value in the same commit phase, only the first commitment should be taken in account by other authorities. Any subsequent commitments MUST be ignored.

Persistent State During Commitment Phase

During the commitment phase, authorities save in their persistent state the authoritative commits they have received from each authority. Only one commit per authority must be considered trusted and active at a given time.

Reveal Phase

The reveal phase lasts from 12:00UTC to 00:00UTC.

Now that the commitments have been agreed on, it's time for authorities to reveal their random values.

Voting During Reveal Phase

During the reveal phase, each authority includes in its votes:

    - Its reveal value that was previously committed in the commit phase.
    - All the commitments and reveals received from other authorities.
    - The two previous shared random values produced by the protocol (if any).

The set of commitments have been decided during the commitment phase and must remain the same. If an authority tries to change its commitment during the reveal phase or introduce a new commitment, the new commitment MUST be ignored.

Persistent State During Reveal Phase

During the reveal phase, authorities keep the authoritative commits from the commit phase in their persistent state. They also save any received reveals that correspond to authoritative commits and are valid (as specified in [VALIDATEVALUES]).

An authority that just received a reveal value from another authority's vote, MUST wait till the next voting round before including that reveal value in its votes.

Shared Random Value Calculation At 00:00UTC

Finally, at 00:00UTC every day, authorities compute a fresh shared random value and this value must be added to the consensus so clients can use it.

Authorities calculate the shared random value using the reveal values in their state as specified in subsection [SRCALC].

Authorities at 00:00UTC start including this new shared random value in their votes, replacing the one from two protocol runs ago. Authorities also start including this new shared random value in the consensus as well.

Apart from that, authorities at 00:00UTC proceed voting normally as they would in the first round of the commitment phase (section [COMMITMENTPHASE]).

Shared Randomness Calculation

An authority that wants to derive the shared random value SRV, should use the appropriate reveal values for that time period and calculate SRV as follows.

      HASHED_REVEALS = SHA3_256(ID_a | R_a | ID_b | R_b | ..)

      SRV = SHA3_256("shared-random" | INT_8(REVEAL_NUM) | INT_4(VERSION) |
                     HASHED_REVEALS | PREVIOUS_SRV)

where the ID_a value is the identity key fingerprint of authority 'a' and R_a is the corresponding reveal value of that authority for the current period.

Also, REVEAL_NUM is the number of revealed values in this construction, VERSION is the protocol version number and PREVIOUS_SRV is the previous shared random value. If no previous shared random value is known, then PREVIOUS_SRV is set to 32 NUL (\x00) bytes.

To maintain consistent ordering in HASHED_REVEALS, all the ID_a | R_a pairs are ordered based on the R_a value in ascending order.

Bootstrapping Procedure

As described in [CONS], two shared random values are required for the HSDir overlay periods to work properly as specified in proposal 224. Hence clients MUST NOT use the randomness of this system till it has bootstrapped completely; that is, until two shared random values are included in a consensus. This should happen after three 00:00UTC consensuses have been produced, which takes 48 hours.

Rebooting Directory Authorities

The shared randomness protocol must be able to support directory authorities who leave or join in the middle of the protocol execution.

An authority that commits in the Commitment Phase and then leaves MUST have stored its reveal value on disk so that it continues participating in the protocol if it returns before or during the Reveal Phase. The reveal value MUST be stored timestamped to avoid sending it on wrong protocol runs.

An authority that misses the Commitment Phase cannot commit anymore, so it's unable to participate in the protocol for that run. Same goes for an authority that misses the Reveal phase. Authorities who do not participate in the protocol SHOULD still carry commits and reveals of others in their vote.

Finally, authorities MUST implement their persistent state in such a way that they will never commit two different values in the same protocol run, even if they have to reboot in the middle (assuming that their persistent state file is kept). A suggested way to structure the persistent state is found at [STATEFORMAT].

Tor Specifications