Differential Privacy under Continual Observation

Publishing a Counter at Every Time Step

A stream releases information repeatedly: after events $x_1,x_2,\ldots$, users see prefix totals $S_t=\sum_{i=1}^t x_i$ at every time $t$. Adding independent noise to every release seems natural, but one event influences every later prefix, so privacy loss can grow with the horizon.

Continual observation treats the entire output transcript as one mechanism. Two streams are event-level neighbors when they differ in one bounded event. An $(\varepsilon,\delta)$-private mechanism requires every set of possible transcripts to have nearly the same probability on neighboring streams. This protects one event’s participation, not necessarily all events belonging to one person.

For events $(1,0,1,1)$, exact prefixes are $(1,1,2,3)$. A binary-tree mechanism stores noisy sums for dyadic intervals such as $[1,4]$, $[1,2]$, $[3,4]$, and leaves. Prefix 3 is reconstructed from disjoint nodes $[1,2]$ and $[3,3]$. Reusing node noise across releases avoids paying separately for every prefix.

Sensitivity measures how much one event changes the released node vector. Composition combines privacy loss from multiple mechanisms. A privacy filter stops or modifies releases before a running budget is exceeded. Utility quantifies error, usually per time, uniformly over all times, or for a downstream decision. The horizon, event bound, neighboring relation, and release schedule are part of the theorem.

Event-Level Privacy Across a Timeline

Fix horizon $T$ and $L=\lceil\log_2T\rceil+1$. Build the complete dyadic tree. Release every node sum with independent Laplace noise of scale $L/\varepsilon$. Changing one event by at most one changes exactly one node on each level, so the vector of all node sums has global $\ell_1$ sensitivity at most $L$. The Laplace mechanism therefore makes the entire noisy node vector $\varepsilon$-differentially private; all prefix releases are post-processing.

Each prefix decomposes into at most $L$ disjoint dyadic nodes. Its noise is a sum of at most $L$ independent Laplace variables. The standard deviation is at most \[ \sqrt{2L}\frac{L}{\varepsilon}=O\!\left(\frac{L^{3/2}}{\varepsilon}\right). \] Tail bounds add dependence on failure probability $\beta$; a uniform-over-time guarantee also pays for controlling all $T$ releases, typically through a union bound or sharper maximal analysis. Constants depend on whether privacy is pure or approximate and whether error is pointwise, expected, or simultaneous.

This proof assumes a bounded event contribution, a fixed or safely extended horizon, independent correctly generated noise, no release of raw node sums, and no side channel leaking exact state. User-level privacy needs contribution limits across all of a person’s events and usually more noise.

flowchart TD
 A[Define neighboring event streams] --> B[Fix horizon T and depth L]
 B --> C[Map each event to one node per level]
 C --> D[Node vector sensitivity at most L]
 D --> E[Add calibrated Laplace or Gaussian noise]
 E --> F[Entire noisy node vector is private]
 F --> G[Decompose each prefix into at most L nodes]
 G --> H[Release prefix by post-processing]
 H --> I[Bound pointwise or uniform utility]
 A --> J{Unbounded contribution or wrong adjacency?}
 J -->|yes| K[Privacy claim invalid]
 J -->|no| B
 classDef navy fill:#17365D,color:#fff,stroke:#17365D;
 classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
 classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
 classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
 class A,B,C,D navy;
 class E,F,G purple;
 class H,I teal;
 class J,K crimson;

Binary Trees, Noise and Composition

The tree can be viewed as one vector-valued Laplace mechanism or as composition across levels. The vector view makes reuse safe: publish each noisy node once, and derive every prefix by post-processing. Resampling noise whenever a node is reused creates additional releases and invalidates the original accounting.

import math
import random

def laplace(rng, scale):
    u = rng.random() - 0.5
    return -scale * math.copysign(math.log1p(-2 * abs(u)), u)

def dyadic_intervals(horizon):
    if horizon < 1 or horizon & (horizon - 1):
        raise ValueError("horizon must be a positive power of two")
    intervals = []
    size = 1
    while size <= horizon:
        for start in range(0, horizon, size):
            intervals.append((start, start + size))
        size *= 2
    return intervals

def private_prefixes(events, epsilon, seed=7):
    if epsilon <= 0 or not events:
        raise ValueError("positive epsilon and nonempty events required")
    if any(value < 0 or value > 1 for value in events):
        raise ValueError("events must lie in [0,1]")
    horizon = len(events)
    intervals = dyadic_intervals(horizon)
    levels = int(math.log2(horizon)) + 1
    rng = random.Random(seed)
    noisy = {}
    for start, end in intervals:
        noisy[(start, end)] = sum(events[start:end]) + laplace(rng, levels / epsilon)

    output = []
    for end in range(1, horizon + 1):
        cursor, total = end, 0.0
        while cursor:
            width = cursor & -cursor
            total += noisy[(cursor - width, cursor)]
            cursor -= width
        output.append(total)
    return output, noisy

events = [1, 0, 1, 1, 0, 1, 0, 1]
released, nodes = private_prefixes(events, epsilon=1.0, seed=11)
released_again, nodes_again = private_prefixes(events, epsilon=1.0, seed=11)
assert released == released_again and nodes == nodes_again
assert len(released) == len(events)
assert len(nodes) == 15

changed = events[:]
changed[5] = 0
intervals = dyadic_intervals(8)
touched = [interval_ for interval_ in intervals
           if interval_[0] <= 5 < interval_[1]]
assert len(touched) == 4

try:
    private_prefixes([0, 2, 1, 0], 1.0)
    raise AssertionError("unbounded event accepted")
except ValueError:
    pass

print("exact prefixes:", [sum(events[:i]) for i in range(1, 9)])
print("private prefixes:", [round(x, 3) for x in released])
print("nodes touched by event 6:", touched)

Private Monitoring Under Continual Release

Teaching should compare exact prefixes, independently noised prefixes, and a tree transcript on the same eight events. In professional monitoring, releases might track incident counts, service demand, or public-health events; the data contract must bound contributions before noise calibration. A failure case is a dashboard claiming user-level protection while one person can generate thousands of events.

Production design must specify horizon extension, late events, corrections, retention, random-number generation, privacy ledger, access control, and downstream post-processing. A privacy filter can reject optional releases when the accountant reaches its limit. Noise is not a substitute for authentication or secure raw-state handling.

Invalidating evidence includes unbounded contributions, exact node sums in logs, resampled node noise, budget resets without population separation, empirical noise variance inconsistent with calibration, missing late-event policy, $delta$ larger than an acceptable failure probability, or decisions whose tolerance is smaller than the measured error.

flowchart TD
 A[Define event or user adjacency] --> B[Bound and validate contributions]
 B --> C[Choose horizon release cadence epsilon delta]
 C --> D[Select tree mechanism and accountant]
 D --> E[Simulate privacy and utility]
 E --> F{Risk and error acceptable?}
 F -->|yes| G[Deploy protected state and ledger]
 F -->|no| H[Reduce releases increase aggregation or reject]
 G --> I[Monitor budget noise and downstream harm]
 I --> J{Assumptions unchanged?}
 J -->|yes| I
 J -->|no| H
 classDef navy fill:#17365D,color:#fff,stroke:#17365D;
 classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
 classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
 classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
 class A,B,C navy;
 class D,E,G purple;
 class F,I teal;
 class H,J crimson;

Calibrate and Audit Continual-Observation Noise

An audit must reproduce both sensitivity and transcript reconstruction. Sampling noise alone does not prove privacy, while a symbolic privacy proof alone does not establish operational utility.