Drop ID too long to provoke collisions

[roeslpa]

Currently Drop IDs of 256 Bit are used. That results in 2^256 Drop IDs, which is much too much even if the whole world uses one drop server. Even the smallest range of Drop IDs (64 Bit) is too long. I recommend to use fewer than 20 Bit for the largest range, depending on how many users we expect per server. So let us:

1. Define how many users can use one (drop+block+accounting) server
   • Can an admin ( @knopwob / @thechauffeur ) estimate the maximum users depending on the number/size of drop/block requests?!
   • Example: max. 2^20 users per server
2. |DropID| = log_2(number of users per server)
   • Four ranges of anonymity level (like it is currently implemented in the Android client)
   • Assumption: 1/4 of the users select one range
   • Example:
     1. First range 9 Bit => 2^9 Drop IDs, 2^18 user => 512 (+64 (+8 (+1))) users per ID*
     2. Second range 12 Bit => 2^12 Drop IDs, 2^18 user => 64 (+8 (+1)) users per ID
     3. Third range 15 Bit => 2^15 Drop IDs, 2^18 user => 8 (+1) users per ID
     4. Fourth range 18 Bit => 2^18 Drop IDs, 2^18 user => 1 user per ID
     5. Out of range 20 Bit => e.g. incrementing 2^19 Drop IDs with leading 1 to avoid collisions for users who do not want to be anonymous

*This sounds like much traffic, but the respective user chose to gain the maximal anonymity and since i. I guess that less than 1/4 of the users will select this range and ii. this number is only reached when 2^20 users use this server. So I think we could even use fewer Bits for this range.

[thechauffeur]

Good points.

I would propose to not let the maximum number of users per drop server -- from a SysOps point of view -- influence the decision about drop id length and generation. Technically this could simple be solved anyway (e.g. by providing one front end / entry point to more servers in the background).

So what we need are assumptions about how many users will select which degree of anonymity. Something like to the power of ten should suffice.
E.g. assumption: 100 to 1000 users choose the highest degree of anonymity. How many bits from the maximal bits should be used to achieve a good collision probability for those users?
Assumption: 1000 to 10000 users choose the second highest degree of anonymity. How many...?
Assumption: 1000 to 10000 users choose the third highest degree of anonymity. How many...?

Collisions probability must be higher for the first degree than for the second degree than for the third degree.

For the least degree of anonymity I would propose to just use the full range of 256 bits to statistically never form a collision. This should be communicated clearly in the clients.

The default degree should either be none (i.e. the user must select one) or the second or third degree.

The default degree will have an impact on how many users will select this degree. If there is no degree I would assume that the second and third degree will be selected more often than the others.

[roeslpa]

1. Levels of Anonymity (Proposal)
1st level: 30-100 ~ 84=(64+20) identities per Drop ID
=> ~84 times of 1-user/ID traffic
2nd level: 10-30 ~ 20=(16+4) identities per Drop ID
=> ~20 times of 1-user/ID traffic
3rd level: 2-10 ~ 4 identities per Drop ID
=> ~4 times of 1-user/ID traffic
4th level: <1 identity per Drop ID
=> 1-user/ID traffic

Since the number of users for one level affects all lower levels, these numbers are added.

2. Assumptions for numbers of users (just for illustration)
I do not know how many users will use Qabel and I do not know how many users will use Qabel/provider.
Assumptions:
1st level 100 - 1.000 identities ~ 2^7 - 2^10
2nd level 1.000 - 10.000 identities ~ 2^10 - 2^13
3rd level 1.000 - 10.000 identities ~ 2^10 - 2^13
4th level <2^256

3. Resulting Drop ID ranges (also for illustration of the formula)
4th level: 256 Bit => identities in this range/2^256 < 1 identity/ID : identities in this range<2^256

3rd level : 2^2 = 2^10/2^bits <=> bits = log_2(assumed identities in this range) - log_2(wanted identities/ID rate)
=> 10 - 2 to 13 - 2 <=> 8 to 11 Bit => corner cases: 1.000 identities and 11 Bit => ~ 1/2 identity/ID; 10.000 identities and 8 Bit => ~ 40 identities/ID
2nd level: 10 - 4 to 13 - 4 <=> 6 to 9 Bit => corner cases: 1.000 identities and 9 Bit => ~ 2 identities/ID; 10.000 identities and 6 Bit => ~ 160(+40) identities/ID
1st level: 7 - 6 to 10 - 6 <=> 1 to 4 Bit => corner cases: 100 identities and 4 Bit => ~ 6(+2) identity/ID; 1.000 identities and 1 Bit => ~ 512(+200) identities/ID

I think a good distribution for the assumed numbers of users could be: 3, 8, 10, 256 Bit

There could be two ways of implementing it: a provider sets the assumption during the setup of a drop server and the clients calculate the ranges upon this assumption or we set the ranges globally for all clients independent of the numbers of users. @thechauffeur what would you prefer and shall we fix this issue now or keep it in mind?

[thechauffeur]

We should definitely enhance the way it is implemented atm, just not with some special high priority. This should get into our backlog.