Re: [tor-dev] Proposal 178: Require majority of authorities to vote for consensus parameters
On Tue, Feb 22, 2011 at 1:34 AM, Sebastian Hahn hahn.seb@web.de wrote:
Design:
When the consensus is generated, the directory authorities ensure that a param is only included in the list of params if at least half of the total number of authorities votes for that param. The value chosen is the low-median of all the votes. We don't mandate that the authorities have to vote on exactly the same value for it to be included because some consensus parameters could be the result of active measurements that individual authorities make.
This is possibly bikeshed, but I would suggest that instead of requiring half of existing authorities to vote on a particular parameter, we require 3 or more to vote on it. (As a degenerate case, fall back to "at least half" if there are fewer than 6 authorities in the clique.)
I think we don't want the number to be _less_ than 3, since 3 is the smallest number of parties who can come up with a low-median that isn't just the diktat of a single member (1 party), or as low as either member wants it to be (2 parties).
yrs,
On Mar 2, 2011, at 8:06 AM, Nick Mathewson wrote:
On Tue, Feb 22, 2011 at 1:34 AM, Sebastian Hahn hahn.seb@web.de wrote:
Design:
When the consensus is generated, the directory authorities ensure that a param is only included in the list of params if at least half of the total number of authorities votes for that param. The value chosen is the low-median of all the votes. We don't mandate that the authorities have to vote on exactly the same value for it to be included because some consensus parameters could be the result of active measurements that individual authorities make.
This is possibly bikeshed, but I would suggest that instead of requiring half of existing authorities to vote on a particular parameter, we require 3 or more to vote on it. (As a degenerate case, fall back to "at least half" if there are fewer than 6 authorities in the clique.)
Hrm. I'm not too happy with this, unless we also include a way for a majority of authorities to prevent voting on that parameter altogether. Doing the design as presented above would then be simpler.
I think we don't want the number to be _less_ than 3, since 3 is the smallest number of parties who can come up with a low-median that isn't just the diktat of a single member (1 party), or as low as either member wants it to be (2 parties).
Yes, anything less than 3 is bad imo.
Sebastian
On May 2, 2011, at 11:23 AM, Sebastian Hahn wrote:
On Mar 2, 2011, at 8:06 AM, Nick Mathewson wrote:
This is possibly bikeshed, but I would suggest that instead of requiring half of existing authorities to vote on a particular parameter, we require 3 or more to vote on it. (As a degenerate case, fall back to "at least half" if there are fewer than 6 authorities in the clique.)
Hrm. I'm not too happy with this, unless we also include a way for a majority of authorities to prevent voting on that parameter altogether. Doing the design as presented above would then be simpler.
I updated the proposal without taking into account the suggested change. If people feel strongly I'm happy to revise it as I indicated above. I've pushed an updated version to my torspec repository, where the old version [0], the new version [1] and a diff [2] between the two is available.
I updated the example implementation to be compatible with the current code, and changed it to refer to this proposal correctly instead of 178. I hope that with this clarification on the intentions this proposal can go into the accepted category, unless concerns remain.
Below I am replicating the new version of the proposal fully.
Thanks Sebastian
[0]: https://gitweb.torproject.org/sebastian/torspec.git/blob/e52b2be829a9a8027c1... [1]: https://gitweb.torproject.org/sebastian/torspec.git/blob/0fe8b85897a8919b291... [2]: https://gitweb.torproject.org/sebastian/torspec.git/commitdiff/0fe8b85897a89...
Filename: 178-param-voting.txt Title: Require majority of authorities to vote for consensus parameters Author: Sebastian Hahn Created: 16-Feb-2011 Status: Open
Overview:
The consensus that the directory authorities create may contain one or more parameters (32-bit signed integers) that influence the behavior of Tor nodes (see proposal 167, "Vote on network parameters in consensus" for more details).
Currently (as of consensus method 11), a consensus will end up containing a parameter if at least one directory authority votes for that paramater. The value of the parameter will be the low-median of all the votes for this parameter.
This proposal aims at changing this voting process to be more secure against tampering by a non-majority of directory authorities.
Motivation:
To prevent a minority of the directory authorities from influencing the value of a parameter unduly, the majority of directory authorities has to vote for that parameter. This is not currently happening, and it was in fact not uncommon for a single authority to govern the value of a consensus parameter.
Design:
When the consensus is generated, the directory authorities ensure that a param is only included in the list of params if at least half of the total number of authorities votes for that param. The value chosen is the low-median of all the votes. We don't mandate that the authorities have to vote on exactly the same value for it to be included because some consensus parameters could be the result of active measurements that individual authorities make.
Security implications:
This change is aimed at improving the security of Tor nodes against attacks carried out by a minority of directory authorities. It is possible that a consensus parameter that would be helpful to the network is not included because not enough directory authorities voted for it, but since clients are required to have sane defaults in case the parameter is absent this does not carry a security risk.
Specification:
dir-spec section 3.4 currently says:
Entries are given on the "params" line for every keyword on which any authority voted. The values given are the low-median of all votes on that keyword.
It is proposed that the above is changed to:
Entries are given on the "params" line for every keyword on which a majority of authorities (total authorities, not just those participating this vote) voted on. The values given are the low-median of all votes on that keyword.
Consensus methods 11 and before, entries are given on the "params" line for every keyword on which any authority voted, the value given being the low-median of all votes on that keyword.
The following should be added to the bottom of section 3.4.:
* If consensus method 12 or later is used, only consensus parameters that more than half of the total number of authorities voted for are included in the consensus.
The following line should be added to the bottom of section 3.4.1.:
"12" -- Params are only included if a majority voted for them
Compatibility:
A sufficient number of directory authorities must upgrade to the new consensus method used to calculate the params in the way this proposal calls for, otherwise the old mechanism is used. Nodes that do not act as directory authorities do not need to be upgraded and should experience no change in behaviour.
Implementation:
An example implementation of this feature can be found in https://gitweb.torproject.org/sebastian/tor.git, branch safer_params.
On Mon, May 2, 2011 at 5:23 AM, Sebastian Hahn hahn.seb@web.de wrote:
On Mar 2, 2011, at 8:06 AM, Nick Mathewson wrote:
On Tue, Feb 22, 2011 at 1:34 AM, Sebastian Hahn hahn.seb@web.de wrote:
Design:
When the consensus is generated, the directory authorities ensure that a param is only included in the list of params if at least half of the total number of authorities votes for that param. The value chosen is the low-median of all the votes. We don't mandate that the authorities have to vote on exactly the same value for it to be included because some consensus parameters could be the result of active measurements that individual authorities make.
This is possibly bikeshed, but I would suggest that instead of requiring half of existing authorities to vote on a particular parameter, we require 3 or more to vote on it. (As a degenerate case, fall back to "at least half" if there are fewer than 6 authorities in the clique.)
Hrm. I'm not too happy with this,
My rationale was that in practice, it's a pain in practice to try to get more than 3 or so authority operators to try out an experimental parameter in a timely basis. If the set of authority operators ever grows, getting half of the ops to tweak a parameter in a hurry will get even harder.
unless we also include a way for a majority of authorities to prevent voting on that parameter altogether.
What if we say that as a matter of design, there should always be, for each parameter, a value that's semantically equivalent to the absence of the parameter? That way a majority of authorities can "turn off" any parameter without any additional machinery during the vote.
On May 4, 2011, at 2:49 AM, Nick Mathewson wrote:
On Mon, May 2, 2011 at 5:23 AM, Sebastian Hahn hahn.seb@web.de wrote:
On Mar 2, 2011, at 8:06 AM, Nick Mathewson wrote:
On Tue, Feb 22, 2011 at 1:34 AM, Sebastian Hahn hahn.seb@web.de wrote:
Design:
When the consensus is generated, the directory authorities ensure that a param is only included in the list of params if at least half of the total number of authorities votes for that param. The value chosen is the low-median of all the votes. We don't mandate that the authorities have to vote on exactly the same value for it to be included because some consensus parameters could be the result of active measurements that individual authorities make.
This is possibly bikeshed, but I would suggest that instead of requiring half of existing authorities to vote on a particular parameter, we require 3 or more to vote on it. (As a degenerate case, fall back to "at least half" if there are fewer than 6 authorities in the clique.)
Hrm. I'm not too happy with this,
My rationale was that in practice, it's a pain in practice to try to get more than 3 or so authority operators to try out an experimental parameter in a timely basis. If the set of authority operators ever grows, getting half of the ops to tweak a parameter in a hurry will get even harder.
Yes, I understand that argument. On the other hand, getting a hold of n-3 authority operators that did set a param can also be hard (I'm thinking about the last time we thought that dirauths might crash the network by distributing ipv6 descriptors, where it took a while to even reach those who had applied our first patch).
unless we also include a way for a majority of authorities to prevent voting on that parameter altogether.
What if we say that as a matter of design, there should always be, for each parameter, a value that's semantically equivalent to the absence of the parameter? That way a majority of authorities can "turn off" any parameter without any additional machinery during the vote.
This could work, but that means we need to re-implement a bunch of our parameters that don't currently work that way. I'm thinking about bug 1947 here, for example. Overloading the param value to mean "this special integer means this specific param is not set" might also lead to interesting situations where we aren't quite sure if 0 or INT32_MIN or something else is responsible for disabling a param. Maybe that's still easier to do than other ideas, and more convenient in the common case where we don't have a bad param that we must not set, which is what we should care about. I'm not sold on your idea just yet, but I do think it can work.
Sebastian
On May 4, 2011, at 7:20 AM, Sebastian Hahn wrote:
On May 4, 2011, at 2:49 AM, Nick Mathewson wrote:
On Mon, May 2, 2011 at 5:23 AM, Sebastian Hahn hahn.seb@web.de wrote:
On Mar 2, 2011, at 8:06 AM, Nick Mathewson wrote:
On Tue, Feb 22, 2011 at 1:34 AM, Sebastian Hahn hahn.seb@web.de wrote:
Design:
When the consensus is generated, the directory authorities ensure that a param is only included in the list of params if at least half of the total number of authorities votes for that param. The value chosen is the low-median of all the votes. We don't mandate that the authorities have to vote on exactly the same value for it to be included because some consensus parameters could be the result of active measurements that individual authorities make.
This is possibly bikeshed, but I would suggest that instead of requiring half of existing authorities to vote on a particular parameter, we require 3 or more to vote on it. (As a degenerate case, fall back to "at least half" if there are fewer than 6 authorities in the clique.)
Hrm. I'm not too happy with this,
My rationale was that in practice, it's a pain in practice to try to get more than 3 or so authority operators to try out an experimental parameter in a timely basis. If the set of authority operators ever grows, getting half of the ops to tweak a parameter in a hurry will get even harder.
Yes, I understand that argument. On the other hand, getting a hold of n-3 authority operators that did set a param can also be hard (I'm thinking about the last time we thought that dirauths might crash the network by distributing ipv6 descriptors, where it took a while to even reach those who had applied our first patch).
unless we also include a way for a majority of authorities to prevent voting on that parameter altogether.
What if we say that as a matter of design, there should always be, for each parameter, a value that's semantically equivalent to the absence of the parameter? That way a majority of authorities can "turn off" any parameter without any additional machinery during the vote.
This could work, but that means we need to re-implement a bunch of our parameters that don't currently work that way. I'm thinking about bug 1947 here, for example. Overloading the param value to mean "this special integer means this specific param is not set" might also lead to interesting situations where we aren't quite sure if 0 or INT32_MIN or something else is responsible for disabling a param. Maybe that's still easier to do than other ideas, and more convenient in the common case where we don't have a bad param that we must not set, which is what we should care about. I'm not sold on your idea just yet, but I do think it can work.
Sebastian
I have since become convinced that it would be better to get this implemented quickly, even if it doesn't have a generic "prevent this param from being set" mechanism. I would thus like to change the proposal to the following (also available in my prop178 branch in my torspec repository). The diff is available at https://gitweb.torproject.org/sebastian/torspec.git/commitdiff/db9a429d005ae...
The branch safer_params in my repository has been updated to reflect the new state of the proposal, the original branch is available as safer_params_old. I'm still targetting this for 0.2.3, but if that's not possible we can also easily delay it.
Thanks Sebastian
On Nov 25, 2011, at 9:27 PM, Sebastian Hahn wrote:
I have since become convinced that it would be better to get this implemented quickly, even if it doesn't have a generic "prevent this param from being set" mechanism. I would thus like to change the proposal to the following (also available in my prop178 branch in my torspec repository). The diff is available at https://gitweb.torproject.org/sebastian/torspec.git/commitdiff/db9a429d005ae...
I meant to also send the proposal here, inline. Looks like I messed that up. Here goes:
Filename: 178-param-voting.txt Title: Require majority of authorities to vote for consensus parameters Author: Sebastian Hahn Created: 16-Feb-2011 Status: Open Target: 0.2.3.x
Overview:
The consensus that the directory authorities create may contain one or more parameters (32-bit signed integers) that influence the behavior of Tor nodes (see proposal 167, "Vote on network parameters in consensus" for more details).
Currently (as of consensus method 11), a consensus will end up containing a parameter if at least one directory authority votes for that paramater. The value of the parameter will be the low-median of all the votes for this parameter.
This proposal aims at changing this voting process to be more secure against tampering by a small fraction of directory authorities.
Motivation:
To prevent a small fraction of the directory authorities from influencing the value of a parameter unduly, a big enough fraction of all directory authorities authorities has to vote for that parameter. This is not currently happening, and it is in fact not uncommon for a single authority to govern the value of a consensus parameter.
Design:
When the consensus is generated, the directory authorities ensure that a param is only included in the list of params if at least three of the authorities (or a simple majority, whichever is the smaller number) votes for that param. The value chosen is the low-median of all the votes. We don't mandate that the authorities have to vote on exactly the same value for it to be included because some consensus parameters could be the result of active measurements that individual authorities make.
Security implications:
This change is aimed at improving the security of Tor nodes against attacks carried out by a small fraction of directory authorities. It is possible that a consensus parameter that would be helpful to the network is not included because not enough directory authorities voted for it, but since clients are required to have sane defaults in case the parameter is absent this does not carry a security risk.
This proposal makes a security vs coordination effort tradeoff. When considering only the security of the design, it would be better to require a simple majority of directory authorities to agree on voting on a parameter, but it would involve requiring more directory authority operators to coordinate their actions to set the parameter successfully.
Specification:
dir-spec section 3.4 currently says:
Entries are given on the "params" line for every keyword on which any authority voted. The values given are the low-median of all votes on that keyword.
It is proposed that the above is changed to:
Entries are given on the "params" line for every keyword on which a majority of authorities (total authorities, not just those participating in this vote) voted on, or if at least three authorities voted for that parameter. The values given are the low-median of all votes on that keyword.
Consensus methods 11 and before, entries are given on the "params" line for every keyword on which any authority voted, the value given being the low-median of all votes on that keyword.
The following should be added to the bottom of section 3.4.:
* If consensus method 12 or later is used, only consensus parameters that more than half of the total number of authorities voted for are included in the consensus.
The following line should be added to the bottom of section 3.4.1.:
"12" -- Params are only included if a enough auths voted for them
Compatibility:
A sufficient number of directory authorities must upgrade to the new consensus method used to calculate the params in the way this proposal calls for, otherwise the old mechanism is used. Nodes that do not act as directory authorities do not need to be upgraded and should experience no change in behaviour.
Implementation:
An example implementation of this feature can be found in https://gitweb.torproject.org/sebastian/tor.git, branch safer_params.
On Nov 25, 2011, at 9:58 PM, Sebastian Hahn wrote:
On Nov 25, 2011, at 9:27 PM, Sebastian Hahn wrote:
I have since become convinced that it would be better to get this implemented quickly, even if it doesn't have a generic "prevent this param from being set" mechanism. I would thus like to change the proposal to the following (also available in my prop178 branch in my torspec repository). The diff is available at https://gitweb.torproject.org/sebastian/torspec.git/commitdiff/db9a429d005ae...
I meant to also send the proposal here, inline. Looks like I messed that up. Here goes:
Looks like Nick liked the revised proposal and implementation after fixups, the code and spec changes have been merged and the proposal was marked closed just a few minutes ago.
Thanks all!
-
Nick Mathewson -
Sebastian Hahn