GitHub (new tab)

Learn · For prover teams and engineersGlossary

Proving a forward pass

The verifier tests the prover's committed values at random points. Matrix products with the committed weights are the cheap part to prove.

3 of 3

Take one reply on Llama 3.1 8B Instruct. Checking it means checking a pass of a quantized copy over the 1,024 tokens of prompt and reply. At two operations per parameter per token, attention aside (Kaplan and others (new tab)), that is about 1.6 × 1013 operations. A verifier on a CPU does not redo them.

Instead, the prover commits to the weights once and, for each proof, to values of the pass. Then the verifier draws each test point after the prover has committed the values that point tests. Read as polynomials, a pass with one wrong value differs from the honest pass almost everywhere (Schwartz-Zippel (new tab)). So a few points catch it, except with a probability that the security level bounds.

  1. Embedlook up one row of a table per token
  2. Normalisedivide by a root mean square
  3. Attention: projectmultiply by weight matrices× committed weights
  4. Attention: mixmultiply activations by activations, take a softmax, multiply again× activations
  5. MLP: projectmultiply by weight matrices× committed weights
  6. MLP: activateapply a fixed curve to each number
  7. Unembedmultiply by a weight matrix× committed weights
  8. Choosetake the largest of the vocabulary's scores

The steps from Normalise to MLP: activate repeat once per layer. A step with no tag needs more than additions and multiplications.

The three weight products hold most of the arithmetic. SASH's statement (new tab) says that inside its proofs, “each matmul is a Freivalds check against the committed weights”. FlashProve's guide (new tab) says its sumcheck and lookup arguments are designed to reduce the claim of a correct run to a few linear claims, inside a hash-based proof.

Testing a product at random

A prover claims that C is the n × n product A·B. To test it, the verifier draws a random vector r and compares A·(B·r) with C·r. That takes three matrix-vector products of n² each, where the schoolbook product takes n³. This test is called Freivalds' algorithm (new tab).

A
201
130
012
B
120
011
301
claimed C
541
154
613
arithmetic modulo 97
r
1
0
1
A·(B·r)
6
4
9
C·r
6
5
9

different: the claimed product is refused

r
1
1
0
A·(B·r)
9
6
7
C·r
9
6
7

equal: this draw misses the wrong entry

A draw misses the wrong entry only when r is 0 in that entry's column.

The test runs in a field. Arithmetic modulo 264 is not a field, and there an even entry of r times an error of 263 is 0, so the error drops out of C·r.

Fiat-Shamir

In place of the verifier's draws, each test point comes from a hash of the statement and the prover's messages. This is called Fiat-Shamir. The problem is a value left out of the hash, because the prover can then change it after the draw. Trail of Bits disclosed this bug in seven repositories (new tab) in 2022, and OtterSec in six zkVMs (new tab) in 2026.

From one product to a layer

A sumcheck tests an inner product by halving its vectors, one round per halving (Thaler's book (new tab), chapter 4). Each round, the prover sends a degree-2 polynomial s, the sum with the next index bit left as a variable.

a, the weights
2718
b, the activations
3141
arithmetic modulo 97

A lying prover claims the result 26

Running claimProver sends s(0), s(1), s(2)Verifier checksVerifier draws rNew claim s(r)
Round 12614, 12, 914 + 12 = 26, the running claim591
Round 29179, 12, 3279 + 12 = 91, the running claim1153

a(r)·b(r) = 65 · 28 = 74, and the last claim is 53: refused

An honest prover claims the result 25

Running claimProver sends s(0), s(1), s(2)Verifier checksVerifier draws rNew claim s(r)
Round 12513, 12, 913 + 12 = 25, the running claim585
Round 28573, 12, 3273 + 12 = 85, the running claim1174

a(r)·b(r) = 65 · 28 = 74, and the last claim is 74: accepted

This lie survives 384 of 9,409 pairs of challenges, under the bound 2·2/97.

After the last round, the verifier reads a(r) from an opening of the weight commitment. The other factor, b(r), is a claim on the layer before, and it is reduced the same way, down to the input tokens the verifier holds (GKR (new tab)). A whole matrix product takes one sumcheck, which costs the prover n² work on top of the product's n³ (Thaler, 2013 (new tab)).

Lookups

Steps such as the softmax and the activation curve are not products with the weights. Provers check them against public tables of valid input-output pairs. This is called a lookup argument (new tab).

On GPT-2 (BaseFold, sequence length 512, 48 threads), DeepProve (new tab)'s authors find that “more than 50% of the prover cost comes from activation functions, Softmax, and requantization”, in both the interactive proof and the commitments. We did not measure this, because the harness times each prover from outside.

One pass for a whole reply

Generating a 512-token reply takes 512 passes in a row, but proving it can take one. DeepProve runs the model once on the prompt and the claimed reply. With the causal mask and a deterministic argmax, “the model's prediction at position t certifies the token at position t+1” (its README (new tab)). FlashProve proves a window of tokens (new tab) in one pass, and SASH a grid of segments joined at the seams.

Zero knowledge

When the prover commits to the weights, for example as the root of a Merkle tree, it is bound to them, but that alone does not keep the proof from revealing them, which takes zero knowledge on top. Each opening reveals a linear equation over the weights, so an opening does not hide them. For the Confidentiality petal, we read what publishers state and prove.

A verifier works at its random test points and on the openings there, not on the whole pass, and its cost differs by system (verify time on the ladder).

What an accepted proof rests on

If the verifier accepts a proof, at least one of four things is true: the statement holds, the draws hit a point where two different polynomials agree, an assumption broke, or the verifier has a bug.

The Ethereum Foundation writes (new tab) that many STARK-based zkEVMs rely on conjectures: “Each conjecture that falls takes bits of security with it: what was advertised as 100 bits might actually be 80.” No test tells 60 bits from 128 short of a 260 search, so for the Integrity petal we read the bound each publisher states.