Counting the crowd without writing down every name.
Picture a stadium gate that needs to know how many different people came in over the season. Writing down every name takes a huge notebook. Compact summaries use another trick: each person goes through a scrambler that turns the name into a number and sends it to one of 16,384 little buckets. Looking only at the buckets, you can estimate the total within 1%, using 12 KB of memory.
That is how Redis counts unique visitors, how databases count distinct customers, and how AI platforms count how many costly requests each customer made, to bill them and to enforce limits.
The "under 1% error" promise has fine print: it holds for people who aren't trying to cheat.
A lock with the code in the manual.
Redis always uses the same scrambler, with a fixed, public seed (0xadc83b19). DataSketches does the same (9001). Anyone can reproduce the scrambler on their own computer and mine names that land wherever they want.
That lets the count go wrong in both directions. Hiding: thousands of costly requests show up as one, and the usage limit never fires. Inflating: a few visitors show up as millions, and the audience dashboard lies.
The fix is cheap: one secret key per counter, drawn at creation. Without the key, the attacker doesn't know where each name will land, and the mining has no target. The summary stays the same size. Theory already said hardening these summaries costs little (Ben-Eliezer and colleagues, 2022), but there was no ready-to-install library. TRUSS is that library.
On counters actually installed.
We didn't attack a paper model. We ran against installed Redis 8.8 and against Apache DataSketches 6.1.1, the distinct counter used by Druid, Hive, Spark and Pinot.
In Redis, 30,000 distinct users chosen by the attacker were counted as 1. Redis answering exactly 1 proves our copy of its scrambler matches byte for byte. In DataSketches, 50,000 distinct became 13.1 million: 262 times too many. Same cause, opposite directions.
With TRUSS's secret key, the same attacks gave 29,705 in the first case and a count within 1% in the second.
We took the case to AI costs: a platform with a limit of 1,000 costly requests per customer, at US$ 0.10 each. With the Redis counter, the abusive customer made 30,000 requests and the limit never fired: US$ 2,999.90 went unbilled. With TRUSS, the limit fired.
| Counter | Scenario | Truly distinct | Counted | Effect |
|---|---|---|---|---|
| Redis 8.8 (HyperLogLog) | honest traffic | 30,000 | 30,195 | true |
| Redis 8.8 (HyperLogLog) | hiding attack | 30,000 | 1 | 30,000× too few; usage limit doesn't fire |
| TRUSS, secret key | same attack | 30,000 | 29,705 | true; limit fires |
| DataSketches 6.1.1 (Theta) | inflating attack | 50,000 | 13.1 million | 262× too many |
| TRUSS, secret key | same attack | 50,000 | ±1% | true |
We also measured the subtler attack, where the attacker asks a question, looks at the answer and adjusts the next step. Against the "sum of squares" estimator (the classic measure of concentration), it inflated an ordinary counter to 2.1 times the correct value. With the copy-switching described in the 2022 paper, which only reveals a fresh copy when the estimate moves to a new level, the result stayed at 1.0: none of the attacker's 20,000 items managed to move the count.
When someone profits from the error.
AI billing and usage limits
Costly requests are an incentive to hide the count. A limit that doesn't fire becomes a direct loss, like the US$ 2,999.90 in the test.
Audience and ads
Unique visitors and impressions can be inflated to sell at a higher price. The dashboard has to withstand whoever wants to inflate it.
Security and abuse
Alarms for scans, new accounts or different cards usually depend on "how many distinct". Hiding them switches the alarm off.
Where you don't need it
If nobody has an incentive to manipulate the count, the ordinary counter is enough. And if the answer must be exact rather than approximate, count exactly.
A counter that estimates the total while storing very little: 12 KB for millions of items, with typical error under 1% on honest traffic.
The function that decides which bucket each item lands in. With a public key, the attacker chooses; with a secret key, they can't.
Someone who asks, looks at the answer and uses it to choose the next step. The ordinary guarantee doesn't cover this case; TRUSS was designed for it.
Where this could be wrong.
Not every defense is complete
Running several copies and taking the median cut the adaptive attack by 2 to 3 times, without eliminating it. The full defense against adaptive attackers, copy-switching, is done for the sum of squares. Distinct counting is protected from mining by the secret key. Other statistics are in progress.
The key must be kept safe
To merge counters from different machines, they all use the same secret key. If it leaks, you are back to the lock with its code in the manual.
The first attack failed
Trying to fake a frequent item in Count-Min didn't work: 1 error in 100,000 queries. It can only overestimate in a bounded way. The attack that worked targets another kind of counter, and we recorded both.
A lab, not your workload
The numbers come from tests with 30,000 to 100,000 items. In production, summary size and volume change the typical error; what doesn't change is the difference between a public and a secret key.
← Certified telemetry · stickybit.com.br
- Our own measurements with the TRUSS library (Go): mining attack against installed Redis 8.8 (30,000 distinct counted as 1; TRUSS 29,705) and against Apache DataSketches 6.1.1 Theta (50,000 counted as 13.1 million; TRUSS within 1%); AI usage-limit case (1,000 requests, US$ 0.10 each); copy-switching on the sum of squares (2.1× versus 1.0×).
- Ben-Eliezer, Jayaram, Woodruff and Yogev, "A Framework for Adversarially Robust Streaming Algorithms", Journal of the ACM, 2022.
- Cohen and colleagues, attacks on CountSketch, ICML 2022.
- Flajolet and colleagues, HyperLogLog (2007): typical error of 1.04/√m, where m is the number of buckets.