commit 3b604e12a8d798b03d3214d76985263fd6ffeb1b Author: teor (Tim Wilson-Brown) <teor2345@gmail.com> Date: Fri Nov 20 11:47:40 2015 +1100 prop224: deal with replica hashring collisions If multiple replicas want to use the same HSDir, give it to the lower-numbered replica, and have the higher-numbered replica(s) ignore it when counting nodes. This avoids services choosing the same HSDir for multiple replicas / spreads, and therefore losing redundancy. --- proposals/224-rend-spec-ng.txt | 19 ++++++++++++++++--- 1 file changed, 16 insertions(+), 3 deletions(-) diff --git a/proposals/224-rend-spec-ng.txt b/proposals/224-rend-spec-ng.txt index 2aeb05b..00586fd 100644 --- a/proposals/224-rend-spec-ng.txt +++ b/proposals/224-rend-spec-ng.txt @@ -696,7 +696,7 @@ Status: Draft with default value 3. hsdir_spread_accept = an integer in range [1,128] - with default value 8. + with default value 12. To determine where a given hidden service descriptor will be stored in a given period, after the blinded public key for that period is @@ -727,15 +727,28 @@ Status: Draft Finally, for replicanum in 1...hsdir_n_replicas, the hidden service host uploads descriptors to the first hsdir_spread_store nodes whose - indices immediately follow hs_index(replicanum). + indices immediately follow hs_index(replicanum). If any of those + nodes have already been selected for a lower-numbered replica of the + service, any nodes already chosen are disregarded when choosing a + replica's hsdir_spread_store nodes. + + [ XX/teor - because the positions don't match the key, this might leak + the fact that nodes from other replicas are nearby to a HSDir. + But this is preferable to having fewer HSDirs for a service. + I think the probability of a collision is approximately: + 1 / (n_hsidrs / (hsdir_n_replicas * hsdir_spread_store)) = 6 / n_hsidrs ] When choosing an HSDir to download from, clients choose randomly from among the first hsdir_spread_fetch nodes after the indices. (Note that, in order to make the system better tolerate disappearing HSDirs, hsdir_spread_fetch may be less than hsdir_spread_store.) + Again, nodes from lower-numbered replicas are disregarded when + choosing the spread for a replica. An HSDir should reject a descriptor if that HSDir is not one of the - first hsdir_spread_accept HSDirs for that node. + first hsdir_spread_accept HSDirs for that node. Since HSDirs can't + derive other replicas of a service, hsdir_spread_accept must be at + least hsdir_n_replicas * hsdir_spread_store. [TODO: Incorporate the findings from proposal 143 here. But watch out: proposal 143 did not analyze how much the set of nodes changes