Proofs of useful work and resource exhaustion

How it works

Proofs of work. A proof of work gives confidence that some declared amount of computation took place. In cryptocurrency mining, workers hash variants of a message until one hash meets a target, and a verifier can check it quickly ⁸. Scher and Thiergart note that applying proof of work "could verify that compute declared to be doing crypto mining is indeed doing it" ⁸.

Proofs of useful work. A proof of useful work (PoUW) makes that computation serve another purpose. Ball et al. gave constructions for problems such as Orthogonal Vectors, 3SUM and All-Pairs Shortest Path ⁷. Komargodski and Weinstein give a PoUW for arbitrary matrix multiplication, which lets the miner choose its own matrices ¹. Their protocol works in three steps ¹:

1. Low-rank random "noise" matrices are derived from public randomness and added to the inputs.
2. The noised product is computed in blocks, and the transcript of intermediate blocks is hashed.
3. A hash below a difficulty threshold is a winning proof.

The noise can then be subtracted cheaply to recover the useful product ¹. Hardness rests on the transcript rather than the output, so choosing trivial matrices gives no shortcut ¹.

Pearl's variant. Pearl's floating-point specification adapts this to FP8 matrix multiplication on GPUs ²:

• quantising after the noise is added lets output tiles be hashed directly;
• the verifier "checks one tile of the matmul, never the whole product", recomputing it bit for bit ².

Use for resource exhaustion. Attestable proposes proof-of-work accounting to bound compute available for unmonitored activity ⁶. In its scheme, "Useful, approved inference contributes to the required work budget". When demand falls short, "additional protocol-defined work fills the shortfall" ⁶.

Memory analogues.

• Proofs of space require dedicating "a significant amount of disk space" ¹⁰.
• A verification system design proposes filling device memory with incompressible noise and challenging random samples ⁹ (see Memory wiping and proofs of secure erasure).

What it establishes

What it can establish.

• A valid proof of useful work shows that a stated amount of matrix-multiplication work was performed on inputs committed through the noise derivation ^{1 2}.
• If the verifier knows the capacity of declared hardware, a sustained rate of such proofs could bound the capacity left for other work. This is Attestable's proposal ⁶, and it bears on There is no undeclared relevant compute and Declared hardware is idle or shut down for declared hardware.

What it cannot establish.

• Undeclared hardware. Attestable states that a proof "cannot discover a datacenter that was never declared" ⁶.
• What the work was for. The proof does not show which AI workload, if any, the matrices came from. Komargodski and Weinstein do not address auditing whether matrices come from real AI workloads ¹. On Pearl's network, an independent study found that verification "does not check whether the matrices originate from an AI model" ⁵. Attestable proposes pairing work accounting with proofs of inference for that ⁶.

Threat model

The adversary is a miner who tries to produce accepted proofs faster than honest work would allow ¹. Security holds in the random-oracle model under a "direct-product" hardness assumption about intermediate values of multiplying random low-rank matrices ¹. Pearl's variant assumes that computing quantised products of noised matrices "is not substantially easier than generic quantized products" ². It also relies on deterministic, reproducible GPU arithmetic for bit-exact verification ².

For capacity bounding, the verifier also needs "a credible estimate of the compute available" to the actor ⁶.

Evidence

• Theory. Komargodski and Weinstein prove a multiplicative overhead of 1 + o(1) over naive matrix multiplication ¹.
• Pearl. Pearl publishes the code of a network built on this construction ⁴, and reports that the chain went live when the node code became public ³. It also reports a benchmark on four H200 GPUs. Its "two-for-one" variant of Llama 3.3 70B, which re-implements a layer with a new quantisation mechanism, reached up to 18,291.66 tokens per second. The original model's best configuration reached 15,269.81 tokens per second; with the four-way data parallelism that gave the variant its best figure, the original bf16 model ran out of memory ³.
• Independent measurement of Pearl. Basu studied Pearl's mainnet in May 2026. String analysis suggests that the dominant mining software, from a third party, contains no inference code and generates matrices from random seeds. Random matrices passed verification in the study's tests ⁵.
• Capacity bounding. As of September 2026 no public result applies proofs of useful work to bounding the capacity of declared AI hardware. Attestable describes its proposal as near-term work ⁶.

Limitations

Verification cost. Komargodski and Weinstein note that plain verification is "relatively expensive on the verifier's side", and suggest the prover can use a zkSNARK to lighten it ¹. They also note that storing the transcript takes significant memory ¹.

Known shortcuts. Pearl lists known mining speedups: crafted inputs, precision shortcuts, seed grinding and work reuse. It adds checks to limit them ². It describes faster kernels or hardware as "not an attack on the protocol" ².

Assumptions and scope. Open problems include PoUW from more standard assumptions, and PoUW for tasks beyond matrix multiplication ¹.