[tor-dev] [RFC] Proposal draft: The move to a single guard node

[George Kadianakis]

Nicholas Hopper <hopper at cs.umn.edu> writes:

> I think I'll have more to say later, but...
>
> On Wed, Mar 26, 2014 at 11:36 AM, George Kadianakis
> <desnacked at riseup.net> wrote:
>> 1.3. Age of guard as a factor on guard probabilities
>>
>>    By increasing the guard rotation period we also increase the lack
>>    of clients for young guards since clients will rotate guards even
>>    more infrequently now (see 'Phase three' of [1]).
>>
>>    We can try to mitigate this phenomenon by giving higher priority to
>>    young guards to be picked as guards:
>>
>>    To do so, everytime an authority needs to vote for a guard, it
>>    reads a set of consensus documents spanning the past NNN months, and
>>    calculates the age of the guard; that is, in how many consensuses
>>    its public key has been included in the past.
>>
>>    The authorities include the age of each guard by appending
>>    '[SP "Age=" INT]' in the guard's "w" line.
>>
>>    When a client picks a guard, it applies the age of each guard as a
>>    weight on its guard probability. XXX unspecified how
>
> I'm pretty sure this section has it backwards from what was the intent
> of the discussion of "guard age" at the dev meeting.  The weight
> factor should be applied when choosing a "new guard" as a middle or
> exit node, because it is being underutilized as a guard.  This makes
> it straightforward to apply: if relay R has had the guard flag for
> fraction k of the last rotation period, then its weight for some other
> position should be
>
> k*(weight with the guard flag) + (1-k)*(weight without the guard flag)

Ah, thanks for this!

I admit I didn't entirely grasp this suggestion during our discussion
in the dev meeting. I still don't really understand it, I think.

So, based on your response, IIUC, the idea is that because young
guards are underutilized, we want to increase the probability of them
being chosen in non-guard positions, so that they become more utilized
till more people pick them as guards?

Some questions on the terminology you used:

a) What do you mean by 'last rotation period'? When you say "for
  fraction k of the last rotation period", you mean that if the
  authorities read consensuses for the past 12 months, and the relay R
  was up as a guard for 6 months, then k would be 6/12 == 0.5?

b) By (weight with the guard flag) you mean the result of:
      <consensus BW> * <consensus weight>  ?

   So for example, for a guard relay with bandwidth == 10000
   contesting to become a guard node for a circuit, you mean the
   result of:
      10000 * Wgg  ?

   And by (weight without the guard flag) you mean that in the above
   example, we would do:
      10000 * Wgm
   (assuming that the relay doesn't have the Exit flag)

Is that right, or did I misunderstand you?

Assuming the above terminology assumptions, I began trying to
understand your formula. First of all, I was wondering how you ended
up with it? Is this some standard form? I'm not very familiar with
these things.

Here are some thoughts I generated while meditating on that formula:

a) The goal is that this formula should give us bigger values as k
   gets smaller (since the smaller the k, the younger the guard).

   So, we want to get the maximum value for k=0, and the minimum value for k=1.
   In our case, for k=0, we get:
      new_weight = [weight without the guard flag]
   And for k=1 we get:
      new_weight = [weight with the guard flag]

   This seems reasonable assuming that:
     [weight without the guard flag] > [weight with the guard flag]

   As k goes from 0 to 1, the formula is a linear function that moves
   from the maximum to the minimum [0].

   It's worth noting that the maximum weight a young guard can achieve
   for any position is its weight without the guard flag. Maybe we
   need to evaluate whether this weight increase is substantial?

b) I also checked whether
     [weight without the guard flag] > [weight with the guard flag]
   by checking the consensus weights of a recent consensus [1].

   The assumption is generally true, if you assume a relay that only
   has the Guard flag. For example, 'Wmm > Wmg' and 'Wem > Weg'.

   However, if the relay has both Guard and Exit flags, then there are
   some bad cases. For example, 'Wme < Wmd' and 'Wbd < Wbe'.

   That is, the consensus weight of a Guard+Exit node for the middle
   position (Wmd = 871) is bigger than the consensus weight for an
   Exit node (Wme = 0).

   So, in this case:
       [weight without the guard flag] < [weight with the guard flag]
   
   To be honest, that doesn't really make sense to me from a load
   balancing perspective (since Guard+Exits are probably more
   overloaded than Exits), but I don't really understand consensus
   weights anyway.

   It's worth noting that the weights in the above example are small
   enough that they probably wouldn't really make a big difference
   IRL. Still, it doesn't fit with the assumption of the formula.


[0]: Since:
       new_weight = k*[weight with the guard flag] + (1-k)*[weight without the guard flag]
     can be rearranged to:
       new_weight = [weight without the guard flag] + k([weight with the guard flag] - [weight without the guard flag])

     Which is basically a linear function 'y = a*x + b' with its slope
     being: [weight with the guard flag] - [weight without the guard flag].

     (Sorry for the mental masturbation...)

[1]: Here are some consensus weights from the consensus with 
     "valid-after 2014-03-13 00:00:00":

    	Wme=0 (Weight for Exit-flagged nodes in the middle Position)
    	Wmd=871 (Weight for Guard+Exit flagged nodes in the middle Position)
    	Wmg=4198 (! Weight for Guard-flagged nodes in the middle Position)
    	Wmm=10000 (Weight for non-flagged nodes in the middle Position
    	
    	Weg=8258 (! Weight for Guard flagged nodes in the exit Position)
    	Wed=8258 (Weight for Guard+Exit-flagged nodes in the exit Position)
    	Wee=10000 (Weight for Exit-flagged nodes in the exit Position)
    	Wem=10000 (Weight for non-flagged nodes in the exit Position)
    	
    	Wbe=0 (Weight for Exit-flagged nodes for BEGIN_DIR requests)
    	Wbd=871 (Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests)
    	Wbg=4198 (! Weight for Guard flagged nodes for BEGIN_DIR requests)
    	Wbm=10000 (Weight for non-flagged nodes for BEGIN_DIR requests)