[tor-dev] Draft Proposal: Random Number Generation During Tor Voting
David Goulet
dgoulet at ev0ke.net
Wed Sep 16 13:06:02 UTC 2015
> George Kadianakis <desnacked at riseup.net> 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 at lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
More information about the tor-dev
mailing list