AI Verification LandscapeSearch

Glossary

Proof of (useful) work

Evidence that a party spent a given amount of computation; in useful variants, the same work also solves a problem someone wants solved.

A proof of work is evidence that a prover spent a non-trivial amount of computation, which a verifier can check quickly; a proof of useful work makes that computation solve a problem someone wants solved 1 2 3.

Dwork and Naor proposed proofs of work to protect shared resources, for example against spam and denial of service, and Bitcoin later used them to prevent double spending 1. Conventional proofs of work waste the computation, so Ball and colleagues built ones whose work solves problems such as Orthogonal Vectors and 3SUM, and showed that the work cannot be amortized across instances 3. Komargodski and Weinstein give a proof of useful work for arbitrary matrix multiplication with 1 + o(1) multiplicative overhead, so that GPUs could do AI work and blockchain mining at once 4; Pearl's specification adapts the construction to FP8 matrix multiplication 5. Attestable proposes using proof-of-work accounting to bound the compute left for unmonitored activity, as in proofs of useful work and resource exhaustion 6. A proof shows that work was done, not that no other work was done: Attestable notes that its scheme needs a credible estimate of the compute available and cannot discover a data centre that was never declared 6.

Related

Used in

Sources

  1. AS. Dziembowski et al. (2015). Proofs of Space. CRYPTO 2015 (IACR Cryptology ePrint Archive 2013/796). Source recordSupports: proofs of work proposed by Dwork and Naor: requester dedicates non-trivial computational work to each request; original uses against spam and denial of service; Bitcoin double spending · abstract
  2. BA. Scher & L. Thiergart (2025). Mechanisms to Verify International Agreements About AI Development. arXiv. Source recordSupports: mining hashes message variants until one meets a target, which a verifier can check quickly · 'Proof-of-Work methods' in the section on verifying known compute is not used for a large training run
  3. BM. Ball et al. (2017). Proofs of Useful Work. IACR Cryptology ePrint Archive 2017/203. Source recordSupports: PoWs based on Orthogonal Vectors, 3SUM and All-Pairs Shortest Path whose work is useful; evaluation cannot be amortized across instances; energy waste motivation · abstract
  4. BI. Komargodski et al. (2025). Proofs of Useful Work from Arbitrary Matrix Multiplication. arXiv. Source recordSupports: PoUW for arbitrary matrix multiplication with 1+o(1) multiplicative overhead; GPUs could do AI work and mining at once · abstract
  5. BPearl Research Team (2026). Pearl Floating Point Scheme Specification. Pearl Research Labs. Source recordSupports: Pearl adapts the matrix-multiplication PoUW to FP8 on GPUs (provider-reported) · abstract; §2
  6. CAttestable (2026). Pacing AI Requires Proof. Attestable blog. Source recordSupports: proposal to use proof-of-work accounting to bound compute for unmonitored activity; needs a credible estimate of available compute; cannot discover an undeclared data centre (provider's own proposal) · whole post