Proposal: minimum advertised bandwidth guarantees fast/guard

[Roger Dingledine <arma@xxxxxxx>]

Hi folks,

This is a quick proposal, based on my post in Mike Perry's recent thread
at http://archives.seul.org/or/dev/Jul-2007/msg00022.html
Please feel free to flesh it out; also somebody should please write us
a patch to the specs.

The issue is the same attack as in proposal 107: an attacker who signs
up a thousand servers each claiming 10MB/s bandwidth will cause the
median bandwidth to be 10MB/s, and all current guards will lose their
guard status -- causing their users to abandon them and pick one of the
new adversary-controlled nodes. The bug is that while we cap bandwidth
at 1.5MB/s when considering load balancing, we failed to do it when
considering median bandwidth for guard qualification.

I've attached a patch; but there are still some design questions to
ponder and maybe improve:

A) I picked 500KB/s as the cutoff. Is there a better way to pick this?

B) I chose to assign guard status to all stable nodes that meet this
cutoff -- even exit nodes. We could instead just make the exception for
non-exit nodes, which would be better for load balancing when exits are
rare. But having sufficient guards is useful too.

C) Since we defined is_possible_guard to require is_fast, there was
another turtle underneath this turtle. I fixed this by declaring that
anybody with at least 100KB/s of bandwidth is automatically Fast. We
could also fix it by getting rid of the is_fast requirement; but I think
if we do that I'll be doing a new proposal later about how somebody can
sign up 8000 new servers and suddenly no other servers count as Fast. ;)

D) Why 100KB/s? Is there a better number?



Index: dirserv.c
===================================================================
--- dirserv.c	(revision 10861)
+++ dirserv.c	(working copy)
@@ -1436,6 +1436,8 @@
  * network using allegedly high-uptime nodes, displacing all the
  * current guards. */
 #define UPTIME_TO_GUARANTEE_STABLE (3600*24*30)
+#define BANDWIDTH_TO_GUARANTEE_FAST 100000
+#define BANDWIDTH_TO_GUARANTEE_GUARD 500000
 
 /* Thresholds for server performance: set by
  * dirserv_compute_performance_thresholds, and used by
@@ -1474,9 +1476,11 @@
         (unsigned)uptime < UPTIME_TO_GUARANTEE_STABLE)
       return 1;
   }
-  if (need_capacity &&
-      router_get_advertised_bandwidth(router) < fast_bandwidth)
-    return 1;
+  if (need_capacity) {
+    uint32_t bw = router_get_advertised_bandwidth(router);
+    if (bw < fast_bandwidth && bw < BANDWIDTH_TO_GUARANTEE_FAST)
+      return 1;
+  }
   return 0;
 }
 
@@ -1709,9 +1713,10 @@
   rs->is_valid = ri->is_valid;
   rs->is_possible_guard = rs->is_fast && rs->is_stable &&
     (!rs->is_exit || exits_can_be_guards) &&
-    router_get_advertised_bandwidth(ri) >=
-    (exits_can_be_guards ? guard_bandwidth_including_exits :
-     guard_bandwidth_excluding_exits);
+    (router_get_advertised_bandwidth(ri) >= BANDWIDTH_TO_GUARANTEE_GUARD ||
+     router_get_advertised_bandwidth(ri) >=
+     (exits_can_be_guards ? guard_bandwidth_including_exits :
+      guard_bandwidth_excluding_exits));
   rs->is_bad_exit = listbadexits && ri->is_bad_exit;
   /* 0.1.1.9-alpha is the first version to support fetch by descriptor
    * hash. */