The Complete Proof

The last five chapters each built one part of a proof. This chapter puts them together and runs the result on the statement $x^3+x+5=35$ with $x=3$, with every commitment computed on the toy curve and every check carried out.

The result is called a NARK, a non-interactive argument of knowledge. The name leaves out the S of SNARK because this proof is not succinct, and we look closely at where its size and its verification cost come from. Those costs are what the rest of the site works to remove, so the chapter ends with an exact list of the verifier steps that remain linear.

1. What the complete proof has to do

The earlier chapters supply these parts:

Assembling them raises three questions that no single chapter answered. The first is the order of the messages, since each challenge has to come after the data it tests. The second is how the verifier knows that the commitments it holds describe the right polynomials. The third is how much of each polynomial the verifier needs to see. The Ragu Book's NARK answers the third question by sending several whole polynomials in the clear. We follow that construction first, and Section 17 shows the shorter proof that the same parts can produce.

2. The running example

The circuit is the one from the arithmetization chapter, with $n=2$ gates, so every polynomial has $4n=8$ coefficients. We reuse that chapter's challenges, $z=5$ and $y=7$, and the witness with $x=3$. These are the polynomials the protocol works with:

A commitment to 8 coefficients needs 8 generators, and the toy curve's public parameters have only four. We add four more points at unused $x$-coordinates, so that the generators are $G_0,\dots ,G_7$ together with the existing $H$ and $U$:

3. Choosing how to check the revdot product

The protocol from the polynomial encoding chapter checks the revdot product by splitting the product $r(X)b(X)$ into $c_1(X)$ and $c_2(X)$. That split keeps every polynomial within the degree limit, but the prover pays for it, because computing a product of this size takes FFTs:

The book counts at least 3 FFTs, over a domain with at least $8n-1$ points. For $4n=2^{13}$, that is at least $16,383$ points, and the next power of two is $16,384$.

There is a blunter alternative. If the prover sends the two vectors, the verifier can compute the revdot product itself with one multiplication per entry, and no product polynomial ever exists. This makes the proof much larger and removes the FFTs. The book chooses this direct check for its NARK and keeps the split for the places in the PCD tree where succinctness matters.

A shortcut that tests $a(x)b(x)$ at a random point against one committed polynomial does not work, for the reason from Section 11 of the encoding chapter. The product has degree up to $8n-2$, and the generators limit commitments to degree below $4n$.

4. Committing before the challenges

The consolidated equation only means something if $r(X)$ is fixed before $z$ and $y$ are known, as the arithmetization chapter showed. So the first message commits to the trace, and it also commits to the public input polynomial:

$$K=⟨\mathbf{k},\mathbf{G}⟩,\bar{R}=⟨\mathbf{r},\mathbf{G}⟩+{\gamma }_r\cdot H.$$

The bar marks a hiding commitment with a blinding factor. The book blinds the polynomials that hold witness data and leaves the public ones unblinded, which is the same as using a blinding factor of zero. Section 13 discusses how much this blinding achieves.

The public input polynomial is $k(Y)=30Y^3$, so $K=30\cdot G_3=(27,1)$. The trace commitment with the blinding factor ${\gamma }_r=17$ is $\bar{R}=⟨\mathbf{r},\mathbf{G}⟩+17\cdot H=(22,24)$. Without the blinding term the same vector would commit to $(4,25)$.

Tying K to the statement

The oracle protocol treated $k(Y)$ as shared knowledge, whereas the NARK has the prover send $K$. A verifier who wants to know about the public value 35 therefore has to connect $K$ to that value, and the book's list of steps does not say how. Checking the evaluation claims about $K$ does not do the job on its own, since those claims say only that $K$ is consistent with itself:

A prover with $x=4$ can commit to $k^{\prime }(Y)=25Y^3$ instead of $30Y^3$, which is the instance of the statement $x^3+x+5=30$. Its $K=(8,22)$ differs from the correct $(27,1)$, while the claims about $K$ are all true, and every other check passes. The proof is valid for $30$ and says nothing about $35$, so a verifier that accepts $K$ without comparing it would be misled.

In our run the verifier closes this gap by recomputing $K$ from the statement. We add this as an explicit step.

The verifier now sends the challenges $z$ and $y$.

5. Building the two multiplicands

The challenges turn the bivariate polynomials into univariate ones, so the prover can now compute the wiring polynomial $s(X,y)$ and the right factor. It sends a commitment to each of these, together with the claimed revdot value:

$$S=⟨\mathbf{s},\mathbf{G}⟩,\bar{B}=⟨\mathbf{b},\mathbf{G}⟩+{\gamma }_b\cdot H,c=k(y).$$

It also sends $\bar{A}$, the commitment to the left factor. In a standalone NARK the left factor is the trace, so $a(X)=r(X)$ and $\bar{A}=\bar{R}$. This looks redundant, and the book says so in a footnote. The two names exist because during recursion they differ. There, $\bar{R}$ holds one step's trace, and $\bar{A}$ holds an aggregate of many revdot claims.

With the vectors from Section 2, the prover computes $S=(7,6)$ with no blinding, $\bar{B}=⟨\mathbf{b},\mathbf{G}⟩+29\cdot H=(1,29)$, and $c=k(7)=30\cdot 7^3=13$ modulo 43. It also sets $\bar{A}=\bar{R}=(22,24)$.

The verifier could compute $S$ alone, so sending it may look pointless as well. The reason is that the next stages make claims about commitments, and $S$ has to be a commitment for those claims to include it. Later chapters reach a verifier that no longer sees the polynomials and holds only commitments, and these objects prepare for that.

6. Checking the wiring and the revdot product directly

The prover now sends the three vectors $\mathbf{s}$, $\mathbf{a}$ and $\mathbf{b}$, along with the blinding factors ${\gamma }_a$ and ${\gamma }_b$. This is the step that makes the proof long. In return, the verifier's checks need no cryptographic argument, since it can recompute everything it was told:

• It computes $\mathbf{s}$ from the circuit and $y$, and compares. The book calls this the wiring consistency protocol.
• It checks that $\bar{A}=\bar{R}$, because in this standalone protocol the book defines $\bar{A}$ to be $\bar{R}$. The book's verifier steps do not list this comparison, so we state it. Without it, a prover could pick a new $\mathbf{a}$ after seeing $z$ and $y$, and the early commitment $\bar{R}$ would constrain nothing.
• It recomputes $S$, $\bar{A}$ and $\bar{B}$ from the vectors, which shows that the vectors are the ones the prover committed to.
• It computes $⟨⟨\mathbf{a},\mathbf{b}⟩⟩$ and compares it with $c$. The book calls this the revdot product protocol.

The order of the messages matters here even though the check looks like arithmetic on public data. The prover sent $\bar{R}$ before it knew $z$ and $y$, and the comparison $\bar{A}=\bar{R}$ together with the recomputation of $\bar{A}$ shows that the vector $\mathbf{a}$ is the one behind that early commitment.

7. Tying b back to the trace

The revdot check accepts any $\mathbf{b}$ that produces the right number, and a prover can always find such a vector, since one linear equation leaves most of the entries free. Nothing so far requires $\mathbf{b}$ to be the specific vector $\mathbf{r}\circ {\mathbf{z}}^{4n}+\mathbf{s}+\mathbf{t}$. In polynomial form, the requirement is

$$b(X)=a(zX)+s(X,y)+t(X,z).$$

This is an identity between polynomials of degree below $4n$, so a test at one random point catches a difference, in the way the encoding chapter described. The prover has already fixed all three commitments, so the verifier can send a random $x$. The prover sends the three values, and the verifier computes $t(x,z)$ alone and checks

$$b(x)=a(xz)+s(x,y)+t(x,z).$$

The verifier sends $x=9$, so $xz=9\cdot 5=2$ modulo 43. The prover sends $a(2)=9$, $s(9,7)=23$ and $b(9)=35$. The verifier computes $t(9,5)=3$ alone and checks $9+23+3=35$.

The dilation works as it did in the encoding chapter, with the value of $a(zX)$ at $x$ coming from the same polynomial at the point $xz$. No separate commitment to the dilated trace exists, so a prover cannot substitute a different trace in the right factor.

The verifier already holds $\mathbf{a}$, $\mathbf{b}$ and $\mathbf{s}$, so it could compare them coefficient by coefficient, and a standalone NARK has no need for a random evaluation here. The book keeps the evaluation form because it is what survives in recursion, where the vectors are gone and only commitments and evaluation claims travel forward.

8. Batching the evaluation claims

The three values just sent, and the value $c$, are claims about committed polynomials. Taken with the recomputations in Section 6 they are redundant here, but we check them through the machinery that recursion will rely on, since the accumulation chapters work on claims of exactly this form. The list has four claims, each about its own polynomial:

The book's list has two further claims, about $a(0)$ and $k(0)$, which tie down a constant wire our toy circuit does not have. Section 14 adds that wire and shows the six-claim form that Batched Openings previewed.

Now we apply that chapter's reduction, using its weights, in which the first claim takes the highest power of $\alpha$ and $f$ takes the highest power of $\beta$. The quotients above come from synthetic division, which ignores the claimed value. The verifier sends $\alpha$ and the prover commits to the combined quotient:

With $\alpha =11$, the powers are ${\alpha }^3=41$, ${\alpha }^2=35$, $\alpha =11$ and $1$. The combination $f(X)=41q_0+35q_1+11q_2+q_3$ has coefficients $(13,4,12,3,31,17,2)$, and with the blinding factor ${\gamma }_f=5$ its commitment is $\bar{F}=(11,30)$.

The verifier sends a new point $u$, the prover sends one value per polynomial, and the verifier derives $f(u)$ from those values and the original claims:

$$f(u)=\sum _{i=0}^3{\alpha }^{3-i}\frac{p_i(u)-y_i}{u-x_i}.$$

At $u=17$ the prover sends $a(17)=42$, $b(17)=29$, $s(17,7)=35$ and $k(17)=29$. The verifier fills in the next table.

The last column sums to $f(17)=24$, and the prover gets the same number by evaluating $f$.

Finally the verifier sends $\beta$, and both parties combine the five inputs. The verifier computes $\bar{P}$ and $v$ from public data, while the prover computes the polynomial $p$ and its blinding factor:

$$\begin{array}{rl}\bar{P}& ={\beta }^4\cdot \bar{F}+{\beta }^3\cdot \bar{A}+{\beta }^2\cdot \bar{B}+\beta \cdot S+K,\\ v& ={\beta }^{4}f(u)+{\beta }^{3}a(u)+{\beta }^{2}b(u)+\beta s(u,y)+k(u),\\ \gamma & ={\beta }^4{\gamma }_f+{\beta }^3{\gamma }_a+{\beta }^2{\gamma }_b.\end{array}$$

The polynomials $s$ and $k$ have no blinding factor, so they contribute nothing to $\gamma$.

Take $\beta =23$. Each input carries its weight into the commitment, the value and the blinding factor.

All the evaluation claims now rest on the single claim $(\bar{P},u,v)$.

9. Revealing p

Batched Openings noted that the book finishes its NARK by having the prover send $p$ in full, and it promised to return to that choice. The final step is:

The prover sends $\mathbf{p}=(17,12,34,38,23,36,30,17)$ and $\gamma =27$. Committing gives $⟨\mathbf{p},\mathbf{G}⟩+27\cdot H=(23,24)$, which equals $\bar{P}$, and evaluating gives $p(17)=23$, which equals $v$.

We built an inner product argument for this exact kind of claim, so it is reasonable to ask why the NARK does not use one. The argument would prove the same thing with a logarithmic number of points, but in this protocol that saving is small, because the proof already contains other full vectors:

For $4n=2^{13}$, the witness part is $1,048,832$ bytes with $\mathbf{p}$ revealed. Replacing the reveal with an argument of $26$ points and one scalar brings it to $787,520$ bytes, because the vectors $\mathbf{s}$, $\mathbf{a}$ and $\mathbf{b}$ remain.

The verifier's work would not improve in growth either, since the argument leaves it with one MSM over all the generators, the same size as recomputing $\bar{P}$ from $\mathbf{p}$.

The reveal also fits how the proof will be used. Sending $\mathbf{p}$ places this polynomial in the witness part of the proof (Section 12), and the split accumulation chapter separates a proof's instance from its witness so that the expensive check on $(\bar{P},u,v)$ can be postponed. The inner product argument comes back at the end of the recursion, when compression ends with one IPA opening on each curve. Section 17 runs the same replacement on our example, along with the replacements for the other vectors, which is where the saving appears.

10. The whole protocol

Here is the sequence of messages. The prover's reveals are grouped with the checks that use them.

The complete run on the toy curve is:

Each check in this table is an assertion in the script behind this chapter. The honest prover should also pass at every challenge, not only the ones we picked, so we tested that too:

We ran the whole protocol for all $43^2=1849$ pairs $(z,y)$ at two values of $x$, moving $u$ whenever it would land on a claim point. The verifier accepted all 3698 runs.

11. Removing the interaction

The N in NARK means non-interactive, and the book treats this step as a direct replacement of each challenge with a hash. The Fiat–Shamir section of chapter 03 explains the transform, and the only thing this protocol adds is the list of what goes into the transcript. Each challenge must depend on every message that it tests, so the list follows the table above. The vectors $\mathbf{s}$, $\mathbf{a}$, $\mathbf{b}$ and $\mathbf{p}$ do not need to be absorbed, because the commitments already fix them, and $\bar{A}$ does not either, because it must equal the absorbed $\bar{R}$.

Here is a full run using the toy Poseidon sponge from chapter 03, starting from the tag $(7,29)$. The same witness and blinding factors now produce different challenges, so all the later values change:

The verifier replays the same absorptions from the proof, obtains the same six challenges, and accepts. Changing only the blinding factor of $\bar{R}$ from $17$ to $18$ changes the first absorbed message, and the six challenges become $(16,24,33,7,21,2)$.

Repeated trials still apply, since a cheater can try many blinding factors privately and look for a lucky set of challenges. The toy field's 43 outputs make that easy, and a 255-bit field does not.

12. The proof's two parts

Collecting the prover's messages, the book divides the proof into an instance part of constant size and a witness part of linear size. The linear witness is why this is a NARK and not a SNARK.

The challenges do not appear, because the verifier replays them from the transcript. The sizes are very different:

Take $4n=2^{13}$ with 32-byte values, the size the Ragu Book's analysis gives for its preferred threshold. The instance holds 6 points and 6 scalars, or $384$ bytes. The witness holds four vectors of $8,192$ entries and 8 more values, or $1,048,832$ bytes, which is about 1 MB.

The division is not only a way of counting. The split accumulation chapter builds a verifier that reads the instance and leaves the witness to a later check.

13. Hiding commitments and what the proof reveals

The commitments $\bar{R}$, $\bar{A}$, $\bar{B}$ and $\bar{F}$ carry blinding factors so that a commitment alone reveals nothing, for the reason given in chapter 06. The difference is visible on our trace:

An observer who holds the unblinded commitment $(4,25)$ can build the trace for every candidate input and compare. Trying all 43 inputs gives exactly one match, $x=3$. An observer who holds only $\bar{R}=(22,24)$ gets no such answer, because each of the 43 candidate traces has exactly one blinding factor that fits this point.

This protection does not last, because the proof then sends the vectors:

In our run the proof contains $\mathbf{a}=(9,27,9,3,3,3,0,0)$. The layout from the arithmetization chapter puts the wire $a_0$ at position 3, so anyone can read the secret input $x=3$ straight from the proof.

So this NARK hides nothing. The book says this openly, and it describes the omission as intentional, since Ragu intends to prevent leakage through rerandomization and not by making this NARK zero knowledge. It also says that a fold-level randomizer is still needed for that. This agrees with the status recorded in chapter 02, where neither the book nor the code yet establishes zero knowledge. The blinding factors in the book's protocol therefore do not provide privacy in this standalone form.

14. The constant wire

So far the toy circuit has moved its constant 5 into the instance. A real circuit needs constants inside its constraints, and the arithmetization chapter mentioned how Ragu provides them, with a wire that holds the value 1. This wire is what the book's two extra claims are about, so we now add it, which requires one more gate. Our $n$ becomes 3, and the polynomials have 12 coefficients, so this section uses four further generators, $G_8$ to $G_{11}$, which the script lists.

The system gate takes position 0, and the other two gates move up by one:

Gate 0 holds $a_0=11$, $b_0=0$, $c_0=0$ and $d_0=1$, and gates 1 and 2 are the two gates from the arithmetization chapter. The first constraint says $d_0=k_0$, and the second becomes $c_2+a_1+5d_0=k_1$, so the constant 5 is now a multiple of the wire. The instance is $k(Y)=1+35Y$, and the trace is $\mathbf{r}=(0,9,27,9,3,11,0,3,3,0,0,1)$. Its constant coefficient is $r(0)=c_0=0$, and its top coefficient is $d_0=1$. Checking all 1849 challenge pairs confirms that the consolidated equation holds at every one.

The wire $d_0$ sits at the top of the trace, position $4n-1$, and its partner in the revdot product is position 0, so the constraint $d_0=k_0$ puts the coefficient 1 on $X^0$ in $s(X,Y)$ with $Y^0$. This gives the identity $s(X,0)=1$, which the book states as well and which the script confirms.

The claims list now has the six entries of chapter 08's preview, on four polynomials, so one value per polynomial still suffices at $u$. Here $\alpha =11$ again, and the weights run from ${\alpha }^5$ down to 1:

With the same challenges as before, the prover sends $\bar{F}=(22,24)$ and four values at $u$, namely $16,4,15,37$. The verifier derives $\bar{P}=(6,23)$ and $v=20$, the revealed $\mathbf{p}$ matches both, and the proof is accepted.

The claim $k(0)=1$ does real work. The wire $d_0$ is only constrained to equal $k_0$, so without a check on $k_0$, a prover can give the constant a different value and change the meaning of every constraint that uses it:

Take $x=4$, which is false for the real statement, since $4^3+4+5=30$ modulo 43. A cheater sets $d_0=2$ and commits to $k^{\prime }(Y)=2+35Y$. Then $c_2+a_1+5d_0=21+4+10=35$, so every gate and constraint holds, and the consolidated equation holds at all 1849 challenge pairs. If the two constant claims are dropped from the list, the verifier accepts this proof. With the claims in the list, the false claim $k^{\prime }(0)=1$ remains. Keeping the other challenges fixed, the verifier rejects for 42 of the 43 values of $\beta$, and it accepts only at $\beta =0$, which removes $f$ from $p$.

A verifier that computes $k(y)$ from the public data with $k_0=1$, as the code does, rejects the same proof, because the cheater's $c=k^{\prime }(y)$ differs from that value at every $y$.

From here on we return to the two-gate circuit.

15. Why cheating fails

The argument relies on the following assumptions, and it is informal. Nobody knows a relation among the generators, which is the discrete log relation assumption. Each challenge is uniform and comes after the messages it tests, which for a non-interactive proof means treating the transcript hash as a random oracle. The verifier has also tied $K$ to the statement, as in Section 4.

We take the false witness with $x=4$ and consider what its prover can try. All of the counts below come from running the same verifier function that accepted the run in Section 10.

The prover follows every instruction

Take the false witness with $x=4$, so ${\mathbf{r}}^{\prime }=(16,21,16,4,4,4,0,0)$, and let the prover follow every instruction. At $z=5$ and $y=7$ the verifier computes $⟨⟨\mathbf{a},\mathbf{b}⟩⟩=18$, while $k(7)=13$, so the revdot check fails. Counting all pairs of challenges finds 43 of the 1849 where the two numbers happen to agree, the same count as in the arithmetization chapter.

The prover changes b

To reach the right revdot value, the prover has to send some vector other than the honest $\mathbf{b}$.

The revdot check only looks at $\mathbf{b}$, so the cheater can replace it with ${\mathbf{b}}^{\prime }=\mathbf{b}+\mathbf{d}$, where $\mathbf{d}$ is any vector with $⟨⟨{\mathbf{r}}^{\prime },\mathbf{d}⟩⟩=13-18=38$. The most direct choice puts one entry at position 4, the partner of $r_3^{\prime }=4$, giving $d_4=31$. The revdot check now passes. The check $b(x)=a(xz)+s(x,y)+t(x,z)$ then compares two polynomials that differ by $D(X)=31X^4$, which has only the root $0$. Running the whole protocol at all 43 values of $x$ gives one acceptance, at $x=0$.

The cheater does better by spreading the difference over all eight coefficients. Let $D(X)$ be a multiple of $(X-1)(X-2)\cdots (X-7)$, scaled so that $⟨⟨{\mathbf{r}}^{\prime },\mathbf{d}⟩⟩=38$, which gives $D(X)=36+16X+25X^2+14X^3+14X^4+2X^5+26X^6+39X^7$. Running the whole protocol at all 43 values of $x$ gives acceptance at exactly $x\in \{1,\dots ,7\}$, which is 7 out of 43. A polynomial with 8 coefficients has at most 7 roots, so no choice of $D$ can do better, and for $4n=2^{13}$ on a field of about $2^{254}$ elements the same limit gives a probability below $2^{-240}$.

The prover lies about an evaluation

Outside those roots, the only way past the check in Section 7 is to send a false value.

At $x=9$ this polynomial is not zero, since $D(9)=13$. The cheater can still pass the check by sending $b(9)=28$ in place of the true $41$, but that value is then a false evaluation claim about $\bar{B}$. The batching of the previous chapter catches it. Running all 43 values of $\beta$ with honest values at $u$ gives one acceptance, at $\beta =0$, where the derived $f(u)$ drops out of $v$.

Chapter 08 counted what the cheater gains by also shifting values at $u$ or by committing to a different $f$, and its reasoning applies to these claims unchanged. In this standalone NARK the verifier could also find the false value by evaluating the $\mathbf{b}$ it holds. The count above measures the batched check alone because that is the check recursion keeps.

The prover knows a challenge early

Every count above assumes the message order. The order is what stops a prover from solving for its messages:

Suppose the prover knows $z=5$ and $y=7$ before it sends $\bar{R}$. Starting from the false trace, it changes entry 0 by $25$ to get ${\mathbf{r}}^{\prime \prime }=(41,21,16,4,4,4,0,0)$, a value found by solving the one quadratic equation. This vector is not a valid trace, because its gates do not hold. It still satisfies the consolidated equation at this one pair, and the verifier accepts the whole proof. The same vector, committed honestly before the challenges, passes the revdot check at only 44 of the 1849 pairs.

This is the reason each challenge has to depend on the commitments before it, and chapter 03 shows what happens if a transcript leaves them out.

The prover knows a relation among the generators

Fixing $\bar{R}$ first only helps if the commitment really fixes the vector. Here is the same attack, carried out after the challenges by a prover that can open a commitment in two ways:

Suppose the prover commits to the false trace first, so $\bar{R}=(27,30)$, and only then learns $z$ and $y$. Because it knows the discrete logs of the toy generators, it can change entries 0 and 1 by $18$ and $8$ without moving the commitment. One such change gives ${\mathbf{r}}^{\prime \prime }=(34,29,16,4,4,4,0,0)$, which commits to the same point and satisfies the consolidated equation at this pair. The verifier accepts, because each of its recomputations finds what it expects.

On a real curve this requires solving discrete log, and the toy curve's small size is what makes it possible here.

16. What the verifier pays

Now we can go through the verifier's work, one step at a time. The next table gives each step's cost, and for sizes it uses $4n=2^{13}$:

The value $t(x,z)$ can be computed quickly because the sums in its definition are geometric. To see this, start from the definition and split it into two sums:

$$-t(x,z)=\sum _{i=0}^{n-1}{z}^{2n-1-i}{x}^{4n-1-i}+\sum _{i=0}^{n-1}{z}^{2n+i}{x}^{4n-1-i}.$$

Substituting $k=n-1-i$ turns the exponents into $2n-1-i=n+k$, $2n+i=3n-1-k$ and $4n-1-i=3n+k$. Factoring out the parts that do not depend on $k$ gives

$$-t(x,z)=x^{3n}{z}^n\sum _{k=0}^{n-1}(xz{)}^k+x^{3n}{z}^{3n-1}\sum _{k=0}^{n-1}(x/z{)}^k,$$

which matches the book's form for nonzero $z$. Each geometric sum has a closed form that takes $O(\log n)$ multiplications, by repeated squaring.

At $x=9$, $z=5$ and $n=2$, the first sum is $1+xz=3$ and the second is $1+x/z=20$. The formula gives $-t=40$, so $t(9,5)=3$, which matches the direct sum over the entries of $\mathbf{t}$.

The wiring vector has no comparable shortcut, since its entries come from an arbitrary circuit:

Our circuit has 8 nonzero wiring coefficients across its four constraints. Each contributes one term $\text{coefficient}\cdot y^j{x}^{\text{position}}$, and at $x=9$, $y=7$ those terms are $(25,2,27,6,22,13,18,39)$, which sum to $s(9,7)=23$. A circuit with more wiring has more terms, and no term can be skipped.

The MSMs can be merged, though this only saves a constant factor. The verifier can pick a random $\rho$ and check that one combined vector commits to the same combination of the commitments, in place of recomputing each one. If any vector does not match its commitment, the difference is a nonzero polynomial in $\rho$, so a random $\rho$ exposes it. The code's uncompressed verifier does this.

For our run take $\rho =8$ and the four vectors $\mathbf{a},\mathbf{b},\mathbf{s},\mathbf{p}$. The combined vector is $(41,30,38,3,39,33,28,17)$ with blinding factor $9$, and it commits to $(18,21)$, the same point as ${\rho }^3\cdot \bar{A}+{\rho }^2\cdot \bar{B}+\rho \cdot S+\bar{P}$. One MSM of size $4n$ did the work of four.

A verifier of this form is fine as a final check, but it cannot be placed inside a recursive proof at reasonable cost, because each of its linear steps would become part of a circuit. The next chapter explains this problem in detail. The book groups the linear work into three subprotocols, namely wiring consistency, the revdot product and the evaluation check.

17. A short proof from the same parts

We already have replacements for two of those three. The revdot product can use the split from chapter 05, at the cost of the prover's FFTs, and the evaluation check can use the inner product argument. Applying both shows what the third item leaves behind. The verifier never receives $\mathbf{s}$ here, because it only needs the single value $s(x,y)$, which it computes alone. We no longer need $b(X)$, $S$ or $K$, so the claims concern only $r$, $c_1$ and $c_2$.

The first thirteen steps mostly repeat chapter 05 and chapter 08, and now every oracle has become a commitment:

The prover now has to prove the claim $(P,u,v)$ without revealing $p$:

The polynomial behind $P$ has coefficients $\mathbf{p}=(28,23,28,13,37,37,24,14)$. The statement point for the argument is $P+v\cdot U=(22,7)$.

The inner product argument takes $k=3$ rounds for 8 coefficients. Its round challenges $u_j$ are unrelated to the batching point $u$, and we pick them by hand. At each round the prover sends $L_j$ and $R_j$, and both sides fold, as chapter 07 explained:

The prover sends the final scalar $\hat{a}=6$. The verifier computes the coefficients of $g(X)$ from the three challenges, which are $(28,37,5,2,22,26,7,20)$, then $\hat{b}=g(17)=30$ and $\hat{G}=(4,25)$ from one MSM over all eight generators. The left side of the check is $(8,22)$, and $\hat{a}\cdot (\hat{G}+\hat{b}\cdot U)=(8,22)$, so the verifier accepts.

The proof is now short:

For $4n=2^{13}$ this proof holds $30$ points and $9$ scalars, or $1,248$ bytes at 32 bytes each, in place of about 1 MB.

The verifier has not improved as much as the proof has. Here is its work:

The rows marked linear come down to two costs, once we treat the coefficients of $g$ as part of computing $\hat{G}$:

1. Computing $s(x,y)$. The verifier has to read the whole circuit, because the wiring has no structure it can exploit.
2. Computing $\hat{G}=⟨\mathbf{g},\mathbf{G}⟩$, where $\mathbf{g}$ is the coefficient vector of $g(X)$. The generators have no structure either, as chapter 07 explained.

The book writes $G_0$ for what this site calls $\hat{G}$. These two steps are the targets of what follows. The accumulation chapter postpones $\hat{G}$, and the chapter on wiring and the registry handles $s(x,y)$. The revdot folding chapter covers how most steps avoid the split and its FFTs.

18. The NARK in Ragu

As Section 1 noted, the code has no type or function for this standalone protocol, since Ragu's real proofs cover a recursive step with many polynomials. Several of its checks can still be located in the uncompressed verifier. The revdot check, step 6 of our run, appears for each claim the proof carries, here from crates/ragu_pcd/src/verify.rs at commit 3219e08:

let native_revdot_claims = {
    native::ky_values::<C::Profile, _>(&native_ky)
        .zip(builder.a.iter().zip(builder.b.iter()))
        .all(|(ky, (a, b))| Verifier::<B>::sparse_revdot(a, b) == ky)
};

19. Where this chapter leaves us

This chapter took the following steps:

1. The prover commits to the instance and the trace before it sees $z$ and $y$, and the verifier ties $K$ to the statement.
2. The prover commits to $s(X,y)$ and to the right factor $b(X)=a(zX)+s(X,y)+t(X,z)$, then sends the vectors, so that the verifier can recompute the wiring, recompute the commitments and compute the revdot product directly.
3. A check at a random $x$ ties $b(X)$ to the trace, wiring and gate polynomials.
4. The evaluation claims batch into one claim $(\bar{P},u,v)$, which the book's NARK finishes by revealing $p$.
5. The resulting proof has a constant-size instance and a linear-size witness, and it hides nothing, despite its blinding factors.
6. A cheater can pass only at rare challenges, as long as each challenge follows the messages it tests and nobody knows a relation among the generators.
7. Replacing the direct checks with the split and the inner product argument makes the proof logarithmic in size, and it leaves the verifier two linear steps, computing $s(x,y)$ and computing $\hat{G}$.

A verifier with linear steps can check a proof, but it cannot fit inside the next proof at reasonable cost. The next chapter takes up proofs about verifiers, and shows why the two steps above block them.