Four new proposals based on experiments with download size

5 files changed, 369 insertions, 0 deletions

diff --git a/proposals/000-index.txt b/proposals/000-index.txt
index 4e400c8..d3a4100 100644
--- a/proposals/000-index.txt
+++ b/proposals/000-index.txt
@@ -194,6 +194,10 @@ Proposals by number:
 271  Another algorithm for guard selection [CLOSED]
 272  Listed routers should be Valid, Running, and treated as such [FINISHED]
 273  Exit relay pinning for web services [DRAFT]
+274  Rotate onion keys less frequently [OPEN]
+275  Stop including meaningful "published" time in microdescriptor consensus [OPEN]
+276  Report bandwidth with lower granularity in consensus documents [OPEN]
+277  Detect multiple relay instances running with same ID [OPEN]
 
 
 Proposals by status:
@@ -249,6 +253,10 @@ Proposals by status:
    256  Key revocation for relays and authorities
    261  AEZ for relay cryptography
    262  Re-keying live circuits with new cryptographic material
+   274  Rotate onion keys less frequently [for 0.3.1.x-alpha]
+   275  Stop including meaningful "published" time in microdescriptor consensus [for 0.3.1.x-alpha]
+   276  Report bandwidth with lower granularity in consensus documents [for 0.3.1.x-alpha]
+   277  Detect multiple relay instances running with same ID [for 0.3.??]
  ACCEPTED:
    140  Provide diffs between consensuses
    172  GETINFO controller option for circuit information
diff --git a/proposals/274-rotate-onion-keys-less.txt b/proposals/274-rotate-onion-keys-less.txt
new file mode 100644
index 0000000..0d61d5d
--- /dev/null
+++ b/proposals/274-rotate-onion-keys-less.txt
@@ -0,0 +1,113 @@
+Filename: 274-rotate-onion-keys-less.txt
+Title: Rotate onion keys less frequently.
+Author: Nick Mathewson
+Created: 20-Feb-2017
+Status: Open
+Target: 0.3.1.x-alpha
+
+1. Overview
+
+   This document proposes that, in order to limit the bandwidth needed
+   for microdescriptor listing and transmission, we reduce the onion key
+   rotation rate from the current value (7 days) to something closer to
+   28 days.
+
+   Doing this will reduce the total microdescriptor download volume
+   by approximately 70%.
+
+2. Motivation
+
+   Currently, clients must download a networkstatus consensus document
+   once an hour, and must download every unfamiliar microdescriptor
+   listed in that document.  Therefore, we can reduce client directory
+   bandwidth if we can cause microdescriptors to change less often.
+
+   Furthermore, we are planning (in proposal 140) to implement a
+   diff-based mechanism for clients to download only the parts of each
+   consensus that have changed.  If we do that, then by having the
+   microdescriptor for each router change less often, we can make these
+   consensus diffs smaller as well.
+
+3. Analysis
+
+   I analyzed microdescriptor changes over the month of January
+   2017, and found that 94.5% of all microdescriptor transitions
+   were changes in onion key alone.
+
+   Therefore, we could reduce the number of changed "m" lines in
+   consensus diffs by approximately 94.5% * (3/4) =~ 70%,
+   if we were to rotate onion keys one-fourth as often.
+
+   The number of microdescriptors to actually download should
+   decrease by a similar number.
+
+   This amount to a significant reduction: currently, by
+   back-of-the-envelope estimates, an always-on client that downloads
+   all the directory info in a month downloads about 449MB of compressed
+   consensuses and something around 97 MB of compressed
+   microdescriptors.  This proposal would save that user about 12% of
+   their total directory bandwidth.
+
+   If we assume that consensus diffs are implemented (see proposal 140),
+   then the user's compressed consensus downloads fall to something
+   closer to 27 MB.  Under that analysis, the microdescriptors will
+   dominate again at 97 MB -- so lowering the number of microdescriptors
+   to fetch would save more like 55% of the remaining bandwidth.
+
+   [Back-of-the-envelope technique: assume every consensus is
+   downloaded, and every microdesc is downloaded, and microdescs are
+   downloaded in groups of 61, which works out to a constant rate.]
+
+   We'll need to do more analysis to assess the impact on clients that
+   connect to the network infrequently enough to miss microdescriptors:
+   nonetheless, the 70% figure above ought to apply to clients that connect
+   at least weekly.
+
+   (XXXX Better results pending feedback from ahf's analysis.)
+
+4. Security analysis
+
+   The onion key is used to authenticate a relay to a client when the
+   client is building a circuit through that relay.  The only reason to
+   limit their lifetime is to limit the impact if an attacker steals an
+   onion key without being detected.
+
+   If an attacker steals an onion key and is detected, the relay can
+   issue a new onion key ahead of schedule, with little disruption.
+
+   But if the onion key theft is _not_ detected, then the attacker
+   can use that onion key to impersonate the relay until clients
+   start using the relay's next key.  In order to do so, the
+   attacker must also impersonate the target relay at the link
+   layer: either by stealing the relay's link keys, which rotate
+   more frequently, or by compromising the previous relay in the
+   circuit.
+
+   Therefore, onion key rotation provides a small amount of
+   protection only against an attacker who can compromise relay keys
+   very intermittently, and who controls only a small portion of the
+   network.  Against an attacker who can steal keys regularly it
+   does little, and an attacker who controls a lot of the network
+   can already mount other attacks.
+
+5. Proposal
+
+   I propose that we move the default onion key rotation interval
+   from 7 days to 28 days, as follows.
+
+   There should be a new consensus parameter, "onion-key-rotation-days",
+   measuring the key lifetime in days.  Its minimum should be 1, its
+   maximum should be 90, and its default should be 28.
+
+   There should also be a new consensus parameter,
+   "onion-key-grace-period-days", measuring the interval for which
+   older onion keys should still be accepted.  Its minimum should be
+   1, its maximum should be onion-key-rotation-days, and its default
+   should be 7.
+
+   Every relay should list each onion key it generates for
+   onion-key-rotation-days days after generating it, and then
+   replace it.  Relays should continue to accept their most recent
+   previous onion key for an additional onion-key-rotation-days days
+   after it is replaced.
+
diff --git a/proposals/275-md-published-time-is-silly.txt b/proposals/275-md-published-time-is-silly.txt
new file mode 100644
index 0000000..b23e747
--- /dev/null
+++ b/proposals/275-md-published-time-is-silly.txt
@@ -0,0 +1,119 @@
+Filename: 275-md-published-time-is-silly.txt
+Title: Stop including meaningful "published" time in microdescriptor consensus
+Author: Nick Mathewson
+Created: 20-Feb-2017
+Status: Open
+Target: 0.3.1.x-alpha
+
+1. Overview
+
+   This document proposes that, in order to limit the bandwidth needed
+   for networkstatus diffs, we remove "published" part of the "r" lines
+   in microdescriptor consensuses.
+
+   The more extreme, compatibility-breaking version of this idea will
+   reduce ed consensus diff download volume by approximately 55-75%.  A
+   less-extreme interim version would still reduce volume by
+   approximately 5-6%.
+
+2. Motivation
+
+   The current microdescriptor consensus "r" line format is:
+     r Nickname Identity Published IP ORPort DirPort
+   as in:
+     r moria1 lpXfw1/+uGEym58asExGOXAgzjE 2017-01-10 07:59:25 \
+        128.31.0.34 9101 9131
+
+   As I'll show below, there's not much use for the "Published" part
+   of these lines.  By omitting them or replacing them with
+   something more compressible, we can save space.
+
+   What's more, changes in the Published field are one of the most
+   frequent changes between successive networkstatus consensus
+   documents.  If we were to remove this field, then networkstatus diffs
+   (see proposal 140) would be smaller.
+
+3. Compatibility notes
+
+   Above I've talked about "removing" the published field.  But of
+   course, doing this would make all existing consensus consumers
+   stop parsing the consensus successfully.
+
+   Instead, let's look at how this field is used currently in Tor,
+   and see if we can replace the value with something else.
+
+      * Published is used in the voting process to decide which
+        descriptor should be considered.  But that is takend from
+        vote networkstatus documents, not consensuses.
+
+      * Published is used in mark_my_descriptor_dirty_if_too_old()
+        to decide whether to upload a new router descriptor.  If the
+        published time in the consensus is more than 18 hours in the
+        past, we upload a new descriptor.  (Relays are potentially
+        looking at the microdesc consensus now, since #6769 was
+        merged in 0.3.0.1-alpha.)  Relays have plenty of other ways
+        to notice that they should upload new descriptors.
+
+      * Published is used in client_would_use_router() to decide
+        whether a routerstatus is one that we might possibly use.
+        We say that a routerstatus is not usable if its published
+        time is more than OLD_ROUTER_DESC_MAX_AGE (5 days) in the
+        past, or if it is not at least
+        TestingEstimatedDescriptorPropagationTime (10 minutes) in
+        the future. [***] Note that this is the only case where anything
+        is rejected because it comes from the future.
+
+          * client_would_use_router() decides whether we should
+            download a router descriptor (not a microdescriptor)
+            in routerlist.c
+
+          * client_would_use_router() is used from
+            count_usable_descriptors() to decide which relays are
+            potentially usable, thereby forming the denominator of
+            our "have descriptors / usable relays" fraction.
+
+   So we have a fairly limited constraints on which Published values
+   we can safely advertize with today's Tor implementations.  If we
+   advertise anything more than 10 minutes in the future,
+   client_would_use_router() will consider routerstatuses unusable.
+   If we advertize anything more than 18 hours in the past, relays
+   will upload their descriptors far too often.
+
+4. Proposal
+
+   Immediately, in 0.2.9.x-stable (our LTS release series), we
+   should stop caring about published_on dates in the future.  This
+   is a two-line change.
+
+   As an interim solution: We should add a new consensus method number
+   that changes the process by which Published fields in consensuses are
+   generated.  It should set all all Published fields in the consensus
+   should be the same value.  These fields should be taken to rotate
+   every 15 hours, by taking consensus valid-after time, and rounding
+   down to the nearest multiple of 15 hours since the epoch.
+
+   As a longer-term solution: Once all Tor versions earlier than 0.2.9.x
+   are obsolete (in mid 2018), we can update with a new consensus
+   method, and set the published_on date to some safe time in the
+   future.
+
+5. Analysis
+
+   To consider the impact on consensus diffs: I analyzed consensus
+   changes over the month of January 2017, using scripts at [1].
+
+   With the interim solution in place, compressed diff sizes fell by
+   2-7% at all measured intervals except 12 hours, where they increased
+   by about 4%.  Savings of 5-6% were most typical.
+
+   With the longer-term solution in place, and all published times held
+   constant permanently, the compressed diff sizes were uniformly at
+   least 56% smaller.
+
+   With this in mind, I think we might want to only plan to support the
+   longer-term solution.
+
+    [1] https://github.com/nmathewson/consensus-diff-analysis
+
+
+
diff --git a/proposals/276-lower-bw-granularity.txt b/proposals/276-lower-bw-granularity.txt
new file mode 100644
index 0000000..4d3735c
--- /dev/null
+++ b/proposals/276-lower-bw-granularity.txt
@@ -0,0 +1,70 @@
+Filename: 276-lower-bw-granularity.txt
+Title: Report bandwidth with lower granularity in consensus documents
+Author: Nick Mathewson
+Created: 20-Feb-2017
+Status: Open
+Target: 0.3.1.x-alpha
+
+1. Overview
+
+   This document proposes that, in order to limit the bandwidth needed for
+   networkstatus diffs, we lower the granularity with which bandwidth is
+   reported in consensus documents.
+
+   Making this change will reduce the total compressed ed diff download
+   volume by around 10%.
+
+2. Motivation
+
+   Consensus documents currently report bandwidth values as the median
+   of the measured bandwidth values in the votes.  (Or as the median of
+   all votes' values if there are not enough measurements.)  And when
+   voting, in turn, authorities simply report whatever measured value
+   they most recently encountered, clipped to 3 significant base-10
+   figures.
+
+   This means that, from one consensus to the next, these weights very
+   often and with little significance:  A large fraction of bandwidth
+   transitions are under 2% in magnitude.
+
+   As we begin to use consensus diffs, each change will take space to
+   transmit.  So lowering the amount of changes will lower client
+   bandwidth requirements significantly.
+
+3. Proposal
+
+   I propose that we round the bandwidth values as they are placed in
+   the votes to two no more than significant digits.  In addition, for
+   values beginning with decimal "2" through "4", we should round the
+   first two digits the nearest multiple of 2.  For values beginning
+   with decimal "5" though "9", we should round to the nearest multiple
+   of 5.
+
+   This change does not require a consensus method; it will take effect
+   once enough authorities have upgraded.
+
+4. Analysis
+
+   The rounding proposed above will not round any value by more than
+   5%, so the overall impact on bandwidth balancing should be small.
+
+   In order to assess the bandwidth savings of this approach, I
+   smoothed the January 2017 consensus documents' Bandwidth fields,
+   using scripts from [1].  I found that if clients download
+   consensus diffs once an hour, they can expect 11-13% mean savings
+   after xz or gz compression.  For two-hour intervals, the savings
+   is 8-10%; for three-hour or four-hour intervals, the savings only
+   is 6-8%.  After that point, we start seeing diminishing returns,
+   with only 1-2% savings on a 72-hour interval's diff.
+
+    [1] https://github.com/nmathewson/consensus-diff-analysis
+
+5. Open questions:
+
+   Is there a greedier smoothing algorithm that would produce better
+   results?
+
+   Is there any reason to think this amount of smoothing would not
+   be save?
+
+   Would a time-aware smoothing mechanism work better?
diff --git a/proposals/277-detect-id-sharing.txt b/proposals/277-detect-id-sharing.txt
new file mode 100644
index 0000000..dee7f6e
--- /dev/null
+++ b/proposals/277-detect-id-sharing.txt
@@ -0,0 +1,59 @@
+Filename: 277-detect-id-sharing.txt
+Title: Detect multiple relay instances running with same ID.
+Author: Nick Mathewson
+Created: 20-Feb-2017
+Status: Open
+Target: 0.3.??
+
+1. Overview
+
+   This document proposes that we detect multiple relay instances running
+   with the same ID, and block them all, or block all but one of each.
+
+2. Motivation
+
+   While analyzing microdescriptor and relay status transitions (see
+   proposal XXXX), I found that something like 16/10631 router
+   identities from January 2017 were apparently shared by two or
+   more relays, based on their excessive number of onion key
+   transitions.  This is probably accidental: and if intentional,
+   it's probably not achieving whatever the relay operators
+   intended.
+
+   Sharing identities causes all the relays in question to "flip" back
+   and forth onto the network, depending on which one uploaded its
+   descriptor most recently.  One relay's address will be listed; and
+   so will that relay's onion key.  Routers connected to one of the
+   other relays will believe its identity, but be suspicious of its
+   address.  Attempts to extend to the relay will fail because of the
+   incorrect onion key.  No more than one of the relays' bandwidths will
+   actually get significant use.
+
+   So clearly, it would be best to prevent this.
+
+3. Proposal 1: relay-side detection
+
+   Relays should themselves try to detect whether another relay is using
+   its identity.  If a relay, while running, finds that it is listed in
+   a fresh consensus using an onion key other than its current or
+   previous onion key, it should tell its operator about the problem.
+
+   (This proposal borrows from Mike Perry's ideas related to key theft
+   detection.)
+
+4. Proposal 2: offline detection
+
+   Any relay that has a large number of onion-key transitions over time,
+   but only a small number of distinct onion keys, is probably two or
+   more relays in conflict with one another.
+
+   In this case, the operators can be contacted, or the relay
+   blacklisted.
+
+   We could build support for blacklisting all but one of the addresses,
+   but it's probably best to treat this as a misconfiguratino serious
+   enough that it needs to be resolved.
+
+
+
+