[tor-bugs] #25964 [Core Tor/Tor]: Remove hs_index_t fetch, and use one of the stores instead

[Tor Bug Tracker & Wiki]

#25964: Remove hs_index_t fetch, and use one of the stores instead
--------------------------------------+----------------------------------
 Reporter:  teor                      |          Owner:  (none)
     Type:  enhancement               |         Status:  new
 Priority:  Medium                    |      Milestone:  Tor: unspecified
Component:  Core Tor/Tor              |        Version:
 Severity:  Normal                    |     Resolution:
 Keywords:  technical-debt, refactor  |  Actual Points:
Parent ID:  #27243                    |         Points:
 Reviewer:                            |        Sponsor:
--------------------------------------+----------------------------------

Comment (by teor):

 There have never been more than 8000 relays in the tor network:
 https://metrics.torproject.org/networksize.html?start=2007-01-01&end=2018-08-28

 And there have never been more than 4500 relays with the HSDir flag:
 https://metrics.torproject.org/relayflags.html?start=2007-01-01&end=2018-08-28&flag=HSDir

 We need need 12 + N bits to index <= 2^12^ = 4096 HSDirs, where N is a
 small slop factor to avoid collisions.

 If we use a 16-bit index, ~1/16 indexes will be occupied. I think this
 means that 1/32 = ~128 HSDirs will share an index with exactly 1 other
 HSDir. Similarly, ~64 HSDirs will share an index with exactly 2 other
 HSDirs, and so on.

 But the spread store is currently 4, so an index shared by 2 HSDirs only
 matters when it's in the 4th spot (128 * 1/4 = 32 HSDirs), an index shared
 by 3 HSDirs only matters in the 3rd or 4th spots (64 * 2/4 = 32 HSDirs), 4
 HSDirs only matters if it's after the 1st spot (32 * 3/4 = 24 HSDirs), and
 5 or more HSDirs always matter (32 HSDirs). So overall, approximately 112
 / 4096 = 2.7% HSDirs will have a meaningful collision.

 I'm not sure how we want to deal with these collisions, given the small
 number of relays involved, we could just store to all the extra equal-
 indexed relays. (If services choose an equal-indexed relay at random, that
 would effectively increase the spread that clients need to check. If
 services use a relay attribute as a tie-breaker, then malicious relays
 would have an incentive to modify that attribute.)

 If we don't want any collisions at all, we should use a 24 bit index.
 (More precisely, 1 meaningful collision every 2 days.)

 It should be impossible for someone to mine relay keys to generate
 collisions, because the shared random value changes every 24 hours, but
 the HSDir flag is only given after 96 hours.

--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/25964#comment:4>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online