Comment by est31 | Hacker News Reader

Comment by est31 | Hacker News Reader

https://covid19-static.cdn-apple.com/applications/covid19/cu...

> Upon a positive test of a user for COVID-19, their Diagnosis Keys and associated DayNumbers are uploaded to the Diagnosis Server. A Diagnosis Server is a server that aggregates the Diagnosis Keys from the users who tested positive and distributes them to all the user clients who are using contact tracing.

Is this scalable? Earlier in the document they mentioned that the tracing keys are 16 bytes long. Let's assume that there are 3 million patients in a country. That'd be 48 megabytes each user has to download and process per day to check whether they've been in contact with an infected person (processing involves calculation of 144 HMACs per tracing key). I don't think this is feasible at scale and one can't avoid thinking about area recognizing diagnosis servers.

E.g. Smartphones of patients would upload not just the diagnosis keys, but also the areas (county, district, something like that) they've been inside during that day. Then smartphones querying the diagnosis servers would have to send the areas they are interested in. But it's easy to see that this approach is then quite privacy invading. On the bright side, this info is already available to carriers so it's already a sunken cost so to speak.

3 million is way too high. Old infections aren't interesting for this; users only need to download newly reported infections since yesterday. Limiting to broad geographic regions would also help reduce scope and not be especially privacy invasive.

> Old infections aren't interesting for this

Yes, healed patients who don't produce viruses any more aren't important, but anyone still infectious is still a danger. Even if you are supposed, often even legally required, to stay at home while being infected, there is no guarantee you aren't. I'd bet that most of these people also take their phones with them, after all far more serious criminals like actual murderers are often taking their phones to sites of crimes as well. The IDs of those devices are still relevant. Quarantine after diagnosis may last up to 14 days, so your phone should be uploading IDs for 14 days to the diagnosis server.

Given continuation of exponential spread, we aren't far from having 3 million new patients within a span of two weeks in populous countries like the US.

It’s new patients only, but for each day they might have been infectious. So, if it’s 100k new cases a day, and each uploads 5 days of keys, then it’s 8 MB.

Seems doable, especially considering that you’d want to have fully blown lockdown during the exponential growth, and only then switch over to this contact tracing phase once the initial wave has abated.

Seems like a scenario where bloom filter[1] could be useful.

1. https://en.wikipedia.org/wiki/Bloom_filter

Bloom filters aren't good for privacy because if there is a hit, you have to upload the id to check it. Which tells the service a) which ID you encountered and b) if it's an ID that was confirmed to be affected, whether you are affected by corona or not, something the system was designed to prevent.

> if there is a hit, you have to upload the id to check it.

Why would you upload it if you know (almost for sure) there was a hit? We can all live with small false positives I think.

You don't have to upload the full id.

It's enough to upload the bucket that was hit in the Bloom filter to fetch the subset of detailed data that corresponds to the bucket.

If the buckets are coarse enough that doesn't reveal much. And if the Bloom filter is too fine-grained for that, fetch a set of buckets instead of one.

There wouldn't be 3 million new patients per day. Wouldn't each phone just need to download the newly-discovered cases since the last time they checked?

Each patient creates a new key per day. Only those keys are uploaded. So everyone who is positive in the app needs their keys to be uploaded. At least this would be a reasonable design choice of the app. Maybe the designers of the app assume you actually follow the quarantine that infected people should do and don't leave your home. In that case, the app can stop uploading of those daily keys.

Say a newly identified case is assumed to have been infectious for the preceding week. My reading of the spec is that they’d upload 7 diagnosis keys (which all devices would have to download).

https://en.wikipedia.org/wiki/Bloom_filter

Is your calculation correct? You only need to download the Diagnosis Keys. How would that be 48MB?

I used the definition 1 MB == 1 000 000 bytes (there are several definitions for what a megabyte is). Each diagnosis key has 16 bytes. 16 bytes * 3 million patients = 48 million bytes = 48 MB. Note that not just the diagnosis are uploaded but also day numbers. Those follow strict power laws and compress pretty well with even the simplest entropy coding schemes to a sub byte size.

48MB per day just isn't that much these days.

For reference WhatsApp is ~70MB (that's considered small) and a Facebook app is ~380MB on iOS.

Both are one time downloads with comparatively rare updates. Users can visit a place with WiFi for doing the download. The daily dataset of infected users however can't wait for manual prompting and is thus likely downloaded in the background. Users might not always be able to connect their devices to WiFi. In many countries, traffic quotas are quite limited.

Reply on news.ycombinator.com