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,
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.
- What does "ito" stand for? Is it documented?
"Inactive TimeOut". It is documented in Proposal #251 (Section 2.1).
- 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-squ...
- 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/12ff82aa23baec4a6421fa299d152126...
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-squ...
- 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..
- 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()).
- 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).
- 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.
- 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.
- 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.
- 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.
On Wed, Nov 7, 2018 at 5:41 PM Mike Perry mikeperry@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.
- 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}"?
- 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-squ...
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.
- 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/12ff82aa23baec4a6421fa299d152126...
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-squ...
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.
- 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..
- 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()).
- 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?
- 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.
- 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.
- 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).
- 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,
-
Mike Perry -
Nick Mathewson -
Nick Mathewson