Tracking Epsilon Spend in a Release Ledger

A privacy budget that lives in a design document is not a budget, because nothing checks it. A ledger is the thing that does: an append-only record of every epsilon charged, keyed by the population it was charged against, that a release cannot bypass because the release cannot obtain noise without writing to it.

Core Calculation # permalink

The ledger’s job is to answer one question — what is the total privacy loss for subject population $S$? — under the composition rule the release policy has adopted.

Basic composition is the safe default and is what a ledger should compute unless told otherwise:

Advanced composition buys a $\sqrt{k}$ saving at the cost of a delta. Over $k$ mechanisms each at $\varepsilon$, for any $\delta' > 0$:

Zero-concentrated DP composes additively in $\rho$ and converts once at the end, which is tighter than advanced composition for large $k$:

The critical modelling decision is what a population is. Two releases over disjoint city districts do not compose, because no subject appears in both. Two releases over the same district at different times do compose, fully. A ledger that charges every release against a single global budget is correct but wasteful; one that charges per-release-with-no-key is simply wrong.

Worked numeric example # permalink

A city publishes three products against a total annual budget of $\varepsilon = 10$ per resident:

Under basic composition the citywide budget is already 34.0 against a cap of 10 before the year starts. The design document said “0.5 for the heatmap”, and 0.5 is indeed each release’s charge — but nobody multiplied by 52.

Under zCDP the same schedule composes to $\rho = 52 \times 0.03125 + 4 \times 0.5 = 3.625$, which at $\delta = 10^{-6}$ converts to

Still over, but by a factor of 1.8 rather than 3.4. The honest conclusion is that the weekly cadence has to drop to fortnightly, or the heatmap’s epsilon to 0.2, and that conclusion is only available because something added the numbers up.

Python Implementation # permalink

from __future__ import annotations

import json
import math
import sqlite3
from dataclasses import dataclass, asdict
from datetime import datetime, timezone


class BudgetExceeded(RuntimeError):
    """Raised instead of returning noise when a charge would overrun."""


@dataclass(frozen=True)
class Charge:
    release_id: str
    population_key: str
    epsilon: float
    delta: float
    mechanism: str
    timestamp: str
    parent_id: str | None = None

    @property
    def rho(self) -> float:
        """zCDP charge. Gaussian converts exactly; Laplace is bounded above."""
        if self.mechanism == "gaussian":
            return self.epsilon ** 2 / 2.0
        return self.epsilon ** 2 / 2.0  # conservative bound for pure-DP mechanisms


class Ledger:
    """Append-only epsilon accounting, checked before noise is issued.

    The ledger is authoritative only if nothing can obtain noise without
    writing to it. A helper that adds Laplace noise directly, bypassing
    `charge`, silently invalidates every total this class reports.
    """

    def __init__(self, path: str, caps: dict[str, float], delta: float = 1e-6):
        self.db = sqlite3.connect(path)
        self.db.execute("""
            CREATE TABLE IF NOT EXISTS charges (
              release_id TEXT NOT NULL,
              population_key TEXT NOT NULL,
              epsilon REAL NOT NULL,
              delta REAL NOT NULL,
              mechanism TEXT NOT NULL,
              timestamp TEXT NOT NULL,
              parent_id TEXT,
              PRIMARY KEY (release_id, population_key)
            )""")
        self.db.commit()
        self.caps = caps
        self.delta = delta

    def spent(self, population_key: str, mode: str = "basic",
              since: str | None = None) -> float:
        q = "SELECT epsilon, mechanism FROM charges WHERE population_key = ?"
        params: list = [population_key]
        if since:
            q += " AND timestamp >= ?"
            params.append(since)
        rows = self.db.execute(q, params).fetchall()
        if not rows:
            return 0.0

        if mode == "basic":
            return sum(e for e, _ in rows)
        if mode == "zcdp":
            rho = sum(e ** 2 / 2.0 for e, _ in rows)
            return rho + 2 * math.sqrt(rho * math.log(1 / self.delta))
        raise ValueError(f"unknown composition mode: {mode}")

    def charge(self, c: Charge, mode: str = "basic") -> None:
        """Record a charge, or refuse the release. There is no third outcome."""
        if c.parent_id is not None:
            # Post-processing of an already-charged release is free by the
            # post-processing theorem — record the lineage, charge nothing.
            self.db.execute(
                "INSERT INTO charges VALUES (?,?,0,0,?,?,?)",
                (c.release_id, c.population_key, c.mechanism, c.timestamp,
                 c.parent_id))
            self.db.commit()
            return

        cap = self.caps.get(c.population_key, self.caps.get("*"))
        if cap is None:
            raise BudgetExceeded(f"no cap defined for population {c.population_key!r}")

        projected = self.spent(c.population_key, mode) + c.epsilon
        if projected > cap:
            raise BudgetExceeded(
                f"{c.population_key}: {projected:.3f} would exceed cap {cap:.3f} "
                f"(already spent {self.spent(c.population_key, mode):.3f})")

        self.db.execute("INSERT INTO charges VALUES (?,?,?,?,?,?,?)",
                        tuple(asdict(c).values()))
        self.db.commit()

The parent_id path is not an optimisation. Without it, every downstream derivation of an already-noised release — a map tile, a rounded summary, a CSV export — gets charged again, the budget is exhausted by artefacts that leak nothing new, and teams route around the ledger. Post-processing is free, and the ledger has to know it.

Verification # permalink

The ledger has three failure modes, and each has a test.

It can be bypassed. Grep the codebase for direct noise calls that do not route through charge, and make that grep a CI check:

import ast
import pathlib

ALLOWED = {"privacy/ledger.py", "privacy/mechanisms.py"}

def find_uncharged_noise(root: str) -> list[str]:
    """Any noise call outside the sanctioned modules is a ledger bypass."""
    hits = []
    for path in pathlib.Path(root).rglob("*.py"):
        rel = str(path.relative_to(root))
        if rel in ALLOWED:
            continue
        tree = ast.parse(path.read_text())
        for node in ast.walk(tree):
            if isinstance(node, ast.Attribute) and node.attr in {
                    "laplace", "normal", "gumbel", "exponential"}:
                hits.append(f"{rel}:{node.lineno} — {node.attr}()")
    return hits

Its population keys are wrong. Assert that two releases sharing any subject share a population key. In practice this means deriving the key from the query’s spatial and temporal extent rather than letting the caller pass a string:

def population_key(bbox: tuple[float, float, float, float],
                   time_window: tuple[str, str]) -> str:
    """Derive the key so callers cannot accidentally split a shared population."""
    # Snap to the coarsest partition the policy recognises. Two releases over
    # overlapping extents must land on the same key or composition is missed.
    return json.dumps({"bbox": [round(v, 2) for v in bbox],
                       "window": time_window}, sort_keys=True)

Its totals are not reproducible. Recompute every total from the raw charge rows in a separate process and compare. If a cached total and a recomputed total ever disagree, the cache is the bug — but only a check will tell you which.

Run all three on every release, and fail closed: a ledger that cannot verify itself should refuse the charge rather than approve it.

Edge Cases & Adjustments # permalink

• Budget resets. An annual reset assumes a subject’s exposure in year one does not compound with year two. That is a policy assertion, not a mathematical one, and it is defensible mainly when the underlying population turns over. State the reasoning in the policy; do not let the reset be an artefact of a WHERE timestamp >= ? clause nobody discussed.
• Failed releases. A release that was computed and then discarded still spent epsilon if anyone saw the output — including the engineer debugging it. Charge on noise generation, not on publication.
• Mixed mechanisms. Composing a Laplace charge and a Gaussian charge under basic composition is valid but loose. Convert everything to zCDP for the total and back once at the end, and record both figures so the conservative number remains available.
• Per-district versus citywide keys. A district release charges only that district’s residents; a citywide release charges everyone including them. The ledger must compute a district’s total as its own charges plus every citywide charge, which means population keys need containment, not just equality.
• Retroactive cap changes. Lowering a cap can put an existing population instantly over budget. Decide in advance whether that halts publication or grandfathers existing spend — and make the ledger’s answer explicit rather than emergent.

FAQ # permalink

Should the cap be per subject or per dataset?

Per subject. A dataset-level cap lets a subject appearing in ten releases absorb ten times the loss of one appearing in a single release, which is exactly backwards.

Can I use advanced composition to fit more releases in?

Yes, and it introduces a delta and a much more delicate accounting. zCDP is usually the better trade: tighter than basic, simpler than advanced, and additive in $\rho$ so the ledger arithmetic stays trivial.

Does an analyst querying the noised output spend budget?

No. Post-processing a released artefact is free regardless of how many queries are run against it. That is why the parent_id path exists.

What happens when the budget runs out?

The release is refused. If that is unacceptable operationally, the answer is a lower per-release epsilon or a lower cadence decided in advance — not a cap that yields under pressure, which is a cap in name only.

Related # permalink

• Privacy Budget Allocation for Spatial Queries — how the budget is divided before it is spent
• Gating Releases on a Re-identification Risk Budget — the risk-side companion gate
• Choosing Between Pure and Approximate DP for Map Releases — which mechanism the ledger is recording
• Automating Spatial Privacy Checks in CI — where the bypass scan runs

← Back to Privacy Budget Allocation for Spatial Queries