Game · medium · 7 min

Verify or Bust

Catch the provers who lie about a matrix product, on a budget

Checking a product can cost far less than computing it
Random spot checks and 1 − 2^−k confidence
Why the saving grows with the size of the matrices
The intuition behind Pearl's small, fast certificate

Verify or Bust

Catch provers who lie about a matrix product

Best—

Arcade · verification

Provers claim they multiplied two matrices. Some lie about one cell. Catch every liar without blowing your budget.

Recompute the whole product (n³ work), or spot-check it with a random 0/1 vector (about 3n² work, catches a bad cell half the time). Then accept or bust.

Accept only when you are at least 99% sure. Letting one cheater through ends the level.

S spot check (Freivalds)
R recompute everything
C read the certificate (level 3)
A accept
B bust

Costs are counted in multiply-adds. The certificate in level 3 is an intuition for Pearl’s zero-knowledge proof, not how it works.

Levels

Best —

Runs in your browser · scores stay on this device src/lib/miner.ts matMul · Freivalds’ algorithm

How to play

Each round a prover shows you two matrices A and B and claims a product C. Some provers cheat by changing a single cell of C. You have a budget of work, counted in multiply-adds, and three tools:

Recompute the whole product: n × n × n multiply-adds. Certain, and cheap for tiny matrices, ruinous for big ones.
Spot check with a random vector r of 0s and 1s: compare A·(B·r) with C·r. That’s three matrix-vector products, about 3n² multiply-adds. A single wrong cell slips past one check exactly half the time, so after k clean checks you’re 1 − 2^−k sure. Seven clean checks put you over 99%.
Read a certificate (level 3, when the prover attached one): a fixed small cost, whatever the size.

Then accept or bust. Accepting a cheater ends the level. Busting an honest prover costs points. Accepting below 99% earns less, even when you’re right, and unused budget becomes a bonus.

Keyboard: S spot check, R recompute, C certificate, A accept, B bust.

What’s real and what’s simplified

Real: the products and checks are computed in your browser with the same matrix code the site’s toy miner uses. A spot check is Freivalds’ algorithm, and the confidence meter is its exact bound for a single wrong cell. Level 3 uses 96 × 96 matrices with entries from −64 to 64, the same range as Pearl’s mining matrices.
Simplified: the certificate here is a stand-in. Pearl’s real certificate is a zero-knowledge proof (a STARK wrapped in two Plonky2 layers) that the block’s winning ticket came out of the committed matrices. It doesn’t prove a whole product, and nobody uses Freivalds checks in Pearl’s consensus. What carries over is the shape of the idea: checking can be far cheaper than doing, and a proof can be checked in milliseconds however big the job was.