1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
<a id="srv-spec.txt-2"></a>
# Overview
This proposal alters the Tor consensus protocol such that a random number is
generated every midnight 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.
<a id="srv-spec.txt-2.1"></a>
## Introduction to our commit-and-reveal protocol {#commit-and-reveal}
Every day, before voting for the consensus at 00:00UTC 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.
The idea is that given a reveal value you can cryptographically confirm that
it corresponds to a given commitment value (by hashing it). 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\].
<a id="srv-spec.txt-2.1"></a>
## Ten thousand feet view of the protocol {#10000-feet}
Our commit-and-reveal protocol aims to produce a fresh shared random value
(denoted shared_random_value here and elsewhere) every day at 00: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:
```text
Starting at 00:00UTC and for a period of 12 hours, authorities every
hour include their commitment in their votes. They also include any
received commitments from other authorities, if available.
Reveal phase:
At 12:00UTC, the reveal phase starts and lasts till the end of the
protocol at 00: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 00:00UTC, the shared random value is computed from the agreed
revealed values and added to the consensus.
This concludes the commit-and-reveal protocol every day at 00:00UTC.
```
<a id="srv-spec.txt-2.3"></a>
## How we use the consensus {#CONS}
The produced shared random values need to be readily available to
clients. For this reason we include them in the consensus documents.
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. This means that both of these two values need to be included
in votes as well.
Hence, consensuses need to include:
```text
(a) The shared random value of the current time period.
(b) The shared random value of the previous time period.
```
For this, a new SR consensus method will be needed to indicate which
authorities support this new protocol.
<a id="srv-spec.txt-2.3.1"></a>
### Inserting Shared Random Values in the consensus {#inserting}
After voting happens, we need to be careful on how we pick which shared
random values (SRV) to put in the consensus, to avoid breaking the consensus
because of authorities having different views of the commit-and-reveal
protocol (because maybe they missed some rounds of the protocol).
For this reason, authorities look at the received votes before creating a
consensus and employ the following logic:
```text
- First of all, they make sure that the agreed upon consensus method is
above the SR consensus method.
- Authorities include an SRV in the consensus if and only if the SRV has
been voted by at least the majority of authorities.
- For the consensus at 00:00UTC, authorities include an SRV in the consensus
if and only if the SRV has been voted by at least AuthDirNumAgreements
authorities (where AuthDirNumAgreements is a newly introduced consensus
parameter).
```
Authorities include in the consensus the most popular SRV that also
satisfies the above constraints. Otherwise, no SRV should be included.
The above logic is used to make it harder to break the consensus by natural
partioning causes.
We use the AuthDirNumAgreements consensus parameter to enforce that a
_supermajority_ of dirauths supports the SR protocol during SRV creation, so
that even if a few of those dirauths drop offline in the middle of the run
the SR protocol does not get disturbed. We go to extra lengths to ensure
this because changing SRVs in the middle of the day has terrible
reachability consequences for hidden service clients.
<a id="srv-spec.txt-2.4"></a>
## Persistent State of the Protocol {#STATE}
A directory authority needs to keep a persistent state on disk of the on
going protocol run. This allows an authority to join the protocol seamlessly
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.
<a id="srv-spec.txt-2.5"></a>
## Protocol Illustration {#illustration}
An illustration for better understanding the protocol can be found here:
<https://people.torproject.org/~asn/hs_notes/shared_rand.jpg>
It reads left-to-right.
The illustration displays what the authorities (A_1, A_2, A_3) put in their
votes. A chain 'A_1 -> c_1 -> r_1' denotes that authority A_1 committed to
the value c_1 which corresponds to the reveal value r_1.
The illustration depicts only a few rounds of the whole protocol. It starts
with the first three rounds of the commit phase, then it jumps to the last
round of the commit phase. It continues with the first two rounds of the
reveal phase and then it jumps to the final round of the protocol run. It
finally shows the first round of the commit phase of the next protocol run
(00:00UTC) where the final Shared Random Value is computed. In our fictional
example, the SRV was computed with 3 authority contributions and its value
is "a56fg39h".
We advice you to revisit this after you have read the whole document.
|
