Hacker News Reader

Comment by farnsworth | Hacker News Reader

Something I don't understand about this approach - if location data is not tracked/included, only contacts, then don't you have to download all the tokens for every person who tests positive in the world? Then even if it is optimized with location data, and I can only download tokens for people in my area, that will be 1000s of people a day multiplied by all of their tokens over whatever period of time.

Either I'm misunderstanding something or it has just been decided that downloading many MBs a day is not a dealbreaker.

View on HN

You're forgetting time of infection.

You only need to download tokens for people who tested positive in the recent past (14 days - assuming you're not infected, any contact before that couldn't have infected you.)

While that's likely still a lot of data in areas with large daily case counts, at least it won't keep growing indefinitely.

BTW it's one token per day per person, to improve privacy. When someone tests positive, their tokens for the last 14 days are published.

To put some numbers to this: If you're living in a city with 10,000 new cases a day, with each case publishing 14 keys and each key being 16 bytes, it's a 2.2MB download a day (assuming incremental downloads).

When you first install the app you might have to download all keys from the last 14 days, which would be about 15 MB.

Probably don't need 16 byte keys, either. If you live in an area under 4 billion people you are unlikely to have any key collisions (for any given day) with a mere 8 bytes. If you can tolerate some probability of false positives, or have fewer than 4 billion people in your meta-region, shorter than 8 bytes is feasible.

16 -> 8 halves those data figures; diminishing returns from there, but it is possible to reduce the data use further (slightly).

My understanding is that this is even feasible without location information if you use an approximate filter (e.g., a Cuckoo Filter [1]), which they propose in DP-3T (II).

With 20 bits/key such filters yield a false positive rate (FPR) of 0.001%. Meaning for 100,000 new cases per day worldwide, you would only need to download 0.24 MiB.

Note that the FPR applies to each lookup. That is, if you have collected say 100 tokens on a given day, the overall probability of a false positive will be 0.01% (assuming independence). With each extra bit per key you can roughly halve that probability. So in practice size won't be an issue.

[1] https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf

2.2 * 30 + 15 = 81MB

For people with 200MB & 500MB data caps (which is a surprisingly large number of people), this is a significant amount of their data allowance.

These are likely to be people that are still required to go out into the world and work, so are still using their data instead of wifi, and thus higher risk.

It's easy to forget when you're on 10GB+ data plans for years just how many people are not.

That's assuming you're never connected to wifi within those 30 days. The apps could either let you choose to only download the list while on wifi, or it'll probably download the list in the middle of the night when it's reasonable to assume most people are at home near wifi.

I understand that people with a data cap of a few GB and no Wi-Fi could end up being unable to download the tokens before the end of the month. For example a friend of mine stopped showing up in video calls with a group of friends because she's saving her GBs for the video calls she has to do for work. She should be spending a few Euros more per month but it's easy to wish with the money of other people.

DP3T is exploring various options for this, smallest daily proposal currently being 5MB, bigger picture download around 100MB. Worst case mobile providers could always be compelled to exempt this from data usage. That aspect seems pretty solved.

I think your phone collects tokens from other phones that you come near. So your phone only needs to take the few hundred / thousand tokens it has and ping the server with them to see if any of them have advertised that they are a positive result.

Ah, my understanding is that it doesn’t do this; that is, you don’t upload tokens you’ve seen, otherwise there would be a privacy issue.

Reply on news.ycombinator.com