From 81e888dca8d971948eff15e3acc4e61cbdfa1b99 Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Sat, 14 Oct 2023 19:00:39 -0400 Subject: Break up some sections in dir-spec that had gotten run together. --- spec/SUMMARY.md | 3 + spec/dir-spec/computing-consensus.md | 762 +++++++++++++++++++++++ spec/dir-spec/downloading-from-other-auths.md | 54 ++ spec/dir-spec/publishing-consensus.md | 38 ++ spec/dir-spec/serving-bandwidth-list-files.md | 854 -------------------------- 5 files changed, 857 insertions(+), 854 deletions(-) create mode 100644 spec/dir-spec/computing-consensus.md create mode 100644 spec/dir-spec/downloading-from-other-auths.md create mode 100644 spec/dir-spec/publishing-consensus.md diff --git a/spec/SUMMARY.md b/spec/SUMMARY.md index 3b8ce7e..9d6207d 100644 --- a/spec/SUMMARY.md +++ b/spec/SUMMARY.md @@ -41,6 +41,9 @@ - [Vote and consensus status document formats](./dir-spec/consensus-formats.md) - [Assigning flags in a vote](./dir-spec/assigning-flags-vote.md) - [Serving bandwidth list files](./dir-spec/serving-bandwidth-list-files.md) + - [Downloading information from other directory authorities](./dir-spec/downloading-from-other-auths.md) + - [Computing a consensus from a set of votes](./dir-spec/computing-consensus.md) + - [Publishing the signed consensus](./dir-spec/publishing-consensus.md) - [Directory cache operation](./dir-spec/directory-cache-operation.md) - [Client operation](./dir-spec/client-operation.md) - [Standards compliance](./dir-spec/standards-compliance.md) diff --git a/spec/dir-spec/computing-consensus.md b/spec/dir-spec/computing-consensus.md new file mode 100644 index 0000000..e17f4c6 --- /dev/null +++ b/spec/dir-spec/computing-consensus.md @@ -0,0 +1,762 @@ + +## Computing a consensus from a set of votes { #computing-consensus } + +Given a set of votes, authorities compute the contents of the consensus. + +The consensus status, along with as many signatures as the server +currently knows (see section 3.10 below), should be available at + +`http:///tor/status-vote/next/consensus.z` + +The contents of the consensus document are as follows: + +The "valid-after", "valid-until", and "fresh-until" times are taken as +the median of the respective values from all the votes. + +The times in the "voting-delay" line are taken as the median of the +VoteSeconds and DistSeconds times in the votes. + +Known-flags is the union of all flags known by any voter. + +Entries are given on the "params" line for every keyword on which a +majority of authorities (total authorities, not just those +participating in this vote) voted on, or if at least three +authorities voted for that parameter. The values given are the +low-median of all votes on that keyword. + +(In consensus methods 7 to 11 inclusive, entries were given on +the "params" line for every keyword on which *any* authority voted, +the value given being the low-median of all votes on that keyword.) + +```text + "client-versions" and "server-versions" are sorted in ascending + order; A version is recommended in the consensus if it is recommended + by more than half of the voting authorities that included a + client-versions or server-versions lines in their votes. +``` + +With consensus methods 19 through 33, a package line is generated for a +given PACKAGENAME/VERSION pair if at least three authorities list such a +package in their votes. (Call these lines the "input" lines for +PACKAGENAME.) The consensus will contain every "package" line that is +listed verbatim by more than half of the authorities listing a line for +the PACKAGENAME/VERSION pair, and no others. + +The authority item groups (dir-source, contact, fingerprint, +vote-digest) are taken from the votes of the voting +authorities. These groups are sorted by the digests of the +authorities identity keys, in ascending order. If the consensus +method is 3 or later, a dir-source line must be included for +every vote with legacy-key entry, using the legacy-key's +fingerprint, the voter's ordinary nickname with the string +"-legacy" appended, and all other fields as from the original +vote's dir-source line. + +```text + A router status entry: + * is included in the result if some router status entry with the same + identity is included by more than half of the authorities (total + authorities, not just those whose votes we have). + (Consensus method earlier than 21) + + * is included according to the rules in section 3.8.0.1 and + 3.8.0.2 below. (Consensus method 22 or later) + + * For any given RSA identity digest, we include at most + one router status entry. + + * For any given Ed25519 identity, we include at most one router + status entry. + + * A router entry has a flag set if that is included by more than half + of the authorities who care about that flag. + + * Two router entries are "the same" if they have the same + (descriptor digest, published time, nickname, IP, ports> tuple. + We choose the tuple for a given router as whichever tuple appears + for that router in the most votes. We break ties first in favor of + the more recently published, then in favor of smaller server + descriptor digest. + + [ + * The Named flag appears if it is included for this routerstatus by + _any_ authority, and if all authorities that list it list the same + nickname. However, if consensus-method 2 or later is in use, and + any authority calls this identity/nickname pair Unnamed, then + this routerstatus does not get the Named flag. + + * If consensus-method 2 or later is in use, the Unnamed flag is + set for a routerstatus if any authorities have voted for a different + identities to be Named with that nickname, or if any authority + lists that nickname/ID pair as Unnamed. + + (With consensus-method 1, Unnamed is set like any other flag.) + + [But note that authorities no longer vote for the Named flag, + and the above two bulletpoints are now irrelevant.] + ] + + * The version is given as whichever version is listed by the most + voters, with ties decided in favor of more recent versions. + + * If consensus-method 4 or later is in use, then routers that + do not have the Running flag are not listed at all. + + * If consensus-method 5 or later is in use, then the "w" line + is generated using a low-median of the bandwidth values from + the votes that included "w" lines for this router. + + * If consensus-method 5 or later is in use, then the "p" line + is taken from the votes that have the same policy summary + for the descriptor we are listing. (They should all be the + same. If they are not, we pick the most commonly listed + one, breaking ties in favor of the lexicographically larger + vote.) The port list is encoded as specified in section 3.8.2. + + * If consensus-method 6 or later is in use and if 3 or more + authorities provide a Measured= keyword in their votes for + a router, the authorities produce a consensus containing a + Bandwidth= keyword equal to the median of the Measured= votes. + + * If consensus-method 7 or later is in use, the params line is + included in the output. + + * If the consensus method is under 11, bad exits are considered as + possible exits when computing bandwidth weights. Otherwise, if + method 11 or later is in use, any router that is determined to get + the BadExit flag doesn't count when we're calculating weights. + + * If consensus method 12 or later is used, only consensus + parameters that more than half of the total number of + authorities voted for are included in the consensus. + + [ As of 0.2.6.1-alpha, authorities no longer advertise or negotiate + any consensus methods lower than 13. ] + + * If consensus method 13 or later is used, microdesc consensuses + omit any router for which no microdesc was agreed upon. + + * If consensus method 14 or later is used, the ns consensus and + microdescriptors may include an "a" line for each router, listing + an IPv6 OR port. + + * If consensus method 15 or later is used, microdescriptors + include "p6" lines including IPv6 exit policies. + + * If consensus method 16 or later is used, ntor-onion-key + are included in microdescriptors + + * If consensus method 17 or later is used, authorities impose a + maximum on the Bandwidth= values that they'll put on a 'w' + line for any router that doesn't have at least 3 measured + bandwidth values in votes. They also add an "Unmeasured=1" + flag to such 'w' lines. + + * If consensus method 18 or later is used, authorities include + "id" lines in microdescriptors. This method adds RSA ids. + + * If consensus method 19 or later is used, authorities may include + "package" lines in consensuses. + + * If consensus method 20 or later is used, authorities may include + GuardFraction information in microdescriptors. + + * If consensus method 21 or later is used, authorities may include + an "id" line for ed25519 identities in microdescriptors. + + [ As of 0.2.8.2-alpha, authorities no longer advertise or negotiate + consensus method 21, because it contains bugs. ] + + * If consensus method 22 or later is used, and the votes do not + produce a majority consensus about a relay's Ed25519 key (see + 3.8.0.1 below), the consensus must include a NoEdConsensus flag on + the "s" line for every relay whose listed Ed key does not reflect + consensus. + + * If consensus method 23 or later is used, authorities include + shared randomness protocol data on their votes and consensus. + + * If consensus-method 24 or later is in use, then routers that + do not have the Valid flag are not listed at all. + + [ As of 0.3.4.1-alpha, authorities no longer advertise or negotiate + any consensus methods lower than 25. ] + + * If consensus-method 25 or later is in use, then we vote + on recommended-protocols and required-protocols lines in the + consensus. We also include protocols lines in routerstatus + entries. + + * If consensus-method 26 or later is in use, then we initialize + bandwidth weights to 1 in our calculations, to avoid + division-by-zero errors on unusual networks. + + * If consensus method 27 or later is used, the microdesc consensus + may include an "a" line for each router, listing an IPv6 OR port. + + [ As of 0.4.3.1-alpha, authorities no longer advertise or negotiate + any consensus methods lower than 28. ] + + * If consensus method 28 or later is used, microdescriptors no longer + include "a" lines. + + * If consensus method 29 or later is used, microdescriptor "family" + lines are canonicalized to improve compression. + + * If consensus method 30 or later is used, the base64 encoded + ntor-onion-key does not include the trailing = sign. + + * If consensus method 31 or later is used, authorities parse the + "bwweightscale" and "maxunmeasuredbw" parameters correctly when + computing votes. + + * If consensus method 32 or later is used, authorities handle the + "MiddleOnly" flag specially when computing a consensus. When the + voters agree to include "MiddleOnly" in a routerstatus, they + automatically remove "Exit", "Guard", "V2Dir", and "HSDir". If + the BadExit flag is included in the consensus, they automatically + add it to the routerstatus. + + * If consensus method 33 or later is used, and the consensus + flavor is "microdesc", then the "Publication" field in the "r" + line is set to "2038-01-01 00:00:00". + + * If consensus method 34 or later is used, the consensus + does not include any "package" lines. +``` + +The signatures at the end of a consensus document are sorted in +ascending order by identity digest. + +All ties in computing medians are broken in favor of the smaller or +earlier item. + + + +### Deciding which Ids to include { #choosing-relay-ids } + +This sorting algorithm is used for consensus-method 22 and later. + +```text + First, consider each listing by tuple of identities, where 'Ed' + may be "None" if the voter included "id ed25519 none" to indicate that + the authority knows what ed25519 identities are, and thinks that the RSA + key doesn't have one. + + For each such tuple that is listed by more than half of the + total authorities (not just total votes), include it. (It is not + possible for any other to have as many votes.) If more + than half of the authorities list a single pair of this type, we + consider that Ed key to be "consensus"; see description of the + NoEdConsensus flag. + + Log any other id-RSA values corresponding to an id-Ed we included, and any + other id-Ed values corresponding to an id-RSA we included. + + For each that is not yet included, if it is listed by more than + half of the total authorities, and we do not already have it listed with + some , include it, but do not consider its Ed identity canonical. +``` + + + +#### Deciding which descriptors to include { #choosing-relay-descs } + +Deciding which descriptors to include. + +A tuple belongs to an `` identity if it is a new tuple that +matches both ID parts, or if it is an old tuple (one with no Ed opinion) +that matches the RSA part. A tuple belongs to an `` identity if its +RSA identity matches. + +A tuple matches another tuple if all the fields that are present in both +tuples are the same. + +For every included identity, consider the tuples belonging to that +identity. Group them into sets of matching tuples. Include the tuple +that matches the largest set, breaking ties in favor of the most recently +published, and then in favor of the smaller server descriptor digest. + + + +### Forward compatibility { #consensus-method-list } + +Future versions of Tor will need to include new information in the +consensus documents, but it is important that all authorities (or at least +half) generate and sign the same signed consensus. + +To achieve this, authorities list in their votes their supported methods +for generating consensuses from votes. Later methods will be assigned +higher numbers. Currently specified methods: + +```text + "1" -- The first implemented version. + "2" -- Added support for the Unnamed flag. + "3" -- Added legacy ID key support to aid in authority ID key rollovers + "4" -- No longer list routers that are not running in the consensus + "5" -- adds support for "w" and "p" lines. + "6" -- Prefers measured bandwidth values rather than advertised + "7" -- Provides keyword=integer pairs of consensus parameters + "8" -- Provides microdescriptor summaries + "9" -- Provides weights for selecting flagged routers in paths + "10" -- Fixes edge case bugs in router flag selection weights + "11" -- Don't consider BadExits when calculating bandwidth weights + "12" -- Params are only included if enough auths voted for them + "13" -- Omit router entries with missing microdescriptors. + "14" -- Adds support for "a" lines in ns consensuses and microdescriptors. + "15" -- Adds support for "p6" lines. + "16" -- Adds ntor keys to microdescriptors + "17" -- Adds "Unmeasured=1" flags to "w" lines + "18" -- Adds 'id' to microdescriptors. + "19" -- Adds "package" lines to consensuses + "20" -- Adds GuardFraction information to microdescriptors. + "21" -- Adds Ed25519 keys to microdescriptors. + "22" -- Instantiates Ed25519 voting algorithm correctly. + "23" -- Adds shared randomness protocol data. + "24" -- No longer lists routers that are not Valid in the consensus. + "25" -- Vote on recommended-protocols and required-protocols. + "26" -- Initialize bandwidth weights to 1 to avoid division-by-zero. + "27" -- Adds support for "a" lines in microdescriptor consensuses. + "28" -- Removes "a" lines from microdescriptors. + "29" -- Canonicalizes families in microdescriptors. + "30" -- Removes padding from ntor-onion-key. + "31" -- Uses correct parsing for bwweightscale and maxunmeasuredbw + when computing weights + "32" -- Adds special handling for MiddleOnly flag. + "33" -- Sets "publication" field in microdesc consensus "r" lines + to a meaningless value. + "34" -- Removes "package" lines from consensus. +``` + +Before generating a consensus, an authority must decide which consensus +method to use. To do this, it looks for the highest version number +supported by more than 2/3 of the authorities voting. If it supports this +method, then it uses it. Otherwise, it falls back to the newest consensus +method that it supports (which will probably not result in a sufficiently +signed consensus). + +All authorities MUST support method 25; authorities SHOULD support +more recent methods as well. Authorities SHOULD NOT support or +advertise support for any method before 25. Clients MAY assume that +they will never see a current valid signed consensus for any method +before method 25. + +(The consensuses generated by new methods must be parsable by +implementations that only understand the old methods, and must not cause +those implementations to compromise their anonymity. This is a means for +making changes in the contents of consensus; not for making +backward-incompatible changes in their format.) + +The following methods have incorrect implementations; authorities SHOULD +NOT advertise support for them: + +"21" -- Did not correctly enable support for ed25519 key collation. + + + +### Encoding port lists + +Whether the summary shows the list of accepted ports or the list of +rejected ports depends on which list is shorter (has a shorter string +representation). In case of ties we choose the list of accepted +ports. As an exception to this rule an allow-all policy is +represented as "accept 1-65535" instead of "reject " and a reject-all +policy is similarly given as "reject 1-65535". + +Summary items are compressed, that is instead of "80-88,89-100" there +only is a single item of "80-100", similarly instead of "20,21" a +summary will say "20-21". + +Port lists are sorted in ascending order. + +The maximum allowed length of a policy summary (including the "accept " +or "reject ") is 1000 characters. If a summary exceeds that length we +use an accept-style summary and list as much of the port list as is +possible within these 1000 bytes. \[XXXX be more specific.\] + + + +### Computing Bandwidth Weights + +Let weight_scale = 10000, or the value of the "bwweightscale" parameter. +(Before consensus method 31 there was a bug in parsing bwweightscale, so +that if there were any consensus parameters after it alphabetically, it +would always be treated as 10000. A similar bug existed for +"maxunmeasuredbw".) + +Starting with consensus method 26, G, M, E, and D are initialized to 1 and +T to 4. Prior consensus methods initialize them all to 0. With this change, +test tor networks that are small or new are much more likely to produce +bandwidth-weights in their consensus. The extra bandwidth has a negligible +impact on the bandwidth weights in the public tor network. + +Let G be the total bandwidth for Guard-flagged nodes. +Let M be the total bandwidth for non-flagged nodes. +Let E be the total bandwidth for Exit-flagged nodes. +Let D be the total bandwidth for Guard+Exit-flagged nodes. +Let T = G+M+E+D + +Let Wgd be the weight for choosing a Guard+Exit for the guard position. +Let Wmd be the weight for choosing a Guard+Exit for the middle position. +Let Wed be the weight for choosing a Guard+Exit for the exit position. + +Let Wme be the weight for choosing an Exit for the middle position. +Let Wmg be the weight for choosing a Guard for the middle position. + +Let Wgg be the weight for choosing a Guard for the guard position. +Let Wee be the weight for choosing an Exit for the exit position. + +Balanced network conditions then arise from solutions to the following +system of equations: + +Wgg*G + Wgd*D == M + Wmd*D + Wme*E + Wmg*G (guard bw = middle bw) +Wgg*G + Wgd*D == Wee*E + Wed*D (guard bw = exit bw) +Wed*D + Wmd*D + Wgd*D == D (aka: Wed+Wmd+Wdg = weight_scale) +Wmg*G + Wgg*G == G (aka: Wgg = weight_scale-Wmg) +Wme*E + Wee*E == E (aka: Wee = weight_scale-Wme) + +We are short 2 constraints with the above set. The remaining constraints +come from examining different cases of network load. The following +constraints are used in consensus method 10 and above. There are another +incorrect and obsolete set of constraints used for these same cases in +consensus method 9. For those, see dir-spec.txt in Tor 0.2.2.10-alpha +to 0.2.2.16-alpha. + +Case 1: E >= T/3 && G >= T/3 (Neither Exit nor Guard Scarce) + +In this case, the additional two constraints are: Wmg == Wmd, +Wed == 1/3. + +```text + This leads to the solution: + Wgd = weight_scale/3 + Wed = weight_scale/3 + Wmd = weight_scale/3 + Wee = (weight_scale*(E+G+M))/(3*E) + Wme = weight_scale - Wee + Wmg = (weight_scale*(2*G-E-M))/(3*G) + Wgg = weight_scale - Wmg + + Case 2: E < T/3 && G < T/3 (Both are scarce) +``` + +Let R denote the more scarce class (Rare) between Guard vs Exit. +Let S denote the less scarce class. + +Subcase a: R+D \< S + +In this subcase, we simply devote all of D bandwidth to the +scarce class. + +```text + Wgg = Wee = weight_scale + Wmg = Wme = Wmd = 0; + if E < G: + Wed = weight_scale + Wgd = 0 + else: + Wed = 0 + Wgd = weight_scale + + Subcase b: R+D >= S +``` + +In this case, if M \<= T/3, we have enough bandwidth to try to achieve +a balancing condition. + +Add constraints Wgg = weight_scale, Wmd == Wgd to maximize bandwidth in +the guard position while still allowing exits to be used as middle nodes: + +Wee = (weight_scale\*(E - G + M))/E +Wed = (weight_scale\*(D - 2*E + 4*G - 2*M))/(3*D) +Wme = (weight_scale\*(G-M))/E +Wmg = 0 +Wgg = weight_scale +Wmd = (weight_scale - Wed)/2 +Wgd = (weight_scale - Wed)/2 + +If this system ends up with any values out of range (ie negative, or +above weight_scale), use the constraints Wgg == weight_scale and Wee == +weight_scale, since both those positions are scarce: + +```text + Wgg = weight_scale + Wee = weight_scale + Wed = (weight_scale*(D - 2*E + G + M))/(3*D) + Wmd = (weight_Scale*(D - 2*M + G + E))/(3*D) + Wme = 0 + Wmg = 0 + Wgd = weight_scale - Wed - Wmd + + If M > T/3, then the Wmd weight above will become negative. Set it to 0 + in this case: + Wmd = 0 + Wgd = weight_scale - Wed + + Case 3: One of E < T/3 or G < T/3 + + Let S be the scarce class (of E or G). + + Subcase a: (S+D) < T/3: + if G=S: + Wgg = Wgd = weight_scale; + Wmd = Wed = Wmg = 0; + // Minor subcase, if E is more scarce than M, + // keep its bandwidth in place. + if (E < M) Wme = 0; + else Wme = (weight_scale*(E-M))/(2*E); + Wee = weight_scale-Wme; + if E=S: + Wee = Wed = weight_scale; + Wmd = Wgd = Wme = 0; + // Minor subcase, if G is more scarce than M, + // keep its bandwidth in place. + if (G < M) Wmg = 0; + else Wmg = (weight_scale*(G-M))/(2*G); + Wgg = weight_scale-Wmg; + + Subcase b: (S+D) >= T/3 + if G=S: + Add constraints Wgg = weight_scale, Wmd == Wed to maximize bandwidth + in the guard position, while still allowing exits to be + used as middle nodes: + Wgg = weight_scale + Wgd = (weight_scale*(D - 2*G + E + M))/(3*D) + Wmg = 0 + Wee = (weight_scale*(E+M))/(2*E) + Wme = weight_scale - Wee + Wmd = (weight_scale - Wgd)/2 + Wed = (weight_scale - Wgd)/2 + if E=S: + Add constraints Wee == weight_scale, Wmd == Wgd to maximize bandwidth + in the exit position: + Wee = weight_scale; + Wed = (weight_scale*(D - 2*E + G + M))/(3*D); + Wme = 0; + Wgg = (weight_scale*(G+M))/(2*G); + Wmg = weight_scale - Wgg; + Wmd = (weight_scale - Wed)/2; + Wgd = (weight_scale - Wed)/2; +``` + +To ensure consensus, all calculations are performed using integer math +with a fixed precision determined by the bwweightscale consensus +parameter (defaults at 10000, Min: 1, Max: INT32_MAX). (See note above +about parsing bug in bwweightscale before consensus method 31.) + +For future balancing improvements, Tor clients support 11 additional weights +for directory requests and middle weighting. These weights are currently +set at weight_scale, with the exception of the following groups of +assignments: + +Directory requests use middle weights: + +Wbd=Wmd, Wbg=Wmg, Wbe=Wme, Wbm=Wmm + +Handle bridges and strange exit policies: + +Wgm=Wgg, Wem=Wee, Weg=Wed + + + +## Computing consensus flavors + +Consensus flavors are variants of the consensus that clients can choose +to download and use instead of the unflavored consensus. The purpose +of a consensus flavor is to remove or replace information in the +unflavored consensus without forcing clients to download information +they would not use anyway. + +Directory authorities can produce and serve an arbitrary number of +flavors of the same consensus. A downside of creating too many new +flavors is that clients will be distinguishable based on which flavor +they download. A new flavor should not be created when adding a field +instead wouldn't be too onerous. + +Examples for consensus flavors include: + +```text + - Publishing hashes of microdescriptors instead of hashes of + full descriptors (see section 3.9.2). + - Including different digests of descriptors, instead of the + perhaps-soon-to-be-totally-broken SHA1. +``` + +Consensus flavors are derived from the unflavored consensus once the +voting process is complete. This is to avoid consensus synchronization +problems. + +Every consensus flavor has a name consisting of a sequence of one +or more alphanumeric characters and dashes. For compatibility, +the original (unflavored) consensus type is called "ns". + +The supported consensus flavors are defined as part of the +authorities' consensus method. + +All consensus flavors have in common that their first line is +"network-status-version" where version is 3 or higher, and the flavor +is a string consisting of alphanumeric characters and dashes: + +"network-status-version" SP version \[SP flavor\] NL + + + +### ns consensus + +The ns consensus flavor is equivalent to the unflavored consensus. +When the flavor is omitted from the "network-status-version" line, +it should be assumed to be "ns". Some implementations may explicitly +state that the flavor is "ns" when generating consensuses, but should +accept consensuses where the flavor is omitted. + + + +### Microdescriptor consensus + +The microdescriptor consensus is a consensus flavor that contains +microdescriptor hashes instead of descriptor hashes and that omits +exit-policy summaries which are contained in microdescriptors. The +microdescriptor consensus was designed to contain elements that are +small and frequently changing. Clients use the information in the +microdescriptor consensus to decide which servers to fetch information +about and which servers to fetch information from. + +The microdescriptor consensus is based on the unflavored consensus with +the exceptions as follows: + +"network-status-version" SP version SP "microdesc" NL + +\[At start, exactly once.\] + +The flavor name of a microdescriptor consensus is "microdesc". + +Changes to router status entries are as follows: + +```text + "r" SP nickname SP identity SP publication SP IP SP ORPort + SP DirPort NL + + [At start, exactly once.] + + Similar to "r" lines in section 3.4.1, but without the digest element. + + "a" SP address ":" port NL + + [Any number] + + Identical to the "r" lines in section 3.4.1. +``` + +(Only included when the vote is generated with consensus-method 14 +or later, and the consensus is generated with consensus-method 27 or +later.) + +"p" ... NL + +\[At most once\] + +Not currently generated. + +Exit policy summaries are contained in microdescriptors and +therefore omitted in the microdescriptor consensus. + +"m" SP digest NL + +\[Exactly once.\*\] + +"digest" is the base64 of the SHA256 hash of the router's +microdescriptor with trailing =s omitted. For a given router +descriptor digest and consensus method there should only be a +single microdescriptor digest in the "m" lines of all votes. +If different votes have different microdescriptor digests for +the same descriptor digest and consensus method, at least one +of the authorities is broken. If this happens, the microdesc +consensus should contain whichever microdescriptor digest is +most common. If there is no winner, we break ties in the favor +of the lexically earliest. + +\[\*Before consensus method 13, this field was sometimes erroneously +omitted.\] + +Additionally, a microdescriptor consensus SHOULD use the sha256 digest +algorithm for its signatures. + + + +## Exchanging detached signatures + +Once an authority has computed and signed a consensus network status, it +should send its detached signature to each other authority in an HTTP POST +request to the URL: + +`http:///tor/post/consensus-signature` + +\[XXX Note why we support push-and-then-pull.\] + +All of the detached signatures it knows for consensus status should be +available at: + +`http:///tor/status-vote/next/consensus-signatures.z` + +Assuming full connectivity, every authority should compute and sign the +same consensus including any flavors in each period. Therefore, it +isn't necessary to download the consensus or any flavors of it computed +by each authority; instead, the authorities only push/fetch each +others' signatures. A "detached signature" document contains items as +follows: + +"consensus-digest" SP Digest NL + +\[At start, at most once.\] + +The digest of the consensus being signed. + +"valid-after" SP YYYY-MM-DD SP HH:MM:SS NL +"fresh-until" SP YYYY-MM-DD SP HH:MM:SS NL +"valid-until" SP YYYY-MM-DD SP HH:MM:SS NL + +\[As in the consensus\] + +"additional-digest" SP flavor SP algname SP digest NL + +\[Any number.\] + +For each supported consensus flavor, every directory authority +adds one or more "additional-digest" lines. "flavor" is the name +of the consensus flavor, "algname" is the name of the hash +algorithm that is used to generate the digest, and "digest" is the +hex-encoded digest. + +The hash algorithm for the microdescriptor consensus flavor is +defined as SHA256 with algname "sha256". + +```text + "additional-signature" SP flavor SP algname SP identity SP + signing-key-digest NL signature. + + [Any number.] +``` + +For each supported consensus flavor and defined digest algorithm, +every directory authority adds an "additional-signature" line. +"flavor" is the name of the consensus flavor. "algname" is the +name of the algorithm that was used to hash the identity and +signing keys, and to compute the signature. "identity" is the +hex-encoded digest of the authority identity key of the signing +authority, and "signing-key-digest" is the hex-encoded digest of +the current authority signing key of the signing authority. + +The "sha256" signature format is defined as the RSA signature of +the OAEP+-padded SHA256 digest of the item to be signed. When +checking signatures, the signature MUST be treated as valid if the +signature material begins with SHA256(document), so that other +data can get added later. +\[To be honest, I didn't fully understand the previous paragraph +and only copied it from the proposals. Review carefully. -KL\] + +"directory-signature" + +\[As in the consensus; the signature object is the same as in the +consensus document.\] + + diff --git a/spec/dir-spec/downloading-from-other-auths.md b/spec/dir-spec/downloading-from-other-auths.md new file mode 100644 index 0000000..8f474e9 --- /dev/null +++ b/spec/dir-spec/downloading-from-other-auths.md @@ -0,0 +1,54 @@ +# Downloading information from other directory authorities + +## Downloading missing certificates from other directory authorities { #download-missing-certs } + +XXX when to download certificates. + + + +## Downloading server descriptors from other directory authorities { #download-missing-descs } + +Periodically (currently, every 10 seconds), directory authorities check +whether there are any specific descriptors that they do not have and that +they are not currently trying to download. +Authorities identify them by hash in vote (if publication date is more +recent than the descriptor we currently have). + +\[XXXX need a way to fetch descriptors ahead of the vote? v2 status docs can +do that for now.\] + +If so, the directory authority launches requests to the authorities for these +descriptors, such that each authority is only asked for descriptors listed +in its most recent vote. If more +than one authority lists the descriptor, we choose which to ask at random. + +If one of these downloads fails, we do not try to download that descriptor +from the authority that failed to serve it again unless we receive a newer +network-status (consensus or vote) from that authority that lists the same +descriptor. + +```text + Directory authorities must potentially cache multiple descriptors for each + router. Authorities must not discard any descriptor listed by any recent + consensus. If there is enough space to store additional descriptors, + authorities SHOULD try to hold those which clients are likely to download the + most. (Currently, this is judged based on the interval for which each + descriptor seemed newest.) +[XXXX define recent] +``` + +Authorities SHOULD NOT download descriptors for routers that they would +immediately reject for reasons listed in section 3.2. + + + +## Downloading extra-info documents from other directory authorities { #download-missing-extrainfo } + +Periodically, an authority checks whether it is missing any extra-info +documents: in other words, if it has any server descriptors with an +extra-info-digest field that does not match any of the extra-info +documents currently held. If so, it downloads whatever extra-info +documents are missing. We follow the same splitting and back-off rules +as in section 3.6. + + diff --git a/spec/dir-spec/publishing-consensus.md b/spec/dir-spec/publishing-consensus.md new file mode 100644 index 0000000..6f9563c --- /dev/null +++ b/spec/dir-spec/publishing-consensus.md @@ -0,0 +1,38 @@ +# Publishing the signed consensus { #publishing-signed-consensus } + +The voting period ends at the valid-after time. If the consensus has +been signed by a majority of authorities, these documents are made +available at + +`http:///tor/status-vote/current/consensus.z` + +and + +`http:///tor/status-vote/current/consensus-signatures.z` + +```text + [XXX current/consensus-signatures is not currently implemented, as it + is not used in the voting protocol.] + + [XXX possible future features include support for downloading old + consensuses.] + + The other vote documents are analogously made available under + +http:///tor/status-vote/current/authority.z +http:///tor/status-vote/current/.z +http:///tor/status-vote/current/d/.z +http:///tor/status-vote/current/bandwidth.z +``` + +once the voting period ends, regardless of the number of signatures. + +The authorities serve another consensus of each flavor "F" from the +locations + +```text +/tor/status-vote/(current|next)/consensus-F.z. and +/tor/status-vote/(current|next)/consensus-F/+....z. +``` + +The standard URLs for bandwidth list files first-appeared in Tor 0.3.5. diff --git a/spec/dir-spec/serving-bandwidth-list-files.md b/spec/dir-spec/serving-bandwidth-list-files.md index 7397dba..2680eb8 100644 --- a/spec/dir-spec/serving-bandwidth-list-files.md +++ b/spec/dir-spec/serving-bandwidth-list-files.md @@ -28,857 +28,3 @@ The standard URLs for bandwidth list files first-appeared in Tor 0.4.0.4-alpha. - -## Downloading missing certificates from other directory authorities { #download-missing-certs } - -XXX when to download certificates. - - - -## Downloading server descriptors from other directory authorities { #download-missing-descs } - -Periodically (currently, every 10 seconds), directory authorities check -whether there are any specific descriptors that they do not have and that -they are not currently trying to download. -Authorities identify them by hash in vote (if publication date is more -recent than the descriptor we currently have). - -\[XXXX need a way to fetch descriptors ahead of the vote? v2 status docs can -do that for now.\] - -If so, the directory authority launches requests to the authorities for these -descriptors, such that each authority is only asked for descriptors listed -in its most recent vote. If more -than one authority lists the descriptor, we choose which to ask at random. - -If one of these downloads fails, we do not try to download that descriptor -from the authority that failed to serve it again unless we receive a newer -network-status (consensus or vote) from that authority that lists the same -descriptor. - -```text - Directory authorities must potentially cache multiple descriptors for each - router. Authorities must not discard any descriptor listed by any recent - consensus. If there is enough space to store additional descriptors, - authorities SHOULD try to hold those which clients are likely to download the - most. (Currently, this is judged based on the interval for which each - descriptor seemed newest.) -[XXXX define recent] -``` - -Authorities SHOULD NOT download descriptors for routers that they would -immediately reject for reasons listed in section 3.2. - - - -## Downloading extra-info documents from other directory authorities { #download-missing-extrainfo } - -Periodically, an authority checks whether it is missing any extra-info -documents: in other words, if it has any server descriptors with an -extra-info-digest field that does not match any of the extra-info -documents currently held. If so, it downloads whatever extra-info -documents are missing. We follow the same splitting and back-off rules -as in section 3.6. - - - -## Computing a consensus from a set of votes { #computing-consensus } - -Given a set of votes, authorities compute the contents of the consensus. - -The consensus status, along with as many signatures as the server -currently knows (see section 3.10 below), should be available at - -`http:///tor/status-vote/next/consensus.z` - -The contents of the consensus document are as follows: - -The "valid-after", "valid-until", and "fresh-until" times are taken as -the median of the respective values from all the votes. - -The times in the "voting-delay" line are taken as the median of the -VoteSeconds and DistSeconds times in the votes. - -Known-flags is the union of all flags known by any voter. - -Entries are given on the "params" line for every keyword on which a -majority of authorities (total authorities, not just those -participating in this vote) voted on, or if at least three -authorities voted for that parameter. The values given are the -low-median of all votes on that keyword. - -(In consensus methods 7 to 11 inclusive, entries were given on -the "params" line for every keyword on which *any* authority voted, -the value given being the low-median of all votes on that keyword.) - -```text - "client-versions" and "server-versions" are sorted in ascending - order; A version is recommended in the consensus if it is recommended - by more than half of the voting authorities that included a - client-versions or server-versions lines in their votes. -``` - -With consensus methods 19 through 33, a package line is generated for a -given PACKAGENAME/VERSION pair if at least three authorities list such a -package in their votes. (Call these lines the "input" lines for -PACKAGENAME.) The consensus will contain every "package" line that is -listed verbatim by more than half of the authorities listing a line for -the PACKAGENAME/VERSION pair, and no others. - -The authority item groups (dir-source, contact, fingerprint, -vote-digest) are taken from the votes of the voting -authorities. These groups are sorted by the digests of the -authorities identity keys, in ascending order. If the consensus -method is 3 or later, a dir-source line must be included for -every vote with legacy-key entry, using the legacy-key's -fingerprint, the voter's ordinary nickname with the string -"-legacy" appended, and all other fields as from the original -vote's dir-source line. - -```text - A router status entry: - * is included in the result if some router status entry with the same - identity is included by more than half of the authorities (total - authorities, not just those whose votes we have). - (Consensus method earlier than 21) - - * is included according to the rules in section 3.8.0.1 and - 3.8.0.2 below. (Consensus method 22 or later) - - * For any given RSA identity digest, we include at most - one router status entry. - - * For any given Ed25519 identity, we include at most one router - status entry. - - * A router entry has a flag set if that is included by more than half - of the authorities who care about that flag. - - * Two router entries are "the same" if they have the same - (descriptor digest, published time, nickname, IP, ports> tuple. - We choose the tuple for a given router as whichever tuple appears - for that router in the most votes. We break ties first in favor of - the more recently published, then in favor of smaller server - descriptor digest. - - [ - * The Named flag appears if it is included for this routerstatus by - _any_ authority, and if all authorities that list it list the same - nickname. However, if consensus-method 2 or later is in use, and - any authority calls this identity/nickname pair Unnamed, then - this routerstatus does not get the Named flag. - - * If consensus-method 2 or later is in use, the Unnamed flag is - set for a routerstatus if any authorities have voted for a different - identities to be Named with that nickname, or if any authority - lists that nickname/ID pair as Unnamed. - - (With consensus-method 1, Unnamed is set like any other flag.) - - [But note that authorities no longer vote for the Named flag, - and the above two bulletpoints are now irrelevant.] - ] - - * The version is given as whichever version is listed by the most - voters, with ties decided in favor of more recent versions. - - * If consensus-method 4 or later is in use, then routers that - do not have the Running flag are not listed at all. - - * If consensus-method 5 or later is in use, then the "w" line - is generated using a low-median of the bandwidth values from - the votes that included "w" lines for this router. - - * If consensus-method 5 or later is in use, then the "p" line - is taken from the votes that have the same policy summary - for the descriptor we are listing. (They should all be the - same. If they are not, we pick the most commonly listed - one, breaking ties in favor of the lexicographically larger - vote.) The port list is encoded as specified in section 3.8.2. - - * If consensus-method 6 or later is in use and if 3 or more - authorities provide a Measured= keyword in their votes for - a router, the authorities produce a consensus containing a - Bandwidth= keyword equal to the median of the Measured= votes. - - * If consensus-method 7 or later is in use, the params line is - included in the output. - - * If the consensus method is under 11, bad exits are considered as - possible exits when computing bandwidth weights. Otherwise, if - method 11 or later is in use, any router that is determined to get - the BadExit flag doesn't count when we're calculating weights. - - * If consensus method 12 or later is used, only consensus - parameters that more than half of the total number of - authorities voted for are included in the consensus. - - [ As of 0.2.6.1-alpha, authorities no longer advertise or negotiate - any consensus methods lower than 13. ] - - * If consensus method 13 or later is used, microdesc consensuses - omit any router for which no microdesc was agreed upon. - - * If consensus method 14 or later is used, the ns consensus and - microdescriptors may include an "a" line for each router, listing - an IPv6 OR port. - - * If consensus method 15 or later is used, microdescriptors - include "p6" lines including IPv6 exit policies. - - * If consensus method 16 or later is used, ntor-onion-key - are included in microdescriptors - - * If consensus method 17 or later is used, authorities impose a - maximum on the Bandwidth= values that they'll put on a 'w' - line for any router that doesn't have at least 3 measured - bandwidth values in votes. They also add an "Unmeasured=1" - flag to such 'w' lines. - - * If consensus method 18 or later is used, authorities include - "id" lines in microdescriptors. This method adds RSA ids. - - * If consensus method 19 or later is used, authorities may include - "package" lines in consensuses. - - * If consensus method 20 or later is used, authorities may include - GuardFraction information in microdescriptors. - - * If consensus method 21 or later is used, authorities may include - an "id" line for ed25519 identities in microdescriptors. - - [ As of 0.2.8.2-alpha, authorities no longer advertise or negotiate - consensus method 21, because it contains bugs. ] - - * If consensus method 22 or later is used, and the votes do not - produce a majority consensus about a relay's Ed25519 key (see - 3.8.0.1 below), the consensus must include a NoEdConsensus flag on - the "s" line for every relay whose listed Ed key does not reflect - consensus. - - * If consensus method 23 or later is used, authorities include - shared randomness protocol data on their votes and consensus. - - * If consensus-method 24 or later is in use, then routers that - do not have the Valid flag are not listed at all. - - [ As of 0.3.4.1-alpha, authorities no longer advertise or negotiate - any consensus methods lower than 25. ] - - * If consensus-method 25 or later is in use, then we vote - on recommended-protocols and required-protocols lines in the - consensus. We also include protocols lines in routerstatus - entries. - - * If consensus-method 26 or later is in use, then we initialize - bandwidth weights to 1 in our calculations, to avoid - division-by-zero errors on unusual networks. - - * If consensus method 27 or later is used, the microdesc consensus - may include an "a" line for each router, listing an IPv6 OR port. - - [ As of 0.4.3.1-alpha, authorities no longer advertise or negotiate - any consensus methods lower than 28. ] - - * If consensus method 28 or later is used, microdescriptors no longer - include "a" lines. - - * If consensus method 29 or later is used, microdescriptor "family" - lines are canonicalized to improve compression. - - * If consensus method 30 or later is used, the base64 encoded - ntor-onion-key does not include the trailing = sign. - - * If consensus method 31 or later is used, authorities parse the - "bwweightscale" and "maxunmeasuredbw" parameters correctly when - computing votes. - - * If consensus method 32 or later is used, authorities handle the - "MiddleOnly" flag specially when computing a consensus. When the - voters agree to include "MiddleOnly" in a routerstatus, they - automatically remove "Exit", "Guard", "V2Dir", and "HSDir". If - the BadExit flag is included in the consensus, they automatically - add it to the routerstatus. - - * If consensus method 33 or later is used, and the consensus - flavor is "microdesc", then the "Publication" field in the "r" - line is set to "2038-01-01 00:00:00". - - * If consensus method 34 or later is used, the consensus - does not include any "package" lines. -``` - -The signatures at the end of a consensus document are sorted in -ascending order by identity digest. - -All ties in computing medians are broken in favor of the smaller or -earlier item. - - - -### Deciding which Ids to include { #choosing-relay-ids } - -This sorting algorithm is used for consensus-method 22 and later. - -```text - First, consider each listing by tuple of identities, where 'Ed' - may be "None" if the voter included "id ed25519 none" to indicate that - the authority knows what ed25519 identities are, and thinks that the RSA - key doesn't have one. - - For each such tuple that is listed by more than half of the - total authorities (not just total votes), include it. (It is not - possible for any other to have as many votes.) If more - than half of the authorities list a single pair of this type, we - consider that Ed key to be "consensus"; see description of the - NoEdConsensus flag. - - Log any other id-RSA values corresponding to an id-Ed we included, and any - other id-Ed values corresponding to an id-RSA we included. - - For each that is not yet included, if it is listed by more than - half of the total authorities, and we do not already have it listed with - some , include it, but do not consider its Ed identity canonical. -``` - - - -#### Deciding which descriptors to include { #choosing-relay-descs } - -Deciding which descriptors to include. - -A tuple belongs to an `` identity if it is a new tuple that -matches both ID parts, or if it is an old tuple (one with no Ed opinion) -that matches the RSA part. A tuple belongs to an `` identity if its -RSA identity matches. - -A tuple matches another tuple if all the fields that are present in both -tuples are the same. - -For every included identity, consider the tuples belonging to that -identity. Group them into sets of matching tuples. Include the tuple -that matches the largest set, breaking ties in favor of the most recently -published, and then in favor of the smaller server descriptor digest. - - - -### Forward compatibility { #consensus-method-list } - -Future versions of Tor will need to include new information in the -consensus documents, but it is important that all authorities (or at least -half) generate and sign the same signed consensus. - -To achieve this, authorities list in their votes their supported methods -for generating consensuses from votes. Later methods will be assigned -higher numbers. Currently specified methods: - -```text - "1" -- The first implemented version. - "2" -- Added support for the Unnamed flag. - "3" -- Added legacy ID key support to aid in authority ID key rollovers - "4" -- No longer list routers that are not running in the consensus - "5" -- adds support for "w" and "p" lines. - "6" -- Prefers measured bandwidth values rather than advertised - "7" -- Provides keyword=integer pairs of consensus parameters - "8" -- Provides microdescriptor summaries - "9" -- Provides weights for selecting flagged routers in paths - "10" -- Fixes edge case bugs in router flag selection weights - "11" -- Don't consider BadExits when calculating bandwidth weights - "12" -- Params are only included if enough auths voted for them - "13" -- Omit router entries with missing microdescriptors. - "14" -- Adds support for "a" lines in ns consensuses and microdescriptors. - "15" -- Adds support for "p6" lines. - "16" -- Adds ntor keys to microdescriptors - "17" -- Adds "Unmeasured=1" flags to "w" lines - "18" -- Adds 'id' to microdescriptors. - "19" -- Adds "package" lines to consensuses - "20" -- Adds GuardFraction information to microdescriptors. - "21" -- Adds Ed25519 keys to microdescriptors. - "22" -- Instantiates Ed25519 voting algorithm correctly. - "23" -- Adds shared randomness protocol data. - "24" -- No longer lists routers that are not Valid in the consensus. - "25" -- Vote on recommended-protocols and required-protocols. - "26" -- Initialize bandwidth weights to 1 to avoid division-by-zero. - "27" -- Adds support for "a" lines in microdescriptor consensuses. - "28" -- Removes "a" lines from microdescriptors. - "29" -- Canonicalizes families in microdescriptors. - "30" -- Removes padding from ntor-onion-key. - "31" -- Uses correct parsing for bwweightscale and maxunmeasuredbw - when computing weights - "32" -- Adds special handling for MiddleOnly flag. - "33" -- Sets "publication" field in microdesc consensus "r" lines - to a meaningless value. - "34" -- Removes "package" lines from consensus. -``` - -Before generating a consensus, an authority must decide which consensus -method to use. To do this, it looks for the highest version number -supported by more than 2/3 of the authorities voting. If it supports this -method, then it uses it. Otherwise, it falls back to the newest consensus -method that it supports (which will probably not result in a sufficiently -signed consensus). - -All authorities MUST support method 25; authorities SHOULD support -more recent methods as well. Authorities SHOULD NOT support or -advertise support for any method before 25. Clients MAY assume that -they will never see a current valid signed consensus for any method -before method 25. - -(The consensuses generated by new methods must be parsable by -implementations that only understand the old methods, and must not cause -those implementations to compromise their anonymity. This is a means for -making changes in the contents of consensus; not for making -backward-incompatible changes in their format.) - -The following methods have incorrect implementations; authorities SHOULD -NOT advertise support for them: - -"21" -- Did not correctly enable support for ed25519 key collation. - - - -### Encoding port lists - -Whether the summary shows the list of accepted ports or the list of -rejected ports depends on which list is shorter (has a shorter string -representation). In case of ties we choose the list of accepted -ports. As an exception to this rule an allow-all policy is -represented as "accept 1-65535" instead of "reject " and a reject-all -policy is similarly given as "reject 1-65535". - -Summary items are compressed, that is instead of "80-88,89-100" there -only is a single item of "80-100", similarly instead of "20,21" a -summary will say "20-21". - -Port lists are sorted in ascending order. - -The maximum allowed length of a policy summary (including the "accept " -or "reject ") is 1000 characters. If a summary exceeds that length we -use an accept-style summary and list as much of the port list as is -possible within these 1000 bytes. \[XXXX be more specific.\] - - - -### Computing Bandwidth Weights - -Let weight_scale = 10000, or the value of the "bwweightscale" parameter. -(Before consensus method 31 there was a bug in parsing bwweightscale, so -that if there were any consensus parameters after it alphabetically, it -would always be treated as 10000. A similar bug existed for -"maxunmeasuredbw".) - -Starting with consensus method 26, G, M, E, and D are initialized to 1 and -T to 4. Prior consensus methods initialize them all to 0. With this change, -test tor networks that are small or new are much more likely to produce -bandwidth-weights in their consensus. The extra bandwidth has a negligible -impact on the bandwidth weights in the public tor network. - -Let G be the total bandwidth for Guard-flagged nodes. -Let M be the total bandwidth for non-flagged nodes. -Let E be the total bandwidth for Exit-flagged nodes. -Let D be the total bandwidth for Guard+Exit-flagged nodes. -Let T = G+M+E+D - -Let Wgd be the weight for choosing a Guard+Exit for the guard position. -Let Wmd be the weight for choosing a Guard+Exit for the middle position. -Let Wed be the weight for choosing a Guard+Exit for the exit position. - -Let Wme be the weight for choosing an Exit for the middle position. -Let Wmg be the weight for choosing a Guard for the middle position. - -Let Wgg be the weight for choosing a Guard for the guard position. -Let Wee be the weight for choosing an Exit for the exit position. - -Balanced network conditions then arise from solutions to the following -system of equations: - -Wgg*G + Wgd*D == M + Wmd*D + Wme*E + Wmg*G (guard bw = middle bw) -Wgg*G + Wgd*D == Wee*E + Wed*D (guard bw = exit bw) -Wed*D + Wmd*D + Wgd*D == D (aka: Wed+Wmd+Wdg = weight_scale) -Wmg*G + Wgg*G == G (aka: Wgg = weight_scale-Wmg) -Wme*E + Wee*E == E (aka: Wee = weight_scale-Wme) - -We are short 2 constraints with the above set. The remaining constraints -come from examining different cases of network load. The following -constraints are used in consensus method 10 and above. There are another -incorrect and obsolete set of constraints used for these same cases in -consensus method 9. For those, see dir-spec.txt in Tor 0.2.2.10-alpha -to 0.2.2.16-alpha. - -Case 1: E >= T/3 && G >= T/3 (Neither Exit nor Guard Scarce) - -In this case, the additional two constraints are: Wmg == Wmd, -Wed == 1/3. - -```text - This leads to the solution: - Wgd = weight_scale/3 - Wed = weight_scale/3 - Wmd = weight_scale/3 - Wee = (weight_scale*(E+G+M))/(3*E) - Wme = weight_scale - Wee - Wmg = (weight_scale*(2*G-E-M))/(3*G) - Wgg = weight_scale - Wmg - - Case 2: E < T/3 && G < T/3 (Both are scarce) -``` - -Let R denote the more scarce class (Rare) between Guard vs Exit. -Let S denote the less scarce class. - -Subcase a: R+D \< S - -In this subcase, we simply devote all of D bandwidth to the -scarce class. - -```text - Wgg = Wee = weight_scale - Wmg = Wme = Wmd = 0; - if E < G: - Wed = weight_scale - Wgd = 0 - else: - Wed = 0 - Wgd = weight_scale - - Subcase b: R+D >= S -``` - -In this case, if M \<= T/3, we have enough bandwidth to try to achieve -a balancing condition. - -Add constraints Wgg = weight_scale, Wmd == Wgd to maximize bandwidth in -the guard position while still allowing exits to be used as middle nodes: - -Wee = (weight_scale\*(E - G + M))/E -Wed = (weight_scale\*(D - 2*E + 4*G - 2*M))/(3*D) -Wme = (weight_scale\*(G-M))/E -Wmg = 0 -Wgg = weight_scale -Wmd = (weight_scale - Wed)/2 -Wgd = (weight_scale - Wed)/2 - -If this system ends up with any values out of range (ie negative, or -above weight_scale), use the constraints Wgg == weight_scale and Wee == -weight_scale, since both those positions are scarce: - -```text - Wgg = weight_scale - Wee = weight_scale - Wed = (weight_scale*(D - 2*E + G + M))/(3*D) - Wmd = (weight_Scale*(D - 2*M + G + E))/(3*D) - Wme = 0 - Wmg = 0 - Wgd = weight_scale - Wed - Wmd - - If M > T/3, then the Wmd weight above will become negative. Set it to 0 - in this case: - Wmd = 0 - Wgd = weight_scale - Wed - - Case 3: One of E < T/3 or G < T/3 - - Let S be the scarce class (of E or G). - - Subcase a: (S+D) < T/3: - if G=S: - Wgg = Wgd = weight_scale; - Wmd = Wed = Wmg = 0; - // Minor subcase, if E is more scarce than M, - // keep its bandwidth in place. - if (E < M) Wme = 0; - else Wme = (weight_scale*(E-M))/(2*E); - Wee = weight_scale-Wme; - if E=S: - Wee = Wed = weight_scale; - Wmd = Wgd = Wme = 0; - // Minor subcase, if G is more scarce than M, - // keep its bandwidth in place. - if (G < M) Wmg = 0; - else Wmg = (weight_scale*(G-M))/(2*G); - Wgg = weight_scale-Wmg; - - Subcase b: (S+D) >= T/3 - if G=S: - Add constraints Wgg = weight_scale, Wmd == Wed to maximize bandwidth - in the guard position, while still allowing exits to be - used as middle nodes: - Wgg = weight_scale - Wgd = (weight_scale*(D - 2*G + E + M))/(3*D) - Wmg = 0 - Wee = (weight_scale*(E+M))/(2*E) - Wme = weight_scale - Wee - Wmd = (weight_scale - Wgd)/2 - Wed = (weight_scale - Wgd)/2 - if E=S: - Add constraints Wee == weight_scale, Wmd == Wgd to maximize bandwidth - in the exit position: - Wee = weight_scale; - Wed = (weight_scale*(D - 2*E + G + M))/(3*D); - Wme = 0; - Wgg = (weight_scale*(G+M))/(2*G); - Wmg = weight_scale - Wgg; - Wmd = (weight_scale - Wed)/2; - Wgd = (weight_scale - Wed)/2; -``` - -To ensure consensus, all calculations are performed using integer math -with a fixed precision determined by the bwweightscale consensus -parameter (defaults at 10000, Min: 1, Max: INT32_MAX). (See note above -about parsing bug in bwweightscale before consensus method 31.) - -For future balancing improvements, Tor clients support 11 additional weights -for directory requests and middle weighting. These weights are currently -set at weight_scale, with the exception of the following groups of -assignments: - -Directory requests use middle weights: - -Wbd=Wmd, Wbg=Wmg, Wbe=Wme, Wbm=Wmm - -Handle bridges and strange exit policies: - -Wgm=Wgg, Wem=Wee, Weg=Wed - - - -## Computing consensus flavors - -Consensus flavors are variants of the consensus that clients can choose -to download and use instead of the unflavored consensus. The purpose -of a consensus flavor is to remove or replace information in the -unflavored consensus without forcing clients to download information -they would not use anyway. - -Directory authorities can produce and serve an arbitrary number of -flavors of the same consensus. A downside of creating too many new -flavors is that clients will be distinguishable based on which flavor -they download. A new flavor should not be created when adding a field -instead wouldn't be too onerous. - -Examples for consensus flavors include: - -```text - - Publishing hashes of microdescriptors instead of hashes of - full descriptors (see section 3.9.2). - - Including different digests of descriptors, instead of the - perhaps-soon-to-be-totally-broken SHA1. -``` - -Consensus flavors are derived from the unflavored consensus once the -voting process is complete. This is to avoid consensus synchronization -problems. - -Every consensus flavor has a name consisting of a sequence of one -or more alphanumeric characters and dashes. For compatibility, -the original (unflavored) consensus type is called "ns". - -The supported consensus flavors are defined as part of the -authorities' consensus method. - -All consensus flavors have in common that their first line is -"network-status-version" where version is 3 or higher, and the flavor -is a string consisting of alphanumeric characters and dashes: - -"network-status-version" SP version \[SP flavor\] NL - - - -### ns consensus - -The ns consensus flavor is equivalent to the unflavored consensus. -When the flavor is omitted from the "network-status-version" line, -it should be assumed to be "ns". Some implementations may explicitly -state that the flavor is "ns" when generating consensuses, but should -accept consensuses where the flavor is omitted. - - - -### Microdescriptor consensus - -The microdescriptor consensus is a consensus flavor that contains -microdescriptor hashes instead of descriptor hashes and that omits -exit-policy summaries which are contained in microdescriptors. The -microdescriptor consensus was designed to contain elements that are -small and frequently changing. Clients use the information in the -microdescriptor consensus to decide which servers to fetch information -about and which servers to fetch information from. - -The microdescriptor consensus is based on the unflavored consensus with -the exceptions as follows: - -"network-status-version" SP version SP "microdesc" NL - -\[At start, exactly once.\] - -The flavor name of a microdescriptor consensus is "microdesc". - -Changes to router status entries are as follows: - -```text - "r" SP nickname SP identity SP publication SP IP SP ORPort - SP DirPort NL - - [At start, exactly once.] - - Similar to "r" lines in section 3.4.1, but without the digest element. - - "a" SP address ":" port NL - - [Any number] - - Identical to the "r" lines in section 3.4.1. -``` - -(Only included when the vote is generated with consensus-method 14 -or later, and the consensus is generated with consensus-method 27 or -later.) - -"p" ... NL - -\[At most once\] - -Not currently generated. - -Exit policy summaries are contained in microdescriptors and -therefore omitted in the microdescriptor consensus. - -"m" SP digest NL - -\[Exactly once.\*\] - -"digest" is the base64 of the SHA256 hash of the router's -microdescriptor with trailing =s omitted. For a given router -descriptor digest and consensus method there should only be a -single microdescriptor digest in the "m" lines of all votes. -If different votes have different microdescriptor digests for -the same descriptor digest and consensus method, at least one -of the authorities is broken. If this happens, the microdesc -consensus should contain whichever microdescriptor digest is -most common. If there is no winner, we break ties in the favor -of the lexically earliest. - -\[\*Before consensus method 13, this field was sometimes erroneously -omitted.\] - -Additionally, a microdescriptor consensus SHOULD use the sha256 digest -algorithm for its signatures. - - - -## Exchanging detached signatures - -Once an authority has computed and signed a consensus network status, it -should send its detached signature to each other authority in an HTTP POST -request to the URL: - -`http:///tor/post/consensus-signature` - -\[XXX Note why we support push-and-then-pull.\] - -All of the detached signatures it knows for consensus status should be -available at: - -`http:///tor/status-vote/next/consensus-signatures.z` - -Assuming full connectivity, every authority should compute and sign the -same consensus including any flavors in each period. Therefore, it -isn't necessary to download the consensus or any flavors of it computed -by each authority; instead, the authorities only push/fetch each -others' signatures. A "detached signature" document contains items as -follows: - -"consensus-digest" SP Digest NL - -\[At start, at most once.\] - -The digest of the consensus being signed. - -"valid-after" SP YYYY-MM-DD SP HH:MM:SS NL -"fresh-until" SP YYYY-MM-DD SP HH:MM:SS NL -"valid-until" SP YYYY-MM-DD SP HH:MM:SS NL - -\[As in the consensus\] - -"additional-digest" SP flavor SP algname SP digest NL - -\[Any number.\] - -For each supported consensus flavor, every directory authority -adds one or more "additional-digest" lines. "flavor" is the name -of the consensus flavor, "algname" is the name of the hash -algorithm that is used to generate the digest, and "digest" is the -hex-encoded digest. - -The hash algorithm for the microdescriptor consensus flavor is -defined as SHA256 with algname "sha256". - -```text - "additional-signature" SP flavor SP algname SP identity SP - signing-key-digest NL signature. - - [Any number.] -``` - -For each supported consensus flavor and defined digest algorithm, -every directory authority adds an "additional-signature" line. -"flavor" is the name of the consensus flavor. "algname" is the -name of the algorithm that was used to hash the identity and -signing keys, and to compute the signature. "identity" is the -hex-encoded digest of the authority identity key of the signing -authority, and "signing-key-digest" is the hex-encoded digest of -the current authority signing key of the signing authority. - -The "sha256" signature format is defined as the RSA signature of -the OAEP+-padded SHA256 digest of the item to be signed. When -checking signatures, the signature MUST be treated as valid if the -signature material begins with SHA256(document), so that other -data can get added later. -\[To be honest, I didn't fully understand the previous paragraph -and only copied it from the proposals. Review carefully. -KL\] - -"directory-signature" - -\[As in the consensus; the signature object is the same as in the -consensus document.\] - - - -## Publishing the signed consensus { #publishing-signed-consensus } - -The voting period ends at the valid-after time. If the consensus has -been signed by a majority of authorities, these documents are made -available at - -`http:///tor/status-vote/current/consensus.z` - -and - -`http:///tor/status-vote/current/consensus-signatures.z` - -```text - [XXX current/consensus-signatures is not currently implemented, as it - is not used in the voting protocol.] - - [XXX possible future features include support for downloading old - consensuses.] - - The other vote documents are analogously made available under - -http:///tor/status-vote/current/authority.z -http:///tor/status-vote/current/.z -http:///tor/status-vote/current/d/.z -http:///tor/status-vote/current/bandwidth.z -``` - -once the voting period ends, regardless of the number of signatures. - -The authorities serve another consensus of each flavor "F" from the -locations - -```text -/tor/status-vote/(current|next)/consensus-F.z. and -/tor/status-vote/(current|next)/consensus-F/+....z. -``` - -The standard URLs for bandwidth list files first-appeared in Tor 0.3.5. -- cgit v1.2.3-54-g00ecf