commit 87eefe8c537bdbab2a34394ee094338e862e9d69
Author: Nick Mathewson <nickm(a)torproject.org>
Date: Wed Jun 3 11:02:52 2020 -0400
Walking onions proposal is completed.
Or at least, the first version of it.
---
proposals/000-index.txt | 2 +
proposals/323-walking-onions-full.md | 4113 ++++++++++++++++++++++++++++++++++
2 files changed, 4115 insertions(+)
diff --git a/proposals/000-index.txt b/proposals/000-index.txt
index 512f64f..6e2e185 100644
--- a/proposals/000-index.txt
+++ b/proposals/000-index.txt
@@ -243,6 +243,7 @@ Proposals by number:
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]
+323 Specification for Walking Onions [DRAFT]
Proposals by status:
@@ -260,6 +261,7 @@ Proposals by status:
312 Tor Relay Automatic IPv6 Address Discovery
313 Tor Relay IPv6 Statistics
316 FlashFlow: A Secure Speed Test for Tor (Parent Proposal)
+ 323 Specification for Walking Onions
NEEDS-REVISION:
212 Increase Acceptable Consensus Age [for 0.2.4.x+]
219 Support for full DNS and DNSSEC resolution in Tor [for 0.2.5.x]
diff --git a/proposals/323-walking-onions-full.md b/proposals/323-walking-onions-full.md
new file mode 100644
index 0000000..d1c054d
--- /dev/null
+++ b/proposals/323-walking-onions-full.md
@@ -0,0 +1,4113 @@
+```
+Filename: 323-walking-onions-full.md
+Title: Specification for Walking Onions
+Author: Nick Mathewson
+Created: 3 June 2020
+Status: Draft
+```
+
+
+<!-- Section 1 --> <a id='S1'></a>
+
+# Introduction: A Specification for Walking Onions
+
+In Proposal 300, I introduced Walking Onions, a design for scaling
+Tor and simplifying clients, by removing the requirement that every
+client know about every relay on the network.
+
+This proposal will elaborate on the original Walking Onions idea,
+and should provide enough detail to allow multiple compatible
+implementations. In this introduction, I'll start by summarizing the
+key ideas of Walking Onions, and then outline how the rest of this
+proposal will be structured.
+
+<!-- Section 1.1 --> <a id='S1.1'></a>
+
+## Remind me about Walking Onions again?
+
+With Tor's current design, every client downloads and refreshes a
+set of directory documents that describe the directory authorities'
+views about every single relay on the Tor network. This requirement
+makes directory bandwidth usage grow quadratically, since the
+directory size grows linearly with the number of relays, and it is
+downloaded a number of times that grows linearly with the number of
+clients. Additionally, low-bandwidth clients and bootstrapping
+clients spend a disproportionate amount of their bandwidth loading
+directory information.
+
+With these drawbacks, why does Tor still require clients to
+download a directory? It does so in order to prevent attacks that
+would be possible if clients let somebody else choose their
+paths through the network, or if each client chose its paths from a
+different subset of relays.
+
+Walking Onions is a design that resists these attacks without
+requiring clients ever to have a complete view of the network.
+
+You can think of the Walking Onions design like this: Imagine that with
+the current Tor design, the client covers a wall with little pieces
+of paper, each representing a relay, and then throws a dart at the wall
+to pick a relay. Low-bandwidth relays get small pieces of paper;
+high-bandwidth relays get large pieces of paper. With the Walking
+Onions design, however, the client throws its dart at a _blank
+wall_, notes the position of the dart, and asks for the relay whose
+paper _would be_ at that position on a "standard wall". These
+"standard walls" are mapped out by directory authorities in advance,
+and are authenticated in such a way that the client can receive a
+proof of a relay's position on the wall without actually having to
+know the whole wall.
+
+Because the client itself picks the position on the wall, and
+because the authorities must vote together to build a set of
+"standard walls", nobody else controls the client's path through the
+network, and all clients can choose their paths in the same way.
+But since clients only probe one position on the wall at a time,
+they don't need to download a complete directory.
+
+(Note that there has to be more than one wall at a time: the client
+throws darts at one wall to pick guards, another wall to pick
+middle relays, and so on.)
+
+In Walking Onions, we call a collection of standard walls an
+"ENDIVE" (Efficient Network Directory with Individually Verifiable
+Entries). We call each of the individual walls a "routing index",
+and we call each of the little pieces of paper describing a relay and
+its position within the routing index a "SNIP" (Separable Network
+Index Proof).
+
+For more details about the key ideas behind Walking Onions, see
+proposal 300. For more detailed analysis and discussion, see
+"Walking Onions: Scaling Anonymity Networks while Protecting Users"
+by Komlo, Mathewson, and Goldberg.
+
+<!-- Section 1.2 --> <a id='S1.2'></a>
+
+## The rest of this document
+
+This proposal is unusually long, since Walking Onions touches on many
+aspects of Tor's functionality. It requires changes to voting,
+directory formats, directory operations, circuit building, path
+selection, client operations, and more. These changes are described in the
+sections listed below.
+
+Here in section 1, we briefly reintroduce Walking Onions, and talk
+about the rest of this proposal.
+
+Section 2 will describe the formats for ENDIVEs, SNIPs, and related
+documents.
+
+Section 3 will describe new behavior for directory authorities as
+they vote on and produce ENDIVEs.
+
+Section 4 describes how relays fetch and reconstruct ENDIVEs from
+the directory authorities.
+
+Section 5 has the necessary changes to Tor's circuit extension
+protocol so that clients can extend to relays by index position.
+
+Section 6 describes new behaviors for clients as they use Walking
+Onions, to retain existing Tor functionality for circuit construction.
+
+Section 7 explains how to implement onion services using Walking
+Onions.
+
+Section 8 describes small alterations in client and relay behavior
+to strengthen clients against some kinds of attacks based on relays
+picking among multiple ENDIVEs, while still making the voting
+system robust against transient authority failures.
+
+Section 9 closes with a discussion of how to migrate from the
+existing Tor design to the new system proposed here.
+
+<!-- Section 1.2.1 --> <a id='S1.2.1'></a>
+
+### Appendices
+
+Additionally, this proposal has several appendices:
+
+Appendix A defines commonly used terms.
+
+Appendix B provides definitions for CDDL grammar productions that
+are used elsewhere in the documents.
+
+Appendix C lists the new elements in the protocol that will require
+assigned values.
+
+Appendix D lists new network parameters that authorities must vote
+on.
+
+Appendix E gives a sorting algorithm for a subset of the CBOR object
+representation.
+
+Appendix F gives an example set of possible "voting rules" that
+authorities could use to produce an ENDIVE.
+
+Appendix G lists the different routing indices that will be required
+in a Walking Onions deployment.
+
+Appendix H discusses partitioning TCP ports into a small number of
+subsets, so that relays' exit policies can be represented only as
+the group of ports that they support.
+
+Appendix Z closes with acknowledgments.
+
+<!-- Section 1.2.2 --> <a id='S1.2.2'></a>
+
+### Related proposals
+
+The following proposals are not part of the Walking Onions proposal,
+but they were written at the same time, and are either helpful or
+necessary for its implementation.
+
+318-limit-protovers.md restricts the allowed version numbers for
+each subprotocol to the range 0..63.
+
+319-wide-everything.md gives a general mechanism for splitting relay
+commands across more than one cell.
+
+320-tap-out-again.md attempts to remove the need for TAP keys in
+the HSv2 protocol.
+
+321-happy-families.md lets families be represented with a single
+identifier, rather than a long list of keys
+
+322-dirport-linkspec.md allows a directory port to be represented
+with a link specifier.
+
+<!-- Section 2 --> <a id='S2'></a>
+
+# Document Formats: ENDIVEs and SNIPs
+
+Here we specify a pair of related document formats that we will
+use for specifying SNIPs and ENDIVEs.
+
+Recall from proposal 300 that a SNIP is a set of information about
+a single relay, plus proof from the directory authorities that the
+given relay occupies a given range in a certain routing index.
+For example, we can imagine that a SNIP might say:
+
+* Relay X has the following IP, port, and onion key.
+* In the routing index Y, it occupies index positions 0x20002
+ through 0x23000.
+* This SNIP is valid on 2020-12-09 00:00:00, for one hour.
+* Here is a signature of all the above text, using a threshold
+ signature algorithm.
+
+You can think of a SNIP as a signed combination of a routerstatus and
+a microdescriptor... together with a little bit of the randomized
+routing table from Tor's current path selection code, all wrapped
+in a signature.
+
+Every relay keeps a set of SNIPs, and serves them to clients when
+the client is extending by a routing index position.
+
+An ENDIVE is a complete set of SNIPs. Relays download ENDIVEs, or
+diffs between ENDIVEs, once every voting period. We'll accept some
+complexity in order to make these diffs small, even though some of the
+information in them (particularly SNIP signatures and index
+ranges) will tend to change with every period.
+
+<!-- Section 2.1 --> <a id='S2.1'></a>
+
+## Preliminaries and scope
+
+<!-- Section 2.1.1 --> <a id='S2.1.1'></a>
+
+### Goals for our formats
+
+We want SNIPs to be small, since they need to be sent on the wire
+one at a time, and won't get much benefit from compression. (To
+avoid a side-channel, we want CREATED cells to all be the same
+size, which means we need to pad up to the largest size possible
+for a SNIP.)
+
+We want to place as few requirements on clients as possible, and we
+want to preserve forward compatibility.
+
+We want ENDIVEs to be compressible, and small. We want successive
+ENDIVEs to be textually similar, so that we can use diffs to
+transmit only the parts that change.
+
+We should preserve our policy of requiring only loose time
+synchronization between clients and relays, and allow even looser
+synchronization when possible. Where possible, we'll make the
+permitted skew explicit in the protocol: for example, rather than
+saying "you can accept a document 10 minutes before it is valid", we
+will just make the validity interval start 10 minutes earlier.
+
+<!-- Section 2.1.2 --> <a id='S2.1.2'></a>
+
+### Notes on Metaformat
+
+In the format descriptions below, we will describe a set of
+documents in the CBOR metaformat, as specified in RFC 7049. If
+you're not familiar with CBOR, you can think of it as a simple
+binary version of JSON, optimized first for simplicity of
+implementation and second for space.
+
+I've chosen CBOR because it's schema-free (you can parse it
+without knowing what it is), terse, dumpable as text, extensible,
+standardized, and very easy to parse and encode.
+
+We will choose to represent many size-critical types as maps whose
+keys are short integers: this is slightly shorter in its encoding
+than string-based dictionaries. In some cases, we make types even
+shorter by using arrays rather than maps, but only when we are
+confident we will not have to make changes to the number of elements
+in the future.
+
+We'll use CDDL (defined in RFC 8610) to describe the data in a way
+that can be validated -- and hopefully, in a way that will make it
+comprehensible. (The state of CDDL tooling is a bit lacking at the
+moment, so my CDDL validation will likely be imperfect.)
+
+We make the following restrictions to CBOR documents that Tor
+implementations will _generate_:
+
+ * No floating-point values are permitted.
+
+ * No tags are allowed unless otherwise specified.
+
+ * All items must follow the rules of RFC 7049 section 3.9 for
+ canonical encoding, unless otherwise specified.
+
+Implementations SHOULD accept and parse documents that are not
+generated according to these rules, for future extensibility.
+However, implementations SHOULD reject documents that are not
+"well-formed" and "valid" by the definitions of RFC 7049.
+
+<!-- Section 2.1.3 --> <a id='S2.1.3'></a>
+
+### Design overview: signing documents
+
+We try to use a single document-signing approach here, using a hash
+function parameterized to accommodate lifespan information and an
+optional nonce.
+
+All the signed CBOR data used in this format is represented as a
+binary string, so that CBOR-processing tools are less likely to
+re-encode or transform it. We denote this below with the CDDL syntax
+`bstr .cbor Object`, which means "a binary string that must hold a valid
+encoding of a CBOR object whose type is `Object`".
+
+<!-- Section 2.1.4 --> <a id='S2.1.4'></a>
+
+### Design overview: SNIP Authentication
+
+I'm going to specify a flexible authentication format for SNIPs that
+can handle threshold signatures, multisignatures, and Merkle trees.
+This will give us flexibility in our choice of authentication
+mechanism over time.
+
+ * If we use Merkle trees, we can make ENDIVE diffs much much smaller,
+ and save a bunch of authority CPU -- at the expense of requiring
+ slightly larger SNIPs.
+
+ * If Merkle tree root signatures are in SNIPs, SNIPs get a
+ bit larger, but they can be used by clients that do not have the
+ latest signed Merkle tree root.
+
+ * If we use threshold signatures, we need to depend on
+ not-yet-quite-standardized algorithms. If we use multisignatures,
+ then either SNIPs get bigger, or we need to put the signed Merkle
+ tree roots into a consensus document.
+
+Of course, flexibility in signature formats is risky, since the more
+code paths there are, the more opportunities there are for nasty bugs.
+With this in mind, I'm structuring our authentication so that there
+should (to the extent possible) be only a single validation path for
+different uses.
+
+With this in mind, our format is structured so that "not using a
+Merkle tree" is considered, from the client's point of view, the same as
+"using a Merkle of depth 1".
+
+The authentication on a single snip is structured, in the abstract, as:
+ - ITEM: The item to be authenticated.
+ - PATH: A string of N bits, representing a path through a Merkle tree from
+ its root, where 0 indicates a left branch and 1 indicates a right
+ branch. (Note that in a left-leaning tree, the 0th leaf will have
+ path 000..0, the 1st leaf will have path 000..1, and so on.)
+ - BRANCH: A list of N digests, representing the digests for the
+ branches in the Merkle tree that we are _not_ taking.
+ - SIG: A generalized signature (either a threshold signature or a
+ multisignature) of a top-level digest.
+ - NONCE: an optional nonce for use with the hash functions.
+
+Note that PATH here is a bitstring, not an integer! "0001" and "01" are
+different paths, and "" is a valid path, indicating the root of the tree.
+
+We assume two hash functions here: `H_leaf()` to be used with leaf
+items, and `H_node()` to be used with intermediate nodes. These functions
+are parameterized with a path through the tree, with
+the lifespan of the object to be signed, and with a nonce.
+
+To validate the authentication on a SNIP, the client proceeds as follows:
+
+ Algorithm: Validating SNIP authentication
+
+ Let N = the length of PATH, in bits.
+
+ Let H = H_leaf(PATH, LIFESPAN, NONCE, ITEM).
+
+ While N > 0:
+ Remove the last bit of PATH; call it P.
+ Remove the last digest of BRANCH; call it B.
+
+ If P is zero:
+ Let H = H_node(PATH, LIFESPAN, NONCE, H, B)
+ else:
+ Let H = H_node(PATH, LIFESPAN, NONCE, B, H)
+
+ Let N = N - 1
+
+ Check wither SIG is a correct (multi)signature over H with the
+ correct key(s).
+
+Parameterization on this structure is up to the authorities. If N is
+zero, then we are not using a Merkle tree. The generalize signature
+SIG can either be given as part of the SNIP, or as part of a consensus
+document. I expect that in practice, we will converge on a single set of
+parameters here quickly (I'm favoring BLS signatures and a Merkle
+tree), but using this format will give clients the flexibility to handle
+other variations in the future.
+
+For our definition of `H_leaf()` and `H_node()`, see "Digests and
+parameters" below.
+
+<!-- Section 2.1.5 --> <a id='S2.1.5'></a>
+
+### Design overview: timestamps and validity.
+
+For future-proofing, SNIPs and ENDIVEs have separate time ranges
+indicating when they are valid. Unlike with current designs, these
+validity ranges should take clock skew into account, and should not
+require clients or relays to deliberately add extra tolerance to their
+processing. (For example, instead of saying that a document is "fresh"
+for three hours and then telling clients to accept documents for 24
+hours before they are valid and 24 hours after they are expired, we will
+simply make the documents valid for 51 hours.)
+
+We give each lifespan as a (PUBLISHED, PRE, POST) triple, such that
+objects are valid from (PUBLISHED - PRE) through (PUBLISHED + POST).
+(The "PUBLISHED" time is provided so that we can more reliably tell
+which of two objects is more recent.)
+
+Later (see section 08), we'll explain measures to ensure that
+hostile relays do not take advantage of multiple overlapping SNIP
+lifetimes to attack clients.
+
+<!-- Section 2.1.6 --> <a id='S2.1.6'></a>
+
+### Design overview: how the formats work together
+
+Authorities, as part of their current voting process, will produce an
+ENDIVE.
+
+Relays will download this ENDIVE (either directly or as a diff),
+validate it, and extract SNIPs from it. Extracting these SNIPs may be
+trivial (if they are signed individually), or more complex (if they are
+signed via a Merkle tree, and the Merkle tree needs to be
+reconstructed). This complexity is acceptable only to the extent that
+it reduces compressed diff size.
+
+Once the SNIPs are reconstructed, relays will hold them and serve them
+to clients.
+
+<!-- Section 2.1.7 --> <a id='S2.1.7'></a>
+
+### What isn't in this section
+
+This section doesn't tell you what the different routing indices
+are or mean. For now, we can imagine there being one routing index for
+guards, one for middles, and one for exits, and one for each hidden
+service directory ring. (See section 06 for more on regular indices,
+and section 07 for more on onion services.)
+
+This section doesn't give an algorithm for computing ENDIVEs from
+votes, and doesn't give an algorithm for extracting SNIPs from an ENDIVE.
+Those come later. (See sections 03 and 04 respectively.)
+
+<!-- Section 2.2 --> <a id='S2.2'></a>
+
+## SNIPs
+
+Each SNIP has three pieces: the part of the SNIP that describes the
+router, the part of that describes the SNIP's place within an ENDIVE, and
+the part that authenticates the whole SNIP.
+
+Why two _separate_ authenticated pieces? Because one (the router
+description) is taken verbatim from the ENDIVE, and the other
+(the location within the ENDIVE) is computed from the ENDIVE by the
+relays. Separating them like this helps ensure that the part
+generated by the relay and the part generated by the authorities
+can't interfere with each other.
+
+ ; A SNIP, as it is sent from the relay to the client. Note that
+ ; this is represented as a three-element array.
+ SNIP = [
+ ; First comes the signature. This is computed over
+ ; the concatenation of the two bstr objects below.
+ auth: SNIPSignature,
+
+ ; Next comes the location of the SNIP within the ENDIVE.
+ index: bstr .cbor SNIPLocation,
+
+ ; Finally comes the information about the router.
+ router: bstr .cbor SNIPRouterData,
+ ]
+
+(Computing the signature over a concatenation of objects is safe, since
+the objects' content is self-describing CBOR, and isn't vulnerable to
+framing issues.)
+
+<!-- Section 2.2.1 --> <a id='S2.2.1'></a>
+
+### SNIPRouterData: information about a single router.
+
+Here we talk about the type that tells a client about a single
+router. For cases where we are just storing information about a
+router (for example, when using it as a guard), we can remember
+this part, and discard the other pieces.
+
+The only required parts here are those that identify the router
+and tell the client how to build a circuit through it. The others
+are all optional. In practice, I expect they will be encoded in most
+cases, but clients MUST behave properly if they are absent.
+
+More than one SNIPRouterData may exist in the same ENDIVE for a
+single router. For example, there might be a longer version to
+represent a router to be used as a guard, and another to represent
+the same router when used as a hidden service directory. (This is
+not possible in the voting mechanism that I'm working on, but relays
+and clients MUST NOT treat this as an error.)
+
+This representation is based on the routerstats and
+microdescriptor entries of today, but tries to omit a number of
+obsolete fields, including RSA identity fingerprint, TAP key,
+published time, etc.
+
+ ; A SNIPRouterData is a map from integer keys to values for
+ ; those keys.
+ SNIPRouterData = {
+ ; identity key.
+ ? 0 => Ed25519PublicKey,
+
+ ; ntor onion key.
+ ? 1 => Curve25519PublicKey,
+
+ ; list of link specifiers other than the identity key.
+ ; If a client wants to extend to the same router later on,
+ ; they SHOULD include all of these link specifiers verbatim,
+ ; whether they recognize them or not.
+ ? 2 => [ LinkSpecifier ],
+
+ ; The software that this relay says it is running.
+ ? 3 => SoftwareDescription,
+
+ ; protovers.
+ ? 4 => ProtoVersions,
+
+ ; Family. See below for notes on dual encoding.
+ ? 5 => [ * FamilyId ],
+
+ ; Country Code
+ ? 6 => Country,
+
+ ; Exit policies describing supported port _classes_. Absent exit
+ ; policies are treated as "deny all".
+ ? 7 => ExitPolicy,
+
+ ; NOTE: Properly speaking, there should be a CDDL 'cut'
+ ; here, to indicate that the rules below should only match
+ ; if one if the previous rules hasn't matched.
+ ; Unfortunately, my CDDL tool doesn't seem to support cuts.
+
+ ; For future tor extensions.
+ * int => any,
+
+ ; For unofficial and experimental extensions.
+ * tstr => any,
+ }
+
+ ; For future-proofing, we are allowing multiple ways to encode
+ ; families. One is as a list of other relays that are in your
+ ; family. One is as a list of authority-generated family
+ ; identifiers. And one is as a master key for a family (as in
+ ; Tor proposal 242).
+ ;
+ ; A client should consider two routers to be in the same
+ ; family if they have at least one FamilyId in common.
+ ; Authorities will canonicalize these lists.
+ FamilyId = bstr
+
+ ; A country. These should ordinarily be 2-character strings,
+ ; but I don't want to enforce that.
+ Country = tstr;
+
+ ; SoftwareDescription replaces our old "version".
+ SoftwareDescription = [
+ software: tstr,
+ version: tstr,
+ extra: tstr
+ ]
+
+ ; Protocol versions: after a bit of experimentation, I think
+ ; the most reasonable representation to use is a map from protocol
+ ; ID to a bitmask of the supported versions.
+ ProtoVersions = { ProtoId => ProtoBitmask }
+
+ ; Integer protocols are reserved for future version of Tor. tstr ids
+ ; are reserved for experimental and non-tor extensions.
+ ProtoId = ProtoIdEnum / int / tstr
+
+ ProtoIdEnum = &(
+ Link : 0,
+ LinkAuth : 1,
+ Relay : 2,
+ DirCache : 3,
+ HSDir : 4,
+ HSIntro : 5,
+ HSRend : 6,
+ Desc : 7,
+ MicroDesc: 8,
+ Cons : 9,
+ Padding : 10,
+ FlowCtrl : 11,
+ )
+ ; This type is limited to 64 bits, and that's fine. If we ever
+ ; need a protocol version higher than 63, we should allocate a
+ ; new protoid.
+ ProtoBitmask = uint
+
+ ; An exit policy may exist in up to two variants. When port classes
+ ; have not changed in a while, only one policy is needed. If port
+ ; classes have changed recently, however, then SNIPs need to include
+ ; each relay's position according to both the older and the newer policy
+ ; until older network parameter documents become invalid.
+ ExitPolicy = SinglePolicy / [ SinglePolicy, SinglePolicy ]
+
+ ; Each single exit policy is a tagged bit array, whose bits
+ ; correspond to the members of the list of port classes in the
+ ; network parameter document with a corresponding tag.
+ SinglePolicy = [
+ ; Identifies which group of port classes we're talking about
+ tag: unsigned,
+ ; Bit-array of which port classes this relay supports.
+ policy: bstr
+ ]
+
+<!-- Section 2.2.2 --> <a id='S2.2.2'></a>
+
+### SNIPLocation: Locating a SNIP within a routing index.
+
+The SNIPLocation type can encode where a SNIP is located with
+respect to one or more routing indices. Note that a SNIPLocation
+does not need to be exhaustive: If a given IndexId is not listed for
+a given relay in one SNIP, it might exist in another SNIP. Clients
+should not infer that the absence of an IndexId in one SNIPLocation
+for a relay means that no SNIPLocation with that IndexId exists for
+the relay.
+
+ ; SNIPLocation: we're using a map here because it's natural
+ ; to look up indices in maps.
+ SNIPLocation = {
+ ; The keys of this mapping represent the routing indices in
+ ; which a SNIP appears. The values represent the index ranges
+ ; that it occupies in those indices.
+ * IndexId => IndexRange / ExtensionIndex,
+ }
+
+ ; We'll define the different index ranges as we go on with
+ ; these specifications.
+ ;
+ ; IndexId values over 65535 are reserved for extensions and
+ ; experimentation.
+ IndexId = uint32
+
+ ; An index range extends from a minimum to a maximum value.
+ ; These ranges are _inclusive_ on both sides. If 'hi' is less
+ ; than 'lo', then this index "wraps around" the end of the ring.
+ ; A "nil" value indicates an empty range, which would not
+ ; ordinarily be included.
+ IndexRange = [ lo: IndexPos,
+ hi: IndexPos ] / nil
+
+ ; An ExtensionIndex is reserved for future use; current clients
+ ; will not understand it and current ENDIVEs will not contain it.
+ ExtensionIndex = any
+
+ ; For most routing indices, the ranges are encoded as 4-byte integers.
+ ; But for hsdir rings, they are binary strings. (Clients and
+ ; relays SHOULD NOT require this.)
+ IndexPos = uint / bstr
+
+A bit more on IndexRanges: Every IndexRange actually describes a set of
+_prefixes_ for possible index positions. For example, the IndexRange
+`[ h'AB12', h'AB24' ]` includes all the binary strings that start with (hex)
+`AB12`, `AB13`, and so on, up through all strings that start with `AB24`.
+Alternatively, you can think of a `bstr`-based IndexRange *(lo, hi)* as
+covering *lo*`00000...` through *hi*`ff...`.
+
+IndexRanges based on the uint type work the same, except that they always
+specify the first 32 bits of a prefix.
+
+<!-- Section 2.2.3 --> <a id='S2.2.3'></a>
+
+### SNIPSignature: How to prove a SNIP is in the ENDIVE.
+
+Here we describe the types for implementing SNIP signatures, to be
+validated as described in "Design overview: Authentication" above.
+
+ ; Most elements in a SNIPSignature are positional and fixed
+ SNIPSignature = [
+ ; The actual signature or signatures. If this is a single signature,
+ ; it's probably a threshold signature. Otherwise, it's probably
+ ; a list containing one signature from each directory authority.
+ SingleSig / MultiSig,
+
+ ; algorithm to use for the path through the merkle tree.
+ d_alg: DigestAlgorithm,
+ ; Path through merkle tree, possibly empty.
+ merkle_path: MerklePath,
+
+ ; Lifespan information. This is included as part of the input
+ ; to the hash algorithm for the signature.
+ LifespanInfo,
+
+ ; optional nonce for hash algorithm.
+ ? nonce: bstr,
+
+ ; extensions for later use. These are not signed.
+ ? extensions: { * any => any },
+ ]
+
+ ; We use this group to indicate when an object originated, and when
+ ; it should be accepted.
+ ;
+ ; When we are using it as an input to a hash algorithm for computing
+ ; signatures, we encode it as an 8-byte number for "published",
+ ; followed by two 4-byte numbers for pre-valid and post-valid.
+ LifespanInfo = (
+ ; Official publication time in seconds since the epoch. These
+ ; MUST be monotonically increasing over time for a given set of
+ ; authorities on all SNIPs or ENDIVEs that they generate: a
+ ; document with a greater `published` time is always more recent
+ ; than one with an earlier `published` time.
+ ;
+ ; Seeing a publication time "in the future" on a correctly
+ ; authenticated document is a reliable sign that your
+ ; clock is set too far in the past.
+ published: uint,
+
+ ; Value to subtract from "published" in order to find the first second
+ ; at which this object should be accepted.
+ pre-valid: uint32,
+
+ ; Value to add to "published" in order to find the last
+ ; second at which this object should be accepted. The
+ ; lifetime of an object is therefore equal to "(post-valid +
+ ; pre-valid)".
+ post-valid: uint32,
+ )
+
+ ; A Lifespan is just the fields of LifespanInfo, encoded as a list.
+ Lifespan = [ LifespanInfo ]
+
+ ; One signature on a SNIP or ENDIVE. If the signature is a threshold
+ ; signature, or a reference to a signature in another
+ ; document, there will probably be just one of these per SNIP. But if
+ ; we're sticking a full multisignature in the document, this
+ ; is just one of the signatures on it.
+ SingleSig = [
+ s_alg: SigningAlgorithm,
+ ; One of signature and sig_reference must be present.
+ ?signature: bstr,
+ ; sig_reference is an identifier for a signature that appears
+ ; elsewhere, and can be fetched on request. It should only be
+ ; used with signature types too large to attach to SNIPs on their
+ ; own.
+ ?sig_reference: bstr,
+ ; A prefix of the key or the key's digest, depending on the
+ ; algorithm.
+ ?keyid: bstr,
+ ]
+
+ MultiSig = [ + SingleSig ]
+
+ ; A Merkle path is represented as a sequence of bits to
+ ; indicate whether we're going left or right, and a list of
+ ; hashes for the parts of the tree that we aren't including.
+ ;
+ ; (It's safe to use a uint for the number of bits, since it will
+ ; never overflow 64 bits -- that would mean a Merkle tree with
+ ; too many leaves to actually calculate on.)
+ MerklePath = [ uint, *bstr ]
+
+<!-- Section 2.3 --> <a id='S2.3'></a>
+
+## ENDIVEs: sending a bunch of SNIPs efficiently.
+
+ENDIVEs are delivered by the authorities in a compressed format, optimized
+for diffs.
+
+Note that if we are using Merkle trees for SNIP authentication, ENDIVEs do
+not include the trees at all, since those can be inferred from the leaves of
+the tree. Similarly, the ENDIVEs do not include raw routing indices, but
+instead include a set of bandwidths that can be combined into the routing
+indices -- these bandwidths change less frequently, and therefore are more
+diff-friendly.
+
+Note also that this format has more "wasted bytes" than SNIPs
+do. Unlike SNIPs, ENDIVEs are large enough to benefit from
+compression with with gzip, lzma2, or so on.
+
+This section does not fully specify how to construct SNIPs from an ENDIVE;
+for the full algorithm, see section 04.
+
+ ; ENDIVEs are also sent as CBOR.
+ ENDIVE = [
+ ; Signature for the ENDIVE, using a simpler format than for
+ ; a SNIP. Since ENDIVEs are more like a consensus, we don't need
+ ; to use threshold signatures or Merkle paths here.
+ sig: ENDIVESignature,
+
+ ; Contents, as a binary string.
+ body: encoded-cbor .cbor ENDIVEContent,
+ ]
+
+ ; The set of signatures across an ENDIVE.
+ ;
+ ; This type doubles as the "detached signature" document used when
+ ; collecting signatures for a consensus.
+ ENDIVESignature = {
+ ; The actual signatures on the endive. A multisignature is the
+ ; likeliest format here.
+ endive_sig: [ + SingleSig ],
+
+ ; Lifespan information. As with SNIPs, this is included as part
+ ; of the input to the hash algorithm for the signature.
+ ; Note that the lifespan of an ENDIVE is likely to be a subset
+ ; of the lifespan of its SNIPs.
+ endive_lifespan: Lifespan,
+
+ ; Signatures across SNIPs, at some level of the Merkle tree. Note
+ ; that these signatures are not themselves signed -- having them
+ ; signed would take another step in the voting algorithm.
+ snip_sigs: DetachedSNIPSignatures,
+
+ ; Signatures across the ParamDoc pieces. Note that as with the
+ ; DetachedSNIPSignatures, these signatures are not themselves signed.
+ param_doc: ParamDocSignature,
+
+ ; extensions for later use. These are not signed.
+ * tstr => any,
+ }
+
+ ; A list of single signatures or a list of multisignatures. This
+ ; list must have 2^signature-depth elements.
+ DetachedSNIPSignatures =
+ [ *SingleSig ] / [ *MultiSig ]
+
+ ENDIVEContent = {
+
+ ; Describes how to interpret the signatures over the SNIPs in this
+ ; ENDIVE. See section 04 for the full algorithm.
+ sig_params: {
+ ; When should we say that the signatures are valid?
+ lifespan: Lifespan,
+ ; Nonce to be used with the signing algorithm for the signatures.
+ ? signature-nonce: bstr,
+
+ ; At what depth of a Merkle tree do the signatures apply?
+ ; (If this value is 0, then only the root of the tree is signed.
+ ; If this value is >= ceil(log2(n_leaves)), then every leaf is
+ ; signed.).
+ signature-depth: uint,
+
+ ; What digest algorithm is used for calculating the signatures?
+ signature-digest-alg: DigestAlgorithm,
+
+ ; reserved for future extensions.
+ * tstr => any,
+ },
+
+ ; Documents for clients/relays to learn about current network
+ ; parameters.
+ client-param-doc: encoded-cbor .cbor ClientParamDoc,
+ relay-param-doc: encoded-cbor .cbor RelayParamDoc,
+
+ ; Definitions for index group. Each "index group" is all
+ ; applied to the same SNIPs. (If there is one index group,
+ ; then every relay is in at most one SNIP, and likely has several
+ ; indices. If there are multiple index groups, then relays
+ ; can appear in more than one SNIP.)
+ indexgroups: [ *IndexGroup ],
+
+ ; Information on particular relays.
+ ;
+ ; (The total number of SNIPs identified by an ENDIVE is at most
+ ; len(indexgroups) * len(relays).)
+ relays: [ * ENDIVERouterData ],
+
+ ; for future exensions
+ * tstr => any,
+ }
+
+ ; An "index group" lists a bunch of routing indices that apply to the same
+ ; SNIPs. There may be multiple index groups when a relay needs to appear
+ ; in different SNIPs with routing indices for some reason.
+ IndexGroup = {
+ ; A list of all the indices that are built for this index group.
+ ; An IndexId may appear in at most one group per ENDIVE.
+ indices: [ + IndexId ],
+ ; A list of keys to delete from SNIPs to build this index group.
+ omit_from_snips: [ *(int/tstr) ],
+ ; A list of keys to forward from SNIPs to the next relay in an EXTEND
+ ; cell. This can help the next relay know which keys to use in its
+ ; handshake.
+ forward_with_extend: [ *(int/tstr) ],
+
+ ; A number of "gaps" to place in the Merkle tree after the SNIPs
+ ; in this group. This can be used together with signature-depth
+ ; to give different index-groups independent signatures.
+ ? n_padding_entries: uint,
+
+ ; A detailed description of how to build the index.
+ + IndexId => IndexSpec,
+
+ ; For experimental and extension use.
+ * tstr => any,
+ }
+
+ ; Enumeration to identify how to generate an index.
+ Indextype_Raw = 0
+ Indextype_Weighted = 1
+ Indextype_RSAId = 2
+ Indextype_Ed25519Id = 3
+ Indextype_RawNumeric = 4
+
+ ; An indexspec may be given as a raw set of index ranges. This is a
+ ; fallback for cases where we simply can't construct an index any other
+ ; way.
+ IndexSpec_Raw = {
+ type: Indextype_Raw,
+ ; This index is constructed by taking relays by their position in the
+ ; list from the list of ENDIVERouterData, and placing them at a given
+ ; location in the routing index. Each index range extends up to
+ ; right before the next index position.
+ index_ranges: [ * [ uint, IndexPos ] ],
+ }
+
+ ; An indexspec given as a list of numeric spans on the index.
+ IndexSpec_RawNumeric = {
+ type: Indextype_RawNumeric,
+ first_index_pos: uint,
+ ; This index is constructed by taking relays by index from the list
+ ; of ENDIVERouterData, and giving them a certain amount of "weight"
+ ; in the index.
+ index_ranges: [ * [ idx: uint, span: uint ] ],
+ }
+
+ ; This index is computed from the weighted bandwidths of all the SNIPs.
+ ;
+ ; Note that when a single bandwidth changes, it can change _all_ of
+ ; the indices in a bandwidth-weighted index, even if no other
+ ; bandwidth changes. That's why we only pack the bandwidths
+ ; here, and scale them as part of the reconstruction algorithm.
+ IndexSpec_Weighted = {
+ type: Indextype_Weighted,
+ ; This index is constructed by assigning a weight to each relay,
+ ; and then normalizing those weights. See algorithm below in section
+ ; 04.
+ ; Limiting bandwidth weights to uint32 makes reconstruction algorithms
+ ; much easier.
+ index_weights: [ * uint32 ],
+ }
+
+ ; This index is computed from the RSA identity key digests of all of the
+ ; SNIPs. It is used in the HSv2 directory ring.
+ IndexSpec_RSAId = {
+ type: Indextype_RSAId,
+ ; How many bytes of RSA identity data go into each indexpos entry?
+ n_bytes: uint,
+ ; Bitmap of which routers should be included.
+ members: bstr,
+ }
+
+ ; This index is computed from the Ed25519 identity keys of all of the
+ ; SNIPs. It is used in the HSv3 directory ring.
+ IndexSpec_Ed25519Id = {
+ type: Indextype_Ed25519Id,
+ ; How many bytes of digest go into each indexpos entry?
+ n_bytes: uint,
+ ; What digest do we use for building this ring?
+ d_alg: DigestAlgorithm,
+ ; What bytes do we give to the hash before the ed25519?
+ prefix: bstr,
+ ; What bytes do we give to the hash after the ed25519?
+ suffix: bstr,
+ ; Bitmap of which routers should be included.
+ members: bstr,
+ }
+
+ IndexSpec = IndexSpec_Raw /
+ IndexSpec_RawNumeric /
+ IndexSpec_Weighted /
+ IndexSpec_RSAId /
+ IndexSpec_Ed25519Id
+
+ ; Information about a single router in an ENDIVE.
+ ENDIVERouterData = {
+ ; The authority-generated SNIPRouterData for this router.
+ 1 => encoded-cbor .cbor SNIPRouterData,
+ ; The RSA identity, or a prefix of it, to use for HSv2 indices.
+ ? 2 => RSAIdentityFingerprint,
+
+ * int => any,
+ * tstr => any,
+ }
+
+ ; encoded-cbor is defined in the CDDL postlude as a bstr that is
+ ; tagged as holding verbatim CBOR:
+ ;
+ ; encoded-cbor = #6.24(bstr)
+ ;
+ ; Using a tag like this helps tools that validate the string as
+ ; valid CBOR; using a bstr helps indicate that the signed data
+ ; should not be interpreted until after the signature is checked.
+ ; It also helps diff tools know that they should look inside these
+ ; objects.
+
+<!-- Section 2.4 --> <a id='S2.4'></a>
+
+## Network parameter documents
+
+Network parameter documents ("ParamDocs" for short) take the place of the
+current consensus and certificates as a small document that clients and
+relays need to download periodically and keep up-to-date. They are generated
+as part of the voting process, and contain fields like network parameters,
+recommended versions, authority certificates, and so on.
+
+ ; A "parameter document" is like a tiny consensus that relays and clients
+ ; can use to get network parameters.
+ ParamDoc = [
+ sig: ParamDocSignature,
+ ; Client-relevant portion of the parameter document. Everybody fetches
+ ; this.
+ cbody: encoded-cbor .cbor ClientParamDoc,
+ ; Relay-relevant portion of the parameter document. Only relays need to
+ ; fetch this; the document can be validated without it.
+ ? sbody: encoded-cbor .cbor RelayParamDoc,
+ ]
+ ParamDocSignature = [
+ ; Multisignature or threshold signature of the concatenation
+ ; of the two digests below.
+ SingleSig / MultiSig,
+
+ ; Lifespan information. As with SNIPs, this is included as part
+ ; of the input to the hash algorithm for the signature.
+ ; Note that the lifespan of a parameter document is likely to be
+ ; very long.
+ LifespanInfo,
+
+ ; how are c_digest and s_digest computed?
+ d_alg: DigestAlgorithm,
+ ; Digest over the cbody field
+ c_digest: bstr,
+ ; Digest over the sbody field
+ s_digest: bstr,
+ ]
+
+ ClientParamDoc = {
+ params: NetParams,
+ ; List of certificates for all the voters. These
+ ; authenticate the keys used to sign SNIPs and ENDIVEs and votes,
+ ; using the authorities' longest-term identity keys.
+ voters: [ + bstr .cbor VoterCert ],
+
+ ; A division of exit ports into "classes" of ports.
+ port-classes: PortClasses,
+
+ ; As in client-versions from dir-spec.txt
+ ? recommend-versions: [ * tstr ],
+ ; As in recommended-client-protocols in dir-spec.txt
+ ? recommend-protos: ProtoVersions,
+ ; As in required-client-protocols in dir-spec.txt
+ ? require-protos: ProtoVersions,
+
+ ; For future extensions.
+ * tstr => any,
+ }
+
+ RelayParamDoc = {
+ params: NetParams,
+
+ ; As in server-versions from dir-spec.txt
+ ? recommend-versions: [ * tstr ],
+ ; As in recommended-relay-protocols in dir-spec.txt
+ ? recommend-protos: ProtoVersions,
+ ; As in required-relay-protocols in dir-spec.txt
+ ? require-versions: ProtoVersions,
+
+ * tstr => any,
+ }
+
+ ; A NetParams encodes information about the Tor network that
+ ; clients and relays need in order to participate in it. The
+ ; current list of parameters is described in the "params" field
+ ; as specified in dir-spec.txt.
+ ;
+ ; Note that there are separate client and relay NetParams now.
+ ; Relays are expected to first check for a defintion in the
+ ; RelayParamDoc, and then in the ClientParamDoc.
+ NetParams = { *tstr => int }
+
+ PortClasses = {
+ ; identifies which port class grouping this is. Used to migrate
+ ; from one group of port classes to another.
+ tag: uint,
+ ; list of the port classes.
+ classes: { * IndexId => PortList },
+ }
+ PortList = [ *PortOrRange ]
+ ; Either a single port or a low-high pair
+ PortOrRange = Port / [ Port, Port ]
+ Port = 1...65535
+
+<!-- Section 2.5 --> <a id='S2.5'></a>
+
+## Certificates
+
+Voting certificates are used to bind authorities' long-term
+identities to shorter-term signing keys. These have a similar
+purpose to the authority certs made for the existing voting
+algorithm, but support more key types.
+
+ ; A 'voter certificate' is a statement by an authority binding keys to
+ ; each other.
+ VoterCert = [
+
+ ; One or more signatures over `content` using the provided lifetime.
+ ; Each signature should be treated independently.
+ [ + SingleSig ],
+ ; A lifetime value, used (as usual ) as an input to the
+ ; signature algorithm.
+ LifespanInfo,
+ ; The keys and other data to be certified.
+ content: encoded-cbor .cbor CertContent,
+ ]
+
+ ; The contents of the certificate that get signed.
+ CertContent = {
+ ; What kind of a certificate is this?
+ type: CertType,
+ ; A list of keys that are being certified in this document
+ keys: [ + CertifiedKey ],
+ ; A list of other keys that you might need to know about, which
+ ; are NOT certififed in this document.
+ ? extra: [ + CertifiedKey ],
+ * tstr => any,
+ }
+
+ CertifiedKey = {
+ ; What is the intended usage of this key?
+ usage: KeyUsage,
+ ; What cryptographic algorithm is this key used for?
+ alg: PKAlgorithm,
+ ; The actual key being certified.
+ data: bstr,
+ ; A human readable string.
+ ? remarks: tstr,
+ * tstr => any,
+ }
+
+<!-- Section 2.6 --> <a id='S2.6'></a>
+
+## ENDIVE diffs
+
+Here is a binary format to be used with ENDIVEs, ParamDocs, and any
+other similar binary formats. Authorities and directory caches need to
+be able to generate it; clients and non-cache relays only need to be
+able to parse and apply it.
+
+ ; Binary diff specification.
+ BinaryDiff = {
+ ; This is version 1.
+ v: 1,
+ ; Optionally, a diff can say what different digests
+ ; of the document should be before and after it is applied.
+ ; If there is more than one entry, parties MAY check one or
+ ; all of them.
+ ? digest: { * DigestAlgorithm =>
+ [ pre: Digest,
+ post: Digest ]},
+
+ ; Optionally, a diff can give some information to identify
+ ; which document it applies to, and what document you get
+ ; from applying it. These might be a tuple of a document type
+ ; and a publication type.
+ ? ident: [ pre: any, post: any ],
+
+ ; list of commands to apply in order to the original document in
+ ; order to get the transformed document
+ cmds: [ *DiffCommand ],
+
+ ; for future extension.
+ * tstr => any,
+ }
+
+ ; There are currently only two diff commands.
+ ; One is to copy some bytes from the original.
+ CopyDiffCommand = [
+ OrigBytesCmdId,
+ ; Range of bytes to copy from the original document.
+ ; Ranges include their starting byte. The "offset" is relative to
+ ; the end of the _last_ range that was copied.
+ offset: int,
+ length: uint,
+ ]
+
+ ; The other diff comment is to insert some bytes from the diff.
+ InsertDiffCommand = [
+ InsertBytesCmdId,
+ data: bstr,
+ ]
+
+ DiffCommand = CopyDiffCommand / InsertDiffCommand
+
+ OrigBytesCmdId = 0
+ InsertBytesCmdId = 1
+
+Applying a binary diff is simple:
+
+ Algorithm: applying a binary diff.
+
+ (Given an input bytestring INP and a diff D, produces an output OUT.)
+
+ Initialize OUT to an empty bytestring.
+
+ Set OFFSET to 0.
+
+ For each command C in D.commands, in order:
+
+ If C begins with OrigBytesCmdId:
+ Increase "OFFSET" by C.offset
+ If OFFSET..OFFSET+C.length is not a valid range in
+ INP, abort.
+ Append INP[OFFSET .. OFFSET+C.length] to OUT.
+ Increase "OFFSET" by C.length
+
+ else: # C begins with InsertBytesCmdId:
+ Append C.data to OUT.
+
+Generating a binary diff can be trickier, and is not specified here.
+There are several generic algorithms out there for making binary diffs
+between arbitrary byte sequences. Since these are complex, I recommend a
+chunk-based CBOR-aware algorithm, using each CBOR item in a similar way
+to the way in which our current line-oriented code uses lines. When
+encountering a bstr tagged with "encoded-cbor", the diff algorithm
+should look inside it to find more cbor chunks. (See
+example-code/cbor_diff.py for an example of doing this with Python's
+difflib.)
+
+The diff format above should work equally well no matter what
+diff algorithm is used, so we have room to move to other algorithms
+in the future if needed.
+
+To indicate support for the above diff format in directory requests,
+implementations should use an `X-Support-Diff-Formats` header. The
+above format is designated "cbor-bindiff"; our existing format is
+called "ed".
+
+<!-- Section 2.7 --> <a id='S2.7'></a>
+
+## Digests and parameters
+
+Here we give definitions for `H_leaf()` and `H_node()`, based on an
+underlying digest function H() with a preferred input block size of B.
+(B should be chosen as the natural input size of the hash function, to
+aid in precomputation.)
+
+We also define `H_sign()`, to be used outside of SNIP authentication
+where we aren't using a Merkle tree at all.
+
+PATH must be no more than 64 bits long. NONCE must be no more than B-33
+bytes long.
+
+ H_sign(LIFESPAN, NONCE, ITEM) =
+ H( PREFIX(OTHER_C, LIFESPAN, NONCE) || ITEM)
+
+ H_leaf(PATH, LIFESPAN, NONCE, ITEM) =
+ H( PREFIX(LEAF_C, LIFESPAN, NONCE) ||
+ U64(PATH) ||
+ U64(bits(path)) ||
+ ITEM )
+
+ H_node(PATH, LIFESPAN, NONCE, ITEM) =
+ H( PREFIX(NODE_C, LIFESPAN, NONCE) ||
+ U64(PATH) ||
+ U64(bits(PATH)) ||
+ ITEM )
+
+ PREFIX(leafcode, lifespan, nonce) =
+ U64(leafcode) ||
+ U64(lifespan.published) ||
+ U32(lifespan.pre-valid) ||
+ U32(lifespan.post-valid) ||
+ U8(len(nonce)) ||
+ nonce ||
+ Z(B - 33 - len(nonce))
+
+ LEAF_C = 0x8BFF0F687F4DC6A1 ^ NETCONST
+ NODE_C = 0xA6F7933D3E6B60DB ^ NETCONST
+ OTHER_C = 0x7365706172617465 ^ NETCONST
+
+ # For the live Tor network only.
+ NETCONST = 0x0746f72202020202
+ # For testing networks, by default.
+ NETCONST = 0x74657374696e6720
+
+ U64(n) -- N encoded as a big-endian 64-bit number.
+ Z(n) -- N bytes with value zero.
+ len(b) -- the number of bytes in a byte-string b.
+ bits(b) -- the number of bits in a bit-string b.
+
+
+<!-- Section 3 --> <a id='S3'></a>
+
+# Directory authority operations
+
+For Walking Onions to work, authorities must begin to generate
+ENDIVEs as a new kind of "consensus document". Since this format is
+incompatible with the previous consensus document formats, and is
+CBOR-based, a text-based voting protocol is no longer appropriate
+for generating it.
+
+We cannot immediately abandon the text-based consensus and
+microdescriptor formats, but instead will need to keep
+generating them for legacy relays and clients. Ideally, process
+that produces the ENDIVE should also produce a legacy consensus,
+to limit the amount of divergence in their contents.
+
+Further, it would be good for the purposes of this proposal if we
+can "inherit" as much as possible of our existing voting mechanism
+for legacy purposes.
+
+This section of the proposal will try to solve these goals by defining a
+new binary-based voting format, a new set of voting rules for it, and a
+series of migration steps.
+
+<!-- Section 3.1 --> <a id='S3.1'></a>
+
+## Overview
+
+Except as described below, we retain from Tor's existing voting
+mechanism all notions of how votes are transferred and processed.
+Other changes are likely desirable, but they are out of scope for
+this proposal.
+
+Notably, we are not changing how the voting schedule works. Nor are
+we changing the property that all authorities must agree on the list
+of authorities; the property that a consensus is computed as a
+deterministic function of a set of votes; or the property that if
+authorities believe in different sets of votes, they will not reach
+the same consensus.
+
+The principal changes in the voting that are relevant for legacy
+consensus computation are:
+
+ * The uploading process for votes now supports negotiation, so
+ that the receiving authority can tell the uploading authority
+ what kind of formats, diffs, and compression it supports.
+
+ * We specify a CBOR-based binary format for votes, with a simple
+ embedding method for the legacy text format. This embedding is
+ meant for transitional use only; once all authorities support
+ the binary format, the transitional format and its support
+ structures can be abandoned.
+
+ * To reduce complexity, the new vote format also includes
+ _verbatim_ microdescriptors, whereas previously microdescriptors
+ would have been referenced by hash. (The use of diffs and
+ compression should make the bandwidth impact of this addition
+ negligible.)
+
+For computing ENDIVEs, the principal changes in voting are:
+
+ * The consensus outputs for most voteable objects are specified in a
+ way that does not require the authorities to understand their
+ semantics when computing a consensus. This should make it
+ easier to change fields without requiring new consensus methods.
+
+<!-- Section 3.2 --> <a id='S3.2'></a>
+
+## Negotiating vote uploads
+
+Authorities supporting Walking Onions are required to support a new
+resource "/tor/auth-vote-opts". This resource is a text document
+containing a list of HTTP-style headers. Recognized headers are
+described below; unrecognized headers MUST be ignored.
+
+The *Accept-Encoding* header follows the same format as the HTTP
+header of the same name; it indicates a list of Content-Encodings
+that the authority will accept for uploads. All authorities SHOULD
+support the gzip and identity encodings. The identity encoding is
+mandatory. (Default: "identity")
+
+The *Accept-Vote-Diffs-From* header is a list of digests of previous
+votes held by this authority; any new uploaded votes that are given
+as diffs from one of these old votes SHOULD be accepted. The format
+is a space-separated list of "digestname:Hexdigest". (Default: "".)
+
+The *Accept-Vote-Formats* header is a space-separated list of the
+vote formats that this router accepts. The recognized vote formats
+are "legacy-3" (Tor's current vote format) and "endive-1" (the vote
+format described here). Unrecognized vote formats MUST be ignored.
+(Default: "legacy-3".)
+
+If requesting "/tor/auth-vote-opts" gives an error, or if one or
+more headers are missing, the default values SHOULD be used. These
+documents (or their absence) MAY be cached for up to 2 voting
+periods.)
+
+Authorities supporting Walking Onions SHOULD also support the
+"Connection: keep-alive" and "Keep-Alive" HTTP headers, to avoid
+needless reconnections in response to these requests.
+Implementors SHOULD be aware of potential denial-of-service
+attacks based on open HTTP connections, and mitigate them as
+appropriate.
+
+> Note: I thought about using OPTIONS here, but OPTIONS isn't quite
+> right for this, since Accept-Vote-Diffs-From does not fit with its
+> semantics.
+
+> Note: It might be desirable to support this negotiation for legacy
+> votes as well, even before walking onions is implemented. Doing so
+> would allow us to reduce authority bandwidth a little, and possibly
+> include microdescriptors in votes for more convenient processing.
+
+<!-- Section 3.3 --> <a id='S3.3'></a>
+
+## A generalized algorithm for voting
+
+Unlike with previous versions of our voting specification, here I'm
+going to try to describe pieces the voting algorithm in terms of
+simpler voting operations. Each voting operation will be named and
+possibly parameterized, and data will frequently self-describe what
+voting operation is to be used on it.
+
+Voting operations may operate over different CBOR types, and are
+themselves specified as CBOR objects.
+
+A voting operation takes place over a given "voteable field". Each
+authority that specifies a value for a voteable field MUST specify
+which voting operation to use for that field. Specifying a voteable
+field without a voting operation MUST be taken as specifying the
+voting operation "None" -- that is, voting against a consensus.
+
+On the other hand, an authority MAY specify a voting operation for
+a field without casting any vote for it. This means that the
+authority has an opinion on how to reach a consensus about the
+field, without having any preferred value for the field itself.
+
+<!-- Section 3.3.1 --> <a id='S3.3.1'></a>
+
+### Constants used with voting operations
+
+Many voting operations may be parameterized by an unsigned integer.
+In some cases the integers are constant, but in others, they depend
+on the number of authorities, the number of votes cast, or the
+number of votes cast for a particular field.
+
+When we encode these values, we encode them as short strings
+rather than as integers.
+
+> I had thought of using negative integers here to encode these
+> special constants, but that seems too error-prone.
+
+The following constants are defined:
+
+`N_AUTH` -- the total number of authorities, including those whose
+votes are absent.
+
+`N_PRESENT` -- the total number of authorities whose votes are
+present for this vote.
+
+`N_FIELD` -- the total number of authorities whose votes for a given
+field are present.
+
+Necessarily, `N_FIELD` <= `N_PRESENT` <= `N_AUTH` -- you can't vote
+on a field unless you've cast a vote, and you can't cast a vote
+unless you're an authority.
+
+In the definitions below, `//` denotes the truncating integer division
+operation, as implemented with `/` in C.
+
+`QUORUM_AUTH` -- The lowest integer that is greater than half of
+`N_AUTH`. Equivalent to `N_AUTH // 2 + 1`.
+
+`QUORUM_PRESENT` -- The lowest integer that is greater than half of
+`N_PRESENT`. Equivalent to `N_PRESENT // 2 + 1`.
+
+`QUORUM_FIELD` -- The lowest integer that is greater than half of
+`N_FIELD`. Equivalent to `N_FIELD // 2 + 1`.
+
+We define `SUPERQUORUM_`..., variants of these fields as well, based
+on the lowest integer that is greater than 2/3 majority of the
+underlying field. `SUPERQUORUM_x` is thus equivalent to
+`(N_x * 2) // 3 + 1`.
+
+ ; We need to encode these arguments; we do so as short strings.
+ IntOpArgument = uint / "auth" / "present" / "field" /
+ "qauth" / "qpresent" / "qfield" /
+ "sqauth" / "sqpresent" / "sqfield"
+
+No IntOpArgument may be greater than AUTH. If an IntOpArgument is
+given as an integer, and that integer is greater than AUTH, then it
+is treated as if it were AUTH.
+
+> This rule lets us say things like "at least 3 authorities must
+> vote on x...if there are 3 authorities."
+
+<!-- Section 3.3.2 --> <a id='S3.3.2'></a>
+
+### Producing consensus on a field
+
+Each voting operation will either produce a CBOR output, or produce
+no consensus. Unless otherwise stated, all CBOR outputs are to be
+given in canonical form.
+
+Below we specify a number of operations, and the parameters that
+they take. We begin with operations that apply to "simple" values
+(integers and binary strings), then show how to compose them to
+larger values.
+
+All of the descriptions below show how to apply a _single_ voting
+operation to a set of votes. We will later describe how to behave when
+the authorities do not agree on which voting operation to use, in our
+discussion of the StructJoinOp operation.
+
+Note that while some voting operations take other operations as
+parameters, we are _not_ supporting full recursion here: there is a
+strict hierarchy of operations, and more complex operations can only
+have simpler operations in their parameters.
+
+All voting operations follow this metaformat:
+
+ ; All a generic voting operation has to do is say what kind it is.
+ GenericVotingOp = {
+ op: tstr,
+ * tstr => any,
+ }
+
+Note that some voting operations require a sort or comparison
+operation over CBOR values. This operation is defined later in
+appendix E; it works only on homogeneous inputs.
+
+<!-- Section 3.3.3 --> <a id='S3.3.3'></a>
+
+### Generic voting operations
+
+<!-- Section 3.3.3.1 --> <a id='S3.3.3.1'></a>
+
+#### None
+
+This voting operation takes no parameters, and always produces "no
+consensus". It is encoded as:
+
+ ; "Don't produce a consensus".
+ NoneOp = { op: "None" }
+
+When encountering an unrecognized or nonconforming voting operation,
+_or one which is not recognized by the consensus-method in use_, the
+authorities proceed as if the operation had been "None".
+
+<!-- Section 3.3.4 --> <a id='S3.3.4'></a>
+
+### Voting operations for simple values
+
+We define a "simple value" according to these cddl rules:
+
+ ; Simple values are primitive types, and tuples of primitive types.
+ SimpleVal = BasicVal / SimpleTupleVal
+ BasicVal = bool / int / bstr / tstr
+ SimpleTupleVal = [ *BasicVal ]
+
+We also need the ability to encode the types for these values:
+
+ ; Encoding a simple type.
+ SimpleType = BasicType / SimpleTupleType
+ BasicType = "bool" / "uint" / "sint" / "bstr" / "tstr"
+ SimpleTupleType = [ "tuple", *BasicType ]
+
+In other words, a SimpleVal is either an non-compound base value, or is
+a tuple of such values.
+
+ ; We encode these operations as:
+ SimpleOp = MedianOp / ModeOp / ThresholdOp /
+ BitThresholdOp / CborSimpleOp / NoneOp
+
+We define each of these operations in the sections below.
+
+<!-- Section 3.3.4.1 --> <a id='S3.3.4.1'></a>
+
+#### Median
+
+_Parameters_: `MIN_VOTES` (an integer), `BREAK_EVEN_LOW` (a boolean),
+`TYPE` (a SimpleType)
+
+ ; Encoding:
+ MedianOp = { op: "Median",
+ ? min_vote: IntOpArgument, ; Default is 1.
+ ? even_low: bool, ; Default is true.
+ type: SimpleType }
+
+Discard all votes that are not of the specified `TYPE`. If there are
+fewer than `MIN_VOTES` votes remaining, return "no consensus".
+
+Put the votes in ascending sorted order. If the number of votes N
+is odd, take the center vote (the one at position (N+1)/2). If N is
+even, take the lower of the two center votes (the one at position
+N/2) if `BREAK_EVEN_LOW` is true. Otherwise, take the higher of the
+two center votes (the one at position N/2 + 1).
+
+For example, the Median(…, even_low: True, type: "uint") of the votes
+["String", 2, 111, 6] is 6. The Median(…, even_low: True, type: "uint")
+of the votes ["String", 77, 9, 22, "String", 3] is 9.
+
+<!-- Section 3.3.4.2 --> <a id='S3.3.4.2'></a>
+
+#### Mode
+
+_Parameters_: `MIN_COUNT` (an integer), `BREAK_TIES_LOW` (a boolean),
+`TYPE` (a SimpleType)
+
+ ; Encoding:
+ ModeOp = { op: "Mode",
+ ? min_count: IntOpArgument, ; Default 1.
+ ? tie_low: bool, ; Default true.
+ type: SimpleType
+ }
+
+Discard all votes that are not of the specified `TYPE`. Of the
+remaining votes, look for the value that has received the most
+votes. If no value has received at least `MIN_COUNT` votes, then
+return "no consensus".
+
+If there is a single value that has received the most votes, return
+it. Break ties in favor of lower values if `BREAK_TIES_LOW` is true,
+and in favor of higher values if `BREAK_TIES_LOW` is false.
+(Perform comparisons in canonical cbor order.)
+
+<!-- Section 3.3.4.3 --> <a id='S3.3.4.3'></a>
+
+#### Threshold
+
+_Parameters_: `MIN_COUNT` (an integer), `BREAK_MULTI_LOW` (a boolean),
+`TYPE` (a SimpleType)
+
+ ; Encoding
+ ThresholdOp = { op: "Threshold",
+ min_count: IntOpArgument, ; No default.
+ ? multi_low: bool, ; Default true.
+ type: SimpleType
+ }
+
+Discard all votes that are not of the specified `TYPE`. Sort in
+canonical cbor order. If `BREAK_MULTI_LOW` is false, reverse the
+order of the list.
+
+Return the first element that received at least `MIN_COUNT` votes.
+If no value has received at least `MIN_COUNT` votes, then return
+"no consensus".
+
+<!-- Section 3.3.4.4 --> <a id='S3.3.4.4'></a>
+
+#### BitThreshold
+
+Parameters: `MIN_COUNT` (an integer >= 1)
+
+ ; Encoding
+ BitThresholdOp = { op: "BitThreshold",
+ min_count: IntOpArgument, ; No default.
+ }
+
+These are usually not needed, but are quite useful for
+building some ProtoVer operations.
+
+Discard all votes that are not of type uint or bstr; construe bstr
+inputs as having type "biguint".
+
+The output is a uint or biguint in which the b'th bit is set iff the
+b'th bit is set in at least `MIN_COUNT` of the votes.
+
+<!-- Section 3.3.5 --> <a id='S3.3.5'></a>
+
+### Voting operations for lists
+
+These operations work on lists of SimpleVal:
+
+ ; List type definitions
+ ListVal = [ * SimpleVal ]
+
+ ListType = [ "list",
+ [ *SimpleType ] / nil ]
+
+They are encoded as:
+
+ ; Only one list operation exists right now.
+ ListOp = SetJoinOp
+
+<!-- Section 3.3.5.1 --> <a id='S3.3.5.1'></a>
+
+#### SetJoin
+
+Parameters: `MIN_COUNT` (an integer >= 1).
+Optional parameters: `TYPE` (a SimpleType.)
+
+ ; Encoding:
+ SetJoinOp = {
+ op: "SetJoin",
+ min_count: IntOpArgument,
+ ? type: SimpleType
+ }
+
+Discard all votes that are not lists. From each vote,
+discard all members that are not of type 'TYPE'.
+
+For the consensus, construct a new list containing exactly those
+elements that appears in at least `MIN_COUNT` votes.
+
+(Note that the input votes may contain duplicate elements. These
+must be treated as if there were no duplicates: the vote
+[1, 1, 1, 1] is the same as the vote [1]. Implementations may want
+to preprocess votes by discarding all but one instance of each
+member.)
+
+<!-- Section 3.3.6 --> <a id='S3.3.6'></a>
+
+### Voting operations for maps
+
+Map voting operations work over maps from key types to other non-map
+types.
+
+ ; Map type definitions.
+ MapVal = { * SimpleVal => ItemVal }
+ ItemVal = ListVal / SimpleVal
+
+ MapType = [ "map", [ *SimpleType ] / nil, [ *ItemType ] / nil ]
+ ItemType = ListType / SimpleType
+
+They are encoded as:
+
+ ; MapOp encodings
+ MapOp = MapJoinOp / StructJoinOp
+
+<!-- Section 3.3.6.1 --> <a id='S3.3.6.1'></a>
+
+#### MapJoin
+
+The MapJoin operation combines homogeneous maps (that is, maps from
+a single key type to a single value type.)
+
+Parameters:
+ `KEY_MIN_COUNT` (an integer >= 1)
+ `KEY_TYPE` (a SimpleType type)
+ `ITEM_OP` (A non-MapJoin voting operation)
+
+Encoding:
+
+ ; MapJoin operation encoding
+ MapJoinOp = {
+ op: "MapJoin"
+ ? key_min_count: IntOpArgument, ; Default 1.
+ key_type: SimpleType,
+ item_op: ListOp / SimpleOp
+ }
+
+First, discard all votes that are not maps. Then consider the set
+of keys from each vote as if they were a list, and apply
+`SetJoin[KEY_MIN_COUNT,KEY_TYPE]` to those lists. The resulting list
+is a set of keys to consider including in the output map.
+
+> We have a separate `key_min_count` field, even if `item_op` has
+> its own `min_count` field, because some min_count values (like
+> `qfield`) depend on the overall number of votes for the field.
+> Having `key_min_count` lets us specify rules like "the FOO of all
+> votes on this field, if there are at least 2 such votes."
+
+For each key in the output list, run the sub-voting operation
+`ItemOperation` on the values it received in the votes. Discard all
+keys for which the outcome was "no consensus".
+
+The final vote result is a map from the remaining keys to the values
+produced by the voting operation.
+
+<!-- Section 3.3.6.2 --> <a id='S3.3.6.2'></a>
+
+#### StructJoin
+
+A StructJoinOp operation describes a way to vote on maps that encode a
+structure-like object.
+
+Parameters:
+ `KEY_RULES` (a map from int or string to StructItemOp)
+ `UNKNOWN_RULE` (An operation to apply to unrecognized keys.)
+
+ ; Encoding
+ StructItemOp = ListOp / SimpleOp / MapJoinOp / DerivedItemOp /
+ CborDerivedItemOp
+
+ VoteableStructKey = int / tstr
+
+ StructJoinOp = {
+ op: "StructJoin",
+ key_rules: {
+ * VoteableStructKey => StructItemOp,
+ }
+ ? unknown_rule: StructItemOp
+ }
+
+To apply a StructJoinOp to a set of votes, first discard every vote that is
+not a map. Then consider the set of keys from all the votes as a single
+list, with duplicates removed. Also remove all entries that are not integers
+or strings from the list of keys.
+
+For each key, then look for that key in the `KEY_RULES` map. If there is an
+entry, then apply the StructItemOp for that entry to the values for that key
+in every vote. Otherwise, apply the `UNKNOWN_RULE` operation to the values
+for that key in every vote. Otherwise, there is no consensus for the values
+of this key. If there _is_ a consensus for the values, then the key should
+map to that consensus in the result.
+
+This operation always reaches a consensus, even if it is an empty map.
+
+<!-- Section 3.3.6.3 --> <a id='S3.3.6.3'></a>
+
+#### CborData
+
+A CborData operation wraps another operation, and tells the authorities
+that after the operation is completed, its result should be decoded as a
+CBOR bytestring and interpolated directly into the document.
+
+Parameters: `ITEM_OP` (Any SingleOp that can take a bstr input.)
+
+ ; Encoding
+ CborSimpleOp = {
+ op: "CborSimple",
+ item-op: MedianOp / ModeOp / ThresholdOp / NoneOp
+ }
+ CborDerivedItemOp = {
+ op: "CborDerived",
+ item-op: DerivedItemOp,
+ }
+
+To apply either of these operations to a set of votes, first apply
+`ITEM_OP` to those votes. After that's done, check whether the
+consensus from that operation is a bstr that encodes a single item of
+"well-formed" "valid" cbor. If it is not, this operation gives no
+consensus. Otherwise, the consensus value for this operation is the
+decoding of that bstr value.
+
+<!-- Section 3.3.6.4 --> <a id='S3.3.6.4'></a>
+
+#### DerivedFromField
+
+This operation can only occur within a StructJoinOp operation (or a
+semantically similar SectionRules). It indicates that one field
+should have been derived from another. It can be used, for example,
+to say that a relay's version is "derived from" a relay's descriptor
+digest.
+
+Unlike other operations, this one depends on the entire consensus (as
+computed so far), and on the entirety of the set of votes.
+
+> This operation might be a mistake, but we need it to continue lots of
+> our current behavior.
+
+Parameters:
+ `FIELDS` (one or more other locations in the vote)
+ `RULE` (the rule used to combine values)
+
+Encoding
+ ; This item is "derived from" some other field.
+ DerivedItemOp = {
+ op: "DerivedFrom",
+ fields: [ +SourceField ],
+ rule: SimpleOp
+ }
+
+ ; A field in the vote.
+ SourceField = [ FieldSource, VoteableStructKey ]
+
+ ; A location in the vote. Each location here can only
+ ; be referenced from later locations, or from itself.
+ FieldSource = "M" ; Meta.
+ / "CP" ; ClientParam.
+ / "SP" ; ServerParam.
+ / "RM" ; Relay-meta
+ / "RS" ; Relay-SNIP
+ / "RL" ; Relay-legacy
+
+To compute a consensus with this operation, first locate each field described
+in the SourceField entry in each VoteDocument (if present), and in the
+consensus computed so far. If there is no such field in the
+consensus or if it has not been computed yet, then
+this operation produces "no consensus". Otherwise, discard the VoteDocuments
+that do not have the same value for the field as the consensus, and their
+corresponding votes for this field. Do this for every listed field.
+
+At this point, we have a set of votes for this field's value that all come
+from VoteDocuments that describe the same value for the source field(s). Apply
+the `RULE` operation to those votes in order to give the result for this
+voting operation.
+
+The DerivedFromField members in a SectionRules or a StructJoinOp
+should be computed _after_ the other members, so that they can refer
+to those members themselves.
+
+<!-- Section 3.3.7 --> <a id='S3.3.7'></a>
+
+### Voting on document sections
+
+Voting on a section of the document is similar to the StructJoin
+operation, with some exceptions. When we vote on a section of the
+document, we do *not* apply a single voting rule immediately.
+Instead, we first "_merge_" a set of SectionRules together, and then
+apply the merged rule to the votes. This is the only place where we
+merge rules like this.
+
+A SectionRules is _not_ a voting operation, so its format is not
+tagged with an "op":
+
+ ; Format for section rules.
+ SectionRules = {
+ * VoteableStructKey => SectionItemOp,
+ ? nil => SectionItemOp
+ }
+ SectionItemOp = StructJoinOp / StructItemOp
+
+To merge a set of SectionRules together, proceed as follows. For each
+key, consider whether at least QUORUM_AUTH authorities have voted the
+same StructItemOp for that key. If so, that StructItemOp is the
+resulting operation for this key. Otherwise, there is no entry for this key.
+
+Do the same for the "nil" StructItemOp; use the result as the
+`UNKNOWN_RULE`.
+
+Note that this merging operation is *not* recursive.
+
+<!-- Section 3.4 --> <a id='S3.4'></a>
+
+## A CBOR-based metaformat for votes.
+
+A vote is a signed document containing a number of sections; each
+section corresponds roughly to a section of another document, a
+description of how the vote is to be conducted, or both.
+
+ ; VoteDocument is a top-level signed vote.
+ VoteDocument = [
+ ; Each signature may be produced by a different key, if they
+ ; are all held by the same authority.
+ sig: [ + SingleSig ],
+ lifetime: Lifespan,
+ digest-alg: DigestAlgorithm,
+ body: bstr .cbor VoteContent
+ ]
+
+ VoteContent = {
+ ; List of supported consensus methods.
+ consensus-methods: [ + uint ],
+
+ ; Text-based legacy vote to be used if the negotiated
+ ; consensus method is too old. It should itself be signed.
+ ; It's encoded as a series of text chunks, to help with
+ ; cbor-based binary diffs.
+ ? legacy-vote: [ * tstr ],
+
+ ; How should the votes within the individual sections be
+ ; computed?
+ voting-rules: VotingRules,
+
+ ; Information that the authority wants to share about this
+ ; vote, which is not itself voted upon.
+ notes: NoteSection,
+
+ ; Meta-information that the authorities vote on, which does
+ ; not actually appear in the ENDIVE or consensus directory.
+ meta: MetaSection .within VoteableSection,
+
+ ; Fields that appear in the client network parameter document.
+ client-params: ParamSection .within VoteableSection,
+ ; Fields that appear in the server network parameter document.
+ server-params: ParamSection .within VoteableSection,
+
+ ; Information about each relay.
+ relays: RelaySection,
+
+ ; Information about indices.
+ indices: IndexSection,
+
+ * tstr => any
+ }
+
+ ; Self-description of a voter.
+ VoterSection = {
+ ; human-memorable name
+ name: tstr,
+
+ ; List of link specifiers to use when uploading to this
+ ; authority. (See proposal for dirport link specifier)
+ ? ul: [ *LinkSpecifier ],
+
+ ; List of link specifiers to use when downloading from this authority.
+ ? dl: [ *LinkSpecifier ],
+
+ ; contact information for this authority.
+ ? contact: tstr,
+
+ ; legacy certificate in format given by dir-spec.txt.
+ ? legacy-cert: tstr,
+
+ ; for extensions
+ * tstr => any,
+ }
+
+ ; An indexsection says how we think routing indices should be built.
+ IndexSection = {
+ * IndexId => bstr .cbor [ IndexGroupId, GenericIndexRule ],
+ }
+ IndexGroupId = uint
+ ; A mechanism for building a single routing index. Actual values need to
+ ; be within RecognizedIndexRule or the authority can't complete the
+ ; consensus.
+ GenericIndexRule = {
+ type: tstr,
+ * tstr => any
+ }
+ RecognizedIndexRule = EdIndex / RSAIndex / BWIndex / WeightedIndex
+ ; The values in an RSAIndex are derived from digests of Ed25519 keys.
+ EdIndex = {
+ type: "ed-id",
+ alg: DigestAlgorithm,
+ prefix: bstr,
+ suffix: bstr
+ }
+ ; The values in an RSAIndex are derived from RSA keys.
+ RSAIndex = {
+ type: "rsa-id"
+ }
+ ; A BWIndex is built by taking some uint-valued field referred to by
+ ; SourceField from all the relays that have all of required_flags set.
+ BWIndex = {
+ type: "bw",
+ bwfield: SourceField,
+ require_flags: FlagSet,
+ }
+ ; A flag can be prefixed with "!" to indicate negation. A flag
+ ; with a name like P@X indicates support for port class 'X' in its
+ ; exit policy.
+ ;
+ ; FUTURE WORK: perhaps we should add more structure here and it
+ ; should be a matching pattern?
+ FlagSet = [ *tstr ]
+ ; A WeightedIndex applies a set of weights to a BWIndex based on which
+ ; flags the various routers have. Relays that match a set of flags have
+ ; their weights multiplied by the corresponding WeightVal.
+ WeightedIndex = {
+ type: "weighted",
+ source: BwIndex,
+ weight: { * FlagSet => WeightVal }
+ }
+ ; A WeightVal is either an integer to multiply bandwidths by, or a
+ ; string from the Wgg, Weg, Wbm, ... set as documented in dir-spec.txt,
+ ; or a reference to an earlier field.
+ WeightVal = uint / tstr / SourceField
+ VoteableValue = MapVal / ListVal / SimpleVal
+
+ ; A "VoteableSection" is something that we apply part of the
+ ; voting rules to. When we apply voting rules to these sections,
+ ; we do so without regards to their semantics. When we are done,
+ ; we use these consensus values to make the final consensus.
+ VoteableSection = {
+ VoteableStructKey => VoteableValue,
+ }
+
+ ; A NoteSection is used to convey information about the voter and
+ ; its vote that is not actually voted on.
+ NoteSection = {
+ ; Information about the voter itself
+ voter: VoterSection,
+ ; Information that the voter used when assigning flags.
+ ? flag-thresholds: { tstr => any },
+ ; Headers from the bandwidth file to be reported as part of
+ ; the vote.
+ ? bw-file-headers: {tstr => any },
+ ? shared-rand-commit: SRCommit,
+ * VoteableStructKey => VoteableValue,
+ }
+
+ ; Shared random commitment; fields are as for the current
+ ; shared-random-commit fields.
+ SRCommit = {
+ ver: uint,
+ alg: DigestAlgorithm,
+ ident: bstr,
+ commit: bstr,
+ ? reveal: bstr
+ }
+
+ ; the meta-section is voted on, but does not appear in the ENDIVE.
+ MetaSection = {
+ ; Seconds to allocate for voting and distributing signatures
+ ; Analagous to the "voting-delay" field in the legacy algorithm.
+ voting-delay: [ vote_seconds: uint, dist_seconds: uint ],
+ ; Proposed time till next vote.
+ voting-interval: uint,
+ ; proposed lifetime for the SNIPs and ENDIVEs
+ snip-lifetime: Lifespan,
+ ; proposed lifetime for client params document
+ c-param-lifetime: Lifespan,
+ ; proposed lifetime for server params document
+ s-param-lifetime: Lifespan,
+ ; signature depth for ENDIVE
+ signature-depth: uint,
+ ; digest algorithm to use with ENDIVE.
+ signature-digest-alg: DigestAlgorithm,
+ ; Current and previous shared-random values
+ ? cur-shared-rand: [ reveals: uint, rand: bstr ],
+ ? prev-shared-rand: [ reveals: uint, rand: bstr ],
+ ; extensions.
+ * VoteableStructKey => VoteableValue,
+ };
+
+ ; A ParamSection will be made into a ParamDoc after voting;
+ ; the fields are analogous.
+ ParamSection = {
+ ? certs: [ 1*2 bstr .cbor VoterCert ],
+ ? recommend-versions: [ * tstr ],
+ ? require-protos: ProtoVersions,
+ ? recommend-protos: ProtoVersions,
+ ? params: NetParams,
+ * VoteableStructKey => VoteableValue,
+ }
+ RelaySection = {
+ ; Mapping from relay identity key (or digest) to relay information.
+ * bstr => RelayInfo,
+ }
+
+ ; A RelayInfo is a vote about a single relay.
+ RelayInfo = {
+ meta: RelayMetaInfo .within VoteableSection,
+ snip: RelaySNIPInfo .within VoteableSection,
+ legacy: RelayLegacyInfo .within VoteableSection,
+ }
+
+ ; Information about a relay that doesn't go into a SNIP.
+ RelayMetaInfo = {
+ ; Tuple of published-time and descriptor digest.
+ ? desc: [ uint , bstr ],
+ ; What flags are assigned to this relay? We use a
+ ; string->value encoding here so that only the authorities
+ ; who have an opinion on the status of a flag for a relay need
+ ; to vote yes or no on it.
+ ? flags: { *tstr=>bool },
+ ; The relay's self-declared bandwidth.
+ ? bw: uint,
+ ; The relay's measured bandwidth.
+ ? mbw: uint,
+ ; The fingerprint of the relay's RSA identity key.
+ ? rsa-id: RSAIdentityFingerprint
+ }
+ ; SNIP information can just be voted on directly; the formats
+ ; are the same.
+ RelaySNIPInfo = SNIPRouterData
+
+ ; Legacy information is used to build legacy consensuses, but
+ ; not actually required by walking onions clients.
+ RelayLegacyInfo = {
+ ; Mapping from consensus version to microdescriptor digests
+ ; and microdescriptors.
+ ? mds: [ *Microdesc ],
+ }
+
+ ; Microdescriptor votes now include the digest AND the
+ ; microdescriptor-- see note.
+ Microdesc = [
+ low: uint,
+ high: uint,
+ digest: bstr .size 32,
+ ; This is encoded in this way so that cbor-based diff tools
+ ; can see inside it. Because of compression and diffs,
+ ; including microdesc text verbatim should be comparatively cheap.
+ content: encoded-cbor .cbor [ *tstr ],
+ ]
+
+ ; ==========
+
+ ; The VotingRules field explains how to vote on the members of
+ ; each section
+ VotingRules = {
+ meta: SectionRules,
+ params: SectionRules,
+ relay: RelayRules,
+ indices: SectionRules,
+ }
+
+ ; The RelayRules object explains the rules that apply to each
+ ; part of a RelayInfo. A key will appear in the consensus if it
+ ; has been listed by at least key_min_count authorities.
+ RelayRules = {
+ key_min_count: IntOpArgument,
+ meta: SectionRules,
+ snip: SectionRules,
+ legacy: SectionRules,
+ }
+
+<!-- Section 3.5 --> <a id='S3.5'></a>
+
+## Computing a consensus.
+
+To compute a consensus, the authorities first verify that all the votes are
+timely and correctly signed by real authorities. This includes
+validating all invariants stated here, and all internal documents.
+
+If they have two votes from an authority, authorities SHOULD issue a
+warning, and they should take the one that is published more
+recently.
+
+> TODO: Teor suggests that maybe we shouldn't warn about two votes
+> from an authority for the same period, and we could instead have a
+> more resilient process here, where authorities can update their
+> votes at various times over the voting period, up to some point.
+>
+> I'm not sure whether this helps reliability more or less than it risks it,
+> but it worth investigating.
+
+Next, the authorities determine the consensus method as they do today,
+using the field "consensus-method". This can also be expressed as
+the voting operation `Threshold[SUPERQUORUM_PRESENT, false, uint]`.
+
+If there is no consensus for the consensus-method, then voting stops
+without having produced a consensus.
+
+Note that in contrast with its behavior in the current voting algorithm, the
+consensus method does not determine the way to vote on every
+individual field: that aspect of voting is controlled by the
+voting-rules. Instead, the consensus-method changes other aspects
+of this voting, such as:
+
+ * Adding, removing, or changing the semantics of voting
+ operations.
+ * Changing the set of documents to which voting operations apply.
+ * Otherwise changing the rules that are set out in this
+ document.
+
+Once a consensus-method is decided, the next step is to compute the
+consensus for other sections in this order: `meta`, `client-params`,
+`server-params`, and `indices`. The consensus for each is calculated
+according to the operations given in the corresponding section of
+VotingRules.
+
+Next the authorities compute a consensus on the `relays` section,
+which is done slightly differently, according to the rules of
+RelayRules element of VotingRules.
+
+Finally, the authorities transform the resulting sections into an
+ENDIVE and a legacy consensus, as in "Computing an ENDIVE" and
+"Computing a legacy consensus" below.
+
+To vote on a single VotingSection, find the corresponding
+SectionRules objects in the VotingRules of this votes, and apply it
+as described above in "Voting on document sections".
+
+<!-- Section 3.6 --> <a id='S3.6'></a>
+
+## If an older consensus method is negotiated (Transitional)
+
+The `legacy-vote` field in the vote document contains an older (v3,
+text-style) consensus vote, and is used when an older consensus
+method is negotiated. The legacy-vote is encoded by splitting it
+into pieces, to help with CBOR diff calculation. Authorities MAY split at
+line boundaries, space boundaries, or anywhere that will help with
+diffs. To reconstruct the legacy vote, concatenate the members of
+`legacy-vote` in order. The resulting string MUST validate
+according to the rules of the legacy voting algorithm.
+
+If a legacy vote is present, then authorities SHOULD include the
+same view of the network in the legacy vote as they included in their
+real vote.
+
+If a legacy vote is present, then authorities MUST
+give the same list of consensus-methods and the same voting
+schedule in both votes. Authorities MUST reject noncompliant votes.
+
+<!-- Section 3.7 --> <a id='S3.7'></a>
+
+## Computing an ENDIVE.
+
+If a consensus-method is negotiated that is high enough to support
+ENDIVEs, then the authorities proceed as follows to transform the consensus
+sectoins above into an ENDIVE.
+
+The ParamSections from the consensus are used verbatim as the bodies of the
+`client-params` and `relay-params` fields.
+
+The fields that appear in each RelaySNIPInfo determine what goes
+into the SNIPRouterData for each relay. To build the relay section,
+first decide which relays appear according to the `key_min_count`
+field in the RelayRules. Then collate relays across all the votes
+by their keys, and see which ones are listed. For each key that
+appears in at least `key_min_count` votes, apply the RelayRules to
+each section of the RelayInfos for that key.
+
+The sig_params section is derived from fields in the meta section.
+Fields with identical names are simply copied; Lifespan values are
+copied to the corresponding documents (snip-lifetime as the lifespan
+for SNIPs and ENDIVEs, and c and s-param-lifetime as the lifespan
+for ParamDocs).
+
+To compute the signature nonce, use the signature digest algorithm
+to compute the digest of each input vote body, sort those digests
+lexicographically, and concatenate and hash those digests again.
+
+Routing indices are built according to named IndexRules, and grouped
+according to fields in the meta section. See "Constructing Indices" below.
+
+> (At this point extra fields may be copied from the Meta section of
+> each RelayInfo into the ENDIVERouterData depending on the meta
+> document; we do not, however, currently specify any case where this
+> is done.)
+
+<!-- Section 3.7.1 --> <a id='S3.7.1'></a>
+
+### Constructing indices
+
+After having built the list of relays, the authorities construct and
+encode the indices that appear in the ENDIVEs. The voted-upon
+GenericIndexRule values in the IndexSection of the consensus say how
+to build the indices in the ENDIVE, as follows.
+
+An `EdIndex` is built using the IndexType_Ed25519Id value, with the
+provided prefix and suffix values. Authorities don't need to expand
+this index in the ENDIVE, since the relays can compute it
+deterministically.
+
+An `RSAIndex` is built using the IndexType_RSAId type. Authorities
+don't need to expand this index in the ENDIVE, since the relays can
+compute it deterministically.
+
+A `BwIndex` is built using the IndexType_Weighted type. Each relay has a
+weight equal to some specified bandwidth field in its consensus
+RelayInfo. If a relay is missing any of the `required_flags` in
+its meta section, or if it does not have the specified bandwidth
+field, that relay's weight becomes 0.
+
+A `WeightedIndex` is built by computing a BwIndex, and then
+transforming each relay in the list according to the flags that it
+has set. Relays that match any set of flags in the WeightedIndex
+rule get their bandwidths multiplied by _all_ WeightVals that
+apply. Some WeightVals are computed according to special rules,
+such as "Wgg", "Weg", and so on. These are taken from the current
+dir-spec.txt.
+
+For both BwIndex and WeightedIndex values, authorities MUST scale
+the computed outputs so that no value is greater than UINT32_MAX;
+they MUST do by shifting all values right by lowest number of bits
+that achieves this.
+
+> We could specify a more precise algorithm, but this is simpler.
+
+Indices with the same IndexGroupId are placed in the same index
+group; index groups are ordered numerically.
+
+<!-- Section 3.8 --> <a id='S3.8'></a>
+
+## Computing a legacy consensus.
+
+When using a consensus method that supports Walking Onions, the
+legacy consensus is computed from the same data as the ENDIVE.
+Because the legacy consensus format will be frozen once Walking
+Onions is finalized, we specify this transformation directly, rather
+than in a more extensible way.
+
+The published time and descriptor digest are used directly.
+Microdescriptor negotiation proceeds as before. Bandwidths,
+measured bandwidths, descriptor digests, published times, flags, and
+rsa-id values are taken from the RelayMetaInfo section. Addresses,
+protovers, versions, and so on are taken from the RelaySNIPInfo. Header
+fields are all taken from the corresponding header fields in the
+MetaSection or the ClientParamsSection. All parameters are copied
+into the net-params field.
+
+<!-- Section 3.9 --> <a id='S3.9'></a>
+
+## Managing indices over time.
+
+> The present voting mechanism does not do a great job of handling
+> the authorities
+
+The semantic meaning of most IndexId values, as understood by
+clients should remain unchanging; if a client uses index 6 for
+middle nodes, 6 should _always_ mean "middle nodes".
+
+If an IndexId is going to change its meaning over time, it should
+_not_ be hardcoded by clients; it should instead be listed in the
+NetParams document, as the exit indices are in the `port-classes`
+field. (See also section 6 and appendix AH.) If such a field needs
+to change, it also needs a migration method that allows clients with
+older and newer parameters documents to exist at the same time.
+
+<!-- Section 4 --> <a id='S4'></a>
+
+# Relay operations: Receiving and expanding ENDIVEs
+
+Previously, we introduced a format for ENDIVEs to be transmitted
+from authorities to relays. To save on bandwidth, the relays
+download diffs rather than entire ENDIVEs. The ENDIVE format makes
+several choices in order to make these diffs small: the Merkle tree
+is omitted, and routing indices are not included directly.
+
+To address those issues, this document describes the steps that a
+relay needs to perform, upon receiving an ENDIVE document, to derive
+all the SNIPs for that ENDIVE.
+
+Here are the steps to be followed. We'll describe them in order,
+though in practice they could be pipelined somewhat. We'll expand
+further on each step later on.
+
+ 1. Compute routing indices positions.
+
+ 2. Compute truncated SNIPRouterData variations.
+
+ 3. Build signed SNIP data.
+
+ 4. Compute Merkle tree.
+
+ 5. Build authenticated SNIPs.
+
+Below we'll specify specific algorithms for these steps. Note that
+relays do not need to follow the steps of these algorithms exactly,
+but they MUST produce the same outputs as if they had followed them.
+
+<!-- Section 4.1 --> <a id='S4.1'></a>
+
+## Computing index positions.
+
+For every IndexId in every Index Group, the relay will compute the
+full routing index. Every routing index is a mapping from
+index position ranges (represented as 2-tuples) to relays, where the
+relays are represented as ENDIVERouterData members of the ENDIVE. The
+routing index must map every possible value of the index to exactly one
+relay.
+
+An IndexSpec field describes how the index is to be constructed. There
+are four types of IndexSpec: Raw, Raw Spans, Weighted, RSAId, and
+Ed25519Id. We'll describe how to build the indices for each.
+
+Every index may either have an integer key, or a binary-string
+key. We define the "successor" of an integer index as the succeeding
+integer. We define the "successor" of a binary string as the next
+binary string of the same length in lexicographical (memcmp) order. We
+define "predecessor" as the inverse of "successor". Both these
+operations "wrap around" the index.
+
+The algorithms here describe a set of invariants that are
+"verified". Relays SHOULD check each of these invariants;
+authorities MUST NOT generate any ENDIVEs that violate them. If a
+relay encounters an ENDIVE that cannot be verified, then the ENDIVE
+cannot be expanded.
+
+> NOTE: conceivably should there be some way to define an index as a
+> subset of another index, with elements weighted in different ways? In
+> other words, "Index a is index b, except multiply these relays by 0 and
+> these relays by 1.2". We can keep this idea sitting around in case there
+> turns out to be a use for it.
+
+<!-- Section 4.1.1 --> <a id='S4.1.1'></a>
+
+### Raw indices
+
+When the IndexType is Indextype_Raw, then its members are listed
+directly in the IndexSpec.
+
+ Algorithm: Expanding a "Raw" indexspec.
+
+ Let result_idx = {} (an empty mapping).
+
+ Let previous_pos = indexspec.first_index
+
+ For each element [i, pos2] of indexspec.index_ranges:
+
+ Verify that i is a valid index into the list of ENDIVERouterData.
+
+ Set pos1 = the successor of previous_pos.
+
+ Verify that pos1 and pos2 have the same type.
+
+ Append the mapping (pos1, pos2) => i to result_idx
+
+ Set previous_pos to pos2.
+
+ Verify that previous_pos = the predecessor of indexspec.first_index.
+
+ Return result_idx.
+
+<!-- Section 4.1.2 --> <a id='S4.1.2'></a>
+
+### Raw numeric indices
+
+If the IndexType is Indextype_RawNumeric, it is described by a set of
+spans on a 32-bit index range.
+
+ Algorithm: Expanding a RawNumeric index.
+
+ Let prev_pos = 0
+
+ For each element [i, span] of indexspec.index_ranges:
+
+ Verify that i is a valid index into the list of ENDIVERouterData.
+
+ Verify that prev_pos <= UINT32_MAX - span.
+
+ Let pos2 = prev_pos + span.
+
+ Append the mapping (pos1, pos2) => i to result_idx.
+
+ Let prev_pos = successor(pos2)
+
+ Verify that prev_pos = UINT32_MAX.
+
+ Return result_idx.
+
+<!-- Section 4.1.3 --> <a id='S4.1.3'></a>
+
+### Weighted indices
+
+If the IndexSpec type is Indextype_Weighted, then the index is
+described by assigning a probability weight to each of a number of relays.
+From these, we compute a series of 32-bit index positions.
+
+This algorithm uses 64-bit math, and 64-by-32-bit integer division.
+
+It requires that the sum of weights is no more than UINT32_MAX.
+
+ Algorithm: Expanding a "Weighted" indexspec.
+
+ Let total_weight = SUM(indexspec.index_weights)
+
+ Verify total_weight <= UINT32_MAX.
+
+ Let total_so_far = 0.
+
+ Let result_idx = {} (an empty mapping).
+
+ Define POS(b) = FLOOR( (b << 32) / total_weight).
+
+ For 0 <= i < LEN(indexspec.indexweights):
+
+ Let w = indexspec.indexweights[i].
+
+ Let lo = POS(total_so_far).
+
+ Let total_so_far = total_so_far + w.
+
+ Let hi = POS(total_so_far) - 1.
+
+ Append (lo, hi) => i to result_idx.
+
+ Verify that total_so_far = total_weight.
+
+ Verify that the last value of "hi" was UINT32_MAX.
+
+ Return result_idx.
+
+This algorithm is a bit finicky in its use of division, but it
+results in a mapping onto 32 bit integers that completely covers the
+space of available indices.
+
+<!-- Section 4.1.4 --> <a id='S4.1.4'></a>
+
+### RSAId indices
+
+If the IndexSpec type is Indextype_RSAId then the index is a set of
+binary strings describing the routers' legacy RSA identities, for
+use in the HSv2 hash ring.
+
+These identities are truncated to a fixed length. Though the SNIP
+format allows _variable_-length binary prefixes, we do not use this
+feature.
+
+ Algorithm: Expanding an "RSAId" indexspec.
+
+ Let R = [ ] (an empty list).
+
+ Take the value n_bytes from the IndexSpec.
+
+ For 0 <= b_idx < MIN( LEN(indexspec.members) * 8,
+ LEN(list of ENDIVERouterData) ):
+
+ Let b = the b_idx'th bit of indexspec.members.
+
+ If b is 1:
+ Let m = the b_idx'th member of the ENDIVERouterData list.
+
+ Verify that m has its RSAIdentityFingerprint set.
+
+ Let pos = m.RSAIdentityFingerprint, truncated to n_bytes.
+
+ Add (pos, b_idx) to the list R.
+
+ Return INDEX_FROM_RING_KEYS(R).
+
+ Sub-Algorithm: INDEX_FROM_RING_KEYS(R)
+
+ First, sort R according to its 'pos' field.
+
+ For each member (pos, idx) of the list R:
+
+ If this is the first member of the list R:
+ Let key_low = pos for the last member of R.
+ else:
+ Let key_low = pos for the previous member of R.
+
+ Let key_high = predecessor(pos)
+
+ Add (key_low, key_high) => idx to result_idx.
+
+ Return result_idx.
+
+<!-- Section 4.1.5 --> <a id='S4.1.5'></a>
+
+### Ed25519 indices
+
+If the IndexSpec type is Indextype_Ed25519, then the index is a set of
+binary strings describing the routers' positions in a hash ring,
+derived from their Ed25519 identity keys.
+
+This algorithm is a generalization of the one used for hsv3 rings,
+to be used to compute the hsv3 ring and other possible future
+derivatives.
+
+ Algorithm: Expanding an "Ed25519Id" indexspec.
+
+ Let R = [ ] (an empty list).
+
+ Take the values prefix, suffix, and n_bytes from the IndexSpec.
+
+ Let H() be the digest algorithm specified by d_alg from the
+ IndexSpec.
+
+ For 0 <= b_idx < MIN( LEN(indexspec.members) * 8,
+ LEN(list of ENDIVERouterData) ):
+
+ Let b = the b_idx'th bit of indexspec.members.
+
+ If b is 1:
+ Let m = the b_idx'th member of the ENDIVERouterData list.
+
+ Let key = m's ed25519 identity key, as a 32-byte value.
+
+ Compute pos = H(prefix || key || suffix)
+
+ Truncate pos to n_bytes.
+
+ Add (pos, b_idx) to the list R.
+
+ Return INDEX_FROM_RING_KEYS(R).
+
+<!-- Section 4.1.6 --> <a id='S4.1.6'></a>
+
+### Building a SNIPLocation
+
+After computing all the indices in an IndexGroup, relays combine
+them into a series of SNIPLocation objects. Each SNIPLocation
+MUST contain all the IndexId => IndexRange entries that point to a
+given ENDIVERouterData, for the IndexIds listed in an IndexGroup.
+
+ Algorithm: Build a list of SNIPLocation objects from a set of routing indices.
+
+ Initialize R as [ { } ] * LEN(relays) (A list of empty maps)
+
+ For each IndexId "ID" in the IndexGroup:
+
+ Let router_idx be the index map calculated for ID.
+ (This is what we computed previously.)
+
+ For each entry ( (LO, HI) => idx) in router_idx:
+
+ Let R[idx][ID] = (LO, HI).
+
+SNIPLocation objects are thus organized in the order in which they will
+appear in the Merkle tree: that is, sorted by the position of their
+corresponding ENDIVERouterData.
+
+Because SNIPLocation objects are signed, they must be encoded as "canonical"
+cbor, according to section 3.9 of RFC 7049.
+
+If R[idx] is {} (the empty map) for any given idx, then no SNIP will be
+generated for the SNIPRouterData at that routing index for this index group.
+
+<!-- Section 4.2 --> <a id='S4.2'></a>
+
+## Computing truncated SNIPRouterData.
+
+An index group can include an `omit_from_snips` field to indicate that
+certain fields from a SNIPRouterData should not be included in the
+SNIPs for that index group.
+
+Since a SNIPRouterData needs to be signed, this process has to be
+deterministic. Thus, the truncated SNIPRouterData should be computed by
+removing the keys and values for EXACTLY the keys listed and no more. The
+remaining keys MUST be left in the same order that they appeared in the
+original SNIPRouterData, and they MUST NOT be re-encoded.
+
+(Two keys are "the same" if and only if they are integers encoding the same
+value, or text strings with the same UT-8 content.)
+
+There is no need to compute a SNIPRouterData when no SNIP is going to be
+generated for a given router.
+
+<!-- Section 4.3 --> <a id='S4.3'></a>
+
+## Building the Merkle tree.
+
+After computing a list of (SNIPLocation, SNIPRouterData) for every entry
+in an index group, the relay needs to expand a Merkle tree to
+authenticate every SNIP.
+
+There are two steps here: First the relay generates the leaves, and then
+it generates the intermediate hashes.
+
+To generate the list of leaves for an index group, the relay first
+removes all entries from the (SNIPLocation, SNIPRouterData) list that
+have an empty index map. The relay then puts `n_padding_entries` "nil"
+entries at the end of the list.
+
+To generate the list of leaves for the whole Merkle tree, the relay
+concatenates these index group lists in the order in which they appear
+in the ENDIVE, and pads the resulting list with "nil" entries until the
+length of the list is a power of two: 2^`tree-depth` for some integer
+`tree-depth`. Let LEAF(IDX) denote the entry at position IDX in this
+list, where IDX is a D-bit bitstring. LEAF(IDX) is either a byte string
+or nil.
+
+The relay then recursively computes the hashes in the Merkle tree as
+follows. (Recall that `H_node()` and `H_leaf()` are hashes taking
+a bit-string PATH, a LIFESPAN and NONCE from the signature information,
+and a variable-length string ITEM.)
+
+ Recursive defintion: HM(PATH)
+
+ Given PATH a bitstring of length no more than tree-depth.
+
+ Define S:
+ S(nil) = an all-0 string of the same length as the hash output.
+ S(x) = x, for all other x.
+
+ If LEN(PATH) = tree-depth: (Leaf case.)
+ If LEAF(PATH) = nil:
+ HM(PATH) = nil.
+ Else:
+ HM(PATH) = H_node(PATH, LIFESPAN, NONCE, LEAF(PATH)).
+
+ Else:
+ Let LEFT = HM(PATH || 0)
+ Let RIGHT = HM(PATH || 1)
+ If LEFT = nil and RIGHT = nil:
+ HM(PATH) = nil
+ else:
+ HM(PATH) = H_node(PATH, LIFESPAN, NONCE, S(LEFT) || S(RIGHT))
+
+Note that entries aren't computed for "nil" leaves, or any node all of
+whose children are "nil". The "nil" entries only exist to place all
+leaves at a constant depth, and to enable spacing out different sections
+of the tree.
+
+If `signature-depth` for the ENDIVE is N, the relay does not need to
+compute any Merkle tree entries for PATHs of length shorter than N bits.
+
+<!-- Section 4.4 --> <a id='S4.4'></a>
+
+## Assembling the SNIPs
+
+Finally, the relay has computed a list of encoded (SNIPLocation,
+RouterData) values, and a Merkle tree to authenticate them. At this
+point, the relay builds them into SNIPs, using the `sig_params` and
+`signatures` from the ENDIVE.
+
+ Algorithm: Building a SNIPSignature for a SNIP.
+
+ Given a non-nil (SNIPLocation, RouterData) at leaf position PATH.
+
+ Let SIG_IDX = PATH, truncated to signature-depth bits.
+ Consider SIG_IDX as an integer.
+
+ Let Sig = signatures[SIG_IDX] -- either the SingleSig or the MultiSig
+ for this snip.
+
+ Let HashPath = [] (an empty list).
+ For bitlen = signature-depth+1 ... tree-depth-1:
+ Let X = PATH, truncated to bitlen bits.
+ Invert the final bit of PATH.
+ Append HM(PATH) to HashPath.
+
+ The SnipSignature's signature values is Sig, and its merkle_path is
+ HashPath.
+
+<!-- Section 4.5 --> <a id='S4.5'></a>
+
+## Implementation considerations
+
+A relay only needs to hold one set of SNIPs at a time: once one
+ENDIVE's SNIPs have been extracted, then the SNIPs from the previous
+ENDIVE can be discarded.
+
+To save memory, a relay MAY store SNIPs to disk, and mmap them as
+needed.
+
+<!-- Section 5 --> <a id='S5'></a>
+
+# Extending circuits with Walking Onions
+
+When a client wants to extend a circuit, there are several
+possibilities. It might need to extend to an unknown relay with
+specific properties. It might need to extend to a particular relay
+from which it has received a SNIP before. In both cases, there are
+changes to be made in the circuit extension process.
+
+Further, there are changes we need to make for the handshake between
+the extending relay and the target relay. The target relay is no
+longer told by the client which of its onion keys it should use... so
+the extending relay needs to tell the target relay which keys are in
+the SNIP that the client is using.
+
+<!-- Section 5.1 --> <a id='S5.1'></a>
+
+## Modifying the EXTEND/CREATE handshake
+
+First, we will require that proposal 249 (or some similar proposal
+for wide CREATE and EXTEND cells) is in place, so that we can have
+EXTEND cells larger than can fit in a single cell. (See
+319-wide-everything.md for an example proposal to supersede 249.)
+
+We add new fields to the CREATE2 cell so that relays can send each
+other more information without interfering with the client's part of
+the handshake.
+
+The CREATE2, CREATED2, and EXTENDED2 cells change as follows:
+
+ struct create2_body {
+ // old fields
+ u16 htype; // client handshake type
+ u16 hlen; // client handshake length
+ u8 hdata[hlen]; // client handshake data.
+
+ // new fields
+ u8 n_extensions;
+ struct extension extension[n_extensions];
+ }
+
+ struct created2_body {
+ // old fields
+ u16 hlen;
+ u8 hdata[hlen];
+
+ // new fields
+ u8 n_extensions;
+ struct extension extension[n_extensions];
+ }
+
+ struct truncated_body {
+ // old fields
+ u8 errcode;
+
+ // new fields
+ u8 n_extensions;
+ struct extension extension[n_extensions];
+ }
+
+ // EXTENDED2 cells can now use the same new fields as in the
+ // created2 cell.
+
+ struct extension {
+ u16 type;
+ u16 len;
+ u8 body[len];
+ }
+
+These extensions are defined by this proposal:
+
+ [01] -- `Partial_SNIPRouterData` -- Sent from an extending relay
+ to a target relay. This extension holds one or more fields
+ from the SNIPRouterData that the extending relay is using,
+ so that the target relay knows (for example) what keys to
+ use. (These fields are determined by the
+ "forward_with_extend" field in the ENDIVE.)
+
+ [02] -- Full_SNIP -- an entire SNIP that was used in an attempt to
+ extend the circuit. This must match the client's provided
+ index position.
+
+ [03] -- Extra_SNIP -- an entire SNIP that was not used to extend
+ the circuit, but which the client requested anyway. This
+ can be sent back from the extending relay when the client
+ specifies multiple index positions, or uses a nonzero "nth" value
+ in their `snip_index_pos` link specifier.
+
+ [04] -- SNIP_Request -- a 32-bit index position, or a single zero
+ byte, sent away from the client. If the byte is 0, the
+ originator does not want a SNIP. Otherwise, the
+ originator does want a SNIP containing the router and the
+ specified index. Other values are unspecified.
+
+By default, EXTENDED2 cells are sent with a SNIP iff the EXTENDED2
+cell used a `snip_index_pos` link specifier, and CREATED2 cells are
+not sent with a SNIP.
+
+<!-- Section 5.1.1 --> <a id='S5.1.1'></a>
+
+### New link specifiers
+
+We add a new link specifier type for a router index, using the
+following coding for its contents:
+
+ /* Using trunnel syntax here. */
+ struct snip_index_pos {
+ u32 index_id; // which index is it?
+ u8 nth; // how many SNIPs should be skipped/included?
+ u8 index_pos[]; // extends to the end of the link specifier.
+ }
+
+The `index_pos` field can be longer or shorter than the actual width of
+the router index. If it is too long, it is truncated. If it is too
+short, it is extended with zero-valued bytes.
+
+Any number of these link specifiers may appear in an EXTEND cell.
+If there is more then one, then they should appear in order of
+client preference; the extending relay may extend to any of the
+listed routers.
+
+This link specifier SHOULD NOT be used along with IPv4, IPv6, RSA
+ID, or Ed25519 ID link specifiers. Relays receiving such a link
+specifier along with a `snip_index_pos` link specifier SHOULD reject
+the entire EXTEND request.
+
+If `nth` is nonzero, then link specifier means "the n'th SNIP after
+the one defined by the SNIP index position." A relay MAY reject
+this request if `nth` is greater than 4. If the relay does not
+reject this request, then it MUST include all snips between
+`index_pos` and the one that was actually used in an Extra_Snip
+extension. (Otherwise, the client would not be able to verify that
+it had gotten the correct SNIP.)
+
+> I've avoided use of CBOR for these types, under the assumption that we'd
+> like to use CBOR for directory stuff, but no more. We already have
+> trunnel-like objects for this purpose.
+
+<!-- Section 5.2 --> <a id='S5.2'></a>
+
+## Modified ntor handshake
+
+We adapt the ntor handshake from tor-spec.txt for this use, with the
+following main changes.
+
+ * The NODEID and KEYID fields are omitted from the input.
+ Instead, these fields _may_ appear in a PartialSNIPData extension.
+
+ * The NODEID and KEYID fields appear in the reply.
+
+ * The NODEID field is extended to 32 bytes, and now holds the
+ relay's ed25519 identity.
+
+So the client's message is now:
+
+ CLIENT_PK [32 bytes]
+
+And the relay's reply is now:
+
+ NODEID [32 bytes]
+ KEYID [32 bytes]
+ SERVER_PK [32 bytes]
+ AUTH [32 bytes]
+
+otherwise, all fields are computed as described in tor-spec.
+
+When this handshake is in use, the hash function is SHA3-256 and keys
+are derived using SHAKE-256, as in rend-spec-v3.txt.
+
+> Future work: We may wish to update this choice of functions
+> between now and the implementation date, since SHA3 is a bit
+> pricey. Perhaps one of the BLAKEs would be a better choice. If
+> so, we should use it more generally. On the other hand, the
+> presence of public-key operations in the handshake _probably_
+> outweighs the use of SHA3.
+
+We will have to give this version of the handshake a new handshake
+type.
+
+<!-- Section 5.3 --> <a id='S5.3'></a>
+
+## New relay behavior on EXTEND and CREATE failure.
+
+If an EXTEND2 cell based on an routing index fails, the relay should
+not close the circuit, but should instead send back a TRUNCATED cell
+containing the SNIP in an extension.
+
+If a CREATE2 cell fails and a SNIP was requested, then instead of
+sending a DESTROY cell, the relay SHOULD respond with a CREATED2
+cell containing 0 bytes of handshake data, and the SNIP in an
+extension. Clients MAY re-extend or close the circuit, but should
+not leave it dangling.
+
+<!-- Section 5.4 --> <a id='S5.4'></a>
+
+## NIL handshake type
+
+We introduce a new handshake type, "NIL". The NIL handshake always
+fails. A client's part of the NIL handshake is an empty bytestring;
+there is no server response that indicates success.
+
+The NIL handshake can used by the client when it wants to fetch a
+SNIP without creating a circuit.
+
+Upon receiving a request to extend with the NIL circuit type, a
+relay SHOULD NOT actually open any connection or send any data to
+the target relay. Instead, it should respond with a TRUNCATED cell
+with the SNIP(s) that the client requested in one or more Extra_SNIP
+extensions.
+
+<!-- Section 5.5 --> <a id='S5.5'></a>
+
+## Padding handshake cells to a uniform size
+
+To avoid leaking information, all CREATE/CREATED/EXTEND/EXTENDED
+cells SHOULD be padded to the same sizes. In all cases, the amount
+of padding is controlled by a set of network parameters:
+"create-pad-len", "created-pad-len", "extend-pad-len" and
+"extended-pad-len". These parameters determine the minimum length
+that the cell body or relay cell bodies should be.
+
+If a cell would be sent whose body is less than the corresponding
+parameter value, then the sender SHOULD pad the body by adding
+zero-valued bytes to the cell body. As usual, receivers MUST ignore
+extra bytes at the end of cells.
+
+> ALTERNATIVE: We could specify a more complicated padding
+> mechanism, eg. 32 bytes of zeros then random bytes.
+
+
+<!-- Section 6 --> <a id='S6'></a>
+
+# Client behavior with walking onions
+
+Today's Tor clients have several behaviors that become somewhat
+more difficult to implement with Walking Onions. Some of these
+behaviors are essential and achievable. Others can be achieved with
+some effort, and still others appear to be incompatible with the
+Walking Onions design.
+
+<!-- Section 6.1 --> <a id='S6.1'></a>
+
+## Bootstrapping and guard selection
+
+When a client first starts running, it has no guards on the Tor
+network, and therefore can't start building circuits immediately.
+To produce a list of possible guards, the client begins connecting
+to one or more fallback directories on their ORPorts, and building
+circuits through them. These are 3-hop circuits. The first hop of
+each circuit is the fallback directory; the second and third hops
+are chosen from the Middle routing index. At the third hop, the
+client then sends an informational request for a guard's SNIP. This
+informational request is an EXTEND2 cell with handshake type NIL,
+using a random spot on the Guard routing index.
+
+Each such request yields a single SNIP that the client will store.
+These SNIPs, in the order in which they were _requested_, will form the
+client's list of "Sampled" guards as described in guard-spec.txt.
+
+Clients SHOULD ensure that their sampled guards are not
+linkable to one another. In particular, clients SHOULD NOT add more
+than one guard retrieved from the same third hop on the same
+circuit. (If it did, that third hop would realize that some client using
+guard A was also using guard B.)
+
+> Future work: Is this threat real? It seems to me that knowing one or two
+> guards at a time in this way is not a big deal, though knowing the whole
+> set would sure be bad. However, we shouldn't optimize this kind of
+> defense away until we know that it's actually needless.
+
+If a client's network connection or choice of entry nodes is heavily
+restricted, the client MAY request more than one guard at a time, but if
+it does so, it SHOULD discard all but one guard retrieved from each set.
+
+After choosing guards, clients will continue to use them even after
+their SNIPs expire. On the first circuit through each guard after
+opening a channel, clients should ask that guard for a fresh SNIP for
+itself, to ensure that the guard is still listed in the consensus, and
+to keep the client's information up-to-date.
+
+<!-- Section 6.2 --> <a id='S6.2'></a>
+
+## Using bridges
+
+As now, clients are configured to use a bridge by using an address and a
+public key for the bridge. Bridges behave like guards, except that they
+are not listed in any directory or ENDIVE, and so cannot prove
+membership when the client connects to them.
+
+On the first circuit through each channel to a bridge, the client
+asks that bridge for a SNIP listing itself in the `Self` routing
+index. The bridge responds with a self-created unsigned SNIP:
+
+ ; This is only valid when received on an authenticated connection
+ ; to a bridge.
+ UnsignedSNIP = [
+ ; There is no signature on this SNIP.
+ auth : nil,
+
+ ; Next comes the location of the SNIP within the ENDIVE. This
+ ; SNIPLocation will list only the Self index.
+ index : bstr .cbor SNIPLocation,
+
+ ; Finally comes the information about the router.
+ router : bstr .cbor SNIPRouterData,
+ ]
+
+*Security note*: Clients MUST take care to keep UnsignedSNIPs separated
+from signed ones. These are not part of any ENDIVE, and so should not be
+used for any purpose other than connecting through the bridge that the
+client has received them from. They should be kept associated with that
+bridge, and not used for any other, even if they contain other link
+specifiers or keys. The client MAY use link specifiers from the
+UnsignedSNIP on future attempts to connect to the bridge.
+
+<!-- Section 6.3 --> <a id='S6.3'></a>
+
+## Finding relays by exit policy
+
+To find a relay by exit policy, clients might choose the exit
+routing index corresponding to the exit port they want to use. This
+has negative privacy implications, however, since the middle node
+discovers what kind of exit traffic the client wants to use.
+Instead, we support two other options.
+
+First, clients may build anonymous three-hop circuits and then use those
+circuits to request the SNIPs that they will use for their exits. This
+may, however, be inefficient.
+
+Second, clients may build anonymous three-hop circuits and then use a
+BEGIN cell to try to open the connection when they want. When they do
+so, they may include a new flag in the begin cell, "DVS" to enable
+Delegated Verifiable Selection. As described in the Walking Onions
+paper, DVS allows a relay that doesn't support the requested port to
+instead send the client the SNIP of a relay that does. (In the paper,
+the relay uses a digest of previous messages to decide which routing
+index to use. Instead, we have the client send an index field.)
+
+This requires changes to the BEGIN and END cell formats. After the
+"flags" field in BEGIN cells, we add an extension mechanism:
+
+ struct begin_cell {
+ nulterm addr_port;
+ u32 flags;
+ u8 n_extensions;
+ struct extension exts[n_extensions];
+ }
+
+We allow the `snip_index_pos` link specifier type to appear as a begin
+extension.
+
+END cells will need to have a new format that supports including policy and
+SNIP information. This format is enabled whenever a new `EXTENDED_END_CELL`
+flag appears in the begin cell.
+
+ struct end_cell {
+ u8 tag IN [ 0xff ]; // indicate that this isn't an old-style end cell.
+ u8 reason;
+ u8 n_extensions;
+ struct extension exts[n_extensions];
+ }
+
+We define three END cell extensions. Two types are for addresses, that
+indicate what address was resolved and the associated TTL:
+
+ struct end_ext_ipv4 {
+ u32 addr;
+ u32 ttl;
+ }
+ struct end_ext_ipv6 {
+ u8 addr[16];
+ u32 ttl;
+ }
+
+One new END cell extension is used for delegated verifiable selection:
+
+ struct end_ext_alt_snip {
+ u16 index_id;
+ u8 snip[..];
+ }
+
+This design may require END cells to become wider; see
+319-wide-everything.md for an example proposal to
+supersede proposal 249 and allow more wide cell types.
+
+<!-- Section 6.4 --> <a id='S6.4'></a>
+
+## Universal path restrictions
+
+There are some restrictions on Tor paths that all clients should obey,
+unless they are configured not to do so. Some of these restrictions
+(like "start paths with a Guard node" or "don't use an Exit as a middle
+when Exit bandwidth is scarce") are captured by the index system. Some
+other restrictions are not. Here we describe how to implement those.
+
+The general approach taken here is "build and discard". Since most
+possible paths will not violate these universal restrictions, we
+accept that a fraction of the paths built will not be usable.
+Clients tear them down a short time after they are built.
+
+Clients SHOULD discard a circuit if, after it has been built, they
+find that it contains the same relay twice, or it contains more than
+one relay from the same family or from the same subnet.
+
+Clients MAY remember the SNIPs they have received, and use those
+SNIPs to avoid index ranges that they would automatically reject.
+Clients SHOULD NOT store any SNIP for longer than it is maximally
+recent.
+
+> NOTE: We should continue to monitor the fraction of paths that are
+> rejected in this way. If it grows too high, we either need to amend
+> the path selection rules, or change authorities to e.g. forbid more
+> than a certain fraction of relay weight in the same family or subnet.
+
+> FUTURE WORK: It might be a good idea, if these restrictions truly are
+> 'universal', for relays to have a way to say "You wouldn't want that
+> SNIP; I am giving you the next one in sequence" and send back both
+> SNIPs. This would need some signaling in the EXTEND/EXTENDED cells.
+
+<!-- Section 6.5 --> <a id='S6.5'></a>
+
+## Client-configured path restrictions
+
+Sometimes users configure their clients with path restrictions beyond
+those that are in ordinary use. For example, a user might want to enter
+only from US relays, but never exit from US. Or they might be
+configured with a short list of vanguards to use in their second
+position.
+
+<!-- Section 6.5.1 --> <a id='S6.5.1'></a>
+
+### Handling "light" restrictions
+
+If a restriction only excludes a small number of relays, then clients
+can continue to use the "build and discard" methodology described above.
+
+<!-- Section 6.5.2 --> <a id='S6.5.2'></a>
+
+### Handling some "heavy" restrictions
+
+Some restrictions can exclude most relays, and still be reasonably easy
+to implement if they only _include_ a small fraction of relays. For
+example, if the user has a EntryNodes restriction that contains only a
+small group of relays by exact IP address, the client can connect or
+extend to one of those addresses specifically.
+
+If we decide IP ranges are important, that IP addresses without
+ports are important, or that key specifications are important, we
+can add routing indices that list relays by IP, by RSAId, or by
+Ed25519 Id. Clients could then use those indices to remotely
+retrieve SNIPs, and then use those SNIPs to connect to their
+selected relays.
+
+> Future work: we need to decide how many of the above functions to actually
+> support.
+
+<!-- Section 6.5.3 --> <a id='S6.5.3'></a>
+
+### Recognizing too-heavy restrictions
+
+The above approaches do not handle all possible sets of restrictions. In
+particular, they do a bad job for restrictions that ban a large fraction
+of paths in a way that is not encodeable in the routing index system.
+
+If there is substantial demand for such a path restriction, implementors
+and authority operators should figure out how to implement it in the
+index system if possible.
+
+Implementations SHOULD track what fraction of otherwise valid circuits
+they are closing because of the user's configuration. If this fraction
+is above a certain threshold, they SHOULD issue a warning; if it is
+above some other threshold, they SHOULD refuse to build circuits
+entirely.
+
+> Future work: determine which fraction appears in practice, and use that to
+> set the appropriate thresholds above.
+
+<!-- Section 7 --> <a id='S7'></a>
+
+# Using and providing onion services with Walking Onions
+
+Both live versions of the onion service design rely on a ring of
+hidden service directories for use in uploading and downloading
+hidden service descriptors. With Walking Onions, we can use routing
+indices based on Ed25519 or RSA identity keys to retrieve this data.
+
+(The RSA identity ring is unchanging, whereas the Ed25519 ring
+changes daily based on the shared random value: for this reason, we
+have to compute two simultaneous indices for Ed25519 rings: one for
+the earlier date that is potentially valid, and one for the later
+date that is potentially valid. We call these `hsv3-early` and
+`hsv3-late`.)
+
+Beyond the use of these indices, however, there are other steps that
+clients and services need to take in order to maintain their privacy.
+
+<!-- Section 7.1 --> <a id='S7.1'></a>
+
+## Finding HSDirs
+
+When a client or service wants to contact an HSDir, it SHOULD do so
+anonymously, by building a three-hop anonymous circuit, and then
+extending it a further hop using the snip_span link specifier to
+upload to any of the first 3 replicas on the ring. Clients SHOULD
+choose an 'nth' at random; services SHOULD upload to each replica.
+
+Using a full 80-bit or 256-bit index position in the link specifier
+would leak the chosen service to somebody other than the directory.
+Instead, the client or service SHOULD truncate the identifier to a
+number of bytes equal to the network parameter `hsv2-index-bytes` or
+`hsv3-index-bytes` respectively. (See Appendix C.)
+
+<!-- Section 7.2 --> <a id='S7.2'></a>
+
+## SNIPs for introduction points
+
+When services select an introduction point, they should include the
+SNIP for the introduction point in their hidden service directory
+entry, along with the introduction-point fields. The format for
+this entry is:
+
+ "snip" NL snip NL
+ [at most once per introduction points]
+
+Clients SHOULD begin treating the link specifier and onion-key
+fields of each introduction point as optional when the "snip" field
+is present, and when the `hsv3-tolerate-no-legacy` network parameter
+is set to 1. If either of these fields _is_ present, and the SNIP is
+too, then these fields MUST match those listed in the SNIPs.
+Clients SHOULD reject descriptors with mismatched fields, and alert
+the user that the service may be trying a partitioning attack.
+The "legacy-key" and "legacy-key-cert" fields, if present, should be
+checked similarly.
+
+> Using the SNIPs in these ways allows services to prove that their
+> introduction points have actually been listed in the consensus
+> recently. It also lets clients use introduction point features
+> that the relay might not understand.
+
+Services should include these fields based on a set of network
+parameters: `hsv3-intro-snip` and `hsv3-intro-legacy-fields`.
+(See appendix C.)
+
+Clients should use these fields only when Walking Onions support is
+enabled; see section 09.
+
+<!-- Section 7.3 --> <a id='S7.3'></a>
+
+## SNIPs for rendezvous points
+
+When a client chooses a rendezvous point for a v3 onion service, it
+similarly has the opportunity to include the SNIP of its rendezvous
+point in the encrypted part of its INTRODUCE cell. (This may cause
+INTRODUCE cells to become fragmented; see proposal about fragmenting
+relay cells.)
+
+> Using the SNIPs in these ways allows services to prove that their
+> introduction points have actually been listed in the consensus
+> recently. It also lets services use introduction point features
+> that the relay might not understand.
+
+To include the SNIP, the client places it in an extension in the
+INTRODUCE cell. The onion key can now be omitted[*], along with
+the link specifiers.
+
+> [*] Technically, we use a zero-length onion key, with a new type
+> "implicit in SNIP".
+
+To know whether the service can recognize this kind of cell, the
+client should look for the presence of a "snips-allowed 1" field in
+the encrypted part of the hidden service descriptor.
+
+In order to prevent partitioning, services SHOULD NOT advertise
+"snips-allowed 1" unless the network parameter
+"hsv3-rend-service-snip" is set to 1. Clients SHOULD NOT use this
+field unless "hsv3-rend-client-snip" is set to 1.
+
+<!-- Section 7.4 --> <a id='S7.4'></a>
+
+## TAP keys and where to find them
+
+If v2 hidden services are still supported when Walking Onions arrives
+on the network, we have two choices: We could migrate them to use
+ntor keys instead of TAP, or we could provide a way for TAP keys to
+be advertised with Walking Onions.
+
+The first option would appear to be far simpler. See
+proposal draft 320-tap-out-again.md.
+
+The latter option would require us to put RSA-1024 keys in SNIPs, or
+put a digest of them in SNIPs and give some way to retrieve them
+independently.
+
+(Of course, it's possible that we will have v2 onion services
+deprecated by the time Walking Onions is implemented. If so, that
+will simplify matters a great deal too.)
+
+
+<!-- Section 8 --> <a id='S8'></a>
+
+# Tracking Relay honesty
+
+Our design introduces an opportunity for dishonest relay behavior:
+since multiple ENDIVEs are valid at the same time, a malicious relay
+might choose any of several possible SNIPs in response to a client's
+routing index value.
+
+Here we discuss several ways to mitigate this kind of attack.
+
+<!-- Section 8.1 --> <a id='S8.1'></a>
+
+## Defense: index stability
+
+First, the voting process should be designed such that relays do not
+needlessly move around the routing index. For example, it would
+_not_ be appropriate to add an index type whose value is computed by
+first putting the relays into a pseudorandom order. Instead, index
+voting should be deterministic and tend to give similar outputs for
+similar inputs.
+
+This proposal tries to achieve this property in its index voting
+algorithms. We should measure the degree to which we succeed over
+time, by looking at all of the ENDIVEs that are valid at any
+particular time, and sampling several points for each index to see
+how many distinct relays are listed at each point, across all valid
+ENDIVEs.
+
+We do not need this stability property for routing indices whose
+purpose is nonrandomized relay selection, such as those indices used
+for onion service directories.
+
+<!-- Section 8.2 --> <a id='S8.2'></a>
+
+## Defense: enforced monotonicity
+
+Once an honest relay has received an ENDIVE, it has no reason to
+keep any previous ENDIVEs or serve SNIPs from them. Because of
+this, relay implementations SHOULD ensure that no data is served
+from a new ENDIVE until all the data from an old ENDIVE is
+thoroughly discarded.
+
+Clients and relays can use this monotonicity property to keep relays
+honest: once a relay has served a SNIP with some timestamp `T`, that
+relay should never serve any other SNIP with a timestamp earlier than
+`T`. Clients SHOULD track the most recent SNIP timestamp that they
+have received from each of their guards, and MAY track the most
+recent SNIP timestamps that they have received from other relays as
+well.
+
+<!-- Section 8.3 --> <a id='S8.3'></a>
+
+## Defense: limiting ENDIVE variance within the network.
+
+The primary motivation for allowing long (de facto) lifespans on
+today's consensus documents is to keep the network from grinding to
+a halt if the authorities fail to reach consensus for a few hours.
+But in practice, _if_ there is a consensus, then relays should have
+it within an hour or two, so they should not be falling a full day out
+of date.
+
+Therefore we can potentially add a client behavior that, within N
+minutes after the client has seen any SNIP with timestamp `T`,
+the client should not accept any SNIP with timestamp earlier than
+`T - Delta`.
+
+Values for N and Delta are controlled by network parameters
+(`enforce-endive-dl-delay-after` and `allow-endive-dl-delay`
+respectively in appendix C). N should be about as long as we expect
+it to take for a single ENDIVE to propagate to all the relays on the
+network; Delta should be about as long as we would like relays to go
+between updating ENDIVEs under ideal circumstances.
+
+<!-- Section 9 --> <a id='S9'></a>
+
+# Migrating to Walking Onions
+
+This proposal is a major change in the Tor network that will
+eventually require the participation of all relays [*], and will make
+clients who support it distinguishable from clients that don't.
+
+> [*] Technically, the last relay in the path doesn't need support.
+
+To keep the compatibility issues under control, here is the order in which it
+should be deployed on the network.
+
+1. First, authorities should add support for voting on ENDIVEs.
+
+2. Relays may immediately begin trying to download and reconstruct
+ ENDIVEs. (Relay versions are public, so they leak nothing by
+ doing this.)
+
+3. Once a sufficient number of authorities are voting on ENDIVEs and
+ unlikely to downgrade, relays should begin serving parameter documents
+ and responding to walking-onion EXTEND and CREATE cells. (Again,
+ relay versions are public, so this doesn't leak.)
+
+4. In parallel with relay support, Tor should also add client
+ support for Walking Onions. This should be disabled by default,
+ however, since it will only be usable with the subset of relays
+ that support Walking Onions, and since it would make clients
+ distinguishable.
+
+5. Once enough of the relays (possibly, all) support Walking Onions,
+ the client support can be turned on. They will not be able to
+ use old relays that do not support Walking Onions.
+
+6. Eventually, relays that do not support Walking Onions should not
+ be listed in the consensus.
+
+Client support for Walking Onions should be enabled or disabled, at
+first, with a configuration option. Once it seems stable, the
+option should have an "auto" setting that looks at a network
+parameter. This parameter should NOT be a simple "on" or "off",
+however: it should be the minimum client version whose support for
+Walking Onions is believed to be correct.
+
+<!-- Section 9.1 --> <a id='S9.1'></a>
+
+## Future work: migrating away from sedentary onions
+
+Once all clients are using Walking Onions, we can take a pass
+through the Tor specifications and source code to remove
+no-longer-needed code.
+
+Clients should be the first to lose support for old directories,
+since nobody but the clients depends on the clients having them.
+Only after obsolete clients represent a very small fraction of the
+network should relay or authority support be disabled.
+
+Some fields in router descriptors become obsolete with Walking
+Onions, and possibly router descriptors themselves should be
+replaced with cbor objects of some kind. This can only happen,
+however, after no descriptor users remain.
+
+<!-- Section A --> <a id='SA'></a>
+
+# Appendices
+
+<!-- Section A.1 --> <a id='SA.1'></a>
+
+## Appendix A: Glossary
+
+I'm going to put a glossary here so I can try to use these terms
+consistently.
+
+*SNIP* -- A "Separable Network Index Proof". Each SNIP contains the
+information necessary to use a single Tor relay, and associates the relay
+with one or more index ranges. SNIPs are authenticated by the directory
+authorities.
+
+*ENDIVE* -- An "Efficient Network Directory with Individually Verifiable
+Entries". An ENDIVE is a collection of SNIPS downloaded by relays,
+authenticated by the directory authorities.
+
+*Routing index* -- A routing index is a map from binary strings to relays,
+with some given property. Each relay that is in the routing index is
+associated with a single *index range*.
+
+*Index range* -- A range of positions withing a routing index. Each range
+ contains many positions.
+
+*Index position* -- A single value within a routing index. Every position in
+ a routing index corresponds to a single relay.
+
+*ParamDoc* -- A network parameters document, describing settings for the
+ whole network. Clients download this infrequently.
+
+*Index group* -- A collection of routing indices that are encoded in the same
+ SNIPs.
+
+<!-- Section A.2 --> <a id='SA.2'></a>
+
+## Appendix B: More cddl definions
+
+ ; These definitions are used throughout the rest of the
+ ; proposal
+
+ ; Ed25519 keys are 32 bytes, and that isn't changing.
+ Ed25519PublicKey = bstr .size 32
+
+ ; Curve25519 keys are 32 bytes, and that isn't changing.
+ Curve25519PublicKey = bstr .size 32
+
+ ; 20 bytes or fewer: legacy RSA SHA1 identity fingerprint.
+ RSAIdentityFingerprint = bstr
+
+ ; A 4-byte integer -- or to be cddl-pedantic, one that is
+ ; between 0 and UINT32_MAX.
+ uint32 = uint .size 4
+
+ ; Enumeration to define integer equivalents for all the digest algorithms
+ ; that Tor uses anywhere. Note that some of these are not used in
+ ; this spec, but are included so that we can use this production
+ ; whenever we need to refer to a hash function.
+ DigestAlgorithm = &(
+ NoDigest: 0,
+ SHA1 : 1, ; deprecated.
+ SHA2-256: 2,
+ SHA2-512: 3,
+ SHA3-256: 4,
+ SHA3-512: 5,
+ Kangaroo12-256: 6,
+ Kangaroo12-512: 7,
+ )
+
+ ; A digest is represented as a binary blob.
+ Digest = bstr
+
+ ; Enumeration for different signing algorithms.
+ SigningAlgorithm = &(
+ RSA-OAEP-SHA1 : 1, ; deprecated.
+ RSA-OAEP-SHA256: 2, ; deprecated.
+ Ed25519 : 3,
+ Ed448 : 4,
+ BLS : 5, ; Not yet standardized.
+ )
+
+ PKAlgorithm = &(
+ SigningAlgorithm,
+
+ Curve25519: 100,
+ Curve448 : 101
+ )
+
+ KeyUsage = &(
+ ; A master unchangeable identity key for this authority. May be
+ ; any signing key type. Distinct from the authority's identity as a
+ ; relay.
+ AuthorityIdentity: 0x10,
+ ; A medium-term key used for signing SNIPs, votes, and ENDIVEs.
+ SNIPSigning: 0x11,
+
+ ; These are designed not to collide with the "list of certificate
+ ; types" or "list of key types" in cert-spec.txt
+ )
+
+ CertType = &(
+ VotingCert: 0x12,
+ ; These are designed not to collide with the "list of certificate
+ ; types" in cert-spec.txt.
+ )
+
+ LinkSpecifier = bstr
+
+<!-- Section A.3 --> <a id='SA.3'></a>
+
+## Appendix C: new numbers to assign.
+
+Relay commands:
+
+* We need a new relay command for "FRAGMENT" per proposal 319.
+
+CREATE handshake types:
+
+* We need a type for the NIL handshake.
+
+* We need a handshake type for the new ntor handshake variant.
+
+Link specifiers:
+
+* We need a link specifier for extend-by-index.
+
+* We need a link specifier for dirport URL.
+
+Certificate Types and Key Types:
+
+* We need to add the new entries from CertType and KeyUsage to
+ cert-spec.txt, and possibly merge the two lists.
+
+Begin cells:
+
+* We need a flag for Delegated Verifiable Selection.
+
+* We need an extension type for extra data, and a value for indices.
+
+End cells:
+
+* We need an extension type for extra data, a value for indices, a
+ value for IPv4 addresses, and a value for IPv6 addresses.
+
+Extensions for decrypted INTRODUCE2 cells:
+
+* A SNIP for the rendezvous point.
+
+Onion key types for decrypted INTRODUCE2 cells:
+
+* An "onion key" to indicate that the onion key for the rendezvous point is
+ implicit in the SNIP.
+
+New URLs:
+
+* A URL for fetching ENDIVEs.
+
+* A URL for fetching client / relay parameter documents
+
+* A URL for fetching detached SNIP signatures.
+
+Protocol versions:
+
+(In theory we could omit many new protovers here, since being listed
+in an ENDIVE implies support for the new protocol variants. We're
+going to use new protovers anyway, however, since doing so keeps our
+numbering consistent.)
+
+We need new versions for these subprotocols:
+
+* _Relay_ to denote support for new handshake elements.
+
+* _DirCache_ to denote support for ENDIVEs, paramdocs, binary diffs, etc.
+
+* _Cons_ to denote support for ENDIVEs
+
+
+<!-- Section A.4 --> <a id='SA.4'></a>
+
+## Appendix D: New network parameters.
+
+We introduce these network parameters:
+
+From section 5:
+
+* `create-pad-len` -- Clients SHOULD pad their CREATE cell bodies
+ to this size.
+
+* `created-pad-len` -- Relays SHOULD pad their CREATED cell bodies to this
+ size.
+
+* `extend-pad-len` -- Clients SHOULD pad their EXTEND cell bodies to this
+ size.
+
+* `extended-pad-len` -- Relays SHOULD pad their EXTENDED cell bodies to this
+size.
+
+From section 7:
+
+* `hsv2-index-bytes` -- how many bytes to use when sending an hsv2 index
+ position to look up a hidden service directory. Min: 1,
+ Max: 40. Default: 4.
+
+* `hsv3-index-bytes` -- how many bytes to use when sending an hsv3 index
+ position to look up a hidden service directory. Min: 1,
+ Max: 128. Default: 4.
+
+* `hsv3-intro-legacy-fields` -- include legacy fields in service descriptors.
+ Min: 0. Max: 1. Default: 1.
+
+* `hsv3-intro-snip` -- include intro point SNIPs in service descriptors.
+ Min: 0. Max: 1. Default: 0.
+
+* `hsv3-rend-service-snip` -- Should services advertise and accept rendezvous
+ point SNIPs in INTRODUCE2 cells? Min: 0. Max: 1. Default: 0.
+
+* `hsv3-rend-client-snip` -- Should clients place rendezvous point SNIPS in
+ INTRODUCE2 cells when the service supports it?
+ Min: 0. Max: 1. Default: 0.
+
+* `hsv3-tolerate-no-legacy` -- Should clients tolerate v3 service descriptors
+ that don't have legacy fields? Min: 0. Max: 1. Default: 0.
+
+From section 8:
+
+* `enforce-endive-dl-delay-after` -- How many seconds after receiving a
+ SNIP with some timestamp T does a client wait for rejecting older SNIPs?
+ Equivalent to "N" in "limiting ENDIVE variance within the network."
+ Min: 0. Max: INT32_MAX. Default: 3600 (1 hour).
+
+* `allow-endive-dl-delay` -- Once a client has received an SNIP with
+ timestamp T, it will not accept any SNIP with timestamp earlier than
+ "allow-endive-dl-delay" seconds before T.
+ Equivalent to "Delta" in "limiting ENDIVE variance within the network."
+ Min: 0. Max: 2592000 (30 days). Default: 10800 (3 hours).
+
+<!-- Section A.5 --> <a id='SA.5'></a>
+
+## Appendix E: Semantic sorting for CBOR values.
+
+Some voting operations assume a partial ordering on CBOR values. We define
+such an ordering as follows:
+
+ * bstr and tstr items are sorted lexicographically, as if they were
+ compared with a version of strcmp() that accepts internal NULs.
+ * uint and int items are are sorted by integer values.
+ * arrays are sorted lexicographically by elements.
+ * Tagged items are sorted as if they were not tagged.
+ * Maps do not have any sorting order.
+ * False precedes true.
+ * Otherwise, the ordering between two items is not defined.
+
+More specifically:
+
+ Algorithm: compare two cbor items A and B.
+
+ Returns LT, EQ, GT, or NIL.
+
+ While A is tagged, remove the tag from A.
+ While B is tagged, remove the tag from B.
+
+ If A is any integer type, and B is any integer type:
+ return A cmp B
+
+ If the type of A is not the same as the type of B:
+ return NIL.
+
+ If A and B are both booleans:
+ return int(A) cmp int(B), where int(false)=0 and int(B)=1.
+
+ If A and B are both tstr or both bstr:
+ while len(A)>0 and len(B)>0:
+ if A[0] != B[0]:
+ return A[0] cmp B[0]
+ Discard A[0] and B[0]
+ If len(A) == len(B) == 0:
+ return EQ.
+ else if len(A) == 0:
+ return LT. (B is longer)
+ else:
+ return GT. (A is longer)
+
+ If A and B are both arrays:
+ while len(A)>0 and len(B)>0:
+ Run this algorithm recursively on A[0] and B[0].
+ If the result is not EQ:
+ Return that result.
+ Discard A[0] and B[0]
+ If len(A) == len(B) == 0:
+ return EQ.
+ else if len(A) == 0:
+ return LT. (B is longer)
+ else:
+ return GT. (A is longer)
+
+ Otherwise, A and B are a type for which we do not define an ordering,
+ so return NIL.
+
+<!-- Section A.6 --> <a id='SA.6'></a>
+
+## Appendix F: Example voting rules
+
+Here we give a set of voting rules for the fields described in our initial
+VoteDocuments.
+
+ {
+ meta: {
+ voting-delay: { op: "Mode", tie_low:false,
+ type:["tuple","uint","uint"] },
+ voting-interval: { op: "Median", type:"uint" },
+ snip-lifespan: {op: "Mode", type:["tuple","uint","uint","uint"] },
+ c-param-lifetime: {op: "Mode", type:["tuple","uint","uint","uint"] },
+ s-param-lifetime: {op: "Mode", type:["tuple","uint","uint","uint"] },
+ cur-shared-rand: {op: "Mode", min_count: "qfield",
+ type:["tuple","uint","bstr"]},
+ prev-shared-rand: {op: "Mode", min_count: "qfield",
+ type:["tuple","uint","bstr"]},
+ client-params: {
+ recommend-versions: {op:"SetJoin", min_count:"qfield",type:"tstr"},
+ require-protos: {op:"BitThreshold", min_count:"sqauth"},
+ recommend-protos: {op:"BitThreshold", min_count:"qauth"},
+ params: {op:"MapJoin",key_min_count:"qauth",
+ keytype:"tstr",
+ item_op:{op:"Median",min_vote:"qauth",type:"uint"},
+ },
+ certs: {op:"SetJoin",min_count:1, type: 'bstr'},
+ },
+ ; Use same value for server-params.
+ relay: {
+ meta: {
+ desc: {op:"Mode", min_count:"qauth",tie_low:false,
+ type:["uint","bstr"] },
+ flags: {op:"MapJoin", key_type:"tstr",
+ item_op:{op:"Mode",type:"bool"}},
+ bw: {op:"Median", type:"uint" },
+ mbw :{op:"Median", type:"uint" },
+ rsa-id: {op:"Mode", type:"bstr"},
+ },
+ snip: {
+ ; ed25519 key is handled as any other value.
+ 0: { op:"DerivedFrom", fields:[["RM","desc"]],
+ rule:{op:"Mode",type="bstr"} },
+
+ ; ntor onion key.
+ 1: { op:"DerivedFrom", fields:[["RM","desc"]],
+ rule:{op:"Mode",type="bstr"} },
+
+ ; link specifiers.
+ 2: { op: "CborDerived",
+ item-op: { op:"DerivedFrom", fields:[["RM","desc"]],
+ rule:{op:"Mode",type="bstr" } } },
+
+ ; software description.
+ 3: { op:"DerivedFrom", fields:[["RM","desc"]],
+ rule:{op:"Mode",type=["tuple", "tstr", "tstr"] } },
+
+ ; protovers.
+ 4: { op: "CborDerived",
+ item-op: { op:"DerivedFrom", fields:[["RM","desc"]],
+ rule:{op:"Mode",type="bstr" } } },
+
+ ; families.
+ 5: { op:"SetJoin", min_count:"qfield", type:"bstr" },
+
+ ; countrycode
+ 6: { op:"Mode", type="tstr" } ,
+
+ ; 7: exitpolicy.
+ 7: { op: "CborDerived",
+ item-op: { op: "DerivedFrom", fields:[["RM","desc"],["CP","port-classes"]],
+ rule:{op:"Mode",type="bstr" } } },
+ },
+ legacy: {
+ "sha1-desc": { op:"DerivedFrom",
+ fields:[["RM","desc"]],
+ rule:{op:"Mode",type="bstr"} },
+ "mds": { op:"DerivedFrom",
+ fields:[["RM":"desc"]],
+ rule: { op:"ThresholdOp", min_count: "qauth",
+ multi_low:false,
+ type:["tuple", "uint", "uint",
+ "bstr", "bstr" ] }},
+ }
+ }
+ indices: {
+ ; See appendix G.
+ }
+ }
+
+<!-- Section A.7 --> <a id='SA.7'></a>
+
+## Appendix G: A list of routing indices
+
+Middle -- general purpose index for use when picking middle hops in
+circuits. Bandwidth-weighted for use as middle relays. May exclude
+guards and/or exits depending on overall balance of resources on the
+network.
+
+Formula:
+ type: 'weighted',
+ source: {
+ type:'bw', require_flags: ['Valid'], 'bwfield' : ["RM", "mbw"]
+ },
+ weight: {
+ [ "!Exit", "!Guard" ] => "Wmm",
+ [ "Exit", "Guard" ] => "Wbm",
+ [ "Exit", "!Guard" ] => "Wem",
+ [ "!Exit", "Guard" ] => "Wgm",
+ }
+
+Guard -- index for choosing guard relays. This index is not used
+directly when extending, but instead only for _picking_ guard relays
+that the client will later connect to directly. Bandwidth-weighted
+for use as guard relays. May exclude guard+exit relays depending on
+resource balance.
+
+ type: 'weighted',
+ source: {
+ type:'bw',
+ require_flags: ['Valid', "Guard"],
+ bwfield : ["RM", "mbw"]
+ },
+ weight: {
+ [ "Exit", ] => "Weg",
+ }
+
+HSDirV2 -- index for finding spots on the hsv2 directory ring.
+
+Formula:
+ type: 'rsa-id',
+
+HSDirV3-early -- index for finding spots on the hsv3 directory ring
+for the earlier of the two "active" days. (The active days are
+today, and whichever other day is closest to the time at which the
+ENDIVE becomes active.)
+
+Formula:
+ type: 'ed-id'
+ alg: SHA3-256,
+ prefix: b"node-idx",
+ suffix: (depends on shared-random and time period)
+
+HSDirV3-late -- index for finding spots on the hsv3 directory ring
+for the later of the two "active" days.
+
+Formula: as HSDirV3-early, but with a different suffix.
+
+Self -- A virtual index that never appears in an ENDIVE. SNIPs with
+this index are unsigned, and occupy the entire index range. This
+index is used with bridges to represent each bridge's uniqueness.
+
+Formula: none.
+
+Exit0..ExitNNN -- Exits that can connect to all ports within a given
+PortClass 0 through NNN.
+
+Formula:
+
+ type: 'weighted',
+ source: {
+ type:'bw',
+ ; The second flag here depends on which portclass this is.
+ require_flags: [ 'Valid', "P@3" ],
+ bwfield : ["RM", "mbw"]
+ },
+ weight: {
+ [ "Guard", ] => "Wge",
+ }
+
+<!-- Section A.8 --> <a id='SA.8'></a>
+
+## Appendix H: Choosing good clusters of exit policies
+
+With Walking Onions, we cannot easily support all the port
+combinations [*] that we currently allow in the "policy summaries"
+that we support in microdescriptors.
+
+> [*] How many "short policy summaries" are there? The number would be
+> 2^65535, except for the fact today's Tor doesn't permit exit policies to
+> get maximally long.
+
+In the Walking Onions whitepaper
+(https://crysp.uwaterloo.ca/software/walkingonions/) we noted in
+section 6 that we can group exit policies by class, and get down to
+around 220 "classes" of port, such that each class was either
+completely supported or completely unsupported by every relay. But
+that number is still impractically large: if we need ~11 bytes to
+represent a SNIP index range, we would need an extra 2320 bytes per
+SNIP, which seems like more overhead than we really want.
+
+We can reduce the number of port classes further, at the cost of
+some fidelity. For example, suppose that the set {https,http} is
+supported by relays {A,B,C,D}, and that the set {ssh,irc} is
+supported by relays {B,C,D,E}. We could combine them into a new
+port class {https,http,ssh,irc}, supported by relays {B,C,D} -- at
+the expense of no longer being able to say that relay A supported
+{https,http}, or that relay E supported {ssh,irc}.
+
+This loss would not necessarily be permanent: the operator of relay
+A might be willing to add support for {ssh,irc}, and the operator of
+relay E might be willing to add support for {https,http}, in order
+to become useful as an exit again.
+
+(We might also choose to add a configuration option for relays to
+take their exit policies directly from the port classes in the
+consensus.)
+
+How might we select our port classes? Three general categories of
+approach seem possible: top-down, bottom-up, and hybrid.
+
+In a top-down approach, we would collaborate with authority and exit
+operators to identify _a priori_ reasonable classes of ports, such
+as "Web", "Chat", "Miscellaneous internet", "SMTP", and "Everything
+else". Authorities would then base exit indices on these classes.
+
+In a bottom-up approach, we would find an algorithm to run on the
+current exit policies in order to find the "best" set of port
+classes to capture the policies as they stand with minimal loss.
+(Quantifying this loss is nontrivial: do we weight by bandwidth? Do
+we weight every port equally, or do we call some more "important"
+than others?)
+
+> See exit-analysis for an example tool that runs a greedy algorithm
+> to find a "good" partition using an unweighted,
+> all-ports-are-equal cost function. See the files
+> "greedy-set-cov-{4,8,16}" for examples of port classes produced
+> by this algorithm.
+
+In a hybrid approach, we'd use top-down and bottom-up techniques
+together. For example, we could start with an automated bottom-up
+approach, and then evaluate it based feedback from operators. Or we
+could start with a handcrafted top-down approach, and then use
+bottom-up cost metrics to look for ways to split or combine those
+port classes in order to represent existing policies with better
+fidelity.
+
+
+<!-- Section A.9 --> <a id='SA.9'></a>
+
+## Appendix I: Non-clique topologies with Walking Onions
+
+For future work, we can expand the Walking Onions design to
+accommodate network topologies where relays are divided into groups,
+and not every group connects to every other. To do so requires
+additional design work, but here I'll provide what I hope will be a
+workable sketch.
+
+First, each SNIP needs to contain an ID saying which relay group it
+belongs to, and an ID saying which relay group(s) may serve it.
+
+When downloading an ENDIVE, each relay should report its own
+identity, and receive an ENDIVE for that identity's group. It
+should contain both the identities of relays in the group, and the
+SNIPs that should be served for different indices by members of that
+group.
+
+The easy part would be to add an optional group identity field to
+SNIPs, defaulting to 0, indicating that the relay belongs to that
+group, and an optional served-by field to each SNIP, indicating
+groups that may serve the SNIP. You'd only accept SNIPs if they
+were served by a relay in a group that was allowed to serve them.
+
+Would guards work? Sure: we'd need to have guard SNIPS served by
+middle relays.
+
+For hsdirs, we'd need to have either multiple shards of the hsdir
+ring (which seems like a bad idea?) or have all middle nodes able to
+reach the hsdir ring.
+
+Things would get tricky with making onion services work: if you need
+to use an introduction point or a rendezvous point in group X, then
+you need to get there from a relay that allows connections to group
+X. Does this imply indices meaning "Can reach group X" or
+"two-degrees of group X"?
+
+The question becomes: "how much work on alternative topologies does
+it make sense to deploy in advance?" It seems like there are
+unknowns affecting both client and relay operations here, which
+suggests that advance deployment for either case is premature: we
+can't necessarily make either clients or relays "do the right thing"
+in advance given what we now know of the right thing.
+
+<!-- Section A.10 --> <a id='SA.10'></a>
+
+## Appendix Z: acknowledgments
+
+Thanks to Peter Palfrader for his original design in proposal 141,
+and to the designers of PIR-Tor, both of which inspired aspects of
+this Walking Onions design.
+
+Thanks to Chelsea Komlo, Sajin Sasy, and Ian Goldberg for feedback on
+an earlier version of this design.
+
+Thanks to David Goulet, Teor, and George Kadianakis for commentary on
+earlier versions of proposal 300.
+
+Thanks to Chelsea Komlo and Ian Goldberg for their help fleshing out
+so many ideas related to Walking Onions in their work on the design
+paper.
+
+Thanks to Teor for improvements to diff format, ideas about grouping
+exit ports, and numerous ideas about getting topology and
+distribution right.
+
+These specifications were supported by a grant from the Zcash
+Foundation.
+
