[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: [tor-dev] Draft Proposal: Random Number Generation During Tor Voting



George Kadianakis <desnacked@xxxxxxxxxx> writes:

> Hello there,
>

Hello,

I'm inlining the latest version of proposal250.

It includes various improvements, like completely removing the need for an SR
doc (which will make implementation much much easier), and switching to
signature-based commitments which are attributable and easier to audit. Also the
voting rules have been fleshed out to counter some partioning attacks.

You can also find it in git form here:
    https://gitweb.torproject.org/user/asn/torspec.git/log/?h=prop250-asn

Enjoy!


--------------

Filename: 250-commit-reveal-consensus.txt
Title: Random Number Generation  During Tor Voting
Authors: David Goulet, George Kadianakis
Created: 2015-08-03
Status: Draft

1. Introduction

1.1. Motivation

   For the next generation hidden services project, we need the Tor network to
   produce a fresh random value every day in such a way that it cannot be
   predicted in advance or influenced by an attacker.

   Currently we need this random value to make the HSDir hash ring
   unpredictable (#8244), which should resolve a wide class of hidden service
   DoS attacks and should make it harder for people to gauge the popularity
   and activity of target hidden services. Furthermore this random value can
   be used by other systems in need of fresh global randomness like
   Tor-related protocols (e.g. OnioNS) or even non-Tor-related (e.g. warrant
   canaries).

1.2. Previous work

   Proposal 225 specifies a commit-and-reveal protocol that can be run as an
   external script and have the results be fed to the directory authorities.
   However, directory authority operators feel unsafe running a third-party
   script that opens TCP ports and accepts connections from the Internet.
   Hence, this proposal aims to embed the commit-and-reveal idea in the Tor
   voting process which should makes it smoother to deploy and maintain.

   Another idea proposed specifically for Tor is Nick Hopper's "A threshold
   signature-based proposal for a shared RNG" which was never turned into an
   actual Tor proposal.

2. Overview

   This proposal alters the Tor consensus protocol such that a random number is
   generated every noon 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.

2.1. Ten thousand feet view

   Our commit-and-reveal protocol aims to produce a fresh shared random value
   everyday at 12: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 12:00UTC and for a period of 12 hours, authorities every
        hour send their commitments in their votes. They also include any
        received commitments from other authorities, if available.

      Reveal phase:

        At 00:00UTC, the reveal phase starts and lasts till the end of the
        protocol at 12: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 12:00UTC, the shared random value is computed from the agreed
        revealed values and added to the consensus.

   This concludes the commit-and-reveal procedure at 12:00UTC everyday.

2.2. Commit & Reveal

   Our commit-and-reveal protocol aims to produce a fresh shared random value
   everyday at 12:00UTC.

   In the beginning of that time period, each authority generates a new random
   value and keeps it for the whole day. The authority cryptographically signs a
   hash of 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. 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]. 

2.3. Consensus [CONS]

   The produced shared random value needs to be readily available to
   clients. For this reason we include it in the consensus documents.

   Furthermore, 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. These means that these two values also need
   to be included in votes and in the authority state as well.

   Hence, the consensuses include:

      (a) The shared random value of the current time period. This is derived
          from the reveal values sent by the authorities during the voting
          session.

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

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

2.4. Persistent State of the Protocol [STATE]

   A directory authority needs to keep a persistent state on disk of the on
   going protocol phases. This allows an authority to join the protocol 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.

2.5. Protocol Illustration

   We have prepared an illustration to help you understand the protocol. You can
   find it here:
         https://people.torproject.org/~asn/hs_notes/shared_rand.jpg

   For every hour, it shows the authority votes, the resulting state (SR) and
   consensus. The chain 'A_1 -> c_1 -> r_1' denotes that the authority
   committed to the value c_1 which corresponds to the reveal value r_1.

   The illustration depicts the first 25 hours of running the protocol. It
   starts with the very first commit round, then moves on to the second commit
   round, and then skips directly to the last commit round. Then the reveal
   phase starts, where we again show the first, second and last rounds.

   After the reveal phase is done, we generate the shared randomness (SR_1)
   and we start the new commit phase. The illustration finishes with the
   second round of this new commit phase.

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

3. 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:

3.1 Commitment Phase [COMMITMENTPHASE]

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

   During this phase, an authority commits a value in its vote and saves it to
   its state as well. Authorities decide which commits are active at any given
   time through majority voting.

3.1.1. Voting During Commitment Phase

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

    - A commitment value for this consensus period.
    - Any 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 (see [COMMITCONFLICT]).

3.1.2. Persistent State During Commitment Phase [STATECOMMIT]

   During the commitment phase, an authority state contains:

    - The active commitments (one per auth) agreed by the majority of authorities
    - The two previous shared random values produced by the protocol (if any).

   All received commitments MUST first be verified according to [VALIDATEVALUES].

   A commitment MUST only be transcribed to permanent state if and only if the
   majority of the voting authorities agreed that a particular commitment was
   sent by a particular authority. Appendix section [COMMITEXAMPLE] contains an
   example of this procedure.

   An authority that just received a commitment from another authority's vote
   MUST wait till the next voting round to include that commitment value in its
   own votes.

   An authority transcribes a foreign commitment value to permanent state, only
   after that commitment value has been broadcasted personally by that
   authority.  For example, if A_1 receives c_2 from A_2 for the first time, it
   MUST not write c_2 to permanent state until it's put in A_1's vote and sent
   out to the other authorities.

3.1.3. First & Last Round Of Commitment Phase [FIRSTLASTROUND]

   It's worth mentioning that during the very first round of the commitment
   phase at 12:00UTC, each authority votes its own commitment and is unaware of
   the commitments of the other authorities. For this reason, it's not possible
   that a majority opinion about commitments will be created at
   12:00UTC. Instead authorities are expected to form a majority opinion and
   transcribe commitments to their state during the voting period of 13:00UTC or
   at least until the reveal phase.

   Similarly, an authority will not be able to commit to a new value during
   the last round of the commitment phase. That's because there won't be
   enough time for the other authorities to form a majority opinion about this
   value before the reveal phase. Hence, Tor authorities SHOULD NOT commit new
   values during the last round of the commitment phase at 23:00UTC.

3.2 Reveal Phase

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

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

3.2.1. 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, it should be flagged as a
   conflict (see [COMMITCONFLICT]) and the authority should be ignored until
   the next protocol run.

   Authorities during the first reveal round MUST verify that received votes
   contain the same commitments as the ones in their state (built during the
   last commitment round).

3.2.2. Persistent State During Reveal Phase [STATEREVEAL]

   During the reveal phase, the state contains:

    - The commitments agreed on during the commitment phase.
    - The corresponding reveal values
    - The two previous shared random values produced by this system (if any).

   Reveal values don't require majority voting to be valid. Instead they MUST be
   verified and matched to a commitment value 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.

   An authority transcribes a foreign reveal value to permanent state, only
   after that reveal value has been broadcasted personally by that authority.

   Section [FIRSTLASTROUND] also applies for the reveal phase. This means that
   Tor authorities SHOULD NOT reveal new values during the last round of the
   reveal phase at 11:00UTC.

3.3. Shared Random Value Calculation At 12:00UTC

   Finally, at 12: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].

   If the shared random value contains reveal contributions by less than 3
   directory authorities, it MUST NOT be created. Instead, the old shared
   random value should be used as specified in section [SRDISASTER].

   Authorities at 12: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 proceed voting normally as they would in the
   first round of the commitment phase (section [COMMITMENTPHASE]).

3.3.1. Shared Randomness Calculation [SRCALC]

   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 = H(ID_a | R_a | ID_b | R_b | ..)

      SRV = HMAC(HASHED_REVEALS,
                "shared-random" | INT_8(reveal_num) | INT_8(version) |
                previous_SR)

   where the ID_a value is the identity fingerprint of directory 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_SR" is the previous
   shared random value if any.

   To maintain consistent ordering, ID_a | R_a pairs are ordered based on the
   identity fingerprint of the authority in ascending order.

   For protocol version 1, H is SHA256 and HMAC is HMAC-SHA256.

3.4. 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 12:00UTC consensuses have been
   produced, which takes 48 hours.

3.5. Rebooting Directory Authorities [REBOOT]

   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.

   For this reason, other authorities should carry the commitment values of
   absent authorities in their persistent state until the end of the protocol.

   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.

3.6. How we define majority [MAJORITY]

   The shared randomness protocol must be able to support directory
   authorities who participate in the consensus protocol but not in the shared
   randomness protocol. It must also be able to tolerate authorities who drop
   or join in the middle of the protocol.

   The security of this proposal strongly relies on forming majority opinion
   so it's important for the number of participants to always be well defined:

   In each voting session we define the number of active participants to be the
   number of directory authorities that included their *own* commit/reveal
   values in their votes.

   As specified in sections [STATECOMMIT] and [STATEREVEAL], a commit/reveal
   value should be transcribed to the an authority state iff the majority
   voted for it. So for example, if there are 6 active participants, a commit
   value will only be transcribed if 4 or more participants agreed on it.

   XXX The number of active participants is dynamic as authorities leave and
       join the protocol. Since the number of active participants is dynamic ,
       an attacker could trick some authorities believing there are N
       participants and some others believing there are N-1 participants, by
       sending different votes to different auths. Should we worry? [asn]

       A way to avoid a dynamic number of participants could be to set the
       number of participants to be the number of auths who committed during the
       very first commitment phase round.

3.7. Shared Randomness Disaster Recovery [SRDISASTER]

   If the consensus at 12:00UTC fails to be created, then there will be no fresh
   shared random value for the day.

   In this case, and assuming there is a previous shared random value, directory
   authorities should use the following construction as the shared random value
   of the day:

       SRV = HMAC(previous_SR, "shared-random-disaster")

   where "previous_SR" is the previous shared random value.

   Clients should keep on using this shared random values.

4. Specification [SPEC]

4.1 Voting

   This section describes how commitments, reveals and SR values are encoded
   in votes. We describe how to encode both the authority's own
   commits/reveals and also the commits/reveals received from the other
   authorities. Commits and reveals share the same line, but reveals are
   optional.

4.1.1. Computing commitments and reveals [COMMITREVEAL]

   A directory authority that wants to participate in this protocol needs to
   create a new pair of commitment/reveal values for every protocol
   run. Authorities SHOULD generate a fresh pair of such values right before the
   first commitment phase of the day (at 12:00UTC).

   The procedure is as follows:
       1. Authority generates a fresh 256-bit random value RN.
       2. Authority uses RN to derive REVEAL (see below).
       3. Authority uses REVEAL to derive COMMIT (see below).

   The value REVEAL is computed as follows:

      REVEAL = base64-encode( TIMESTAMP || RN )

      where TIMESTAMP is a big-endian unsigned 64 bit integer being the number
      of seconds since the Unix epoch. RN is the 256-bit random value RN.

   The value COMMIT is computed as follows:

      SIGNATURE = ed25519-sign( privkey=PRIVKEY, msg=H(REVEAL) || TIMESTAMP )
      COMMIT = base64-encode( TIMESTAMP || H(REVEAL) || SIGNATURE )

      where PRIVKEY is the identity key of the authority that is used to sign
      the vote documents. TIMESTAMP is the same as the one used for REVEAL.
      H is the hashing algorithm "sha256".

4.1.2. Validating commitments and reveals [VALIDATEVALUES]

   When authorities receive a COMMIT value, they need to verify the signature
   and ensure that the TIMESTAMP field corresponds ot the current protocol run.
   The same timestamp check should be done on REVEAL values. If an outdated
   COMMIT or REVEAL value is found, it should be ignored.

   Given a COMMIT value, if you later receive its REVEAL value it should be
   possible to verify that they indeed correspond. This can be done as follows:

      TIMESTAMP_R || RN = base64-decode(REVEAL)
      TIMESTAMP_C || COMMIT_SIG = base64-decode(COMMIT)

      return ed25519-verify( pubkey=PUBKEY, sig=COMMIT_SIG,
                             msg=H(RN) || TIMESTAMP )

      where PUBKEY is the identity public key of the authority revealing its
      value. H is the hashing algorithm "sha256".

      TIMESTAMP_R must be equal to TIMESTAMP_C else REVEAL is an invalid value
      for COMMIT.

   Authorities should ignore reveal values during the Reveal Phase that don't
   correspond to commit values published during the Commitment Phase.

4.1.3. Encoding the authority's own commit/reveal value

   The commitment value COMMIT (as computed in [COMMITREVEAL]) should be included
   on votes as follows:

      "shared-rand-commitment" SP algname SP COMMIT [SP REVEAL] NL

   During the Reveal Phase, an authority can also optionally publish its reveal
   value REVEAL. The "algname" is the hash algorithm that should be used to
   compute COMMIT and REVEAL if any. It should be "sha256" for version 1.

4.1.4. Encoding commit/reveal values received by other authorities [COMMITOTHER]

   An authority puts in its vote the commitments and reveals it has seen from
   the other authorities. To do so, it includes the following in its votes:

      "shared-rand-received-commitment" SP identity SP algname SP
                                           COMMIT [SP REVEAL] NL

   where "identity" is the hex-encoded commitment's authority fingerprint and
   COMMIT is the received commitment value. Authorities can also optionally
   include the reveal value REVEAL. There MUST be only one line per authority
   else the vote is considered invalid. Finally, the "algname" is the hash
   algorithm that should be used to compute COMMIT and REVEAL which is
   "sha256" for version 1.

4.1.5. Shared Random Value [SRVOTE]

  Authorities include a shared random value in their votes using the following
  encoding for the previous and current value respectively:

     "shared-rand-previous-value" SP status SP value NL
     "shared-rand-current-value" SP status SP value NL

  where "value" is the actual shared random value. It's normally computed as
  specified in the section [SRCALC].

  "status" denotes how fresh the value is. If that value was produced as
  specified in section [SRCALC] then status is "fresh". If the value was
  produced from a failed protocol run (as specified in [SRDISASTER]) then
  status is "non-fresh".

  To maintain consistent ordering, the shared random values of the previous
  period should be listed before the values of the current period.

4.1.6. Conflict [COMMITCONFLICT]

   If an authority sees two distinct commitments from an other authority, that
   authority is broken or evil: you include both commits, thereby proving
   there is a conflict:

      "shared-rand-conflict" SP identity SP commit1 SP commit2 NL

   where "identity" is the hex-encoded commitment's authority fingerprint.
   "commit1" is the previous commit that the authority had in its state and
   "commit2" is the new received commit of the same period. Both commit values
   are constructed as specified in section [COMMITREVEAL].

   A conflict can occur if:
      - An authority sends two different values during the commitment phase.
      - An authority sends a new commit value during the reveal phase.
      - A commit value seen by other authorities that doesn't match the value
        in the authority's persistent state.

   It is possible for an authority to vote multiple times in the same voting
   period so only the latest commitment conflict should be added to the vote.
   The point of this line is to notify that a conflict happened and not list
   them all.

   When a conflict line is seen in a vote, an authority should verify the
   commit values (see [VALIDATEVALUES]) that they are in fact coming from the
   authority identified by "identity" and if so, ignore that authority until
   the next protocol run. If the conflict line is invalid, ignore it.


4.2. Persistent State

   As a way to keep ground truth state in this protocol, an authority MUST
   keep a persistent state of the protocol.

4.2.1 Format [STATEFORMAT]

   It contains a preamble, a commitment and reveal section and a list of
   shared random values.

   The preamble (or header) contains the following items. They MUST occur in
   the order given here:

    "shared-random-version" SP version NL

        [At start, exactly once.]

        A document format version. For this specification, version is "1".

    "valid-until" SP YYYY-MM-DD SP HH:MM:SS NL

        [Exactly once]

        After this time, this state is expired and shouldn't be used nor
        trusted. The validity time period is till the end of the current
        protocol run (the upcoming noon).

    "protocol-phase" SP phase NL

        [Exactly once]

        The current protocol phase when this document is generated. The
        accepted values are: "commitment" and "reveal".

   The following details the commitment and reveal section.

     "shared-rand-commitment" SP algname SP identity SP
                              YYYY-MM-DD SP HH:MM:SS SP
                              commitment-value [SP revealed-value] NL

        [Exactly once per authority]

        This is the commitment or/and reveal value agreed upon by the majority
        from one authority. The algname is always "sha256" in version 1. The
        "identity" is the authority hex-encoded digest of the authority
        identity key of the signing authority from which the values are from.
        Finally, "{commitment|revealed}-value" is the value as specified in
        section [SPEC].

        This line is also used by an authority to store its own value.

   Finally is the shared random value section.

     "shared-rand-previous-value" SP status SP value NL

        [At most once]

        This is the previous shared random value agreed on at the previous
        period. The fields are the same as in section [SRVOTE].

     "shared-rand-current-value" SP status SP value NL

        [At most once]

        This is the latest shared random value. The fields are the same as in
        section [SRVOTE].


4.3. Shared Random Value in Consensus [SRCONSENSUS]

   Authorities insert the two shared random values in the consensus following
   the same encoding format as in [SRFORMAT].

5. Security Analysis

5.1. Security of commit-and-reveal and future directions

   The security of commit-and-reveal protocols is well understood, and has
   certain flaws. Basically, the protocol is insecure to the extent that an
   adversary who controls b of the authorities gets to choose among 2^b
   outcomes for the result of the protocol. However, an attacker who is not a
   dirauth should not be able to influence the outcome at all.

   We believe that this system offers sufficient security especially compared
   to the current situation. More secure solutions require much more advanced
   crypto and more complex protocols so this seems like an acceptable solution
   for now.

5.2. Is there a need for a final agreement phase?

   Commit-and-reveal protocols usually also end with an agreement phase,
   during which participants agree on which reveal values should be used to
   make the shared random value.

   An agreement phase is needed, because if the protocol ended with the reveal
   phase, an evil authority could wait until the last reveal round, and reveal
   its value to half of the authorities. That would partition the authorities
   into two sets: the ones who think that the shared random value should
   contain this new reveal, and the rest who don't know about it. This would
   result in a tie and two different shared random value.

   However, we believe that an agreement phase is not necessary in our
   protocol since reveal values are choosen if only if the majority agrees.
   Hence, a tie is not enough to confuse the authorities since it's not
   majority and the offending value would just be discarded.

   That said, an attack that could still work here would be if an authority
   can make half of the authorities believe that the value should be
   discarded, and make the other half of the authorities believe that the
   value should be included. That could be achieved if the attacker could
   force honest authorities to send different votes to different authorities.
   We believe this should not be the case currently, but we should look more
   into this.

   XXX Needs feedback by a person who knows the voting protocol well!!!

5.3. Predicting the shared random value during reveal phase

   The reveal phase lasts 12 hours, and most authorities will send their
   reveal value on the first round of the reveal phase. This means that an
   attacker can predict the final shared random value about 12 hours before
   it's generated.

   This does not pose a problem for the HSDir hash ring, since we impose an
   higher uptime restriction on HSDir nodes, so 12 hours predictability is not
   an issue.

   Any other protocols using the shared random value from this system should
   be aware of this property.

6. Discussion

6.1. Why the added complexity from proposal 225?

   The complexity difference between this proposal and prop225 is in part
   because prop225 doesn't specify how the shared random value gets to the
   clients. This proposal spends lots of effort specifying how the two shared
   random values can always be readily accessible to clients.

6.2. Why do you do a commit-and-reveal protocol in 24 rounds?

   The reader might be wondering why we span the protocol over the course of a
   whole day (24 hours), when only 3 rounds would be sufficient to generate a
   shared random value.

   We decided to do it this way, because we piggyback on the Tor voting
   protocol which also happens every hour.

   We could instead only do the shared randomness protocol from 21:00 to 00:00
   every day. Or to do it multiple times a day.

   However, we decided that since the shared random value needs to be in every
   consensus anyway, carrying the commitments/reveals as well will not be a
   big problem. Also, this way we give more chances for a failing dirauth to
   recover and rejoin the protocol.

6.3. Why can't we recover if we fail to do a consensus at 12:00UTC?

   Section [SRDISASTER] specifies that if the 12:00UTC consensus fails to be
   created, we simply hash the random value of the previous day and use it as
   the new shared random value. This changes the daily value but fails to make
   it fresh, which is not optimal.

   Theoretically, we could recover by calculating the shared randomness of the
   day at 13:00UTC instead. However, adding such fallback logic would
   complicate the protocol even further, so we have not yet considered it.

7. Appendix

7.1. Example commitment majority [COMMITEXAMPLE]

   Here is an example of voting during the commitment phase. The table below
   represents the votes of 6 individual authorities A_i (one vote per column).

   Since it's the commitment phase, votes include the authorities commitments
   and all commitments received. For example, below all authorities believe
   that A_1 has registered the value 7 as its commitment.

    +------------+------------+-------------+-------------+-------------+-----------+
    | A_1 vote   | A_2 vote   | A_3 vote    | A_4 vote    | A_5 vote    | A_6 vote  |
    +------------+------------+-------------+-------------+-------------+-----------+
    | A_1 -> 7   | A_1 -> 7   | A_1 -> 7    | A_1 -> 7    |  A_1 -> 7   | A_1 -> 7  |
    | A_2 -> 66  | A_2 -> 66  | A_2 -> 42   | A_2 -> 42   |  A_2 -> 42  | A_2 -> 42 |
    | A_3 -> 16  | A_3 -> 16  | A_3 -> 16   | A_3 -> 16   |  A_3 -> 16  | A_3 -> 16 |
    | A_4 -> 22  | A_4 -> 22  | A_4 -> 22   | BLANK       |  A_4 -> 22  | BLANK     |
    | A_5 -> 9   | A_5 -> 9   | A_5 -> 9    | A_5 -> 9    |  A_5 -> 9   | A_5 -> 9  |
    | A_6 -> 33  | A_6 -> 33  | A_6 -> 33   | A_6 -> 33   |  A_6 -> 33  | BLANK     |
    +------------+------------+-------------+-------------+-------------+-----------+

    In this case, following the majority rule, the final values used are:

                                     +-------------+
                                     | A_1 -> 7    |
                                     | A_2 -> 42   |
                                     | A_3 -> 16   |
                                     | A_4 -> 22   |
                                     | A_5 -> 9    |
                                     | A_6 -> 33   |
                                     +-------------+

7.2. Example reveal phase [REVEALEXAMPLE]

   Here is an example of voting during the reveal phase.

   The table below represents 6 votes by 6 different authorities A_i (one vote
   per column). Since it's the reveal phase, votes include all reveals
   received (commitments have been hidden for simplicity). For example, below
   all authorities believe that A_1 has revealed the value 444.

   Let's say that a malicious dirauth is trying to partition the group into
   two sets, by sending different votes to different auths. The attacker has
   splitted the group into two sets, the auths who think that A_6 has revealed
   the value 123, and the rest who have not seen a reveal from A_6.

    +------------+------------+-------------+-------------+-------------+------------+
    | A_1 vote   | A_2 vote   | A_3 vote    | A_4 vote    | A_5 vote    | A_6 vote   |
    +------------+------------+-------------+-------------+-------------+------------+
    | A_1 -> 444 | A_1 -> 444 | A_1 -> 444  | A_1 -> 444  |  A_1 -> 444 | A_1 -> 444 |
    | A_2 -> 110 | A_2 -> 110 | A_2 -> 110  | A_2 -> 110  |  A_2 -> 110 | A_2 -> 110 |
    | A_3 -> 420 | A_3 -> 420 | A_3 -> 420  | A_3 -> 420  |  A_3 -> 420 | A_3 -> 420 |
    | BLANK      | BLANK      | A_4 -> 980  | BLANK       |  A_4 -> 980 | BLANK      |
    | A_5 -> 666 | A_5 -> 555 | A_5 -> 555  | A_5 -> 555  |  A_5 -> 555 | A_5 -> 555 |
    | A_6 -> 123 | A_6 -> 123 | A_6 -> 123  | BLANK       |  BLANK      | BLANK      |
    +------------+------------+-------------+-------------+-------------+------------+

   Following the rules of the reveal phase, the reveal of A_4 should be
   ignored since it was not voted by > 3 authorities. The reveal from A_6
   should be broadcasted by A_1, A_2 and A_3 during the reveal phase thus
   making the rest of the authorities see it at some point. Remember that for
   a reveal to be used by an authority, no majority is needed, it just need to
   be verified and used if the commit value was choosen by the majority.

   Hence, the final values that must be used are:

                                     +-------------+
                                     | A_1 -> 444  |
                                     | A_2 -> 110  |
                                     | A_3 -> 420  |
                                     | BLANK       |
                                     | A_5 -> 555  |
                                     | A_6 -> 123  |
                                     +-------------+

_______________________________________________
tor-dev mailing list
tor-dev@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev