[tor-dev] Proposal: Merging Hidden Service Directories and Introduction Points

[isis]

Aaron Johnson transcribed 2.1K bytes:
> > > That seems easy to fix. Make the number of Introduction Points the same
> > > as it was before and make them be selected in a bandwidth-weight
> > > way. There is no cost to this. You need IPs to be online, and so
> > > whatever number was used in the past will yield the same availability
> > > now. And bandwidth-weighting should actually improve both performance
> > > and security.
> > 
> > Is it obvious how to build a bandwidth-weighted DHT that is stable
> > across changes in the consensus?  One advantage of using the hash ring
> > is that the loss of an HSDir causes only local changes in the
> > topology, so if the client is using a different version of the
> > consensus they can still locate one of the responsible HSDirs.  (Note:
> > I do not claim this cannot be done; it just seems like an important
> > detail to sort out…)
> 
> You could reserve a space after each relay in the hash ring with a length
> equal to the relay's bandwidth, and then assign an onion service with a hash
> that is a fraction f of the maximum possible hash value to the relay owning
> the space in which the fraction f of the total hash-ring length is
> located. Removing or adding a relay adjusts the onion service locations by
> an amount that is at most the fraction that is that relay’s total bandwidth
> fraction. To ensure coverage for clients with older consensuses, the relay
> can maintain HSDir+IPs at the locations indicated by both the current and
> previous consensus.

At one point, I wanted to do something like this for BridgeDB's hashrings, to
be able to increase the probability that Bridges with higher bandwidth would
be distributed (assuming we live in a glorious future where Bridges are
actually measured).  The above design isn't the most time efficient, and it
also turned out to be *super* unfun to implement/debug.  For HS reliability,
it could be a bit disastrous, depending on how much "shifting" happens between
consensuses, and (at least, for BridgeDB's case) my testing showed that even a
small differential meant that nearly the entire hashring would be in an
unusable state.

A better algorithm would be a Consistent Hashring, modified to dynamically
allocate replications in proportion to fraction of total bandwidth weight. As
with a normal Consistent Hashring, replications determine the number times the
relay is uniformly inserted into the hashring.  The algorithm goes like this:

  bw_total     ← Σ BW, ∀ CONSENSUS ∃ DESC {BW: DESC → BW}
  router       ← ⊥
  replications ← ⊥
  key          ← ⊥
  while router ∈ CONSENSUS:
   | replications ← FLOOR(CONSENSUS_WEIGHT_FRACTION(BW, bw_total) * T)
   | while replications != 0:
   |  | key ← HMAC(CONCATENATE(FPR, replications))[:X]
   |  | INSERT(key, router)
    
where:

  * BW is the routers's `w bandwith=` weight line from the consensus,
  * DESC is a descriptor in the CONSENSUS,
  * CONSENSUS_WEIGHT_FRACTION is a function for computing a router's consensus
    weight in relation to the summation of consensus weights (bw_total),
  * T is some arbitrary number for translating a router's consensus weight
    fraction into the number of replications,
  * HMAC is a keyed hashing function,
  * FPR is an hexadecimal string containing the hash of the router's public
    identity key,
  * X is some arbitrary number of bytes to truncate an HMAC to, and
  * INSERT is an algorithm for inserting items into the hashring.

For routers A and B, where B has a little bit more bandwidth than A, this gets
you a hashring which looks like this:

                          B-´¯¯`-BA
                       A,`        `.
                       /            \
                      B|            |B
                       \            /
                        `.        ,´A
                         AB--__--´B

When B disappears, A remains in the same positions:
                               
                          _-´¯¯`-_A
                       A,`        `.
                       /            \
                       |            |
                       \            /
                        `.        ,´A
                         A`--__--´
                               
And similarly if B disappears:

                          B-´¯¯`-B
                        ,`        `.
                       /            \
                      B|            |B
                       \            /
                        `.        ,´
                          B--__--´B

So no more "shifting" problem.  It also makes recalculation of the hashring
when a new consensus arrives much more time efficient.

If you want to play with it, I've implemented it in Python for BridgeDB:

https://gitweb.torproject.org/user/isis/bridgedb.git/tree/bridgedb/hashring.py?id=949d33e8#n481

One tiny caveat being that the ConsistentHashring class doesn't dynamically
assign replication count by bandwidth weight (still waiting for that glorious
future…); it gets initialised with the number of replications.  However,
nothing in the current implementation prevents you from doing:

>>> h = ConsistentHashring('SuperSecureKey', replications=6)
>>> h.insert(A)
>>> h.replications = 23
>>> h.insert(B)
>>> h.replications = 42
>>> h.insert(C)

Best Regards,
-- 
 ♥Ⓐ isis agora lovecruft
_________________________________________________________
OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35
Current Keys: https://blog.patternsinthevoid.net/isis.txt
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 1240 bytes
Desc: Digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20150724/806d7f4a/attachment.sig>