GitHub

Anonymously Counting Users

It’s hard to estimate the number of users of open source software. In the Julia ecosystem, whenever someone installs or updates packages, they connect (by default) to a global network of Pkg servers operated by the open source project. If each client were to send some metadata along with each request, allowing us to count them, then we could use the number of unique client installs making requests to Pkg servers to help figure out the number of Julia users. We also want package authors to be able to estimate the number of people using their specific software. This isn’t merely a matter of curiosity or bragging rights: research funding for open source software is often predicated on demonstrating impact—if you can say “our package was installed on 50,000 systems last year”, that’s a pretty strong argument for the impact of your project. As a community, we also want to understand other things about Julia users, including how many people use various operating systems, how many people are using different versions of Julia, and where in the world Julia users come from.

The simplest way to count unique installs would be for each Pkg client to generate a unique random value (e.g. a random 128-bit value) the first time they make a Pkg request, save it, and then send it as a header along with each Pkg server request. This was proposed at one point, but after much discussion it was deemed to be too much of a privacy hazard. Such a unique ID would allow anyone with access to Pkg server logs to track every Pkg request made by every client. Even with the ability to opt out, doing this by default is too invasive. If we’re going to count clients, we need to ensure anonymity. It should be impossible for anyone—even with full access to our Pkg server logs—to identify or track users making requests.

The naive random ID approach, even though it was deemed unacceptable for privacy reasons, will serve as a “gold standard” for us, at least in terms of functionality. We will judge our solutions by how close they get to providing equivalent functionality to unique client IDs. The “golden features” include:

  • Clients can generate their own IDs, servers do not need to issue them
  • Servers can passively collect request logs and post-process them
  • Client counts can be computed within arbitrary slices of request logs.

Ideally we want something that gives us similar architectural simplicity and flexibility but preserves user anonymity and privacy. Is this even possible? If we can come up with a user count estimation scheme that functionally approximates unique client IDs while preserving user anonymity, we will consider it a success.

The rest of this writeup is about exactly that: a new technique for estimating unique client installs in such a way that individual users are very hard to track or identify, even by people with full access to server logs. It makes two modest sacrifices compared to unique client IDs that have little impact on utility in practice:

  1. It doesn’t allow client counting across completely arbitrary slices of requests—there are certain classes of requests across which client counts cannot be aggregated;
  2. It is approximate rather than exact. We can estimate the number of users in each slice of logs with some random error. The error bounds, however, are small and tunable.

Our approach combines two algorithms that each seem like magic: HyperLogLog and RSA. HyperLogLog is an algorithm for estimating the number of unique values in huge data sets using less memory than seems like should be possible. RSA (Rivest–Shamir–Adleman) is one of the original public key cryptography techniques, which, even though we now take it for granted, also doesn’t seem like it should be possible. The new protocol, which I’m tentatively calling “HyperLogLog Over RSA”, combines these magical technologies and does something new: it allows accurately estimating the number of unique clients making requests to a service without anyone being able to single out or track individual clients, even with full access to request logs.

Throughout this writeup, I will use Julia’s client-server interaction as the grounding context, but user counting via HyperLogLog over RSA is a completely general technique that could be used by other open source projects, or anywhere one wants to estimate unique client counts while keeping individual clients anonymous in the aggregate. As above, the guarantee is strongest precisely where counting matters most—in large populations. Privacy laws like Europe’s GDPR and California’s CCPA make this not just a Good Thing™ to do, but also a legal requirement in many parts of the world.

HyperLogLog

HyperLogLog (HLL) is an algorithm for answering the question “How many unique values are there in this collection of values with repeats?” The naive way to do this, of course, would be to collect all the values and when you see a value, check if it’s in the collection of seen values. But that requires saving all the encountered values, which requires $O(n)$ memory. HyperLogLog allows accurately estimating the number of unique values with $O(\log(\log(n)))$ memory—whence the name. This grows so slowly that it is, for most practical purposes, constant. In most use cases a fixed upper bound on $n$ is assumed, which makes the memory usage actually constant. Being able to count unique values with effectively constant memory, even approximately, is amazing.

It’s worth emphasizing that this is not one of those algorithms that has great theoretical properties but is impractical to use in reality. HyperLogLog is extremely practical and widely used. The constant factor in the asymptotic memory usage is quite small, and relative standard error is around $1.6\%$ in a common configuration and can be made smaller with very modest increases in memory footprint.

Our approach treats each client install as a “unique value” to count and uses HyperLogLog to estimate the cardinality of the set of those unique values. Recall that in the “gold standard” client counting algorithm, each client generates a random unique value. Instead of sending that unique random value, each client can derive a HyperLogLog value from it, and send that instead. Individual HLL samples are very small—only 18 bits in a common configuration—so they don’t encode nearly enough information to uniquely identify all clients. Moreover, since clients generate these values independently, the birthday paradox tells us that collisions occur long before there are $2^{18}$ clients, and since HLL values are highly non-uniform, we actually start getting collisions around as few as 64 clients! This is a promising start but, as we’ll see, there are some issues.

Before we get to the problems with naively using HyperLogLog for counting clients, let’s develop an intuition for how and why HyperLogLog works. Suppose each client draws a random geometric sample value, i.e.

  • $0$ has probability $\frac{1}{2}$
  • $1$ has probability $\frac{1}{4}$
  • $2$ has probability $\frac{1}{8}$
  • $k$ has probability $\frac{1}{2^{k+1}}$

The basic intuition of HyperLogLog is that if the maximum geometric sample observed is $k$ then there are around $2^k$ unique values in the set. Of course, this estimator is terrible. It only ever estimates power-of-two cardinalities and has huge variance. HyperLogLog addresses both problems by uniformly splitting the space of clients into buckets, making a geometric estimate for each bucket, and then combining all those estimates into a single improved estimate. With enough buckets this actually produces a high quality estimate. The number of necessary buckets is not even inordinately large—in the common configuration we’ve mentioned, there are $2^{12} = 4096$ buckets, which gives relative standard error of $1.63\%$, corresponding to a 95% confidence interval of $±3.19\%$. If more accuracy is desired, it’s relatively cheap to add more buckets and reduce the error bounds—the error is inversely proportional to the square root of the number of buckets.

Each HyperLogLog sample has two parts:

  • b: a uniformly distributed bucket index
  • k: a geometrically distributed sample value

The common configuration we’ve referred to above has $2^{12} = 4096$ buckets and caps the geometric sample value at $63$ so that the geometric value can be encoded with $6$ bits and the estimates are capped at $2^{63}$. This is plenty for many purposes, including ours. Each such HyperLogLog value can be encoded with only $18$ bits: $12$ bits for the bucket and $6$ bits for the geometric sample. If we want to splurge and allow estimating cardinalities up to $2^{127}$ we need only a single extra bit per HLL value. If we want to make our estimates twice as accurate, we have to quadruple the number of buckets, which only costs two extra bits per HLL sample. HyperLogLog’s extreme memory efficiency means every additional bit has great leverage. We will use the “typical” 18-bit configuration as a reasonable reference point throughout.

A straightforward implementation of generating a random HLL pair is:

b = rand(UInt16) >> 4
k = min(63, trailing_zeros(rand(UInt64)))

Suppose each client generates an 18-bit HLL sample value like this once, saves it, and then includes that value in the header of each Pkg request it makes. Then we can estimate the number of unique clients appearing in any subset of request logs by applying HyperLogLog aggregation and estimation to the HLL values for that set of logs. Since each client’s HLL value is only 18 bits, it’s impossible to uniquely identify most users—there just aren’t enough bits to distinguish more than $2^{18} = 262144$ different users—and since they generate values independently, collisions will start to happen long before that many users.

This seems pretty good. Can we just do this? I have, frankly, considered it. But there are two main issues that have given me pause:

  1. Most clients get small geometric sample values that are very common and thus anonymous, but some clients will get rare geometric values and be highly identifiable. HLL samples are anonymous on average, but an inherent aspect of how the estimator works is that some values are rare and thus not anonymous.
  2. HyperLogLog values are trivially forgeable. If a malicious client were to send requests with intentionally large geometric values, they could inflate the client count estimates arbitrarily high, rendering them useless. Worse: a malicious client only needs to send one forged request per bucket to push the estimate to the maximum.

Using HyperLogLog by itself for unique client estimation, while tantalizing, is not as anonymous as we’d like and requires a trivial amount of work to sabotage. Fortunately, both of these issues can be addressed.

Resource class sharding

The first problem with HyperLogLog is that some clients get rare, highly identifiable hash values. This issue can be mitigated by sharding requests by resource class. The idea is to split requests into classes that are narrow enough that correlating a client’s behavior within each class is harmless yet broad enough that estimating within each class is still useful. Rather than having a single global HyperLogLog value, a client would have a different, independent HLL value for each resource class. There may be situations where such a split is not possible, but in Julia’s Pkg server context, it’s fairly clear how to do it—a resource class would be some prefix of a request URL’s resource path. For example, here’s how I would map resource paths to resource class prefixes:

  • /registries $\longrightarrow$ /registries
  • /registry/$uuid $\longrightarrow$ /registry/$uuid
  • /package/$uuid/$hash $\longrightarrow$ /package/$uuid
  • /artifact/$hash $\longrightarrow$ /artifact/$hash

For registries and artifacts, this is the full resource path; for packages, it lops off the package version hash, keeping only the package UUID. Note that this means that each client generates a new, statistically independent HyperLogLog value for each package and artifact that they request. This sharding scheme allows estimating:

  • Total Julia users via requests to /registries
  • Users of each registry via requests to /registry/$uuid
  • Users of each package via requests to /package/$uuid
  • Users of each artifact via requests to /artifact/$hash

Estimates can be made for arbitrary slices of the request logs within each resource class too. We can, for example, aggregate at various time scales—daily, weekly, monthly, yearly. We can slice by region, operating system, Julia version, and any other data that the client shares with the servers. Or any combination of the above that may turn out to be of interest. There’s no need to anticipate which ways of slicing and dicing will be useful ahead of time—logs can be queried and aggregated arbitrarily after the fact.

This slicing freedom comes with one important caveat, which connects back to anonymity. A slice is a population restriction, and the anonymity of HyperLogLog counting depends on the population being counted being reasonably large. Slice finely enough—a single package, in one country, on one Julia version, in one hour—and the effective population can fall to a handful of clients or even one, at which point the bucket-and-geometric tag in that slice is unique and reporting it would single out individuals. The protocol therefore enforces a minimum-cardinality floor: it refuses to report (or publish) any slice whose estimated cardinality falls below a threshold, folding everything beneath the floor into a single “other” aggregate. This costs almost nothing in practice, because HyperLogLog is already a poor estimator at small cardinalities—the slices a floor suppresses are exactly the ones whose counts were least trustworthy anyway. We return to how to choose the floor, and to a subtlety about answering many overlapping queries, in the Protocol Summary.

The only thing that resource class sharding prevents is aggregating or correlating across classes. You cannot ask how many clients downloaded package A or B. You can only estimate A and B separately, you can’t estimate the union or intersection. This is a limitation, but it seems like an acceptable one. Whereas there is significant demand for knowing how many users there are of specific packages, there is very little call for estimating correlations between packages.

How does sharding help privacy? Even in the original, simple “each client sends a unique ID” scheme, resource class sharding makes the privacy situation considerably better. Imagine that instead of sending the same ID with each request, each client generates a “master key” and derives a “class-specific ID” for each request class by cryptographically hashing the master key with the resource class string. This prevents tracking users across resource classes since the IDs are different and the cryptographic hash prevents linking them. You could still see that the same client downloaded three versions of a package this month, but you’d have no way to connect that to the same client downloading any other packages. This is actually not a bad scheme, but I suspect that some people would still strongly object to clients being uniquely identifiable at all, and it may still run afoul of privacy laws like GDPR.

Resource class sharding with HyperLogLog works in much the same way except that instead of sending the derived class-specific ID, the client uses the hash of the master key with the class string to generate a HyperLogLog value and sends that along with the request. The HLL values in different classes are statistically independent thanks to the cryptographic hashing. In a given resource class, only a few unlucky clients will have rare, uniquely identifiable values. Crucially, clients that are rare in one class will be common in most other classes. Even if a client is unlucky enough to be rare in two different classes, the server has no way of knowing that those rare HLL values belong to the same client.

Sharding also improves fairness. Without sharding, most clients are unremarkable, but a few, unlucky clients have uncommon, identifiable HLL values. This is unfair: some clients are trackable, most aren’t. With sharding, every client will be unremarkable in most classes and rare in a few. Since there are an unbounded and, in practice, large number of resource classes—one per package/artifact—each client will be anonymous in most of them and rare in only some. This is a much fairer and more symmetrical situation.

One may object that some resource classes are surely more important than others. For example, suppose a client has a rare HLL value in the /registries class. Doesn’t this seem more significant than having a rare sample in some obscure package’s class that the client may never even download? Perhaps, but consider that the only thing you can learn about a client with a rare value in the /registries class is how often they check for new registries—information that is not interesting or sensitive in the slightest. Not accidentally either: this information is uninteresting precisely because everyone requests /registries regularly. If a package has very few users, on the other hand, then it’s more notable if some user does download it, but for the very same reason, none of the package’s users is likely to have an especially rare HLL value. The rarity of the most uncommon HLL value in a class is inherently inversely related to the popularity of that resource class: the rarest HLL sample values will tend to happen in classes that are the most popular—and popular classes are the ones that are the least interesting to learn anything about. With sharding, the most identifiable HLL values tend to occur in the least interesting classes and the most interesting classes tend to have the least identifiable HLL values.

Sharding is an effective privacy measure because almost everything of interest to an attacker comes from following users across packages, which is precisely what sharding blocks. On the other hand, correlating users across packages is of fairly minor interest for legitimate purposes, and losing that ability is a small sacrifice for a significant privacy gain.

Signed HLLs?

The second major issue with clients generating and sending raw HyperLogLog values is how easy it is for a malicious client to forge large geometric values and sabotage client count estimates. If a single malicious client sends k = 63 in every bucket, then the client count estimate is inflated to 19 quintillion (billion billion) clients, which is obviously absurd, but also makes all our estimates useless. In other words, the entire system can be brought to its knees with a tiny number of malicious requests—only one per bucket, of which there are only a few thousand. If the attack is that blatant, of course, it’s easy to filter out the requests with the implausible k = 63 geometric sample values, but a more subtle attack could render estimates incorrect without being so easy to detect or filter.

To prevent spoofing, it seems like a client would need to present, alongside its HyperLogLog value, some evidence that it got that value legitimately and didn’t just “make it up.” Some kind of stamp of authenticity—a digital signature. A simple signature system would be for the server to generate a random secret key and cryptographically hash the HLL value along with that key, and use the hash value as a signature. If the client presents the correct hash value with its HLL value, then the pair is valid; otherwise it should be ignored for client counting purposes. Unfortunately, there are several problems with signed HLL values—some are solvable while others are not.

The first problem with signed HLL values is that many signature schemes could themselves act as a unique client fingerprint, which is exactly what we’re trying to avoid. It doesn’t matter if the HLL value is only a few bits if the signature that accompanies it is large enough to uniquely identify billions of clients. Maybe the signature is a pure function of the HLL value, but how can the client know that? A protocol that’s supposed to protect client anonymity needs to not only be resilient to misbehaving clients, but also prevent malicious servers from surreptitiously tracking users. Unless the client has a way to verify that the signature attached to an HLL value is the unique, correct signature for that value, then a signature scheme can be used by a malicious server to track clients.

This problem is solvable: public key cryptography allows signatures that can be checked but not forged. The server publishes a public key and signs each HLL value with its corresponding private key. A client can check that the signature is correct using the public key. Depending on the public key system chosen, additional care may need to be taken to ensure that multiple different signatures cannot appear correct, but this is a minor technical detail. Public key cryptography applied carefully can fully solve this issue.

A second problem with HLL signatures is that we still want to do resource class sharding. This means that a client needs a different signature for each resource class and it has to serve the same HLL value for that resource class every time (otherwise we’re counting requests, not clients). The obvious way to do this is for the client to request a new HLL value the first time it makes a request in a given class and then store that value to be used in the future. Assuming 256 bits per resource class key, 18 bits per HLL value, 512 bits per signature (common for state-of-the-art elliptic curve signatures; other systems have larger signatures), that’s about 100 bytes per resource class. If the typical user installs 5k packages over time, that’s half a megabyte of storage. Given modern hard disk capacity this is certainly feasible, but that’s a lot of data for each client to keep around for the sake of something that arguably doesn’t benefit the individual user directly. Even if it is feasible, it has an “optics” problem: people may see this data and think “Why are they storing all this 'telemetry' data about me?” Yes, we can explain how the data isn’t used to track you, but it doesn’t look great.

A third problem with signed HLL values is that it adds operational complexity to our servers. This can certainly be done, but it comes at a cost. We have carefully designed the Pkg server system to be simple and reliable to run. The /registries endpoint is the only Pkg endpoint that ever changes—everything else that a Pkg server serves is immutable and content addressed and thus perfectly cacheable without possibility of invalidation. Even the /registries endpoint can be implemented as a small, static file that just needs to be updated when registry content changes. This means everything in the Pkg protocol is straightforwardly cacheable: most paths can be cached forever, and /registries can be cached with any reasonably short time to live. This makes putting a content-delivery network (CDN) in front of Pkg servers trivial, and we lean quite heavily on CDNs. An endpoint handing out randomly generated, signed HLL values would require complex, dynamic logic on a server, would be inherently uncacheable, and could not be served through a CDN. All feasible, but not ideal.

The last and most critical problem with signed values is that they still allow malicious clients to observe and selectively choose HyperLogLog values with large geometric values. If the HLL values are sent in the clear, it’s trivial to request as many as one wants and selectively choose the rarest one. This can be partially addressed by encryption: instead of sending HLL values in the clear, encrypt them. We can’t use off-the-shelf encryption algorithms since they all have block sizes of at least 64 bits—if we encrypt an 18-bit HLL value with a 64-bit block cipher, we get an opaque 64-bit value with plenty of bits to fingerprint clients. Fortunately, one can easily roll a bespoke Feistel cipher whose block size matches our HLL size. Since the encrypted payload is the same size as an HLL value, and the signature can be checked to be a pure function of the encrypted HLL value, the client can be sure that only one HLL value’s worth of identifying information is being submitted with each request.

Encryption doesn’t entirely solve the observability problem, however: even if they’re encrypted, a malicious client can request a large number of HLL values and observe which values are served most often—they can statistically reconstruct the distribution of HLL values by observation. They can submit the rarest ones they get as often as they want and bias our client count estimates. This is not as severe a problem as an attacker being able to forge arbitrarily large geometric samples, but it means that they can inflate user count estimates.

Is this significantly worse than the “gold standard” of random unique client IDs? Unfortunately, it is. With client IDs, if an attacker wants to inflate the client count for a slice of requests by $n$ extra clients, they have to make $n$ requests. With encrypted, signed HLL values, the attacker has to do a lot of work up front to find rare values, but once they have some rare values, they only need to send one request per bucket in a slice in order to inflate its client count. Of course, they don’t know which values are in which buckets, but they can submit all of the rarest values that they’ve found (presumably whichever ones they’ve only seen a single time). This means that given enough up front work finding rare HLL values, any slice of requests can be inflated arbitrarily with a fixed amount of attack-time effort.

Any one of these problems might not be fatal on its own, but between the size of data storage required, the additional operational complexity, and the fact that an attacker can still inflate estimates with a fixed amount of effort, signed HyperLogLog values are, unfortunately, not an appealing solution for client count estimation. If this was the best we could do, I might consider deploying it, but I would have significant reservations. Fortunately, however, signatures are not the only possible solution.