Proof of (useful) work
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 lets that computation also 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 proposed ones based on problems such as Orthogonal Vectors and 3SUM, and showed that the work cannot be amortized across instances 3. Their revised version drops the claim that this work is useful, because a naive construction already met their definition 3 4. 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. The proof does not show that the matrices came from AI work. On Pearl's network, which ran the earlier integer scheme, an independent study in May 2026 found that random matrices passed verification 6.
Attestable proposes using proof-of-work accounting to bound the compute left for unmonitored activity, as in proofs of useful work for capacity accounting 7. 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 7.
Related
Used in
- ProposedProofs of useful work for capacity accounting
- Research demoTimed challenge-response and memory-occupation challenges
- Research demoGPU contention probes Draft
- Operational usePearl proof-of-useful-work blockchain
Sources
- Tier A. S. 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
- Tier B. A. Scher & L. Thiergart (2024). Mechanisms to Verify International Agreements About AI Development. Machine Intelligence Research Institute. Source recordSupports: mining hashes message variants until one meets a target, which a verifier can check quickly · 'Proof-of-Work methods for crypto mining', in 'Verifying That Known Compute is Not Being Used for a Large Training Run'
- Tier B. M. 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 first presented as useful; evaluation cannot be amortized across instances; energy waste motivation; revised version drops the usefulness claim · abstract; note
- Tier B. I. Komargodski & O. Weinstein (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; Ball et al.'s follow-up dropping the usefulness claim · abstract; §1 'Proofs of Useful Work' (arXiv v4)
- Tier B. Pearl 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
- Tier B. A. Basu (2026). The Usefulness Gap in Proof-of-Useful-Work: An Empirical Study of Pearl's cuPOW Protocol. arXiv. Source recordSupports: independent measurement of Pearl's mainnet: random matrices pass verification · abstract; measurement and verification sections
- Tier C. Attestable (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