Proof of Useful Work
from the Ground Up

Let's start at the very bottom. A matrix is a grid of numbers. Matrix multiplication takes two grids and produces a third.

The rule for computing each output cell is: take a row from the first matrix and a column from the second, multiply the corresponding elements together, and add up the results. This is called a dot product.

Here's the simplest case. One row, one column:

Two multiplications and one addition. This single operation, multiply pairs and sum, is called a multiply-accumulate (MAC). It's the atom of AI computation. Everything in modern AI is built from this.

Now scale up. Below is a 2×3 matrix multiplied by a 3×2 matrix, producing a 2×2 output. Each output cell is one dot product.

Notice what happened: each dot product required 3 MACs (because the shared dimension is 3), and we needed 4 dot products (because the output is 2×2). That's 12 multiplications total.

The pattern is general. For matrices with dimensions M×K and K×N, the output is M×N, and each of the M×N output cells requires K multiply-accumulates. Total:

That formula is the reason AI is expensive.

This operation, multiplying two matrices, is called GEMM: General Matrix Multiplication. When people say “AI runs on matrix multiplication,” they mean GEMM. When people say there's a global GPU shortage, what they mean is that the world's demand for GEMM exceeds supply.

Matrix multiplication is fundamental to machine learning because it encodes the transformation of data from one representation into another: a (learned) change of basis: mapping an input X into a new space Y where useful patterns become easier to detect (e.g., sparsity, invariances, spectral decay etc.).

Indeed, a core underlying assumption in ML is that some structure exists in data, albeit not necessarily in its raw form. Training statistical models can be viewed as the process of finding representations that uncover patterns in the input layer's signal. Matrix multiplication encodes a linear transformation that enables this process. For example, MLP layers project activations into new feature spaces, while attention layers use learned projections to form queries, keys, and values. In both cases, matrix multiplication is what turns raw inputs into useful representations.

A CPU computes one (or a few) operations at a time. It has a small number of powerful cores. A GPU has thousands of weaker small cores that each compute one multiply-accumulate simultaneously.

Look at our 2×3 times 3×2 example again. There are 4 output cells, each independent of the others. A CPU computes them one after another, 4 sequential steps. A GPU computes all 4 in parallel, 1 step.

This is why NVIDIA's market cap has exceeded $4 trillion. This is why there are multi-billion-dollar data center buildouts. The world needs an unimaginable number of GEMM, and GPUs remain the dominant hardware for this workload.

It's also why Pearl mining runs on GPUs, not ASICs (Application-Specific Integrated Circuit). GEMM is the native operation of GPU silicon. Bitcoin miners need custom chips because GPUs aren't efficient at hashing. Pearl miners just need the GPUs they'd already want for AI inference.

Now that you know what a matrix multiplication is, let's see why AI is built entirely out of them.

A neural network layer takes an input, multiplies it by a matrix of learned “weights,” adds a bias, and applies a nonlinear function. Let's build this up piece by piece.

That's the whole thing. A neural network layer is a matrix multiplication, plus one small addition (bias) that is computationally trivial by comparison. The next step is activation functions that are non-linear but usually represent less than 5 percent of the compute used by a neural network.

Now, a transformer (the architecture behind GPT, Claude, Llama, Gemini, and every modern LLM) is a specific arrangement of these layers. Each “transformer block” contains two major sections, and each section is built from GEMMs.

Q = input × W_Q    // "Query"  what am I looking for?
K = input × W_K    // "Key"    what do I contain?
V = input × W_V    // "Value"  what information do I carry?
output = attn(Q,K) × V × W_O   // combine and project

hidden = input × W_up      // expand: 4096 → 14336 dimensions
gate   = input × W_gate    // gating (in SwiGLU architectures)
output = (hidden ⊙ gate) × W_down   // contract: 14336 → 4096

That's ~7 GEMMs per transformer block. A model like Llama 3 8B has 32 blocks. Llama 3 70B has 80.

Every one of those MACs is a multiplication and an addition inside a GEMM. This is what Pearl miners compute. The exact same GEMMs that every AI inference provider on earth (OpenAI, Anthropic, Google, every startup hosting a model) is running right now.

Here is the problem that blocked “useful” proof of work for 15 years. It's subtle, and it's worth understanding precisely.

In Bitcoin, mining is hard and verification is trivial:

// Mining: try ~10²¹ nonces to find one that works
for (let nonce = 0; ; nonce++) {
    const hash = sha256(blockData + nonce);
    if (hash < difficultyTarget) {
        return { nonce, hash }; // Found it!
    }
}

// Verification: compute ONE hash and check
function verify(blockData, nonce, target) {
    return sha256(blockData + nonce) < target;
}
// Cost: 1 hash. Takes nanoseconds.

The asymmetry is enormous. Mining costs ~10²¹ hash operations. Verification costs 1 hash operation. Any node in the network can verify a block on a Raspberry Pi.

Now imagine a miner says “I multiplied matrix A by matrix B and got C.” How does a verifier check?

The naive way: redo the multiplication.

function verifyNaive(A, B, claimedC) {
    const actualC = matmul(A, B);  // Full GEMM: O(n³)
    return matricesEqual(actualC, claimedC);
}
// Mining cost:       O(n³)
// Verification cost: O(n³)
// Ratio: 1. Useless.

If verification costs as much as the work itself, you haven't accomplished anything. Every verifier would need the same GPU as the miner. You can't build a decentralized network where every node needs an H100.

This is the fundamental challenge. Every previous attempt at useful PoW (protein folding, optimization problems, training runs) failed here. Either verification was as expensive as the work, or the verification required trusting a third party, which defeats the purpose of a decentralized system.

In 1977, Rūsiņš Freivalds published a beautifully simple result. You can probabilistically verify a matrix multiplication in O(n²) instead of O(n³).

Here's how it works. Given matrices A, B, and a claimed product C = A × B:

1. Pick a random vector r ∈ {0,1}ⁿ
2. Compute y₁ = C × r (one matrix-vector multiply: O(n²))
3. Compute y₂ = A × (B × r) (two matrix-vector multiplies: O(n²))
4. If y₁ = y₂, accept. Otherwise, reject.

Why does this work?

If C = A·B: Then C·r = A·(B·r) always. It follows from the associativity of matrix multiplication. The check passes every time.

If C ≠ A·B: Meaning at least one element is different, then C·r ≠ A·(B·r) with probability ≥ 1/2 for a randomly chosen r.

The intuition: r is a random projection that “samples” the disagreement between C and the true product. Any single projection has at least a coin-flip chance of landing on the error. Repeat with k independent random vectors and the probability of missing a cheater drops to 2^−k. At k = 10, that's a 99.9% catch rate.

But Freivalds gives you a proof of correctness, not a proof of work. It confirms the miner got the right answer but it says nothing about how much effort was spent getting there. There's no difficulty parameter, so no way to make the problem harder when more miners join. A miner who precomputed A·B last week passes Freivalds just as easily as one who computed it right now. Freivalds tells you what was computed. A proof-of-work protocol needs to tell you how much was computed, and make that amount tunable.

Another natural idea is to use zero-knowledge proofs to certify that an inference pass was executed correctly on a specified model. The thinking is that if the proof attests to a model whose execution in a timely manner requires significant computational resources, it could serve as a proof of useful work. In principle, that is very appealing: the prover could show that a model really produced an output without revealing internal weights or every intermediate activation. In practice, though, state-of-the-art ZK systems still impose too much overhead to serve as a practical proof layer for the frontier models that matter economically today. Modern LLMs live in the high tens of billions to trillions of parameters, which means enormous matrix multiplies, long activation traces, and many nonlinear operations that must be encoded into proof-friendly arithmetic. The result is that proof generation is still far more expensive than the lightweight verification a decentralized proof-of-work protocol needs.

One recent example is NANOZK, which proposes layerwise zero-knowledge proofs for verifiable LLM inference and reports meaningful improvements over earlier ZKML approaches. That is real progress. But translated into the latency budget of autoregressive generation, these numbers are still nowhere near production inference. A proved forward pass for GPT-2-scale models is measured in tens of seconds, not milliseconds: zkGPT reports under 25 seconds for GPT-2 inference, which is at best about 0.04 proved tokens per second if each next-token step is proved. NANOZK reports minutes for full GPT-2 verification under parallel proving, and zkLLM reports under 15 minutes for a 13B-parameter model. These are impressive cryptographic results, but they are many orders of magnitude away from the tens to hundreds of tokens per second expected from ordinary LLM serving. It is also a useful reality check: the paper's proof benchmarks are still at GPT-2 scale and below, on the order of roughly 124 million parameters rather than the tens of billions to trillions of parameters used by production frontier models. So while ZK inference is an active and promising research direction, it is not yet the mechanism that makes useful proof-of-work viable for most LLMs used in production today. And perhaps more importantly, the question becomes whether it will ever have practically equivalent or lower overhead for proof generation compared to cuPOW.

We've established the problem: verification of a matrix multiplication costs O(n³), the same as doing the work itself. Every previous attempt at useful proof of work died here. Let's see how cuPOW, the protocol introduced by Ilan Komargodski and Omri Weinstein in the PoUW paper, actually solves it.

The solution doesn't arrive in one step. It arrives through three ideas, each one fixing a flaw in the previous.

Idea 1: Add random noise

Start with two matrices A and B that a miner wants to multiply. Let's say, a weight matrix and an activation matrix from a real AI inference request. The product C = A·B is the useful result.

Now, here's our first idea on how to turn this into a proof of work. Instead of computing A·B directly, force the miner to compute:

where E and F are random matrices derived from a public seed σ (generated by hashing the block header, so the miner can't predict them in advance).

Why does this work as a proof of work? Because C' is the product of two random matrices. No matter what A and B the miner chose, (A+E) and (B+F) are random, which means C' is random too. The miner hashes C', and if the hash falls below a difficulty target, they win a block. Just like Bitcoin, except instead of hashing nonces, the miner is multiplying matrices.

But there's a fatal flaw. The miner needs to output the useful result C = A·B, not the noisy C'. To recover C from C', they need to “peel off” the noise:

That subtraction requires computing A·F and E·(B+F), two additional full n×n matrix multiplications. So the honest miner does 3 GEMMs total (one for C', two for denoising), while a cheating miner who doesn't care about the useful result only needs 1 GEMM to produce C' and check if its hash wins.

The honest miner works 3× harder than a cheater. That's not a proof of useful work; it's a proof of wasted work, just with matrices instead of hashes.

Idea 2: Make the noise low-rank

The problem was that peeling off the noise cost two full GEMMs. What if the noise were structured so that removing it is cheap?

Instead of making E and F fully random n×n matrices, construct them as low-rank matrices. Specifically, sample four smaller matrices, E_L and F_L of size n×r, and E_R and F_R of size r×n, and set:

where r ≪ n (think r = n^0.3, so for n = 4096, r ≈ 20).

E and F are still n×n matrices, but they each have only rank r. They look random (every r×r subblock is marginally uniform) but they have far less independent information than a truly random matrix.

The honest miner now does:

• 1 full GEMM: C' = (A+E)·(B+F), cost O(n³)
• Denoising: cost O(n²·r), negligible

Total overhead: O(n²·r)/O(n³) = O(r/n) = o(1). As matrix dimensions grow, the overhead vanishes.

But we've introduced a new problem. A cheating miner who picks A = B = 0 (the all-zeros matrix) reduces their task to computing E·F, the product of two rank-r matrices. And multiplying two rank-r matrices can be done in O(n²·r) time, massively faster than the honest O(n³). The cheater has an enormous advantage.

Idea 3: Prove the transcript, not the output

Here is the key insight of the paper. The two previous attempts both used the output of the computation, the final matrix C', as the source of hardness. Hash C', check if it's below a target. The problem is that clever attackers can compute the output without doing the full work.

cuPOW does something different. Instead of hashing the output, it hashes the transcript, the full sequence of intermediate results that accumulate during the block-by-block execution of the matrix multiplication.

Recall how the canonical matrix multiplication algorithm works on blocks. You partition A' = (A+E) and B' = (B+F) into r×r tiles, and compute the product iteratively:

where i, j, ℓ range over the n/r block indices. Each step multiplies one r×r tile from A' by one r×r tile from B' and adds it to a running sum. The full computation produces (n/r)³ intermediate r×r matrices. This sequence (every intermediate partial sum at every step) is the transcript.

Now the miner hashes this entire transcript and checks if the hash falls below the difficulty target. The honest prover produces the transcript naturally; it's just the standard computation, recorded step by step.

But can a cheater produce the transcript without doing the full work?

This is where the low-rank noise pays off. Because E and F are random rank-r matrices, the noised matrices A' = A+E and B' = B+F have a crucial property: every r×r tile of A' and B' is marginally uniform; it looks completely random on its own. This means each intermediate product A'_i,ℓ · B'_ℓ,j is the product of two random r×r matrices, which cannot be computed faster than O(r³).

There are (n/r)³ such intermediates, each costing O(r³), giving a total of O(n³), the full cost of the GEMM.

“But wait,” you might think, “the intermediates are correlated; they share rows and columns from A' and B'. Can't the attacker exploit those correlations to compute multiple intermediates at once?”

The paper argues no. Recovering those correlations amounts to solving a batch of low-rank random linear equations, a problem for which no known algorithm is faster than performing the honest computation. This is the core security assumption of cuPOW.

The full cuPOW protocol:

The miner receives an inference request (matrices A, B) and a public seed σ (from the block header):

1. Encode: Derive low-rank noise matrices E = E_L·E_R and F = F_L·F_R from σ. Set A' = A+E, B' = B+F. Cost: O(n²·r), negligible.
2. Compute: Run the block matrix multiplication MatMul_r(A', B'), recording the full transcript of (n/r)³ intermediate r×r matrices. Cost: O(n³). This is the real work.
3. Hash: Hash the transcript. If the hash falls below the difficulty target, a valid proof is found.
4. Decode: Peel off the noise to recover C = A·B. Cost: O(n²·r), negligible.
5. Output: Return C to the AI client (the useful inference result) and submit the transcript hash as the proof of work.

The verifier receives (σ, A, B, transcript hash) and recomputes to check correctness.

Total overhead for the honest miner: O(n²·r) / O(n³) = O(r/n) = o(1). For the matrix sizes in modern LLMs, this is a fraction of a percent.

Advantage for a cheating miner: none. Computing the transcript honestly is the fastest known method. No shortcut exists.

Let's step back and appreciate what cuPOW achieves.

For almost 20 years, since Bitcoin launched in 2008, the question of useful proof of work was considered open, and by many, impossible. Vitalik Buterin called it “probably not feasible” in 2019. Ethereum's entire migration to proof of stake was partly motivated by the belief that proof of work could never be made useful.

cuPOW resolves this for matrix multiplication, the single most economically valuable computation in the world. The construction is not a brute-force trick or a clever hack. It follows from a structural observation about matrix multiplication: that the transcript of a block computation over randomly-perturbed matrices is inherently hard to produce without doing the actual work, even when the noise is structured enough to be peeled off cheaply.

The overhead is 1+o(1) and vanishes as matrices grow. The security reduces to a concrete algebraic problem (low-rank random linear equations). And because matrix multiplication is AI inference, the useful work has an immediate, enormous market of paying customers.

A single computation simultaneously serves an AI client and secures the blockchain. The energy spent mining Pearl is not wasted; it's the energy cost of AI inference that would have been spent anyway. Pearl just lets the miner get paid twice for it.

Every PRL in existence was minted through verified GPU computation: the actual matrix multiplications that served a real inference request. Token mining is physically bounded by the amount of GPU capacity dedicated to the network. You cannot mint PRL faster without deploying more hardware and doing more useful work.

That makes PRL supply a direct function of the scarcest resource in the global technology economy. GPU demand is growing exponentially. Supply trails by years. Every hyperscaler, every startup, every sovereign fund is competing for the same chips. NVIDIA's lead times stretch past a year. New fab capacity takes three to five years to come online. The bottleneck that constrains PRL issuance is the same bottleneck the entire AI industry is throwing hundreds of billions of dollars at.

No other digital asset has this property. Bitcoin's scarcity is enforced by an arbitrary difficulty adjustment over computation. The energy is spent, the hash is checked, the result is discarded. PRL's scarcity is enforced by the physical availability of GPUs doing work the market is already desperate to buy. The computation isn't discarded; it's delivered to a customer.

This distinction matters for how you think about the asset long-term. Bitcoin's value rests on a social consensus that scarce-because-the-protocol-says-so is valuable. That consensus has proven remarkably durable, but the scarcity is ultimately circular. PRL's scarcity is grounded in something external to the protocol: the supply-demand imbalance of AI compute. As long as the world needs more inference than it can supply, and every credible forecast says that gap is widening, the resource that backs PRL issuance becomes more constrained, not less.

The equilibrium is self-correcting. If PRL trades below the cost of the GPU-hours required to mint it, rational miners redirect hardware to selling inference directly. If PRL trades above that cost, new miners join, expanding both supply and the network's total inference throughput. The token price gravitates toward the real economic cost of AI computation. And as demand for inference grows faster than GPU supply, that floor rises.

Bitcoin proved that a decentralized network can produce trustless digital scarcity. But Bitcoin's scarcity is self-referential; tokens are scarce because the protocol says so, secured by energy that vanishes after use.

Pearl's scarcity is inherited. It comes from a bottleneck that exists independent of the protocol: the global shortage of AI compute. Every token is a receipt for verified useful work that the market was already willing to pay for. The constraint isn't designed. It's physical.