Overview

This proposal alters the Tor consensus protocol such that a random number is generated every midnight by the directory authorities during the regular voting process. The distributed random generator scheme is based on the commit-and-reveal technique.

The proposal also specifies how the final shared random value is embedded in consensus documents so that clients who need it can get it.

Introduction to our commit-and-reveal protocol

Every day, before voting for the consensus at 00:00UTC each authority generates a new random value and keeps it for the whole day. The authority cryptographically hashes the random value and calls the output its "commitment" value. The original random value is called the "reveal" value.

The idea is that given a reveal value you can cryptographically confirm that it corresponds to a given commitment value (by hashing it). However given a commitment value you should not be able to derive the underlying reveal value. The construction of these values is specified in section [COMMITREVEAL].

Ten thousand feet view of the protocol

Our commit-and-reveal protocol aims to produce a fresh shared random value (denoted shared_random_value here and elsewhere) every day at 00:00UTC. The final fresh random value is embedded in the consensus document at that time.

Our protocol has two phases and uses the hourly voting procedure of Tor. Each phase lasts 12 hours, which means that 12 voting rounds happen in between. In short, the protocol works as follows:

Commit phase:

        Starting at 00:00UTC and for a period of 12 hours, authorities every
        hour include their commitment in their votes. They also include any
        received commitments from other authorities, if available.

      Reveal phase:

        At 12:00UTC, the reveal phase starts and lasts till the end of the
        protocol at 00:00UTC. In this stage, authorities must reveal the value
        they committed to in the previous phase. The commitment and revealed
        values from other authorities, when available, are also added to the
        vote.

      Shared Randomness Calculation:

        At 00:00UTC, the shared random value is computed from the agreed
        revealed values and added to the consensus.

   This concludes the commit-and-reveal protocol every day at 00:00UTC.

How we use the consensus

The produced shared random values need to be readily available to clients. For this reason we include them in the consensus documents.

Every hour the consensus documents need to include the shared random value of the day, as well as the shared random value of the previous day. That's because either of these values might be needed at a given time for a Tor client to access a hidden service according to section [TIME-OVERLAP] of proposal 224. This means that both of these two values need to be included in votes as well.

Hence, consensuses need to include:

      (a) The shared random value of the current time period.
      (b) The shared random value of the previous time period.

For this, a new SR consensus method will be needed to indicate which authorities support this new protocol.

Inserting Shared Random Values in the consensus

After voting happens, we need to be careful on how we pick which shared random values (SRV) to put in the consensus, to avoid breaking the consensus because of authorities having different views of the commit-and-reveal protocol (because maybe they missed some rounds of the protocol).

For this reason, authorities look at the received votes before creating a consensus and employ the following logic:

   - First of all, they make sure that the agreed upon consensus method is
     above the SR consensus method.

   - Authorities include an SRV in the consensus if and only if the SRV has
     been voted by at least the majority of authorities.

   - For the consensus at 00:00UTC, authorities include an SRV in the consensus
     if and only if the SRV has been voted by at least AuthDirNumAgreements
     authorities (where AuthDirNumAgreements is a newly introduced consensus
     parameter).

Authorities include in the consensus the most popular SRV that also satisfies the above constraints. Otherwise, no SRV should be included.

The above logic is used to make it harder to break the consensus by natural partioning causes.

We use the AuthDirNumAgreements consensus parameter to enforce that a supermajority of dirauths supports the SR protocol during SRV creation, so that even if a few of those dirauths drop offline in the middle of the run the SR protocol does not get disturbed. We go to extra lengths to ensure this because changing SRVs in the middle of the day has terrible reachability consequences for hidden service clients.

Persistent State of the Protocol

A directory authority needs to keep a persistent state on disk of the on going protocol run. This allows an authority to join the protocol seamlessly in the case of a reboot.

During the commitment phase, it is populated with the commitments of all authorities. Then during the reveal phase, the reveal values are also stored in the state.

As discussed previously, the shared random values from the current and previous time period must also be present in the state at all times if they are available.

Protocol Illustration

An illustration for better understanding the protocol can be found here:

https://people.torproject.org/~asn/hs_notes/shared_rand.jpg

It reads left-to-right.

The illustration displays what the authorities (A_1, A_2, A_3) put in their votes. A chain 'A_1 -> c_1 -> r_1' denotes that authority A_1 committed to the value c_1 which corresponds to the reveal value r_1.

The illustration depicts only a few rounds of the whole protocol. It starts with the first three rounds of the commit phase, then it jumps to the last round of the commit phase. It continues with the first two rounds of the reveal phase and then it jumps to the final round of the protocol run. It finally shows the first round of the commit phase of the next protocol run (00:00UTC) where the final Shared Random Value is computed. In our fictional example, the SRV was computed with 3 authority contributions and its value is "a56fg39h".

We advice you to revisit this after you have read the whole document.

Tor Specifications