[torspec/master] Walking onions proposal is completed.

3 Jun 2020

commit 87eefe8c537bdbab2a34394ee094338e862e9d69
Author: Nick Mathewson <nickm@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.
+

    

nickm＠torproject.org

tags

participants (1)