Answer any open questions about client-side Bloom filter badge solution

This spike is to answer the open questions about a client-side Bloom filter approach to solving the badge problem. The list of questions follows. After the questions is a full description of the client-side Bloom filter solution and its pros and cons.

See Also
=======

* [HoneyBadger filter endpoint issue](https://github.com/hypothesis/product-backlog/issues/926) (a different solution to the same problem). Also the [Google doc about the HoneyBadger solution](https://docs.google.com/document/d/1e8dvWDbWtRGwsabcDiM1Uyt8c8kF_yMTa4wFOWhGB_A/)
* [Badger prototype](https://github.com/hypothesis/badger) (another alternative solution to the same problem, similar to HoneyBadger)
* [2015 h-dev thread](https://groups.google.com/a/list.hypothes.is/d/msg/dev/JGjIPWannng/PjkbqjbHBAAJ) about an earlier variation of the client-side Bloom filter solution
* [EPIC: Badge API improvements issue](https://github.com/hypothesis/product-backlog/issues/717) and [google doc](https://docs.google.com/document/d/1TqNduRkkjfIVK98QKrWGpJW3eWmPx2ns4XSrHJfBSdE/). The output of a previous outburst of discussion about the badge issue that did not result in any solution being implemented
* [EPIC: Investigate how best to deal with badge traffic issues](https://github.com/hypothesis/product-backlog/issues/585) seems to be another epic for the same thing, and links to the same google doc

Questions that this spike aims to answer
===============

The aim is that after this spike, with the answers that the spike provided, we will be ready to begin implementing the client-side Bloom filter solution with confidence (or we will know that the solution is unworkable and can discard it). The specific questions that this spike needs to provide concrete, specific and definitive answers to are:

- [x] We need to design the Bloom filter. What exactly does it take as input, when querying it to ask whether something has been annotated. A URL? A normalized URL? A document ID? (We think probably a normalized URL but requires confirmation and proof-of-concept code.)

**Answer:** We think the input is going to have to be normalized URIs

- [ ] If the input to the Bloom filter is going to be normalized URIs, which we think it is, then we need to duplicate h's server-side URI normalization code in JavaScript for the client side URI normalization.

**Task:** Investigate re-implementing our URI normalization in JavaScript. Is it possible? How hard is it? How will we keep the Python and JavaScript copies in sync as we make updates to the code?

- [ ] We need to find or write a Python Bloom filter library for generating the Bloom filter, and a compatible JavaScript one for querying the Python-generated Bloom filter.

**Task:** Choose Python and JS libraries, provide example (not production quality) code for generating (Python), updating (Python) and querying (JavaScript) the filter.

- [ ] How expensive is it to update the Bloom filter every n mins (if any new URLs have been annotated since last time)?

**Task:** Given our chosen Python lib or own code for updating the Bloom filter, and our actual production data, test how expensive adding and deleting URLs is. Test locally. Maybe also test on QA, e.g. by adding unused Bloom filter generation code to h and a Jenkins task to add and delete test URLs.

We think that adding URLs into the filter will be cheap: . Deleting is harder but we don't really need to delete (at least not often). I haven't checked this task as done yet though as I think an actual test using the actual Bloom filter code we intend to use and our actual production data is needed.

Also see this comment: , we create about 1700 new normalized URIs per week day, and about 800 new document IDs.

- [ ] How big will the Bloom filter download be? If it's too big then one download every n mins from every Chrome extension might be too much traffic (although it will be cached by Cloudflare, so those won't be hitting our app servers). We might be able to fix that by having the extension only download the new parts, e.g. an append-only log, but we would only want to implement this if necessary.

**Task:** Given our chosen Python lib or own code for creating the Bloom filter, actually create the Bloom filter for our production data and see how big it is. And given our production rate of growth in the URLs, project forward at least a few years and test this too (by adding in that many randomly generated URLs). This testing can just be done locally. We want an actual answer to the size of the filter today, and its likely size growth in future.

- [x] Do we care about the potential security issue mentioned in **Cons** below?

**Answer:** According to [this comment](https://github.com/hypothesis/product-backlog/issues/950#issuecomment-461104917) the filter only tells a client that a given URL _may_ have been annotated. As the filter gets larger it becomes more likely that Yes does mean that that particular URL has been annotated. Also we should not worry about this because "any sensible system that needs URLs to be secret should use a large key space (eg. UUIDs)". Privacy benefits of extension not sending history to server outweigh this concern, also.

- [ ] How exactly should the Bloom filter response caching work? ETags etc.

**Task:** Research how HTTP caching, browser caching, and Cloudflare caching works, and describe exactly how we would control caching of the Bloom filter download endpoint.

The Client-side Bloom Filter Solution
===================================================

This describes the client-side Bloom filter solution to the badge in full, in one place, where it can be discussed. This is basically a more fleshed out version of the client-side Bloom filter discussion described in [an email to h-dev in 2015](https://groups.google.com/a/list.hypothes.is/d/msg/dev/JGjIPWannng/PjkbqjbHBAAJ) (specifically see my last message in that thread) although this version just has a single Bloom filter for everyone, not a different one for each user as in the 2015 version.

This solution rejects the usage of a separate badge service as suggested by the [Badger prototype](https://github.com/hypothesis/badger) and the [HoneyBadger document](https://docs.google.com/document/d/1e8dvWDbWtRGwsabcDiM1Uyt8c8kF_yMTa4wFOWhGB_A/).

Solution
--------

This solution relies on a [Bloom filter](https://en.wikipedia.org/wiki/Bloom_filter). Specifically, it's a Bloom filter of all URLs that have any annotations in h (including Only Me annotations from any user, and private group annotations from any group). You can query this Bloom filter to ask whether a given URL has any annotations. If the Bloom filter responds No then the badge number is definitely 0. If the Bloom filter responds Yes then the badge number _might_ be greater than zero, if any of the URL's annotations are readable by the current user. When this happens the Chrome extension then needs to query the badge number endpoint to get the actual number and find out if it's greater than zero.

1. Every n mins, _if_ any new URLs have been annotated since last time, a background worker in h updates a Bloom filter that's stored in h's DB.

The Bloom filter only needs to be updated when a new document has been annotated, not on every new annotation. And no more than once every n mins.

If updating the Bloom filter is fast then it could be updated lazily in response to one of the `GET` requests below. Whenever a Bloom filter request comes in, if it has been more than n mins since the last update, you update it as part of responding to that request. Or it could be updated at annotation create/update time -- if the annotation is of a new URL, then you update the Bloom filter as part of responding to the annotation create request. But if updating the Bloom filter is slow then a background worker, possibly kicked off by annotation creates for new URLs, will be needed.

2. h has a new endpoint, `GET /bloom` (path TBD) that just returns the current Bloom filter. No query params. Unauthenticated. HTTP headers in the response instruct Cloudflare and browsers to cache the response for n mins, or for as long as until the current n mins is up.

3. Every time the user browses to a URL the Chrome extension:

1. Fetches the Bloom filter from h with a `GET` request. These responses will be cached by the browser and by Cloudflare, so the Chrome extension isn't really sending a request to h on every page load, but this is handled by caching, the Chrome extension's JavaScript code can be dumb and just send the request every time.

Even if the n mins cache time has expired, it may be possible to do a `HEAD` request only and ask whether the Bloom filter has actually changed, before actually re-downloading it.

2. Queries the Bloom filter client-side (in JavaScript) to ask whether the URL might contain visible annotations.

3. If the Bloom filter responds No, then the Chrome extension shows no badge.

4. If the Bloom filter responds Yes, then the Chrome extension sends an authenticated request to h's badge endpoint.

This returns the actual number of annotations that this user can see, including Only Me and private group annotations.

5. If the number is 0 the Chrome extension shows no badge.

6. If the number is >0 the Chrome extension shows the number on its badge.

Pros
----

* This is overall a simpler solution than creating and deploying a separate service, both in initial development cost and in ongoing maintenance.

* The Chrome extension is no longer sending the user's entire browser history to our servers. Client-side filtering is the only solution that fixes this issue.

* The Chrome extension is no longer sending a request to our servers every time anyone with our Chrome extension installed browses to any web page (a lot of traffic). Client-side filtering is the only solution that fixes this issue. Separate service solutions only move the traffic to a separate service, but we're still receiving the traffic.

* Traffic to the Bloom extension endpoint will be negligible. This is an endpoint with no authentication and no query params. It always returns the same response to all users. It just changes every n minutes. It can be made cacheable by just adding the appropriate HTTP headers to the response. We can expect one Cloudflare request to this endpoint every n mins. That's all that will be hitting our servers (plus badge requests when the Bloom filter responds Yes).

Endpoints that take a URL as query as in the separate service-based solutions aren't very cache friendly.

* Traffic to the badge endpoint will be negligible. Since almost all URLs do not have any annotations, the Bloom filter will prevent almost all badge requests.

* Because its implemented in h rather than in a separate service, the Bloom filter code can much more easily use h's URI normalization and document equivalence logic, and its DB and search index. There's no need to deal with sharing this logic and data with a separate service, or figuring out the API between h and a separate service.

Cons
----

* The Bloom filter needs to be updated by h up to once every n mins. This won't be a problem if updating the Bloom filter is cheap enough. And the Bloom filter updating could even be moved to a separate server.

* When a new document is annotated for the first time this won't show up in badges until the current n minutes is up, and extensions re-fetch the Bloom filter. This should be a short delay. For already-annotated documents, new annotations will cause the badge numbers to increase immediately, no delay.

* Is there a privacy issue with delivering a Bloom filter of all annotated URLs to browser extensions / with making it publicly available at a URL?

The Bloom filter contains private URLs. It can be queried with arbitrary URLs and will answer Yes if the URL has been annotated, which may reveal the existence of private URLs.

Separate service solutions that involve an endpoint that you query to ask whether a URL has annotations also have the same problem, though at least in that case we can rate-limit requests.

Is this actually a problem? Is there something we can do about it? For example, can we encrypt the Bloom filter in such a way that only the Chrome extension (as delivered by us through the Chrome store) can decrypt it? (Requires the Chrome extension to be able to keep a secret key.)

(Struck out because we don't think this is actually an issue.)

What is n?
----------

We should make n configurable via the admin pages (not via an environment variable as that requires EB to do a redeploy in order to change it). We can then experiment with different values, and change it over time if necessary. n could be 10 seconds, or five minutes. The amount of time it takes to update the Bloom filter applies a minimum possible value for n.