give steven's everybody-a-bridge proposal a number

1 files changed, 239 insertions, 0 deletions

diff --git a/proposals/175-automatic-node-promotion.txt b/proposals/175-automatic-node-promotion.txt
new file mode 100644
index 0000000..bbe6b37
--- /dev/null
+++ b/proposals/175-automatic-node-promotion.txt
@@ -0,0 +1,239 @@
+Filename: xxx-automatic-node-promotion.txt
+Title: Automatically promoting Tor clients to nodes
+Author: Steven Murdoch
+Created: 12-Mar-2010
+Status: Draft
+Target:
+
+1. Overview
+
+   This proposal describes how Tor clients could determine when they
+   have sufficient bandwidth capacity and are sufficiently reliable to
+   become either bridges or Tor relays. When they meet this
+   criteria, they will automatically promote themselves, based on user
+   preferences. The proposal also defines the new controller messages
+   and options which will control this process.
+
+   Note that for the moment, only transitions between client and
+   bridge are being considered. Transitions to public relay will
+   be considered at a future date, but will use the same
+   infrastructure for measuring capacity and reliability.
+
+2. Motivation and history
+
+   Tor has a growing user-base and one of the major impediments to the
+   quality of service offered is the lack of network capacity. This is
+   particularly the case for bridges, because these are gradually
+   being blocked, and thus no longer of use to people within some
+   countries. By automatically promoting Tor clients to bridges, and
+   perhaps also to full public relays, this proposal aims to solve
+   these problems.
+ 
+   Only Tor clients which are sufficiently useful should be promoted,
+   and the process of determining usefulness should be performed
+   without reporting the existence of the client to the central
+   authorities. The criteria used for determining usefulness will be
+   in terms of bandwidth capacity and uptime, but parameters should be
+   specified in the directory consensus. State stored at the client
+   should be in no more detail than necessary, to prevent sensitive
+   information being recorded.
+
+3. Design
+
+3.x Opt-in state model
+
+   Tor can be in one of five node-promotion states:
+
+   - off (O): Currently a client, and will stay as such
+   - auto (A): Currently a client, but will consider promotion
+   - bridge (B): Currently a bridge, and will stay as such
+   - auto-bridge (AB): Currently a bridge, but will consider promotion
+   - relay (R): Currently a public relay, and will stay as such
+
+   The state can be fully controlled from the configuration file or
+   controller, but the normal state transitions are as follows:
+
+   Any state -> off: User has opted out of node promotion
+   Off -> any state: Only permitted with user consent
+
+   Auto -> auto-bridge: Tor has detected that it is sufficiently
+    reliable to be a *bridge*
+   Auto -> bridge: Tor has detected that it is sufficiently reliable
+    to be a *relay*, but the user has chosen to remain a *bridge*
+   Auto -> relay: Tor has detected that it is sufficiently reliable
+    to be *relay*, and will skip being a *bridge*
+   Auto-bridge -> relay: Tor has detected that it is sufficiently
+    reliable to be a *relay*
+
+   Note that this model does not support automatic demotion. If this
+   is desirable, there should be some memory as to whether the
+   previous state was relay, bridge, or auto-bridge. Otherwise the
+   user may be prompted to become a relay, although he has opted to
+   only be a bridge.
+
+3.x User interaction policy
+
+   There are a variety of options in how to involve the user into the
+   decision as to whether and when to perform node promotion. The
+   choice also may be different when Tor is running from Vidalia (and
+   thus can readily prompt the user for information), and standalone
+   (where Tor can only log messages, which may or may not be read).
+
+   The option requiring minimal user interaction is to automatically
+   promote nodes according to reliability, and allow the user to opt
+   out, by changing settings in the configuration file or Vidalia user
+   interface.
+
+   Alternatively, if a user interface is available, Tor could prompt
+   the user when it detects that a transition is available, and allow
+   the user to choose which of the available options to select. If
+   Vidalia is not available, it still may be possible to solicit an
+   email address on install, and contact the operator to ask whether
+   a transition to bridge or relay is permitted.
+
+   Finally, Tor could by default not make any transition, and the user
+   would need to opt in by stating the maximum level (bridge or
+   relay) to which the node may automatically promote itself.
+
+3.x Performance monitoring model
+
+   To prevent a large number of clients activating as relays, but
+   being too unreliable to be useful, clients should measure their
+   performance. If this performance meets a parameterized acceptance
+   criteria, a client should consider promotion. To measure
+   reliability, this proposal adopts a simple user model:
+
+    - A user decides to use Tor at times which follow a Poisson
+      distribution
+    - At each time, the user will be happy if the bridge chosen has
+      adequate bandwidth and is reachable
+    - If the chosen bridge is down or slow too many times, the user
+      will consider Tor to be bad
+
+   If we additionally assume that the recent history of relay
+   performance matches the current performance, we can measure
+   reliability by simulating this simple user.
+
+   The following parameters are distributed to clients in the
+   directory consensus:
+
+     - min_bandwidth: Minimum self-measured bandwidth for a node to be
+       considered useful, in bytes per second
+     - check_period: How long, in seconds, to wait between checking
+       reachability and bandwidth (on average)
+     - num_samples: Number of recent samples to keep
+     - num_useful: Minimum number of recent samples where the node was
+       reachable and had at least min_bandwidth capacity, for a client
+       to consider promoting to a bridge
+
+   A different set of parameters may be used for considering when to
+   promote a bridge to a full relay, but this will be the subject of a
+   future revision of the proposal.
+
+3.x Performance monitoring algorithm
+
+   The simulation described above can be implemented as follows:
+
+   Every 60 seconds:
+     1. Tor generates a random floating point number x in
+        the interval [0, 1).
+     2. If x > (1 / (check_period / 60)) GOTO end; otherwise:
+     3. Tor sets the value last_check to the current_time (in seconds)
+     4. Tor measures reachability
+     5. If the client is reachable, Tor measures its bandwidth
+     6. If the client is reachable and the bandwidth is >=
+        min_bandwidth, the test has succeeded, otherwise it has failed.
+     7. Tor adds the test result to the end of a ring-buffer containing
+        the last num_samples results: measurement_results
+     8. Tor saves last_check and measurements_results to disk
+     9. If the length of measurements_results == num_samples and
+        the number of successes >= num_useful, Tor should consider
+        promotion to a bridge
+   end.
+ 
+   When Tor starts, it must fill in the samples for which it was not
+   running. This can only happen once the consensus has downloaded,
+   because the value of check_period is needed.
+ 
+      1. Tor generates a random number y from the Poisson distribution [1]
+         with lambda = (current_time - last_check) * (1 / check_period)
+      2. Tor sets the value last_check to the current_time (in seconds)	
+      3. Add y test failures to the ring buffer measurements_results
+      4. Tor saves last_check and measurements_results to disk
+ 
+   In this way, a Tor client will measure its bandwidth and
+   reachability every check_period seconds, on average. Provided
+   check_period is sufficiently greater than a minute (say, at least an
+   hour), the times of check will follow a Poisson distribution. [2]
+ 
+   While this does require that Tor does record the state of a client
+   over time, this does not leak much information. Only a binary
+   reachable/non-reachable is stored, and the timing of samples becomes
+   increasingly fuzzy as the data becomes less recent.
+
+   On IP address changes, Tor should clear the ring-buffer, because
+   from the perspective of users with the old IP address, this node
+   might as well be a new one with no history. This policy may change
+   once we start allowing the bridge authority to hand out new IP
+   addresses given the fingerprint.
+
+3.x Bandwidth measurement
+
+   Tor needs to measure its bandwidth to test the usefulness as a
+   bridge. A non-intrusive way to do this would be to passively measure
+   the peak data transfer rate since the last reachability test. Once
+   this exceeds min_bandwidth, Tor can set a flag that this node
+   currently has sufficient bandwidth to pass the bandwidth component
+   of the upcoming performance measurement.
+
+   For the first version we may simply skip the bandwidth test,
+   because the existing reachability test sends 500 kB over several
+   circuits, and checks whether the node can transfer at least 50
+   kB/s.  This is probably good enough for a bridge, so this test
+   might be sufficient to record a success in the ring buffer.
+
+3.x New options
+
+3.x New controller message
+
+4. Migration plan
+
+   We should start by setting a high bandwidth and uptime requirement
+   in the consensus, so as to avoid overloading the bridge authority
+   with too many bridges. Once we are confident our systems can scale,
+   the criteria can be gradually shifted down to gain more bridges.
+
+5. Related proposals
+
+6. Open questions:
+
+   - What user interaction policy should we take?
+
+   - When (if ever) should we turn a relay into an exit relay?
+
+   - What should the rate limits be for auto-promoted bridges/relays?
+     Should we prompt the user for this?
+
+   - Perhaps the bridge authority should tell potential bridges
+     whether to enable themselves, by taking into account whether
+     their IP address is blocked
+
+   - How do we explain the possible risks of running a bridge/relay
+     * Use of bandwidth/congestion
+     * Publication of IP address
+     * Blocking from IRC (even for non-exit relays)
+
+   - What feedback should we give to bridge relays, to encourage then
+     e.g. number of recent users (what about reserve bridges)?
+
+   - Can clients back-off from doing these tests (yes, we should do
+     this)
+
+[1] For algorithms to generate random numbers from the Poisson
+    distribution, see: http://en.wikipedia.org/wiki/Poisson_distribution#Generating_Poisson-distributed_random_variables
+[2] "The sample size n should be equal to or larger than 20 and the
+     probability of a single success, p, should be smaller than or equal to
+     .05. If n >= 100, the approximation is excellent if np is also <= 10."
+    http://www.itl.nist.gov/div898/handbook/pmc/section3/pmc331.htm (e-Handbook of Statistical Methods)
+
+% vim: spell ai et: