Proof of useful work diagram one matrix multiplication produces both a new block and AI training work

Proof of Useful Work Turns GPU Matrix Multiplication Into Blockchain Consensus

matrix multiplication, proof of useful work, proof of work

Proof of useful work (PoUW)

A consensus mechanism in which miners perform computation with value outside the blockchain, such as neural network training on GPUs, instead of hashing block headers with SHA-256. Each attempt still succeeds with a fixed, tunable probability, so block arrival and difficulty adjustment work as in Bitcoin.

Why SHA-256 Mining Leaves No Reusable Output

Proof of useful work (PoUW) replaces the SHA-256 hashing of Bitcoin mining with computation of value outside the blockchain, including neural network training on GPUs. Bitcoin miners run application-specific chips and test block headers against a difficulty target; miners discard every hash missing the target. A proof of useful work protocol keeps the security role of hash-based mining and directs the discarded effort toward matrix multiplication, the operation AI workloads already pay for.

Bitcoin verifies work with a single hash: a node recomputes the SHA-256 digest of the block header and checks the value against the target. The protocol retargets difficulty every 2,016 blocks to hold block intervals near ten minutes, which ties the cost of finding a block to hash rate rather than a fixed price. The Cambridge Bitcoin Electricity Consumption Index estimates network power demand from assumptions about mining hardware efficiency and electricity prices.

Ethereum moved from proof of work to proof of stake in 2022 and replaced hash-based energy use with locked capital. A proof of useful work design pursues the same energy objective without a stake requirement: the scarce resource remains computation, and the network keeps the permissionless entry of mining.

Conditions a Useful Work Function Must Meet

A proof of useful work scheme needs three properties at once: economic value, meaning a customer pays for the computation result; efficiency, meaning miners run a near-optimal algorithm for the task; and security, meaning no participant passes verification with less computation than an honest miner spends.

Nakamoto consensus adds a fourth condition: each attempt succeeds with a fixed, tunable probability, which gives block arrival a Poisson process and keeps difficulty adjustment working as in SHA-256 mining.

Earlier designs show how hard a proof of useful work is to build with usefulness, efficiency and security in one consensus rule. Primecoin searches for Cunningham chains of prime numbers, links each chain to the block header hash to block reuse across blocks, and retargets difficulty on every block; the chains have no paying customer.

Ofelimos, presented at CRYPTO 2022 and developed at IOG, lets miners run Doubly Parallel Local Search on optimization instances clients post to the ledger, with locked funds as payment. Generic useful tasks carry a risk: an attacker steers the network toward instances the attacker solves cheaply, which weakens the security model.

Proof of useful work designs compared: Bitcoin SHA-256, Primecoin, Ofelimos, cuPOW and Qubic by work function and reusable output
Figure 1. Useful work designs compared with SHA-256 mining

Matrix Multiplication as the Mining Task

Matrix multiplication dominates the cost of neural network training and inference: forward and backward propagation in large language models multiply matrices with tens of thousands of rows and columns, and GPUs specialize in the operation. The cuPOW protocol defines a proof of useful work over arbitrary matrices: a miner submits the product A·B from its own training job and produces a valid mining certificate.

cuPOW proof of useful work flow: block seed, low-rank noise, block-wise matrix product, transcript hash and noise removal
Figure 2. cuPOW mining flow for one matrix product

The protocol hides the miner’s inputs behind low-rank noise: a miner derives four small matrices from the block seed and the inputs through a random oracle, builds noise matrices E and F of rank r, and multiplies (A+E) by (B+F). Noise removal costs O(n²·r) operations, far below the O(n³) cost of the product for small r; the miner recovers the exact result A·B at 1+o(1) multiplicative overhead.

Bar chart of noise removal cost as a percentage of matrix product cost for matrix sizes from 1,024 to 65,536 in GPU mining
Figure 3. Noise removal cost as a percentage of matrix product cost for matrix sizes

The hash covers the transcript of the block-wise multiplication, not the final product, and every intermediate r×r block feeds the lottery. Low-rank noise makes the final product cheap to compute for trivial inputs, including all-zero matrices, and an attacker would skip the work. Transcript hashing removes the shortcut: each noisy block demands a full r×r multiplication.

Deterministic Difficulty and Instant Verification

The miner hashes the transcript and compares the digest with a threshold; each attempt succeeds with probability ε regardless of the chosen matrices. A constant success probability preserves the Poisson arrival process of blocks, and the network can retarget the threshold every 2,016 blocks as Bitcoin retargets its SHA-256 target.

Larger matrices produce more intermediate blocks, and the protocol can hash each block separately to scale the number of attempts with the work performed. A proof of useful work network keeps a deterministic difficulty rule with no change to block-time statistics.

Verification cost remains the main engineering question: a verifier without extra tooling recomputes the miner’s work to check the digest, which removes the single-hash check of SHA-256. The proposed fix asks the miner to attach a SNARK, or a zkSNARK for private matrices, proving the verifier would accept the proof.

A valid proof appears rarely; the miner generates the SNARK on success only, and the proving cost amortizes across all failed attempts.

Verification methods for useful GPU mining work: single-hash check, full recomputation, SNARK on success and refereed delegation
Figure 4. Verification methods for GPU mining work

Bit-exact reproducibility matters for consensus: floating-point addition depends on operation order, and different GPU kernels accumulate sums in different orders. Reproducible Operators (RepOps) from Gensyn fix the order of operations for common machine learning operators, including matrix multiplication, and return bitwise identical results across hardware.

A proof of useful work network needs the same property, or integer arithmetic, to give every node an identical transcript.

Verifying Training Work Without Repeating It

Training runs add a verification problem beyond single products: a full run contains millions of steps. Proof-of-Learning logs training checkpoints and lets a verifier re-execute the steps with the largest weight updates; later work demonstrated spoofing attacks against the original scheme. Verde, a protocol from Gensyn, applies refereed delegation: two or more providers run the same task, and a bisection game locates the first training step and operator with diverging outputs, which lets the referee recompute one operator rather than the whole run.

Qubic directs miner computation toward training artificial neural networks in its Aigarth system and validates results through a quorum of nodes called Computors, a trust model different from a cryptographic proof. The comparison matters for blockchain consensus design: a quorum vote, a SNARK and a refereed dispute give different guarantees on cost, trust assumptions and latency, and each proof of useful work protocol picks one per workload type.

Security Assumptions Behind GPU Proof of Useful Work

The security of cuPOW, a proof of useful work for matrices, rests on a conjecture and not on a proof: computing the transcript of noisy low-rank products requires essentially the work of the honest algorithm, which reduces to solving a batch of low-rank random linear equations.

Each intermediate block taken alone multiplies two uniformly random matrices; no single block admits a shortcut without a speedup for random matrix products, and the correlations between blocks hold the open question.

Fast matrix multiplication algorithms in the Strassen family cut asymptotic cost and run poorly on GPUs, with memory demands and large constants; the protocol analysis takes naive multiplication as the baseline and keeps its security argument valid against attackers using faster algorithms.

SHA-256 ASICs cannot run dense matrix workloads, and the reward structure pays GPU owners block rewards for the computation training or serving their models, an arrangement the proposal describes as 2-for-1.

Security rests on a conjecture

The security of cuPOW is not formally proven. It depends on the conjecture that computing the transcript of noisy low-rank products requires essentially the work of the honest algorithm. Correlations between intermediate blocks remain an open question, so read the security claim as a working assumption rather than a theorem.

FAQ

What is proof of useful work?

Proof of useful work (PoUW) is a consensus mechanism that replaces the SHA-256 hashing of Bitcoin mining with computation that has value outside the blockchain, such as neural network training on GPUs. It keeps the security role of hash-based mining and directs the discarded effort toward work a customer pays for.

How does proof of useful work differ from proof of work?

Bitcoin miners test block headers against a difficulty target and discard every hash that misses it, using ASICs that run no other workload. A proof of useful work network keeps the same lottery and difficulty adjustment, but the miner’s computation, such as matrix multiplication, produces a result someone needs. Ethereum removed hash-based energy use by moving to proof of stake in 2022. Proof of useful work pursues the same energy goal without a stake requirement: computation stays the scarce resource and entry stays permissionless.

Why use GPU matrix multiplication as the mining task?

Matrix multiplication dominates the cost of neural network training and inference, and GPUs specialize in it. The cuPOW protocol lets a miner submit the product A·B from its own training job and still produce a valid mining certificate. Low-rank noise hides the inputs, and removing it costs O(n²·r) operations against O(n³) for the product, a 1+o(1) multiplicative overhead.

How do nodes verify useful work without repeating it?

Without extra tooling, a verifier recomputes the miner’s work, which loses the single-hash check of SHA-256. The proposed fix is a SNARK (or zkSNARK for private matrices) attached only when an attempt succeeds, so the proving cost amortizes across all failed attempts. Bit-exact results across GPUs also matter, and Gensyn’s Reproducible Operators (RepOps) provide them. For full training runs, Verde uses refereed delegation: a bisection game finds the first diverging step, so the referee recomputes one operator instead of the whole run.

Is GPU proof of useful work secure?

Its security rests on a conjecture, not a proof. The conjecture says that computing the transcript of noisy low-rank products requires essentially the work of the honest algorithm. Each intermediate block taken alone multiplies two uniformly random matrices, so the open question is the correlation between blocks. The analysis uses naive multiplication as the baseline and holds against faster algorithms such as the Strassen family, which run poorly on GPUs.