Tool · Mining

Freivalds' check

Catch a wrong matrix product without redoing it

Freivalds’ check

Catch a wrong matrix product without redoing it

The prover is

Size n

−1−1−2−1044−2−13−3−21−2−45

1−3−3−3−14−123−5−4−4−30−41

claimed C · one cell may be off

−3916814−6−12−10−7302019−249−514

Show me the wrong cell

Random 0/1 vector r · tap to flip

B·r

−50−5−6

A·(B·r)

21−832−15

C·r

21−832−15

Press Check to compare A·(B·r) with C·r.

Confidence after 0 passing checks in a row

0% sure. A wrong C survives one random check with chance at most ½, so after 0 passing checks the chance it slipped through is at most 1 in 1.

Work per check

one check: B·r, A·(B·r), C·r: 3n² = 48
redo the product: n³ = 64
at n = 8,192: 201 M vs 550 G · 2,731× cheaper

Multiply-accumulates. The saving grows with n: at toy sizes it barely shows.

Intuition only This shows why checking can be far cheaper than doing. Pearl’s nodes don’t run Freivalds’ check: they verify a ~60 KB zero-knowledge certificate (a STARK wrapped in two Plonky2 layers) that proves the winning ticket came from the committed matrices, with the right noise, without ever seeing A or B.

Runs in your browser · nothing is sent src/lib/miner.ts · matMul

What it does

A prover hands you A, B and a claimed product C. Switch it between honest and a cheater (one cell quietly off by a little). Instead of multiplying A·B yourself, pick a random vector r of 0s and 1s and compare A·(B·r) with C·r.

How to read it

B·r, then A·(B·r), then C·r: three matrix-times-vector products, n² multiply-accumulates each.
If the two columns differ anywhere, C is wrong. That’s proof, not luck.
If they match, C might still be wrong: a single bad cell in column j hides whenever r has a 0 at position j. That happens half the time, so k passing checks in a row leave at most a 1 in 2ᵏ chance of a cheat. 10 random rounds shows how fast that shrinks.
The cost box compares 3n² per check with n³ to redo the product. At toy sizes the saving is small; at n = 8,192 one check is about 2,700 times cheaper.

Pearl specifics

This is intuition for why checking can be far cheaper than doing. Pearl does not use Freivalds’ check. A winning ticket is proven with a zero-knowledge certificate (a STARK wrapped in two Plonky2 layers, about 60 KB) that shows the ticket came from the committed matrices with the right noise, and nodes verify it in milliseconds without seeing A or B.

What’s simplified

Small matrices (3, 4 or 6 wide) with entries from −5 to 5, and a cheater who changes exactly one cell. Freivalds’ bound of ½ per check holds for any wrong C; with one bad cell it is exactly ½.

Under the hood

Runs entirely in your browser. Products come from matMul in src/lib/miner.ts (unit-tested with the toy miner’s denoising identity); random vectors come from your browser’s cryptographic generator.