[tor-dev] Proposal 323: Specification for Walking Onions

``` 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.