Proof of useful work for verifying AI treaties

Published on October 9, 2026 10:26 AM GMT Cross-posted from my website and Substack. Verifying an international agreement pausing AI development needs evidence of how compute is used. Cryptography can give protocols that run in software on the chips already installed, without trusted hardware checking each computation. This post is a literature review of one such tool, proof of useful work (PoUW), with which a GPU proves that it did a given amount of work, here typically matrix multiplication. In contrast with inference verification, PoUW has been developed almost exclusively in relation to cryptocurrencies in order to use a more useful computation instead of the useless hashing used in Bitcoin. PoUW could be used to show remotely that chips are kept busy on useless tasks during an emergency shutdown, or, together with a zero-knowledge proof of the workload, that they run only declared inference. I describe the two existing constructions, by Komargodski and Weinstein for matrices over a finite field, and by Pearl Research for the FP8 format used in AI, verifiable for now only on NVIDIA chips. For the finite-field scheme, a lower bound on the work is proven, but it covers only a fraction of what an honest prover does. The guarantee a treaty needs, at realistic matrix sizes, rests on unproven assumptions in both schemes; for Pearl, the assumption is stated only informally. PoUW depends on knowledge of the hardware. It gives only a lower bound on work, which means little without a trusted bound on peak chip capacity and a way to tie the work to the declared chips; the floating-point scheme moreover needs a bit-exact model of each chip's arithmetic, and the true cost of the declared workload depends on the GPU it runs on. These hardware questions aside, most of the open problems are mathematical and should be amenable to AI-assisted research. Cryptography for verification An agreement that pauses AI development, or paces the frontier, needs evidence about how declared compute is used. James Petrie's forthcoming agenda, Research Priorities for AI Compute Verification, lists many kinds of evidence. Here, I only mention three that rest on cryptography, more specifically on zero-knowledge (ZK) proofs. These protocols could run on the chips already installed, since checking the computation needs no secure enclaves or verifier devices in the datacenter. Some trusted knowledge of the hardware may still be needed, as discussed below. If such protocols were formally verified and trusted, the first phase of a pause could keep the chips in use instead of decommissioning or retrofitting them. Inference verification. Show that compute runs declared inference and nothing else. This is the closest to deployment, in a regime that allows verified inference and nothing else, either through network certifiers that recompute the outputs or through zero-knowledge proofs of inference (Petrie's agenda; startup Attestable reports ZK proofs of inference for a 31B open model on a single H100, as alpha results with 8-bit integer matrix multiplications and a 16K context). Training verification. Show what exactly happened during a training run. At the robustness a treaty needs, this is a long shot due to the large compute overhead of current methods, but Peigné-Lefebvre, Nguyen and Wang argue that the overhead is not fundamental: committing to intermediate results on the fly and proving only randomly sampled steps brings it down to an estimated single-digit percentage. Proof of useful work. Show remotely that compute was occupied, with no verifier hardware on site. The boundary between inference verification and PoUW is blurry, since both start from the observation in Petrie's agenda that "an alternative to hardware measurements is to provide the results of computations themselves as evidence of how compute is being used." The difference is that inference verification shows what was computed and says how much work this took only indirectly, under the assumption that the declared outputs could not have been produced more cheaply. Because the prover chooses the inputs, this assumption fails for easy instances, for example repeated prompts or cached prefixes. PoUW gives the lower bound on work directly. Noise derived from a public seed prevents the prover from choosing easy instances, so the results themselves certify how much work they required. The current schemes, however, cover only matrix multiplication, whereas inference verification also has to deal with the nonlinear layers. These layers (softmax, GELU, normalization) are not polynomial operations, and ZK provers typically check them against precomputed tables using lookup arguments. One key limitation of PoUW schemes is that they do depend on knowledge of the prover's hardware, because they give only a lower bound on the work performed. Without a trusted bound on the peak capacity of the chips, a prover could run provable work on part of the capacity and use the rest for something e