commit 4f8d5a4b24741680c231a99f2f1af9172bf126e5
Author: Nick Mathewson <nickm(a)torproject.org>
Date: Wed May 27 15:12:01 2020 -0400
Add proposals 321 and 322 for walking-onions-related stuff
---
proposals/000-index.txt | 4 +
proposals/321-happy-families.md | 231 ++++++++++++++++++++++++++++++++++++++
proposals/322-dirport-linkspec.md | 41 +++++++
3 files changed, 276 insertions(+)
diff --git a/proposals/000-index.txt b/proposals/000-index.txt
index 3374a26..512f64f 100644
--- a/proposals/000-index.txt
+++ b/proposals/000-index.txt
@@ -241,6 +241,8 @@ Proposals by number:
318 Limit protover values to 0-63 [OPEN]
319 RELAY_FRAGMENT cells [OPEN]
320 Removing TAP usage from v2 onion services [OPEN]
+321 Better performance and usability for the MyFamily option (v2) [OPEN]
+322 Extending link specifiers to include the directory port [OPEN]
Proposals by status:
@@ -287,6 +289,8 @@ Proposals by status:
318 Limit protover values to 0-63
319 RELAY_FRAGMENT cells
320 Removing TAP usage from v2 onion services
+ 321 Better performance and usability for the MyFamily option (v2)
+ 322 Extending link specifiers to include the directory port
ACCEPTED:
188 Bridge Guards and other anti-enumeration defenses
249 Allow CREATE cells with >505 bytes of handshake data
diff --git a/proposals/321-happy-families.md b/proposals/321-happy-families.md
new file mode 100644
index 0000000..288ba66
--- /dev/null
+++ b/proposals/321-happy-families.md
@@ -0,0 +1,231 @@
+```
+Filename: 321-happy-families.md
+Title: Better performance and usability for the MyFamily option (v2)
+Author: Nick Mathewson
+Created: 27 May 2020
+Status: Open
+```
+
+## Problem statement.
+
+The current family mechanism allows well-behaved relays to
+identify that they all belong to the same 'family', and should
+not be used in the same circuits.
+
+Right now, families work by having every family member list every
+other family member in its server descriptor. This winds up using
+O(n^2) space in microdescriptors and server descriptors. (For RAM,
+we can de-duplicate families which sometimes helps.) Adding or
+removing a server from the family requires all the other servers to
+change their torrc settings.
+
+The is growth in size is not just a theoretical problem. Family
+declarations currently make up a little over 55% of the
+microdescriptors in the directory--around 24% after compression.
+The largest family has around 270 members. With Walking Onions, 270
+members times a 160-bit hashed identifier leads to over 5 kilobytes
+per SNIP, which is much greater than we'd want to use.
+
+This is an updated version of proposal 242. It differs by clarifying
+requirements and providing a more detailed migration plan.
+
+## Design overview.
+
+In this design, every family has a master ed25519 "family key". A node
+is in the family iff its server descriptor includes a certificate of its
+ed25519 identity key with the family key. The certificate
+format the one in the tor-certs.txt spec; we would allocate a new
+certificate type for this usage. These certificates would need to
+include the signing key in the appropriate extension.
+
+Note that because server descriptors are signed with the node's
+ed25519 signing key, this creates a bidirectional relationship
+between the two keys, so that nodes can't be put in families without
+their consent.
+
+## Changes to router descriptors
+
+We add a new entry to server descriptors:
+
+ "family-cert" NL
+ "-----BEGIN FAMILY CERT-----" NL
+ cert
+ "-----END FAMILY CERT-----".
+
+This entry contains a base64-encoded certificate as described
+above. It may appear any number of times; authorities MAY reject
+descriptors that include it more than three times.
+
+## Changes to microdescriptors
+
+We add a new entry to microdescriptors: `family-keys`.
+
+This line contains one or more space-separated strings describing
+families to which the node belongs. These strings MUST be sorted in
+lexicographic order. Clients MUST NOT depend on any particular property
+of these strings.
+
+## Changes to voting algorithm
+
+We allocate a new consensus method number for voting on these keys.
+
+When generating microdescriptors using a suitable consensus method,
+the authorities include a "family-keys" line if the underlying
+server descriptor contains any valid family-cert lines. For each
+valid family-cert in the server descriptor, they add a
+base-64-encoded string of that family-cert's signing key.
+
+> See also "deriving family lines from family-keys?" below for an
+> interesting but more difficult extension mechanism that I would
+> not recommend.
+
+## Relay configuration
+
+There are several ways that we could configure relays to let them
+include family certificates in their descriptors.
+
+The easiest would be putting the private family key on each relay,
+so that the relays could generate their own certificates. This is
+easy to configure, but slightly risky: if the private key is
+compromised on any relay, anybody can claim membership in the
+family. That isn't so very bad, however -- all the relays would
+need to do in this event would be to move to a new private family
+key.
+
+A more orthodox method would be to keep the private key somewhere
+offline, and using it to generate a certificate for each relay in
+the family as needed. These certificates should be made with
+long-enough lifetimes, and relays should warn when they are going to
+expire soon.
+
+## Changes to relay behavior
+
+Each relay should track which other relays they have seen using the
+same family-key as itself. When generating a router descriptor,
+each relay should list all of these relays on the legacy 'family'
+line. This keeps the "family" lines up-to-date with "family-keys"
+lines for compliant relays.
+
+Relays should continue listing relays in their family lines if they
+have seen a relay with that identity using the same family-key at
+any time in the last 7 days.
+
+The presence of this line should be configured by a network
+parameter, `derive-family-line`.
+
+Relays whose family lines do not stay at least mostly in sync with
+their family keys should be marked invalid by the authorities.
+
+## Client behavior
+
+Clients should treat node A and node B as belonging to the same
+family if ANY of these is true:
+
+* The client has descriptors for A and B, and A's descriptor lists B
+ in its family line, and B's descriptor lists A in its family line.
+
+* Client A has descriptors for A and B, and they both contain the
+ same entry in their family-keys or family-cert.
+
+## Migration
+
+For some time, existing relays and clients will not support family
+certificates. Because of this, we try to make sure above the
+well-behaved relays will list the same entries in both places.
+
+Once enough clients have migrated to using family
+certificates, authorities SHOULD disable `derive-family-line`.
+
+## Security
+
+Listing families remains as voluntary in this design as in today's
+Tor, though bad-relay hunters can continue to look for families that
+have not adopted a family key.
+
+A hostile relay family could list a "family" line that did not match
+its "family-certs" values. However, the only reason to do so would
+be in order to launch a client partitioning attack, which is
+probably less valuable than the kinds of attacks that they could run
+by simply not listing families at all.
+
+## Appendix: deriving family lines from family-keys?
+
+As an alternative, we might declare that _authorities_ should keep
+family lines in sync with family-certs. Here is a design sketch of
+how we might do that, but I don't think it's actually a good idea,
+since it would require major changes to the data flow of the
+voting system.
+
+In this design, authorties would include a "family-keys" line in
+each router section in their votes corresponding to a relay with any
+family-cert. When generating final microdescriptors using this
+method, the authorities would use these lines to add entries to the
+microdescriptors' family lines:
+
+1. For every relay appearing in a routerstatus's family-keys, the
+ relays calculate a consensus family-keys value by listing including
+ all those keys that are listed by a majority of those voters listing
+ the same router with the same descriptor. (This is the algorithm we
+ use for voting on other values derived from the descriptor.)
+
+2. The authorities then compute a set of "expanded families": one
+ for each family key. Each "expanded family" is a set containing
+ every router in the consensus associated with that key in its consensus
+ family-keys value.
+
+3. The authorities discard all "expanded families" of size 1 or
+ smaller.
+
+4. Every router listed for the "expanded family" has every other
+ router added to the "family" line in its microdescriptor. (The
+ "family" line is then re-canonicalized according to the rules of
+ proposal 298 to remove its )
+
+5. Note that the final microdescriptor consensus will include the
+ digest of the derived microdescriptor in step 4, rather than the
+ digest of the microdescriptor listed in the original votes. (This
+ calculation is deterministic.)
+
+The problem with this approach is that authorities would have to s
+to fetch microdescriptors they do not have in order to replace their
+family lines. Currently, voting never requires an authority to
+fetch a microdescriptor from another authority. If we implement
+vote compression and diffs as in the Walking Onions proposal,
+however, we might suppose that votes could include microdescriptors
+directly.
+
+Still, this is likely more complexity than we want for a transition
+mechanism.
+
+## Appendix: Deriving family-keys from families??
+
+We might also imagine that authorities could infer which families
+exist from the graph of family relationships, and then include
+synthetic "family-keys" entries for routers that belong to the same
+family.
+
+This has two challenges: first, to compute these synthetic family
+keys, the authorities would need to have the same graph of family
+relationships to begin with, which once again would require them to
+include the complete list of families in their votes.
+
+Secondly, finding all the families is equivalent to finding all
+maximal cliques in a graph. This problem is NP-hard in its general
+case. Although polynomial solutions exist for nice well-behaved
+graphs, we'd still need to worry about hostile relays including
+strange family relationships in order to drive the algorithm into
+its exponential cases.
+
+## Appendix: New assigned values
+
+We need a new assigned value for the certificate type used for
+family signing keys.
+
+We need a new consensus method for placing family-keys lines in
+microdescriptors.
+
+## Appendix: New network parameters
+
+* `derive-family-line`: If 1, relays should derive family lines from
+ observed family-keys. If 0, they do not. Min: 0, Max: 1. Default: 1.
+
diff --git a/proposals/322-dirport-linkspec.md b/proposals/322-dirport-linkspec.md
new file mode 100644
index 0000000..5fd42ac
--- /dev/null
+++ b/proposals/322-dirport-linkspec.md
@@ -0,0 +1,41 @@
+```
+Filename: 322-dirport-linkspec.md
+Title: Extending link specifiers to include the directory port
+Author: Nick Mathewson
+Created: 27 May 2020
+Status: Open
+```
+
+## Motivation
+
+Directory ports remain the only way to contact a (non-bridge) Tor
+relay that isn't expressible as a Link Specifier. We haven't
+specified a link specifier of this kind so far, since it isn't a way
+to contact a relay to create a channel.
+
+But authorities still expose directory ports, and encourage relays
+to use them preferentially for uploading and downloading. And with
+Walking Onions, it would be convenient to try to make every kind of
+"address" a link specifier -- we'd like want authorities to be able
+to specify a list of link specifiers that can be used to contact
+them for uploads and downloads.
+
+> It is possible that after revision, Walking Onions won't need a way
+> to specify this information. If so, this proposal should be moved
+> to "Reserve" status as generally unuseful.
+
+## Proposal
+
+We reserve a new link specifier type "dir-url", for use with the
+directory system. This is a variable-length link specifier, containing
+a URL prefix. The only currently supported URL schema is "http://".
+Implementations SHOULD ignore unrecognized schemas. IPv4 and IPv6
+addresses MAY be used directory; hostnames are also allowed.
+Implementations MAY ignore hostnames and only use raw addresses.
+
+The URL prefix includes everything through the string "tor" in the
+directory hierarchy.
+
+A dir-url link specifier SHOULD NOT appear in an EXTEND cell;
+implementations SHOULD reject them if they do appear.
+
