Introduction

From the 1st of June to the 12th of June (10 working days), two consultants from zkSecurity reviewed the generalized-bulletproofs crate inside the monero-oxide project, commit f3660043e042b5608fc9c8ce1383cee238da9d0a for MAGIC Grants. This code is slated for use in the upcoming Monero ‘fullchain membership proofs’ (FCMP++) and a soundness/privacy critical component of the whole system. We reviewed the codebase as a general library, meaning, we did not discount findings simply because the current application does not trigger the issue.

The code was found to be well-written and easy to understand. The code was reviewed along with its associated paper, for context and because of some concerns about the formal writeup of the extractor (proof of knowledge soundness), we include here a writeup / motivation for the ‘generalized bulletproofs’ protocol as well as a formal proof of (computational) knowledge soundness.

Notation

Let $𝔽$ denote the scalar field and $𝔾$ a prime-order group (in practice a subgroup of an elliptic curve), written additively. Generators are denoted $G,H\in 𝔾$ and $\mathbf{G},\mathbf{H}\in {𝔾}^n$; commitments are capitalized ($V_{(k)},A_C^{(i)}$) and blinding factors written as Greek letters ($\gamma$). We write $a\leftarrow S$ to denote sampling an element from the set $S$ uniformly. An (honest) vector Pedersen commitment to $\mathbf{v}$ with randomness $\gamma$ is $⟨\mathbf{v},\mathbf{G}⟩+\gamma ·H$, and a scalar commitment to $v$ is $v·G+\gamma ·H$.

Bold font denotes vectors, $\mathbf{a}=(a_1,\dots ,a_n)\in {𝔽}^n$, with $\mathbf{1}$ and $\mathbf{0}$ the all-ones and all-zeros vectors, respectively; the witness wires ${\mathbf{a}}_{\mathbf{L}},{\mathbf{a}}_{\mathbf{R}},{\mathbf{a}}_{\mathbf{O}}$ (left, right, output) lie in ${𝔽}^n$, where $n$ and $q$ are the number of multiplication gates and linear constraints. We denote by $⟨\mathbf{a},\mathbf{b}⟩={\sum }_i{a}_i{b}_i$ the inner product, and by $\mathbf{a}\circ \mathbf{b}=(a_1{b}_1,\dots ,a_n{b}_n)$ the Hadamard (entry-wise) product; $(\mathbf{a}{)}^{-1}$ is the entry-wise inverse, so $\mathbf{a}\circ (\mathbf{a}{)}^{-1}=\mathbf{1}$. For $y\in {𝔽}^{*}$ we write $\mathbf{y}=(1,y,\dots ,y^{n-1})$ for the vector of powers and abbreviate $(\mathbf{y}{)}^{-1}=(\mathbf{y}{)}^{-1}$; likewise $\mathbf{z}=(1,z,\dots ,z^{q-1})$.

Generalized Bulletproofs

Bulletproofs provide a Non-Interactive (perfectly) Zero-Knowledge Argument-of-Knowledge (NIZKAoK) for knowledge of ${\mathbf{a}}_{\mathbf{L}},{\mathbf{a}}_{\mathbf{R}},{\mathbf{a}}_{\mathbf{O}},\mathbf{v}$ such that the following relation holds:

Where ${\mathbf{a}}_{\mathbf{L}},{\mathbf{a}}_{\mathbf{R}},{\mathbf{a}}_{\mathbf{O}}\in {𝔽}^n$ and $\mathbf{v}$ are the witnesses, with $\mathbf{v}$ being the opening of a number of (scalar) Pedersen commitments $V_{(1)},\dots ,V_{(m)}\in 𝔾$. Compared to the standard bulletproofs description, to follow the implementation, we have moved $W_V·\mathbf{v}$ and $\mathbf{c}$ over, so the relation is a single linear combination equal to $\mathbf{0}$. Generalized bulletproofs extends this with $c$ “pre-committed” vectors ${{\mathbf{a}}_{\mathbf{C}}}^{(1)},\dots ,{{\mathbf{a}}_{\mathbf{C}}}^{(c)}$, each the opening of a Pedersen commitment of some higher dimension:

For vector commitments $A_C^{(1)},\dots ,A_C^{(c)}\in 𝔾$ and scalar commitments $V_{(1)},\dots ,V_{(m)}\in 𝔾$. Each committed vector ${{\mathbf{a}}_{\mathbf{C}}}^{(i)}$ comes with its own public weight matrix $W_C^{(i)}$ and public commitment $A_C^{(i)}$. The “$⟨{\mathsf{a}\mathsf{u}\mathsf{x}}^{(i)},\mathbf{H}⟩$” term is an artifact of the proof system: it lets a prover who only knows an opening which also depends on the $\mathbf{H}$ generators complete a proof, however these “wires” cannot be “accessed” from within the circuit. To build context for the following code-level review, let’s walk through the Bulletproof arithmetization, which turns this R1CS-equivalent system into an inner product relation, between uniformly random vectors.

GBP Arith 1: R1CS $\to$ $\Sigma$ IP

To simplify the claim:

The verifier samples $y\leftarrow {𝔽}^{*}$ and $z\leftarrow 𝔽$, and defines $\mathbf{y}=(1,\dots ,y^{n-1})$ and $\mathbf{z}=(1,\dots ,z^{q-1})$. We use this to compute linear combinations of every row of each expression:

In case either of the old relations did not hold, this new relation only holds with probability $\le max(n,q)/|𝔽|$. Finally, we can compute a linear combination of each of these equations to end up with a single equation which must equal zero, here, we “reuse” the challenge $z$ to “shift” the second equation:

In summary, we went from an equation over vectors to single field elements using the challenges $y$ and $z$. Moving $z·$ in and splitting the inner products, we can rewrite the second part of the expression as:

Let us define:

Note that the verifier can compute all the vectors itself, since the matrices are public.

We are now left to “deal” with:

Splitting the first inner product, we get the expression that we want to look at going forward:

The next issue at hand is that the expression above has many inner products. Since we need to do an expensive folding argument for every inner product we would like to avoid this: we want to combine all these inner products into a single one. The trick is going to be to interpret these as committed vector polynomials, enabling us to evaluate many parallel polynomials of low degree. More on that now…

GBP Arith 2: Vector Polynomials

An “$n$” dimensional “vector polynomial” consists of $n$ polynomials “in parallel”:

In other words, a polynomial with coefficients in ${\mathbf{c}}_{\mathbf{i}}\in {𝔽}^n$ and evaluation points from $𝔽$, such that plugging an $x$ into $𝐟(X)$ evaluates to $𝐟(x)\in {𝔽}^n$. This notion is useful, because (vector) Pedersen commitments allow us to commit to a vector polynomial efficiently (independently of the dimension $n$):

As well as homomorphically evaluate every coordinate of the vector polynomial at some public point $x$:

Pedersen vector commitments support one further homomorphic operation we will rely on: multiplying the committed vector by a public vector, i.e. a Hadamard product with a public factor, simply by a change of basis. Writing the commitment to $\mathbf{v}$ in basis $\mathbf{G}$ explicitly as $⟨\mathbf{v},\mathbf{G}⟩+r·H$, a public Hadamard factor $\mathbf{s}$ is applied to the opening by re-committing in the basis $(\mathbf{s}{)}^{-1}\circ \mathbf{G}$:

In other words, a commitment to $\mathbf{v}$ in basis $\mathbf{G}$ is also a commitment to $\mathbf{v}\circ \mathbf{s}$ in the basis $(\mathbf{s}{)}^{-1}\circ \mathbf{G}$ with the same blinding $r$: to apply a public Hadamard factor $\mathbf{s}$ to the opening, one re-commits in the basis $(\mathbf{s}{)}^{-1}\circ \mathbf{G}$. This holds because $\mathbf{s}\circ (\mathbf{s}{)}^{-1}=\mathbf{1}$ leaves each generator’s contribution unchanged and the blinding term $r·H$ is untouched.

The “inner product” between two vector polynomials is defined in the intuitive way (for any module over any ring): taking the coordinate-wise product of polynomials and summing:

Note that $\forall x.⟨𝐟,𝐠⟩(x)=⟨𝐟(x),𝐠(x)⟩$ and $\mathrm{deg}(⟨𝐟,𝐠⟩)=\mathrm{deg}(𝐟)+\mathrm{deg}(𝐠)$.

GBP Arith 3: $\Sigma$ IP $\to$ Single IP

Viewing the vectors as vector polynomials is useful because it allows us to batch check independent inner products. Suppose we have two inner products:

We define the vector polynomials (“left/right”):

And consider the inner product, then the desired inner product $\Delta$ lands in the square term:

Where ${\delta }_0,{\delta }_1,{\delta }_3$ are some cross-term garbage we don’t care about. More generally: we define a “left polynomial” where powers increase for every left term in the series of inner products and a “right polynomial” where the powers decrease for every right term, then the terms will “align” at the “middle power”. i.e. in general, suppose we have:

Then we define:

In which case, the $t$‘th coefficient of $⟨{\mathbf{f}}_{\mathbf{L}},{\mathbf{f}}_{\mathbf{R}}⟩(X)$ is $\Delta$. This observation suggests the following approach to reduce a sum of multiple inner products, given commitments to every vector, to a single inner product as follows:

1. Prover sends commitments to the coefficients $\{{\delta }_i{\}}_{i\in 0,\dots ,2·t-1}$, where we are interested in ${\delta }_t=\Delta$, which is usually implicit (e.g. fixed to $0$). Then both parties locally define:

1. Verifier samples $x\leftarrow 𝔽$
2. Both sides compute commitments to the vectors:

And a commitment to the field element $g(x)\in 𝔽$, using the homomorphic property of the Pedersen commitments. We now have just a single inner product claim about Pedersen commitments:

GBP Arith 4: Combining

Recall the expression we were trying to verify, before our digression about batching inner products and vector polynomials:

To apply the techniques above, we want to:

• Eliminate Pairwise Products. We haven’t yet described a technique for proving Hadamard (pairwise) products of secret (committed) vectors, so we get to get rid of ${\mathbf{a}}_{\mathbf{L}}\circ {\mathbf{a}}_{\mathbf{R}}$; we want each secret to appear on a different side of an inner product.

• Collect Common Terms. Reduce the number of inner products, for efficiency, by collecting common terms. This reduces the degree of the vector polynomials, meaning: less committed coefficients and less cross-terms.

Eliminate Secret-Secret Hadamard Product

Note that the left side of the inner product $⟨\mathbf{y},{\mathbf{a}}_{\mathbf{L}}\circ {\mathbf{a}}_{\mathbf{R}}⟩$ is public, so let us move one secret to each side, using $⟨\mathbf{y},{\mathbf{a}}_{\mathbf{L}}\circ {\mathbf{a}}_{\mathbf{R}}⟩=⟨{\mathbf{a}}_{\mathbf{L}},\mathbf{y}\circ {\mathbf{a}}_{\mathbf{R}}⟩$ to get rid of the Hadamard product between secret values:

Note that we know how to deal with a Hadamard product between a secret and a public value.

Combine the ${\mathbf{a}}_{\mathbf{O}}$ terms

Rewrite ${\mathbf{a}}_{\mathbf{R}}$ Inner Product

Using $⟨{\mathbf{a}}_{\mathbf{R}},{\mathbf{w}}_{\mathbf{R}}⟩=⟨{\mathbf{w}}_{\mathbf{R}}\circ (\mathbf{y}{)}^{-1},\mathbf{y}\circ {\mathbf{a}}_{\mathbf{R}}⟩$ rewrite:

Collect $\mathbf{y}\circ {\mathbf{a}}_{\mathbf{R}}$ Terms

This was our motivation for the previous step:

Add $\delta (y,z)$ to Both Sides

Add the public scalar $\delta (y,z)=⟨(\mathbf{y}{)}^{-1}\circ {\mathbf{w}}_{\mathbf{R}},{\mathbf{w}}_{\mathbf{L}}⟩$ to both sides (note that $0$ on the left becomes $\delta (y,z)$):

Note that $\delta (y,z)$ does not depend on the witness! (the verifier can compute it)

Combine ${\mathbf{w}}_{\mathbf{L}}$ Terms

Combine ${\mathbf{a}}_{\mathbf{L}}+{\mathbf{w}}_{\mathbf{R}}\circ (\mathbf{y}{)}^{-1}$ Terms

So we are left with $2+c$ inner products: two coming from the ${\mathbf{a}}_{\mathbf{L}},{\mathbf{a}}_{\mathbf{R}},{\mathbf{a}}_{\mathbf{O}}$ terms and one for each of the $c$ committed vectors ${{\mathbf{a}}_{\mathbf{C}}}^{(i)}$. All these are combined into a single inner product using the previous technique based on vector polynomials.

Note that during verification everything except the $2+c$ inner products is known to the verifier: $\delta (y,z)$ (on the left) and $w_c$ are public, and $⟨{\mathbf{w}}_{\mathbf{V}},\mathbf{v}⟩$ is a commitment to a single field element, formed homomorphically from the $V_{(k)}$. Those inner products are folded into a single one next.

Arithmetization

Public inputs: generators $\mathbf{G},\mathbf{H}\in {𝔾}^n$ and $G,H\in 𝔾$; weight matrices $W_L$, $W_R$, $W_O$, $\{W_C^{(k)}{\}}_{k=1}^c$, $W_V$ with constant $\mathbf{c}$; vector commitments $\{A_C^{(k)}{\}}_{k=1}^c$ and scalar commitments $\{V_{(j)}{\}}_{j=1}^m$. Write $n^{\prime }=2c+2$ for the target monomial.

• Prover $\to$ Verifier.
  • Sample $\alpha ,\beta ,\rho \leftarrow 𝔽$ and ${\mathbf{s}}_{\mathbf{L}},{\mathbf{s}}_{\mathbf{R}}\leftarrow {𝔽}^n$.
  • $A_{L|R}=⟨{\mathbf{a}}_{\mathbf{L}},\mathbf{G}⟩+⟨{\mathbf{a}}_{\mathbf{R}},\mathbf{H}⟩+\alpha H$
  • $A_O=⟨{\mathbf{a}}_{\mathbf{O}},\mathbf{G}⟩+\beta H$
  • $S=⟨{\mathbf{s}}_{\mathbf{L}},\mathbf{G}⟩+⟨{\mathbf{s}}_{\mathbf{R}},\mathbf{H}⟩+\rho H$
  • Send $(A_{L|R},A_O,S)$.
• Verifier $\to$ Prover.
  • Sample $y,z\leftarrow {𝔽}^{*}$.
  • Send $(y,z)$.
  • Both parties compute:
    • The challenge vectors $\mathbf{y},(\mathbf{y}{)}^{-1},\mathbf{z}$
    • The weights ${\mathbf{w}}_{\mathbf{L}},{\mathbf{w}}_{\mathbf{R}},{\mathbf{w}}_{\mathbf{O}},\{{{\mathbf{w}}_{\mathbf{C}}}^{(k)}\},{\mathbf{w}}_{\mathbf{V}},w_c$
    • $\delta (y,z)=⟨(\mathbf{y}{)}^{-1}\circ {\mathbf{w}}_{\mathbf{R}},{\mathbf{w}}_{\mathbf{L}}⟩$
• Prover $\to$ Verifier.
  • Recall that the inner products to batch are: $$\begin{array}{cc}\hfill t_{n^{\prime }}& =⟨{\mathbf{a}}_{\mathbf{L}}+{\mathbf{w}}_{\mathbf{R}}\circ (\mathbf{y}{)}^{-1},\mathbf{y}\circ {\mathbf{a}}_{\mathbf{R}}+{\mathbf{w}}_{\mathbf{L}}⟩+⟨{\mathbf{a}}_{\mathbf{O}},{\mathbf{w}}_{\mathbf{O}}-\mathbf{y}⟩+\sum _{k=1}^c⟨{{\mathbf{a}}_{\mathbf{C}}}^{(k)},{{\mathbf{w}}_{\mathbf{C}}}^{(k)}⟩\hfill \\ \hfill & =\delta (y,z)-w_c-⟨{\mathbf{w}}_{\mathbf{V}},\mathbf{v}⟩.\hfill \end{array}$$
  • Build ${\mathbf{f}}_{\mathbf{L}}(X),{\mathbf{f}}_{\mathbf{R}}(X)\in 𝔽[X{]}^n$ (powers as in GBP Arith 3) with nonzero coefficients:
    • ${\mathbf{f}}_{\mathbf{L}}(X)$:
      • ${\mathbf{a}}_{\mathbf{L}}+{\mathbf{w}}_{\mathbf{R}}\circ (\mathbf{y}{)}^{-1}$ at $X^{n^{\prime }/2}$
      • ${{\mathbf{a}}_{\mathbf{C}}}^{(k)}$ at $X^{n^{\prime }-k}$ for $k=1,\dots ,c$
      • ${\mathbf{a}}_{\mathbf{O}}$ at $X^{n^{\prime }}$
      • ${\mathbf{s}}_{\mathbf{L}}$ at $X^{n^{\prime }+1}$
    • ${\mathbf{f}}_{\mathbf{R}}(X)$:
      • ${\mathbf{w}}_{\mathbf{O}}-\mathbf{y}$ at $X^0$
      • ${{\mathbf{w}}_{\mathbf{C}}}^{(k)}$ at $X^k$ for $k=1,\dots ,c$
      • $\mathbf{y}\circ {\mathbf{a}}_{\mathbf{R}}+{\mathbf{w}}_{\mathbf{L}}$ at $X^{n^{\prime }/2}$
      • $\mathbf{y}\circ {\mathsf{a}\mathsf{u}\mathsf{x}}^{(k)}$ at $X^{n^{\prime }-k}$ for $k=1,\dots ,c$
      • $\mathbf{y}\circ {\mathbf{s}}_{\mathbf{R}}$ at $X^{n^{\prime }+1}$
    • Corresponding to generators in $\mathbf{G}$ and $\mathbf{H}$ respectively.
  • $t(X)=⟨{\mathbf{f}}_{\mathbf{L}}(X),{\mathbf{f}}_{\mathbf{R}}(X)⟩={\sum }_{i=n^{\prime }/2}^{2(n^{\prime }+1)}{t}_i{X}^i$; the target coefficient is $t_{n^{\prime }}$.
  • Sample ${\tau }_i\leftarrow 𝔽$ for every $i\ne n^{\prime }$ and set $T_i=t_{i}G+{\tau }_{i}H$.
  • Send $\{T_i{\}}_{i\ne n^{\prime }}$.
• Verifier $\to$ Prover.
  • Sample $x\leftarrow {𝔽}^{*}$.
  • Send $x$.
• Prover $\to$ Verifier.
  • Opening of $t(x)$ (value $\hat{t}$, blinding ${\tau }_x$): $$\begin{array}{cc}\hfill \hat{t}& =⟨{\mathbf{f}}_{\mathbf{L}}(x),{\mathbf{f}}_{\mathbf{R}}(x)⟩=t(x)\hfill \\ \hfill {\tau }_x& =\sum _{i\ne n^{\prime }}{\tau }_i{x}^i-x^{n^{\prime }}⟨{\mathbf{w}}_{\mathbf{V}},{\gamma }_V⟩\hfill \end{array}$$
  • Opening of $P$ (vectors ${\mathbf{f}}_{\mathbf{L}}(x),{\mathbf{f}}_{\mathbf{R}}(x)$, blinding $\mu$): $$\mu =\alpha ·x^{n^{\prime }/2}+\beta ·x^{n^{\prime }}+\rho ·x^{n^{\prime }+1}+\sum _{k=1}^c{\gamma }^{(k)}·x^{n^{\prime }-k}$$ With ${\gamma }_V$ the blinding factors of the $V_{(j)}$ and ${\gamma }^{(k)}$ the blinding factor of $A_C^{(k)}$.
  • Send $({\tau }_x,\mu ,\hat{t},{\mathbf{f}}_{\mathbf{L}}(x)\in {𝔽}^n,{\mathbf{f}}_{\mathbf{R}}(x)\in {𝔽}^n)$.
• Verifier.
  • Set ${\mathbf{H}}^{(\mathbf{y}{)}^{-1}}=(\mathbf{y}{)}^{-1}\circ \mathbf{H}$.
  • Define: $$\begin{array}{cccc}\hfill {\tilde{W}}_L& =⟨{\mathbf{w}}_{\mathbf{L}},{\mathbf{H}}^{(\mathbf{y}{)}^{-1}}⟩\in 𝔾\hfill & \hfill {\tilde{W}}_R& =⟨(\mathbf{y}{)}^{-1}\circ {\mathbf{w}}_{\mathbf{R}},\mathbf{G}⟩\in 𝔾\hfill \\ \hfill {\tilde{W}}_O& =⟨{\mathbf{w}}_{\mathbf{O}}-\mathbf{y},{\mathbf{H}}^{(\mathbf{y}{)}^{-1}}⟩\in 𝔾\hfill & \hfill {\tilde{W}}_k& =⟨{{\mathbf{w}}_{\mathbf{C}}}^{(k)},{\mathbf{H}}^{(\mathbf{y}{)}^{-1}}⟩\in 𝔾\hfill \end{array}$$
  • Compute: $$P={\tilde{W}}_O+\sum _{k=1}^c{x}^k{\tilde{W}}_k+x^{n^{\prime }/2}(A_{L|R}+{\tilde{W}}_L+{\tilde{W}}_R)+\sum _{k=1}^c{x}^{n^{\prime }-k}{A}_C^{(k)}+x^{n^{\prime }}{A}_O+x^{n^{\prime }+1}S$$
  • Check: $$\hat{t}G+{\tau }_{x}H=x^{n^{\prime }}((\delta (y,z)-w_c)G-{\sum }_{j=1}^m({\mathbf{w}}_{\mathbf{V}}{)}_j{V}_{(j)})+\sum _{i\ne n^{\prime }}{x}^i{T}_i$$
  • Check: $$((\mathbf{G},{\mathbf{H}}^{(\mathbf{y}{)}^{-1}},H,P,\mu ,\hat{t}),({\mathbf{f}}_{\mathbf{L}}(x),{\mathbf{f}}_{\mathbf{R}}(x)))\in {ℛ}_{\mathsf{I}\mathsf{P}}$$

Computational Special Soundness

We prove that the arithmetization (‘Generalized Bulletproofs’) is an argument of knowledge for ${ℛ}_{\mathsf{G}\mathsf{B}\mathsf{P}}$. The theorem below establishes $(n,q+1,2n^{\prime }+3)$-computational special soundness. By Attema, Fehr and Klooß (TCC 2022) the Fiat-Shamir compiled argument then has tight security: under the hardness of discrete log over $𝔾$ it is knowledge sound with knowledge error at most $(Q_{\mathsf{r}\mathsf{o}}+1)·(n+q+4c+5)/(|𝔽|-1)$, where $Q_{\mathsf{r}\mathsf{o}}$ is the number of random-oracle queries made by the adversary.

Theorem. Assume $W_V$ has full column rank $m$, i.e. a left inverse. The full arithmetization is $(n,q+1,2n^{\prime }+3)$-computationally special sound for ${ℛ}_{\mathsf{G}\mathsf{B}\mathsf{P}}$: from any $(n,q+1,2n^{\prime }+3)$-tree of accepting transcripts a deterministic extractor returns either a witness for ${ℛ}_{\mathsf{G}\mathsf{B}\mathsf{P}}$, or a non-trivial discrete-log relation among the generators , i.e. a non-zero $\mathbf{v}$ with $⟨\mathbf{v},\Gamma ⟩=0$.

The Tree of Transcripts. A $(n,q+1,2n^{\prime }+3)$-tree fixes the first message $(A_{L|R},A_O,S)$ at the root and branches on the three challenges, recording each verifier message at its node: $n$ distinct children on $y$; under each, $q+1$ distinct children on $z$, each with its $\{T_i\}$; under each, $2n^{\prime }+3$ distinct leaves on $x$, each with its opening $({\tau }_x,\mu ,{\mathbf{f}}_{\mathbf{L}}(x),{\mathbf{f}}_{\mathbf{R}}(x))$. Every root-to-leaf path is an accepting transcript. Index a $(y,z)$-node by $(i_y,i_z)$ and its $x$-leaves by $i_x$, so $(i_y,i_z,i_x)$ indexes a full transcript. The three arities are forced by the three interpolations below: $2n^{\prime }+3=\mathrm{deg}t+1$ for $x$; $q+1$ for the $q$ constraint rows together with the constant Hadamard term; $n$ for the Hadamard coordinates.

Step 1: $x$-Vandermonde Read-off. Fix a node $(i_y,i_z)$. The verifier’s $P$ is the value at the leaf’s challenge of a polynomial ${\sum }_{p=0}^{2(n^{\prime }+1)}{x}^p{P}_p$ whose coefficients $P_p\in 𝔾$ are:

With $P_p=\mathbf{0}$ for $p>n^{\prime }+1$.

The $2n^{\prime }+3$ leaves of the node share $(y,z)$ and use distinct $x$, so the $P$-opening check at leaf $i_x$:

Is a Vandermonde system in $x$; inverting it writes each $P_p$ as a representation in the $(\mathbf{G},{\mathbf{H}}^{(\mathbf{y}{)}^{-1}},H)$ basis. When the node’s collision candidates (Step 5) all vanish, the $\mathbf{G}$-block of $P_p$ at every degree equals the honest ${\mathbf{f}}_{\mathbf{L}}$ coefficient and the ${\mathbf{H}}^{(\mathbf{y}{)}^{-1}}$-block at every degree $\ne n^{\prime }$ equals the honest ${\mathbf{f}}_{\mathbf{R}}$ coefficient: the public degrees $0$ and $k$ open purely on ${\mathbf{H}}^{(\mathbf{y}{)}^{-1}}$ to ${\mathbf{w}}_{\mathbf{O}}-\mathbf{y}$ and ${{\mathbf{w}}_{\mathbf{C}}}^{(k)}$; degree $n^{\prime }/2$ gives ${\mathbf{a}}_{\mathbf{L}}+{\mathbf{w}}_{\mathbf{R}}\circ (\mathbf{y}{)}^{-1}$ on $\mathbf{G}$ and $\mathbf{y}\circ {\mathbf{a}}_{\mathbf{R}}+{\mathbf{w}}_{\mathbf{L}}$ on ${\mathbf{H}}^{(\mathbf{y}{)}^{-1}}$; degrees $n^{\prime }-k$, $n^{\prime }$, $n^{\prime }+1$ give the wires ${{\mathbf{a}}_{\mathbf{C}}}^{(k)},{\mathbf{a}}_{\mathbf{O}},{\mathbf{s}}_{\mathbf{L}}$ on $\mathbf{G}$ and $\mathbf{y}\circ {\mathsf{a}\mathsf{u}\mathsf{x}}^{(k)},\mathbf{y}\circ {\mathbf{s}}_{\mathbf{R}}$ on ${\mathbf{H}}^{(\mathbf{y}{)}^{-1}}$. The lone degree-$n^{\prime }$ ${\mathbf{H}}^{(\mathbf{y}{)}^{-1}}$-block — the $\mathbf{H}$-part of $A_O$ — is unconstrained; the relation tolerates this slack, and since its convolution partner is the degree-$0$ coefficient of ${\mathbf{f}}_{\mathbf{L}}$, which is $\mathbf{0}$, it never contributes downstream.

Step 2: The Per-Node Identity $(\star )$. With the leaf openings pinned to the honest ${\mathbf{f}}_{\mathbf{L}},{\mathbf{f}}_{\mathbf{R}}$, the $n^{\prime }$-coefficient of $⟨{\mathbf{f}}_{\mathbf{L}}(X),{\mathbf{f}}_{\mathbf{R}}(X)⟩$ — the committed target $t_{n^{\prime }}$, recovered from the leaves by inverting the same $x$-Vandermonde at degree $n^{\prime }$ — expands without invoking any constraint into $\delta (y,z)$, the $z$-aggregated linear $R1CS$ rows, and the $y$-weighted Hadamard term $⟨\mathbf{y},{\mathbf{a}}_{\mathbf{L}}\circ {\mathbf{a}}_{\mathbf{R}}-{\mathbf{a}}_{\mathbf{O}}⟩$. The first verifier check independently pins the same coefficient to $t_{n^{\prime }}=\delta (y,z)-w_c-⟨{\mathbf{w}}_{\mathbf{V}},\mathbf{v}⟩$; here the check couples $⟨{\mathbf{w}}_{\mathbf{V}},\mathbf{v}⟩$ to the aggregate ${\sum }_j({\mathbf{w}}_{\mathbf{V}}{)}_j{V}_{(j)}$ through its degree-$n^{\prime }$ coefficient, the two agreeing once the corresponding $(G,H)$-collision candidate of Step 5 vanishes. Equating the two expansions and cancelling $\delta (y,z)$ gives, at every node $(i_y,i_z)$: