💻 computer science

Elton: Urn Resources for Reasoning about Adversarial Probabilistic Programs

This paper introduces Elton, a higher-order separation logic featuring novel "urn resources" and delayed sampling mechanisms to formally verify error bounds and security properties in probabilistic programs containing unknown adversarial code, with all proofs mechanized in the Rocq proof assistant.

Original authors: Kwing Hei Li, Alejandro Aguirre, Philipp G. Haselwarter, Joseph Tassarotti, Lars Birkedal

Published 2026-07-16

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Kwing Hei Li, Alejandro Aguirre, Philipp G. Haselwarter, 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 Digital Detective and the Mystery of the Moving Target

Imagine you are trying to prove that a secret code is unbreakable. In the world of computer security, you aren't just testing the code against a static lock; you are testing it against a clever, invisible hacker who can try anything they want. This field is called formal verification, where mathematicians and computer scientists use rigorous logic to prove that software behaves exactly as intended, even when attacked by the worst possible enemy.

To do this, they often deal with probabilistic programs. Think of these not as standard calculators that always give the same answer, but as digital dice rollers. They make random choices—like flipping a coin or picking a number from a hat—to do things like encrypt messages or train artificial intelligence. The tricky part is that when you mix these random dice rolls with higher-order functions (which are like "functions that can take other functions as ingredients") and unknown code (the hacker's secret recipe), the math gets incredibly messy. You can't just look at one possible outcome; you have to reason about the entire distribution of possible outcomes to ensure the hacker can't cheat the odds.

The Problem: The "Guessing Game" That Breaks Logic

For years, researchers had tools to check these programs, but they hit a wall when the order of events got complicated. Imagine a game where a computer picks a secret number, and then a hacker tries to guess it. If the computer picks the number before the hacker makes their move, it's easy to prove the hacker can't win. But what if the hacker makes their move first, and then the computer picks the number based on what the hacker did?

In the real world, this is like a magician who asks you to pick a card, and then shuffles the deck to make sure that card is at the bottom. Standard logic tools struggled here. They could either handle the randomness or the complex interaction with the hacker, but not both at the same time. They couldn't say, "Wait, the secret number is still a mystery until the very end, so let's pretend it's a cloud of possibilities that we only clear up after the hacker is done." Without this ability, proving that a security system is safe against a smart, adaptive hacker was often impossible.

The Solution: Elton and the Magic Urns

Enter Elton, a new set of logical tools created by researchers Li, Aguirre, Haselwarter, Tassarotti, and Birkedal. They built a system that treats random numbers not as immediate results, but as delayed samplings.

Think of a standard random number generator like a vending machine that spits out a soda the moment you press a button. Elton changes the game: when you press the button, instead of a soda, you get a sealed, magical urn. You don't know what's inside yet. You can carry this urn around, pass it to the hacker, and even do math on the idea of the soda without ever opening the urn. The urn represents a "cloud" of all possible sodas that could be inside, with equal chances for each.

This is where the paper's main innovation shines: Urn Resources.
In Elton's logic, these urns are special objects that the computer can reason about. The researchers proved that you can perform calculations on these "clouds" of possibilities. For example, if you have an urn containing numbers 0 through 10, and you add 1 to it, the logic knows you now have an urn containing 1 through 11. You can even pass this "mathematical urn" to the hacker. The hacker can try to guess what's inside, but as long as they don't peek, the urn remains a cloud of possibilities.

The magic happens at the end of the program. Once the hacker has finished their moves, the logic allows you to resolve the urn. This is like finally opening the magical box to see what soda is actually inside. Because the researchers built a special "delayed sampling" system, they can prove that opening the urn at the very end gives you the exact same statistical results as if you had opened it immediately. This allows them to delay the decision of "what is the random number?" until after the hacker has made all their moves, making it possible to prove that the hacker couldn't have rigged the game.

What They Proved and What They Didn't

The authors didn't just suggest this might work; they proved it. They built Elton inside a powerful proof assistant called Rocq (formerly Coq), which acts like a super-strict math teacher that checks every single step of the logic to ensure there are no mistakes.

They used Elton to solve several tricky security puzzles that previous tools couldn't handle:

The Complicated Flip: They proved that even if a hacker tries to mess with a coin flip by calling functions back and forth, the coin remains perfectly fair (50/50), provided the hacker can't see the coin before they start.
The Interactive Guess: They showed that even if a hacker gets multiple chances to guess a secret number, the odds of them winning stay low, even if the hacker decides their next guess based on the previous ones.
Hash Functions: They verified that a "random oracle" (a perfect hash function) remains secure against an attacker who can query it many times, proving that finding a "collision" (two inputs that give the same output) is incredibly unlikely.
Discrete Logarithms: They provided the first formal proof for the security of the discrete logarithm problem against interactive attackers in the "generic group model," a standard way of testing cryptographic strength.

However, the paper is honest about its limits. The current version of Elton is designed specifically for uniform distributions—where every outcome in the urn is equally likely, like a fair die. The authors explicitly state that they cannot yet handle "biased" urns (like a weighted coin) or infinite possibilities without making significant changes to their math. They also note that while their method is powerful, it is complex and "convoluted," meaning it might be hard to scale up for every single type of random program in the future.

The Takeaway

Elton is a breakthrough in the specific corner of computer science dealing with adversarial probabilistic programs. It doesn't just say "this code is probably safe"; it provides a rigorous, machine-checked proof that the code is safe even when a clever, adaptive hacker tries to game the system. By introducing the concept of "delayed sampling" and "urn resources," the authors found a way to keep the random numbers in a "suspended state" until the very end, allowing them to outsmart the logic traps that previously stopped researchers from proving these security guarantees. It's a new set of glasses that lets us see the hidden fairness in a chaotic, random world.

Technical Summary: Elton: Urn Resources for Reasoning about Adversarial Probabilistic Programs

Problem Statement
Formal verification of probabilistic programs is critical for applications in randomized algorithms, machine learning, differential privacy, and cryptographic security. A specific challenge arises in cryptographic security, where one must establish properties that hold in the presence of arbitrary, unknown adversarial code. While higher-order separation logics have successfully modeled adversarial interactions in non-probabilistic settings, extending this to probabilistic programs is difficult. The core difficulty lies in reasoning about the combination of probabilistic choice, higher-order functions, and local state when the adversary's behavior is unknown.

Existing verification techniques face a trilemma:

Distributional Logics: These allow predicates to describe distributions of states (useful for invariants like "the value is uniformly distributed") but often lack the expressive features (higher-order functions, general references) needed to model complex adversarial interactions.
Lifting-Based Logics: These retain standard state-based predicates and lift them to distributions (easier to extend with higher-order features) but struggle to express distributional invariants, such as those required to prove that an adversary cannot bias a random bit.
Adversarial Reasoning: Existing approaches often fail to handle the simultaneous combination of unknown code, higher-order state, and distributional invariants. For instance, standard "prophecy variables" or "presampling tapes" (used in logics like Clutch) cannot soundly predict the output of an unknown adversary's code, nor can they easily handle cases where the order of random sampling and adversarial calls is swapped.

Methodology
The authors present Elton, a higher-order separation logic designed to reason about the robust safety of probabilistic programs in the presence of unknown adversarial code. Elton adopts a "mixed" approach, combining the structural benefits of lifting-based logics (built on the Iris framework) with novel mechanisms to capture distributional properties.

The methodology relies on two primary extensions:

Delayed Sampling (Operational Semantics):
Elton introduces a variant of the language (RandML) featuring a drand primitive. Unlike standard random sampling (rand), drand does not immediately resolve to a value. Instead, it creates a symbolic "urn" (a set of possible values) and returns an "urn label." Computations involving these labels produce "delayed values" (symbolic expressions). This allows the logic to defer the resolution of randomness until after the adversary has interacted with the system. The operational semantics ensures that these delayed computations can be soundly erased back to standard call-by-value probabilistic semantics.
Urn Resources (Logical Facilities):
At the logic level, Elton introduces urn resources (denoted $\iota \sim s$ ), which assert that a delayed sample variable $\iota$ is uniformly distributed over a set $s$ . This allows the logic to reason about the distribution of states without abandoning the expressive power of separation logic.
The proof process for urn resources follows a three-phase lifecycle:
- Creation: The drand primitive creates an urn resource.
- Resolution: The logic can "resolve" an urn resource, splitting it into subsets (e.g., avoiding a specific value guessed by an adversary) while distributing "error credits" (probabilistic bounds) accordingly. This is governed by rules like ht-resolve-partial.
- Promotion: Once the adversary's interaction is complete and the distributional properties are established, "delayed values" are promoted to concrete values using the promote update predicate ( $v \mapsto [R] w$ ), which asserts semantic equivalence under the current urn resources.

Elton inherits the error credits mechanism from its predecessor, Eris, to bound error probabilities, and utilizes logical relations to derive specifications for unknown, well-typed adversaries based solely on their types.

Key Contributions
The paper claims the following contributions:

First Probabilistic Higher-Order Separation Logic: Elton is the first logic capable of handling the combination of unknown adversarial code, higher-order local state, and distributional invariants simultaneously.
Novel Operational Semantics: A semantics supporting delayed samplings and symbolic execution of suspended values, proven sound via erasure to standard probabilistic call-by-value semantics.
Urn Resources: A new separation logic resource for reasoning about distributions of states arising from delayed samplings.
Soundness and Adequacy: A formal soundness proof connecting the delayed sampling semantics to standard semantics, ensuring that proving properties on the delayed version implies error bounds on the standard version.
Mechanized Case Studies: All results are mechanized in the Rocq proof assistant (using the Iris framework and Coquelicot library). The paper demonstrates the logic's expressiveness through several complex examples:
- Interactive Guessing: Proving error bounds for an adversary with multiple attempts to guess a secret, where the number of attempts is unknown.
- Complicated Flip: Verifying that a program returns a uniformly distributed bit even when an adversary can manipulate the state via closures, provided they cannot read the state directly.
- Preimage Resistance: Formalizing the preimage resistance of a random oracle hash model against an interactive adversary.
- Unlinkability: Verifying the unlinkability property of the Basic Hash protocol.
- Discrete Logarithm Problem: Providing the first formal, mechanized proof of error bounds for the discrete logarithm problem in the generic group model against interactive generic algorithms.

Results
The authors demonstrate that Elton can prove error bounds for a wide range of security examples that were previously out of scope for existing techniques. Specifically:

Elton successfully handles scenarios where the order of random sampling and adversarial calls is swapped (e.g., guess2), a case where standard Eris rules fail.
It verifies properties involving dynamically allocated local state and complex probabilistic reasoning, such as the unlinkability of the Basic Hash protocol.
It provides a formal proof for the discrete logarithm problem in the generic group model, matching the error bounds established by Shoup but within a precise operational semantics for interactive programs.

Significance
The paper positions Elton as a significant advancement in the formal verification of cryptographic protocols. By bridging the gap between lifting-based logics (which handle complex language features) and distributional logics (which handle probabilistic invariants), Elton enables the verification of security properties in the presence of unknown adversaries without resorting to simplified models or ad-hoc syntactic restrictions. The authors note that while the approach is currently limited to uniform distributions and requires significant modifications to support more complex distributions (e.g., non-uniform or infinite), it establishes a promising foundation for expressing distributional properties within a lifting-based logic framework. The work is fully mechanized, providing a high degree of trust in the derived security guarantees.