💻 computer science

Verifying Exact Samplers for Continuous Distributions with a Discrete Program Logic

This paper introduces Continuous-Eris, a higher-order separation logic implemented in the Rocq proof assistant, to formally verify the correctness of exact sampling algorithms for continuous distributions like Gaussian and Laplace, addressing the security and accuracy limitations of floating-point approximations.

Original authors: Markus de Medeiros, Puming Liu, Kwing Hei Li, Alejandro Aguirre, Lars Birkedal, Joseph Tassarotti

Published 2026-05-14

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Markus de Medeiros, Puming Liu, Kwing Hei Li, Alejandro Aguirre, Lars Birkedal, Joseph Tassarotti

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to bake a cake, but instead of using a standard measuring cup, you have to measure every ingredient by pouring water from a bucket into a tiny cup, one drop at a time. If you stop after 100 drops, you have an approximation of the amount. If you stop after 1,000, it's closer. But if you stop at any point, you've technically made a tiny mistake because you didn't get the exact amount.

In the world of computer science, this is exactly what happens when computers handle real numbers (like 3.14159...). They use "floating-point numbers," which are like those 100-drop approximations. For most things, this is fine. But for sensitive tasks—like protecting private data in medical studies or financial records—those tiny "rounding errors" can add up to big security leaks.

This paper introduces a new way to fix this problem. The authors built a tool called Continuous-Eris that helps programmers prove their code is doing exact sampling from continuous distributions (like picking a perfectly random number between 0 and 1) without ever making a rounding error.

Here is how they did it, using some creative analogies:

1. The Problem: The "Lazy" Chef

Usually, to get a random number between 0 and 1, a computer might try to generate the whole infinite sequence of digits (0.101101...) all at once. But that's impossible; you can't write down an infinite list.

Instead, the authors use a "lazy" approach. Imagine a chef who only peels an onion layer by layer, but only when you ask for it.

The Code: The program U (Uniform) doesn't generate the whole number immediately. It just creates an empty list.
The Request: When you ask for the first few digits (using a function called GetBits), the program peels one layer (generates one random bit, 0 or 1).
The Magic: If you ask for more digits later, it peels another layer. It builds the number bit-by-bit, only as fast as you need it. This ensures you never have to deal with an infinite list, but you can get as precise an answer as you want.

2. The Challenge: Proving the Chef is Honest

The hard part isn't writing the code; it's proving that the lazy chef is actually picking numbers fairly.

If the chef peels a layer, is it truly random?
If you ask for 10 layers, is the resulting number truly distributed across the whole range?
How do you prove this when the chef hasn't even finished peeling the onion yet?

Previous tools could only prove this for simple, discrete things (like rolling a die). They couldn't handle the "infinite onion" of continuous numbers, especially when the code was complex, used memory, and changed values on the fly.

3. The Solution: The "Infinite Tape" and "Time Receipts"

To solve this, the authors invented a new logic system (a set of rules for proving code correctness) that combines three clever tricks:

A. The "Pre-Drawn Tape" (Pre-sampling)

Imagine you are a magician. To prove your trick works, you secretly write down the entire sequence of cards you will pull from the deck before you even start the show.
In their logic, they use a "tape" that acts like this pre-written list. Even though the computer generates bits one by one, the proof assumes the whole infinite sequence of bits is already written down on a magical tape. This lets the mathematician reason about the "whole number" even though the program only sees "one bit at a time."

B. The "Time Receipt" (The Budget)

Here is the tricky part: A tape can't actually be infinite in a computer proof.
So, they use a concept called Time Receipts. Think of this as a "step budget."

The logic says: "We are only going to watch the program run for 100 steps."
Because the program only takes one step to generate one bit, if we only watch for 100 steps, we only need to know the first 100 bits on our magical tape.
The "Time Receipt" is a token that says, "I have 100 steps left." Every time the program takes a step, you spend a receipt.
This allows them to pretend the tape is infinite, because for any specific moment in the proof, they only need a finite number of bits, and they have a "receipt" to pay for them.

C. The "Error Credit" (The Safety Net)

Finally, they use Error Credits. Imagine you have a budget of "mistakes" you are allowed to make.

If you want to prove the program is 99.9% correct, you spend 0.1% of your credit.
The authors developed a way to "spend" these credits to prove that the probability of the program behaving incorrectly is vanishingly small.
They figured out how to turn these discrete "mistake budgets" into a smooth, continuous math tool (using integrals) so they could prove the code works for the whole range of real numbers, not just specific points.

4. What They Actually Proved

Using this new system, the authors didn't just talk about theory; they built and verified actual code for:

Uniform Distribution: Picking a random number between 0 and 1.
Gaussian (Bell Curve): Picking a number that clusters around an average (like human heights).
Laplace Distribution: A specific type of noise used in Differential Privacy (a method to share data without revealing individual secrets).

They proved that their code for these distributions is mathematically exact. If you use their code, you aren't getting a "close enough" floating-point number; you are getting a number that is guaranteed to follow the perfect mathematical rules, bit by bit.

The Bottom Line

The paper presents a new "rulebook" (Continuous-Eris) that allows programmers to write complex, lazy, exact sampling code and prove it is 100% correct. They did this by combining a "magical pre-written tape" with a "step-budget" system, allowing them to reason about infinite possibilities using finite, manageable steps. This is a major step forward for ensuring that privacy-preserving algorithms and other critical systems don't have hidden mathematical bugs caused by rounding errors.

Technical Summary: Verifying Exact Samplers for Continuous Distributions with a Discrete Program Logic

Problem Statement

Most implementations of sampling algorithms for continuous probability distributions rely on floating-point arithmetic. While acceptable for many applications, floating-point operations introduce round-off errors that are difficult to analyze and can lead to critical security vulnerabilities, particularly in differential privacy where algorithms are often formally developed under the assumption of exact arithmetic.

An alternative is to use exact sampling algorithms based on computable reals, which can lazily generate digits of a continuous sample to arbitrary precision. However, these algorithms are intricate. They require a combination of semantically challenging language features, including probabilistic choice, higher-order functions, and dynamically allocated mutable state. Existing program logics for probabilistic verification are insufficient for this task: prior work either restricts reasoning to discrete distributions or assumes the existence of primitives for sampling from continuous distributions (often relying on non-computable real arithmetic). Consequently, there is a lack of formal techniques to verify the correctness of computable, exact samplers for continuous distributions that operate within a discrete, stateful programming model.

Methodology

The authors present Continuous-Eris, a higher-order separation logic designed to verify the correctness of exact sampling algorithms for computable distributions. Continuous-Eris extends Eris (a logic for verifying approximate correctness of discrete probabilistic programs) and is built upon the Iris separation logic framework.

The core methodology relies on bridging the gap between discrete and continuous reasoning through three key logical ingredients:

Error Credits: Borrowed from Eris, these are separation logic resources $E(r)$ representing an upper bound on the probability of a specification failing. They allow for modular reasoning about probabilistic programs by "spending" credits to exclude low-probability error events.
Time Receipts: Adapted from Mével et al., these are used to internalize the partial correctness of the logic. By tracking the number of execution steps remaining ($StepsLeft(k)$), the logic can reason about finite prefixes of potentially infinite executions. This is crucial because exact samplers often involve lazy evaluation where an infinite sequence of bits is never fully generated.
Pre-sampling Tapes: Adapted from Clutch, these allow the proof to pre-determine the outcomes of future random sampling commands. While standard tapes are finite, the authors combine them with time receipts to simulate infinite pre-sampling tapes. This mechanism allows the logic to condition error credits on a specific real number $r$ (represented by an infinite bitstring) even though the program only generates a finite number of bits during any finite execution.

Theoretical Foundation

The logic generalizes the discrete correctness specification of Marionneau et al. to the continuous setting. Instead of characterizing a sampler by a discrete probability mass function, Continuous-Eris characterizes a sampler by a Riemann integral over a probability density function.

The central specification pattern for a sampler $U$ generating a uniform real in $[0, 1]$ is:
$\forall F \in PC([0, 1]), \quad \left\{ E\left(\int_0^1 F(x) dx\right) \right\} U() \{ v. \exists r. E(F(r)) * IsReal\ v\ r \}$
Here, $F$ is a bounded, piecewise-continuous function. The logic allows conditioning credits on the sampled value $r$ as if it were drawn uniformly, provided the expected value of the credits is preserved. The soundness of this approach relies on the fact that a Riemann sum (derived from finite pre-sampling) can approximate the integral arbitrarily closely, with the discretization error paid for by "thin-air" error credits.

Key Contributions

Continuous-Eris Logic: A novel program logic that combines error credits, time receipts, and pre-sampling tapes to verify computable continuous sampling algorithms. It supports higher-order functions, mutable state, and dynamic allocation.
Formal Verification of Exact Samplers: The authors provide formally verified implementations of exact samplers for:
- The Uniform distribution over $[0, 1]$ .
- The Gaussian (Normal) distribution.
- The Laplace distribution.
  These implementations are based on algorithms by Karney and utilize lazy bit-list representations.
Verified Constructive Real Arithmetic: A library for exact real arithmetic (an adaptation of CReal) verified within Continuous-Eris. This library supports operations (addition, negation, scaling, comparison) on lazy real numbers, enabling the construction of complex distributions from simpler ones.
Accuracy Bound for Differential Privacy: A formal proof that the verified Laplace sampler satisfies a specific accuracy bound used in differential privacy literature. This demonstrates that the sampler's output adheres to the theoretical guarantees required for privacy-preserving mechanisms without relying on floating-point approximations.
Mechanization: All results are mechanized in the Rocq proof assistant (formerly Coq), building on the Iris framework and the Coquelicot real analysis library.

Results

The paper demonstrates the utility of Continuous-Eris through the verification of the MaxU2 program (computing the maximum of two uniform samples) and the full Karney Gaussian sampler.

MaxU2: The authors prove that the program returns a value distributed with probability density $\mu_{max}(x) = 2x$ . The proof involves iterated integrals and Löb induction to handle recursive bit comparisons.
Gaussian Sampler: The verification follows a modular structure, verifying subroutines for Bernoulli trials, integer parts, and rejection sampling loops. The proof establishes that the sampler generates values with the correct Gaussian density.
Laplace Sampler: The authors verify a sampler for the Laplace distribution and derive the tail bound $P[|L_{\epsilon, \mu} - \mu| > \frac{\log(1/\beta)}{\epsilon}] \leq \beta$ directly from the logic, without adding it as a primitive axiom.

Significance and Claims

The paper claims to fill a critical gap in formal verification by providing the first technique capable of verifying exact, computable samplers for continuous distributions that utilize mutable state and higher-order functions.

Correctness without Approximation: Unlike prior work that assumes continuous primitives or uses floating-point arithmetic, Continuous-Eris verifies algorithms that generate exact samples (to arbitrary precision) using only discrete primitives (Bernoulli trials).
Handling Complexity: The logic successfully manages the semantic challenges of combining randomness, mutable state, and higher-order functions, which are typically difficult to reason about denotationally.
Practical Relevance: By verifying the Laplace sampler and its accuracy bounds, the work provides a foundation for building differentially private systems with rigorous guarantees against floating-point errors.
Modesty: The authors acknowledge limitations. The current approach relies on Riemann integration, requiring credit distribution functions to be piecewise continuous. This prevents reasoning about distributions with uncountable discontinuities (e.g., avoiding all rational points). Additionally, the paper focuses on partial correctness; proving almost-sure termination for these samplers is left to future work or other logics like Total Eris.

In summary, Continuous-Eris offers a rigorous, mechanized framework for verifying that complex, stateful programs correctly implement exact sampling from continuous distributions, bridging the gap between theoretical computable analysis and practical program verification.