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

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

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.

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

Maybe some pseudocode would help me understand better.

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?

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.

5) In section 3.1.1, can we include a formula for the bounds of the n'th bin?

6) In section 3.1.1, why is a uniform distribution used, and not some
other distribution?

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

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.

9) Can we include an example definition of one of these state
machines, with pseudocode included?

10) Should clients (eventually) begin killing circuits if they receive
padding from an unexpected place?


cheers,

[Mike Perry]

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

Post by Nick Mathewson
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*.

Post by Nick Mathewson
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.

Post by Nick Mathewson
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

Post by Nick Mathewson
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

Post by Nick Mathewson
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..

Post by Nick Mathewson
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()).

Post by Nick Mathewson
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).

Post by Nick Mathewson
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.

Post by Nick Mathewson
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.

Post by Nick Mathewson
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.

Post by Nick Mathewson
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.

[Nick Mathewson]

Post by Mike Perry

Post by 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}"?

Post by Mike Perry

Post by Nick Mathewson
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.

Post by Mike Perry
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 :)

Post by Mike Perry

Post by Nick Mathewson
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.

Post by Mike Perry
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.

Post by Nick Mathewson
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.

Post by Mike Perry

Post by Nick Mathewson
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
https://github.com/mikeperry-tor/tor/commit/12ff82aa23baec4a6421fa299d152126870f6caf
And the circpad_deliver_* functions, which dissect those into sent and
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.

Post by Mike Perry

Post by Nick Mathewson
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..

Post by Nick Mathewson
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()).

Post by Nick Mathewson
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?

Post by Mike Perry

Post by Nick Mathewson
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.

Post by Nick Mathewson
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.

Post by Nick Mathewson
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).

Post by Mike Perry

Post by Nick Mathewson
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,