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

[Mike Perry]

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

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

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*.
 
> 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).

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

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

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


-- 
Mike Perry