💻 computer science

Contextual Refinement of Higher-Order Concurrent Probabilistic Programs (Extended Version)

This paper introduces Foxtrot, the first higher-order separation logic that enables the mechanized proof of contextual refinement for higher-order concurrent probabilistic programs with local state by integrating advanced concurrency and probabilistic reasoning principles, including a novel reliance on the axiom of choice within the Iris framework.

Original authors: Kwing Hei Li, Alejandro Aguirre, Joseph Tassarotti, Lars Birkedal

Published 2026-04-20

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Kwing Hei Li, Alejandro Aguirre, Joseph Tassarotti, Lars Birkedal

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

The Big Picture: A High-Stakes Game of "Copycat"

Imagine you are a quality control inspector for a software factory. You have two machines:

Machine A (The Implementation): A complex, messy machine that uses random dice rolls and has multiple workers (threads) running at the same time, sometimes getting in each other's way.
Machine B (The Specification): A simple, perfect machine that does exactly what the customer wants to happen, with no mess or randomness.

Your job is to prove that Machine A is safe to use. You need to show that no matter how you try to trick Machine A (by changing the order of workers or the dice rolls), it will never produce a result that Machine B couldn't also produce. In computer science, this is called proving Contextual Refinement.

The problem? When you mix randomness (dice rolls) with concurrency (multiple workers racing), the math gets incredibly messy. It's like trying to predict the outcome of a card game where the deck is being shuffled by three different people simultaneously, and the cards themselves are slightly sticky.

Enter Foxtrot.

What is Foxtrot?

Foxtrot is a new set of rules (a "logic") invented by the authors to help inspectors prove that Machine A is just as good as Machine B, even when things are chaotic. Think of Foxtrot as a super-powered magnifying glass that can see through the chaos of randomness and multitasking to find the hidden order.

Before Foxtrot, we had tools to check simple programs or programs with just randomness, or just multitasking. But we didn't have a tool that could handle all three at once:

High-Order: Functions that can pass other functions around (like a manager hiring a subcontractor who hires another subcontractor).
Concurrency: Multiple threads running at once.
Probability: Randomness and chance.

The Three Magic Tricks of Foxtrot

To solve this messy problem, Foxtrot uses three clever "tricks" (reasoning principles). Here is how they work, using analogies:

1. The "Presampling Tape" (The Crystal Ball)

Imagine you are trying to prove that two people rolling dice will get the same result.

The Problem: In a concurrent program, Thread A rolls a die, then Thread B rolls a die. You can't just say "Thread A's roll equals Thread B's roll" because they happen at different times.
The Foxtrot Trick: Foxtrot introduces a "Presampling Tape." Think of this as a magical roll of film. Before the game even starts, Foxtrot secretly writes down all the dice rolls that will happen on this tape.
How it helps: When Thread A needs a number, Foxtrot says, "Don't roll yet! Just look at the tape and take the next number." This allows the inspector to line up the dice rolls from the messy machine (Machine A) with the perfect machine (Machine B) before they actually happen, making it easy to compare them.

2. The "Error Credit" (The Budget for Mistakes)

Sometimes, you can't prove two machines are exactly the same. Maybe Machine A has a 0.0001% chance of doing something weird that Machine B never does.

The Problem: In strict math, even a tiny chance of failure means the proof fails.
The Foxtrot Trick: Foxtrot gives you "Error Credits." Imagine you have a budget of "mistakes" you are allowed to make. You can say, "I will prove these machines are the same, provided I am allowed a tiny error budget of 0.0001."
The Magic: Foxtrot has a rule called "Induction by Error Amplification." It's like a magic trick where you can take a tiny error budget, use it to prove a step, and then get more error budget back. If you can keep doing this forever, you prove that the total error is effectively zero. It's like proving you can walk across a tightrope by taking steps so small that the wobble disappears.

3. The "Fragmented Coupling" (The Rejection Sampler)

Some programs work by "rejection sampling." Imagine you want a number between 1 and 10, but you only have a die that rolls 1 to 100. You roll the die; if it's 1-10, you keep it. If it's 11-100, you throw it away and roll again.

The Problem: This creates a loop. You might roll 50 times before you get a "keep." How do you prove this loop is safe?
The Foxtrot Trick: Foxtrot uses "Fragmented Coupling." Instead of trying to match every single roll, it matches the successful rolls. It says, "If the messy machine accepts a number, the perfect machine must also accept a number." If the messy machine rejects a number (rolls 11-100), the perfect machine doesn't have to do anything. It's like a bouncer at a club: if the messy machine lets someone in, the perfect club must also let them in. If the messy machine turns someone away, the perfect club doesn't care.

Why is this a Big Deal? (The "Axiom of Choice" Twist)

The paper mentions a very technical challenge: proving that Foxtrot works requires using a version of the Axiom of Choice.

The Analogy:
Imagine you have a infinite number of boxes, and inside each box is a different way to organize a team of workers. To prove your logic works, you have to pick one specific way to organize the workers for every possible scenario.

In normal math, you can just say "Pick one."
In the world of computer logic (specifically the Iris framework used here), you usually can't just "pick" things arbitrarily because it breaks the rules of the system.
The Breakthrough: The authors figured out a way to use this "picking" rule (Axiom of Choice) safely within their specific system. This is like finding a secret backdoor that lets you organize the infinite boxes without breaking the laws of physics. This is what makes Foxtrot's underlying math so strong and new.

Real-World Examples They Tested

The authors didn't just write theory; they tested Foxtrot on real-world problems:

The Adversarial Coin: A coin flipper that is being hacked by an enemy who can change the coin's weight while it's being flipped. Foxtrot proved that even with the hacker, the coin still behaves like a fair coin.
Sodium (Cryptography): A famous security library. They proved that a specific function used to generate random numbers for encryption is safe to use, even if other parts of the program are running at the same time. This is crucial because if random number generation fails, your encryption fails.

Summary

Foxtrot is a new, powerful tool for software engineers and mathematicians. It allows them to prove that complex, chaotic, random, multi-threaded programs are safe and correct.

Old way: "I hope this works, but I can't prove it because the math is too hard."
Foxtrot way: "I can prove it works, even with the chaos, by using magical tapes to predict the future, a budget for tiny mistakes, and a way to match up the good outcomes."

All of this has been checked by a computer (the Rocq proof assistant), so we know the rules are 100% solid. It's a giant leap forward for making secure, reliable software in a world where randomness and multitasking are everywhere.

1. Problem Statement

The paper addresses the challenge of formally verifying contextual refinement and equivalence in higher-order concurrent probabilistic programs.

The Gap: While formal methods exist for reasoning about concurrency (e.g., Concurrent Separation Logic) and probabilistic programs (e.g., probabilistic couplings) separately, combining them is notoriously difficult. Concurrency introduces non-determinism (scheduler choices), while probability introduces stochastic branching. These two features do not compose straightforwardly in semantic models.
Specific Challenges:
- Higher-Order & Local State: Programs can pass functions as arguments and manipulate dynamically allocated local state (references), complicating relational reasoning.
- Scheduler Interaction: In concurrent probabilistic programs, the scheduler decides which thread runs next. Proving refinement requires showing that for every scheduler of the implementation, there exists a scheduler for the specification such that the implementation's termination probability is bounded by the specification's.
- Complex Couplings: Reasoning about joint probability distributions arising from independent random samples in different threads (e.g., combining two random bits into one byte) or rejection sampling loops requires advanced coupling techniques that were previously unavailable in a concurrent, higher-order setting.
Goal: To provide a logic capable of proving that a complex concurrent probabilistic implementation behaves "at least as well" (in terms of termination probability and observable behavior) as a simpler specification, even when the implementation uses adversarial or unknown code.

2. Methodology: The Foxtrot Logic

The authors present Foxtrot, the first higher-order separation logic designed specifically for this domain. It is built on top of the Iris framework (a logic for reasoning about concurrent programs) and the Rocq (formerly Coq) proof assistant.

Core Components

Language (ConcRandML): The logic targets a higher-order ML-style language featuring:
- Discrete probabilistic sampling (rand N).
- Unstructured concurrency via fork.
- Higher-order dynamically allocated local state (references).
- Atomic operations (e.g., fetch-and-add).
Logical Framework:
- Relational Hoare Triples: The logic uses triples of the form $\{P\} e \{Q\}$ , but defined relationally to compare an implementation $e$ against a specification $e'$ .
- Logical Relations: Contextual refinement is proven via a binary logical relation ( $\Delta \models e \preceq e' : \tau$ ), which is defined inductively on types. This relation is sound with respect to contextual refinement (quantifying over all contexts).
- Adequacy Theorem: The logic proves that if a Hoare triple holds in Foxtrot, the upper termination probability of the implementation is bounded by that of the specification.
Key Reasoning Principles:
- Concurrency Features: Inherits standard Iris features like invariants, ghost resources, and framing to handle shared state and thread synchronization.
- Probabilistic Coupling: Uses approximate probabilistic couplings to relate the distributions of two programs.
- Presampling Tapes: Adapted from the Clutch logic, these allow the logic to "pre-sample" random values onto virtual tapes during the proof. This enables coupling multiple random samplings in different threads (left-hand side) with a single sampling (right-hand side) by treating the tapes as a shared resource.
- Fragmented Couplings: Adapted from Approxis, this technique handles rejection sampling by splitting the coupling into "accepted" and "rejected" cases.
- Error Credits & Induction by Error Amplification: Adapted from Eris and Approxis, this uses a resource $E(\epsilon)$ representing an allowable error probability. The logic allows proving equivalence up to an error $\epsilon$ , then using an induction principle to show that if the error can be amplified by a factor $k > 1$ in a loop, the total error can be made arbitrarily small (approaching 0).
The "Right-Hand Side" Challenge:
- A major technical hurdle is that in concurrent settings, one cannot simply "presample" on the specification (right-hand side) side because the scheduler might depend on future random outcomes, violating the operational semantics.
- Solution: Foxtrot restricts presampling to the implementation side (left) and uses parallel composition rules to decompose the specification side into multiple threads to match the implementation's structure.
Semantic Model & Soundness:
- The model relies on Full-Information Schedulers (FIsches), a specialized internal scheduler type that tracks execution history.
- Axiom of Choice: A critical novelty is the use of a version of the Axiom of Choice within the Iris logic. To prove soundness, the authors must construct a single scheduler for the specification that "pieces together" a family of schedulers for sub-expressions. Since the family of possible outcomes is countably infinite, constructing this scheduler requires the Axiom of Choice (restricted to meta-level types to avoid logical contradictions in the intuitionistic setting).

3. Key Contributions

First Higher-Order Logic: Foxtrot is the first separation logic to support contextual refinement for programs combining higher-order functions, local state, concurrency, and probability.
Advanced Coupling Rules: It introduces a rich set of rules for complex scenarios:
- Batch Sampling: Coupling multiple concurrent random samples into a single distribution.
- Rejection Sampling: Handling unbounded loops where samples are accepted/rejected based on conditions.
- Adversarial Code: Reasoning about programs interacting with unknown, potentially malicious concurrent threads.
Mechanization: All results, including the semantic model and soundness proofs, are mechanized in Rocq using the Iris framework and the Coquelicot real analysis library.
Novelty in Model Construction: The use of the Axiom of Choice to compose families of schedulers is a significant departure from previous Iris-based logics, which typically constructed a single trace.

4. Results and Case Studies

The authors demonstrate the expressiveness of Foxtrot through several challenging examples:

Adversarial von Neumann Coin: Proving that a biased coin simulation remains fair even when the bias is stored in shared memory and modified by an adversarial thread. This required unary logical relations to reason about the unknown adversary.
Sodium randombytes_uniform: Verifying a real-world cryptographic function from the Sodium library. The implementation uses rejection sampling and non-atomic reads, yet Foxtrot proves it is contextually equivalent to a direct uniform sampler, establishing its thread-safety and correctness.
Batch Sampling: Proving that generating two independent random numbers in parallel and combining them is equivalent to generating a single larger random number.
Rejection Sampling: Verifying that a loop-based rejection sampler produces a uniform distribution, using fragmented couplings and error amplification.

5. Significance

Bridging a Critical Gap: This work bridges the gap between concurrency and probabilistic verification, enabling the formal verification of modern cryptographic protocols and randomized distributed algorithms that rely on complex interactions between threads and randomness.
Scalability: By demonstrating verification of real-world code (Sodium) and complex patterns (adversarial threads, rejection loops), Foxtrot moves beyond toy examples to practical program verification.
Theoretical Advancement: The successful integration of the Axiom of Choice into the Iris model to handle scheduler composition opens new avenues for reasoning about non-determinism in probabilistic systems.
Foundation for Future Work: The paper sets the stage for verifying security properties of distributed systems and extends the applicability of separation logic to the full spectrum of modern programming language features.

In summary, Foxtrot represents a major leap forward in program verification, providing the first robust, mechanized framework for proving that complex, concurrent, randomized programs behave correctly relative to their specifications.