[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
Re: [tor-bugs] #25964 [Core Tor/Tor]: Remove hs_index_t fetch, and use one of the stores instead
#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
_______________________________________________
tor-bugs mailing list
tor-bugs@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs