MVP Matching Algorithm (individual reporting)

[ainsleys]

Drawing on this issue: #17

The MVP matching algorithm is Rust code that runs inside the enclave, takes inputs of userID, infectionStatus, latitude, longitude, time, and duration.

The code compares latitude and longitude between submitted user data and all user data which has been submitted and has a positive test result to find matches within 4m and 24hours (subject to change).

For each match in time and proximity with an individual who has tested positive, the algorithm returns latitude, longitude, date, and duration (duration from both submitting user and positive match users user "matched" with).

Other elements mentioned in #17 are out of scope for the MVP

[ainsleys]

@lacabra when you have a moment can you make sure these requirements are in line with what you've been anticipating / add any additional detail that could be useful? This is for an MVP and does not have all features included that we've discussed previously.

[FishmanL]

Why return the lat,long of a match rather than just the existence?

[ainsleys]

@FishmanL that way the front end can query google to find a likely placename. The thinking was people can then know where they were exposed and assess the risk (i.e., oh, that was a grocery store vs. oh, that was a park). It does expose additional data.

[cankisagun]

@lacabra @ainsleys from the epidemiology feedback issue, we can potentially change the match criteria to 2 meters and location overlap of any period of time.

We can also leave this out of MVP scope. I detailed this further in issue #33

[ainsleys]

Amazing effort from @lacabra and we now have this working within the enclave. Documentation coming soon!

via @lacabra:

• JSON_RPC server implements 4 endpoints documented here: https://github.com/enigmampc/SafeTrace/tree/master/api-server#api-endpoints
• There is a permanently working version of the enclave available at https://safetrace.enigma.co (if you visit with the browser you’ll get a 405 error becuause it does not accept GET requests, only POST requests properly formatted as JSON RPC requests. For example try from command line:

curl -H "Content-Type: application/json" -d '{"jsonrpc": "2.0", "id":1, "method":"getEnclaveReport", "params": {}}' https://safetrace.enigma.co
and you will get the report in response

• As per the above, Remote Attestation just works

• Users can send encrypted data to the enclave, like so: https://github.com/enigmampc/SafeTrace/blob/master/client/data.js. Data gets received by the enclave, that decrypts it, seals it and stores it on disk

• Users can query matches for userdata that has been submitted previously to the enclave: userID is sent encrypted to the enclave. Enclave unseals data, and performs a time+geolocation match between the user and other users that tested positive. The actual matching algorithm is here: https://github.com/enigmampc/SafeTrace/blob/7094bf340e53743950903a2febd8f3c780490296/enclave/safetrace/enclave/src/data.rs#L228

• Time and distance resolution are hardcoded as constants, (Time=5min, Distance=10m) which we can change and recompile, or can be moved to parameters in the future (should be easy)

• Results from the matching algo are encrypted back to the user.

• Sample javascript client code is included for reference here: https://github.com/enigmampc/SafeTrace/blob/master/client/index.js It’s not packaged as a library yet (left as a ToDo, but frontend devs should be able to copy/paste and reuse)

[FishmanL]

All you need to make this initial-DP is to change line 252 of data.rs to subtract 2*abs(lap(0.87)), using (https://docs.rs/GSL/0.4.25/rgsl/randist/laplace/fn.laplace.html), it's a simple change that has real privacy benefits

[lacabra]

Thanks @FishmanL. Can you please document the reasoning behind the 2 constants: 2 and 0.87?

[FishmanL]

Sure -- 0.87 is based on finding the 80% sensitivity of adding an additional random person with covid to the minimum across all people (assuming people are distributed uniformly with at least 10 people with covid per 10000 meters and the max distance we care about is 100 meters, using the order statistics formulae for the uniform to get that 0.87), and the 2 is because, to avoid false negatives, i'm using the absolute value of the laplace instead of the laplace (I'm not sure you need it to actually be twice as far on the tail bounds, but this is overly conservative anyway, so)

[FishmanL]

(the relevant math is 2/(M+1)*(1-x/N)^(M+1) is the tail bound on x, where N is the max distance we care about and M is person density)

[cankisagun]

@FishmanL I invite you to open a PR and propose this code in Rust. We can review and merge it. At this point we do not have the bandwidth to add DP to the MVP matching algorithm