Figure out a "good" congestion control strategy.

[Yawning]

Right now, all the inter-node traffic is done over TCP/IP links which ensures that the network is internet friendly. However within the network at a higher level, there is no congestion control beyond mixes and providers dropping packets to keep internal queue latency down. On the client side, mailproxy's send scheduler by default will send a packet once every 10 sec (approximate with intentional jitter of +- 5 sec), and while a rather conservative choice, the parameter is tunable and there is nothing to stop misbehaving clients from sending faster (See: katzenpost/katzenpost#159).

This could possibly be improved for better network health though how to do so is not immediately obvious. The main issues with using loss as a signalling for congestion for this network is that it can take considerable amounts of time (dependent on lambda) for the originator of a lost packet to detect the loss, and due to the per-packet path selection the relevance of any given loss incident on subsequent traffic is questionable.

To be put in simpler terms, backing off based on a loss that happened minutes if not hours ago on a part of the network that may not even be utilized, will only lead to poor network utilization.

[Yawning]

The closest equivalent to the per-packet congestion avoidance problem is probably something like low data volume UDP with insufficient return traffic to maintain an RTT estimate. While pedants will point out that mixnet has an RTT estimate per packet, said estimate almost entirely dependent on lambda rather than the status of the actual network.

See: https://tools.ietf.org/html/rfc8085#section-3.1.3

[willscott]

You basically suggest what seems like the logical answer to this problem in https://github.com/katzenpost/katzenpost/issues/159

The entry mix should be able to maintain a much more temporally relevant estimation of congestion /utilization across the overall traffic of the mix, and communicate that back to clients.

Rather than just a TCP window, that seems to suggest that the server should communicate a suggested delay before next transmission, and should be able to discard excessive traffic from noncompliant clients.

[david415]

here's my thoughts on this:

• in the Loopix paper client send scheduler models a poisson process with parameter lambda-p. therefore if we want some kind of exponential back off we can do so by manipulating lambda-p. mu (time tau) controls the per hop delay. i would think that this is also an important parameter. should it also change dynamically? i'm not sure.
• the sender can calculate the time delta of wanted rtt versus real rtt by observing when the ACK arrives. if this delta spikes suddenly it could mean upstream congestion.
• explicit congestion notification messages can be sent to the clients... perhaps a new wire protocol command for this?

[david415]

perhaps after some future research, we could do weird things like use cryptographic receipts exchanges between mixes to determine congestion. the miranda paper uses them to defend against n-1 attacks but i think it could easily apply to congestion control. actually many years ago @daira wrote a similar paper called "A Reputation System to Increase MIX-Net Reliability".

[MIRANDA] Leibowitz, H., Piotrowska, A., Danezis, G., Herzberg, A., 2017, "No right to ramain silent: Isolating Malicious Mixes" https://eprint.iacr.org/2017/1000.pdf.

[MIXRELIABLE] Dingledine, R., Freedman, M., Hopwood, D., Molnar, D., 2001 "A Reputation System to Increase MIX-Net Reliability" In Information Hiding, 4th International Workshop https://www.freehaven.net/anonbib/cache/mix-acc.pdf.

[Yawning]

here's my thoughts on this:

I'm... unconvinced.

• While it is possible to adjust lambda-p (and/or the shift, yes I'm departing from the Loopix paper again to not kill the network), the adjustment frequency is once per epoch, so my intuitive feeling is that such measures will be insufficiently responsive to either mitigate congestion, or allow good network utilization.
• All of the approaches you list will give a view into what happened to the network approx 0.5 RTT before, where the RTT is dominated by the mixing delay.
• The sender doesn't (and shouldn't) poll immediately when it expects a SURB-ACK to arrive.
• ECN would only be useful for the link between the client and provider. I'm not massively opposed to explicit signalling there (I kind of want the provider to send responses to SendPackets for other reasons), but that does comparatively little for congestion further down the mix net.

[daira]

BTW on rereading my old paper, I think we didn't take this attack (documented at the end of section 4.1) seriously enough:

Note that an adversary may be able to force negative ratings on a MIX, while goal 2 [Reject false claims] still holds: if he floods that MIX’s incoming bandwidth (either directly or via witnesses), the MIX will no longer be able to sustain the load. However, this is exactly the point where the MIX demonstrates that it is unreliable. Causing MIXes to lose reputation in the face of successful flooding is consistent with our scoring system goals: the scoring system measures reliability and capabilities, not intent.

The loose global timing synchronization assumption is also really ugly, and I still don't know how to do better.

[david415]

• i think it might be possible to adapt this sharing of the delivery receipts for the Poisson mix strategy [LOOPIX]. this of course is insufficient for reliability but it's nice to know there are alternate defenses for n-1 attacks besides relying on a heartbeat protocol.

other open questions:

• can we use source quench/explicit congestion notification to get congestion information to clients faster than waiting for round trip timeouts?

• if we don't do exponential backoff then what does it take to cause congestion collapse?

• how do we adjust the lambda-p value for exponential backoff in response to congestion notification?

  [LOOPIX] Piotrowska, A., Hayes, J., Elahi, T., Meiser, S., Danezis, G., “The Loopix Anonymity System”, USENIX, August, 2017 https://arxiv.org/pdf/1703.00536.pdf

[Yawning]

can we use source quench/explicit congestion notification to get congestion information to clients faster than waiting for round trip timeouts?

Only between the client and provider. Interior nodes do not have an idea of where to send such notifications to for reasons that should be obvious, and I would be fairly solidly against including a SURB per hop in forward traffic.

if we don't do exponential backoff then what does it take to cause congestion collapse?

ITYM "mitigate congestion collapse". The solutions that come to me as "viable" are (in decreasing order of preference):

• Throw hardware and bandwidth at the problem.
• Rate limit on a per-client basis at the provider level.
• Rate limit on a per-provider basis at the first layer.
• If everything is super overloaded over a long period of time, increase lambdaP.
• If certain providers are responsible for an excessive fraction of network traffic, delist them.

I'm also far from convinced that each client should be constantly sampling lambdaP and always sending cover traffic when idle, because that wastes a gigantic amount of bandwidth when everyone does that. How to balance out "not burning bandwidth like crazy" vs "it's stupid to only send cover traffic when you're sending messages" to me is an open research question.

how do we adjust the lambda-p value for exponential backoff in response to congestion notification?

You don't. It's a network wide parameter. The authority can increase/reduce it based on anonymity requirements, or set it to something super conservative if the network is under sustained overload, but the opportunity to adjust the value is once every 3 hours, firmly cementing it as a coarse and blunt instrument.

[david415]

1. I disagree with the first point: "Interior nodes do not have an idea of where to send such notifications to for reasons that should be obvious"

Interior nodes send congestion information to the next outer layer of nodes until it reaches all Providers and finally all clients.

2. "ITYM 'mitigate congestion collapse'. Wrong again. I meant that I would like to find out how to cause congestion collapse. I want to know what kind of usage statistics cause congestion collapse so that an over provisioned network knows how much longer it has to live at the given growth rate.

3. I am unconvinced that epoch key rotation (PKI updates) must be set at 3 hours and therefore barred from being a useful mechanism for congestion control.

[Yawning]

Interior nodes send congestion information to the next outer layer of nodes until it reaches all Providers and finally all clients.

That feels relatively worthless. Figure out how much bandwidth amplification this sort of scheme will entail. And if one node has a blip with congestion, so what? What possible useful action can you take? It's stupid to alter the transmit scheduling just because a single link has experienced a congestion event because that will massively under-utilize network capacity....

"ITYM 'mitigate congestion collapse'. Wrong again. I meant that I would like to find out how to cause congestion collapse. I want to know what kind of usage statistics cause congestion collapse so that an over provisioned network knows how much longer it has to live at the given growth rate.

I think the load shedding is too aggressive and the transmit/retransmit timer granularity is too coarse grained for this to be a practical consideration. This will be even more of a non-issue once the server code starts throttling outgoing sends on a per-user basis as well.

"Kind of bad things happen if the network is undersized relative to the number of users. For that, lambda and lambdaP adjustment is sufficient to adjust load till new servers can be added".

I am unconvinced that epoch key rotation (PKI updates) must be set at 3 hours and therefore barred from being a useful mechanism for congestion control.

You're missing the point.

Any realistic epoch interval (even say, a few mins, though that would be considerably shorter than what I'm comfortable with), is entirely too coarse grained to react to dynamic network conditions, because there will still be way too much delay. By the time any sort of lambda adjustment propagates to clients (which will take a while), all the loss that's going to happen, has happened, and the particular link is likely back to normal.

[Yawning]

With something like my autoratelimit server branch (https://github.com/katzenpost/server/tree/autoratelimit), people that try to inject traffic too fast into the network will be forced to use multiple accounts.

The rate limiter is PKI parameter based (it primarily enforces the SendShift parameter), so there is room for dynamic tuning, but like all other PKI parameters this is something that will happen once every epoch.