A new paper argues that AI agents should carry cryptographic receipts proving their actions followed agreed rules.
The proposal, posted to arXiv, describes a pipeline in which a correctness or policy condition is encoded as a logical predicate, compiled into a set of polynomial constraints, and then certified using a succinct cryptographic proof system. The result is a certificate that travels with an agent's action and can be checked independently, without the verifier needing to trust the agent or replay its computation. The authors also flag an optional zero-knowledge variant, which would let an agent prove compliance without revealing anything about its internal state or the data it processed.
The timing is not accidental. Agentic AI systems — models that autonomously take sequences of actions, call APIs, and operate with minimal human oversight — are moving from demos into production, and the governance frameworks for auditing them have not kept pace. This proposal sits between two existing approaches that each have serious drawbacks: formal verification of source code is rigorous but expensive and often impractical for large neural systems, while cryptographic authentication tells you who sent a message but nothing about whether what they did was correct.
The authors acknowledge that a working implementation would have to answer hard questions around specification (who writes the policy predicate and how?), auditing, and deployment overhead. Proof systems like zkVMs have matured quickly, but the computational cost of generating proofs at inference-time scale remains a real constraint — one the paper does not resolve so much as defer.