Recursion in Ragu

Part four built the pieces one at a time. We have a way to fold revdot claims, a registry that makes wiring cheap to check, endoscalars that let challenges cross the curve cycle, and stages that let circuits share data. This chapter puts them together into the operation that Ragu actually runs, and then follows a finished proof out of the tree.

The first half describes one fuse. We list what it has to do, the order of its messages, the circuits that divide the work, the split of the transcript between two of those circuits, and the public inputs they share. The second half describes compression, with a complete run on the toy curve, and then covers what the verifier pays, the size of the result, rerandomization, and the comparison with Orchard.

1. What one fuse has to do

A fuse receives two child proofs and a step, and it has to produce a new proof that a parent can fuse in turn. Chapter 10 described the idea as a proof about a verifier. The children's verifier cannot run in full, so each child's expensive work joins an accumulator, and a fuse checks the cheap remainder inside its circuits. That remainder is still large, and a circuit may hold at most $n=2^{11}$ gates. These are the jobs:

Dividing the jobs among circuits creates a new need, because the circuits have to agree with each other. They must use the same challenges, and they must read the same child data. Stages give them shared witness data, and Section 5 gives them shared public inputs. So a fuse produces many small traces where a textbook recursion step would produce one large one.

In the standard profile, one fuse therefore fills $45$ native polynomials, of which $34$ are circuit traces and $11$ are stages, and $39$ nested polynomials, and it adds the $a$, $b$, registry_xy and $p$ polynomials on each side, for $92$ in all. The native side folds $86$ revdot claims and the nested side folds $72$.

Each internal circuit's claim counts once per child in the fold, since a parent checks both children's copies. All of these polynomials come from one call to fuse.

2. The order of the messages

Each challenge has to depend on everything it tests, so the order of the commitments is the backbone of a fuse. The code follows one schedule, and its phases sit in numbered files:

Nearly every row is a step of an earlier chapter. Phases 2 to 4 and 7 run the walk of chapter 15, phases 4 to 6 run the quotient fold of chapter 14, and phases 8 to 10 run the split accumulation of chapter 12.

Two details of the last rows matter later. Only pre_beta is ground, because it has to lie in the endoscalar range, so the prover re-blinds the eval stage and tries again until it does. And the internal circuits come last, because they prove statements about everything before them. Their traces feed no challenge of this fuse. Instead their commitments enter the parent's preamble, which puts them on the parent's transcript.

3. The internal circuits

We can now say what each circuit does. This table extends the one in Section 15 of the staging chapter, and it adds a column for the job:

The stage column shows why stages were worth building. The hashes_1 circuit computes each child's $k(y)$ and needs the child's data, which sits in the preamble. The collapse circuit reads that same data. Both read one polynomial, so a prover cannot show them different children, and only the bridge commitment has to enter the transcript.

The nested side has a shorter list. Its collapse checks the nested fold and pins its unified instance to the stages, its compute_v computes $v_n$, and 26 endoscaling steps walk the native batch. The loading polynomial ties the walk's points to the bridge stages. That side has no transcript and no application circuit, as chapter 13 found.

The application's circuit uses no stages. All of the machinery above sits beside it and leaves its budget of gates to the application.

4. Splitting the transcript

The transcript has to be replayed in circuit, because the Fiat–Shamir challenges would otherwise be numbers that the prover merely asserts. One circuit cannot hold the whole replay:

A permutation costs $288$ gates, and the code documents $3$ permutations in the first half and $5$ in the second. Together that makes $8$ permutations and $2,304$ gates, which already exceeds the limit of $2,048$ gates per circuit before any other check runs. The two halves cost $864$ and $1,440$ gates, so each fits.

So the replay has to cross a circuit boundary, and the sponge's state has to cross with it. The second circuit cannot recompute the state without repeating the permutations it is trying to avoid, and passing the state as a public input would add wires to every $k(Y)$. The code places it in a stage. The state is known once the inner error bridge is absorbed, and the outer error stage is the next one committed, because it holds values folded with the $\mu$ that the state produces.

We run this on the toy sponge from chapter 03. The bridge commitments are points on $E^{\prime }$, whose coordinates lie in ${\mathbb{F}}_{43}$, the field the sponge works in. The first point is the one chapter 17 built, and the others are stand-ins:

The first half ends by permuting and saving the three cells of the state, $(2,42,12)$. The second half loads those cells and squeezes $\mu =2$ with no further permutation, which is why its count starts from the absorption of outer_error. We ran the sponge once straight through and once split at this point, and all nine challenges agree. The toy sponge takes $3$ permutations in the first half and $5$ in the second, as the code does, because we leave out the domain tag and its rate of 2 fits one point per permutation.

Reading the state from a stage leaves one question, which is what forces the stage to hold the right value. Only hashes_1 knows that value, having computed it, so the check goes in that circuit:

// save_state() applies a permutation (since there's pending absorbed data)
// and returns the raw state, ready for squeeze-mode resumption in hashes_2.
transcript
    .save_state(dr)
    .expect("save_state should succeed after absorbing")
    .enforce_equal(dr, &outer_error.sponge_state)?;

Without this line, a prover could pick the state and with it the challenges:

Suppose a prover wants $\mu =9$, and it writes the state $(9,42,12)$ into outer_error. The second half alone would resume from this state and produce $\mu =9$ and ${\mu }^{\prime }=20$. Of the $79,507$ possible states, $1,849$ give the wanted $\mu$, but the first half compares the stage with the state it computed, and exactly $1$ state passes that comparison, the honest one. Both circuits read one committed stage polynomial, so the prover cannot show them different values.

5. Public inputs

Each circuit also has a public input polynomial $k(Y)$, and a parent has to compute $k(y)$ for each of a child's circuits. If every internal circuit exposed its own values, a parent would compute many different polynomials. The code avoids that with a unified instance, one structure of values that nearly all internal circuits expose in full, so that one computed $k(y)$ serves them all.

Sharing an instance raises the question of who checks each value, since a circuit that merely exposes a value proves nothing about it. The code assigns each slot to exactly one circuit, and the prover asserts that all were covered. Other circuits read a slot as a witness, and the shared $k(y)$ forces them to agree with the owner:

The rows add to $13$ points and $11$ elements, which is the code's $37$ wires.

Recursion uses three forms of $k(Y)$ over these values, plus a fourth with no wires of its own. All are Horner evaluations ending in the constant wire's 1:

$$k_{\text{unified}}(Y)=\text{Horner}(\text{unified}\Vert 0\Vert 1,Y),$$

$$k_{\text{bridge}}(Y)=\text{Horner}(\text{unified}\Vert \text{left}\Vert \text{right}\Vert 0\Vert 1,Y),$$

$$k_{\text{app}}(Y)=\text{Horner}(\text{left}\Vert \text{right}\Vert \text{output}\Vert 1,Y).$$

Here Horner over wires $w_0,\dots ,w_{m-1}$ and the final 1 means $(\cdots (w_{0}y+w_1)y+\cdots +w_{m-1})y+1$, so the last wire before the 1 is the coefficient of $Y$. The hashes_1 circuit uses $k_{\text{bridge}}$, because it exposes the child headers, and the application circuit exposes the same headers through $k_{\text{app}}$. Together those two claims stop a proof from using one pair of headers in the step and another in the recursion. An endoscaling step exposes nothing but the zero, so its polynomial is $k(Y)=1$.

Take a toy unified output of five wires, $(21,25,11,4,10)$, which are the first bridge point and the challenges $w$, $y$ and $z$ from the run above. Take child headers $(8,3)$ and $(12,3)$, whose second entry is the suffix, and the output header $(20,3)$. At $y=4$:

Horner's rule reaches $40$ after the five unified wires, and both $k_{\text{unified}}$ and $k_{\text{bridge}}$ continue from that value. Each table entry also matches a direct evaluation of the polynomial.

These values reach the fold through the parent. Its hashes_1 and collapse circuits compute each child's values from the preamble stage with gates, at the $y$ of the current fuse, and those values become the targets of the claims being folded.

6. Keeping internal and application circuits apart

The registry holds internal and application circuits side by side, and a proof names its application circuit by a domain point the prover selects. So a prover could try to name an internal circuit and claim its trace as an application step. To rule that out, the code makes the two kinds of $k(Y)$ unable to coincide. Each internal circuit ends its output with a zero, and each application header ends with a suffix that is never zero.

Let an internal circuit expose wires $(a,b)$ and its zero suffix, so that $k_{\text{int}}(Y)=a{Y}^3+b{Y}^2+1$, and let an application circuit expose a header $(d,s)$, so that $k_{\text{app}}(Y)=d{Y}^2+sY+1$. If an application could use the suffix $s=0$, then $43$ of the $79,507$ triples $(a,b,d)$ would make the two polynomials identical, and the swap would pass at every $y$. For $s=3,4,5$ the difference depends only on $a$ and $b-d$, so we tried all $1,849$ pairs of those, and none makes the polynomials identical. The two values then agree at no more than $2$ of the $42$ nonzero values of $y$, and on a real field the same count is a negligible fraction.

This also explains why an endoscaling step needs the zero although it exposes nothing. Its comments say that the suffix is what stops a step from satisfying an application instance, given that the application's circuit ID may name any native slot. The nested registry holds internal circuits only, so it omits the zero.

The value 2 has a job of its own, which chapter 10 described. Only the internal Bootstrap step declares the Dummy input, and only then does collapse waive its final comparison. The Rerandomize step has a witnessed suffix, so it constrains that wire away from 2.

7. What a proof carries to its parent

A parent does not repeat the checks in a child's circuits. It folds the child's claims into its own accumulators and reads the child's public data. Here is what it takes from a child:

Three accumulators therefore pass up the tree, namely $(A,B,c)$, $(P,u,v)$ and $m(W,x,y)$, one of each per side of the cycle. Each fuse replaces two of each with one, so a proof has the same shape at every depth. A child's internal circuits do not run again in the parent, and they cannot be skipped either, since their claims are among those folded.

The application's circuit sits in the registry like any other, and the base case runs through a single bootstrap proof. Chapter 10 records that the code has no Merkle root of initial states.

8. From a large proof to a short one

The accumulators stay few, but each one still holds polynomials of $2^{13}$ coefficients, and so does each stage and trace. A parent needs those polynomials to compute its fold. A verifier outside the tree does not want to receive them. The code's verify_uncompressed does hold every polynomial and checks the claims directly, and the code keeps it as a test oracle.

Compression replaces each polynomial with its commitment and a few of its values, and it restates the decider's checks so that those are enough. Chapter 09 ran this idea on one circuit. The book's compression chapter and the code arrange it in three reductions, which run once per curve:

The sections below run all three on the toy curve. We use the two circuits from the staging chapter, with $D=16$ and the sixteen generators listed there. We choose the challenges by hand. In the code a transcript under its own tag supplies them, after absorbing the instance and the output header, with fresh $w$, $y$, $z$ and $\sigma$ on each curve.

9. The instance and its claims

The instance has to tell the verifier everything it would otherwise read off the polynomials. For our two circuits that gives this:

These numbers carry over from earlier chapters. The accumulator pair stands in for what the last fuse left, and we took the squaring claim at $x=5$ for it. The polynomial $p$ behind $\bar{P}$ is chapter 06's example, with its opening point $9$. The real instance holds a commitment for each native and nested polynomial, which makes it the largest part of the proof.

The verifier now rebuilds the decider's revdot claims from what it holds, in the order of the code's claim list:

The first five claims have appeared in earlier chapters. The sixth exists because the decider also compares individual wires of certain stages against values it computes for itself, and a verifier that holds only a stage's commitment needs another way to make that comparison. The code turns it into a revdot claim. For wires at degrees $d_j$ with expected values $e_j$, it sets

$$E_{\sigma }=\sum _j{e}_j{X}^{d_j},M_{\sigma }=\sum _j{\sigma }^j{X}^{D-1-d_j},$$

and the revdot product picks out the differences at those wires:

$$⟨⟨\mathbf{q}-{\mathbf{E}}_{\sigma },{\mathbf{M}}_{\sigma }⟩⟩=\sum _j{\sigma }^j(q_{d_j}-e_j).$$

The target is 0, and it holds at a random $\sigma$ only if each wire holds its expected value. The real list has five such claims natively and three on the nested side. In our run a small stage $q(X)$ plays the role of the query stage:

The registry here has two circuits at $W=1$ and $W=-1$, whose wiring gives $m(1,9,7)=11$ and $m(-1,9,7)=12$. The stage $q(X)$ claims those values in the wires $a_1$ and $d_1$. With $\sigma =20$, the mask $M_{\sigma }$ has a $1$ opposite $a_1$ and a $20$ opposite $d_1$, and $E_{\sigma }$ holds the expected values at those two degrees. So the product is $(a_1-11)+20(d_1-12)=0$. If the stage holds a wrong $a_1$, the product is nonzero at all 43 values of $\sigma$. If both wires are wrong, the two errors cancel at one value of $\sigma$ out of 43.

A real compressed proof has $56$ native claims, namely one accumulator pair, one application circuit, $33$ internal circuits, $16$ masks and $5$ wire bindings, and it has $46$ nested claims. In groups of $7$, the native side has $8$ groups, $336$ first-layer terms and $56$ second-layer terms, and the nested side has $7$ groups, $264$ first-layer terms and $42$ second-layer terms.

10. Folding to three claims

Now the fold, in the form the code's compression uses. Chapter 14 noted that this differs from the fuse's quotient fold, and that the sources do not say why. Claim $i$ in group $g$ and slot $s$ takes the weights

$${\lambda }_i=({\mu }^{\prime }{)}^g{\mu }^s,{\eta }_i=({\nu }^{\prime }{)}^g{\nu }^s,$$

and the folded pair is $A={\sum }_i{\lambda }_i{a}_i$ and $B={\sum }_i{\eta }_i{b}_i$. To see the target, expand the revdot product and separate the terms with $i=j$:

$$⟨⟨\mathbf{A},\mathbf{B}⟩⟩=\sum _i{\lambda }_i{\eta }_i⟨⟨{\mathbf{a}}_i,{\mathbf{b}}_i⟩⟩+{\epsilon }_1+{\epsilon }_2.$$

The first sum holds the true targets $k_i$. The other two terms collect the products $e_{i,j}=⟨⟨{\mathbf{a}}_i,{\mathbf{b}}_j⟩⟩$ that the verifier cannot compute, with ${\epsilon }_1$ for pairs inside a group and ${\epsilon }_2$ for pairs across groups. The verifier does not need those products individually. The prover lays them out as low coefficients of a vector ${\mathbf{E}}_{\ell }$ for each layer, and the weights go in mirrored positions of a public vector ${\mathbf{W}}_{\ell }$, so that each ${\epsilon }_{\ell }$ is itself a revdot product, as chapter 14 showed. Our six claims fall into two groups of three, where the code uses seven per group:

With $\mu =19$, $\nu =38$, ${\mu }^{\prime }=2$ and ${\nu }^{\prime }=33$:

The vectors $\mathbf{A}$ and $\mathbf{B}$ have public parts that nobody needs to commit to, so the verifier separates what it derives from commitments and what it evaluates alone. A circuit claim's $b_i$ contains $a_i(zX)$, so the committed polynomial $T={\sum }_{\text{circuits}}{\eta }_i{a}_i$ takes care of that part at the dilated point $rz$:

$$A(X)=A_c(X)+A_{\text{pub}}(X),B(X)=B_c(X)+T(zX)+B_{\text{pub}}(X).$$

Here $B_{\text{pub}}$ holds the wiring restrictions, the $t(X,z)$ terms, the masks and $M_{\sigma }$, and $A_{\text{pub}}$ holds the expected values of the wire bindings. The commitments come from the instance:

The verifier obtains ${\bar{A}}_c=(11,30)$, $\bar{T}=(20,25)$ and ${\bar{B}}_c=(25,29)$ from small MSMs over the instance's points. Committing to the three polynomials directly gives the same points.

11. The split

We have three revdot claims, $(A,B,K)$, $(E_1,W_1,{\epsilon }_1)$ and $(E_2,W_2,{\epsilon }_2)$, and nothing has yet shown that any of them is true. The split from chapter 05 handles this. The prover combines the products with a challenge $\rho$,

$$t(X)=A(X)B(X)+\rho E_1(X)W_1(X)+{\rho }^2{E}_2(X)W_2(X),$$

and writes the result as $t(X)=X^{D-1}p(1/X)+X^{D}q(X)$. A revdot product is the coefficient of $X^{D-1}$ in the ordinary product, so that coefficient of $t$ is the combination of all three revdot products, and it lands in $p(0)$. This is the one place that pays for the product polynomial and its FFTs. The verifier then picks a point $r$ and checks the identity at it, and it sets aside its required value of $p(0)$ to be opened later:

At $\rho =41$ the prover commits to $\bar{p}=(23,7)$ and $\bar{q}=(30,8)$, and the required value is $p(0)=K+\rho {\epsilon }_1+{\rho }^2{\epsilon }_2=21$. At $r=18$, so that $rz=26$ and $1/r=12$, it sends seven values:

The verifier adds what it can compute alone. It needs $s_1(r,y)=39$, $s_2(r,y)=9$ and $t(r,z)=3$, the masks at $r$, which are $28$, $29$ and $5$, and the two public vectors, $W_1(r)=14$ and $W_2(r)=7$. That gives $A(r)=38+20=15$ and $B(r)=12+7+10=29$, modulo 43. The left side of the split is $A(r)B(r)+\rho E_1(r)W_1(r)+{\rho }^2{E}_2(r)W_2(r)=34$, and the right side is $r^{15}p(1/r)+r^{16}q(r)=34$.

The two sides agree, but all seven values are still only claims about commitments, which the next step settles.

12. Batching and the argument

The reduction leaves eight claims, seven from the values above and one for the required $p(0)$. The instance adds four of its own, which carry the fuse's accumulators into the check:

With only 43 points on the toy curve, some commitments repeat by chance, such as those of $T$ and $E_1$. The polynomials themselves differ.

The last four rows are what the decider still owes from the recursion. Claim 9 is the fuse's accumulated $(P,u,v)$, and claims 10 and 11 pin the values of the accumulator pair at that $u$. Claim 8 is the restriction check of chapter 15:

Claim 8 opens $m(W,9,7)$ at the fresh point $w=7$. The verifier computes the value $8$ for itself, by evaluating the wiring of both circuits and combining the results with Lagrange weights, and this is the step that reads the whole registry.

Chapter 08's batch turns all twelve into one. The prover commits to the quotient $f(X)={\sum }_j{\alpha }^{m-1-j}(h_{i_j}(X)-y_j)/(X-x_j)$ and sends each polynomial's value $z_i$ at a new point $u$. Then the verifier derives, with $n=11$ polynomials and $m=12$ claims,

$$\bar{H}={\beta }^n\cdot \bar{F}+\sum _{i=0}^{n-1}{\beta }^{n-1-i}\cdot {\bar{h}}_i,$$

$$v={\beta }^n\sum _{j=0}^{m-1}{\alpha }^{m-1-j}\frac{z_{i_j}-y_j}{u-x_j}+\sum _{i=0}^{n-1}{\beta }^{n-1-i}{z}_i.$$

Unlike the fuse's $\beta$, which has to be short so that a circuit can scale points with it, this $\beta$ is an ordinary squeezed element, since no circuit runs this verifier.

With $\alpha =17$ the quotient commits to $\bar{F}=(5,29)$. At $u=38$ the prover sends the eleven values $(18,5,35,18,1,12,36,14,5,22,35)$. The verifier derives $f(u)=30$ from those values and the claims. With $\beta =20$ this gives $\bar{H}=(28,10)$ and $v=14$, and the prover's polynomial $H$ agrees on both.

Now the inner product argument of chapter 07, in the code's form, proves $H(u)=v$:

The argument commits to the masking polynomial, $\bar{S}=(26,23)$, and takes $\xi =29$ and a multiplier $z=12$ on $U$. The statement becomes $\bar{H}-v\cdot G_0+\xi \cdot \bar{S}=(1,29)$. Then come ${\log }_{2}16=4$ rounds:

The final scalar is $\hat{a}=38$. The verifier computes $\hat{G}=(18,10)$ from an MSM over all sixteen generators and $\hat{b}=14$ from a product of four factors. The folded statement is $(22,7)$, and $\hat{a}\cdot (\hat{G}+\hat{b}z\cdot U)=(22,7)$, so the verifier accepts.

That finishes the run on this curve. In the code the same three reductions run again on the nested curve with its own claims, on one continuous transcript.

13. What the verifier pays

Chapter 09 named two linear costs, computing $s(x,y)$ and computing $\hat{G}$, and part three set out to remove them from the circuits. They have not disappeared. No circuit pays them, which is what recursion needed, and the wiring chapter deferred the last piece to this page. The verifier of a compressed proof pays them once, at the root:

The rows in bold are what remains of chapter 09's two costs. Wiring appears three times, because the compressed verifier evaluates each circuit claim's restriction at $(r,y)$, the whole registry over its domain and at further points to fill the wire bindings, and the registry at the fresh $(w,x,y)$. This last evaluation is the one chapter 15 described. It lets a whole tree of fuses rely on one restriction polynomial, since the verifier checks that polynomial against the full registry exactly once. Each of these passes grows with the wiring of the registered circuits, including the application's steps.

The last row is the deferred MSM of chapter 11. Compression computes it in full, with one per curve. None of these costs grows with the depth of the tree, so a proof that covers many leaves has the same verifier as a proof that covers two.

14. The size of the result

Counting from the code's wire format gives the following, for the standard profile at the production rank of 13 and headers of 4 elements, which is the size the code's benchmarks use:

At 32 bytes per point or scalar, with 4 bytes for the circuit index and the 28-byte envelope, that comes to $7,264$ bytes. The uncompressed encoding writes $8,192$ coefficients for each of $92$ polynomials, which is $24,117,248$ bytes before counting its cached points, so compression shrinks the proof by a factor of about $3,320$. Most of the compressed proof is the instance, with $93$ of its $157$ points. The IPA rounds, the only part that grows with the circuit size, take $52$ points.

The code's comment on profiles says "a few kilobytes", which agrees with this count.

A header larger than $4$ elements adds $64$ bytes per extra element, since the proof holds the two child headers. The output header does not count, because the verifier supplies it as the statement.

15. Why cheating fails

The chapters before this one each counted cheating at their own step. Here we look at what compression adds, which is the chance to hide a false claim in a value the verifier will never check directly. Start with a false public input:

Suppose the prover claims the output $11$ for the squaring circuit in place of $10$, so its target rises by $y=35$ while its vectors stay honest. At our challenges the folded pair then misses $K$ by $14$. Before the challenges, it can lower the term $e_{0,1}$, whose weight is $\nu$, by some amount $e$. The false target adds $35\mu \nu$ to $K$ and the lowered term removes $e\nu$, so the fold balances only if $\mu =e/35$. For $e=5$ that means $\mu =37$, and we confirmed the balance there on the full vectors. Over all $1,764$ nonzero pairs $(\mu ,\nu )$, every nonzero $e$ balances exactly $42$ pairs, which is one value of $\mu$ out of 42.

The value ${\epsilon }_1$ is a second place to try:

After seeing $\mu$ and $\nu$, the prover could raise ${\epsilon }_1$ alone and leave ${\mathbf{E}}_1$ as committed. That can make $(A,B)$ balance, but it makes the claim $(E_1,W_1,{\epsilon }_1)$ false by the same amount, and $\rho$ arrives only after ${\epsilon }_1$ is fixed. We tried all $42$ nonzero shifts against all $43$ values of $\rho$, and each shift passes at exactly $1$ value of $\rho$.

The prover could also try to change the required value of $p(0)$ directly:

Suppose the prover wants $p(0)$ to be too large by $7$. The coefficient of $X^{15}$ in $X^{15}p(1/X)+X^{16}q(X)$ is exactly $p(0)$, so whatever else it does, the difference from the true product is a nonzero polynomial of degree at most $30$. The prover can choose the other coefficients of $p$ and $q$ to give that difference as many roots as possible, and we built such a pair. It passes the split at $30$ of the $42$ nonzero values of $r$. This is the toy field's small size at work, since the same count on the real parameters is $2^{14}-2$ roots out of about $2^{254}$ values.

Once the split passes, every remaining claim is a statement about a commitment, and chapter 08 and chapter 07 already counted those. A prover cannot avoid the registry either, since the verifier computes both $m(w,x,y)$ and each $s_i(r,y)$ for itself. It cannot slip in a stray commitment, because every polynomial commitment the verifier reads gets opened through the IPA. The code's one exception is the nested challenge stage's partial commitment, which commits to no polynomial, and the bind_challenges claims hold it in place.

The argument above is informal, and it rests on these assumptions. Nobody knows a relation among the generators on either curve, so commitments bind. The two transcripts behave as random oracles, and each challenge comes after the commitments and values it tests. A false proof about a tree also has to get past the accumulation arguments of the earlier chapters. The book reports Lean proofs for some gadget contracts and says that these do not cover the protocol's overall soundness, which we do not establish here either.

16. Rerandomization and zero knowledge

A wallet would like two things from a proof beyond soundness. The proof should hide its witness, and when it reaches someone else it should not link back to the proof that produced it. As chapter 02 recorded, neither the Ragu Book nor the code at this commit establishes either property.

The code has an operation aimed at the second, rerandomize. It fuses the input proof as the left child with a cached proof of the unit header as the right child, under an internal step whose output header uses the same wires as the left input, so it cannot change the header. The result verifies as the input did. Both the book and the code say that unlinkability is the intention, and the comment on that function says that it is not achieved today. One of its reasons is that the fold is deterministic:

Reduce the fold to one commitment and let the output be ${\bar{A}}_{\text{out}}={\lambda }_0{\bar{A}}_{\text{in}}+{\lambda }_1{\bar{A}}_{\text{seed}}$, with the public weights ${\lambda }_0=16$ and ${\lambda }_1=22$ and the cached seeded point $(1,29)$. An input of $(25,29)$ gives the output $(24,30)$. An observer who wonders which proof went in can test each candidate against that equation. We tried all $42$ points as candidates, and only the true input matches.

The comment's other reason is more direct, because the output holds the input's commitments and stage polynomials in the clear as left-child data. It lists the remaining work as a randomizer in the fold and a way of hiding the child data.

Hiding the witness has a similar status. The stages' random $\alpha$ is there to prevent cancellation and not for hiding, the IPA is unblinded at this commit, and the code says that a compressed proof is not hiding, because its openings are evaluations of the witness polynomials. To see what one evaluation can tell an observer:

Take the stage $a(X)$ from chapter 17, where $v=x^2$ and one random entry $\alpha$ sits at $a_0$. Among all $1,849$ pairs $(x,\alpha )$, the commitment $(22,24)$ matches $43$. Adding one value at a point, $a(17)=3$, leaves $2$ pairs, the true $(3,10)$ and also $(24,42)$, because the commitment and the value together give a quadratic equation in $x$. On a real curve nobody can list the commitment's matches, but the value still gives one linear equation in the secret wires, which is the sense in which the proof does not hide them.

This small case shows the effect of one value on one stage. A compressed proof opens combinations of polynomials at points the transcript chooses, so the leak there has a different shape, and we have not analyzed how much it reveals in practice. An uncompressed proof holds the polynomials themselves. The Tachyon book's description of stamps assumes zero knowledge, so this is an open requirement for Tachyon and not a settled property, as chapter 02 noted.

17. Performance against Orchard

The sizes above give a first comparison, which we can make from public formulas:

ZIP 225 gives an Orchard proof $2720+2272\cdot n$ bytes for $n$ actions, which is $7,264$ bytes at $n=2$ and $25,440$ bytes at $n=10$. So by our count a compressed Ragu proof with headers of $4$ elements is about the size of an Orchard proof for two actions, and one Ragu proof can stand for many transactions. The exact match at $n=2$ is a coincidence of these parameters.

For verification time, the book's analysis chapter gives a rough model, and it states that the figures need checking against benchmarks. It puts Orchard's batch verification at about 10 to 15 ms per proof on one thread, scaling as roughly $N_{\text{tx}}/\log N_{\text{tx}}$. It estimates a Ragu proof at about 100 ms at $K=11$, driven mainly by an MSM of $2^{13}$ points. Setting the two equal gives the crossover, with $c$ the cost per proof:

$$\frac{N_{\text{tx}}\times c}{\log N_{\text{tx}}}\approx 100\text{ ms}.$$

The book reports about 50 transactions with $c=10$ ms, and it does not state the base of the logarithm. We solved the equation at both ends of its range and for the two natural bases:

The book's figure sits inside the range the model allows, and the range is wide, as one would expect of a rough estimate. The shape of the curves is the more reliable conclusion. Batch verification of independent proofs keeps growing with the number of transactions, and verifying one aggregated proof does not.

The parameter $K$ gives a trade-off that the book leaves open. A larger circuit limit raises the verifier's cost for every proof and allows a shallower tree, and a smaller limit does the reverse.

These figures describe verification only. They leave out the prover's costs, which the sources do not quantify, and they compare with Orchard as it runs today, whereas Tachyon changes what a transaction carries. Tachyon has not activated on mainnet, its design is still changing, and it pins a different Ragu revision from the one this chapter reads.

18. Fusing after compression

One part of this design is still moving, and later chapters depend on it. Chapter 02 recorded that the Ragu Book calls a compressed proof terminal, while the code's profile comments foresee an Aggregator profile that verifies a compressed proof in circuit, with an internal Decompress step that outputs its header. The code says this has not landed, and a test pins the aggregator's shape to the standard one until it does. Such a circuit would have to run the verifier of Section 13 with gates, which is why the design places it in extra circuits that only aggregators carry. The chapter on aggregation returns to this.

19. Where this chapter leaves us

This chapter took the following steps:

1. A fuse runs one transcript through eleven phases, each commitment coming before the challenge that tests it, and it divides the checks among many small circuits because each has at most $2^{11}$ gates.
2. The replay takes more gates than one circuit holds, so hashes_1 and hashes_2 share it, with the sponge state held in the outer error stage and checked by the first circuit.
3. The internal circuits expose one unified instance, with each slot owned by one circuit, so one $k(y)$ serves them.
4. Internal outputs end in zero and application headers end in a nonzero suffix, so the coefficient of $Y$ keeps the two kinds of circuit apart.
5. A parent folds three accumulators per side from each child, namely $(A,B,c)$, $(P,u,v)$ and $m(W,x,y)$, so a proof keeps its shape at every depth.
6. Compression replaces polynomials with commitments and values, through three reductions on each curve, from revdot claims to openings, from openings to one claim, and from that claim to an IPA.
7. A wire binding turns the decider's comparisons of stage wires into revdot claims that a verifier can check from commitments.
8. The compressed verifier pays the deferred linear costs once, as registry evaluations and one MSM per curve, and those costs do not depend on the tree.

9. By our count a compressed proof takes $7,264$ bytes, against more than $24,117,248$ uncompressed. Rerandomization and hiding are not yet established, and the comparison with Orchard remains an estimate.

That completes Ragu as a proof system. The next part turns to what Tachyon proves with it, starting with notes, nullifiers, and tachygrams.