doc/spec/proposals/140-consensus-diffs.txt

   1 Filename: 140-consensus-diffs.txt
   2 Title: Provide diffs between consensuses
   3 Version: $Revision$
   4 Last-Modified: $Date$
   5 Author: Peter Palfrader
   6 Created: 13-Jun-2008
   7 Status: Accepted
   8 Target: 0.2.1.x
   9
  10 1. Overview.
  11
  12   Tor clients and servers need a list of which relays are on the
  13   network.  This list, the consensus, is created by authorities
  14   hourly and clients fetch a copy of it, with some delay, hourly.
  15
  16   This proposal suggests that clients download diffs of consensuses
  17   once they have a consensus instead of hourly downloading a full
  18   consensus.
  19
  20 2. Numbers
  21
  22   After implementing proposal 138 which removes nodes that are not
  23   running from the list a consensus document is about 92 kilobytes
  24   in size after compression.
  25
  26   The diff between two consecutive consensus, in ed format, is on
  27   average 13 kilobytes compressed.
  28
  29 3. Proposal
  30
  31 3.1 Clients
  32
  33   If a client has a consensus that is recent enough it SHOULD
  34   try to download a diff to get the latest consensus rather than
  35   fetching a full one.
  36
  37   [XXX: what is recent enough?
  38         time delta in hours / size of compressed diff
  39          0      20
  40          1      9650
  41          2      17011
  42          3      23150
  43          4      29813
  44          5      36079
  45          6      39455
  46          7      43903
  47          8      48907
  48          9      54549
  49         10      60057
  50         11      67810
  51         12      71171
  52         13      73863
  53         14      76048
  54         15      80031
  55         16      84686
  56         17      89862
  57         18      94760
  58         19      94868
  59         20      94223
  60         21      93921
  61         22      92144
  62         23      90228
  63         [ size of gzip compressed "diff -e" between the consensus on
  64           2008-06-01-00:00:00 and the following consensuses that day.
  65           Consensuses have been modified to exclude down routers per
  66           proposal 138. ]
  67
  68    Data suggests that for the first few hours diffs are very useful,
  69    saving about 60% for the first three hours, 30% for the first 10,
  70    and almost nothing once we are past 16 hours.
  71   ]
  72
  73 3.2 Servers
  74
  75   Directory authorities and servers need to keep up to X [XXX: depends
  76   on how long clients try to download diffs per above] old consensus
  77   documents so they can build diffs.  They should offer a diff to the
  78   most recent consensus at the URL
  79
  80   http://tor.noreply.org/tor/status-vote/current/consensus/diff/<HASH>/<FPRLIST>
  81
  82   where hash is the full digest of the consensus the client currently
  83   has, and FPRLIST is a list of (abbreviated) fingerprints of
  84   authorities the client trusts.
  85
  86   Servers will only return a consensus if more than half of the requested
  87   authorities have signed the document, otherwise a 404 error will be sent
  88   back.  The fingerprints can be shortened to a length of any multiple of
  89   two, using only the leftmost part of the encoded fingerprint.  Tor uses
  90   3 bytes (6 hex characters) of the fingerprint.  (This is just like the
  91   conditional consensus downloads that Tor supports starting with
  92   0.1.2.1-alpha.)
  93
  94   If a server cannot offer a diff from the consensus identified by the
  95   hash but has a current consensus it MUST return the full consensus.
  96
  97   [XXX: what should we do when the client already has the latest
  98   consensus?  I can think of the following options:
  99     - send back 3xx not modified
 100     - send back 200 ok and an empty diff
 101     - send back 404 nothing newer here.
 102
 103     I currently lean towards the empty diff.]
 104
 105 4. Diff Format
 106
 107   Diffs start with the token "network-status-diff-version" followed by a
 108   space and the version number, currently "1".
 109
 110   If a document does not start with network-status-diff it is assumed
 111   to be a full consensus download and would therefore currently start
 112   with "network-status-version 3".
 113
 114   Following the network-status-diff header line is a diff, or patch, in
 115   limited ed format.  We choose this format because it is easy to create
 116   and process with standard tools (patch, diff -e, ed).  This will help
 117   us in developing and testing this proposal and it should make future
 118   debugging easier.
 119
 120   [ If at one point in the future we decide that the space benefits from
 121     a custom diff format outweighs these benefits we can always
 122     introduce a new diff format and offer it at for instance
 123     ../diff2/... ]
 124
 125   We support the following ed commands, each on a line by itself:
 126    - "<n1>d"          Delete line n1
 127    - "<n1>,<n2>d"     Delete lines n1 through n2, including
 128    - "<n1>c"          Replace line n1 with the following block
 129    - "<n1>,<n2>c"     Replace lines n1 through n2, including, with the
 130                       following block.
 131    - "<n1>a"          Append the following block after line n1.
 132    - "a"              Append the following block after the current line.
 133    - "s/.//"          Remove the first character in the current line.
 134
 135   Note that line numbers always apply to the file after all previous
 136   commands have already been applied.
 137
 138   The "current line" is either the first line of the file, if this is
 139   the first command, the last line of a block we added in an append or
 140   change command, or the line immediate following a set of lines we just
 141   deleted (or the last line of the file if there are no lines after
 142   that).
 143
 144   The replace and append command take blocks.  These blocks are simply
 145   appended to the diff after the line with the command.  A line with
 146   just a period (".") ends the block (and is not part of the lines
 147   to add).  Note that it is impossible to insert a line with just
 148   a single dot.  Recommended procedure is to insert a line with
 149   two dots, then remove the first character of that line using s/.//.