Proposal idea: Automatically promoting Tor clients to nodes

["Steven J. Murdoch" <tor+Steven.Murdoch@xxxxxxxxxxxx>]

I've been working recently on a proposal to increase the number of
bridges in the Tor network. It describes how Tor clients can
automatically become bridges, if they are considered to be
sufficiently reliable and the operator consents.

Comments and suggestions would be appreciated.

The current draft is below, and the latest version can be found here:

 https://gitweb.torproject.org//sjm217/tor.git?a=blob;f=doc/spec/proposals/ideas/xxx-automatic-node-promotion.txt;hb=xxx-automatic-node-promotion

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)

-- 
http://www.cl.cam.ac.uk/users/sjm217/