Vote for your favorite SkillMD. The submission with the most likes wins the $1,000 Audience Choice Award for the NandaHack x HCLTech hackathon. Voting is open through September 25.Vote now →
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 avatar

@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 diff

Checkout locally

git fetch origin pull/170/head:pr-170
git checkout pr-170