[tor-dev] Proposal: Tor bandwidth measurements document format
teor
teor2345 at gmail.com
Wed May 2 12:39:12 UTC 2018
Hi Nick,
Juga asked me to comment on your review, so she could read it before our bandwidth meeting this week. If I don't comment on a suggestion, you should assume I agree with it.
Backwards Compatibility
Nick asked about backwards compatibility. This format uses semantic versioning. Tor 0.2.9 - 0.3.3 reads format version 1.0.0. It also reads format 1.1.0, but ignores the new features with warnings.
If we want to introduce an incompatible format, we should call it 2.0.0, because semantic versioning requires a major increment for breaking changes.
Here's how we could add the new format:
* The new format should have a new torrc option.
* Tor should be modified to support the new format, and we should put time on the roadmap for people to work on implementing, testing, or reviewing it.
* Either we should backport the new format to the latest stable release, or sbws should produce both formats.
The current implementation has at least one security bug, some weird order restrictions, and some line length restrictions. So I would support re-implementing it using the standard directory document parsing code. Even if that takes more time.
Testing the format
Most of us don't have a spare directory authority for testing.
If you run chutney with my bwfile branch, all the authorities in the network read /tmp/bwfile for every consensus. Look for the warnings at the end of the chutney output.
The basic-min network is fast:
chutney/tools/test-network.sh --flavour basic-min
Here's the branch:
https://github.com/teor2345/chutney/commit/ebdb4760fbcae40979ab248e4208c27a71cccb11
I've already found one minor security bug using this branch: #26007.
Next Steps
I'm going to be away next week for a week and a half. I encourage other people to make decisions while I'm away, so we can keep making progress.
> On 1 May 2018, at 22:36, Nick Mathewson <nickm at alum.mit.edu> wrote:
>
> Hi, Juga!
>
> This is a review of the document from https://raw.githubusercontent.com/juga0/torspec/c7f06023dd1d5d47adad128de541f8eba2a13bfb/bandwidth-file-spec.txt , which I *think* is the same as the document you have below.
>
> I'm reviewing this as though it were a fully new format, since I'm not sure how much we already have locked-in based on existing code, and how much is new. We might decide that backward compatibility is more important than consistency, and if so, we won't want to take all of my recommendations here.
>
> > Tor Bandwidth Measurements Document Format
> > juga
> > teor
> >
> > 1. Scope and preliminaries
> >
> > This document describes the format of Tor's bandwidth measurements
Replace measurements document with list?
> > document, version 1.0.0 and later.
>
> Suggestion: Maybe explicitly say "1.0.0, 1.1.0, and later"?
>
> > Since Tor version 0.2.4.12-alpha the directory
> > authorities use the bandwidth measurements document called
Replace measurements document with list?
> > "V3BandwidthsFile" and produced by Torflow [1]
> > (format described in README.spec.txt [2]).
>
> Recommendation: "Format described in Torflow's README.spec.txt".
>
> Explanation needed: Is this a new format, or a new specification of the
> existing format? Let's say so here.
A new specification for the existing format 1.0.0.
A new format 1.1.0, which is backwards compatible with 1.0.0 parsers.
> Question: If this is a different format, and we're calling it version
> 1.0.0, what should we call the old one? But later it seems that we're
> introducing 1.1.0, and we're calling the old one 1.0.0.
"The Legacy Torflow format" or just "legacy"?
> Suggestion: let's be explicit that we're only describing the format
> here, and *not* describing how bwauths generate their data.
I agree. We want to leave room for peerflow and future schemes.
So we might want to:
* replace every "measurements document" with "list"
* replace every "measurements scanner" with "generator"
> > The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL
> > NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and
> > "OPTIONAL" in this document are to be interpreted as described in
> > RFC 2119.
> >
> > 1.2. Acknowledgements
> >
> > The original bandwidth measurement scanner (Torflow)
Replace measurement scanner with generator?
> and format was
> > created by mike. Teor suggested to write this specification while
> > contributing on pastly's new bandwidth scanner implementation.
> >
> > This specification was revised after feedback from:
> >
> > XXX
Please update.
> > 1.3 Outline
> >
> > The bandwidth measurements mentioned in sections 3.4.1 and 3.4.2
Hmm, the dir-spec calls them measurements.
Maybe we should fix it as well.
> > of "Tor directory protocol" (dir-spec.txt) [3] are obtained
> > by bandwidth authorities,
Is a bandwidth authority a directory authority that votes for bandwidths?
Or is it a bandwidth generator that produces the bandwidth file?
> which generate a file storing information
> > on relays' measured bandwidth capacities.
Remove "measured".
> >
> > 1.4. Format Versions
> >
> > 1.0.0 - The legacy fallback bandwidth measurements document format
Instead of "bandwidth measurements document format", say "bandwidth list"?
> >
> > 1.1.0 - Adds key_value lines to the header, format version,
> > optional ones and section separator.
>
> Information: Let's repeat in this section which versions of Tor can
> consume these versions.
All Tor versions can consume format version 1.0.0.
All Tor versions can consume format version 1.1.0, but they warn on header lines.
See https://trac.torproject.org/projects/tor/ticket/25960
> > 2. Format details
> >
> > Bandwidth measurements MUST contain the following sections:
And if they don't, the file SHOULD be ignored.
> > - Header (exactly once)
> > - Relays measurements (zero or more times)
>
> Grammar suggestion: "Relay measurements".
Replace "measurements" with "bandwidths"?
> > 2.1. Definitions
> >
> > The following nonterminals are defined in dir-spec.txt, sections
> > 1.2., 2.1.1., 2.1.3.:
> >
> > Int
> > SP (space)
> > NL (newline)
> > Keyword
> > ArgumentChar
> > fingerprint (hexdigest)
>
> Does this have to start with a "$" ? I think it does. Maybe we should be explicit about that.
It does. And we should.
> > nickname
> >
> > Nonterminals defined in "Tor Directory List Format" (dir-list-spec.txt),
> > section 2.2.1.:
> >
> > version_number
> >
> > We define the following nonterminals:
> >
> > value ::= ArgumentChar+
Excluding SP
> > key_value ::= Keyword "=" value
> > line ::= ArgumentChar* NL
> > timestamp ::= Int
> > bandwidth ::= Int
> > relay_line ::= key_value (SP key_value)* NL
> >
> > 2.2. Header format
> >
> > Some header lines MUST appear in specific positions, as documented below.
And if they don't, the file SHOULD be ignored.
> > All other lines can appear in any order.
> >
> > There MUST NOT be multiple key_value header lines with the same key.
And if there are, the parser SHOULD choose an arbitrary line.
All lines in the file MUST be 510 characters or less, to allow for the trailing newline and NUL characters. (The previous limit was 254 characters in Tor 0.2.6.2-alpha and earlier.)
The parser MAY ignore longer lines.
Should we lift this restriction in 1.1.0?
> Maybe this line belongs below in the key_value section?
>
> > It consists of:
> >
> > timestamp NL
> >
> > [At start, exactly once.]
> >
> > The Unix Epoch time in seconds when the file was created.
>
> Question: Why no keyword and equal sign here? Is this a legacy thing?
Yes, tor expects a Unix timestamp on a single line by itself.
> Also, wouldn't it be more standard to have it be in YYYY-MM-DDTHH:MM:SS
> format?
Tor refuses to read bandwidth files unless they start with an integer on a line by itself. So this would be a breaking change.
> > "version=" version_number NL
> >
> > [In second position, zero or one time.]
> >
> > The specification document format version.
> > It uses semantic versioning [5].
> >
> > This line has been added in version 1.1.0 of this specification.
> >
> > Version 1.0.0 documents do not contain this line, and the
> > version_number is considered to be "1.0.0".
>
> General concern: I question the use of = signs here in the headers. If
> we use "SP" instead, then we can reuse a lot of the same machinery tor
> currently uses to parse other documents.
I think using SP is fine.
But if we want to re-use the parsing machinery, we probably need to add a keyword to the initial timestamp. That would be a breaking change.
> > "software=" value NL
> >
> > [Zero or one time.]
> >
> > The name of the software that created the document.
> >
> > This line has been added in version 1.1.0 of this specification.
> >
> > Version 1.0.0 documents do not contain this line, and the software is
> > considered to be "torflow".
> >
> > "software_version=" value NL
> >
> > [Zero or one time.]
> >
> > The version of the software that created the document.
> > The version may be a version_number, a git commit, or some other
> > version scheme.
> >
> > This line has been added in version 1.1.0 of this specification.
If we use SP as a separator, we can make these two lines:
"software" SP name_value SP version_value NL
> > "scanner_started=" timestamp NL
> >
> > [Zero or one time.]
> >
> > The Unix Epoch time in seconds when the scanner that generates the
> > measurements document started.
> >
> > This line has been added in version 1.1.0 of this specification.
>
> See note above about time format. YYYY-MM-DDTHH:MM:SS is how we specify
> times elsewhere in Tor.
This is a new field, so we can choose the format.
> > "earliest_measurement=" timestamp NL
> >
> > [Zero or one time.]
> >
> > The Unix Epoch time in seconds when the first relay measurement
> > was obtained.
> >
> > This line has been added in version 1.1.0 of this specification.
>
> See note above about time format.
>
> > key_value NL
> >
> > [Zero or more times.]
> >
> > Future format versions may include additional key_value header lines.
> > Additional header lines will be accompanied by a minor version increment.
> >
> > Implementations MAY add additional header lines as needed. This
> > specification SHOULD be updated to avoid conflicting meanings for the
> > same header keys.
> >
> > Parsers MUST NOT rely on the order of these additional lines.
> >
> > Additional header lines MUST NOT use any keywords specified in the
> > relay measurements format.
And if there are, the parser MAY ignore conflicting keywords.
> > If a header line does not conform to this format, the line SHOULD be
> > ignored by parsers.
>
> Suggestion: say what recipients of this document should do with
> unrecognized data. In general, it's good for forward compatibility to
> say something like, "Recipients MUST ignore key_value lines if they do
> not recognize the keyword. Recipients MUST ignore any extra material in
> a line that they do not recognize."
We should specify what parsers should do with every MUST in the document.
> Also see suggestion above about using SP as our separator rather than
> "=" for consistency with other documents Tor parses.
>
> > NL
> >
> > [Zero or one time.]
> >
> > The header ends.
> >
> > This line has been added in version 1.1.0 of this specification.
> >
> > For version 1.0.0 documents, the header ends when the first relay
> > measurement line is found conforming to the next section.
>
> Suggestion: Replace this empty line with an explicit keyword, for
> consistency with other documents.
>
> > 2.3. Relay measurements format
> >
> > It consists of zero or more relay_line with the measurement results
> > of relays in arbitrary order.
> >
> > There can be at most one relay_line per relay identity (fingerprint).
> >
> > There MUST NOT be multiple key_value pairs with the same key in the same
> > relay_line.
And if there are, the parser SHOULD choose an arbitrary value.
> > Each relay_line MUST include the following key_value in arbitrary order:
>
> Do existing implementations accept arbitrary order here?
Existing Tor implementations do not accept node_id at the end of a line.
https://trac.torproject.org/projects/tor/ticket/26004
We should:
* add this as a MUST NOT in 1.0.0, and
* allow it in 1.1.0, with a list of tor versions that support it
If we use the standard directory parser, each relay line will have to start with a keyword. Perhaps we should use "b" or "r" or "n". This would be a breaking change.
> > "node_id=" fingerprint
> >
> > [Exactly once.]
> >
> > The fingerprint of the relay being measured.
>
> Suggestion: Add a field to hold the Ed25519 Identity of the relay being
> measured. Say that implementations SHOULD include both RSA fingerprint
> and Ed25519 identity, and that implementations SHOULD accept lines that
> contain at least one of them.
Suggestion: the ed25519 IDs should be base64 encoded, without a trailing =, because a trailing = makes the format ambiguous.
> > "bw=" bandwidth
> >
> > [Exactly once.]
> >
> > The measured bandwidth of this relay.
> >
> > Tor accepts zero bandwidths, but they trigger bugs in older Tor
> > implementations. Therefore, implementations SHOULD NOT produce zero
> > bandwidths. Instead, they SHOULD use one as their minimum bandwidth.
And if there are zero bandwidths, the parser MAY ignore them.
> > Multiple measurements can be aggregated using an averaging scheme, such
> > as a mean, median, or decaying average.
> >
> > Torflow scales bandwidths to kilobytes per second. Other implementations
> > SHOULD use kilobytes per second for their initial bandwidth scaling.
> >
> > If different implementations or configurations are used in votes for the
> > same network, their measurements MAY need further scaling. See Appendix B
> > for information about scaling, and one possible scaling method.
> >
> > key_value
> >
> > [Zero or more times.]
>
> Technically, this isn't a key_value, because a "value" is made of
> ArgumentChar, and ArgumentChar can contain spaces. So if we were
> parsing
> "foo=abc bar=def"
> we might be parsing either one key_value ("foo", "abc bar=def") or two
> ("foo", "abc"), ("bar, "def").
Let's exclude SP from value to resolve this issue.
> > Future format versions may include additional key_value pairs on a relay_line.
> > Additional key_value pairs will be accompanied by a minor version increment.
> >
> > Implementations MAY add additional relay key_value pairs as needed. This
> > specification SHOULD be updated to avoid conflicting meanings for the
> > same relay keys.
> >
> > Parsers MUST NOT rely on the order of these additional key_value pairs.
> >
> > Additional key_value pairs MUST NOT use any keywords specified in the
> > header format.
And if there are, the parser MAY ignore conflicting keywords.
> As above, let's say that a parser should ignore key_value entries with
> keywords that it doesn't recognize.
>
> >
> > If a relay line does not conform to this format, the line SHOULD be
> > ignored by parsers.
> >…
T
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20180502/a6e1de67/attachment-0001.html>
More information about the tor-dev
mailing list