Certified Multi-Source Integrity for Structured Agent Actions

What it is

This paper gives a formal certifier for structured, privileged agent actions (e.g. paying an invoice) assembled from multiple untrusted sources (purchase order, invoice, bank confirmation, sanctions feed), designed to resist indirect prompt injection that corrupts one or more of those sources. Code and data are at https://github.com/anmolpandey299/certified-multisource-integrity.

How it works

The core mechanism is a corruption-distinct count, computed as a minimum hitting set over attestations' dependency sets — the fewest control domains an adversary must corrupt to erase a fact. This stops laundered copies or republished records (e.g. a national list that merely transposes a UN designation) from being miscounted as independent corroboration.

The certifier applies different rules per field type instead of one universal rule:

• Agreement-or-escalate (identity fields): execute only if a mandatory quorum of corruption-distinct classes all agree; abstain otherwise. Proven (N-1)-safe but not maximally live.
• Unique-threshold admission (value fields): execute a value if at most k corruption-distinct classes dissent AND it's the only value clearing that threshold. Proven safe and maximally live exactly when N > 2k (the Byzantine bound, exact-value radius ⌊(N-1)/2⌋).
• Reconciliation (complementary fields, e.g. invoice amount): deterministic check against an authorized ceiling, not a vote.
• Trusted anchor (single-sourced fields, e.g. payee account): execute only if the account matches the payee name at the bank AND appears on an onboarding allowlist — safety here rests on the anchor, not a corruption radius.

A trusted obligation skeleton (operation, transaction key, mandatory sources, amount cap, destination constraints) is fixed from user intent before any untrusted evidence is read, closing a "selection attack" where a poisoned source redirects the agent to a different transaction entirely.

Theorem 1 formalizes the central result: safe execution is possible exactly when the set of k-feasible actions is a singleton; the certifier that executes the unique feasible action and abstains otherwise is both k-safe and maximally live (abstains least among all safe certifiers).

Preconditions / Affected

Applies to agentic systems executing irreversible structured actions (payments, sanctions screening, record filing) sourced from multiple documents/tool outputs where an adversary can control at most k control domains via indirect prompt injection. Vote-identity counting requires attestations to be bound to an unforgeable origin identifier per control domain — without this, a single corrupted source can emit multiple records/copies to manufacture a fake quorum (the attack Proposition 3 specifically closes).

Caveats

The paper states its own scope limits: real-world evidence corroborates only a minority of relations (only ~15% of the 70,966 sanctions entities had three or more issuing domains; none of the 450 npm packages reached three corruption-distinct witnesses once shared origin was counted). The account field's safety depends on a trusted anchor rather than the corruption-radius proof. The live-model adversary tested was property-based rather than a fully optimizing attacker. Exact dependency sets aren't yet available, so Section 4's corruption-distinct counts are described as upper-bound proxies.