Cheap verification

Here is a fact that sounds too good to be true: you can check that someone multiplied two big matrices correctly with far less work than doing the multiplication yourself.

It’s the key idea behind any proof of work that isn’t hashing. Mining has to be expensive; checking it has to be cheap, because every node checks every block. This page shows a classic trick for cheap checking, Freivalds’ check, and why Pearl needs something stronger.

Try it

Someone claims a product C = A·B, and may have cheated on a cell or two. Catch them with random vectors instead of redoing the work.

How does Freivalds’ check work?

Instead of recomputing A·B, pick a random vector x of 0s and 1s and compare two things:

$$A \cdot (B \cdot x) \;\overset{?}{=}\; C \cdot x$$

Freivalds, 1977

If C really is A·B, both sides are always equal. If C is wrong, they usually differ. A worked example with a cheat:

How sure can you be?

One random check catches a wrong answer with probability at least ½. Repeat with fresh random vectors and the chances of missing multiply:

That probability of being fooled measures the check’s soundness. Using random numbers from a bigger range than 0 and 1 makes each round stronger still.

Why at least one half?

Let D = A·B − C. If C is wrong, D has a non-zero entry, say in row i and column j. The check passes only if (D·x)_i = 0, which is D_ij·x_j plus terms that don’t involve x_j. Fix all the other coordinates of x. Of the two choices x_j = 0 or 1, at most one makes the sum zero, since D_ij ≠ 0. So at most half of all vectors pass.

And the saving grows with size. For n = 8,192, a full multiplication is n³ ≈ 5.5 × 10¹¹ multiply-accumulates; a Freivalds round is about 3n² ≈ 2.0 × 10⁸. That’s about 2,700 times cheaper.

Why doesn’t Pearl use it?

Three reasons, each important.

1. Nodes never see the matrices. Freivalds needs A, B and C in hand. The matrices declared in block 130,825’s certificate are about 1 GiB and 2 GiB. A node receives 164 bytes of public data and a proof, nothing more.
2. The final product isn’t enough. A Pearl ticket is built from each tile’s running sums at every checkpoint, then hashed. Freivalds can check a final product but says nothing about intermediate sums or hashes (see rank and noise for why the intermediate sums matter).
3. Privacy. A miner’s matrices may be a company’s AI model and its users’ data. A public check shouldn’t reveal them.

So Freivalds is the right intuition (checking can be vastly cheaper than doing) but not the mechanism. Pearl’s mechanism is a zero-knowledge proof.

How cheap is Pearl’s check?

Very. The certificate’s proof is about 59,560 bytes whatever the matrix sizes, and a node verifies it in about 7–21 ms.

Work behind a block

≈ 1.13 × 10²² MACs

expected, at the snapshot difficulty

Winning tile

1,048,576 MACs

128 cells × k = 8,192

Proof

59,560 bytes

constant size

Prove

5.7–17 s

once per block found

Verify

7–21 ms

by every node

Light clients

verify too

every header’s certificate

That asymmetry, from about 1.13 × 10²² multiply-accumulates of network work down to milliseconds of checking, is what makes a matrix-multiplication blockchain possible.

Make a guess

A pool receives a miner's winning share: the tile's 2 rows of A and 64 columns of B, with their Merkle paths. How can the pool check it without a zero-knowledge proof?

Think of your answer first, then check it.

Reveal the answer

Answer By recomputing that one tile.

The share reveals the actual rows and columns, so the pool can verify the Merkle paths against the fingerprints, regenerate the noise for those rows and columns, and redo the tile’s 1,048,576 multiply-accumulates. That’s cheap. The catch is size and privacy: a share is about 552 KB at k = 8,192, and it reveals real data. That’s why the pool then turns it into a ~60 KB zero-knowledge certificate for the chain.

Who checks what?

Pearl’s checking happens in layers, each cheaper and more public than the last:

1. The GPU checks every ticket

   As the multiplication runs, each tile’s ticket is compared on the chip with the pool’s easier share target. Almost all are thrown away.

2. The pool checks a share

   It verifies the revealed rows and columns against the fingerprints and recomputes the tile.

3. The gateway proves

   For a ticket that also beats the network target, it builds the zero-knowledge certificate (seconds of work, once per block).

4. Every node verifies

   Each node, and each light client, checks the certificate against the header in milliseconds, without ever seeing a matrix.