Revdot Folding

The split accumulation chapter sorted the verifier's work by what it reads, and it folded the evaluation claims. One row of its table stayed open, which was the revdot product $⟨⟨\mathbf{a},\mathbf{b}⟩⟩$. That product reads two whole witness vectors, so a recursive verifier cannot compute it, and this chapter folds it instead.

A revdot claim contains a product of two unknown vectors, so it does not combine linearly as an evaluation claim does. Chapter 12 ended with the first sign of this, a cross term that the prover has to supply. We start from that example and find that its single challenge stops working at three claims. Repairing it leads to the error matrix and the challenges $\mu$ and $\nu$. We then remove the two costs that this fold would place in a circuit, namely the commitment sums and the quadratic field arithmetic, and we finish with the different fold that Ragu's code runs at each step.

1. The claim that remains

A step of the proof from chapter 09 ends up holding two commitments and a target value, and it needs to know that the committed vectors have that revdot product. Following the book's relation, a revdot claim has the instance $(\bar{A},\bar{B},c)$ and the witness $(\mathbf{a},\mathbf{b},{\gamma }_a,{\gamma }_b)$, and it holds when

$$⟨\mathbf{a},\mathbf{G}⟩+{\gamma }_a\cdot H=\bar{A},⟨\mathbf{b},\mathbf{G}⟩+{\gamma }_b\cdot H=\bar{B},⟨⟨\mathbf{a},\mathbf{b}⟩⟩=c.$$

Chapter 09's proof gives the instance $(\bar{A},\bar{B},c)=((22,24),(1,29),13)$ and the witness $\mathbf{a}=(9,27,9,3,3,3,0,0)$, $\mathbf{b}=(9,6,16,30,20,8,31,17)$, ${\gamma }_a=17$, ${\gamma }_b=29$. Checking the claim takes both parts. The two commitments recompute to the stated points, and $⟨⟨\mathbf{a},\mathbf{b}⟩⟩=13$.

The earlier chapters offer two ways to check such a claim, and each has a cost in the wrong place:

The direct check cannot go in a circuit, since a recursive verifier reads only instances. The split suits a verifier, but the prover would run its FFTs at every step of a long computation, and the book wants to confine that to the places in the tree where a short proof is needed.

Chapter 12 suggests a third route, in which we reduce many claims to one claim of the same form and leave the last one to a decider. The reduction has to handle many claims at once, because a fuse in Ragu's standard profile has 86 native and 72 nested revdot claims. The book names their sources, which are the consolidated equation of each circuit, the stage checks, and the accumulators of the previous step.

Chapter 09 listed two linear costs as targets for this part of the site. This chapter does not address either of them directly. The cost of $\hat{G}$ already left the recursive path in chapter 12. The cost of computing $s(x,y)$ remains after this chapter too, because a fold says nothing about whether $\bar{B}$ was built from the right circuit, and the wiring chapter deals with that. What this chapter removes is the need for the split and its FFTs at most steps, as chapter 09 promised.

2. Two claims and one cross term

Start with two claims and weight the second by a challenge $r$, as chapter 12 did. The commitments combine by linearity, so anyone can compute ${\bar{A}}_0+r\cdot {\bar{A}}_1$ and ${\bar{B}}_0+r\cdot {\bar{B}}_1$. The value needs more care, because the revdot product is linear in each argument separately. Expanding both arguments gives four products:

$$\begin{array}{rl}⟨⟨{\mathbf{a}}_0+r{\mathbf{a}}_1,{\mathbf{b}}_0+r{\mathbf{b}}_1⟩⟩& =⟨⟨{\mathbf{a}}_0,{\mathbf{b}}_0⟩⟩+r⟨⟨{\mathbf{a}}_0,{\mathbf{b}}_1⟩⟩+r⟨⟨{\mathbf{a}}_1,{\mathbf{b}}_0⟩⟩+r^2⟨⟨{\mathbf{a}}_1,{\mathbf{b}}_1⟩⟩\\ & =c_0+rE+r^2{c}_1.\end{array}$$

The outer two products are the claimed values, which the verifier holds. The middle two involve one claim's $\mathbf{a}$ and the other claim's $\mathbf{b}$, which no claim says anything about, so the prover supplies their sum $E$.

Chapter 12 used inner products, so we reverse its $\mathbf{b}$ vectors to write the same numbers as revdot products. Take ${\mathbf{a}}_0=(2,5)$, ${\mathbf{b}}_0=(3,7)$ with $c_0=29$, and ${\mathbf{a}}_1=(4,6)$, ${\mathbf{b}}_1=(8,1)$ with $c_1=9$. The two products that mix the claims are $⟨⟨{\mathbf{a}}_0,{\mathbf{b}}_1⟩⟩=42$ and $⟨⟨{\mathbf{a}}_1,{\mathbf{b}}_0⟩⟩=3$, so $E=42+3=2$ modulo 43, as chapter 12 found. At $r=9$ the folded vectors are $(38,16)$ and $(32,16)$, their revdot product is $2$, and $c_0+rE+r^2{c}_1=29+9\cdot 2+38\cdot 9=2$.

The new claim is $({\bar{A}}_0+r\cdot {\bar{A}}_1,{\bar{B}}_0+r\cdot {\bar{B}}_1,c_0+rE+r^2{c}_1)$, which has the same form as the old ones. The prover has to send $E$ before it learns $r$, and the next count shows why:

Suppose the prover states the false $c_0=30$. The two sides then differ by $1+r(E^{\prime }-E)$, where $E^{\prime }$ is the value it sends. We tried all 43 values of $E^{\prime }$ against all 43 values of $r$. The honest $E^{\prime }=2$ never passes, and each of the other 42 values passes at exactly one $r$. If the prover could choose $E^{\prime }$ after seeing $r$, then it could solve this linear equation and pass every time.

So a false claim survives only if $r$ lands on one root. The argument is the root count of chapter 03, applied to a polynomial in $r$ whose constant term is the false claim's error.

3. Three claims break the single challenge

The natural extension gives claim $i$ the weight $r^i$ on both sides. Bilinearity gives one product for each pair, and we write the products as

$$e_{i,j}=⟨⟨{\mathbf{a}}_i,{\mathbf{b}}_j⟩⟩,\text{so that }{e}_{i,i}=c_i\text{ for a true claim.}$$

Expanding for $m=3$ and collecting powers of $r$ gives

$$\begin{array}{rl}⟨⟨\sum _i{r}^i{\mathbf{a}}_i,\sum _j{r}^j{\mathbf{b}}_j⟩⟩& =\sum _{i,j}{r}^{i+j}{e}_{i,j}\\ & =c_0+r(e_{0,1}+e_{1,0})+r^2(e_{0,2}+c_1+e_{2,0})+r^3(e_{1,2}+e_{2,1})+r^4{c}_2.\end{array}$$

Look at the coefficient of $r^2$. It adds the claim $c_1$ to two cross terms, and the verifier can check only this sum. If $c_1$ is false, the prover can move the error into a cross term, which it controls, and the polynomial in $r$ stays exactly right. To see this we need real claims, so we take three proofs of the step function $F(z)=z^3+z+5$ from chapter 12's chain:

The first two rows are the claims printed in chapters 09 and 12. The third row uses its own blinding factors, since this curve has so few points that repeated factors can land two different vectors on one commitment. Now we attack the fold:

Put chapter 09's false witness with $x=4$ in the middle slot, between the two later proofs of the table above. Its vectors give $18$ while its statement requires $c_1=13$, so this claim is false by $5$. The honest cross terms are $E_1=26$, $E_2=11$ and $E_3=26$, and the fold rejects at all 42 nonzero values of $r$. The cheater sends $E_2^{\prime }=11+5=16$ instead, before it knows $r$. At $r=9$ both sides equal $15$, and running all 43 values of $r$ gives 43 passes. The output is a true claim, because the vectors ${\mathbf{a}}^{\ast }$ and ${\mathbf{b}}^{\ast }$ really have that revdot product, so the decider accepts it too.

The challenge did nothing here, because the error and its cancellation carried the same power of $r$ for every $r$. Two claims escaped this problem because each of their diagonal entries has a power of $r$ to itself, and that stops being true at three claims. We therefore need weights under which no cross term can share a monomial with a diagonal entry.

4. Two challenges and the error matrix

Give the two sides independent weights, say ${\lambda }_i$ on ${\mathbf{a}}_i$ and ${\eta }_j$ on ${\mathbf{b}}_j$. Bilinearity gives

$$⟨⟨\sum _i{\lambda }_i{\mathbf{a}}_i,\sum _j{\eta }_j{\mathbf{b}}_j⟩⟩=\sum _{i,j}{\lambda }_i{\eta }_j{e}_{i,j}.$$

With ${\lambda }_i={\lambda }^i$ and ${\eta }_j={\eta }^j$ for two independent challenges, every cell has its own monomial ${\lambda }^i{\eta }^j$, and the collision disappears. The book makes the same choice in a different form. It takes two challenges $\mu$ and $\nu$, and it sets

$${\lambda }_i={\mu }^{-i},{\eta }_j=(\mu \nu {)}^j,$$

so that $\lambda ={\mu }^{-1}$ and $\eta =\mu \nu$. Multiplying the weights gives

$${\lambda }_i{\eta }_j={\mu }^{-i}{\mu }^j{\nu }^j={\mu }^{j-i}{\nu }^j.$$

On the diagonal $\mu$ cancels and the weight is ${\nu }^i$. The pair of exponents $(j-i,j)$ determines the cell $(i,j)$, so no two cells share a monomial. The array of all the $e_{i,j}$ is called the error matrix. The folded claim is

$${\bar{A}}^{\ast }=\sum _i{\mu }^{-i}\cdot {\bar{A}}_i,{\bar{B}}^{\ast }=\sum _j(\mu \nu {)}^j\cdot {\bar{B}}_j,c^{\ast }=\sum _{i,j}{\mu }^{j-i}{\nu }^j{e}_{i,j},$$

where the verifier fills the diagonal of the last sum with its own $c_i$ and the prover supplies the other $m^2-m$ entries.

We can test the repair against the attack that just succeeded:

We replay the cheat of Section 3, with the same false claim and the same shift of $5$ on the cross term in cell $(0,2)$. The diagonal error now has weight $\nu$ and the shift has weight ${\mu }^2{\nu }^2$, so the two cancel only where ${\mu }^2\nu =1$ or $\nu =0$. Across all 1,806 pairs with $\mu \ne 0$ the fold passes at 84, which is 0.047 of them. Half of those have $\nu =0$, where ${\mathbf{b}}^{\ast }$ reduces to ${\mathbf{b}}_0$ and the other claims drop out of the check.

Section 9 counts the cheater's other options, and Section 11 shows that the book's other chapters write the same family of weights in other ways.

5. One fold on the toy curve

Here are the book's steps, in the order that the argument above requires:

Take the three true claims of Section 3. The prover computes the error matrix. The bold entries match the $c_i$ in the instances, so the prover leaves them out of its message and sends the other six.

The verifier sends $\mu =6$ and $\nu =13$, so ${\mu }^{-1}=36$ and $\mu \nu =35$. The weights on the ${\mathbf{a}}_i$ are $(1,36,6)$, and the weights on the ${\mathbf{b}}_j$ are $(1,35,21)$. Each cell of the next table is the matching weight times the entry above:

All nine cells sum to $c^{\ast }=19$.

Both parties then finish their sides, and each part of the new claim comes from the same weights:

The verifier's three rows touch only instances and cross terms. The blinding factors follow the vectors because each commitment is linear in its vector and its blinding factor together, as chapter 06 showed.

The decider now has one claim to check. It computes $⟨⟨{\mathbf{a}}^{\ast },{\mathbf{b}}^{\ast }⟩⟩=19$, which equals $c^{\ast }$, and it recomputes both commitments, which gives $(1,2)$ and $(5,29)$. Three revdot products and six commitment checks have become one and two.

An honest prover should pass whatever the challenges are, and it does:

Repeating the fold for all 1,806 pairs $(\mu ,\nu )$ with $\mu \ne 0$ gives a true output claim every time.

6. An accumulator of revdot claims

The output has the same form as each input, so it can serve as an accumulator. The book says exactly this. The instance of the accumulator is $(\bar{A},\bar{B},c)$ and its witness is $(\mathbf{a},\mathbf{b},{\gamma }_a,{\gamma }_b)$, and each step places the old accumulator in the list along with the step's new claims. This explains the two names chapter 09 kept apart, since $\bar{R}$ holds one step's trace while $\bar{A}$ can hold an aggregate of many claims.

The accumulator sits beside the one from chapter 12, and the book lists both in the accumulator of one curve. Here is a chain over the first three proofs, which folds one new claim at each step:

Every vector still has 8 entries, because each fold takes a linear combination of vectors of that length. Suppose the chain stops here:

The decider receives the last accumulator. It finds $⟨⟨\mathbf{a},\mathbf{b}⟩⟩=25=c$, and with ${\gamma }_a=42$ and ${\gamma }_b=30$ both commitments recompute to the instance. It accepts.

The decider's work is two MSMs of size $4n$ and one revdot product, once for the whole history. The prover pays for the cross terms at each step, and we can compare that with the alternative it avoids:

A fold of one accumulator and one new claim needs $2$ cross terms, at 8,192 multiplications each for dense vectors of $2^{13}$ entries, so 16,384 multiplications. The split of chapter 05 needs at least 3 FFTs of about 114,688 multiplications each, or 344,064, and then the prover still has to commit to two more polynomials.

The second figure counts radix-2 FFTs at $\frac{N}{2}{\log }_{2}N$ multiplications over $N$ points, which is the usual estimate. The fold needs no product polynomial, since each cross term is one number computed with one pass over the vectors, and so most steps never run an FFT. The split comes back only in Section 11, where a proof leaves the tree.

7. Replacing the commitment sums with evaluations

The verifier of Section 5 computes ${\bar{A}}^{\ast }$ and ${\bar{B}}^{\ast }$, which takes $2m$ scalar multiplications. Inside a circuit those are operations on points whose coordinates lie in the wrong field. Chapter 13 could defer each one to the other circuit, but the book takes a different route that reuses a mechanism we already have.

The relation ${\bar{A}}^{\ast }={\sum }_i{\mu }^{-i}\cdot {\bar{A}}_i$ between commitments says that the polynomials behind them satisfy $a^{\ast }(X)={\sum }_i{\mu }^{-i}{a}_i(X)$, as long as the commitments are binding. An identity between polynomials can be tested at a random point. So the prover names ${\bar{A}}^{\ast }$ without the verifier computing it, the verifier sends a random $\theta$, and the prover reports the values $a_i(\theta )$ and $a^{\ast }(\theta )$. The verifier then checks

$$a^{\ast }(\theta )=\sum _i{\mu }^{-i}{a}_i(\theta ).$$

This is field arithmetic, which a circuit handles natively. It only means something if the reported values are true, so each value becomes an evaluation claim, $({\bar{A}}_i,\theta ,a_i(\theta ))$ for each $i$ and $({\bar{A}}^{\ast },\theta ,a^{\ast }(\theta ))$ for the output. The $\bar{B}$ side works in the same way. That makes $2(m+1)$ claims, which join the list that chapter 12's accumulator folds anyway.

Take $\theta =22$ for the fold of Section 5. The prover sends these values:

Field arithmetic alone confirms both sums: $1\cdot 16+36\cdot 5+6\cdot 6=17$ and $1\cdot 39+35\cdot 8+21\cdot 1=39$ modulo 43.

The list now holds 8 claims, all at the single point $\theta =22$. Running the fold of chapter 12 with $\alpha =11$, $u=17$ and $\beta =25$ gives $\bar{F}=(25,2)$, $f(17)=33$ and the output $((28,21),17,42)$. Its witness $\mathbf{p}=(22,30,5,36,41,17,35,5)$ with $\gamma =7$ commits to the same point and evaluates to the same value.

The challenge $\theta$ has to come after the prover names ${\bar{A}}^{\ast }$ and ${\bar{B}}^{\ast }$, for the reason that every test at a random point needs. A wrong commitment shows up as a nonzero difference polynomial:

Suppose the prover names ${\bar{A}}^{\ast }=(14,22)$, a commitment to ${\mathbf{a}}^{\ast }$ with its entry 4 raised by one, and reports true values for it. The linear check then fails at every $\theta$ except 0. A difference that vanishes at $1,\dots ,7$ does as well as a difference can, and it passes at those 7 of the 43 values. Outside those roots the prover has to report a false value at $\theta$, which makes that entry of the list a false evaluation claim for chapter 08 to catch.

The saving comes from how chapter 08's batching charges for its inputs. Its point combination takes one scalar multiplication per polynomial, however many points that polynomial is queried at, and the book makes this argument for why the total falls:

For the fold above with $m=3$, computing the commitment sums directly takes $2m=6$ scalar multiplications in the circuit. In the batched form each of the 8 polynomials takes one power of $\beta$, so the proof's own ${\bar{A}}_i$ and ${\bar{B}}_i$ cost nothing extra when the list already contains them, and only ${\bar{A}}^{\ast }$ and ${\bar{B}}^{\ast }$ are new. That makes $2$ new scalar multiplications in place of $6$, and they happen in the circuit on the other curve.

8. Two layers

The circuit still has to compute $c^{\ast }$, which has $m^2$ terms. Factoring the weights lets it compute each level of the sum by repeated multiply-and-add, which is Horner's rule:

$$c^{\ast }=\sum _i{\mu }^{-i}(\sum _j(\mu \nu {)}^j{e}_{i,j}).$$

Each inner sum over $m$ entries takes $m-1$ multiplications, and the outer sum takes $m-1$ more, for a total of $m(m-1)+(m-1)=m^2-1$. Precomputing $\mu \nu$ and ${\mu }^{-1}$ adds two, which gives the book's $m^2+1$ constraints.

For the matrix of Section 5, the three inner sums at $\mu \nu =35$ are $(30,21,37)$, which take $2$ multiplications per row. The outer sum at ${\mu }^{-1}=36$ takes $2$ more and gives $c^{\ast }=19$, the same value as before. That is $8=3^2-1$ multiplications, plus the $2$ that precomputed $\mu \nu$ and ${\mu }^{-1}$.

Quadratic growth is a problem because of the limit of $2^{11}$ gates per circuit. The book's example of 133 claims would need far more than that, and it notes that smaller circuits also lead to smaller commitments and faster verifiers later on. Since the cost is the square of the list's length, shorter lists help, so we can fold in stages.

The two-layer reduction

Divide the $M\cdot N$ claims into $N$ groups of $M$ claims each. The book's steps are then as follows:

1. First layer. The prover sends the cross terms within each group, which are $N\cdot M(M-1)$ values. The verifier sends $\mu$ and $\nu$. Applying Section 4 to each group $g$ gives one intermediate claim $({\bar{A}}^{(g)},{\bar{B}}^{(g)},c^{(g)})$.
2. Second layer. The prover computes the cross terms $e_{g,h}=⟨⟨{\mathbf{a}}^{(g)},{\mathbf{b}}^{(h)}⟩⟩$ between the intermediate claims and sends these $N(N-1)$ values. The verifier sends fresh challenges ${\mu }^{\prime }$ and ${\nu }^{\prime }$. Applying Section 4 to the $N$ intermediate claims gives the final claim.

The second layer's diagonal consists of the values $c^{(g)}$, which the verifier computed in the first layer. Cross terms between claims in different groups never appear individually. They are bundled into the $e_{g,h}$, which is why the count drops.

A run with six claims

We extend the chain to six proofs and take $(M,N)=(3,2)$:

The prover sends $2\cdot 3\cdot 2=12$ cross terms, listed row by row with the diagonal left out. The verifier then sends $\mu =6$ and $\nu =13$, and both sides compute one intermediate instance per group. Group 0 holds the claims of Section 5, so its result is the one we already found.

The prover now computes the cross terms between the two intermediate claims, $e_{0,1}=3$ and $e_{1,0}=33$, and sends them. The verifier sends fresh challenges ${\mu }^{\prime }=29$ and ${\nu }^{\prime }=10$. The diagonal entries are the $c^{(g)}$ that both sides already hold, so $c^{\ast }=19+32\cdot 3+3\cdot 33+10\cdot 1=9$ modulo 43.

The final instance is $((20,25),(20,6),9)$. The prover's vectors are ${\mathbf{a}}^{\ast }=(13,29,13,21,21,21,0,0)$ and ${\mathbf{b}}^{\ast }=(41,33,25,35,10,41,36,21)$, whose revdot product is $9$, and the decider accepts. The prover sent $12+2=14$ cross terms, where a single layer over six claims would have needed $6\cdot 5=30$. The book's count for $(M,N)=(3,2)$ is $23$ constraints against $37$.

Choosing M and N

Applying Horner's rule at each layer gives the book's count. The first layer costs $N(M^2-1)$ for its groups plus $2$ for the precomputed values, and the second costs $N^2-1$ plus $2$. The total is

$$(N{M}^2-N+2)+(N^2+1)=N{M}^2+N^2-N+3.$$

The term $N{M}^2$ favours small groups and the term $N^2$ favours few groups, so a balance exists:

Among all $M$ from 2 to 66, each with the smallest $N$ that gives room for 133 claims, the book's pair $(7,19)$ has the lowest count, 1,276. That is 93% below the single layer, and the book reports the same two counts.

9. Why cheating fails

This argument is informal. The toy curve permits forgeries, since every discrete log is known, so the counts below model a prover who holds real vectors and does not use those relations, except in the last example.

A false claim with honest cross terms

Take the false list of Section 3 and let the prover send every cross term honestly. The stated $c^{\ast }$ then differs from the true product by the diagonal error alone, $(13-18)\nu =38\nu$, which is zero only at $\nu =0$. The fold passes at 42 of the 1,806 pairs, all of them with $\nu =0$, where the second and third claims drop out.

Those passes are a real weakness of $\nu =0$, but a random challenge rarely takes that value. A false claim in slot 0 has weight ${\nu }^0=1$ and no such exception.

Choosing the cross terms

A cheater can also move the cross terms away from their honest values. The difference between the two sides then becomes a polynomial in $\mu$ and $\nu$, nonzero because of the diagonal error, and multiplying by ${\mu }^{m-1}$ clears the negative powers and leaves total degree at most $3(m-1)=6$. The Schwartz–Zippel bound therefore allows at most $258$ of the $43^2$ pairs. The best attack we found raises $e_{0,1}$ by $22$ and $e_{2,1}$ by $32$. The difference becomes $\nu (38+22\mu +32{\mu }^{-1})$, which vanishes for every $\nu$ at $\mu =3$ and $\mu =7$, and it passes at 126 of the 1,806 pairs. The best of 300 random choices of offsets passes at 83.

On a 255-bit field, $m=133$ gives a bound of $3\cdot 132/2^{254}$, which is below $2^{-245}$.

Sending cross terms after the challenges

Every count so far assumes that the prover fixes its cross terms first, which in a non-interactive proof means that the transcript absorbs them before it produces $\mu$ and $\nu$:

At $\mu =6$ and $\nu =13$, the false list fails with honest cross terms. A prover who already knows these challenges raises $e_{0,2}$ by $42$, which solves one linear equation, and the fold passes. The same shift committed in advance passes at only 84 of the 1,806 pairs.

Two layers and fresh challenges

A false claim survives the first layer as a false intermediate claim, which the second layer then treats as an ordinary false claim in its diagonal:

Now place the false claim in group 0 of the six-claim run, with honest cross terms. At $\mu =6$ and $\nu =13$ the group's stated value $c^{(0)}=39$ differs from the true product by $21$, and over all pairs the first layer passes at 42 of 1,806. That error sits in a diagonal slot of the second layer, in the group with weight 1, so with honest cross terms the second layer passes at 0 of its 1,806 pairs.

The book explains the fresh challenges by noting that the root-counting argument applies separately at each layer. That argument needs each layer's messages to come before that layer's challenges, and the second layer's messages depend on the first layer's result, so reusing the challenges breaks the order:

Suppose the second layer reused $\mu$ and $\nu$. The prover learns them before it sends the second layer's cross terms, so it can compute the error in $c^{(0)}$ and cancel it through $e_{0,1}$. At $\mu =6$ and $\nu =13$ the shift is $8$. Doing this at every pair with $\mu ,\nu \ne 0$ passes all 1,764 of them. With fresh challenges the same message is fixed first, and it passes at 42 of the 1,806 pairs $({\mu }^{\prime },{\nu }^{\prime })$.

A false claim reaches the decider

As in chapter 12, the verifier checks arithmetic and has no way to know that a claim is true:

Start the chain of Section 6 from the false claim in place of the true one, keeping every later step honest.

The verifier computes each new instance and sees nothing wrong. The accumulator sits in slot 0, whose diagonal weight is ${\nu }^0=1$, so the gap of $38$ passes through each fold unchanged. The decider rejects the last accumulator because its product differs from its stated value.

A chain that never runs the decider has therefore established nothing about its revdot claims. The target $c_i$ of a new claim must also come from the statement and not from the prover, which is the lesson of chapter 09, and the old accumulator's instance must be tied to the previous proof, as chapter 12 showed. A comment in the code records the first of these two requirements.

Binding at the decider

The decider's check means something only because ${\bar{A}}^{\ast }$ can be opened in one way:

Using the known discrete logs of the toy generators, a prover can state the false $c^{\ast }=20$ for the fold of Section 5 and present ${\mathbf{a}}^{\ast }=(22,40,40,22,22,22,0,0)$. This vector commits to the same ${\bar{A}}^{\ast }=(1,2)$, and its revdot product with ${\mathbf{b}}^{\ast }$ is $20$, so the decider accepts it.

On a real curve, such a vector would give a discrete log relation among the generators.

Assumptions

The reasoning relies on the discrete log relation assumption, and it treats the transcript hash as a random oracle, with each challenge drawn after the data it tests. It assumes that the circuit takes each target from the statement or the previous proof, and that the decider runs honestly. Private retries under Fiat–Shamir add to these chances. We do not analyse Ragu's scheme as a whole here.

10. The quotient fold in Ragu's fuse

The matrix has one remaining cost, which the table at the end of this section measures. The prover sends one field element per off-diagonal cell, and each of those values enters the circuit. The verifier uses them only through the weighted sum $c^{\ast }$, so we can ask whether a shorter message could determine that sum. The code at 3219e08 answers this by changing the weights.

The derivation

Treat the claims as the values of one curve through the points $0,1,\dots ,m-1$. Let $L_i(T)$ be the Lagrange basis polynomial that equals 1 at $T=i$ and 0 at the other nodes, and define

$$\mathbf{A}(T)=\sum _i{L}_i(T){\mathbf{a}}_i,\mathbf{B}(T)=\sum _i{L}_i(T){\mathbf{b}}_i,K(T)=\sum _i{L}_i(T)c_i.$$

For three claims the nodes are $0,1,2$, and the basis polynomials over ${\mathbb{F}}_{43}$ have these coefficients of $T^0,T^1,T^2$: $L_0=(1,20,22)$, $L_1=(0,2,42)$ and $L_2=(0,21,22)$. The vanishing polynomial is $Z(T)=T(T-1)(T-2)$, with coefficients $(0,2,40,1)$.

At the node $T=i$ these reduce to ${\mathbf{a}}_i$, ${\mathbf{b}}_i$ and $c_i$. So the difference

$$R(T)=⟨⟨\mathbf{A}(T),\mathbf{B}(T)⟩⟩-K(T)$$

equals $e_{i,i}-c_i$ at node $i$, and it vanishes at every node exactly when all the claims are true. A polynomial that vanishes at all $m$ nodes is a multiple of $Z(T)={\prod }_i(T-i)$. Bilinearity gives the first term of $R(T)$ as

$$⟨⟨\mathbf{A}(T),\mathbf{B}(T)⟩⟩=\sum _{i,j}{L}_i(T)L_j(T)e_{i,j},$$

which has degree at most $2m-2$. Since $Z$ has degree $m$, the quotient $Q(T)=R(T)/Z(T)$ has degree at most $m-2$, and therefore only $m-1$ coefficients. This is the shorter message. The prover sends the coefficients of $Q$, and the verifier sends one challenge $\mu$. Evaluating at $\mu$ gives the new claim, with weights ${\lambda }_i=L_i(\mu )$ on both sides:

$${\bar{A}}^{\ast }=\sum _i{\lambda }_i\cdot {\bar{A}}_i,{\bar{B}}^{\ast }=\sum _i{\lambda }_i\cdot {\bar{B}}_i,c^{\ast }=K(\mu )+Z(\mu )Q(\mu ).$$

The value is right because $⟨⟨\mathbf{A}(\mu ),\mathbf{B}(\mu )⟩⟩=K(\mu )+R(\mu )=K(\mu )+Z(\mu )Q(\mu )$. Notice that the prover's work has not shrunk, since the sum over $i,j$ still needs every product, including the diagonal.

A run with three claims

We reuse the matrix of Section 5, so the two folds can be compared directly:

Using the matrix of Section 5 in the expansion gives the coefficients of $T^0,\dots ,T^4$ below.

Dividing by $Z(T)$ leaves no remainder and gives $Q(T)=34+31T$. The prover commits to these two coefficients before it sees the challenge.

The verifier sends $\mu =20$. The three weights are ${\lambda }_i=L_i(20)$, which gives $(42,27,18)$, and the same weights apply on both sides, so ${\bar{A}}^{\ast }=(22,7)$ and ${\bar{B}}^{\ast }=(8,22)$. The verifier computes $K(20)=0$, $Z(20)=3$ and $Q(20)=9$, so the new value is $c^{\ast }=0+3\cdot 9=27$. The prover's folded vectors are ${\mathbf{a}}^{\ast }=(17,13,17,14,14,14,0,0)$ and ${\mathbf{b}}^{\ast }=(17,37,18,17,28,36,16,33)$, and their revdot product is $27$. All 43 values of $\mu$ pass for these honest claims. The prover sent two field elements where the error matrix needed six.

Why one challenge is enough

Section 3 showed that one challenge with weights $r^i$ fails, so we need to see what has changed. Suppose claim $i$ is false. For any quotient $Q$ the prover might send, the difference between the two sides is

$$⟨⟨\mathbf{A}(T),\mathbf{B}(T)⟩⟩-K(T)-Z(T)Q(T),$$

and at node $i$ the last term vanishes because $Z(i)=0$. The difference there equals $e_{i,i}-c_i$, which is not zero. So no choice of $Q$ can make this polynomial zero, and it has at most $2m-2$ roots. In Section 3 the prover's message shared a power of $r$ with the false claim and could cancel it. Here the message is multiplied by $Z$, which is zero at the place where the false claim shows up.

Take the false list of Section 3, with slot 1 false by $5$. We tried all $43^2=1,849$ values of the two quotient coefficients against all 43 values of $\mu$. The best choice passes at 4 values of $\mu$, which is the bound $2m-2=4$. Every choice passes at $\mu =0$ and $\mu =2$, because at a node the weights select one claim and $Z$ vanishes, so the fold checks only the claim in that slot. No choice passes at $\mu =1$, the node of the false claim.

The passes at nodes show the fold's weak spot. The code's comments note it too, and they rely on a challenge hitting a node only with probability $m/|S|$. The message order matters as before:

At $\mu =20$ the cheater needs $Q(20)=30$, and one linear equation in the two coefficients provides it. This is why the code fixes the quotient before the challenge.

The code's comments give each layer a failure bound of $(2m-2)/|S|$ for a challenge uniform on a set $S$, and they put the nested challenges at $|S|=2^{143}$. The largest reduction on the nested side has $m=10$, which gives $18/2^{143}$, and that is below $2^{-138}$.

Two layers in the code

The code still folds in two layers. The second layer treats the groups' values as its targets and has a fresh challenge ${\mu }^{\prime }$:

For the six claims of Section 8 with the groups unchanged, the first layer commits to $Q_0=(34,31)$ and $Q_1=(10,15)$. At $\mu =20$ the groups give values $c^{(0)}=27$ and $c^{(1)}=37$. The second layer has two inputs, so its quotient has the single coefficient $3$. At ${\mu }^{\prime }=33$ the final value is $c^{\ast }=42$, which equals the revdot product of the final vectors. The prover sent $2\cdot 2+1=5$ field elements, where Section 8 sent 14.

Its comments give the reason for keeping two layers. The number of carried coefficients is $b-1$ for any split of a budget of $b$ slots, while the prover's count of revdot products depends on the split, and the choice of seven per group sits near the minimum. So the two layers now serve the prover more than the circuit. The next table applies the counts to the native parameters:

The last row of the first column uses the book's formula, and the other two use our count of the multiplications in the code's Basis, which is $3m-5$ per layer for the basis and $2m-1$ per group. These rows cover only the folding of scalars. The circuit also computes the targets $k(y)$, and another circuit checks the folded evaluations.

By the same count, the nested side's $(M,N)=(8,10)$ has room for $80$ claims, commits to $79$ coefficients, and uses 213 multiplication gates for its scalar folds.

Locating the fold in the code

The formula $c^{\ast }=K(\mu )+Z(\mu )Q(\mu )$ appears in corrected, where target is $K(\mu )$, the loop is Horner's rule for $Q(\mu )$, and self.z is $Z(\mu )$:

let target = self.linear(dr, targets)?;
if quotient.is_empty() {
    return Ok(target);
}
let mut q = quotient.last().expect("quotient").clone();
for coefficient in quotient[..quotient.len() - 1].iter().rev() {
    q = q.mul(dr, r)?.add(dr, coefficient);
}
let correction = self.z.mul(dr, &q)?;
Ok(target.add(dr, &correction))

All of this describes the Ragu revision at 3219e08. Tachyon, which has not activated on mainnet and whose design is still changing, pins a different Ragu revision and runs its steps against a mock of Ragu, so nothing at its pinned commit executes this fold.

11. Compression and the forms of the fold

Compression folds again when a proof leaves the tree, and here the matrix returns, with plain weights ${\mu }^i$ on the $\mathbf{a}$ side and ${\nu }^j$ on the $\mathbf{b}$ side. These are the same family as Section 4 under a change of names, where the plain weights' bases are the book's ${\mu }^{-1}$ and $\mu \nu$:

For the fold of Section 5, the book's $\mu =6$ and $\nu =13$ correspond to the plain weights $\lambda =36$ and $\eta =35$, and these give the same ${\mathbf{a}}^{\ast }$, ${\mathbf{b}}^{\ast }$ and $c^{\ast }=19$. The form in the structured vectors chapter at the same $\mu$ and $\nu$ gives a different pair of vectors with revdot product $18$, and its stated formula holds as well.

Its verifier does not read the cross terms either. The prover packs them into a vector $\mathbf{E}$ and commits to it, and the public vector $\mathbf{W}$ holds their weights in mirrored positions, so that the weighted sum becomes one more revdot product $\epsilon =⟨⟨\mathbf{E},\mathbf{W}⟩⟩$. With the numbers of Section 5 and one layer:

The six cross terms of Section 5, packed row by row, give $\mathbf{E}=(37,19,35,27,36,27,0,0)$. The public vector with the weights mirrored is $\mathbf{W}=(0,0,38,6,25,36,21,35)$, and $\epsilon =⟨⟨\mathbf{E},\mathbf{W}⟩⟩=12$. The diagonal contributes $7$, so the target of the folded pair is $7+12=19$, the value of $c^{\ast }$ from Section 5.

The fold then leaves three revdot claims, $(A,B)$ and one $(E,W)$ per layer, and the split of chapter 05 proves a random combination of them. This is the one place that pays for the product polynomial and its FFTs. The chapter on recursion in Ragu continues from there.

12. Where this chapter leaves us

This chapter took the following steps:

1. A revdot claim has the instance $(\bar{A},\bar{B},c)$ and the witness $(\mathbf{a},\mathbf{b},{\gamma }_a,{\gamma }_b)$, and neither the direct check nor the split suits every step of a long computation.
2. Folding two claims with one challenge needs one cross term, but with three claims a cross term shares a power of $r$ with a claimed value, which lets a false claim pass at every $r$.
3. Independent weights give each cell of the error matrix its own monomial, and the book's choice is ${\mu }^{-i}$ and $(\mu \nu {)}^j$. The prover sends the $m^2-m$ off-diagonal cells before the challenges.
4. The result has the form of its inputs, so it serves as an accumulator, and steps avoid the split and its FFTs. A decider finishes with two MSMs and one revdot product.
5. A spot check at a random $\theta$ replaces the commitment sums in the circuit with field arithmetic and evaluation claims for chapter 08's batching.
6. Two layers with fresh challenges cut the quadratic field arithmetic, from $(MN{)}^2+1$ constraints to $N{M}^2+N^2-N+3$.
7. A false claim passes only at rare challenges, as long as each layer's messages come before that layer's challenges and nobody knows a relation among the generators. If it passes, it stays false until the decider.
8. Ragu's fuse replaces the matrix with a quotient polynomial of $m-1$ coefficients and one challenge per layer, using Lagrange weights. Compression keeps a committed form of the matrix and then runs the split.

The fold accepts any $\bar{B}$ whose vector has the right product, and we have not yet asked whether that vector contains the right circuit's wiring. The verifier's other linear cost, computing $s(x,y)$, concerns the same question. The next chapter answers it.