in reviewhumanPR #170Registry
feat(registry): add dp_bloom, a differentially private registry with a membership-inference validator
This PR adds dp_bloom, a differentially private registry. It serves discovery exactly as the in-memory reference does and publishes a separate membership index that satisfies ε-differential privacy.
Author
@jadidbourbaki
github profile →- Status
- In review
- Opened on
- Jul 10
- Branch
- hackathon/jadidbourbaki-dp-bloom-registry
Description
The pitch.
## Overview
This PR adds `dp_bloom`, a differentially private registry. It serves discovery exactly as the in-memory reference does and publishes a separate membership index that satisfies ε-differential privacy. An observer who reads that index cannot decide whether any single agent registered beyond an e^ε factor. The PR ships the plugin, an adversarial membership-inference validator that the reference registry fails, a scenario, and a test suite.
## Motivation
Every registry today answers who is registered and what each agent can do exactly. That behavior is correct for discovery and it leaks membership. Anyone who queries the registry or reads its published index recovers the full member set and every advertised capability. In many deployments the fact that an agent registered a capability such as `sell_medical_data` reveals more than any message the agent later encrypts. Problem 9 hardened message confidentiality. Nothing in the stack bounds membership confidentiality. This PR adds that surface to the registry and gives it a formal guarantee. I treat this as a new privacy angle on the registry building block rather than one of the ten written problems, which the Phase 1 brief permits when it invites contributors to improve a building block or add a new one.
## Testing Plan
The validator `check_membership_inference_bounded` runs a membership-inference experiment across the seed bank. For a fixed target it estimates the probability the index reports the target present when the target registered and when it did not. It then reports the empirical ε as the larger log-likelihood ratio across the two outcomes. A calibrated `dp_bloom` stays at or below its budget because the membership query is post-processing of an ε-DP index. The exact registry reports the target present exactly when the target registered, so its empirical ε is unbounded and it fails any finite budget. The test suite covers the ε and flip-probability calibration, exact lookups under privacy, byte-identical output under a fixed seed, seed sensitivity across seeds, and the pass or fail gate against both registries. All nine tests pass.
## Some Quick Analysis
Fix k hashes. Inserting one member sets at most k bits, so two registries whose members differ by one agent differ in at most k bit positions. Flipping each published bit independently with probability p gives a per-bit ε of ln((1-p)/p). Sequential composition over the at most k differing bits gives ε = k·ln((1-p)/p), where the unit of privacy is one agent's membership. Inverting for a target budget gives p = 1/(1+e^{ε/k}). The membership query reads only the private index, so post-processing preserves the bound.
The plugin draws the randomized-response coins once from a keyed PRF over a secret per-instance seed, following RAPPOR memoization. An adversary without the seed observes only the published bits and gains advantage at most e^ε. Fixing the seed fixes one draw of the coins and makes a Tier 1 trace reproducible without weakening the guarantee for a seedless adversary.
On identical inputs and seeds the validator measures the following.
| registry | empirical ε | budget plus slack | verdict |
|----------|-------------|-------------------|---------|
| `dp_bloom`, ε=3, k=3 | 2.40 | 4.0 | pass |
| `in_memory`, exact | 6.69 | 4.0 | fail |
## Limitations
The index is monotone. A Bloom filter cannot clear a bit it shares with another member, so `deregister` hides future lookups but leaves historical membership bits until the index rebuilds. The privacy unit is a single membership fact, so repeated registrations by one principal compose and fall outside this bound. A smaller ε raises the flip probability toward one half and increases membership-query error, which sets the usable privacy range.
## Success Criteria
The PR meets each mandatory deliverable in the charter. It adds a registry plugin registered as `("registry", "dp_bloom")`, an adversarial validator that passes the new plugin and fails th
…Try it
Open PR on GitHubView diffCheckout locally
git fetch origin pull/170/head:pr-170
git checkout pr-170