[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

(lots of text sorry but this is important).

Ok I had an epiphany while eating my lunch. The partition attack is actually
not mitigated with this requirement:
	"don't use a value until you broadcast it if seen for first time".

For the purpose of the example, we have two groups, A and B composed of each 4
authorities and X is the malicious authority (the 9th one). We are in the
reveal phase of the protocol at hour - 2 (10:00UTC).

At hour - 2, X broadcast its reveal value r_x to group A.

Group A sees r_x for the first time so keep it in memory and wait until the
next voting period at hour - 1 to broadcast the value before using it.

At hour - 1, group A broadcast r_x and thus can start using it.

At hour - 1, group B receives r_x from group A, saves it to memory and wait to
broadcast it until the next voting period (so they can use it).

At hour - 0 (12:00UTC), group B has r_x in memory and *COULD* use it if it
could broadcast it _but_ at this time, all authorities should compute the
shared random value and start a new protocol run. So r_x is NOT put into the
vote of group B thus theoritically, they can NOT use that value for the SR.

-> Partition attack completed. Group A sees r_x with majority but not group B.

Ok ok... now how can we mitigate that. I think we should change the "seen for
the first time" requirement to "seen for the first time and only once in a
voting period".

In the example above, I think group B could have use r_x right away because
they basically got 4 votes (all from group A) with r_x in there. It means that
for the value r_x, it has been seen four times (yes in the same period but
that's not important). It's pretty different then "Oh I've seen r_x but from
only one vote in this period" which can be an attempt to trick me as an
authority so I must inform the others of what I just got.

In a nutshell, if a value arrives in multiple vote for the same period, it's OK
to use it right away but if only seen once for the first time in a single
period, the requirement is to wait-until-broadcast. (Same goes for commit and
reveal). It comes back bit into the indirect/direct vote discussion on when we
are allow to use the value.

Requirement becomes: "Don't use a value until you broadcast it to the others
iff it has been seen for the first time and only once for a single period."

If I have not completely fuck it up, I think it's a very light addition to the
requirement for which we have great benefit :).

Cheers!
David

> 
> 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



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