Counting Without Watching

Abstract. We state an open problem we have not solved. Our stated objective is eight billion useful, daily-used personal agents; our stated architecture forbids the telemetry that would ordinarily measure such a thing. These two commitments are in direct tension, and we have been operating without resolving it. This paper formalizes the tension as a measurement problem under a consent constraint, gives a threat model, surveys the primitives the literature already provides, proposes a construction combining edge-local aggregation, receipt-anchored attestation, and calibrated noise, and states plainly where the construction is weak and what remains unsolved. We publish it in the open because the problem is more useful to the field than our eventual answer to it.

1. The problem, stated honestly

Every company that builds personal software eventually writes down a number that defines it. Ours is eight billion useful, daily-used agents — not accounts created, not impressions served, but agents that did something genuinely valuable for the person who owns them, today.

The ordinary way to measure that is to instrument the client, emit an event per interaction to a central pipeline, and count. This is so standard it is nearly invisible as a design choice. It is also, for us, forbidden. The architecture we committed to says that sensitive computation happens on hardware the person owns, that data leaves only by a specific, scoped, revocable grant, and that every departure writes a receipt the owner can read. An event stream that reports “this person used their agent to do this kind of thing at this time” is precisely the behavioral exhaust we exist to eliminate.

So we have a company whose most important metric is, by its own design, the one thing it has chosen not to observe. That is not a rhetorical flourish; it is our actual operating state. We do not currently have an instrument that measures daily useful agent usage at the fidelity the objective demands, and we have said so publicly rather than let the number quietly become a guess.

We think the problem generalizes well beyond us. Any system that promises local-first computation and then needs to know whether it is working faces the same contradiction. The literature on private analytics is deep, but it has largely been developed for a setting the promise here rules out: a trusted central collector receiving per-user reports.

2. Definitions

Agent. A software process bound to exactly one owner, executing on hardware the owner controls, capable of acting on the owner's behalf under grants the owner issues.

Useful session. A bounded period in which an agent completed at least one owner-initiated or owner-approved task that produced an outcome the owner can point to. The definition is deliberately outcome-anchored rather than interaction-anchored: opening an application is not usefulness, and neither is a background poll.

Grant. A consent object naming a scope (what data), a purpose (what for), a validity window (until when), and a revocation handle. Access outside a live grant is not permitted; revocation terminates future access under that grant unconditionally.

Receipt. An append-only record, readable by the owner, produced by every access performed under a grant. A receipt names the requester, the grant, the time, and what was returned.

The measurement question is then: estimate D(t), the number of distinct agents with at least one useful session in day t, and a small number of coarse breakdowns of it, such that the estimate is accurate enough to steer a company, and such that no party — including us — learns anything about any individual owner beyond what that owner explicitly granted.

3. Threat model

We assume the adversary is us. This is the unusual and, we think, correct posture. A privacy architecture that assumes the operator is benign has assumed away the only threat it can actually control. So:

The operator is honest-but-curious and may become hostile. Our own future employees, our own future acquirer, and anyone who compels us legally should be unable to reconstruct individual behavior from the measurement system, regardless of intent. The guarantee must be structural, not procedural.

The network is observable. Timing, size, and frequency of reports are visible to a passive observer, so a construction that hides payload contents but reports at behavior-correlated times leaks the behavior anyway. Metadata is data.

A minority of clients are malicious. Because agents run on hardware the owner controls, an owner can modify their client. A construction that trusts client-reported counts is trivially inflatable — which matters commercially, since an inflated usage number is exactly the thing a dishonest operator would want.

Owners are not adversaries and should not be treated as such. This rules out remote attestation schemes whose effect is to prevent a person from controlling a machine they own. We would rather accept measurement error than ship an architecture that treats ownership as a threat.

These four together are restrictive. The third and fourth are in genuine tension, and resolving that tension is, in our view, the hardest part of the problem.

4. What the literature already gives us

We are not starting from nothing, and it would be dishonest to present this as unexplored ground. Four bodies of work bear directly on it, with public deployments we have studied.

Randomized response and local differential privacy.The idea that a respondent can answer a sensitive question with calibrated randomness, such that individual answers are deniable but population statistics are recoverable, dates to Warner's 1965 work on survey methodology and was adapted for large-scale software telemetry in Google's RAPPOR (2014) and Apple's local differential privacy deployment (2016). Local DP fits our setting well because it requires no trusted collector. Its cost is severe: the noise required for meaningful privacy at the individual level makes small subpopulations effectively unmeasurable.

Shuffling and the encode-shuffle-analyze model. The observation that anonymizing a batch of reports before analysis amplifies a weak local privacy guarantee into a much stronger central one, developed in the Prochlo line of work and the subsequent shuffle-model literature. This is attractive here: it buys back much of the accuracy that pure local DP destroys, provided the shuffler does not collude with the analyzer.

Cardinality estimation under sketches. Counting distinct entities without storing them is a solved problem in the non-private setting — HyperLogLog and its relatives give tight estimates in kilobytes. The private variants are subtler than they first appear, because a sketch is a lossy but real function of the identities inserted into it, and naive merging across time can leak membership.

Secure aggregation. Protocols from the federated-learning literature let a server learn the sum of many client vectors without learning any individual vector, tolerating dropout. This gives us summation without disclosure, which is most of what a usage scoreboard needs.

None of these were designed for the specific object we care about — an outcome-anchored notion of usefulness, attested by a consent receipt — and that gap is where we think the contribution lies.

5. Proposed construction

We describe the design we intend to build. It is not yet implemented; treating it as a result would violate the standard this paper is trying to hold.

The construction has four stages, and the essential move is that the unit of measurement is derived from receipts the owner already holds, rather than from a parallel telemetry channel. If a useful session is definitionally one that produced receipts, then the receipt log — which exists for the owner's benefit and is already consent-gated — is the honest substrate for measurement.

  ON THE OWNER'S DEVICE                    │  OFF-DEVICE
                                           │
  1. DERIVE      receipts ──► useful?      │
     (local)     outcome-anchored predicate│
                        │                  │
  2. SKETCH      daily bit / bucketed      │
     (local)     sketch, salted per epoch  │
                        │                  │
  3. NOISE       calibrated randomization  │
     (local)     local DP at the edge      │
                        │                  │
                        ▼                  │
  4. SHUFFLE + AGGREGATE ─────────────────►│  sum only,
     unlinkable transport, secure sum      │  never a row

Stage 1 — derive locally. The agent evaluates the useful-session predicate on its own receipt log, on-device. The predicate is public and auditable, so an owner can verify what is being counted about them. No raw receipt is ever an input to anything off-device.

Stage 2 — sketch. The agent produces a minimal object: for the core metric, one bit for the day, plus a small number of coarse buckets (for example, a region at low resolution and a broad task family). Identifiers are salted per epoch so that sketches from different epochs cannot be linked into a trajectory, which is the property that makes longitudinal profiling infeasible rather than merely discouraged.

Stage 3 — randomize at the edge. Local randomization is applied before anything leaves, so the guarantee does not depend on the honesty of any later party. This is the stage that makes the operator-as-adversary assumption survivable.

Stage 4 — shuffle, then aggregate. Reports traverse an unlinkable transport that strips origin metadata and batches on a fixed schedule — importantly, on a schedule uncorrelated with when the person actually used their agent, since a report that arrives when a person acts leaks that they acted. The analyzer computes sums under secure aggregation and never sees an individual contribution.

The result is a daily figure with a quantified error bar, plus a handful of coarse breakdowns, and no path from the published number back to a person.

6. Why the obvious alternatives fail

“Just ask people to opt in to analytics.” Opt-in telemetry is legitimate and we support it, but it does not answer this question. The population that opts in differs systematically from the population that does not, and the bias is correlated with exactly the thing being measured — privacy-motivated users are both our core constituency and the least likely to opt in. An estimate biased toward the users least representative of the thesis is worse than no estimate, because it is confidently wrong.

“Count server-side from API calls.” This measures the fraction of the product that is not local-first. As the architecture succeeds and more work runs on-device, this metric falls. Optimizing it would mean optimizing against our own thesis, which is the classic failure of measuring what is easy instead of what is true.

“Trust the client's reported count.” Owners control their hardware, so counts are inflatable at will. Since the operator has a commercial incentive to see a large number, a construction that cannot resist inflation is one whose output no external party should believe — including our own board.

“Use a trusted third party.”This relocates the trust assumption without discharging it, and a promise that depends on another company's good behavior is the same category of promise we have argued against throughout our work.

7. Evaluation plan

A construction of this kind should be judged on four axes, and we state our intended acceptance thresholds in advance so that we cannot move them afterward.

Accuracy. Relative error on the daily figure within a few percent at population scale, with the error bar published alongside the number rather than omitted. A scoreboard that reports a point estimate without its uncertainty is a scoreboard that will eventually be misread.

Privacy. A stated epsilon for the local stage and the amplified bound after shuffling, with the composition over a year computed and published — since a daily release composes, and a per-release guarantee that ignores composition is not a guarantee at all.

Inflation resistance. The cost, to an adversary controlling a given fraction of clients, of shifting the published figure by a given amount. We expect this to be our weakest axis and we would rather report it honestly than omit it.

Cost. Bytes and battery per device per day. A privacy mechanism that meaningfully degrades the device is one that will be switched off, and a mechanism nobody runs provides no privacy.

8. Limitations and open problems

We think the following are genuinely unresolved, and we would rather name them than let a reader discover them.

Usefulness is not obviously measurable. Our definition — a completed, owner-approved task with a pointable outcome — is a proxy. A person whose agent quietly prevented a problem may have had the most valuable day of all and generated almost no signal. Every outcome-anchored metric we can construct is biased toward legible activity and against exactly the calm, invisible operation we claim to want. We do not know how to fix this, and we suspect it is the deepest problem in the paper.

Inflation resistance and owner sovereignty may be irreconcilable. If the owner genuinely controls the hardware, the owner can lie. Attestation would fix it at the cost of the ownership property. We currently choose ownership and accept a weaker integrity guarantee, but we do not claim this is settled, and a construction that achieves both without hardware-rooted coercion would be a real contribution.

Long-tail breakdowns may be unmeasurable in principle. Small subpopulations cannot be measured under any meaningful local guarantee. Some questions we would like to answer about small communities are questions we should expect never to answer, and the honest response is to say so rather than to quietly lower the privacy bar for them.

Composition over years is unsolved for us. Daily releases compose. A ten-year privacy budget for a system meant to run indefinitely is an unresolved design question, not a parameter we can simply pick.

9. Why publish an unsolved problem

There is an obvious argument against this paper: it announces that the company does not measure its own most important number. We think publishing is correct anyway, for three reasons.

The first is that it is true, and we have committed to reporting our own state accurately whether or not it flatters us. A company that only publishes its good days eventually gets believed on none of them.

The second is that the problem is more valuable to the field than our eventual solution. Local-first software is proliferating, and the measurement contradiction we have described is going to arrive for everyone building it. Stating it precisely is a contribution even before anyone solves it.

The third is disciplinary. Publishing acceptance thresholds before building the system removes our ability to quietly relax them later. We have written down what would count as success while we still have no result to protect.

We would rather be the company that published the hard version of its own scoreboard problem than the one that shipped a comfortable number nobody should have believed.

References and gratitude

This paper stands on public work by others, cited with admiration and no claim of affiliation or endorsement. On randomized response: S. L. Warner, “Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias” (1965). On local differential privacy in deployed telemetry: the RAPPOR line of work from Google (2014) and Apple's published local differential privacy work (2016). On the shuffle model and encode-shuffle-analyze: the Prochlo work and the subsequent privacy-amplification-by-shuffling literature. On cardinality estimation: the HyperLogLog family. On secure aggregation without disclosure of individual contributions: the practical secure-aggregation protocols developed for federated learning. On the foundations of differential privacy and composition: the work of Dwork, McSherry, Nissim, Smith, and colleagues.

Errors, omissions, and the unresolved parts are ours. If you work on private measurement and think our construction is wrong, we would genuinely like to hear it.