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

[tor-commits] [torspec/master] Add draft proposal 250-commit-reveal-consensus.txt



commit efdf976b0c2f207eb70f16494d1e2bf3e6da9089
Author: David Goulet <dgoulet@xxxxxxxxx>
Date:   Mon Aug 3 10:11:53 2015 -0400

    Add draft proposal 250-commit-reveal-consensus.txt
    
    Signed-off-by: David Goulet <dgoulet@xxxxxxxxx>
---
 proposals/000-index.txt                   |    2 +
 proposals/250-commit-reveal-consensus.txt |  711 +++++++++++++++++++++++++++++
 2 files changed, 713 insertions(+)

diff --git a/proposals/000-index.txt b/proposals/000-index.txt
index ea312f4..5341899 100644
--- a/proposals/000-index.txt
+++ b/proposals/000-index.txt
@@ -170,6 +170,7 @@ Proposals by number:
 247  Defending Against Guard Discovery Attacks using Vanguards [DRAFT]
 248  Remove all RSA identity keys [DRAFT]
 249  Allow CREATE cells with >505 bytes of handshake data [DRAFT]
+250  Random Number Generation  During Tor Voting [DRAFT]
 
 
 Proposals by status:
@@ -200,6 +201,7 @@ Proposals by status:
    247  Defending Against Guard Discovery Attacks using Vanguards
    248  Remove all RSA identity keys
    249  Allow CREATE cells with >505 bytes of handshake data
+   250  Random Number Generation  During Tor Voting
  NEEDS-REVISION:
    131  Help users to verify they are using Tor
    190  Bridge Client Authorization Based on a Shared Secret
diff --git a/proposals/250-commit-reveal-consensus.txt b/proposals/250-commit-reveal-consensus.txt
new file mode 100644
index 0000000..5861fd9
--- /dev/null
+++ b/proposals/250-commit-reveal-consensus.txt
@@ -0,0 +1,711 @@
+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 Tor-related protocols (or even non-Tor-related) like
+   OnioNS to introduce unpredictability to the protocol.
+
+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 by the directory authorities during the regular voting
+   process. The distributed random generator scheme is based on a
+   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
+   microdescriptor consensus document at that time.
+
+   Our protocol uses a *new* consensus flavor document called "shared
+   randomness document" (SR doc). We use a new consensus document as a way to
+   keep ground truth state and also as a way to apply the majority (see
+   section [MAJORITY]) rule on commit and reveal values. It also allows
+   rebooting authorities to rejoin the protocol in some cases.
+
+   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. From those
+        votes, a shared random document consensus is computed containing the
+        commitments decided by the majority.
+
+      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. Then a shared random document consensus is computed containing
+        the commitments and the revealed values agreed on.
+
+      Shared Randomness Calculation:
+
+        At 12:00UTC, the shared random value is computed from the agreed
+        revealed values located in the shared random document and finally
+        added to the microdescriptor 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 hashes the random value and calls the
+   output its "commitment" value. The original random value is called the
+   "reveal value". Given a reveal value you can verify that it corresponds to
+   a given commitment value. However given a commitment value you cannot
+   derive the underlying reveal value.
+
+2.3. Microdescriptor Consensus [MDCONS]
+
+   Every hour, the microdescriptor 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 SR documents as well.
+
+   Microdescriptor 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. This is the
+          same shared random value that was included in the votes.
+
+2.4. Shared Random Document [SRDOC]
+
+   The Shared Random document is a consensus flavor that contains the current
+   state of our commit & reveal protocol. Since it uses the consensus
+   mechanism of Tor, we use it as a way to enforce majority voting on the
+   commitments and reveals without messing with the actual network status
+   consensus. See section [REBOOT] for detail on how this document is handled
+   when an authority reboots.
+
+   During the commitment phase, the SR doc is populated with the commitments
+   of all authorities. Then during the reveal phase, it's also used to store
+   the reveal values as well.
+
+   As discussed previously, the shared random values from the current and
+   previous time period must be present in the document at all times if they
+   are available.
+
+   A shared random document requires 50% + 1 authority signatures to be
+   considered valid. As this proposal is being written, there are 9
+   authorities thus we would need 5.
+
+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 and the resulting SR doc and
+   microdescriptor 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.
+
+   The goal is that at the end of this phase, the shared random document MUST
+   contain a single commitment value from each authority (or none, if that
+   authority did not participate in this phase).
+
+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).
+
+   After all votes have been received or pulled in, the authorities
+   collectively generate the shared random document containing the
+   commitments.
+
+3.1.2. Shared Random Document During Commitment Phase [SRDOCCOMMIT]
+
+   During the commitment phase, the shared random document contains:
+
+    - The commitments received by the majority of authorities
+    - The two previous shared random values produced by the protocol (if any).
+
+   A commitment should only be transcribed to the shared random document 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.
+
+   The commit phase lasts for 12 hours, so authorities have multiple chances
+   to commit their values. An authority can commit a second value during a
+   subsequent round of the commit phase, but only the last value should be
+   transcribed to the shared random document and only if it has been seen by
+   the majority.
+
+   Also, an authority should not be able to register a commitment value for a
+   different authority. Hence, an authority X should only vote and place in
+   the SR doc commitments by authority Y, iff authority Y included that
+   commitment in its vote.
+
+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 unlikely
+   that a majority opinion of commitments will be created at 12:00UTC. Instead
+   authorities are expected to form a majority opinion and transcribe
+   commitments to the SR doc 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 established during the commitment phase
+   and must remain the same. If an authority tries to change its commitment
+   during the reveal phase or introduce a new commitment, the entire vote MUST
+   be ignored for the purposes of this system. To do so, authorities during
+   the first reveal round MUST check that received votes contain the same
+   commitments as the last SR document of the commitment phase. In subsequent
+   reveal rounds, authorities check the previous hour SR document for
+   commitment validation.
+
+   After all votes have been received, authorities generate the shared random
+   document along with the consensus.
+
+3.2.2. Shared Random Document During Reveal Phase [SRDOCREVEAL]
+
+   During the reveal phase, the shared random document contains:
+
+    - The commitments agreed on during the commitment phase.
+    - The corresponding reveal values from the majority of authorities.
+    - The two previous shared random values produced by this system (if any).
+
+   Similar to the commitment phase, authorities transcribe reveal values to
+   the shared random document if and only if the majority of the voting
+   authorities have voted on that particular reveal value. An example of this
+   can be seen in section [REVEALEXAMPLE].
+
+   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 microdescriptor consensus so
+   clients can use it.
+
+   Authorities calculate the shared random value using the reveal values in
+   the latest shared random document 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 SR document and in the
+   microdescriptor 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 V, should use the
+   appropriate reveal values for that time period and calculate V as follows:
+
+      V = H(ID_a | R_a | ID_b | R_b | ...)
+
+   where the ID_k value is the identity fingerprint of directory authority k
+   and R_k is its corresponding reveal value of that authority for the current
+   period. H is the sha256 for protocol version 1.
+
+   XXX Should the hashing here include more elements? Like the previous random
+       value for chaining? Or the current date? See how the NIST beacon does it
+       in case we can steal some additional RNG security properties:
+               http://hackaday.com/2014/12/19/nist-randomness-beacon/
+
+3.4. Bootstrapping Procedure
+
+   As described in [MDCONS], 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 SHOULD
+   store 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 the shared randomness document until the end of the
+   protocol. The shared randomness document can be used to verify that the
+   commitment values are carried properly.
+
+   An authority that misses the Commitment Phase cannot commit anymore, so
+   it's unable to participate in the protocol for that run. Same thing 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 the voting session right before creating the SR doc, we define the
+   number of active participants to be the number of directory authorities
+   that included commit/reveal values in their votes.
+
+   As specified in sections [SRDOCCOMMIT] and [SRDOCREVEAL], a commit/reveal
+   value should be transcribed to the SR doc if and only if 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.
+
+   Furthermore, as specified in section [SRDOC], the shared random document is
+   considered valid only if it is signed by 50% + 1 authorities.
+
+   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 new
+   shared random value for the day.
+
+   Directory authorities should keep including the previous shared random
+   values in the consensus till the next 12:00UTC commit-and-reveal session.
+   The time period needs to be updated to reflect the current time period even
+   if the random value stays the same.
+
+   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 Encoding the authority's own commit/reveal value
+
+   An authority that wants to commit (or reveal) a value during a vote, should
+   generate a random 256-bit value REVEAL, and include its commitment COMMIT
+   in its 12:00UTC vote as follows:
+
+      "shared-rand-commitment" SP algname SP COMMIT [SP REVEAL] NL
+
+   During the Reveal Phase, an authority can also optionally reveal the value
+   REVEAL. The "algname" is the hash algorithm that should be used to compute
+   COMMIT and REVEAL if any. It should be "sha256" for this version.
+
+   The commitment value COMMIT is constructed as follows:
+
+      C = base64-encode( SHA256(REVEAL) )
+
+4.1.2 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
+
+   when "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 if any.
+
+4.1.3. Shared Random value
+
+  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 value NL
+     "shared-rand-current-value" SP value NL
+
+  where "value" is the actual shared random value. It's computed as specified
+  in the section [SRCALC].
+
+  To maintain consistent ordering, the shared random values of the previous
+  period should be listed before the values of the current period.
+
+4.2. Shared Random Document
+
+   As a way to keep ground truth state in this protocol, we introduce a new
+   consensus flavor document. We call it the "Shared Random Document". This
+   document is only used by directory authorities.
+
+   This new consensus flavor should be signed with the sha256 signature format
+   as documented in proposal 162.
+
+4.2.1 Format [SRFORMAT]
+
+   This document has a very strict format because authorities need to generate
+   the exact same document.
+
+   It contains a preamble, a commitment and reveal section, a list of shared
+   random values and finally a footer.
+
+   The preamble (or header) contains the following items. They MUST occur in
+   the order given here:
+
+    "shared-random-version" SP version SP flavor NL
+
+        [At start, exactly once.]
+
+        A document format version. For this specification, version is "1". The
+        flavor is always "shared-random".
+
+    "created" SP YYYY-MM-DD SP HH:MM:SS NL
+
+        [Exactly once]
+
+        The creation time of this document.
+
+    "valid-until" SP YYYY-MM-DD SP HH:MM:SS NL
+
+        [Exactly once]
+
+        After this time, this document is invalid and shouldn't be used nor
+        trusted. The validity time period is 3 hours.
+
+    "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 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].
+
+   Next is the shared random value section.
+
+     "shared-rand-previous-value" SP value NL
+
+        [At most once]
+
+        This is the previous shared random value agreed on at the previous
+        period. The "value" is defined in section [SRCALC].
+
+     "shared-rand-current-value" SP value NL
+
+        [At most once]
+
+        This is the latest shared random value. The "value" is defined in
+        section [SRCALC].
+
+   Finally, the footer of the document:
+
+     "shared-random-footer" NL
+
+        [Exactly once]
+
+        It contains one subsection, the authority signatures.
+
+           "authority-signature" SP algname SP identity SP signing-key-digest
+                                 NL Signature NL
+
+              [Exactly once per authority]
+
+              The "identity" is the hex-encoded digest of the authority
+              identity key and the "signing-key-digest" is the hex-encoded
+              digest of the current authority signing key of the signing
+              authority.
+
+              The "algname" item is the algorithm used to compute the hash of
+              the document before signing it. As proposal 162 proposed,
+              "sha256" should be used. The authority-signature entry MUST be
+              ignored if "algname" is unrecognized.
+
+              See dir-spec.txt for a specification for the Signature item.
+
+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 SR docs.
+
+   However, we believe that an agreement phase is not necessary in our
+   protocol since reveal values are transcribed in the SR document 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
+   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 or SR doc
+   fails to be created, we fall back to the random value of the previous day
+   meaning authorities will carry the last valid SR values from the previous
+   microdescriptor consensus to the new one.
+
+   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 SR doc will contain:
+
+                         +-------------+
+                         | SR Document |
+                         +-------------+
+                         | 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 also be ignored since it was only seen by half of the auths (3/6)
+   which is not majority (it would require at least 4/6 votes).
+
+   Hence, the final shared random document should contain:
+
+                         +-------------+
+                         | SR Document |
+                         +-------------+
+                         | A_1 -> 444  |
+                         | A_2 -> 110  |
+                         | A_3 -> 420  |
+                         | BLANK       |
+                         | A_5 -> 555  |
+                         | BLANK       |
+                         +-------------+

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