01 / The mechanism and its boundary
What is being described
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 S-1607 S-0005 S-1608.
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 S-1607. 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 S-1608. 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 S-1609. Pearl's specification adapts the construction to FP8 matrix multiplication S-1105. The proof does not show where the matrices came from. On Pearl's network, an independent study found that random matrices passed verification S-0071.
Attestable proposes using proof-of-work accounting to bound the compute left for unmonitored activity, as in proofs of useful work for capacity accounting S-1102. 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 S-1102.
Connections in the research map
Related research
Sources and provenance
- S-1607 / Tier A
Proofs of Space ↗
S. Dziembowski, S. Faust, V. Kolmogorov, K. Pietrzak · 2015 · CRYPTO 2015 (IACR Cryptology ePrint Archive 2013/796)
Supports: 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
Locator: abstract
Version and catalogue details - S-0005 / Tier B
Mechanisms to Verify International Agreements About AI Development ↗
A. Scher, L. Thiergart · 2025 · arXiv
Supports: mining hashes message variants until one meets a target, which a verifier can check quickly
Locator: 'Proof-of-Work methods for crypto mining', in 'Verifying That Known Compute is Not Being Used for a Large Training Run'
Version and catalogue details - S-1608 / Tier B
Proofs of Useful Work ↗
M. Ball, A. Rosen, M. Sabin, P. N. Vasudevan · 2017 · IACR Cryptology ePrint Archive 2017/203
Supports: PoWs based on Orthogonal Vectors, 3SUM and All-Pairs Shortest Path whose work is useful; evaluation cannot be amortized across instances; energy waste motivation
Locator: abstract
Version and catalogue details - S-1609 / Tier B
Proofs of Useful Work from Arbitrary Matrix Multiplication ↗
I. Komargodski, O. Weinstein · 2025 · arXiv
Supports: PoUW for arbitrary matrix multiplication with 1+o(1) multiplicative overhead; GPUs could do AI work and mining at once
Locator: abstract
Version and catalogue details - S-1105 / Tier B
Pearl Floating Point Scheme Specification ↗
Pearl Research Team · 2026 · Pearl Research Labs
Supports: Pearl adapts the matrix-multiplication PoUW to FP8 on GPUs (provider-reported)
Locator: abstract; §2
Version and catalogue details - S-0071 / Tier B
The Usefulness Gap in Proof-of-Useful-Work: An Empirical Study of Pearl's cuPOW Protocol ↗
A. Basu · 2026 · arXiv
Supports: independent measurement of Pearl's mainnet: random matrices pass verification
Locator: abstract; measurement and verification sections
Version and catalogue details - S-1102 / Tier C
Pacing AI Requires Proof ↗
Attestable · 2026 · Attestable blog
Supports: 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)
Locator: whole post
Version and catalogue details
- Source review date
- 2026-09-25
- Drafted by (source map)
- ai
- Review handles (source map)
- codex-review