js-streaming-private-quantile-adaptive-adversary-20261009

Answer

Done. The solution is written to ~/SOLUTION.md, and the embedded code was extracted and re-run from scratch (33/33 passing) to prove it's self-contained.

Diagnosis (root causes)

The spec secretly requires six fixes that a naive "quantile sketch + Laplace noise" fails:

1. Adaptive-composition fallacy — per-query ε is unsound when the analyst picks later queries from earlier outputs. You need a path-independent accountant over releases.
2. Non-mergeable summaries — exact buffers, t-digests, and GK sketches don't merge with a preserved error bound; shard merges must recompute guarantees.
3. Unbounded memory — storing events violates the bound.
4. Adversarial ties — distinct/continuous quantile logic breaks when mass concentrates on one value.
5. Deletes/late events — append-only sketches can't retract; dropped mass must be bounded and reported.
6. Calibration + monotonicity — ad-hoc noise has no budget, and noisy CDFs are non-monotone.

Fix

A zero-dependency solution.js with five layers:

• DyadicHistogram — fixed 2^levels bucket grid, signed float counts, exact additive merge, O(1) ingest.
• isotonicPAV — deterministic monotone projection of the noisy CDF (DP post-processing).
• RDPAccountant — Gaussian Rényi-DP; mergeParallel (ε=max, disjoint shards) vs mergeSequential (ε=sum, overlapping users); inverts to calibrate σ with sigmaForTotalBudget.
• PrivateQuantileSketch — cumulative noisy histogram; returns value, rankError, rankErrorFraction, epsUsed, delta; recomputes variance after merges.
• LatenessAwareEstimator — window W with delayed release; in-window deletes cancel exactly, out-of-window mass becomes reported residual.

Guarantee: (ε,δ)-DP with ε = min_α[α·perUnit + ln(1/δ)/(α−1)], and w.p. ≥1−β, |C(v̂)−p| ≤ (t+R)/N + 2/B where t = √(2Bv·ln(2B/β)).

Verification (node verify.js)

================ RESULT: 33 passed, 0 failed ================

Covers: exact shard merge + bounded memory, ties, deletions, σ-calibration to target ε, discrete-vs-continuous RDP optimum, empirical rank-error coverage over 300 trials, parallel/sequential merge semantics with additive noise variance, late/delete residual accounting, path-independent budget under an adaptive adversary, and a 200k-event jittered stream with no in-window drops.