AI agents increasingly act on a person's behalf across many organizations. An agent receives a token from a user's home institution, passes a narrower token to a sub-agent, which calls a computing facility, which calls a storage service. Each hop in this chain is a "dual-role" party: it checks a token it received, acting as a relying party, and then issues a new one, acting as an identity provider. That pattern is already known to be dangerous. Model-based testing of 500 OAuth deployments found that a single compromised dual-role party can break every client downstream of it (Model-based Security Testing: An Empirical Study on OAuth 2.0 Implementations). Scientific agents working across high-performance computing (HPC) sites already struggle with brittle cross-domain credentials (Experiences with Model Context Protocol Servers for Science and High Performance Computing). The three-token delegation design proposed for agents in Position: AI Agents Need Authenticated Delegation has never been verified at all.
We propose to verify such chains one hop at a time, for chains of any length, and to have those proofs hold for real signature algorithms over real token bytes, not only for idealized symbolic tokens. The idea rests on one observation. The conditions that make a symbolic proof valid for real cryptography are the tagging rules of A Universally Composable Cryptographic Library. The fix for dual-role amplification is to bind every token to its intended audience and type. These are the same condition. We therefore make these soundness conditions explicit assumptions in each hop's contract, where a contract is a local promise of the form "if my inputs look like this, my outputs will look like that." A cheap check on concrete token formats can then discharge them.
Core Claim
A delegation hop can be written as an assume-guarantee contract $C_i = (A_i, G_i)$. Here $A_i$ is what hop $i$ requires of the token it receives and $G_i$ is what it promises about the token it mints. The assumption $A_i$ has two parts. The first is symbolic: the incoming token is signed by hop $i-1$, names hop $i$ as audience, carries the delegation type tag, and carries scope $s_{i-1}$. The second is a set of concrete preconditions: audience, type and issuer fields sit inside the signed region of the bitstring; each token carries a fresh nonce; and the hop's branching logic reads only signed plaintext claims, never encrypted ones. The guarantee $G_i$ says that every token the hop mints is tagged for hop $i+1$ and carries scope $s_i \subseteq s_{i-1}$.
Because every hop instantiates the same contract template, the interface check $G_i \Rightarrow A_{i+1}$ holds by construction. Induction then gives the end-to-end property for any chain length $n$:
$$\mathrm{Acc}_n(s) \;\Rightarrow\; \exists\, s_0 \supseteq s_1 \supseteq \dots \supseteq s_{n-1} \supseteq s \;:\; \mathrm{Signed}_U(s_0) \wedge \textstyle\bigwedge_{i<n} \mathrm{Minted}_i(s_i).$$
In words: if the final resource grants access with scope $s$ ($\mathrm{Acc}_n(s)$), then the human user $U$ signed some broader scope $s_0$, and every intermediate hop $i$ actually minted a token with a scope $s_i$ that narrows monotonically. The concrete preconditions are exactly the ones a computational soundness theorem needs, so the same local proof also lifts to probabilistic polynomial-time adversaries attacking real signatures.
This differs from each strand of prior work in a specific way:
- Symbolic-to-computational bridging. Computational Soundness for Interactive Primitives bridges symbolic and computational models for isolated primitives such as blind signatures. It requires universally composable (UC) setup assumptions and "uniform" protocols whose control flow ignores secret data. We need no interactive primitives, so we need no common reference string. We also target a restricted relaxation of uniformity, described below.
- Computational composition logic. Key Exchange Protocols: Security Definition, Proof Method and Applications gives computationally meaningful sequential composition, but only for two-party handshakes and without mechanization. We compose an unbounded chain of three-role parties and mechanize each hop.
- Contract theory. Moving from Specifications to Contracts in Component-Based Design supplies the algebra of contract composition over transition systems, with no adversary. We reuse its composition rules and add an attacker-knowledge semantics.
- Federated naming. A Logic for SDSI's Linked Local Name Spaces separates naming from delegation of authority in a purely symbolic setting. We inherit that separation (scopes are authority; audiences are names) and attach cryptographic meaning to it.
Research Program
The theoretical core has three pieces.
The first is the contract language and a composition theorem for chains, built on the dominating-contract construction of Bauer et al., with an induction principle for template contracts.
The second is a lifting argument. We check that each per-hop symbolic model falls inside the fragment covered by existing soundness results for signatures, and we show that chaining hops preserves those side conditions. Restrictions such as key cycles are already handled in Computational Soundness without Protocol Restrictions.
The third, and the riskiest, is a "public-branching" lemma. Uniformity is meant to stop control flow from leaking secrets. Branching on claims that are signed but not encrypted leaks nothing, because the attacker already sees those claims. We conjecture that protocols whose branches depend only on attacker-derivable values still admit soundness lifting. If the lemma fails, we fall back to treating encrypted-claim tokens as out of scope and say so plainly.
We deliberately exclude two things from the guarantee. Revocation and expiry are left out, because time-varying guarantees break static contract algebra. Transport leaks are also left out: OAuth Demystified for Mobile Application Developers found 59.7% of OAuth apps vulnerable, and many of those failures come from bearer tokens leaking over insecure inter-app channels. Transport security stays an explicit environment assumption, which is flagged rather than proved.
The engineering core has two pieces. The first is a set of per-hop models in ProVerif, a symbolic protocol verifier. It covers the three-token agent delegation design and an OAuth token-exchange-style chain, following the modular style that let Chaum's protocol verify in under one second in about 200 lines (Computational Soundness for Interactive Primitives). The second is a precondition checker that parses concrete token formats (JSON Web Tokens and issuer configurations). It decides whether a deployed hop meets the concrete part of $A_i$: signed audience, signed type tag, nonce present, and routing that reads only signed claims.
Baselines
The naive reference point is checking conformance to published specifications, meaning the audience and state checks the specifications already recommend, without any proof. The deployment studies show what this achieves in practice: 55.31% of applications using the STATE parameter mishandled it, 82.96% did not mandate TLS (Model-based Security Testing), and 59.7% of OAuth mobile apps were vulnerable (OAuth Demystified). We will run the same conformance checklist over our seeded-flaw benchmark. Beating it means detecting seeded flaws that the checklist passes, especially cross-hop audience confusion.
The strongest competitor is monolithic ProVerif verification of the whole chain at a fixed length. It is the strongest because for short chains it is complete for the modeled attacker and needs no new theory. We will give it identical protocol models, the same machine, and the same wall-clock budget, sweeping chain length from 1 upward. No reported result for monolithic verification of multi-hop delegation chains was found on Lacuna; the closest reported figure is the under-one-second verification of the modularized Chaum model. Beating this baseline means two things: finding every attack it finds on bounded chains, and returning proofs at lengths where it times out. Beyond that, only our method gives a guarantee for unbounded length.
The dynamic-testing baseline is OAuthTester-style model-based fuzzing (Model-based Security Testing), which reports 20.3 minutes per application and rediscovered dual-role amplification. We will reimplement its state-machine exploration against our reference chain deployments under an equal time budget. We compare detection of seeded flaws and false alarms.
The key ablation removes the concrete preconditions from $A_i$, keeping only the symbolic assumptions. We then check whether per-hop proofs still "succeed" on chains that have real attacks against real token encodings. If they do, those false proofs are exactly the gap our contracts close.
Why not just…?
Why not just verify the whole chain monolithically in ProVerif? For chains of two or three hops this may well work, and we treat it as a real threat rather than a strawman. The experiment settles the practical question by plotting proof time against chain length. Even if monolithic verification scales further than expected, it proves only the lengths it was run on. Agent delegation depth is set at run time, so a bounded proof does not cover the deployed system. The per-hop induction does. If monolithic verification also finds attacks our local checks miss, the composition theorem is wrong, and the soundness check below is designed to catch that.
Why not just require audience-bound, typed tokens as an engineering rule? This is close to what the contracts enforce, and we expect the contract preconditions to reduce largely to it. The contribution is showing that the rule is sufficient for arbitrary-length chains against computational adversaries. The ablation tests which conditions are necessary: if dropping each one yields a concrete attack, the rule is minimal. If audience binding alone turns out sufficient, we will report that as the finding. The deployment data show that such rules are routinely skipped when nothing checks them, so a mechanical checker still earns its place.
Why not just fuzz deployments with OAuthTester? Fuzzing finds bugs but cannot establish their absence, and it examines traces rather than the cryptographic conditions that determine whether a symbolic argument transfers to real bytes. We will measure its recall on seeded flaws directly instead of assuming it is low.
Why not let a language model write the per-hop contracts? On the DAFNYCOMP benchmark, which tests multi-function contract writing in the Dafny verification language, frontier models fall from 58–67% on single functions to a 2% Pass@8 ceiling on call chains (Local Success Does Not Compose). Language-model self-checks catch only 0–20% of malfunction attacks (Breaking Agents). Our design sidesteps the problem, because the contract is one fixed template rather than a new invention at each boundary. We will test that explanation by asking models to write per-hop contracts for our chains with and without the template.
Proposed Experiments
We will build a delegation-chain benchmark. Its seeds are the three-token agent design and a token-exchange chain, instantiated at lengths 1 to 10. Each chain receives injected flaws: audience omitted from the signed region, a missing type tag distinguishing ID tokens from delegation tokens, scope widening at one hop, routing on an encrypted claim, and a re-creation of the dual-role amplification attack from the OAuthTester study, which serves as the positive control.
The decisive checks are three.
The first tests soundness of composition. On every bounded chain where monolithic ProVerif finds an attack, some local contract must fail. A single miss refutes the theorem as stated.
The second tests necessity of the concrete preconditions. For each precondition removed, we must exhibit a concrete attack on real token encodings that the purely symbolic per-hop proof misses. This is the symbolic-computational gap made visible, in the spirit of the hidden-algebra attacks shown in Formal Verification and Solutions for Estonian E-Voting.
The third tests scaling: proof time per hop should stay flat as chains grow, while the monolithic baseline's time climbs.
We will additionally run the precondition checker on publicly documented issuer configurations and token samples from the agent-delegation and scientific-computing settings, reporting how many hops meet or violate $A_i$. We will not claim prevalence figures beyond what we measure.
References
- Model-based Security Testing: An Empirical Study on OAuth 2.0 Implementations
- Experiences with Model Context Protocol Servers for Science and High Performance Computing
- Position: AI Agents Need Authenticated Delegation
- A Universally Composable Cryptographic Library
- Computational Soundness for Interactive Primitives
- Key Exchange Protocols: Security Definition, Proof Method and Applications
- Moving from Specifications to Contracts in Component-Based Design
- A Logic for SDSI's Linked Local Name Spaces
- Computational soundness without protocol restrictions
- OAuth Demystified for Mobile Application Developers
- Local Success Does Not Compose: Benchmarking Large Language Models for Compositional Formal Verification
- Breaking Agents: Compromising Autonomous LLM Agents Through Malfunction Amplification
- Formal Verification and Solutions for Estonian E-Voting