Cryptographic certificates of validity for trustworthy AI Murdoch J. Gabbay Abstract We propose cryptographic certificates of validity for agentic AI systems. The core idea is to formally specify a correctness or policy condition as a logical predicate, compile this predicate to a witness-checking problem over polynomial constraints, and use a succinct cryptographic proof system (and optionally zero-knowledge) to certify that the condition holds. This offers a middle ground between formal verification of source code, and cryptographic authentication. An agent’s action can be accompanied by an independently checkable proof that it satisfies an agreed formal policy, without requiring the verifier to trust the agent or to re-execute computation. We outline the approach at a high level, give the core mathematical translation, relate the proposal to proof-carrying code, zkVMs, formal methods, and agent governance, and note the specification, auditing, and deployment questions that a full implementation must answer. 1 Introduction Agentic AI systems are beginning to take actions, not merely produce recommendations. A travel assistant may book a flight; an enterprise agent may approve an invoice; a software agent may deploy code; a robotic agent may act in the physical world. For such systems a key question is: is this action authorised and policy compliant; is it correct? Cryptographic signatures traditionally authenticate origin , by certifying that the sender of a message knew a certain key. Logs can be used retrospectively to reconstruct events. However, cryptographic signatures, logs, and monitoring cannot prove that an action will satisfy correctness, safety, or compliance conditions in advance . In this paper, we propose a complementary mechanism: cryptographic certificates of validity for agent actions, before actions are carried out. The idea is simple. 1. Express the relevant policy or correctness condition as a formal specification in an appropriate logic. 2. Compile the resulting finite witness-checking problem to cryptography-friendly polynomial constraints (as we will sketch). 3. Require the agent or an associated prover to attach a succinct cryptographic proof that the constraints are satisfied. (In zero-knowledge settings, the verifier may check the certificate without learning private witness data.) The slogan is: do not trust an action because of its origin; trust it because it carries cryptographically checkable evidence of correctness. A note on scope may now be helpful. The mathematics in Section 2 is application-agnostic: it provides an arithmetisation of first‑order logic validity to judgements on polynomial constraints. This may be useful wherever a verifier requires succinct cryptographic evidence that a stated condition holds. This builds a bridge from first-order specification to cryptographic certification. The setting of agentic AI makes the assurance problem concrete and urgent — autonomous action is a signal case in which origin-based authentication and post-hoc logging may not be fully adequate. But the mathematical architecture which we use to address this problem — predicate \to polynomial constraint \to cryptographic certificate — is general, and might be usefully specialised to any domain where untrusted parties must provide checkable evidence of correctness. From this perspective, systems of AI agents are just heterogeneous distributed systems of agents who may be independently developed and may act according to their own priorities. They may also (to borrow a term from distributed systems) be Byzantine , meaning that they do not satisfy the expected specification. Our proposal is to make selected actions proof-carrying, in a very particular sense: for their action to be accepted, they must produce a cryptographic certificate of validity of their correctness predicate. Advanced AI assistants can plan and execute sequences of actions Gabriel et al. 2024 . Thus we need accountability, which requires evidence of where, why, how, and by whom agents are used Chan et al. 2024 . This paper offers a complementary assurance: further to identity, logging, and risk-management practices such as those articulated in the NIST AI Risk Management Framework National Institute of Standards and Technology 2023 , selected agent actions should carry compact certificates that a formal specification has been validated. We can think of this as a cryptographic analogue of proof-carrying code Necula 1997 , instantiated using succinct arguments and polynomial arithmetisation Thaler 2022 ; Gabbay 2024 ; Gabbay 2025 ; Garreta et al. 2025 . One final note, for the record: a certificate of validity for a formal specification does not in and of itself prove that the formal specification is the right specification. It proves, under the stated assumptions and to within appropriate soundness bounds of the underlying cryptographic back end, that the formal specification has been validated. 2 A compact slice of maths Notation 2.1 . Define [n]=\{1,\dots,n\}\subseteq\mathbb{N} . If R is a ring and X is a formal variable symbol then P\in R[X] is a formal sum of powers of X , which we call a polynomial (with coefficients in R ). Polynomials can be added and multiplied in the usual way. For example, (1+X)*(1-X)=1-X^{2}\in\mathbb{Z}[X] . Notation 2.2 . If P,Q\in\mathbb{Z}[X] then write P(Q)\in\mathbb{Z}[X] for the result of instantiating X to Q in P . For example if P=X+1 and Q=2*X then P(Q)=2*X+1 . \begin{array}[]{r@{\ }l}t::=&X\mid a\in\mathbb{Z}\mid t+t\mid t*t\mid{\text{$\mathtt{C}$}}_{i}(t)\mid{\text{$\mathsf{len}$}}({\text{$\mathtt{C}$}})\mid{\text{$\mathsf{reify}$}}(\phi)\\ \phi,\psi::=&t\mathbin{{\boldsymbol{\text{=}}}}t\mid\phi\mathbin{{\boldsymbol{\wedge}}}\phi\mid\phi\mathbin{{\boldsymbol{\vee}}}\phi\mid{{\boldsymbol{\hskip 0.8pt\raisebox{0.5pt}{\scalebox{.85}{$\forall$}}\hskip 0.2pt}}}_{\hskip-1.0pt{\text{$\mathtt{C}$}}}X.\phi\mid{\text{$\mathtt{C}$}}_{i}\mathbin{{\boldsymbol{<}}}t\mid t\mathbin{{\boldsymbol{<}}}{\text{$\mathtt{C}$}}_{i}\end{array} Above, i{\in}[{\text{$\mathit{arity}$}}({\text{$\mathtt{C}$}})] . These grammars are in BNF style, such that \phi and t to the right of ::= represent any predicate or term. Thus \phi\mathbin{{\boldsymbol{\wedge}}}\phi denotes a conjunction of two (possibly non-equal) predicates, and t\mathbin{{\boldsymbol{\text{=}}}}t denotes two (possibly non-equal) terms. Figure 1: Syntax of terms and predicates (Definition 2.3 ) Definition 2.3 . Fix an index variable symbol X and a set of polynomial function symbols {\text{$\mathtt{C}$}},{\text{$\mathtt{D}$}}\in{\text{$\mathsf{PolyFunc}$}} , each of which has a fixed but arbitrary arity {\text{$\mathit{arity}$}}({\text{$\mathtt{C}$}})\in\mathbb{N}_{\geq 1} . Write {\text{$\mathtt{C}$}}:n for the assertion “ {\text{$\mathtt{C}$}}\in{\text{$\mathsf{PolyFunc}$}} and {\text{$\mathit{arity}$}}({\text{$\mathtt{C}$}})=n ”. Define terms and predicates inductively as in Figure 1 . Notation 2.4 . We may write t\mathbin{{\boldsymbol{\leq}}}{\text{$\mathtt{C}$}}_{i}\mathbin{{\boldsymbol{\leq}}}t^{\prime} for (t-1\mathbin{{\boldsymbol{<}}}{\text{$\mathtt{C}$}}_{i})\mathbin{{\boldsymbol{\wedge}}}({\text{$\mathtt{C}$}}_{i}\mathbin{{\boldsymbol{<}}}t^{\prime}+1) . We may call predicates based on \mathbin{{\boldsymbol{<}}} range-checks . \begin{array}[]{r@{\ }l@{\ \ }r@{\ }l}{[\hskip-1.99997pt[X]\hskip-1.99997pt]}_{\varsigma}=&X&{[\hskip-1.99997pt[a]\hskip-1.99997pt]}_{\varsigma}=&a\\ {[\hskip-1.99997pt[t+t^{\prime}]\hskip-1.99997pt]}_{\varsigma}=&{[\hskip-1.99997pt[t]\hskip-1.99997pt]}_{\varsigma}+{[\hskip-1.99997pt[t^{\prime}]\hskip-1.99997pt]}_{\varsigma}&{[\hskip-1.99997pt[t*t^{\prime}]\hskip-1.99997pt]}_{\varsigma}=&{[\hskip-1.99997pt[t]\hskip-1.99997pt]}_{\varsigma}*{[\hskip-1.99997pt[t^{\prime}]\hskip-1.99997pt]}_{\varsigma}\\ {[\hskip-1.99997pt[{\text{$\mathtt{C}$}}_{i}(t)]\hskip-1.99997pt]}_{\varsigma}=&{\text{$\mathit{itplnt}$}}(\varsigma({\text{$\mathtt{C}$}})_{i})({[\hskip-1.99997pt[t]\hskip-1.99997pt]}_{\varsigma})&{[\hskip-1.99997pt[{\text{$\mathsf{len}$}}({\text{$\mathtt{C}$}})]\hskip-1.99997pt]}_{\varsigma}=&{\text{$\mathit{len}$}}(\varsigma({\text{$\mathtt{C}$}}))\\ {[\hskip-1.99997pt[{\text{$\mathsf{reify}$}}(\phi)]\hskip-1.99997pt]}_{\varsigma}=&{[\hskip-1.99997pt[\phi]\hskip-1.99997pt]}_{\varsigma}\\[8.61108pt] {[\hskip-1.99997pt[t\mathbin{{\boldsymbol{\text{=}}}}t^{\prime}]\hskip-1.99997pt]}_{\varsigma}=&({[\hskip-1.99997pt[t]\hskip-1.99997pt]}_{\varsigma}-{[\hskip-1.99997pt[t^{\prime}]\hskip-1.99997pt]}_{\varsigma})^{2}\\ {[\hskip-1.99997pt[\phi\mathbin{{\boldsymbol{\wedge}}}\phi^{\prime}]\hskip-1.99997pt]}_{\varsigma}=&{[\hskip-1.99997pt[\phi]\hskip-1.99997pt]}_{\varsigma}+{[\hskip-1.99997pt[\phi^{\prime}]\hskip-1.99997pt]}_{\varsigma}&{[\hskip-1.99997pt[\phi\mathbin{{\boldsymbol{\vee}}}\phi^{\prime}]\hskip-1.99997pt]}_{\varsigma}=&{[\hskip-1.99997pt[\phi]\hskip-1.99997pt]}_{\varsigma}*{[\hskip-1.99997pt[\phi^{\prime}]\hskip-1.99997pt]}_{\varsigma}\\ {[\hskip-1.99997pt[{{\boldsymbol{\hskip 0.8pt\raisebox{0.5pt}{\scalebox{.85}{$\forall$}}\hskip 0.2pt}}}_{\hskip-1.0pt{\text{$\mathtt{C}$}}}X.\phi]\hskip-1.99997pt]}_{\varsigma}=&\hbox to0.0pt{$\sum_{x{\in}[{\text{$\mathit{len}$}}(\varsigma({\text{$\mathtt{C}$}}))]}{[\hskip-1.99997pt[\phi]\hskip-1.99997pt]}_{\varsigma}(x)$\hss}\\[8.61108pt] {[\hskip-1.99997pt[{\text{$\mathtt{C}$}}_{i}0,\ \text{and}\ 1\text{ otherwise}\end{array} So: • \vDash_{\varsigma}\chi_{{\text{$\mathtt{m}$}}} when \varsigma({\text{$\mathtt{m}$}}) is a two-row matrix where in each column the second entry is the negation of the first. Thus, each column in \varsigma({\text{$\mathtt{m}$}}) represents a pair (x,{\shortminus}x) for some x\in\mathbb{Z} . {\text{$\mathit{arity}$}}({\text{$\mathtt{m}$}})=2 because \lambda x.{\shortminus}x has one input and output. • \vDash_{\varsigma}\chi_{{\text{$\mathtt{a}$}}} when \varsigma({\text{$\mathtt{a}$}}) is a three-row matrix where in each column the third entry is the sum of the first and the second; thus \varsigma({\text{$\mathtt{a}$}}) has columns of the form (x,x^{\prime},x{+}x^{\prime}) and samples the graph of \lambda x,x^{\prime}.x{+}x^{\prime} at {\text{$\mathit{len}$}}(\varsigma({\text{$\mathtt{a}$}})) many points. {\text{$\mathit{arity}$}}({\text{$\mathtt{a}$}})=3 because \lambda x,x^{\prime}.x{+}x^{\prime} has two inputs and one output. • \vDash_{\varsigma}\chi_{{\text{$\mathtt{p}$}}} when \varsigma({\text{$\mathtt{p}$}}) is a one-row matrix (a vector) of strictly positive numbers. {\text{$\mathit{arity}$}}({\text{$\mathtt{p}$}})=1 because ‘is strictly positive’ is a predicate on one argument. Logic Polynomial Truth values 0= true/valid/success; strictly positive = false/invalid/failure. Equality {[\hskip-1.99997pt[t\mathbin{{\boldsymbol{\text{=}}}}t^{\prime}]\hskip-1.99997pt]}_{\varsigma}=({[\hskip-1.99997pt[t]\hskip-1.99997pt]}_{\varsigma}-{[\hskip-1.99997pt[t^{\prime}]\hskip-1.99997pt]}_{\varsigma})^{2} , so equality is valid exactly at zero. Conjunction {[\hskip-1.99997pt[\phi\mathbin{{\boldsymbol{\wedge}}}\psi]\hskip-1.99997pt]}_{\varsigma}={[\hskip-1.99997pt[\phi]\hskip-1.99997pt]}_{\varsigma}+{[\hskip-1.99997pt[\psi]\hskip-1.99997pt]}_{\varsigma} ; sum of nonnegatives is zero iff both are zero. Disjunction {[\hskip-1.99997pt[\phi\mathbin{{\boldsymbol{\vee}}}\psi]\hskip-1.99997pt]}_{\varsigma}={[\hskip-1.99997pt[\phi]\hskip-1.99997pt]}_{\varsigma}*{[\hskip-1.99997pt[\psi]\hskip-1.99997pt]}_{\varsigma} ; product is zero iff at least one factor is zero. Range check 0 when satisfied, 1 otherwise. Top-level \forall Root test for a range of values. \phi valid {[\hskip-1.99997pt[\phi]\hskip-1.99997pt]}_{\varsigma}=0 \phi invalid {[\hskip-1.99997pt[\phi]\hskip-1.99997pt]}_{\varsigma}>0 Figure 3: Table of semantic meaning (Remark 3.2 ) Remark 3.2 . A table of semantic meanings is in Figure 3 . The reader may be more used to seeing ‘true = 1; false = 0’, but representing truth with 0 and non-truth with strictly positive values also has pedigree. In a paper from 1943 Kleene 1943 on page 51 just after equation 17, Kleene writes “a representing function \pi of P , the value of which is to be 0 , 1 , or undefined according as the value of P is true, false, or undefined” . More recently, in the sysexits.h file ( credited to Eric Allman in 1980) which describes status codes for system programs, 0 represents successful termination and strictly positive values represent various kinds of failure. We will consider one more example, because it is an important one. We will indicate that our framework can handle recursion ; this is the essence of looping and of Turing-complete computation. The reader will have to excuse that our example will be extremely simple, but it is the structure of the computation that interests us. 3.2 A recursive example Definition 3.3 . Recall the inductive definition of a^{b} for a,b\in\mathbb{N}_{\geq 0} : \begin{array}[]{l@{\qquad}r@{\ }l}\text{base case (BC)}&{\text{$\mathit{pow}$}}(a,0)&=1\\ \text{inductive step (IS)}&{\text{$\mathit{pow}$}}(a,b{+}1)&=a*{\text{$\mathit{pow}$}}(a,b)\end{array} Remark 3.4 . Note how Definition 3.3 , and definitions like it, implicitly equate computation , inductively-defined relations , and derivation , because \mathit{pow} is a relation, it is inductively defined as above, and when we try to compute a value — {\text{$\mathit{pow}$}}(2,2) , say — we generate a derivation-tree as follows: base case \displaystyle{\text{$\mathit{pow}$}}(2,0)=1 inductive step \displaystyle{\text{$\mathit{pow}$}}(2,1)=2 inductive step \displaystyle{\text{$\mathit{pow}$}}(2,2)=4 This example, simple as it is, illustrates the close link between logic, computation, and inductively defined relations. Definition 3.5 . Suppose {\text{$\mathit{ln}$}}\in\mathbb{N}_{\geq 1} . Say a 4\times{\text{$\mathit{ln}$}} matrix C encodes a partial power function when \forall a\in 1..{\text{$\mathit{ln}$}}.\ C_{3,a}=C_{1,a}^{C_{2,a}}. In words, C encodes a partial power function when for each column, the third entry is equal to the first entry raised to the power of the second. Definition 3.6 . Assume {\text{$\mathtt{pow}$}}:4 , so \varsigma({\text{$\mathtt{pow}$}})\in\mathbb{Z}^{4\times{\text{$\mathit{len}$}}(\varsigma({\text{$\mathtt{pow}$}}))} . Figure 4 expresses a validity predicate \chi_{{\text{$\mathtt{pow}$}}} , that \mathtt{pow} encodes a partial power function such that: 1. Row 1 (values of {\text{$\mathtt{pow}$}}_{1}(a) ) stores input values a . 2. Row 2 (values of {\text{$\mathtt{pow}$}}_{2}(a) ) stores input values b . 3. Row 3 (values of {\text{$\mathtt{pow}$}}_{3}(a) ) stores output values a^{b} . 4. Row 4 (values of {\text{$\mathtt{pow}$}}_{4}(a) ) stores the index of a column representing the recursive call in the inductive step. Write {\text{$\mathtt{pow}$}}_{1}(t){=}{\text{$\mathsf{in}$}}_{1}(t) , {\text{$\mathtt{pow}$}}_{2}(t){=}{\text{$\mathsf{in}$}}_{2}(t) , {\text{$\mathtt{pow}$}}_{3}(t){=}{\text{$\mathsf{out}$}}(t) , and {\text{$\mathtt{pow}$}}_{4}(t){=}{\text{$\mathsf{rec}$}}(t) . \begin{array}[]{r@{\ }l}{\text{$\mathsf{BC}$}}(X)=&({\text{$\mathsf{in}$}}_{2}(X)\mathbin{{\boldsymbol{\text{=}}}}0)\mathbin{{\boldsymbol{\wedge}}}({\text{$\mathsf{out}$}}(X)\mathbin{{\boldsymbol{\text{=}}}}1)\\ {\text{$\mathsf{IS}$}}(X)=&{\text{$\mathsf{in}$}}_{1}(X)\mathbin{{\boldsymbol{\text{=}}}}{\text{$\mathsf{in}$}}_{1}({\text{$\mathsf{rec}$}}(X))\mathbin{{\boldsymbol{\wedge}}}{\text{$\mathsf{in}$}}_{2}(X)\mathbin{{\boldsymbol{\text{=}}}}{\text{$\mathsf{in}$}}_{2}({\text{$\mathsf{rec}$}}(X)){+}1\mathbin{{\boldsymbol{\wedge}}}\\ &\hskip 9.24994pt{\text{$\mathsf{out}$}}(X)\mathbin{{\boldsymbol{\text{=}}}}{\text{$\mathsf{in}$}}_{1}(X)*{\text{$\mathsf{out}$}}({\text{$\mathsf{rec}$}}(X))\\ \chi_{{\text{$\mathtt{pow}$}}}=&1\mathbin{{\boldsymbol{\leq}}}{\text{$\mathsf{rec}$}}\mathbin{{\boldsymbol{\leq}}}{\text{$\mathsf{len}$}}({\text{$\mathtt{pow}$}})\ \mathbin{{\boldsymbol{\wedge}}}\ {{\boldsymbol{\hskip 0.8pt\raisebox{0.5pt}{\scalebox{.85}{$\forall$}}\hskip 0.2pt}}}_{{\text{$\mathtt{pow}$}}}X.({\text{$\mathsf{BC}$}}(X)\ \mathbin{{\boldsymbol{\vee}}}\ {\text{$\mathsf{IS}$}}(X))\end{array} Figure 4: Exponentiation a^{b} (Definitions 3.3 and 3.6 ) Lemma 3.7 . If \vDash_{\varsigma}\chi_{{\text{$\mathtt{pow}$}}} then \varsigma({\text{$\mathtt{pow}$}}) encodes a partial power function. Proof. We examine the clauses in Figure 4 and using Theorem 2.9 we check that they correctly encode the definition in Definition 3.3 . ∎ Example 3.8 . We illustrate some values for \varsigma({\text{$\mathtt{pow}$}}) such that \vDash_{\varsigma}\chi_{{\text{$\mathtt{pow}$}}} , so that by Lemma 3.7 they encode a partial power function: \begin{pmatrix}2&2&2\\ 0&1&2\\ 1&2&4\\ 1&1&2\end{pmatrix}\quad\begin{pmatrix}2&2&2\\ 2&1&0\\ 4&2&1\\ 2&3&3\end{pmatrix}\quad\begin{pmatrix}2&2&2&2\\ 0&2&1&0\\ 1&4&2&1\\ 2&3&1&1\end{pmatrix}\quad\begin{pmatrix}3&2&3&2\\ 0&0&1&1\\ 1&1&3&2\\ 1&1&1&2\end{pmatrix} These all represent the derivation-tree from Remark 3.4 : 1. The leftmost matrix encodes in columns 1-3 respectively, the base case of a derivation that 2^{0}=1 , the step 2^{1}=2 , and the final step 2^{2}=4 . Entry 4 in columns 2 and 3 contain a number which is a pointer to the previous step/column in the derivation; entry 4 in column 1 also contains a number but it is not used. 2. The columns need not appear in a particular order, provided that the pointers match up; the next matrix illustrates this by putting the columns in the reverse order. 3. Columns can be duplicated as per the third matrix. 4. The fourth (rightmost) matrix includes information from computing 2^{1}=2 and 3^{1}=3 . Example 3.9 . The converse implication for Lemma 3.7 does not hold. The predicate \chi_{{\text{$\mathtt{pow}$}}} certifies the pointwise correctness of the input-output samples in rows 1-3 and also that those samples can be assembled into a well-formed derivation tree, whose recursive calls are represented by in-range pointers in row 4. {wrapstuff} [r] \begin{pmatrix}2\\ 2\\ 4\\ 2\end{pmatrix} A matrix may encode true values of the partial power function while failing \chi_{{\text{$\mathtt{pow}$}}} , if the certificate of derivation is missing or malformed. For example, the one-column matrix to the right contains the correct input-output sample (2,2,4), since 2^{2}=4 . However, it omits the recursive premise (2,1,2) required by the inductive step. Formally, {\text{$\mathsf{len}$}}({\text{$\mathtt{pow}$}})=1 and the row 4 entry is 2, so the range check 1\mathbin{{\boldsymbol{\leq}}}{\text{$\mathsf{rec}$}}\mathbin{{\boldsymbol{\leq}}}{\text{$\mathsf{len}$}}({\text{$\mathtt{pow}$}}) fails. Equivalently: the supposed recursive pointer points outside the matrix. {wrapstuff} [r] \begin{pmatrix}2&2&2\\ 2&1&0\\ 4&2&1\\ 2&3&\underline{0}\end{pmatrix} A second instructive failure is as per the three-column matrix to the right. Rows 1-3 contain correct samples: 2^{2}=4 , 2^{1}=2 , and 2^{0}=1 , and the first two recursive pointers are meaningful: column 1 points to column 2, and column 2 points to column 3. However, the underlined pointer in the base-case column is not in the range \{1,2,3\} . The base-case clause (BC) does not use this pointer, but our simple presentation imposes the uniform range check on all entries of the pointer row. Hence this matrix encodes correct samples of the partial power function but is not a well-formed \chi_{{\text{$\mathtt{pow}$}}} -certificate. Replacing the underlined 0 with any in-range value, for example with 1, would repair this. In summary: rows 1-3 describe claimed values of the relation; row 4 supplies the proof-carrying structure that allows a verifier to check claims against the inductive definition. Remark 3.10 . Example 3.9 connects directly to agent certification. Columns are not isolated output values; they are structured witnesses which reference each other to prove their validity. In an agentic setting this distinction separates a validator that checks whether an action is compliant from one that checks whether an action carries evidence of its compliance (in this case, columns pointing to one another to prove a recursive computation). This is precisely the proof-carrying structure that the certificates of Section 4 would cryptographically attest to. Remark 3.11 . A more efficient specification of a^{b} is: \begin{array}[]{r@{\ }l}{\text{$\mathit{pow}$}}(a,0)=&1\\ {\text{$\mathit{pow}$}}(a,2*b)=&{\text{$\mathit{pow}$}}(a,b)*{\text{$\mathit{pow}$}}(a,b)\\ {\text{$\mathit{pow}$}}(a,2*b+1)=&a*{\text{$\mathit{pow}$}}(a,b)*{\text{$\mathit{pow}$}}(a,b)\end{array} This yields smaller derivations, which correspond algorithmically to a runtime that is logarithmic in b rather than linear. We could translate this into our logic, and it would just yield an implementation that permits shorter matrices. Remark 3.12 . The logic in Figure 1 is more expressive than it might seem. In particular, negation is expressible in the framework, via \mathsf{reify} . A fuller treatment is in Gabbay 2025 . A proposal for a SNARK-friendly constraint system is in Gabbay and Mendelsohn 2026 . 4 How to apply this mathematics to AI agents Before we address the question of how to apply this mathematics to AI agents — the motivating application of this paper, although the framework in Sections 2 and 3 is general — it is important to understand that polynomial semantics can be plugged directly into cryptographic proof schemes. The semantics in Figure 2 is optimised for exposition, but variations optimised for implementation can be constructed. 3 3 3 One such variant has been submitted for publication, but at time of writing, submission rules prohibit sharing the results. By time of publication I hope to be able to provide links. Thus it is important to appreciate that the presentation in Section 2 is optimised for fitting onto one page including Figure 2 and Theorem 2.9 , consistent with clear exposition. We can optimise for practical implementability instead, but that would be a longer and less accessible presentation: the passage from cleanly presentable theory to applicability is analogous to the passage from a high-level programming language to something more like assembly language or bytecode. Be that as it may, the strategy for applying these ideas is simple: • Write down a predicate that expresses the desired notion of correctness, and translate it (using techniques analogous to program compilation) to an algebraic relation accepted by a cryptographic proof back end. Suitable back ends include integer or mixed-characteristic systems such as Zinc Garreta et al. 2025 and polynomial-commitment/SNARK stacks such as Halo2 and related foundations Electric Coin Company and Zcash Foundation 2026 ; Boneh et al. 2021 . • Require the agent, or associated prover, to produce a cryptographic certificate accepted by the back end. Under the proof system’s assumptions, and subject to stated soundness error, a valid certificate convinces the verifier that the encoded relation has a witness. If this seems conceptually simple, that is because it is. Though this is a short paper, we can make this more concrete. At the boundary of an agentic system, we can represent a certificate of validity abstractly as \mathsf{Cert}=(\mathsf{policyID},\mathsf{action},\mathsf{pub},\mathsf{vk},\mathsf{paramsHash},\pi). Here \mathsf{policyID} identifies the formal predicate \phi and the compiler version; \mathsf{action} is the proposed action; \mathsf{pub} is the public instance data needed to check that action; \mathsf{vk} and \mathsf{paramsHash} identify the approved verifier key and proof-system parameters; and \pi is the succinct cryptographic proof. The intended statement verified by \pi is \exists w.\;R_{\phi,\mathsf{action}}(\mathsf{pub},w)=0, where w is private witness data and R_{\phi,\mathsf{action}} is the algebraic relation obtained by compiling the formal predicate to polynomial constraints. Thus verification of an action has the following form. 1. The policy author or system operator fixes a predicate \phi expressing the required correctness, safety, or compliance condition. 2. A compiler translates \phi , together with the relevant public action data, into an algebraic relation R_{\phi,\mathsf{action}} . 3. The agent, or an associated prover, produces a proof \pi that there exists witness data w satisfying that relation. 4. The receiving system checks \pi using the approved verifier key and rejects action if verification fails. We can sum this up as a slogan: logical validity translates to vanishing of the corresponding algebraic relation. In this interface the verifier need not trust the agent, inspect internal implementation, or re-execute computation. It just checks the proof. Conversely, the certificate proves only the compiled formal claim: it does not prove that the policy was wisely chosen, that the compiler is bug-free, or that the proof-system parameters were correctly governed. A practical compiler would use implementation-oriented arithmetisation techniques; for example multilinear encodings, range checks, and lookup arguments, targeting the back ends mentioned above (Zinc; Halo2). The mathematics of Sections 2 and 3 specifies the correctness condition that such a compiler must preserve. Roadmap. So we can propose a provisional roadmap. If a policy can be logically expressed as a predicate, and if a trusted compilation chain maps that predicate to an algebraic relation while preserving the zero-versus-positive philosophy of Figure 3 , then any sound succinct argument for that relation yields a succinct certificate that the policy predicate is satisfied by the supplied witness data. Remaining questions are just what one would expect, moving from mathematics to a deployed assurance mechanism: how to author and audit correctness predicates; how to verify or test the compiler; how to select and parameterise the proof back end; how to benchmark proving cost; and how to record policy versions and verifier configurations for later accountability. 5 Related work Formal specification and verification. Formal methods provide mature tools for specifying and proving properties of software and systems. Hoare logic Hoare 1969 , proof-carrying code Necula 1997 , verified compilers like CompCert Leroy 2009 , and verified kernels like seL4 Klein et al. 2009 can provide machine-checkable assurance for critical systems. Correctness-by-construction makes assurance part of design and implementation Hall and Chapman 2002 . These approaches share with our proposal a formally specified notion of ‘correctness’. However, the deployments differ: proof-carrying code is not a black-box technique, whereas our proposal imposes no restrictions on how an agent is designed and implemented, other than insisting that some or all of the actions that it proposes be associated to a succinct certificate proving validity of an agreed correctness predicate. Runtime verification, proof-carrying code, and certificates. Runtime verification checks traces of an executing system against formal properties Leucker and Schallhart 2009 . Proof-carrying code asks an untrusted code producer to supply a proof that code satisfies a consumer’s safety policy Necula 1997 . Our proposal can be read as a cryptographic, succinct, and optionally zero-knowledge analogue of proof-carrying code: the consumer publishes or fixes a policy; the agent supplies an action and a certificate; and the verifier checks the certificate without re-running the agent’s entire computation or inspecting all private witness data. Succinct cryptographic proofs and verifiable computation. zk-SNARKs and related succinct arguments allow a prover to convince a verifier that a relation holds between a witness and an instance , while keeping verifier effort small and, in zero-knowledge variants, hiding some or all of the witness. Examples include Pinocchio Parno et al. 2013 , SNARKs for C Ben-Sasson et al. 2013 , Groth’s pairing-based arguments Groth 2016 , and later general frameworks for polynomial IOPs, constraint systems, and related lookup machinery Ben-Sasson et al. 2016 ; Bünz et al. 2020 ; Thaler 2022 ; Setty et al. 2023 ; Setty et al. 2024 . The technical constructions underlying this paper use similar technology; in unpublished work we have shown how to arithmetise the first-order logic of this paper to polynomial constraints on integer/mixed-characteristic proof systems such as Zinc Garreta et al. 2025 , and we are studying how to translate to Halo2 Electric Coin Company and Zcash Foundation 2026 so that logical specifications can be connected to cryptographic back ends. zkVMs and proof-oriented execution environments. An engineering response to the difficulty of writing polynomial constraints directly is zero-knowledge virtual machines, like Cairo Goldberg et al. 2021 , RISC0 RISC Zero 2026 , and Jolt Arun et al. 2024 . These all offer verifiable receipts of correct code execution. Work on formally verifying Cairo execution in Lean reflects the importance of connecting cryptographic proof systems to proof-assistant-level assurance Avigad et al. 2021 . In contrast, the present proposal does not introduce another machine model. Its high-level specification language is first-order logic itself. Programs, policies, transaction rules, and compliance requirements are represented as predicates, which are compiled directly to polynomial proof obligations. Choreographic programming and distributed correctness. Choreographic programming and multiparty session types address distributed correctness from complementary angles. Multiparty session types use global protocol descriptions whose projections type-check communicating processes and establish communication safety, progress, and fidelity Honda et al. 2016 . Choreographic programming writes a global coordination plan from which decentralised implementations can be generated correct by construction Cruz-Filipe and Montesi 2017 (subsequently developed to include functional Cruz-Filipe et al. 2022 and machine-checked Cruz-Filipe et al. 2023 formulations). These ideas may be relevant to agentic AI systems. Our proposal does not replace choreographic or protocol-based design, and it deals with the orthogonal problem of how to ensure that possibly Byzantine, possibly black-box agents — i.e. agents which we did not implement and which we may not be able to look inside — should still carry cryptographic certificates of correct behaviour. 6 Conclusions Formal methods provide the language of formal specification; correctness-by-construction provides a design discipline; runtime verification and proof-carrying code provide certificate-oriented assurance; and zk-SNARKs/zkVMs provide cryptographically checkable execution. This paper articulates a synthesis of these ideas for trustworthy agentic AI: a consequential action may be logged and signed — and also , where feasible, it may be accompanied by a succinct certificate of validity of a formally specified notion of correctness, safety, or compliance. It remains to render these ideas into cryptographically implementable schemes, e.g. by reduction to SNARK-friendly constraint systems. This is ongoing work: a proposal has been very recently presented Gabbay and Mendelsohn 2026 and a conference paper submitted. Future work includes generating auditable deployment patterns; e.g. specification templates for common agent actions, benchmarks across proof back ends, recording of policy versions and verifier configurations, and independent cryptographic, formal-methods, and policy review. These are not mere engineering details. A cryptographic certificate proves satisfaction of the encoded formal predicate under the relevant proof-system assumptions and soundness bounds. It does not prove that the correctness predicate itself reflects safety, legal, operational, or ethical requirements. This specification gap must be addressed through governance, visibility, and risk-management processes; it cannot be closed by mathematics, logic or cryptography alone Chan et al. 2024 ; National Institute of Standards and Technology 2023 .