[tor-dev] A few wtf-pad/prop254 questions

Wed Nov 7 23:05:08 UTC 2018

On Wed, Nov 7, 2018 at 5:41 PM Mike Perry <mikeperry at torproject.org> wrote:
>
> Nick Mathewson:
> > Hi!  I'm looking over prop254 and I have a few questions or
> > clarification requests that I hope will make things clearer to me.
> > Some of these are probably "wrong questions" that stem from a
> > misunderstanding of the underlying proposal.
> >
> > 1) What does "ito" stand for?  Is it documented?
>
> "Inactive TimeOut". It is documented in Proposal #251 (Section 2.1).

Okay. Can we rename it to "timeout_{min,max}"?

> > 2) How is RTT measurement meant to work?  It seems to me from reading
> > section 3.1 that middle if a middle node sees a delay of N ms between
> > getting a cell in the forward direction, and getting a cell in the
> > backward direction, then it will conclude that the RTT is at least N
> > ms.
>
> Yes, where "forward" means "away from origin" and backward means
> "towards origin". What the middle node is trying to measure is the
> remaining RTT of the rest of the circuit towards the exit, so that it
> can simulate response delays if it wishes.

Let's document that.

> I found Tor's interchanging use of "forward", "outgoing", "incoming",
> and "backward" to be somewhat maddening for reasoning about the state
> machines. So I defined everything in terms of direction of packets *from
> the perspective of the state machine*.

Okay, but let's make that vocab shift explicit so that people who feel
like they grok the old (janky?) status quo can still understand the
new hotness :)

> > But that doesn't make sense to me -- the latter cell might have been
> > sent in response to a different cell, or sent asynchonously, and not
> > in response to the first cell at all.  AFAICT unless we can be
> > reasonably sure that we are seeing a packet that is sent in response
> > to an earlier cell, be sure that we're actually measuring min(rtt).
>
> This is why the RTT measurement stops as soon as two back-to-back cells
> arrive in either direction on a circuit. Two back-to-back cells in
> either direction means the 1:1 request/response pattern of circuit
> setup/RELAY_BEGIN is now over (though we do wait for one more response
> counting time from the head of the first request packet train, to
> measure optimistic data response times).

This still seems to me that we're going to get wrong answers!

For EXTEND/EXTENDED pairs, there is an unusual delay in between
because of the delay from onionskin queues and crypto delays.

For BEGIN/CONNECTED pairs, there is an unusual delay in waiting for
the target service to respond to the exit node.

For EXTENDED/BEGIN pairs, there could be a HUGE delay, since the
circuit might be preemptive, and the client might wait indefinitely to
actually use it.

> Note that there is a huge looming issue with how we decide to handle
> var_cell_t. Right now, Proposal #249 is very ambiguous wrt how
> RELAY_EARLY and var cells interact. If we instead made it a MUST that
> the first var_cell piece is always RELAY_EARLY and subsequent fragments
> are RELAY, then middle nodes could still compute RTT during circuit
> setup using this back-to-back heuristic for RELAY_EARLY cells.
> Otherwise, I am not sure what we can do here.
>
> > Maybe some pseudocode would help me understand better.
>
> Current implementation is in circpad_estimate_circ_rtt_on_receieved()
> and circpad_estimate_circ_rtt_on_send()
> https://github.com/mikeperry-tor/tor/blob/adaptive_padding-rebased_0.3.6-squashed/src/core/or/circuitpadding.c#L1245

For this and other questions where you reference the code: I like this
and it's great, but the spec will need to explain what the code needs
to do.  If we make the proposal explain what the code does, that will
make updating the spec easier.

> > 3) In section 3.1, I'm assuming that "cell sent" and "cell received"
> > refer to a cell that we are originating, and a cell that we are
> > receiving, recognizing, and processing: relayed cells don't count.  Is
> > that correct?
>
> Relayed cells do count. Relayed cells are always "non-padding".
>
> But yes you are correct about the directionality here.
>
> To see exactly what this means, please look at this commit, which adds
> the hooks into Tor's cell processing for both relayed cells and
> originating cells:
> https://github.com/mikeperry-tor/tor/commit/12ff82aa23baec4a6421fa299d152126870f6caf
>
> And the circpad_deliver_* functions, which dissect those into sent and
> received padding and non-padding events:
> https://github.com/mikeperry-tor/tor/blob/adaptive_padding-rebased_0.3.6-squashed/src/core/or/circuitpadding.c#L1782

As above; let's incorporate this information about what the code does
into the proposal/spec, so it can explain what the code is _supposed_
to do.

> > 4) I like that section 3.1.1 specified delays in terms of
> > microseconds, but we should be aware that with current implementation
> > restrictions, microsecond-level precision is unlikely to actually be
> > realistic.  I hope that's okay.
>
> Yeah I think it should be fine but we'll see..
>
> > 5) In section 3.1.1, can we include a formula for the bounds of the n'th bin?
>
> Hrmm, I had one in the form of pseudocode but asn said it was not
> useful. He asked for this prose description instead... But maybe I can
> write a succinct one-liner that is not too confusing. We certainly had
> them, and have them in the source (see circpad_histogram_bin_to_usec()
> and circpad_histogram_usec_to_bin()).
>
> > 6) In section 3.1.1, why is a uniform distribution used, and not some
> > other distribution?
>
> Interpolating seemed excessively complex, and it was not clear it is
> worth it. In order to interpolate, we'd have to get the relative bin
> counts of the current bin, the next bin, compute those weights relative
> to total remaining weight, and then pick some probability distribution
> to sample piece-wise between these two weights?
>
> Could be done but none of the research so far has indicated that very
> high distribution resolution was that important (though I am not sure if
> the effects of distribution resolution was comparatively studied though,
> either).

This is plausible; can/should we amend the proposal to _allow_ interpolation?

As it stands, any implementation that does anything other than a
uniform distribution is wrong. Is that what we want to say?

> > 7) In section 3.1 (I'm not sure where) can we specify how bins are
> > initialized, and how they are refilled (if at all)?
>
> Oh this should definitely be in 3.1.2, where we mention the internal
> "bins empty" event. If the "bins empty" event does not cause a state
> transition, the bins are refilled. I can do a fixup to add this
> sentence.
>
> Maybe we want to make this token refill optional.. Would be kind of
> weird, though.
>
> > 8) For machine negotiation (in section 3.3), I'd suggest that we have
> > the client send a list of acceptable machines in preference order,
> > rather than demanding a particular machine.  I think a 16-bit
> > identifier is safer than an 8-bit one.  We should reserve an area of
> > the identifier space for experimental use.
>
> These are good ideas. I'll put them in the TODO file for the
> implementation and update the code and proposal for this.
>
> > 9) Can we include an example definition of one of these state
> > machines, with pseudocode included?
>
> Hrmm.. I highly suggest checking out Tobias's blog posts, which the
> proposal cites in Section 4. They are very succinct and accurate. If
> they are insufficient, please explain how they fall short of what you
> want.

That's good but let's summarize one in an appendix or something, so
it's clear what we mean? Feel free to just copy and past from the
appropriate part of one of these posts (with permission of course).

> > 10) Should clients (eventually) begin killing circuits if they receive
> > padding from an unexpected place?
>
> Yes. This is mentioned in Section 5.3. The vanguards addon will already
> do this when run with the branch.

IIUC, 5.3 only says that the vanguards add-on should do this.  If
clients should do so too, let's say so.

cheers,
-- 
Nick