Hello,

Thank you for your helpful review, teor.

I updated the proposal from most of your comments (see attached .txt) and I respond inline to add some precisions relative to a few of your questions.

Btw, I've mirrored my private repo to github https://github.com/frochet/Waterfilling, such that you have the proper commit history.

On 2018-01-11 14:47, teor wrote:
Hi Florentin,

I have copied your proposal below, so I can respond to it inline.

On 11 Jan 2018, at 21:00, Florentin Rochet <florentin.rochet@uclouvain.be> wrote:

<skip>
1  Overview

  The current Tor path selection algorithm is designed to satisfy two
  important properties:

  1) Each relay should handle a fraction of connections that is
  proportional to its bandwidth.

  2) The nodes in each circuit position (entry-middle-exit) should
  be able to handle the same volume of connections.

What about onion service circuits?

They consist of entry - middle - middle, and for the purposes of this
analysis, make up about 4% of the network.
(2% of traffic at rend points, going through 2 x 3-hop circuits.)

https://metrics.torproject.org/hidserv-rend-relayed-cells.html


That's a good point. Waterfilling uses the current bandwidth-weights logic as a basis and they doesn't account for onion service circuit, hence it also ignore this sort of traffic. Prop 265 tries to address that problem when producing the bandwidth-weights; Since our method achieves the same total consensus weight balance between position as the one produced by bandwidth-weights, Waterfilling would directly inherit Prop 265's properties if this proposal is merged.


  Hence, in addition to select paths in a probabilistic manner, the
  path selection algorithm is responsible for balancing the network,
  that is, making sure that enough bandwidth is made available in all
  the positions.  The current balance of the network is decided by the
  bandwidth-weights (see dir-spec.txt section 3.8.3.  or/and the
  Waterfilling PETS2017 paper
  https://petsymposium.org/2017/papers/issue2/paper05-2017-2-source.pdf).
  This balance does not achieve maximum diversity in end-positions of
  user paths: the same network throughput could be achieved by
  decreasing the use of high-bandwidth relays and increasing the use
  of lower-bandwidth relays in the guard position, instead of using
  these relays in a way that is just proportional to their bandwidth.

When you say "bandwidth", it's not clear whether you mean consensus
weight (measured bandwidth) or advertised bandwidth (bandwidth
capacity). They're not the same.

I'm going to assume consensus weight from now on.
Please fix all uses of bandwidth in the rest of the proposal.

Yes, we mean consensus weight :) I did s/bandwidth/consensus weight within the proposal


<skip>
2  Design

  Correlation attacks require to control guard and exit nodes, but the
  scarcity of exit bandwidth is such that there is no real freedom in
  the way to use it.

As a result, the Waterfilling proposal focuses
  on the guard position. However, it could be easily extended to the
  exit position if, someday, nodes in that position happen not to be
  exploited to their full capacity.

No, exit bandwidth is only exploited to its full capacity on
high-bandwidth exits in the northern EU and North America.


Well, I changed my wording here to avoid ambiguity. I was talking about relays flagged as Exits being used only in the exit position (Wee and Wed have the max value), which means that we cannot apply our method over those relays with the current state of the Tor network.

Select "Consensus Weight vs Bandwidth" on this map:
https://atlas.torproject.org/#map/flag:Exit
All the exits in all the purple countries are probably under-loaded.
And some exits elsewhere are under-loaded.
(That's why we let Exits be fallback directories.)

So the network might actually benefit the most from a reallocation
of Exit bandwidth. But you'd have to use the advertised bandwidth
rather than Wee and Wed.

What would it look like if we used waterfilling on the advertised
bandwidths of Exits?

The problem your mention is more a measurement problem that would not exist if the bwauths were perfect, within a perfect network. I believe that research such as Peerflow[0] is the right path to track down such issue, and this is compatible to our proposal.

[0] www.robgjansen.com/publications/peerflow-popets2017.pdf
Is there a way to do this that avoids gaming the system by
increasing advertised bandwidth?
Does the feedback loop with bandwidth authority measurements
mitigate this risk?

  _Recall_: Tor currently computes bandwidth-weights in order to balance
  the bandwidth made available by nodes between the different path
  positions. In particular the Wgg weight indicates to each guard which
  proportion of its bandwidth should be used for entry traffic (the rest
  being normally devoted to the middle position).  This proportion is
  the same for all guards.

Wgg indicates to *clients* how often they should select guards
in the guard position in *circuits*.

It doesn't influence relays themselves, and it only indirectly
affects bandwidth.

Please fix similar wording in the rest of the proposal.

Yep, this is basically what we tried to say. In fact, what I wrote was the description of the *consequence* of bandwidth-weights. I tried to re-word with your suggestion, thank you.

<skip>
Compute a "pivot" N and the weight Wgg_i assigned to
  relay_i in such a way that:
     
     (a) Wgg_i * BW_i == Wgg_i+1 * BW_i+1 forall i in [1, N]

subscripts in brackets, otherwise it's ambiguous:

Wgg_(i+1) * BW_(i+1)

     (b) Wgg_i == 1 forall i in [N+1, K] 
     (c) sum_{i=1}^{K} Wgg_i*BW_i = Wgg*G  (Wgg is provided by Tor)

These equations are under-specified, because they allow solutions with:
Wgg*G > 0
Wgg_1 == 0
That is, no guard selections for high-bandwidth relays.

From the descriptions, I think the missing condition is:
Wgg_N * BW_N >= Wgg_(N+1) * BW_(N+1)

Yes, this can be added. But I think that this condition is redundant, since BW_i are sorted in decreasing order.


Also, Wgg is provided by the Tor directory authorities based on
consensus weights from the bandwidth authorities.

And what happens to any remainder in the calculations?

This is a very good question. Currently in my implementation, I ignore the remainder. This is negligible for large network but can be weird for small one (of a few relays).

A possible solution would be to use floating precision for consensus weights. 

(This is most important for small, low bandwidth test networks.)

For example, if:
G = 10
Wgg = 0.6
BW_i = 6, 2, 2
What are the final weighted bandwidths?
2, 2, 2?

From my note, my current implementation would crash if the water level reaches the smallest relay. Since it was prototype code, I didn't mind to think about it, and I let it that way.

I think that below a fixed size of the network, it does not make sense to use this proposal. In this example, the remainder accounts for a large part of the network capacity and would just be wasted.

<skip>
  As a result of this process, each guard ranked before the pivot N
  dedicates the same bandwidth to its guard role (equation (a)) -- we
  say that these guards achieve the water level, while each guard
  ranked after the pivot N dedicates its full bandwidth to the guard
  role (equation (b)) -- they are below the water level.  Equation (c)
  makes sure that the pivot and the water level are positioned in a
  way that guarantees that the total amount of bandwidth dedicated to
  the guard position is the same as before. In practice, the value of
  N can be efficiently computed by dichotomic search on Equation (c),

Is this the same as a binary search?
Does it require any division?
Because division is slow on some Tor client architectures.

Yes, binary search. It does require division. However, waterfilling is designed to be executed in the authority side and called only when the consensus document is produced. Moreover, my tests indicates that the computation consumes a few ms.

<skip>
2.1 Going further by tweaking original bandwidth-weights computation

  As explained above, our Waterfilling equations are based on: 1) the
  Wgg weight computed by Tor 2) the assumption that the bandwidth
  available in exit is scarce, i.e., it is lower than the one
  available for guard (and middle) positions.
  
  The second point is satisfied most of the time in Tor, and we do take
  it for granted here.
  
  We, however, observe that Waterfilling could be made even more
  effective by applying a minor change in the way Tor computes the
  Wgg.  For the moment, Tor computes Wgg in such a way that the same
  bandwidth is allocated to the guard and middle positions. As a
  result, both positions are in excess compared to the exit position.

  The water level could be decreased and, as a result, the uniformity
  of the guard selection process could be improved, by computing Wgg
  in a way that allocates the same bandwidth to the guard and exit
  positions, putting the middle position as the only position in
  excess.

No, this would slow down Guards, and everything that isn't an exit circuit:
* directory fetches (3% of total bandwidth to guard position)
* onion services (rend is 4% of total bandwidth to guard and middle)
* HSDir is unweighted, and we don't know how much bandwidth it uses
* FallbackDir is unweighted, but mostly Guards, and small


That's difficult to predict, I cannot be sure if it is better or worse for that type of traffic since internal circuits use at least 2 middle relays + the guard and sometimes, even not the guard. Hence we might also think that pushing a bit more to the middle position could be a good thing to do. Moreover, middle relays are unstable and often at the edge of the internet, while guard are stable and most of them within the core of the internet. Hence, a little more of them within the middle position *could* be a good thing, especially if it makes entry's selection probability more uniform. Anyway, I don't have any proof to assert this, as well that I don't have any proof to assert that this optimization could be bad. What I got, is that, for exit circuits, it does not slow down anything.

This optimization is not mandatory, and could also be enabled/disabled at will by the directory auths.

  We show in the performance section of the Waterfilling paper that
  scarcity on two positions does not reduce performance compared to
  vanilla bandwidth-weights.

What about guards that have low consensus weight due to latency,
rather than available bandwidth?

I think this could also cause you huge latency issues as you push more
bandwidth away from fast relays. I'm not sure if shadow captures this
accurately.


If it happens that any bandwidth is pushed away from fast relays within the entry position and make the entry position slower, at average, then it will make the middle position faster (because it got that bandwidth pushed away). Since the latency of your traffic flow just care about the global latency of the circuit, this will not appear to be slower or faster, on average. This is exactly what we observe in Shadow, and yes, it captures latency accurately. At least, better than any other simulator.

3  Security implications

  An analysis of the security impact of the Waterfilling proposal is
  made in Section 6 of the Waterfilling paper. It studies the
  expectation of the number of relays that an adversary needs to
  control in order to mount a successful correlation attack at a given
  time, as well as an analysis of the evolution of the time until
  first path compromise, based on TorPS.

  Given that the distribution produced by Waterfilling is closer to
  the uniform distribution, the use of Waterfilling increases the
  expectation of the number of relays that an adversary needs to
  compromise in order mount a successful correlation
  attack. Concretely, and based on real data from 2015, this
  expectation increases by approximately 150 relays.

What percentage is this?

 ~ 25 %


<skip>

I'm sorry, I can't read this, there are build files everywhere.
I can't even find which files were changed.
Can you provide clean commits in a fork, based on the Tor master branch?

Also, I think you will need a new consensus method for this change.
We don't use consensus parameters or torrc options to modify the
content of the consensus, we use consensus methods.


Sorry about this. I've updated the repo with a proper commit history based on my fork. The code gives an idea about the easiness to plug-in this method to the current path selection.

<skip>
These are redundant, and could significantly expand the size of the
consensus, and consensus diffs. (Consensus weights are one of the
largest contributors to consensus diff size.)

True, each time the consensus weights are modified, those waterfilling weights need to be recomputed. It adds one line per guard, which is about 2~3% of the size of the full consensus. Is such a thing a problem?


Why not calculate wmg on clients?
Why not calculate both wgg and wmg on clients?


This is again a very good question: for such a critical feature (path selection), it is important that the directory auths have full power over the weight computation. If it happens that some change are needed, then the Tor network is updated in a straightforward way. This is not the case if those weights are computed in client code. In fact, I believe that one of the strength of this proposal is the oriented design towards the dirauths.

<skip>

Unanswered questions:

What about the feedback loop between this new allocation system
and the bandwidth authorities?


I am sorry, I don't really understand why a feedback loop is needed. Measuring bandwidth and producing bandwidth-weights seems orthogonal to me.

Should bandwidth authority clients use the new system?

How do we report on the new system?
How can we determine whether it is better for security in practice?
How can we determine if it is faster or slower in practice?
How can we work out if someone is trying to game the system?

T


I've added a section within the proposal for all upcoming questions.

Best,
Florentin




_______________________________________________
tor-dev mailing list
tor-dev@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev