Source-linked AI summary
Detection and Resolution of Periodic Artifacts in OpenDP's Discrete Laplace Sampler
Cesare Gerolimetto Fabrello, Valeria Rossi, Alberto Trombetta, Massimo Caccia
TL;DR
Finite-precision implementations can exhibit numerical precision issues even when the underlying mathematical foundations are well understood. The paper diagnoses systematic artifacts in OpenDP’s discrete Laplace sampler and proposes an exact-rational alternative. The corrected implementation eliminates the artifacts at the tested precision level.
Problem
Finite-precision hardware introduces subtle challenges in realizing sampling procedures whose mathematical foundations are well understood.
Source: §I · p. 1Method
Results
The alternative implementation eliminates the artifacts at the tested precision level, and the reported privacy-loss analysis indicates that both corrections restore the e±ε bound.
Source: §X · p. 7Takeaways & Limitations
The work emphasizes rigorous statistical validation beyond unit tests for differential privacy implementations.
Source: §X · p. 8
Abstract
from arXiv · showhide
Differential privacy implementations rely on precise sampling from noise distributions to provide formal privacy guarantees. We report the discovery of systematic artifacts in OpenDP's discrete Laplace sampler that manifest as periodic distortions in the output distribution. Through systematic testing, we trace these artifacts to a faulty implementation in the rational arithmetic library used by the bernoulli_exp1 function, a low-level primitive that implements sampling from Bernoulli(e^(-x)) distributions. We present a diagnostic methodology that isolates the faulty component in the nested sampling hierarchy and propose an alternative implementation based on exact rational arithmetic that eliminates the artifacts. Statistical validation with 10^6 samples confirms that the corrected sampler produces outputs indistinguishable from the theoretical distribution at the tested precision level.
I. INTRODUCTION
The paper reports periodic artifacts in OpenDP’s discrete Laplace sampler and connects the broader issue to precision challenges in finite-precision implementations. It introduces a diagnostic approach and describes the library and experimental checks used in the investigation.
I. INTRODUCTION
- The work extends concerns about finite-precision sampling to exact sampling implementations, where numerical precision issues can appear as systematic artifacts.The paper notes that floating-point arithmetic can leak information through least significant bits.Source: §I · p. 1
II. OPENDP LIBRARY
- OpenDP implements the discrete Laplace mechanism following CKS20, using nested primitives with formal correctness guarantees.The paper cautions that implementation details can still introduce unexpected behavior.Source: §I · p. 1
I. INTRODUCTION
- The initial sampler plot shows periodic distortions in the discrete Laplace output, with insets zooming in and error bars marking 1σ confidence intervals.The paper’s contribution includes a diagnostic method and an exact-rational alternative intended to eliminate the artifacts.Source: Figure 1 · p. 1, §I · p. 1
A. Experimental Setup
- Base entropy-source checks reported χ2_red ≈1 and p > 0.4, supporting the conclusion that the entropy source operated correctly.The experimental setup also included millions of iterations across parameter and randomness-source combinations.Source: A. Experimental Setup · pp. 1–2
B. Empirical Distribution Reconstruction
The reconstructed output has symmetric, scale-dependent periodic artifacts that persist across entropy sources. The implementation hierarchy includes exponential Bernoulli primitives, and tests show failures in the exponential and fast geometric samplers.
B. Empirical Distribution Reconstruction
- The reconstructed Laplace histogram shows evenly spaced artifacts; their symmetry and spacing depend on the distribution center and Laplace scale, and they persist across entropy sources.Larger bins smooth the artifacts and can obscure them.Source: B. Empirical Distribution Reconstruction · p. 2
IV. IMPLEMENTATION STRUCTURE
- The implementation hierarchy runs from the discrete Laplace sampler through geometric and exponential Bernoulli samplers to the rational Bernoulli and uniform-integer primitives.The fast geometric sampler calls bernoulli_exp, which invokes bernoulli_exp1; the rational Bernoulli sampler is among the lower-level primitives.Source: §IV · pp. 2–3
- Both exponential Bernoulli samplers deviate from their theoretical model, with χ2 = 128 and p = 0 for each.The figure compares bernoulli_exp and bernoulli_exp1; the latter is restricted to x ∈ [0, 1] and uses an alternating Taylor series.Source: Figure 4 · p. 3, §IV · p. 3
- The fast geometric sampler fails goodness-of-fit testing and shows periodic artifacts, while the slow implementation passes.The fast sampler’s mean z is 3.99 (p = 6.6 × 10−5; χ2 = 1.9 × 10^3, p = 0), versus mean z = 0.96 (p = 0.34; χ2 = 15, p = 0.26) for the slow sampler.Source: Figure 5 · p. 3
V. DIAGNOSTIC METHODOLOGY
The diagnostic method traces representative outputs through the sampler’s call chain and tests each primitive against its theoretical distribution. Because the traced values share an entropy source, the earliest deviation identifies where a discrepancy enters and how it propagates downstream.
V. DIAGNOSTIC METHODOLOGY
- A traced version records representative outputs from each primitive for every generated discrete Laplace sample.The diagnostic row includes outputs from the entropy draw, Bernoulli and geometric samplers, and the final sample.Source: §V · p. 3
- The method applies χ2 and z-tests to each recorded column against its corresponding theoretical distribution, using cascades generated from the same entropy source.The authors iterate the process N = 10^6 times.Source: §V · p. 3
- A deviation first visible in one primitive’s column marks the earliest faulty step, while downstream columns reveal its propagation through the sampling pipeline.Because the columns share the same random bytes, the discrepancy is attributed to a deterministic transformation rather than a change in entropy source.Source: §V · p. 3
VI. LAYER-BY-LAYER ANALYSIS
Layer-by-layer tests confirm that uniform sampling works and identify failures in the exponential Bernoulli samplers. The shared failure pattern points to sample_bernoulli_exp1 as the likely fault location.
A. Uniform Sampling
- χ2_red ≈ 1, with p = 0.433 for uniform bit sampling and p = 0.654 for thresholded uniform sampling, supports conformity to the uniform model.The authors conclude that the entropy source and uniform integer sampling layer operate correctly.Source: A. Uniform Sampling · pp. 3–4
B. Bernoulli Samplers
- The conformity checks use χ2 goodness-of-fit and a z-test comparing the empirical success probability with its theoretical value.The supplied passage describes agreement as |z| < 3, corresponding to 99% confidence.Source: B. Bernoulli Samplers · p. 4
- The standard Bernoulli and rational Bernoulli pass both tests, with z = 0.58 and p = 0.56 for the former and z = 0.66 and p = 0.51 for the latter.Both z-values are within 1σ of the expected value, with correspondingly high p-values.Source: B. Bernoulli Samplers · p. 4
- z = 11.30, p ≈ 0, and χ2 = 127.7 for bernoulli_exp1; bernoulli_exp shows identical failure statistics.Because calls proceed from bernoulli_exp through bernoulli_exp1 to bernoulli_rational, the authors identify bernoulli_exp1 as the likely failing function.Source: B. Bernoulli Samplers · p. 4
C. Geometric Samplers
The geometric samplers diverge: the slow sampler appears correct, while the fast sampler shows artifacts and fails statistical tests. The passages attribute this contrast to how each uses the exponential Bernoulli sampler.
C. Geometric Samplers
- The slow geometric sampler appears correct, but the fast geometric sampler exhibits artifacts like those in the final Laplacian output and fails statistical tests.The samplers are tested against the geometric distribution.Source: C. Geometric Samplers · p. 4
- At x = 1, the slow sampler uses only one Bernoulli with p = e^-1, for which the underlying bias is negligible.The passage says the slow sampler therefore returns a correct result despite depending on the faulty bernoulli_exp.Source: C. Geometric Samplers · p. 4
- The fast sampler repeatedly draws from coins with probabilities e^-u/b, over-selecting some samples and under-selecting others and distorting the geometric distribution.Here x = 1/b for the fast sampler, compared with x = 1 for the slow sampler.Source: C. Geometric Samplers · p. 4
D. Final Laplace Distribution
The discrete Laplace output exhibits systematic artifacts despite a well-centered mean; goodness-of-fit testing fails, and the analysis traces the problem to bernoulli_exp1.
D. Final Laplace Distribution
- Mean z = −0.68 with p = 0.49, but χ2 = 2.1 × 10^3 with p = 0 for the generated discrete Laplace distribution.The passage reports that the mean is well-centered while the distribution fails goodness-of-fit testing due to systematic deviations.Source: D. Final Laplace Distribution · p. 4
- The top-down analysis traces the visible output problem to the bernoulli_exp1 function.The passage says the proposed alternative changes this sampler while leaving the rest of the CKS20 construction untouched.Source: D. Final Laplace Distribution · p. 4
- The reported failure is distributional: the well-centered mean does not prevent the goodness-of-fit test from failing.The reported χ2 statistic is 2.1 × 10^3 with p = 0.Source: D. Final Laplace Distribution · p. 4
VII. ALTERNATIVE SAMPLING ALGORITHM
The alternative sampler uses an alternating Taylor series and exact rational arithmetic to sample Bernoulli(exp(−x)). It refines bounds until the uniform sample falls outside the undecided interval.
VII. ALTERNATIVE SAMPLING ALGORITHM
- The alternative implementation samples Bernoulli(exp(−x)) by iteratively refining partial sums of the Taylor series.It is based on Proposition 33 in CKS20 and an alternating-series Bernoulli sampler described in.Source: §VII · pp. 4–5
- A 128-bit uniform integer is interpreted as the rational u = U/2^128 and stored as arbitrary-precision numerator and denominator using dashu::RBig.This is the first step of the implementation.Source: §VII · p. 5
- Because the alternating series has decreasing terms, consecutive partial sums bracket the true value e^-x.One partial sum lies above and the other below the true value.Source: §VII · p. 5
- The algorithm returns True when u < L and False when u ≥ H; otherwise it computes another term until the bracket resolves the decision.It initializes Sprev = 1 and Scurr = 1 − x, then uses their minimum and maximum as L and H; Fig. 6 depicts the interval tightening.Source: §VII · p. 5, Figure 6 · p. 5
VIII. VALIDATION RESULTS
Replacing the original bernoulli_exp1 implementation resolved the observed sampling bias, and the improvement carried through the geometric samplers. Both Bernoulli samplers and both geometric samplers fit their theoretical distributions in the reported tests.
VIII. VALIDATION RESULTS
- After replacing bernoulli_exp1 with the Taylor-series implementation, the diagnostic pipeline found that all samples fit their theoretical distributions.Figure 7 reports consistent results for both bernoulli_exp1 and bernoulli_exp.Source: §VIII · p. 5, A. Bernoulli Samplers · p. 5
A. Bernoulli Samplers
- The corrected Bernoulli sampler yielded p̂ = 0.6651 versus pth = 0.6643, with z = 1.80 and p = 0.073; the original implementation had z ≈ 11 and p ≈ 0.The corrected result was within 2σ, and independent experiments with different parameter choices confirmed it.Source: A. Bernoulli Samplers · p. 5
B. Geometric Samplers
- The fast geometric sampler passed its goodness-of-fit test (χ2 = 145.5, p = 0.315), with empirical mean 9.507 versus theoretical 9.508 and variance 99.94 versus 99.92.The slow geometric sampler also passed (χ2 = 9.74, p = 0.715), and periodic artifacts were no longer visible.Source: B. Geometric Samplers · p. 5
C. Discrete Laplace Distribution
The corrected discrete Laplace sampler eliminates the periodic artifacts and produces samples statistically indistinguishable from theory at the tested precision. The discussion traces the artifacts to faulty rational division in dashu and describes the local fix used in OpenDP.
C. Discrete Laplace Distribution
- The corrected discrete Laplace distribution passed the goodness-of-fit test (χ2 = 275.4 on 276 degrees of freedom, p = 0.499), and its sample mean was statistically indistinguishable from zero (z = −1.22, p = 0.224).The periodic artifacts were eliminated, and the empirical variance was 199.90 versus a theoretical 199.83.Source: C. Discrete Laplace Distribution · p. 5, Figure 8 · p. 6
IX. DISCUSSION
- The artifacts were traced to a bug in dashu’s RBig / UBig operator, which computed the denominator of rational division incorrectly.For x = a/b divided by k, the buggy operator used (b/g) · k rather than b · (k/g), where g = gcd(a, k).Source: §IX · p. 5
- The incorrect probability at each coin flip biased outcomes according to k, and those errors accumulated through the geometric and discrete Laplace constructions.The dashu patch was not included in an official release; OpenDP instead computed b · (k/g) locally, preserving the CKS20 structure.Source: §IX · p. 5
- The patched implementation’s diagnostic pipeline found no visible artifacts in the final discrete Laplace distribution, and all samplers in the chain passed goodness-of-fit tests.Figure 8 also reports that the slow geometric, fast geometric, and discrete Laplace samplers pass their tests.Source: §IX · p. 6, Figure 8 · p. 6
A. Performance Benchmarking
The local fix costs nearly the same as the original sampler, while the Taylor-series alternative is slower. Empirical privacy-loss results show violations for the faulty sampler but not for either correction, although the paper does not quantify effective privacy loss rigorously.
A. Performance Benchmarking
- The original sampler took 14.68±0.01 µs per call, the Fixed sampler 15.08±0.01 µs, and the Taylor sampler 17.45±0.01 µs.The original and Fixed costs were within 2.7%; the Taylor sampler was 15.7% slower than Fixed.Source: A. Performance Benchmarking · p. 6
B. Implications on the Privacy Guarantee
- The faulty sampler’s empirical PLRV exceeded the theoretical bounds systematically, while the Taylor-series sampler and official fix stayed within bounds at 3σ across the histogram.The violating bins corresponded to outputs over- or undersampled by the faulty Laplace distribution.Source: B. Implications on the Privacy Guarantee · p. 7, Figure 9 · p. 7
- The privacy implication is presented as an empirical conjecture, not a rigorous PLRV analysis; quantifying effective privacy violation would require dedicated privacy-loss accounting.The paper does not attempt that accounting analysis.Source: B. Implications on the Privacy Guarantee · p. 7
X. CONCLUSION
The study identifies numerical precision issues in OpenDP’s bernoulli_exp1 primitive as the source of discrete Laplace artifacts and reports that corrections remove them at the tested precision level. The analysis also suggests the faulty sampler violates the e±ε bound, while both corrections restore it.
X. CONCLUSION
- Both corrections restore the e±ε bound that empirical privacy-loss analysis suggests is violated by the faulty sampler.The corrected implementation eliminates the artifacts at the tested precision level.Source: §X · p. 7
- Numerical precision issues in bernoulli_exp1 caused the systematic artifacts, which the alternative implementation eliminates at the tested precision level.The reported correction agrees with the official OpenDP patch released after disclosure.Source: §X · p. 7
- The work’s disclosure led OpenDP to integrate extended statistical testing throughout its library.The authors present rigorous statistical validation as important for differential privacy implementations and as a template for diagnosing hierarchical sampling issues.Source: §X · p. 8