Wiring and the Registry

Chapter 09 ended with two linear steps in the verifier. Accumulation dealt with the first, computing $\hat{G}$. This chapter deals with the second, computing $s(x,y)$, which requires reading the whole circuit. It also takes up a related problem that has waited since chapter 02, which is how different nodes of a PCD tree can run different circuits.

Both problems have the same answer. The prover commits to pieces of the wiring polynomial, a cheap random check ties each new piece to the old ones, and a single expensive check at the very end covers the whole history. The Ragu Book calls this idea post-processing, and credits it to Halo. We start with one circuit, then extend the method to a polynomial that holds many circuits, called the registry polynomial.

1. What the verifier still computes

Recall the check that ties the right factor to the trace in chapter 09,

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

The value $t(x,z)$ has a short closed form, while the value $s(x,y)$ has none, because the wiring comes from an arbitrary circuit:

Our circuit has 8 nonzero wiring coefficients, so computing $s(9,7)=23$ takes 8 terms. A real circuit has at least one coefficient for each wire it uses, so at $4n=2^{13}$ a full circuit needs on the order of 8,192 terms for this one value.

A recursive verifier would have to do this inside a circuit, so the circuit would have to contain a description of itself and grow with every wire it adds, as chapter 10 found. Chapter 11 escaped the same problem for $\hat{G}$ by testing a claim at a random point, which worked because $g_{\mathbf{u}}$ has a short product form. The wiring polynomial has no such form.

A natural next idea is to let the prover supply a commitment $S$ to $s(X,y)$ and to carry the claim forward in the accumulator, as split accumulation does for evaluation claims. That chapter showed that folding establishes what $S$ opens to. It says nothing about whether $S$ commits to the right polynomial, and this gap is exploitable:

Take the false trace with $x=4$, ${\mathbf{r}}^{\prime }=(16,21,16,4,4,4,0,0)$, at $z=5$ and $y=7$. With the true wiring the revdot product is 18, and the target is $k(7)=13$. The prover adds $31X^4$ to its wiring polynomial, which moves the revdot product by $r_3^{\prime }\cdot 31=38$ and reaches the target. It commits to the altered polynomial $(0,0,6,42,25,7,42,36)$, which gives $S^{\ast }=(17,7)$ in place of the true $(7,6)$. The right factor is built from this polynomial, so the check $b(x)=a(xz)+s(x,y)+t(x,z)$ holds at all 43 values of $x$, and every evaluation claim is true of the committed polynomials. The only thing wrong with this proof is that $S^{\ast }$ does not commit to $s(X,7)$.

So the claim $S=\mathrm{com}(s(X,y))$ has to be checked somehow, and we want the check to cost far less than computing $s(X,y)$. Polynomial identity tests are the usual tool for this, but a test needs a polynomial on the other side to compare with, and the verifier does not want to compute any of them. The next section finds that second polynomial inside $s$ itself.

2. Restricting a polynomial of two variables

The wiring polynomial $s(X,Y)$ has two variables. Its coefficients form a table, with one row for each constraint and one column for each position in the trace. Here is the table for our circuit, with empty cells for zeros:

We can fix either variable. Fixing $Y$ gives a polynomial in $X$, and fixing $X$ gives a polynomial in $Y$. Each of these is called a restriction. Both directions take the same table and add it up along different lines, so the two restrictions agree where they cross:

$$s(X,y){|}_{X=x}=s(x,y)=s(x,Y){|}_{Y=y}.$$

Fixing $Y=7$ collapses the rows into $s(X,7)$, with coefficients $(0,0,6,42,37,7,42,36)$. Fixing $X=9$ collapses the columns into $s(9,Y)$, with coefficients $(27,17,13,29,0,0,0,0)$ on $Y^0,\dots ,Y^7$. These are different polynomials, and they meet at one number, since evaluating the first at $X=9$ and the second at $Y=7$ both give $23$.

This crossing is what the protocol uses. A commitment to a restriction in $X$ and a commitment to a restriction in $Y$ make two evaluation claims that must have the same value, and chapter 08 already knows how to check evaluation claims cheaply. The verifier needs no knowledge of the table to compare the two claims.

Restricting in $Y$ only makes sense if the result fits the commitment scheme, and this explains a limit we met earlier. The commitment has $4n$ generators, so $s(x,Y)$ must have degree below $4n$ in $Y$. The book gives this as the reason for the bound of $4n$ constraint rows.

3. Consistency for one circuit

Suppose a node has two children, and each child's accumulator holds a claim of the form $(S_i,y_i)$, meaning that $S_i$ commits to $s(X,y_i)$. The node wants to replace the two claims with one claim of the same form. We want three things from the replacement. It should tie each old $S_i$ to the true circuit, it should create a new claim at a fresh point, and it should leave no work that depends on the size of the circuit.

The book's protocol achieves this with a single restriction in $Y$ that crosses all three restrictions in $X$:

1. Both parties hold the old claims $(S_0,y_0)$ and $(S_1,y_1)$.
2. The verifier sends a random $x$.
3. The prover sends $S^{\prime }$, a commitment to $s(x,Y)$.
4. The verifier sends a random $y_{\text{new}}$.
5. The prover sends $S_{\text{new}}$, a commitment to $s(X,y_{\text{new}})$.
6. Both parties add six evaluation claims to the batch of chapter 08.

Each pair of claims says that a restriction in $X$ and the restriction in $Y$ agree at their crossing. The first two pairs concern the old claims, and the last concerns the new one:

$$S_0(x)=S^{\prime }(y_0),S_1(x)=S^{\prime }(y_1),S_{\text{new}}(x)=S^{\prime }(y_{\text{new}}).$$

Here we write $S(x)$ for the value at $x$ of the polynomial behind a commitment $S$, as the book does. We now run this on our circuit, using two accumulators with values we have already met. The first holds chapter 09's $y$, and the second holds the $y$ of chapter 12's second proof:

The prover states one value for each pair, which gives six claims about four polynomials:

The verifier never computes these values. It treats them as claims that share polynomials and places them in the batch, so one number in each pair appears twice:

With $\alpha =11$, $u=17$ and $\beta =15$, the prover sends $F=(9,9)$ and the values at $u$, one for each of the four polynomials: $35,31,33,4$. The verifier derives $f(17)=4$, then $P=(11,30)$ and $v=9$. A decider holding $\mathbf{p}=(35,38,42,37,30,17,37,17)$ commits to it and evaluates it, and both results match. Checking the crossing identity at all 1849 pairs $(x,y)$ confirms that an honest prover passes at every challenge.

A batched check tells us that the claims are true of the committed polynomials, and it says nothing about the circuit. Something still has to connect the last commitment to the real wiring. That job falls to the end of the chain, in the same way that a single MSM ended chapter 11's chain:

The accumulator that leaves this fold is $(S_{\text{new}},y_{\text{new}})=((20,6),12)$. If the chain stops here, the decider computes $s(X,12)$ from the circuit, which takes 8 terms, commits to it and gets $(20,6)$. That one linear computation stands in for computing $s$ at each of the three points.

4. Why a false accumulator fails

The argument runs backward from the decider. Suppose the decider has confirmed that $S_{\text{new}}$ commits to $s(X,y_{\text{new}})$. Then the third pair of claims fixes $S^{\prime }(y_{\text{new}})$ to the correct value, and the prover committed to $S^{\prime }$ before it saw $y_{\text{new}}$. Two different polynomials of degree below $4n$ agree at no more than $4n-1$ points, so $S^{\prime }$ is $s(x,Y)$, except with probability about $4n/|\mathbb{F}|$. That makes $S^{\prime }(y_0)$ correct, so the first pair fixes $S_0(x)$ to the correct value, and the prover fixed $S_0$ before it saw $x$. The same reasoning then shows that $S_0$ commits to $s(X,y_0)$.

We can follow this in the toy run by giving the prover a false $S_0$ and counting what it can do at each step. Say it holds an $S_0$ built for the attack of Section 1. The first check it faces is the pair at $x$:

The most favourable false polynomial differs from $s(X,7)$ by a multiple of $(X-1)(X-2)\cdots (X-7)$, the difference that chapter 09 found best for its cheater. Against an honest $S^{\prime }$, the pair of claims about $s(x,7)$ can hold only where this difference vanishes. Trying all 43 values of $x$ finds 7 that pass, $x\in \{1,\dots ,7\}$. No polynomial with 8 coefficients has more roots.

Outside those values the prover must lie in $S^{\prime }$ to keep the pair true, which moves the error one step along:

At $x=21$ the false $S_0$ opens to $15$, while the true $s(21,7)$ is $35$. The prover can absorb this error $23$ by committing to $s(21,Y)+D(Y)$ with $D(7)=23$ and $D(34)=0$, so that both old pairs now hold. The polynomial $D$ can have at most 7 roots, and one of them has to be $34$. Taking the other six at $1,\dots ,6$, we tried all 43 values of $y_{\text{new}}$ against an honest $S_{\text{new}}$, and 7 pass.

Outside those values the error moves once more:

At $y_{\text{new}}=12$ the difference is $D(12)=20$, so the prover has one option left. It commits to $s(X,12)+20$, which opens at $x=21$ to the value that $S^{\prime }$ now requires. All six claims are true of the committed polynomials, and the batched check of the previous section accepts. The prover has moved its error into the new accumulator, whose commitment is $(5,29)$. The decider computes $s(X,12)$ itself, gets $(20,6)$, and rejects.

So a false accumulator does not disappear. At each step it either hits a rare root or it passes its error into a new commitment, and the decider exposes the last one. A chain that never runs the decider has established nothing about its wiring, in the same way as chapter 12's evaluation claims.

All of this depends on the order of the messages. If the prover knows $x$ before fixing $S_0$, then the pair at $x$ tests nothing:

Suppose the prover knows $x=21$ before it fixes the old accumulator. The difference $(X-21)X^3$, scaled by $35$, vanishes at that point and gives the revdot shift of Section 1, so the false polynomial $(0,0,6,38,29,7,42,36)$ passes with an honest $S^{\prime }$ and an honest $S_{\text{new}}$, and the decider accepts the accumulator that leaves the fold.

This is why the old commitments have to enter the transcript before $x$ is squeezed.

5. A polynomial for many circuits

The protocol above assumes that every accumulator refers to the same $s(X,Y)$. Now suppose a tree has two kinds of step. We will use the running circuit as circuit A, along with a second circuit B that has the same number of gates and proves a different statement:

The two accumulators may now refer to different circuits, and the bridge of Section 3 stops working, since a single $S^{\prime }$ cannot be a restriction of both:

Let the first accumulator hold circuit A at $y_0=7$ and the second hold circuit B at $y_1=34$, so that $S_1=(9,22)$. If $S^{\prime }$ commits to $s_A(21,Y)$, the first pair of claims holds, and the second compares $s_B(21,34)=24$ with $s_A(21,34)=6$. Over all 43 values of $x$ these agree only at $x=0$, so an honest prover with two different circuits fails almost everywhere.

We could avoid this by merging A and B into one large circuit with a selector, as chapter 04 did for a branch. Then every step would pay for the gates of all its branches, which is the cost chapter 02 wanted to avoid. A better way is to keep the circuits apart and to put the choice of circuit into the polynomial itself, as one more variable.

Pick a set of points ${\omega }^0,\dots ,{\omega }^{2^k-1}$, one for each circuit, where $\omega$ is a root of unity of order $2^k$. Let ${\ell }_i(W)$ be the Lagrange polynomial that equals 1 at ${\omega }^i$ and 0 at the other points, as in chapter 05. The registry polynomial is

$$m(W,X,Y)=\sum _{i=0}^{2^k-1}{\ell }_i(W)s_i(X,Y).$$

Setting $W={\omega }^i$ makes every term vanish except one, so $m({\omega }^i,X,Y)=s_i(X,Y)$. The field needs enough roots of unity for this. The toy field ${\mathbb{F}}_{43}$ has $42=2\cdot 21$ nonzero elements, so its only roots of unity of 2-power order are $1$ and $-1=42$, and our registry holds exactly two circuits. With two points, the Lagrange polynomials are ${\ell }_0(W)=(1+W)/2$ and ${\ell }_1(W)=(1-W)/2$:

The script compares $m(1,x,y)$ with $s_A(x,y)$ and $m(42,x,y)$ with $s_B(x,y)$ at all 1849 pairs, and they agree at every pair. Since ${\ell }_0+{\ell }_1=1$ at every $W$, the two weights at $W=14$ also add up to 1, and we return to this fact in Section 10.

The last row of that table shows what $W$ does away from the domain. It gives a blend of the circuits that belongs to no single one, and the protocol uses this blend as a random fingerprint of the whole set.

An accumulator now has to carry a claim that does not name one circuit, so that accumulators from different circuits can merge. The form the book chooses leaves $W$ free. The claim is $(S,x,y)$, meaning that $S$ commits to $m(W,x,y)$, the polynomial in $W$ that holds every circuit's value at the point $(x,y)$. Section 7 shows why this form is also the one we want for reading a single circuit's value. Since this polynomial is committed with the same generators, it needs degree below $4n$ in $W$, and the code enforces that a registry has at most $4n$ entries.

6. Consistency for the registry

Two old claims $(S_0,x_0,y_0)$ and $(S_1,x_1,y_1)$ now differ in two coordinates, while the claims in Section 3 differed in only one. A single bridge cannot cross both, so we change one variable at a time. The book's protocol freezes $W$ at a random point, moves $Y$ to a common value, moves $X$ to a common value, and then lets $W$ go free again. Here are its steps:

1. Both parties hold the old claims.
2. The verifier sends a random $w$.
3. The prover sends $S_0^{\prime }$ and $S_1^{\prime }$, commitments to $m(w,x_0,Y)$ and $m(w,x_1,Y)$.
4. The verifier sends a random $y$.
5. The prover sends $S^{\prime \prime }$, a commitment to $m(w,X,y)$.
6. The verifier sends a random $x$.
7. The prover sends $S_{\text{new}}$, a commitment to $m(W,x,y)$.
8. Both parties add ten evaluation claims to the batch.

Each arrow in the figure stands for a crossing of two restrictions, and each crossing gives a pair of claims:

$$\begin{array}{rl}{S}_0(w)& =m(w,x_0,y_0)=S_0^{\prime }(y_0),\\ S_1(w)& =m(w,x_1,y_1)=S_1^{\prime }(y_1),\\ S_0^{\prime }(y)& =m(w,x_0,y)=S^{\prime \prime }(x_0),\\ S_1^{\prime }(y)& =m(w,x_1,y)=S^{\prime \prime }(x_1),\\ S^{\prime \prime }(x)& =m(w,x,y)=S_{\text{new}}(w).\end{array}$$

Two bridges are needed in step 3 because the children have different $x_i$. Only one is needed in step 5, because at that point both children have the same $y$, and both restrictions in $Y$ land on the same polynomial in $X$.

For the toy run, let the left child have used circuit A at chapter 09's challenges, and the right child circuit B at the $x$ and $y$ of chapter 12's second proof:

Notice that the commitment to $m(W,x,y)$ uses only the first two generators, because on this domain it has degree 1 in $W$. The five crossings give the following values:

The script repeats these comparisons at all 79,507 triples $(w,x,y)$, and an honest prover passes every one.

The accumulator that leaves the fold is $(S_{\text{new}},x,y)$, and it has the same form as the two that entered, so the next node can repeat the walk.

7. Selecting a circuit

The walk keeps the accumulators consistent with $m$, but the point of all this was to obtain the value $s_i(x,y)$ for the check in Section 1, for whichever circuit a child used. The new accumulator provides that value directly. Since $S_{\text{new}}$ commits to $m(W,x,y)$, opening it at the domain point of circuit $i$ gives

$$S_{\text{new}}({\omega }^i)=m({\omega }^i,x,y)=s_i(x,y).$$

This is why the accumulator leaves $W$ free. Each circuit's value is one evaluation claim on the same commitment, and the prover names the circuit by naming the point. The check from Section 1 then reads a claimed value that the batch will test, in place of a value the circuit would have to compute.

The new accumulator is $m(W,21,12)=31+14W$. Take $z=16$, so that $xz=35$. For each child the circuit reads the wiring value by opening $S_{\text{new}}$ at the child's domain point, and it adds the trace value and the gate value:

The script also confirms that each child's revdot product at $z=16$ and $y=12$ equals its own $k(y)$, with different wiring and different public inputs on the two sides.

The two children here used different wiring and the same step of the protocol handled both. Only the evaluation point changed. These two openings bring the list to twelve claims, on six polynomials:

With $\alpha =11$, $u=17$ and $\beta =23$, the prover sends $F=(28,21)$ and six values at $u$: $7,29,11,20,15,11$. The verifier derives $f(17)=21$, then $P=(22,7)$ and $v=22$, and a decider holding $\mathbf{p}=(19,41,39,5,8,29,9,10)$ accepts. The wiring decider then evaluates the accumulator at a fresh point. At $W=30$ the polynomial gives $21$, and the two circuits give ${\ell }_0(30)s_A(21,12)+{\ell }_1(30)s_B(21,12)=21$.

The last sentence of that run is the registry's form of the decider, and we describe its cost next.

8. What the registry costs

The cost divides among three parties. The recursive circuit handles claims only, whatever the size of the registry or of the circuits. It does a little field arithmetic per claim, as in chapter 12, and the six commitments join that chapter's list. It also checks that each child's circuit point lies in the domain, which takes $k$ squarings per child, as Section 10 explains. Here is a comparison for a hypothetical tree with 256 application circuits of $2^{11}$ gates each, which is the gate limit chapter 10 recorded:

The prover pays more than this table suggests. Each of the four new polynomials is a Lagrange-weighted sum over the circuits, so computing one touches every registered circuit, including those the step did not use. The book describes a floor planner and memoization that let circuits with common routines share this work, which is one source of the "diminishing overhead" it claims. We have not measured these costs.

The decider pays too. To test $S_{\text{new}}$ it computes $m(w,x,y)$ at a fresh $w$, which means one $s_i(x,y)$ for each circuit. That is a linear cost in the total size of the registry, and the compressed verifier evaluates $m$ at several points of the walk, but all of this happens once for a whole history.

Adding a circuit therefore leaves the recursive circuit almost unchanged, so the book encourages applications to split work into many small circuits that communicate along the PCD tree, and it speaks of hundreds or thousands of circuits. Tachyon, which has not activated on mainnet and whose design is still changing, has a few dozen steps at the revision we read, and those steps run against a mock of Ragu.

9. Assigning domain points

The formula in Section 5 gives circuit $i$ the point ${\omega }^i$, but $\omega$ depends on $k$, and $k$ depends on how many circuits there are. If a registry grows from four circuits to five, it moves from a domain of 4 points to one of 8, and then $\omega$ changes and so does the point of every circuit except the first. Circuit code that refers to another circuit's point would then need to know the final count. The toy field has no room to show this, so we use ${\mathbb{F}}_{97}$ in this section, for arithmetic only. Its multiplicative group has order $96=2^5\cdot 3$, so it has a root of unity ${\omega }_5$ of order $2^5$. Write ${\omega }_k$ for the element of order $2^k$, with ${\omega }_k={\omega }_5^{2^{5-k}}$.

The first two columns differ at every circuit except the first, and the 8-point column gives circuit 2 the value that the 4-point column gave circuit 1. To avoid this, we take one maximal domain, of order $2^S$ where $2^S$ is the largest power of 2 dividing the group order, and assign each circuit a point there. Circuit $j$ gets ${\omega }_S^i$, where $i$ is $j$ with its $S$ bits reversed. The book calls this rolling domain extension, and the third column above uses it.

Reversing the bits puts the low bits of $j$ at the top of the exponent, so small values of $j$ give exponents that are multiples of a large power of 2:

The last column shows why this works. The first $2^k$ circuits always land on elements of order at most $2^k$, which are exactly the $2^k$-th roots of unity. They fill the small domain first, and growing the registry adds new points without moving old ones. The element also stays the same when written in the smaller domain, since ${\omega }_S^{\text{rev}(j,S)}={\omega }_k^{\text{rev}(j,k)}$ for $j<2^k$, which the script checks at every size. So a circuit can compute its own point, or another circuit's, from its index alone. The code's omega_j does this, and a test asserts the orders 1, 2, 4, 4, 8, 8, 8, 8 that the table shows.

On ${\mathbb{F}}_{43}$ the largest available 2-power order is 2, so $S=1$. Circuit 0 gets ${\omega }_1^0=1$, and circuit 1 gets ${\omega }_1^1=42$, which are the two points our registry has used all along.

The degree of $m$ in $W$ still depends on $k$, because the Lagrange polynomials change with the domain. What stays fixed is the element that names each circuit.

10. What the prover may select

The prover chooses the point at which $S_{\text{new}}$ opens for each child, and a verifier should worry about a free choice like this. We go through the three things the prover might choose.

A point outside the domain

The fact from Section 5 that the Lagrange weights add up to 1 now causes trouble. A point outside the domain gives a blend of circuits with $s(X,0)=1$, and that blend behaves as a third circuit that nobody registered. We need the constant wire of chapter 09 to show this, so this section uses circuits of 3 gates, with $k_0=1$ and $s(X,0)=1$:

Take the instance $k(Y)=1+35Y$, whose second coefficient is the public output, and let the prover select the out-of-domain point $w=4$. There the weights are $24$ and $20$, and they add up to 1, so $m(4,X,0)=1$ and the mixture looks like a circuit. The input $x=7$ does not satisfy $x^3+x+5=35$, yet the trace with $b_2=30$, which is $(0,6,8,6,7,11,0,7,30,0,0,1)$, satisfies the consolidated equation at all 1849 pairs $(z,y)$. The same trace passes against circuit A at 43 pairs and against circuit B at 43. The domain check catches the selection, because $4^2=16$, which is not 1.

So the protocol has to check the point. A value is in the domain exactly when squaring it $k$ times gives 1, and the hashes_1 circuit enforces this on both children's points. The uncompressed and compressed verifiers make the same check on the root's point.

A domain point with no circuit

The domain usually has more points than circuits, because $2^k$ is the next power of two. The registry also holds bonding polynomials, which chapter 17 uses for its stage checks, and which enforce the relation $⟨⟨\mathbf{r},\mathbf{s}⟩⟩=0$ on a partial trace. A prover might select one of these in place of a circuit.

The book treats every domain point as a wiring polynomial. An unassigned point holds the zero polynomial, and it counts as a bonding polynomial. The two kinds differ in one coefficient. A circuit has the constraint $d_0=k_0$ at $Y^0$, so $s(X,0)=1$, while a bonding polynomial leaves that constraint out, so $s(X,0)=0$. Here is a registry with three entries on a domain of 4 points in ${\mathbb{F}}_{97}$:

The verifier always sets $k_0=1$ when it expects a circuit, and this rules out the second kind. To see this, read the consolidated equation at $y=0$, as a statement about the coefficient of $Y^0$. A bonding polynomial contributes nothing to that coefficient, so the only terms left on the left side are the gate terms from chapter 04,

$$\sum _{i=0}^{n-1}(a_i{b}_i-c_i)(z^{2n-1-i}+z^{2n+i})+\sum _{i=0}^{n-1}{c}_i{d}_i(z^i+z^{4n-1-i}),$$

and these would have to equal 1 for every $z$. Only the term with $i=0$ in the second sum contains $z^0$, and it brings $z^{4n-1}$ with it, so a constant 1 cannot be formed.

Take the trace with $x=3$ and the instance $k(Y)=1+35Y$, and let the prover select the zero polynomial. Its gates hold, so the left side is 0, and the equation becomes $0=1+35y$, which holds for one value of $y$. Over all 1849 pairs it passes at 43. A prover can try to manufacture the missing 1 from the $c_0{d}_0$ terms by setting $c_0=d_0=1$, with an instance that has no public outputs. Then the left side is $1+z^{11}$, because the term at $z^0$ always comes with a partner at $z^{4n-1}$. It equals 1 only at $z=0$, which is 43 of the 1849 pairs.

A different registered circuit

The two checks above leave the prover a free choice among registered circuits. That choice is safe only if the statement says which circuit it expects, and a public input with the same shape can otherwise be proved by the wrong circuit:

Suppose the verifier wants a proof that some $x$ satisfies $x^4+2=35$. Trying all 43 values shows that no such $x$ exists, so this statement is false. The verifier computes $k(Y)=1+35Y$, and the prover selects circuit A in place of circuit B, with $x=3$. Every check passes at all 1849 pairs, because the instance is the same as that of the true statement $3^3+3+5=35$. Now add a row to each circuit that sets the linear coefficient of $k(Y)$ to a value fixed for that circuit, 2 for A and 3 for B, and let the verifier compute $k(Y)=1+3Y+35Y^2$. Circuit B with a true output, such as $x=3$ and the output 40, still passes everywhere. The same substitution with circuit A now passes at 43 of the 1849 pairs, all of them at $y=0$.

The extra row plays the part of the header suffix from chapter 02. The book's substitution section says that an application circuit's suffix fills the linear coefficient of $k(Y)$, and that application suffixes are nonzero. Internal circuits output suffix zero, so they cannot pass as application circuits. The code applies this to every internal circuit slot. In the code a suffix belongs to a header type and not to one circuit, so unlike our toy row it leaves steps with the same output header interchangeable.

11. Post-processing and the registry tag

We can now say what is unusual about this design. Many recursive systems preprocess each circuit into a verification key, a short commitment to the circuit's polynomials, and the verifier reads this key. With many circuits, a recursive verifier would have to handle a table of keys. Ragu has no such keys, as its book states. A verifier holds the registries themselves, built from the circuit definitions, and a prover computes the restrictions it needs at each step. That is the sense in which the work moves from before the proof to after it.

Without keys, one question remains, which is how the transcript comes to depend on the circuits. Fiat–Shamir requires the statement to enter the transcript before any challenge, and the circuits are part of the statement. Here is what goes wrong otherwise:

Fix the false trace $(16,21,16,4,4,4,0,0)$ and suppose the transcript has produced $z=5$ and $y=7$ from data that does not depend on the circuit. At these values the trace misses its target, because constraint 3 is off by $38$. An author who has seen $y$ can now publish a slightly different circuit, whose constraint 0 reads $(1+31)a_0-b_0=0$. This constraint fails on the trace by $31\cdot 4=38$, and with its weight $y^0$ that exactly cancels the error of constraint 3 with its weight $y^3=42$. Two constraints are broken, and the equation holds at $y=7$. Counting over all 1849 pairs, it holds at 129, namely those with $y\in \{7,37,42\}$, so the verifier was misled only because the circuit came after the challenge.

The usual fix is to hash the circuits into the first transcript state. That does not work directly here, for a reason the code documents. The registry contains the recursive verifier's own circuits, and those circuits replay the transcript, so a transcript that starts from a digest of the registry would need that digest inside the circuits that it summarizes. Keyed systems avoid the cycle because they generate the key beforehand and carry it in public inputs.

Ragu breaks the cycle with a registry tag, a field element $\kappa$ added to the polynomial at the one slot that no circuit uses:

$$m(W,X,Y)\to m(W,X,Y)+\kappa (XY{)}^{4n-1}.$$

We should first check that this cannot break an honest proof. Read as a constraint, the term is at row $Y^{4n-1}$, and at $X^{4n-1}$ its partner in the revdot product is position 0 of the trace, the wire $c_0$. So it adds the constraint $\kappa c_0=0$, which holds for every $\kappa$, because the system gate has $c_0=0$. The code reserves that row by refusing a circuit that would reach it. The term has no factor of $W$, so it appears at every domain point, and it vanishes at $Y=0$, so it does not disturb the distinction of Section 10.

Take $\kappa =19$. On the trace of chapter 09's constant-wire circuit, $\mathbf{r}=(0,9,27,9,3,11,0,3,3,0,0,1)$, the wire $c_0$ is 0, and the tagged wiring polynomial $s(X,Y)+19(XY{)}^{11}$ still satisfies the consolidated equation at all 1849 pairs. The tag cannot be added to our earlier two-gate circuit, whose $c_0=9$. There the term contributes $9\cdot 19\cdot y^7$, and the honest trace passes at only 43 pairs, those with $y=0$. The tag reaches every commitment a fold makes to a restriction. For $x=21$ the commitment to $s_{\kappa }(21,Y)$ is $(11,1)$, and going through all 43 values of $\kappa$ gives 43 different points. So a transcript that absorbs this commitment gives challenges that the author of the circuit could not predict before $\kappa$ was drawn.

The order of events is what provides the protection. The whole system description, including every circuit, is fixed and published first, and then $\kappa$ is sampled independently and without bias. An author cannot adapt a circuit to challenges that depend on a number drawn after the circuit was published. The code keeps one tag for each of its two registries.

12. Why cheating fails

This argument is informal. It assumes the discrete log relation assumption for the generators, it treats the transcript hash as a random oracle with each challenge drawn after the data it tests, and it assumes that someone runs the decider. It also assumes that the circuit ties each child's $(S_i,x_i,y_i)$ and circuit point to that child's proof, for the reason that chapter 12 gave about dropping an accumulator. A prover who could restate $x_i$ and $y_i$ freely could prove consistency for coordinates that have nothing to do with the check they were meant to support.

The reasoning of Section 4 applies to the registry link by link. Each commitment is tested at a challenge drawn after it was fixed, and a false commitment passes only at a root of its difference from the true polynomial. Running the toy registry with the best difference we could build at each link gives these counts:

The right child's commitments behave in the same way as the left child's. Those rates are large because the field is small and the polynomials have 8 coefficients:

At $4n=2^{13}$ on a field of about $2^{254}$ elements, each link passes with probability at most $(4n-1)/2^{254}$. Adding this over the six commitments of one fold gives $49,146/2^{254}$, which is below $2^{-238}$.

Now take the attack that opened this chapter and try it against the full protocol. The prover no longer gets to supply a free $S$, because its wiring value has to come out of the accumulator at the domain point of the circuit it named:

Replay Section 1 at $y=12$ and $z=16$. The false trace needs a wiring value of $26$ at $x=21$, while the true $s_A(21,12)$ is $2$. That value comes from $S_{\text{new}}$ at $W=1$, so the prover has to change this polynomial, and it can do so without disturbing the claim at $w=14$ or the right child's value by adding $9(W-14)(W+1)$. All twelve claims are true of the committed polynomials, and the batched check accepts. The false accumulator commits to $(9,9)$ in place of $(23,7)$. The next check tests it at a fresh point. Over all 43 values, the only ones that pass are $W=14$ and $W=42$, the two points the prover built into its difference.

That false accumulator then behaves as in Section 4. It moves from node to node, it changes form with each fold, and at the end of the chain the decider rejects it. As chapter 12 showed, this conclusion relies on binding, because a prover who knows a relation among the generators could open the same point to a different polynomial.

13. Wiring and the registry in Ragu

The code at commit 3219e08 runs the walk of Section 6 inside fuse on both of its registries. Its test-oracle verifier states what each stage must hold, and this list locates most of the values from our table in Section 6 and the two openings from Section 7. Here m is the registry polynomial, left_id is the left child's domain point, and the first entry is the value shared by $S^{\prime \prime }$ and $S_{\text{new}}$:

let query_claim = claimed
    == [
        m(w, x, y),
        m(w, left_x, left_y),
        m(left_id, x, y),
        m(w, left_x, y),
        m(w, right_x, right_y),
        m(right_id, x, y),
        m(w, right_x, y),
    ];

The book and the code use different names for the same objects:

We use $\kappa$ because $k$ already names the public input polynomial.

14. Where this chapter leaves us

This chapter took the following steps:

1. Without a check against the circuit, a prover can commit to wiring of its own and satisfy every other part of the proof.
2. Two restrictions of a polynomial agree at their crossing, which turns a claim about wiring into a pair of evaluation claims.
3. For one circuit, a restriction $s(x,Y)$ ties old claims $(S_i,y_i)$ to a new claim, and a false claim either hits a rare root or passes its error forward until a decider rejects it.
4. The registry polynomial $m(W,X,Y)$ holds many circuits, each at a root of unity, and its restriction $m(W,x,y)$ lets a single commitment supply any circuit's wiring value.
5. The registry walk moves $W$, $Y$ and $X$ one at a time, using four new commitments and ten claims, and each child's circuit adds one more claim.
6. The recursive circuit pays a fixed cost for any registry size, while the prover and the decider pay for reading all of the circuits.
7. Bit reversal gives each circuit a point that does not depend on the size of the registry.
8. A domain check rules out blended circuits, $k_0=1$ rules out bonding polynomials and unassigned points, and a header suffix tells apart circuits whose output headers differ in type.
9. No verification keys exist, so the transcript depends on the circuits through a registry tag that is sampled after they are published, and the code treats this tag as a temporary measure.

This completes the three linear subprotocols that chapter 09 listed: evaluation claims in chapter 12, revdot products in chapter 14, and wiring here. All of them produce challenges in one field and use them on commitments handled in another, so the next chapter looks at how a challenge can cross the curve cycle cheaply.