commit efdf976b0c2f207eb70f16494d1e2bf3e6da9089 Author: David Goulet dgoulet@ev0ke.net Date: Mon Aug 3 10:11:53 2015 -0400
Add draft proposal 250-commit-reveal-consensus.txt
Signed-off-by: David Goulet dgoulet@ev0ke.net --- 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 | + +-------------+