The Inner Product Argument

The previous chapter reduced a polynomial evaluation to one statement about a secret vector, and it finished the exchange by revealing that vector. This chapter replaces the reveal with a proof whose size grows with the logarithm of the vector's length. The idea is to turn a claim about a vector of length $n$ into a claim of the same shape about a vector of length $n/2$, and to repeat this until one scalar is left, which the prover can send.

We derive one halving round in full, run the argument by hand on the toy curve, and then look at what cheating would take and what the verifier pays. The last sections compare this textbook form with the version in Ragu's code, which differs in several visible ways while proving the same claim.

1. The claim to prove

Section 9 of the previous chapter ended with this statement, where $U$ is an extra generator and ${\mathbf{x}}^{\mathbf{n}}$ is the vector of powers of $x$:

$$\text{given }\mathbf{G},U,P,x,\text{ the prover knows }\mathbf{a}\text{ such that }P=⟨\mathbf{a},\mathbf{G}⟩+⟨\mathbf{a},{\mathbf{x}}^{\mathbf{n}}⟩\cdot U.$$

The halving step never uses the fact that the second vector consists of powers, so we write $\mathbf{b}$ for it until Section 8 needs the powers again:

$$P=⟨\mathbf{a},\mathbf{G}⟩+⟨\mathbf{a},\mathbf{b}⟩\cdot U.$$

The verifier knows $\mathbf{G}$, $\mathbf{b}$, $U$ and $P$. Only the prover knows $\mathbf{a}$. We keep the running example from the previous chapter, the polynomial $p(X)=7+2X+5X^2+3X^3$ at $x=9$:

2. Halving produces cross terms

To shorten $\mathbf{a}$, the prover has to combine its entries. A natural way to do this is to split each vector into a lower and an upper half, written ${\mathbf{a}}_{lo},{\mathbf{a}}_{hi}$ and ${\mathbf{G}}_{lo},{\mathbf{G}}_{hi}$, and add the halves. Each half has length $n/2$, so the sums do too.

Now compare the commitment before and after. The original commitment pairs each half with its own half of the generators:

$$⟨\mathbf{a},\mathbf{G}⟩=⟨{\mathbf{a}}_{lo},{\mathbf{G}}_{lo}⟩+⟨{\mathbf{a}}_{hi},{\mathbf{G}}_{hi}⟩.$$

The shortened vectors pair every half with every other half, because the inner product distributes over the sums:

$$⟨{\mathbf{a}}_{lo}+{\mathbf{a}}_{hi},{\mathbf{G}}_{lo}+{\mathbf{G}}_{hi}⟩=⟨{\mathbf{a}}_{lo},{\mathbf{G}}_{lo}⟩+⟨{\mathbf{a}}_{hi},{\mathbf{G}}_{hi}⟩+⟨{\mathbf{a}}_{hi},{\mathbf{G}}_{lo}⟩+⟨{\mathbf{a}}_{lo},{\mathbf{G}}_{hi}⟩.$$

The last two terms are cross terms, and they are what stands between the short vectors and the original commitment. In this section and the next we use the second vector from the previous chapter, because the running vector has $⟨{\mathbf{a}}_{hi},{\mathbf{G}}_{hi}⟩=\mathcal{O}$ by coincidence, and an identity point would hide the effect we want to see.

Take $\mathbf{d}=(3,1,8,4)$, whose commitment is $C_d=(6,23)$. It splits into ${\mathbf{d}}_{lo}=(3,1)$ and ${\mathbf{d}}_{hi}=(8,4)$, and the four inner products between the halves are:

The first two pieces add up to $C_d$. The plain sums are ${\mathbf{d}}_{lo}+{\mathbf{d}}_{hi}=(11,5)$ and ${\mathbf{G}}_{lo}+{\mathbf{G}}_{hi}=((28,10),(18,10))$, and their inner product is $(30,23)$. That point is the sum of all four pieces, so it differs from $C_d$.

The cross terms depend on $\mathbf{a}$, so the verifier cannot compute them. The prover has to send them. That creates a new problem, because a prover who sends two points and then folds in a fixed, known way could pick those points to make any claim look consistent. Section 6 turns this into an explicit attack. The fix is to weight the halves with a random challenge that the verifier picks after the prover has sent the cross terms, so that the prover cannot tailor them to the weights.

3. Choosing the weights

The weights must not disturb the two terms that make up the original commitment. Suppose we scale the upper half of $\mathbf{a}$ by a scalar $\alpha$ and the upper half of $\mathbf{G}$ by a scalar $\beta$. Expanding as before gives

$$⟨{\mathbf{a}}_{lo}+\alpha {\mathbf{a}}_{hi},{\mathbf{G}}_{lo}+\beta {\mathbf{G}}_{hi}⟩=⟨{\mathbf{a}}_{lo},{\mathbf{G}}_{lo}⟩+\alpha \beta ⟨{\mathbf{a}}_{hi},{\mathbf{G}}_{hi}⟩+\alpha ⟨{\mathbf{a}}_{hi},{\mathbf{G}}_{lo}⟩+\beta ⟨{\mathbf{a}}_{lo},{\mathbf{G}}_{hi}⟩.$$

For the second term to keep weight 1 we need $\alpha \beta =1$, so $\alpha$ and $\beta$ must be inverses of each other. This is why inverses of the challenge appear throughout the argument. One half of the pair goes on the scalars and the other goes on the generators, and they cancel exactly on the terms we want to keep.

Take the weight $3$, whose inverse modulo 43 is $29$. Scaling both high halves by $3$ gives $(26,8)$. Removing the cross pieces, each of which carries weight $3$, leaves $(17,7)$, which is $⟨{\mathbf{d}}_{lo},{\mathbf{G}}_{lo}⟩+9⟨{\mathbf{d}}_{hi},{\mathbf{G}}_{hi}⟩$ and not $C_d$. Scaling ${\mathbf{d}}_{hi}$ by $29$ and ${\mathbf{G}}_{hi}$ by $3$ gives $(4,6)$. Removing the cross pieces, which now carry weights $29$ and $3$, leaves $(6,23)=C_d$.

The scale of each half is also free, as long as the product over a matching pair of halves stays 1. Bulletproofs and the Ragu Book spread the challenge $u$ over both halves, which gives weights $u,u^{-1}$ on the scalars and $u^{-1},u$ on the generators. This symmetric form puts $u^{\pm 2}$ on the cross terms, and it leads to the tidy formula in Section 8. Ragu's code uses the one-sided form from the display above, with the lower halves unweighted, and Section 9 shows that the two forms differ only by a rescaling.

4. One round of folding

The second vector $\mathbf{b}$ pairs with $\mathbf{a}$ in the same way that $\mathbf{G}$ does, so it needs the same weights as $\mathbf{G}$ to keep $⟨\mathbf{a},\mathbf{b}⟩$ intact. One round therefore defines, for a challenge $u$,

$$\begin{array}{rl}{\mathbf{a}}^{\prime }& =u{\mathbf{a}}_{lo}+u^{-1}{\mathbf{a}}_{hi},\\ {\mathbf{b}}^{\prime }& =u^{-1}{\mathbf{b}}_{lo}+u{\mathbf{b}}_{hi},\\ {\mathbf{G}}^{\prime }& =u^{-1}{\mathbf{G}}_{lo}+u{\mathbf{G}}_{hi}.\end{array}$$

We now find the point that these three vectors commit to. Expanding the first inner product term by term gives

$$\begin{array}{rl}⟨{\mathbf{a}}^{\prime },{\mathbf{G}}^{\prime }⟩& =⟨u{\mathbf{a}}_{lo}+u^{-1}{\mathbf{a}}_{hi},u^{-1}{\mathbf{G}}_{lo}+u{\mathbf{G}}_{hi}⟩\\ & =u{u}^{-1}⟨{\mathbf{a}}_{lo},{\mathbf{G}}_{lo}⟩+uu⟨{\mathbf{a}}_{lo},{\mathbf{G}}_{hi}⟩+u^{-1}{u}^{-1}⟨{\mathbf{a}}_{hi},{\mathbf{G}}_{lo}⟩+u^{-1}u⟨{\mathbf{a}}_{hi},{\mathbf{G}}_{hi}⟩\\ & =⟨\mathbf{a},\mathbf{G}⟩+u^2⟨{\mathbf{a}}_{lo},{\mathbf{G}}_{hi}⟩+u^{-2}⟨{\mathbf{a}}_{hi},{\mathbf{G}}_{lo}⟩.\end{array}$$

The scalar inner product expands in exactly the same way, because ${\mathbf{b}}^{\prime }$ has the same weights as ${\mathbf{G}}^{\prime }$:

$$⟨{\mathbf{a}}^{\prime },{\mathbf{b}}^{\prime }⟩=⟨\mathbf{a},\mathbf{b}⟩+u^2⟨{\mathbf{a}}_{lo},{\mathbf{b}}_{hi}⟩+u^{-2}⟨{\mathbf{a}}_{hi},{\mathbf{b}}_{lo}⟩.$$

Next we form the point $P^{\prime }=⟨{\mathbf{a}}^{\prime },{\mathbf{G}}^{\prime }⟩+⟨{\mathbf{a}}^{\prime },{\mathbf{b}}^{\prime }⟩\cdot U$ by adding the first expansion to $U$ times the second, and we collect terms by their power of $u$:

$$\begin{array}{rl}{P}^{\prime }& =⟨\mathbf{a},\mathbf{G}⟩+⟨\mathbf{a},\mathbf{b}⟩\cdot U\\ & +u^{-2}\left(⟨{\mathbf{a}}_{hi},{\mathbf{G}}_{lo}⟩+⟨{\mathbf{a}}_{hi},{\mathbf{b}}_{lo}⟩\cdot U\right)\\ & +u^2\left(⟨{\mathbf{a}}_{lo},{\mathbf{G}}_{hi}⟩+⟨{\mathbf{a}}_{lo},{\mathbf{b}}_{hi}⟩\cdot U\right).\end{array}$$

The first line is $P$. The other two brackets are the two points the prover must send, and we name them

$$\begin{array}{rl}L& =⟨{\mathbf{a}}_{hi},{\mathbf{G}}_{lo}⟩+⟨{\mathbf{a}}_{hi},{\mathbf{b}}_{lo}⟩\cdot U,\\ R& =⟨{\mathbf{a}}_{lo},{\mathbf{G}}_{hi}⟩+⟨{\mathbf{a}}_{lo},{\mathbf{b}}_{hi}⟩\cdot U.\end{array}$$

This gives the update rule for the statement point:

$$P^{\prime }=P+u^{-2}\cdot L+u^2\cdot R.$$

The verifier can compute everything on the right once it has $L$ and $R$, and it can fold $\mathbf{G}$ and $\mathbf{b}$ itself because they are public. Only ${\mathbf{a}}^{\prime }$ remains in the prover's hands. The result is a new claim with the same shape as the old one, at half the length:

$$P^{\prime }=⟨{\mathbf{a}}^{\prime },{\mathbf{G}}^{\prime }⟩+⟨{\mathbf{a}}^{\prime },{\mathbf{b}}^{\prime }⟩\cdot U.$$

The order of the messages matters, because the prover must commit to $L$ and $R$ before it learns $u$:

5. A complete run on the toy curve

For $n=4$ the argument takes $k={\log }_{2}n=2$ rounds. We number rounds in the order they happen, write ${\mathbf{a}}^{(j)}$ for the vector after round $j$, and start from ${\mathbf{a}}^{(0)}=\mathbf{a}$, ${\mathbf{b}}^{(0)}=\mathbf{b}$, ${\mathbf{G}}^{(0)}=\mathbf{G}$ and $P^{(0)}=P$. The challenges below are picked by hand so that the numbers avoid accidental coincidences. Fiat–Shamir, covered in Statements and Challenges, would derive them from a transcript in a real proof.

Round 1

The prover computes the cross terms from the secret vector:

After it receives $L_1$ and $R_1$, the verifier picks the challenge:

The verifier sends $u_1=15$. Its inverse is $u_1^{-1}=23$, and the weights on the cross terms are $u_1^{-2}=13$ and $u_1^2=10$.

Both parties fold what they hold. The last two rows of the next table compute the same point in two ways, once by the verifier from public values and once by the prover from the folded secret vector:

The inner product changes the way the algebra predicts: $37+13\cdot 32+10\cdot 4=20$ modulo 43, and direct computation of $⟨{\mathbf{a}}^{(1)},{\mathbf{b}}^{(1)}⟩$ gives $20$ as well.

Round 2

The second round applies the same steps to vectors of length 2, so each half now has one entry:

The verifier sends $u_2=10$, with $u_2^{-1}=13$, $u_2^{-2}=40$ and $u_2^2=14$.

The final check

All three vectors now have one entry, so the prover can send its scalar without exposing a long vector. We write $\hat{a}$, $\hat{b}$ and $\hat{G}$ for the single entries left at the end. The claim $P^{(k)}=⟨{\mathbf{a}}^{(k)},{\mathbf{G}}^{(k)}⟩+⟨{\mathbf{a}}^{(k)},{\mathbf{b}}^{(k)}⟩\cdot U$ becomes

$$P^{(k)}=\hat{a}\cdot \hat{G}+\hat{a}\hat{b}\cdot U=\hat{a}\cdot (\hat{G}+\hat{b}\cdot U).$$

The prover sends $\hat{a}=4$. The verifier already holds $\hat{b}=19$ and $\hat{G}=(20,25)$ from folding, and it checks one equation:

$$P^{(2)}=(14,22),\hat{a}\cdot (\hat{G}+\hat{b}\cdot U)=4\cdot ((20,25)+19\cdot U)=(14,22).$$

The two points match, so the verifier accepts.

Unrolling the update rule gives the whole check in one line, which is how an implementation evaluates it:

$$P+\sum _{j=1}^k\left(u_j^{-2}\cdot L_j+u_j^2\cdot R_j\right)=\hat{a}\cdot (\hat{G}+\hat{b}\cdot U).$$

The whole proof is $L_1=(22,7)$, $R_1=(30,8)$, $L_2=(28,21)$, $R_2=(14,9)$ and $\hat{a}=4$. For $n=4$ that is four points and one scalar, against the four scalars of revealing $\mathbf{a}$. The saving only appears at larger $n$, because the proof grows with ${\log }_{2}n$.

6. Why cheating fails

The verifier never sees $\mathbf{a}$, so we need a reason to believe that a false claim cannot pass. We start with a prover who lies about the value and follows the protocol otherwise:

Claim $y=38$ instead of $37$, so the statement point is $C+38\cdot U=(1,29)$, and fold honestly from $\mathbf{a}$. Running the argument for all $1764$ pairs of nonzero challenges gives 1764 rejections and no acceptances, because the extra $1\cdot U$ stays in the folded point in every round.

A cheater can do more than this, because $L_j$ and $R_j$ can be any points it likes. To see the limits of that freedom, we track one number through the protocol.

The gap

Assume for now that the prover builds every point from the public generators and knows the coefficients it used, and that nobody knows a relation among the generators. Then each point $X$ the prover handles has one expression $X=⟨\mathbf{c},\mathbf{G}⟩+t\cdot U$, so the following number is well defined:

$$\text{gap}(X)=t-⟨\mathbf{c},\mathbf{b}⟩.$$

The statement is true exactly when $\text{gap}(P)=0$, since that says the coefficient of $U$ equals the inner product of the coefficients of $\mathbf{G}$ with $\mathbf{b}$. The gap is linear in the point, which means $\text{gap}(X+r\cdot Y)=\text{gap}(X)+r\text{gap}(Y)$. It also has simple values on the generators, namely $\text{gap}(G_i)=-b_i$ and $\text{gap}(U)=1$.

Now look at the right side of the final check. For a folded generator, linearity gives

$$\text{gap}(u^{-1}\cdot G_i+u\cdot G_{i+n/2})=-(u^{-1}{b}_i+u{b}_{i+n/2})=-b_i^{\prime },$$

so each folded generator has the folded entry of $\mathbf{b}$ as its negative gap, and this repeats in every round. At the end $\text{gap}(\hat{G})=-\hat{b}$, and therefore

$$\text{gap}\left(\hat{a}\cdot (\hat{G}+\hat{b}\cdot U)\right)=\hat{a}(-\hat{b}+\hat{b})=0$$

for every possible $\hat{a}$. Without any relation among the generators, two equal points have equal coefficients and so equal gaps. A passing proof therefore needs the left side of the check to have gap zero as well:

$$\text{gap}(P)+\sum _{j=1}^k\left(u_j^{-2}\text{gap}(L_j)+u_j^2\text{gap}(R_j)\right)=0.$$

Counting the challenges a cheater can survive

Let $e$ be the gap of the current statement point at the start of some round, and suppose $e\ne 0$. The prover fixes $L$ and $R$, and then the verifier picks $u$. The new gap is zero only if, with $w=u^2$,

$$e+w^{-1}\text{gap}(L)+w\text{gap}(R)=0.$$

Multiplying by $w$ gives the polynomial equation $\text{gap}(R)w^2+ew+\text{gap}(L)=0$. Its middle coefficient is $e\ne 0$, so the polynomial is not zero, whatever the prover chose. By the root count from Statements and Challenges it has at most 2 roots $w$, and each root has at most 2 square roots $u$. At most 4 challenges in a round can therefore clear a nonzero gap, and the same bound holds for every vector length.

We can test this on a two-entry vector. Comparing coefficients of each generator gives three equations in the final scalar, and we can check them directly for every strategy in a family:

Take $\mathbf{a}=(7,2)$, $\mathbf{b}=(1,9)$, and the false value $y=26$, so the true inner product is $25$ and the statement has gap $1$. Keep the honest $\mathbf{G}$ coefficients in $L$ and $R$, and try all $1849$ choices of their $U$ coefficients. For each choice, test all 42 nonzero challenges against the equations for $G_0$, $G_1$ and $U$ with the final scalar free. The largest number of passing challenges is $4$, and the honest $U$ coefficients pass none. A further $5,625$ strategies with altered $\mathbf{G}$ coefficients, taken from a grid of values, reach at most $2$, and in every passing case the gap equation holds.

A false statement starts with a nonzero gap and must reach gap zero by the end, so the gap has to be cleared in one of the $k$ rounds. The chance of this is at most $4k$ divided by the number of nonzero challenges. On the toy curve this is a large fraction, which is one more way the toy curve is insecure. On a real curve the fraction is negligible:

For $n=2^{13}$ over a Pasta scalar field, which has about $2^{254}$ elements, this bound is $52$ divided by about $2^{254}$, which is below $2^{-248}$.

Why the challenge must come after the cross terms

The count above relies on $L$ and $R$ being fixed before $u$. If the prover sees the challenge first, it can solve the equation for the point it still has to send:

Suppose the prover knows $u_1=15$ before it sends $R_1$, and it wants to pass with the false statement $y=38$, whose point carries an extra $1\cdot U$. It replaces the honest $R_1=(30,8)$ by $R_1-u_1^{-2}\cdot 1\cdot U=(28,10)$. The weight $u_1^2$ then turns the change into $-1\cdot U$, and $P^{(1)}$ comes out as $(30,23)$, exactly the honest folded point. The rest of the run is honest, and the verifier accepts.

The same altered point does poorly when the challenge arrives afterwards:

Now fix that altered $R_1$ first and let the challenge vary. Running the protocol for all 42 nonzero values of $u_1$ gives acceptance only at $u_1\in \{15,28\}$, the guess and its negative, which share the same square. The prover wins with probability $2/42$.

In this attack $\text{gap}(P)=1$, $\text{gap}(L_1)=0$ and $\text{gap}(R_1)=30$. The equation $1+30\cdot u_1^2=0$ has the solutions $u_1^2=10$, which are the two challenges just found.

In a non-interactive proof this ordering becomes a requirement on the transcript. Every $L_j$ and $R_j$ must go into the hash before $u_j$ comes out, for the reason given in the section on omitted transcript data.

Why the generators must have no known relation

The gap only makes sense if each point has one expression in the generators. On the toy curve every point is a known multiple of every other point, so the gap has no fixed meaning there, and the final scalar can absorb any error:

Keep the false statement $y=38$ and the honest $L_j,R_j$. With challenges $(15,10)$ the folded point is $(7,6)$, and the right side of the check is a multiple of $\hat{G}+\hat{b}\cdot U=(30,23)$. Every point on the toy curve is a known multiple of $G_0$, so the prover can divide logs: $\hat{a}=16/35=41$. Then $41\cdot (30,23)=(7,6)$ and the verifier accepts the false value. This is the attack the discrete log relation assumption rules out on a real curve.

The argument above therefore rests on the following assumptions. The discrete log relation assumption from the previous chapter holds for $\mathbf{G}$ together with $U$. The prover builds its points from the generators with coefficients it knows. The challenges are uniform and come after the points they weight, which in a non-interactive proof means treating the transcript hash as a random oracle. This section gives the reasoning informally and is not a security proof.

7. The verifier's linear cost

The proof is short, but the verifier still has to compute $\hat{G}$ and $\hat{b}$. Folding $\mathbf{G}$ round by round costs about $n$ scalar multiplications in the first round, $n/2$ in the second, and so on. The verifier can do better by computing the final point in one step, which requires knowing the final weight of each original generator.

For $n=4$ we can substitute one round into the other. The first round gives

$${\mathbf{G}}^{(1)}=\left(u_1^{-1}\cdot G_0+u_1\cdot G_2,u_1^{-1}\cdot G_1+u_1\cdot G_3\right),$$

and the second round combines those two entries with weights $u_2^{-1}$ and $u_2$:

$$\begin{array}{rl}\hat{G}& =u_2^{-1}\cdot (u_1^{-1}\cdot G_0+u_1\cdot G_2)+u_2\cdot (u_1^{-1}\cdot G_1+u_1\cdot G_3)\\ & =u_1^{-1}{u}_2^{-1}\cdot G_0+u_1^{-1}{u}_2\cdot G_1+u_1{u}_2^{-1}\cdot G_2+u_1{u}_2\cdot G_3.\end{array}$$

Each generator's weight is a product with one factor per round. Round $j$ contributes $u_j$ if the generator sat in the upper half at that round and $u_j^{-1}$ if it sat in the lower half. Reading the index $i$ in binary, round 1 looks at the highest bit and the last round at the lowest. This defines the vector $\mathbf{s}$ with

$$s_i=\prod _{j=1}^k{u}_j^{\pm 1},\text{with exponent }+1\text{ when bit }k-j\text{ of }i\text{ is }1,\text{ and }-1\text{ otherwise},$$

and it gives $\hat{G}=⟨\mathbf{s},\mathbf{G}⟩$. The vector $\mathbf{b}$ folds with the same weights, so $\hat{b}=⟨\mathbf{s},\mathbf{b}⟩$ for the same $\mathbf{s}$. Here is the table for our run:

With $(u_1,u_2)=(15,10)$, the multi-scalar multiplication $⟨\mathbf{s},\mathbf{G}⟩$ gives $(20,25)$, the same point as $\hat{G}$ from the round-by-round folding. The same weights applied to $\mathbf{b}$ give $⟨\mathbf{s},\mathbf{b}⟩=19=\hat{b}$.

Computing $\hat{G}$ this way is one multi-scalar multiplication (MSM) with $n$ terms. An MSM of that size is cheaper than folding, but its cost still grows linearly with $n$, and no shortcut is available, because the generators are independent points with no structure to exploit.

8. The polynomial g(X)

The scalar $\hat{b}$ is cheaper than $\hat{G}$, because $\mathbf{b}$ has structure that $\mathbf{G}$ lacks. Its entries are powers of $x$, so $b_{i+n/2}=x^{n/2}{b}_i$. Substituting this into the fold gives

$$b_i^{\prime }=u^{-1}{b}_i+u{b}_{i+n/2}=(u^{-1}+u{x}^{n/2})b_i.$$

One round therefore multiplies the first half of $\mathbf{b}$ by a single factor, and the result is still a power vector up to that factor.

In the run of Section 5, ${\mathbf{b}}^{(1)}=(34,5)$. The predicted factor is $u_1^{-1}+u_1{x}^2=23+15\cdot 38=34$, and $34\cdot (1,9)=(34,5)$ modulo 43.

Round $j$ acts on a vector of length $2^{k-j+1}$, so its factor uses the exponent $2^{k-j}$. Multiplying the factors of all $k$ rounds gives the final entry. Replacing $x$ with a variable defines the polynomial

$$g(X)=\prod _{j=1}^k\left(u_j^{-1}+u_j{X}^{2^{k-j}}\right),$$

and then $\hat{b}=g(x)$. The coefficients of this polynomial are the entries of $\mathbf{s}$. To see this, expand the product by choosing one term from each factor. Choosing $u_j{X}^{2^{k-j}}$ adds $2^{k-j}$ to the power of $X$ and contributes $u_j$, while choosing $u_j^{-1}$ adds nothing and contributes $u_j^{-1}$. The coefficient of $X^i$ then comes from the single choice that matches the binary digits of $i$, which is the rule for $s_i$ from Section 7.

With $(u_1,u_2)=(15,10)$, the polynomial is $g(X)=(23+15X^2)(13+10X)$. Multiplying it out gives coefficients $(41,15,23,21)$, which is the $\mathbf{s}$ of the table. At $x=9$ the first factor is $23+15\cdot 38=34$, the second is $13+10\cdot 9=17$, and their product is $19=\hat{b}$.

Ordering mistakes are easy to make here, so we also check a longer case:

The script behind this chapter repeats the comparison for $k=3$ with eight generators and challenges $(3,5,7)$: round-by-round folding gives $\hat{G}=(25,2)$, and the coefficients of $g$ give the same point through one multi-scalar multiplication. The folded power vector and $g(9)$ also agree, at $37$.

The book's listing of $\mathbf{s}$ matches this after relabelling rounds. With rounds numbered downward, its $u_j$ is our $u_{k+1-j}$, and its second entry has a positive exponent on $u_1$, its last challenge, which is our $s_1$.

This also gives a compact statement of the verifier's costs. The expression $\hat{G}=⟨\mathbf{s},\mathbf{G}⟩$ says that $\hat{G}$ is the Pedersen commitment to $g$, whose coefficient vector is $\mathbf{s}$:

Everything in this table except the two rows involving all of $\mathbf{s}$ is logarithmic in $n$. A recursive verifier cannot afford those rows, because it would have to perform them inside a circuit. The accumulation chapter works from this exact point. It notices that $\hat{G}$ is a claim about the commitment to a polynomial with a short description, namely the $k$ challenges, and it postpones checking that claim.

9. The code's one-sided fold

The remaining sections compare the form above with Ragu's implementation, which the code describes as adapted from halo2. The differences fall into two groups. This section covers how the code folds, and the next covers what statement it folds.

The code leaves the lower halves unweighted. To avoid mixing up the two conventions, we write $w$ for the challenge in this form, although the code calls it $u_j$:

$$\begin{array}{rl}{\mathbf{a}}^{\prime }& ={\mathbf{a}}_{lo}+w^{-1}{\mathbf{a}}_{hi},\\ {\mathbf{b}}^{\prime }& ={\mathbf{b}}_{lo}+w{\mathbf{b}}_{hi},\\ {\mathbf{G}}^{\prime }& ={\mathbf{G}}_{lo}+w{\mathbf{G}}_{hi}.\end{array}$$

These are the lines in prover.rs that fold the two scalar vectors:

for i in 0..half {
    p_prime[i] = p_prime[i] + &(p_prime[i + half] * &u_j_inv);
    b[i] = b[i] + &(b[i + half] * &u_j);
}

Repeating the expansion from Section 4 with these weights gives the terms $w^{-1}L$ and $wR$, with the same $L$ and $R$:

$$\begin{array}{rl}⟨{\mathbf{a}}^{\prime },{\mathbf{G}}^{\prime }⟩& =⟨{\mathbf{a}}_{lo},{\mathbf{G}}_{lo}⟩+w⟨{\mathbf{a}}_{lo},{\mathbf{G}}_{hi}⟩+w^{-1}⟨{\mathbf{a}}_{hi},{\mathbf{G}}_{lo}⟩+⟨{\mathbf{a}}_{hi},{\mathbf{G}}_{hi}⟩,\\ P^{\prime }& =P+w^{-1}\cdot L+w\cdot R.\end{array}$$

Setting $w=u^2$ makes this update identical to the symmetric one. The folded vectors then differ only by a scale factor. Writing ${\mathbf{a}}_{\text{sym}}^{\prime }$ for the symmetric fold,

$${\mathbf{a}}_{\text{sym}}^{\prime }=u{\mathbf{a}}_{lo}+u^{-1}{\mathbf{a}}_{hi}=u\left({\mathbf{a}}_{lo}+u^{-2}{\mathbf{a}}_{hi}\right)=u{\mathbf{a}}^{\prime },$$

and likewise ${\mathbf{G}}_{\text{sym}}^{\prime }=u^{-1}{\mathbf{G}}^{\prime }$ and ${\mathbf{b}}_{\text{sym}}^{\prime }=u^{-1}{\mathbf{b}}^{\prime }$. The factors cancel in both inner products, which explains why the statement point does not change.

Run the same statement $P=(5,29)$ with the code's weights and the squared challenges $(w_1,w_2)=(10,14)$, which are the squares of $(15,10)$ modulo 43.

The product of the challenges is $u_1{u}_2=21$, and multiplying the one-sided scalar by it gives $35\cdot 21=4=\hat{a}$. Dividing the one-sided $\mathbf{b}$ entry and generator by it gives $\hat{b}$ and $\hat{G}$ as well. Both forms pass their final checks.

The one-sided form also changes the polynomial. In the verifier code, compute_b and compute_s work with ${\prod }_{j=1}^k(1+w_j{X}^{2^{k-j}})$, which equals the symmetric $g(X)$ times ${\prod }_j{u}_j$ when $w_j=u_j^2$:

For $(w_1,w_2)=(10,14)$, the code's polynomial is $(1+10X^2)(1+14X)$, with coefficients $(1,14,10,11)$. Dividing them by $u_1{u}_2=21$ gives $(41,15,23,21)$, the coefficients of the symmetric $g$. At $x=9$ the code's polynomial takes the value $12$, which is the one-sided $\mathbf{b}$ entry from the table above.

The code's challenges are not literally squares, since a hash outputs $w_j$ directly. A uniform $w_j$ could be a non-square, so the one-sided form is not a change of variables for every challenge, though the expansion above holds for any nonzero $w$. The gap argument of Section 6 also carries over, with the simpler conclusion that a round has at most 2 surviving challenges.

10. The code's opening statement

The book opens $P=C+y\cdot U$ directly. The code makes three changes to the statement before it starts folding, and each change answers a specific need. Throughout, $C$ is the polynomial commitment and $v$ is the claimed value, which is the $y$ of the earlier sections.

Moving the value into the constant coefficient

The polynomial $p(X)-v$ has a root at $x$ exactly when $p(x)=v$. Its coefficient vector differs from $\mathbf{a}$ only in the constant entry, and its commitment is $C-v\cdot G_0$, where $G_0$ here is the first public generator. The verifier can compute this point itself. The claim then has the form "this commitment has inner product zero with $\mathbf{b}$", which removes the need for any $U$ term in the starting point, since $0\cdot U=\mathcal{O}$.

Adding a mask

The final scalar is a fixed linear combination of the coefficients, with weights the verifier can compute, so sending it reveals one piece of information about $\mathbf{a}$. To hide that combination, the prover picks a random polynomial that has a root at $x$, commits to it, and adds a random multiple of it:

Start from the random vector $(11,4,19,6)$, whose polynomial takes the value $26$ at $x=9$. Subtracting that from the constant coefficient gives ${\mathbf{s}}_{\text{mask}}=(28,4,19,6)$, whose polynomial has a root at $9$. Its commitment is $S=(6,23)$.

The notation ${\mathbf{s}}_{\text{mask}}$ keeps this vector apart from the weight vector $\mathbf{s}$ of Section 7. The code uses the letter $s$ for both, as s_poly and compute_s. Adding $\xi \cdot S$, for a challenge $\xi$ sampled after $S$, gives the statement that the code folds:

$$P^{\prime }=C-v\cdot G_0+\xi \cdot S,{\mathbf{a}}^{\prime }=\mathbf{a}+\xi {\mathbf{s}}_{\text{mask}}-(v,0,\dots ,0).$$

The inner product of ${\mathbf{a}}^{\prime }$ with $\mathbf{b}$ is $p(x)+\xi \cdot 0-v$, which is zero exactly when the claim is true.

With $\xi =6$, the combined vector is $\mathbf{a}+6{\mathbf{s}}_{\text{mask}}=(3,26,33,39)$. It still evaluates to $37$ at $x=9$, because the mask contributes zero there. Subtracting $v=37$ from the constant coefficient gives ${\mathbf{a}}^{\prime }=(9,26,33,39)$, and direct evaluation gives $⟨{\mathbf{a}}^{\prime },\mathbf{b}⟩=0$. The verifier computes $P^{\prime }=C-37\cdot G_0+6\cdot S=(23,24)$, and committing to ${\mathbf{a}}^{\prime }$ directly gives $(23,24)$.

The order matters for the same reason as before. If the mask did not vanish at $x$, it could shift the evaluation, and a prover who knew $\xi$ in advance could choose the mask to cover a false value. Fixing $S$ before $\xi$ removes that choice:

Suppose the prover claims the false value $v=38$ and commits to the unadjusted mask $(11,4,19,6)$, which takes the value $26$ at $x=9$. The combination evaluates to the claimed value only if $37+\xi \cdot 26=38$, so the prover needs $\xi =5$. Running the full argument for all 43 values of $\xi$ gives acceptance at $\xi =5$ and nowhere else, a chance of $1/43$.

The mask changes the value the prover reveals at the end:

Rerunning the same challenges with no mask gives the final scalar $7$, which is a fixed linear combination of the coefficients once the challenges are public. With the mask it is $4$, and it also depends on the random entries of ${\mathbf{s}}_{\text{mask}}$.

The module documentation says the mask is retained for the folded coefficients, and also that the IPA at this commit has no Pedersen blinding, so neither the commitment nor the $L_j,R_j$ carry a blinding term. The mask is therefore not a claim that the argument is zero knowledge. This matches the status recorded in chapter 02, where the Ragu Book and code do not yet establish zero knowledge. The same documentation records a limitation of unblinded round commitments. A valid opening can produce an identity $L_j$ or $R_j$, for example $R$ with two coefficients at $x=0$, and the transcript rejects identity points.

Scaling U by a challenge

The statement in Section 1 uses a fixed $U$, and that leaves a weakness the earlier sections did not need to address. A prover could send a commitment with a hidden $U$ component, $C^{\ast }=⟨\mathbf{a},\mathbf{G}⟩+\delta \cdot U$. This point is not a commitment to any polynomial under $\mathbf{G}$ alone, but it can still be opened, because the extra $\delta$ makes up the difference between the true evaluation and a false claim.

The code handles this by sampling a challenge $z$ after $C$, $v$ and $S$ are in the transcript, and using $z\cdot U$ as the generator for inner products in every round. With ${\mathbf{a}}^{\prime }$ formed from the claimed $v$, the final check now requires $\delta =z⟨{\mathbf{a}}^{\prime },\mathbf{b}⟩$. The prover chose $\delta$ and $v$ before it saw $z$, so this can hold for only one value of $z$ when $\delta \ne 0$.

The prover sends $C^{\ast }=C+6\cdot U=(14,22)$ and claims $v=37-6=31$. The vector behind the $\mathbf{G}$ part of $C^{\ast }$ still evaluates to $37$, so the claim is false for that vector. After subtracting $v$, the inner product is $6$, and the spare $6\cdot U$ in $C^{\ast }$ supplies the matching $U$ term as long as $U$ carries weight 1. Running the argument for all 42 nonzero values of $z$ gives acceptance at $z=1$ only, which is the case where the scaling does nothing. A fixed, unscaled $U$ would therefore accept this claim every time, and a random $z$ accepts it with probability $1/42$.

The code's comment on $z$ gives this purpose in one line, saying that it ensures the prover did not interfere with the $U$ term in its commitments. The Halo 2 background page reaches the same goal in a different way, by having the verifier select a random group element $U$ before the argument begins. Ragu fixes $U$ in its public parameters and randomizes its weight instead. The book's description of the relation does not mention this step.

11. A complete run of the code's form

We can now run the code's protocol on the same claim. The challenges are again chosen by hand. The verifier starts from $P^{\prime }$, the prover computes each $L_j,R_j$ with weight $z$ on $U$, and the check the verifier comment states is

$$P^{\prime }+\sum _{j=1}^k\left(w_j^{-1}\cdot L_j+w_j\cdot R_j\right)=c\cdot \hat{G}+(c\hat{b}z)\cdot U,$$

where $c$ is the code's name for the final scalar, and $\hat{G}$ and $\hat{b}$ are built with the one-sided weights.

The verifier skips the round-by-round fold of $\mathbf{G}$ and $\mathbf{b}$. It computes both at the end from the challenges, as Sections 7 and 8 describe. In the compression verifier, which is where this IPA is checked at this commit, the call chain is verify_proof, then use_challenges, then eval, so the full linear MSM runs. The Guard type also offers use_g, which accepts a claimed $\hat{G}$ and returns the challenges alongside it as an Accumulator. No code under crates/ragu_pcd/src outside the IPA module calls it at this commit.

12. Comparing the two forms

The next table gathers the differences in one place. Both columns prove that a committed polynomial takes the value $v$ at $x$.

The Halo 2 background page uses a third labelling, in which $L_j$ pairs the lower half of $\mathbf{a}$ with the upper half of $\mathbf{G}$. Its $L$ is therefore this chapter's $R$, so a reader comparing the sources should check the pairing and not only the letter. Later chapters on this site use the symmetric $g(X)$ of Section 8, and they point out the code's form where it matters.

13. Where this chapter leaves us

This chapter took the following steps:

1. Folding a vector in half creates two cross terms, and weights that are inverses of each other keep the original commitment intact.
2. One round sends $L$ and $R$, receives $u$, and turns $P$ into $P+u^{-2}\cdot L+u^2\cdot R$, which is a claim of the same shape at half the length.
3. After $k={\log }_{2}n$ rounds the prover sends one scalar, so the proof has $2k$ points and one scalar.
4. A false claim has a nonzero gap, and each round lets at most 4 challenges clear it, provided the generators have no known relation and each challenge follows its cross terms.
5. The verifier's remaining cost is $\hat{G}=⟨\mathbf{s},\mathbf{G}⟩$, an MSM of size $n$, while $\hat{b}=g(x)$ takes only $k$ factors because of the product form of $g$.
6. Ragu's code uses one-sided weights, moves the value into the constant coefficient, adds a mask, and scales $U$ by a challenge, and it proves the same evaluation claim.

The IPA opens one polynomial at one point, and a proof in Ragu needs many openings. The next chapter reduces many evaluation claims to a single one, so that one IPA can finish the job.