Add circuit padding to padding-spec.txt and write a doc for researchers

There are a few things that can be done to the spec to improve them.

For the basics, we can improve the sectioning and also add some indentation to make it more clear how sections are structured (for example, to make it clear the distinctions between histograms and prob distrs).

changed milestone to %Tor: unspecified

added 041-proposed component::core tor/tor milestone::Tor: unspecified network-team-roadmap-august owner::mikeperry padding points::2 priority::high resolution::fixed reviewer::asn scalability-roadmap severity::normal sponsor::2 status::closed tor-cell tor-relay tor-spec type::defect wtf-pad labels

Also update spec (and maybe code) with the discussion from https://github.com/torproject/tor/pull/461#discussion_r239949925 .

Trac:
Keywords: N/A deleted, 041-proposed added

Prop 254 also needs to be folded into padding-spec.txt.

Trac:
Points: N/A to 2

Let's just supercede the proposal with the padding-spec and a doc for creating state machines. The actual final spec is more important than the historical proposal archive anyway.

Trac:
Priority: Medium to High
Summary: Improve quality of prop254 spec to Write padidng spec and a doc for researchers

Trac:
Summary: Write padidng spec and a doc for researchers to Add circuit padding to padding-spec.txt and write a doc for researchers

Trac:
Sponsor: N/A to Sponsor2

Reparent children of #28637 (moved) into #28631 (moved)

Trac:
Parent: #28637 (moved) to #28631 (moved)

Trac:
Parent: #28631 (moved) to N/A

Trac:
Keywords: N/A deleted, network-team-roadmap-2019-Q1Q2 added

Ideas that are popping into my head now that #28634 (moved) is done:

One section of the doc should walk the reader through the fields of circpad_machine_spec_t, circpad_state_t, and their interaction with circpad_machine runtime_t (which is invisible to them but feature choice has consequences on how much memory and CPU time circpad_machine_runtime_t requires). This section of the doc should also describe potential features from the wtf-pad tag ticket list, but make it clear we're unlikely to implement them unless someone tells us them need them. And also mention that we're happy to accept patches for any useful feature or flag.

The second section of the doc should have a pile of example machines, to show that the system can do much much more than we're currently using it for. We should not only explain #28634 (moved) and why it chose the options it did for performance reasons, but also explain that there's more features we can implement easily. We should highlight a few of those from the wtf-pad tag ticket list, and also show some example machines that do the following:

• Netflow/channelpadding as circuitpadding to the guard
• Original WTF-PAD
• APE (https://www.cs.kau.se/pulls/hot/thebasketcase-ape/)
• Constant rate cover traffic from the guard (will require #29494 (moved) implementation to make cell delivery decisions based on cmux queue status, but as far as machines are concerned, this will just be a flag they set)
• A reduced padding machine vs not (perhaps using a heavier-padding-count #28634 (moved) example)

We also want to discuss some high level interactions with Tor:

• Explain our load balancing plans
• Explain how machine precedence is meant to work when multiple machines exist for the same conditions

Other things to do: I want to stop referring to what we implemented as "WTF-PAD" in technical documentation. WTF-PAD was the implementation of the system described by the research paper http://arxiv.org/pdf/1512.00524. The stuff in Tor now is NOT WTF-PAD. If people start writing research papers about how they attacked the new WTF-PAD as implemented in Tor, all hell will break loose and nobody will know what anybody is talking about anymore.

We should update the Tor spec/proposal (aka https://lists.torproject.org/pipermail/tor-dev/2019-May/013822.html) accordingly.

Additionally, I updated the comments in https://github.com/torproject/tor/blob/master/src/core/or/circuitpadding_machines.c#L60 to make it easier to understand, but these did not get updated in the spec. So we should do that too.

One more thing to cover in the research doc: We should explain how we will accept and deploy changes to the padding machine featureset itself (one potentially useful change is for all state transitions have a probability associated with them, to explicitly support HMM representations).

Trac:
Status: new to assigned
Owner: N/A to mikeperry

Trac:
Keywords: network-team-roadmap-2019-Q1Q2 deleted, network-team-roadmap-august, scalability-roadmap added

We should be sure to document potential shutdown sync issues of #30992 (moved) in a "known bugs/implementation issues" section. I bet there will be other things for such a section, too.

Ok, here's a branch with an updated padding-spec. Has a couple XXX's (we need the new NSF numbers and it needs to cite the researcher developer doc that still needs to be written).

https://github.com/mikeperry-tor/torspec/tree/hs-padding-spec

Developer doc WIP lives here for now: https://github.com/mikeperry-tor/tor/blob/circuitpadding-dev-doc/doc/circuitpadding-dev-readme.txt

Putting myself as the reviewer here.

Trac:
Reviewer: N/A to asn

Oops I thought this was needs_review so I took a look, but it seems like it's not.

Anyhow, spec patch looks good.

And also some high-level comments on the developer doc:

• Let's make it markdown since both github and gitlab support md files these days and it seems to be the norm? I doubt researchers appreciate text files that much.
• Let's add a "High-level system overview" section before the "Header walkthrough" that explains how this whole system works in two paragraphs or so.
• On the 2. What to consider when creating a new machine, I'd also like an explanation of how machine numbers should work, and how to choose your machine number to avoid conflicts with other tor versions etc.
• Other than that, looks good to me.

Ok I think this is finally ready. I just squashed down everything into one commit for both the dev doc and the quickstart guide.

This is a doc-only commit. It only needs to be merged into master (though we do need it soon so we can link to it in the website oracle blog post).

https://github.com/torproject/tor/pull/1591

Trac:
Status: assigned to needs_review

LGTM but I think a changes file might be good here for the future.

Trac:
Status: needs_review to needs_revision

Ok I pushed the changes file and a small fixup to Section 7.5 for clarification

Trac:
Status: needs_revision to needs_review

Merged! Thanks!

Trac:
Status: needs_review to closed
Resolution: N/A to fixed

closed

changed time estimate to 16h

mentioned in issue #31806 (moved)

moved to tpo/core/tor#28804 (closed)