ZK-EXECBIND: Verifiable Stateful Policy Compliance for Tool-Using Agents

Tool-using agents can satisfy each per-action rule while exceeding a cumulative budget or call-count limit. A plaintext checker can evaluate this state, but an external auditor must either trust the checker or receive the underlying policy, credential, and cumulative state. We present ZK-EXECBIND, a protocol that combines a Groth16 proof of a stateful policy relation with an action commitment computed under a versioned Python reference contract, a tool-signed receiver-side receipt, and signed session boundaries. The verifier receives the disclosed action, receipt, session fields, proof, and commitments, but not raw policy, credential, or cumulative-state values. In a controlled payment-like environment, the zero-knowledge path matches the full-access decision on 234/234 archived trajectories. The anchored verifier rejects 2,880/2,880 deterministic mutation, omission, replay, fork, and encoding controls. For 50-action bundles, external verification takes 535.1ms at p50 and the median serialized bundle is 170.2kB. These results measure decision parity, protocol conformance, and cost; they do not claim improved policy accuracy or action privacy.