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