When the app records GPS data, it records the following in the local secure database
lat / long / timestamp, as today
A series of hashes computed as follows:
For this time window + 1 “nearby” time window…
For this geohash + N “nerby” geohashes (there may be 0, 1 or many of these - see below)…
A scrypt hash computed from the (geohash, time window) pair, as per details below.
In total, if there are N “nearby” geohashes, a total of 2 x (N + 1) hashes will be stored. These can be stored in an unorded list (no need to store any info on which is which).
The “time window” is a UTC timestamp in seconds, rounded down to the nearesrt 5 minutes.
E.g. Time: 14 April 2020, 12:03:12pm (which rounds down to 12:00:00pm), which maps to 1586865600
The “nearby” time window is defined as follows:
If the timestamp is in the 1st half of the time window (e.g. 12:01pm) it is the preceding time winow (begins 11:55am)
If the timestamp is in the 2nd half of the time window (e.g. 12:03pm), it is the following time winow (begins 12:05pm)
The exact midpoint of the 5 min window (2:30) is ttreated as being in the 2nd half.
We determine N “nearby” geohashes as follows:
If the point is latitude X, longtiude Y, we compute geohashes for the following points:
N: X, Y+1e-04
NE: X+7e-05, Y+7e-05
E: X+1e-04, Y
SE: X+7e-05, Y-7e-05
S: X, Y-1e-04
SW: X-7e-05, Y-7e-05
W: X-1e-04, Y
NW: X-7e-05, Y+7e-05
This is approximately a circle of radius 10m, using an approximate that 1e-05 degrees is 1m. In fact it is 1.1m of longitude and 1.1m to 0.7m of latitude (from the equator to 50 degrees north). Given the overall crudeness of geohash accuracy, and inaccuracy inherent in our GPS position, we consider this “good enough” for MVP1.
Beyond 50 degrees north calculations get a bit more complicated, which we’ll worry about beyind MVP1).
This picture (not necessarily to scale) shows the geohashes that would be considered “nearby” to the central geohash (green), based on the blue GPS position dot.
We use a scrypt hash with the following parameters:
A “cost” (N) that is to be determined. For initial implemention we use 2^12 = 16384. For improved security we expect to move to 2^16,. 2^17 or 2^18 for production, but the exact value still needs to be determined.
A block size (r) of 8 - this is the default.
Parallelization (p) of 1 - this is the default.
A keylen (output) of 8 bytes = 16 hex digits.
As a salt, we use the 4 charaters “salt” (lower case) - or the ASCII values of these letters for scrypt implementations that require a byte array.
For the text to be encoded, we use
The 8 char geohash
Followed by the UTC timestamp of the beginning of the relevant 5 minute time window, in seconds
Example:
Latitude: 51.5019, Longitude: -0.1415
Time: 14 April 2020, 12:03:12pm (which rounds down to 12:00:00pm)
Gives us:
8 character geohash: gcpuuz8u
UTC timestamp: 1586865600
Data string to encode: “gcpuuz8u1586865600”
To keep implementation costs down for MVP1, there is no change to this interface.
Therefore, we continue to send the JSON data exactly as todaY:
{"longitude": 14.91328448, "latitude": 41.24060321, "time": 1589117739000 }
In future we may make an optimization where:
Safe Paths sends the already-computed hash to Safe Places as an additional file in the JSON location data shared
Safe Places stores this off & uses this hash, where available, when generating JSON “points of concern” data.
For MVP1, the value of this optimization is low, as the expected rollout of the app will be low. Therefore we save implementation costs now, and will add this later.
Note that none of the “nearby” geohash or time window calculations performed by the App are shared with Safe Places - just the originally recorded GPS data point & timestamp.
When publishing points of concern JSON data, there are two key changes:
Points of concern
Notification sensitivity controls
The current lat/long/timestamp format is replaced by just a hash.
So this:
"concern_points":[ { "time":1589224427000, "longitude":1.00000919, "latitude":2.00000943 } ]
beocmes this:
"concern_points":[ { "hash":“87e916850d4def3c” } ]
For compatibility reasons as we work through this change, our plan is to add the hash first, and then remove the other points later - so for an interim period during MVP1 development, we may output data like this:
"concern_points":[ { "time":1589224427000, "longitude":1.00000919, "latitude":2.00000943, "hash":“87e916850d4def3c” } ]
This will allow both old & new versions of the app to work with Safe Places. But we aim to move to the final format before we launch MVP1.
Two new top-level fields are added at the top of the HA JSON file.
"notification_threshold_percent":66, “notification_threshold_count”:6 |
These two parameters work together to control the sensitivity of exposure notifications for this data. The Health Authority can turn these based on their experience and feedback from their community.
With the defaults, we trigger an exposure notification if we get more than 66% of location matches, across any 6 consecutive location data points (i.e. if we match 4 or more).
On receipt of the “points of concern” data from the Health Authority, Safe Paths:
Stores the notification sensitivity controls for use during matching
Stores all the reported hash values in a data structure that allows for fast lookups by hash value (e.g. a tree).
Safe Paths then looks for matches on points of concern as follows:
It iterates through each data point stored in its local database.
For each of the 2 x (N+1) hashes stored with that data point, it looks for a match in the HA’s declared “points of concern”.
If it identifies a match, then it marks that data point as having matched a point of concern for that HA. (it must record the specific HA so that it can apply the correct notiifcation sensitivity cotrols).
Having performed this matching on all local data points, it then searches for notifiable events within the local data set.
For each data point that matches an HA’s “point of concern”, it inspects the next K local data points in the local database (where K is the supplied “notification threshold count”). If more than M% of these matched “points of concern” with the same Health Authority (where M is tthe “notification threshold percent”, then it generates an exposure notification.
To determine the duration of the exposure notification, the same calculation is repeated for each data point that matches a point of concern. Exposure notifications that overlap are combined together to create an overall exposure duration.
To illustrate, this diagram shows a series of data points, some of which match, and some of which do not match any points of concern. The brackets on the left indicate the groups of 6 data points that match more than 66% (4 points). The brackets on the right show the overall Exposure Duration that is derived.
Normally, the data points will be ~5 minutes apart. Where data points are missing, and the gaps are more than 5 minutes apart, this does not need to affect the calculation - the same calculation can be performed, and the Exposure Duration may be calculatyed in the same way.
In some rare cases, if a data point right at the end of the Exposure Duration were to be delayed for a long time (e.g. hours), this would result in an overstatded Exposure Duration. That is a characteristic we can live with - we are actively working to reduce the frequency of this kind of occurrence (SAF-257 / SAF-278).
In MVP, under