# Generalized Bulletproofs
- **Client**: MAGIC Grants
- **Date**: June 1st, 2026
- **Tags**: Bulletproofs, Zero-Knowledge Proofs, R1CS
The math in this report uses the following custom LaTeX macros:
```latex
\newcommand{\ACi}[1]{A_C^{(#1)}}
\newcommand{\ALR}{A_{L|R}}
\newcommand{\AO}{A_O}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\G}{G}
\newcommand{\GG}{\mathbb{G}}
\newcommand{\H}{H}
\newcommand{\RGBPp}{\mathcal{R}_{\mathsf{GBP}'}}
\newcommand{\RIP}{\mathcal{R}_{\mathsf{IP}}}
\newcommand{\RIPA}[1]{\mathcal{R}_{\mathsf{IPA}, #1}}
\newcommand{\S}{S}
\newcommand{\WCi}[1]{W_C^{(#1)}}
\newcommand{\WL}{W_L}
\newcommand{\WO}{W_O}
\newcommand{\WR}{W_R}
\newcommand{\WV}{W_V}
\newcommand{\Wt}[1]{\widetilde{W}_{#1}}
\newcommand{\aC}{\nvec{a_C}}
\newcommand{\aCi}[1]{\nvec{a_C}^{(#1)}}
\newcommand{\aL}{\nvec{a_L}}
\newcommand{\aO}{\nvec{a_O}}
\newcommand{\aR}{\nvec{a_R}}
\newcommand{\aux}[1]{\mathsf{aux}^{(#1)}}
\newcommand{\bind}{r}
\newcommand{\blind}{\gamma}
\newcommand{\bpG}{\nvec{G}}
\newcommand{\bpH}{\nvec{H}}
\newcommand{\bpHt}{\widetilde{\nvec{H}}}
\newcommand{\chal}{\xi}
\newcommand{\comI}[1]{V_{(#1)}}
\newcommand{\concat}{\mathbin{\|}}
\newcommand{\f}{f}
\newcommand{\fL}{\mathbf{f_L}}
\newcommand{\fR}{\mathbf{f_R}}
\newcommand{\g}{g}
\newcommand{\h}{h}
\newcommand{\hl}[1]{\color{#C96A2F}{#1}}
\newcommand{\ht}{\widehat{t}}
\newcommand{\ip}[2]{\left\langle #1, #2 \right\rangle}
\newcommand{\ix}{i_x}
\newcommand{\iy}{i_y}
\newcommand{\iz}{i_z}
\newcommand{\leaf}{e}
\newcommand{\numCom}{m}
\newcommand{\numCons}{q}
\newcommand{\numGates}{n}
\newcommand{\numQueries}{Q_{\mathsf{ro}}}
\newcommand{\numVecCom}{c}
\newcommand{\nvec}[1]{\mathbf{#1}}
\newcommand{\relation}{\mathcal{R}}
\newcommand{\row}{\ell}
\newcommand{\sample}{\gets}
\newcommand{\size}{N}
\newcommand{\taux}{\tau_x}
\newcommand{\vc}{\nvec{c}}
\newcommand{\vf}{\mathbf{f}}
\newcommand{\vg}{\mathbf{g}}
\newcommand{\vh}{\mathbf{h}}
\newcommand{\vv}{\nvec{v}}
\newcommand{\vy}{\nvec{y}}
\newcommand{\vz}{\nvec{z}}
\newcommand{\vzero}{\nvec{0}}
\newcommand{\wC}{\nvec{w_C}}
\newcommand{\wCi}[1]{\nvec{w_C}^{(#1)}}
\newcommand{\wL}{\nvec{w_L}}
\newcommand{\wO}{\nvec{w_O}}
\newcommand{\wR}{\nvec{w_R}}
\newcommand{\wV}{\nvec{w_V}}
\newcommand{\x}{x}
\newcommand{\xdeg}{p}
\newcommand{\y}{y}
\newcommand{\yinv}{(\nvec{y})^{-1}}
\newcommand{\z}{z}
```
# 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](https://github.com/cypherstack/generalized-bulletproofs-fix), 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 $\FF$ denote the scalar field and $\GG$ a prime-order group (in practice a subgroup of an elliptic curve), written additively.
Generators are denoted $\G, \H \in \GG$ and $\bpG, \bpH \in \GG^{\numGates}$; commitments are capitalized ($\comI{k}, \ACi{i}$) and blinding factors written as Greek letters ($\blind$).
We write $a \sample S$ to denote sampling an element from the set $S$ uniformly.
An (honest) vector Pedersen commitment to $\nvec{v}$ with randomness $\blind$ is $\ip{\nvec{v}}{\bpG} + \blind \cdot \H$, and a scalar commitment to $v$ is $v \cdot \G + \blind \cdot \H$.
Bold font denotes vectors, $\nvec{a} = (a_1, \ldots, a_{\numGates}) \in \FF^{\numGates}$, with $\nvec{1}$ and $\vzero$ the all-ones and all-zeros vectors, respectively; the witness wires $\aL, \aR, \aO$ (left, right, output) lie in $\FF^{\numGates}$, where $\numGates$ and $\numCons$ are the number of multiplication gates and linear constraints.
We denote by $\ip{\nvec{a}}{\nvec{b}} = \sum_i a_i b_i$ the inner product, and by $\nvec{a} \circ \nvec{b} = (a_1 b_1, \ldots, a_{\numGates} b_{\numGates})$ the Hadamard (entry-wise) product; $(\nvec{a})^{-1}$ is the entry-wise inverse, so $\nvec{a} \circ (\nvec{a})^{-1} = \nvec{1}$.
For $\y \in \FF^{*}$ we write $\vy = (1, \y, \ldots, \y^{\numGates-1})$ for the vector of powers and abbreviate $\yinv = (\vy)^{-1}$; likewise $\vz = (1, \z, \ldots, \z^{\numCons-1})$.
# Generalized Bulletproofs
Bulletproofs provide a Non-Interactive (perfectly) Zero-Knowledge Argument-of-Knowledge (NIZKAoK)
for knowledge of $\aL, \aR, \aO, \vv$ such that the following relation holds:
$$
\relation_{\mathsf{BP}} = \left\{ \begin{array}{l}
\left(\aL, \aR, \aO, \vv, \{\blind_k\}_{k=1}^{\numCom}\right) \ : \\
\vzero = \WL \cdot \aL + \WR \cdot \aR + \WO \cdot \aO + \WV \cdot \vv + \vc \\
\vzero = \aL \circ \aR - \aO \\
\forall k.\ \comI{k} = v_k \cdot \G + \blind_k \cdot \H
\end{array} \right\}
$$
Where $\aL, \aR, \aO \in \FF^{\numGates}$ and $\vv$ are the witnesses, with $\vv$
being the opening of a number of (scalar) Pedersen commitments $\comI{1}, \ldots, \comI{\numCom} \in \GG$.
Compared to the standard bulletproofs description, to follow the implementation,
we have moved $\WV \cdot \vv$ and $\vc$ over, so the relation is a single linear combination equal to $\vzero$.
Generalized bulletproofs extends this with $\numVecCom$ "pre-committed" vectors $\aCi{1}, \ldots, \aCi{\numVecCom}$,
each the opening of a Pedersen commitment of some higher dimension:
$$
\relation_{\mathsf{GBP}} = \left\{ \begin{array}{l}
\left(\aL, \aR, \aO, \vv, \{\aCi{i}, \aux{i}, \blind^{(i)}\}_{i=1}^{\numVecCom}, \{\blind_k\}_{k=1}^{\numCom}\right) \ : \\
\vzero = \WL \cdot \aL + \WR \cdot \aR + \WO \cdot \aO + \sum_{i=1}^{\numVecCom} \WCi{i} \cdot \aCi{i} + \WV \cdot \vv + \vc \\
\vzero = \aL \circ \aR - \aO \\
\forall i.\ \ACi{i} = \ip{\aCi{i}}{\bpG} + \ip{\aux{i}}{\bpH} + \blind^{(i)} \cdot \H \\
\forall k.\ \comI{k} = v_k \cdot \G + \blind_k \cdot \H
\end{array} \right\}
$$
For *vector commitments* $\ACi{1}, \ldots, \ACi{\numVecCom} \in \GG$ and *scalar commitments* $\comI{1}, \ldots, \comI{\numCom} \in \GG$.
Each committed vector $\aCi{i}$ comes with its own public weight matrix $\WCi{i}$ and public commitment $\ACi{i}$.
The "$\ip{\aux{i}}{\bpH}$" term is an artifact of the proof system: it lets a prover who only knows an opening which also depends on the $\bpH$ 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 $\rightarrow$ $\Sigma$ IP
To simplify the claim:
$$
\begin{align*}
\vzero &= \aL \circ \aR - \aO \\
\\
\vzero &= \WL \cdot \aL + \WR \cdot \aR + \WO \cdot \aO + \sum_{i=1}^{\numVecCom} \WCi{i} \cdot \aCi{i} + \WV \cdot \vv + \vc
\end{align*}
$$
The verifier samples $\y \sample \FF^{*}$ and $\z \sample \FF$,
and defines $\vy = (1, \ldots, y^{\numGates-1})$ and $\vz = (1, \ldots, z^{\numCons-1})$.
We use this to compute linear combinations of every row of each expression:
$$
\begin{align*}
0 &= \ip{\vy}{\aL \circ \aR - \aO} \\
\\
0 &= \ip{\vz}{\WL \cdot \aL + \WR \cdot \aR + \WO \cdot \aO + \sum_{i=1}^{\numVecCom} \WCi{i} \cdot \aCi{i} + \WV \cdot \vv + \vc}
\end{align*}
$$
In case either of the old relations did not hold,
this new relation only holds with probability $\leq \max(\numGates, \numCons)/|\FF|$.
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:
$$
\begin{align*}
0 &= \ip{\vy}{\aL \circ \aR - \aO} \\
& + z \cdot \ip{\vz}{\WL \cdot \aL + \WR \cdot \aR + \WO \cdot \aO + \sum_{i=1}^{\numVecCom} \WCi{i} \cdot \aCi{i} + \WV \cdot \vv + \vc}
\end{align*}
$$
In summary, we went from an equation over vectors to single field elements using the challenges $\y$ and $\z$.
Moving $z \cdot$ in and splitting the inner products, we can rewrite the second part of the expression as:
$$
\begin{align*}
0 &= \ip{z \vz \cdot \WL}{\aL} + \ip{z \vz \cdot \WR}{\aR} + \ip{z \vz \cdot \WO}{\aO} \\
& + \sum_{i=1}^{\numVecCom} \ip{z \vz \cdot \WCi{i}}{\aCi{i}} + \ip{z \vz \cdot \WV}{\vv} + \ip{z \vz}{\vc}
\end{align*}
$$
Let us define:
$$
\begin{align*}
\wL &= z \cdot \vz \cdot \WL \in \FF^{\numGates} \\
\wR &= z \cdot \vz \cdot \WR \in \FF^{\numGates} \\
\wV &= z \cdot \vz \cdot \WV \in \FF^{\numGates} \\
\wCi{i} &= z \cdot \vz \cdot \WCi{i} \in \FF^{\numGates} \quad (i = 1, \ldots, \numVecCom) \\
\wO &= z \cdot \vz \cdot \WO \in \FF^{\numGates} \\
w_c &= \ip{z \cdot \vz}{\vc} \in \FF
\end{align*}
$$
Note that the verifier can compute all the vectors itself, since the matrices are public.
We are now left to "deal" with:
$$
\begin{align*}
0 &= \ip{\vy}{\aL \circ \aR - \aO} + \ip{\wL}{\aL} + \ip{\wR}{\aR} + \ip{\wO}{\aO} + \sum_{i=1}^{\numVecCom} \ip{\wCi{i}}{\aCi{i}} \\
&+ \ip{\wV}{\vv} + w_c \in \FF
\end{align*}
$$
Splitting the first inner product, we get the expression that we want to look at going forward:
$$
\begin{align*}
0 &= \ip{\vy}{\aL \circ \aR} - \ip{\vy}{\aO} + \ip{\wL}{\aL} + \ip{\wR}{\aR} + \ip{\wO}{\aO} + \sum_{i=1}^{\numVecCom} \ip{\wCi{i}}{\aCi{i}} \\
&+ \ip{\wV}{\vv} + w_c \in \FF
\end{align*}
$$
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 "$\numGates$" dimensional "vector polynomial" consists of $\numGates$ polynomials "in parallel":
$$
\vf(X) = (\f_1(X), \ldots, \f_n(X)) = \sum_{i=0}^d \nvec{c_i} \cdot X^i \in \FF[X]^{\numGates}
$$
In other words, a polynomial with *coefficients* in $\nvec{c_i} \in \FF^{\numGates}$ and evaluation points from $\FF$,
such that plugging an $\x$ into $\vf(X)$ evaluates to $\vf(\x) \in \FF^{\numGates}$.
This notion is useful, because (vector) Pedersen commitments allow us to commit to a vector polynomial efficiently (independently of the dimension $\numGates$):
$$
\begin{align*}
\mathsf{Com}_{\bpG, \H} \ : \ (\FF^{\numGates})[X]^{\leq d} \times \FF^{d+1} &\to \GG^{d+1}\\
\mathsf{Com}_{\bpG, \H}(\mathbf{f}(X);\ \nvec{r}) &\mapsto (\ip{\nvec{c_0}}{\bpG} + r_0 \cdot \H, \ldots, \ip{\nvec{c_d}}{\bpG} + r_d \cdot \H) \in \GG^{d+1}
\end{align*}
$$
As well as homomorphically evaluate every coordinate of the vector polynomial at some public point $\x$:
$$
\sum_{i=0}^{d} \x^i \cdot \left( \ip{\nvec{c_i}}{\bpG} + r_i \cdot \H \right) = \ip{\vf(\x)}{\bpG} + r' \cdot \H \in \GG
$$
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 $\nvec{v}$ in basis $\bpG$ explicitly as $\ip{\nvec{v}}{\bpG} + r \cdot \H$, a public Hadamard factor $\nvec{s}$ is applied to the opening by re-committing in the basis $(\nvec{s})^{-1} \circ \bpG$:
$$
\begin{align*}
\mathsf{Com}_{(\nvec{s})^{-1} \circ \bpG,\ \H}(\nvec{v} \circ \nvec{s};\ r) &= \mathsf{Com}_{\bpG,\ \H}(\nvec{v};\ r) \\
\ip{\nvec{v} \circ \nvec{s}}{(\nvec{s})^{-1} \circ \bpG} + r \cdot \H &= \ip{\nvec{v}}{\bpG} + r \cdot \H
\end{align*}
$$
In other words, a commitment to $\nvec{v}$ in basis $\bpG$ is also a commitment to $\nvec{v} \circ \nvec{s}$ in the basis $(\nvec{s})^{-1} \circ \bpG$ with the same blinding $r$: to apply a public Hadamard factor $\nvec{s}$ to the opening, one re-commits in the basis $(\nvec{s})^{-1} \circ \bpG$. This holds because $\nvec{s} \circ (\nvec{s})^{-1} = \nvec{1}$ leaves each generator's contribution unchanged and the blinding term $r \cdot \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*:
$$
\ip{\mathbf{f}(X)}{\mathbf{g}(X)} = \sum_i f_i(X) \cdot g_i(X) \in \FF[X]
$$
Note that $\forall \x. \ip{\vf}{\vg}(\x) = \ip{\vf(\x)}{\vg(\x)}$ and $\deg(\ip{\vf}{\vg}) = \deg(\vf) + \deg(\vg)$.
## GBP Arith 3: $\Sigma$ IP $\rightarrow$ 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:
$$
\Delta = \ip{\mathbf{a}}{\mathbf{b}} + \ip{\mathbf{c}}{\mathbf{d}}
$$
We define the vector polynomials ("left/right"):
$$
\begin{align*}
\fL(X) &= \nvec{a} \cdot X + \nvec{c} \cdot X^2 \\
\fR(X) &= \nvec{b} \cdot X + \nvec{d}
\end{align*}
$$
And consider the inner product, then the desired inner product $\Delta$ lands in the square term:
$$
\ip{\fL}{\fR}(X) = \delta_0 + \delta_1 \cdot X + \Delta \cdot X^2 + \delta_3 \cdot X^3
\in \FF[X]$$
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:
$$
\Delta = \sum_{i=1}^t \ip{\mathbf{L_i}}{\mathbf{R_i}}
$$
Then we define:
$$
\begin{align*}
\fL(X) &= \sum_{i=1}^t \mathbf{L_i} \cdot X^i \\
\fR(X) &= \sum_{i=1}^{t} \mathbf{R_i} \cdot X^{t - i}
\end{align*}
$$
In which case, the $t$'th coefficient of $\ip{\fL}{\fR}(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, \ldots, 2 \cdot t - 1}$, where we are interested in $\delta_t = \Delta$, which is usually implicit (e.g. fixed to $0$). Then both parties locally define:
$$
\begin{align*}
\fL(X) &= \sum_{i=1}^t \mathbf{L_i} \cdot X^i \in \FF[X]^{\numGates} \\
\fR(X) &= \sum_{i=1}^{t} \mathbf{R_i} \cdot X^{t - i} \in \FF[X]^{\numGates} \\
g(X) &= \sum_{i = 0}^{2 \cdot t - 1} \delta_i \cdot X^i \in \FF[X]
\end{align*}
$$
1. Verifier samples $\x \sample \FF$
1. Both sides compute commitments to the vectors:
$$
\fL(x), \fR(x)\in \FF^{\numGates}
$$
And a commitment to the field element $g(x) \in \FF$, using the homomorphic property of the Pedersen commitments. We now have just a single inner product claim about Pedersen commitments:
$$
\ip{\fL(x)}{\fR(x)} = g(x)
$$
## GBP Arith 4: Combining
Recall the expression we were trying to verify,
before our digression about batching inner products and vector polynomials:
$$
\begin{align*}
0 &= \ip{\vy}{\aL \circ \aR} - \ip{\vy}{\aO} + \ip{\wL}{\aL} + \ip{\wR}{\aR} + \ip{\wO}{\aO} + \sum_{i=1}^{\numVecCom} \ip{\wCi{i}}{\aCi{i}} \\
&+ \ip{\wV}{\vv} + w_c \in \FF
\end{align*}
$$
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 $\aL \circ \aR$; 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 $\ip{\vy}{\aL \circ \aR}$ is public, so let us move one secret to each side, using $\ip{\vy}{\aL \circ \aR} = \ip{\aL}{\vy \circ \aR}$ to get rid of the Hadamard product between secret values:
$$
\begin{align*}
0 &= {\hl{\ip{\vy}{\aL \circ \aR}}} - \ip{\vy}{\aO} + \ip{\wL}{\aL} + \ip{\wR}{\aR} + \ip{\wO}{\aO} + \sum_{i=1}^{\numVecCom} \ip{\wCi{i}}{\aCi{i}} \\
&+ \ip{\wV}{\vv} + w_c \in \FF
\end{align*}
$$
Becomes
$$
\begin{align*}
0 &= {\hl{\ip{\aL}{\vy \circ \aR}}} - \ip{\vy}{\aO} + \ip{\wL}{\aL} + \ip{\wR}{\aR} + \ip{\wO}{\aO} + \sum_{i=1}^{\numVecCom} \ip{\wCi{i}}{\aCi{i}} \\
&+ \ip{\wV}{\vv} + w_c \in \FF
\end{align*}
$$
Note that we *know* how to deal with a Hadamard product between a secret and a public value.
#### Combine the $\aO$ terms
$$
\begin{align*}
0 &= \ip{\aL}{\vy \circ \aR} - {\hl{\ip{\vy}{\aO}}} + \ip{\wL}{\aL} + \ip{\wR}{\aR} + {\hl{\ip{\wO}{\aO}}} + \sum_{i=1}^{\numVecCom} \ip{\wCi{i}}{\aCi{i}} \\
&+ \ip{\wV}{\vv} + w_c \in \FF
\end{align*}
$$
$$
\begin{align*}
\delta(\y, \z) &= {\hl{\ip{\aL + \wR \circ \yinv}{\vy \circ \aR + \wL}}} + \ip{\wO - \vy}{\aO} + \sum_{i=1}^{\numVecCom} \ip{\wCi{i}}{\aCi{i}} \\
&+ \ip{\wV}{\vv} + w_c \in \FF
\end{align*}
$$
So we are left with $2 + \numVecCom$ inner products: two coming from the $\aL, \aR, \aO$ terms and one for each of the $\numVecCom$ committed vectors $\aCi{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 + \numVecCom$ inner products is known to the verifier: $\delta(\y, \z)$ (on the left) and $w_c$ are public, and $\ip{\wV}{\vv}$ is a commitment to a single field element, formed homomorphically from the $\comI{k}$. Those inner products are folded into a single one next.
## Arithmetization
Public inputs: generators $\bpG, \bpH \in \GG^{\numGates}$ and $\G, \H \in \GG$; weight matrices $\WL$, $\WR$, $\WO$, $\{\WCi{k}\}_{k=1}^{\numVecCom}$, $\WV$ with constant $\vc$; vector commitments $\{\ACi{k}\}_{k=1}^{\numVecCom}$ and scalar commitments $\{\comI{j}\}_{j=1}^{\numCom}$. Write $n' = 2\numVecCom + 2$ for the target monomial.
- **Prover $\to$ Verifier.**
- Sample $\alpha, \beta, \rho \sample \FF$ and $\nvec{s_L}, \nvec{s_R} \sample \FF^{\numGates}$.
- $\ALR = \ip{\aL}{\bpG} + \ip{\aR}{\bpH} + \alpha \H$
- $\AO = \ip{\aO}{\bpG} + \beta \H$
- $\S = \ip{\nvec{s_L}}{\bpG} + \ip{\nvec{s_R}}{\bpH} + \rho \H$
- Send $(\ALR, \AO, \S)$.
- **Verifier $\to$ Prover.**
- Sample $\y, \z \sample \FF^{*}$.
- Send $(\y, \z)$.
- Both parties compute:
- The challenge vectors $\vy, \yinv, \vz$
- The weights $\wL, \wR, \wO, \{\wCi{k}\}, \wV, w_c$
- $\delta(\y, \z) = \ip{\yinv \circ \wR}{\wL}$
- **Prover $\to$ Verifier.**
- Recall that the inner products to batch are:
$$
\begin{align*}
t_{n'} &=
\ip{\aL + \wR \circ \yinv}{\vy \circ \aR + \wL}
+ \ip{\aO}{\wO - \vy}
+ \sum_{k=1}^{\numVecCom} \ip{\aCi{k}}{\wCi{k}} \\
&= \delta(\y, \z) - w_c - \ip{\wV}{\vv}.
\end{align*}
$$
- Build $\fL(X), \fR(X) \in \FF[X]^{\numGates}$ (powers as in GBP Arith 3) with nonzero coefficients:
- $\fL(X)$:
- $\aL + \wR \circ \yinv$ at $X^{n'/2}$
- $\aCi{k}$ at $X^{n'-k}$ for $k = 1, \ldots, \numVecCom$
- $\aO$ at $X^{n'}$
- $\nvec{s_L}$ at $X^{n'+1}$
- $\fR(X)$:
- $\wO - \vy$ at $X^{0}$
- $\wCi{k}$ at $X^{k}$ for $k = 1, \ldots, \numVecCom$
- $\vy \circ \aR + \wL$ at $X^{n'/2}$
- $\vy \circ \aux{k}$ at $X^{n'-k}$ for $k = 1, \ldots, \numVecCom$
- $\vy \circ \nvec{s_R}$ at $X^{n'+1}$
- Corresponding to generators in $\bpG$ and $\bpH$ respectively.
- $t(X) = \ip{\fL(X)}{\fR(X)} = \sum_{i=n'/2}^{2(n'+1)} t_i X^i$; the target coefficient is $t_{n'}$.
- Sample $\tau_i \sample \FF$ for every $i \neq n'$ and set $T_i = t_i \G + \tau_i \H$.
- Send $\{T_i\}_{i \neq n'}$.
- **Verifier $\to$ Prover.**
- Sample $\x \sample \FF^{*}$.
- Send $\x$.
- **Prover $\to$ Verifier.**
- Opening of $t(\x)$ (value $\ht$, blinding $\taux$):
$$
\begin{align*}
\ht &= \ip{\fL(\x)}{\fR(\x)} = t(\x) \\
\taux &= \sum_{i \neq n'} \tau_i \x^{i} - \x^{n'} \ip{\wV}{\blind_V}
\end{align*}
$$
- Opening of $P$ (vectors $\fL(\x), \fR(\x)$, blinding $\mu$):
$$
\mu = \alpha \cdot \x^{n'/2} + \beta \cdot \x^{n'} + \rho \cdot \x^{n'+1} + \sum_{k=1}^{\numVecCom} \blind^{(k)} \cdot \x^{n'-k}
$$
With $\blind_V$ the blinding factors of the $\comI{j}$ and $\blind^{(k)}$ the blinding factor of $\ACi{k}$.
- Send $(\taux, \mu, \ht, \fL(\x) \in \FF^{\numGates}, \fR(\x) \in \FF^{\numGates})$.
- **Verifier.**
- Set $\bpH^{\yinv} = \yinv \circ \bpH$.
- Define:
$$
\begin{align*}
\Wt{L} &= \ip{\wL}{\bpH^{\yinv}} \in \GG
& \Wt{R} &= \ip{\yinv \circ \wR}{\bpG} \in \GG \\
\Wt{O} &= \ip{\wO - \vy}{\bpH^{\yinv}} \in \GG
& \Wt{k} &= \ip{\wCi{k}}{\bpH^{\yinv}} \in \GG
\end{align*}
$$
- Compute:
$$
P = \Wt{O} + \sum_{k=1}^{\numVecCom} \x^{k} \Wt{k} + \x^{n'/2}\!\left(\ALR + \Wt{L} + \Wt{R}\right) + \sum_{k=1}^{\numVecCom} \x^{n'-k} \ACi{k} + \x^{n'} \AO + \x^{n'+1} \S
$$
- Check:
$$
\ht\, \G + \taux \H = \x^{n'}\!\left(\left(\delta(\y, \z) - w_c\right)\G - \sum_{j=1}^{\numCom} (\wV)_j\, \comI{j}\right) + \sum_{i \neq n'} \x^{i} T_i
$$
- Check:
$$
\big((\bpG, \bpH^{\yinv}, \H, P, \mu, \ht),\ (\fL(\x), \fR(\x))\big) \in \RIP
$$
#### Computational Special Soundness
We prove that the arithmetization ('Generalized Bulletproofs') is an argument of knowledge for $\relation_{\mathsf{GBP}}$. The theorem below establishes $(\numGates, \numCons{+}1, 2n'{+}3)$-computational special soundness. By [Attema, Fehr and Klooß (TCC 2022)](https://eprint.iacr.org/2021/1377) the Fiat-Shamir compiled argument then has tight security: under the hardness of discrete log over $\GG$ it is knowledge sound with knowledge error at most $(\numQueries + 1) \cdot (\numGates + \numCons + 4\numVecCom + 5)/(|\FF| - 1)$, where $\numQueries$ is the number of random-oracle queries made by the adversary.
**Theorem.** *Assume $\WV$ has full column rank $\numCom$, i.e. a left inverse. The full arithmetization is $(\numGates, \numCons{+}1, 2n'{+}3)$-computationally special sound for $\relation_{\mathsf{GBP}}$: from any $(\numGates, \numCons{+}1, 2n'{+}3)$-tree of accepting transcripts a deterministic extractor returns either a witness for $\relation_{\mathsf{GBP}}$, or a non-trivial discrete-log relation among the generators $\Gamma = \bpG \concat \bpH \concat \G \concat \H \in \GG^{2\numGates+2}$, i.e. a non-zero $\nvec{v}$ with $\ip{\nvec{v}}{\Gamma} = 0$.*
**The Tree of Transcripts.** A $(\numGates, \numCons{+}1, 2n'{+}3)$-tree fixes the first message $(\ALR, \AO, \S)$ at the root and branches on the three challenges, recording each verifier message at its node: $\numGates$ distinct children on $\y$; under each, $\numCons{+}1$ distinct children on $\z$, each with its $\{T_i\}$; under each, $2n'{+}3$ distinct **leaves** on $\x$, each with its opening $(\taux, \mu, \fL(\x), \fR(\x))$. Every root-to-leaf path is an accepting transcript. Index a $(\y, \z)$-node by $(\iy, \iz)$ and its $\x$-leaves by $\ix$, so $(\iy, \iz, \ix)$ indexes a full transcript. The three arities are forced by the three interpolations below: $2n'{+}3 = \deg t + 1$ for $\x$; $\numCons{+}1$ for the $\numCons$ constraint rows together with the constant Hadamard term; $\numGates$ for the Hadamard coordinates.
The $(\numGates, \numCons{+}1, 2n'{+}3)$ tree of accepting transcripts: each edge is a verifier challenge ($\y$, then $\z$, then $\x$), and every root-to-leaf path is an accepting transcript (one highlighted).
**Step 1: $\x$-Vandermonde Read-off.** Fix a node $(\iy, \iz)$. The verifier's $P$ is the value at the leaf's challenge of a polynomial $\sum_{\xdeg=0}^{2(n'+1)} \x^{\xdeg} P_\xdeg$ whose coefficients $P_\xdeg \in \GG$ are:
$$
\begin{align*}
P_0 &= \Wt{O}, & P_k &= \Wt{k}\ (1 \le k \le \numVecCom), & P_{n'/2} &= \ALR + \Wt{L} + \Wt{R}, \\
P_{n'-k} &= \ACi{k}, & P_{n'} &= \AO, & P_{n'+1} &= \S,
\end{align*}
$$
With $P_\xdeg = \vzero$ for $\xdeg > n'{+}1$.
The $2n'{+}3$ leaves of the node share $(\y, \z)$ and use distinct $\x$, so the $P$-opening check at leaf $\ix$:
$$
\sum_{\xdeg} \x_{\ix}^{\xdeg}\, P_\xdeg = \ip{\fL(\x_{\ix})}{\bpG} + \ip{\fR(\x_{\ix})}{\bpH^{\yinv}} + \mu_{\ix} \H,
$$
Is a Vandermonde system in $\x$; inverting it writes each $P_\xdeg$ as a representation in the $(\bpG, \bpH^{\yinv}, \H)$ basis. When the node's collision candidates (Step 5) all vanish, the $\bpG$-block of $P_\xdeg$ at every degree equals the honest $\fL$ coefficient and the $\bpH^{\yinv}$-block at every degree $\neq n'$ equals the honest $\fR$ coefficient: the public degrees $0$ and $k$ open purely on $\bpH^{\yinv}$ to $\wO - \vy$ and $\wCi{k}$; degree $n'/2$ gives $\aL + \wR \circ \yinv$ on $\bpG$ and $\vy \circ \aR + \wL$ on $\bpH^{\yinv}$; degrees $n'{-}k$, $n'$, $n'{+}1$ give the wires $\aCi{k}, \aO, \nvec{s_L}$ on $\bpG$ and $\vy \circ \aux{k}, \vy \circ \nvec{s_R}$ on $\bpH^{\yinv}$. The lone degree-$n'$ $\bpH^{\yinv}$-block — the $\bpH$-part of $\AO$ — is unconstrained; the relation tolerates this slack, and since its convolution partner is the degree-$0$ coefficient of $\fL$, which is $\vzero$, it never contributes downstream.
**Step 2: The Per-Node Identity $(\star)$.** With the leaf openings pinned to the honest $\fL, \fR$, the $n'$-coefficient of $\ip{\fL(X)}{\fR(X)}$ — the committed target $t_{n'}$, recovered from the leaves by inverting the same $\x$-Vandermonde at degree $n'$ — expands *without invoking any constraint* into $\delta(\y, \z)$, the $\z$-aggregated linear $R1CS$ rows, and the $\y$-weighted Hadamard term $\ip{\vy}{\aL \circ \aR - \aO}$. The first verifier check independently pins the same coefficient to $t_{n'} = \delta(\y, \z) - w_c - \ip{\wV}{\vv}$; here the check couples $\ip{\wV}{\vv}$ to the aggregate $\sum_{j} (\wV)_j\, \comI{j}$ through its degree-$n'$ 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 $(\iy, \iz)$:
$$
(\star) \qquad \ip{\vy}{\aL \circ \aR - \aO} + \sum_{\row=1}^{\numCons} \z^{\row} \left( \WL\aL + \WR\aR + \WO\aO + \textstyle\sum_k \WCi{k}\aCi{k} + \WV\vv + \vc \right)_\row = 0
$$
**Step 3: Deaggregation over $\z$ then $\y$.** It suffices to know $(\star)$ on one reference row and one reference column. Fix a reference $\y$-child: as $\z$ ranges over the $\numCons{+}1$ children of that node, $(\star)$ is a degree-$\numCons$ polynomial in $\z$ — constant term $\ip{\vy}{\aL \circ \aR - \aO}$, row $\row$ at $\z^{\row}$ — vanishing at $\numCons{+}1$ distinct points, so a Vandermonde in $\z$ forces every $R1CS$ row to zero. With the rows gone, $(\star)$ on the reference column ($\z$ fixed to a reference child, $\y$ ranging over its $\numGates$ children) collapses to $\ip{\vy}{\aL \circ \aR - \aO} = 0$ at $\numGates$ distinct $\y$; a Vandermonde in $\y$ forces each coordinate. This yields the first two relation clauses:
$$
\begin{align*}
\WL\aL + \WR\aR + \WO\aO + \textstyle\sum_k \WCi{k}\aCi{k} + \WV\vv + \vc &= \vzero \\
\aL \circ \aR - \aO &= \vzero
\end{align*}
$$
(The $\numCons{+}1$ arity is the constant term plus $\numCons$ rows; the L-shape avoids needing $(\star)$ on the full $\numGates \cdot (\numCons{+}1)$ grid.)
**Step 4: Commitment Openings.** Two clauses remain, read straight off Step 1. The degree-$(n'{-}k)$ coefficient is $\ACi{k}$, whose $\bpG$-, $\bpH$- and $\H$-blocks give the *vector-commitment* clause:
$$
\ACi{k} = \ip{\aCi{k}}{\bpG} + \ip{\aux{k}}{\bpH} + \blind^{(k)} \H
$$
with the $\ip{\aux{k}}{\bpH}$ slack retained — precisely the term the improved protocol removes. For the *scalar* commitments, the first check's degree-$n'$ coefficient opens the aggregate $\sum_{j} (\wV)_j\, \comI{j}$ as a $(\G, \H)$-combination at each of the $\numCons{+}1$ $\z$-children; inverting the Vandermonde in $\z$ and applying the left inverse of $\WV$ recovers each $\comI{k} = v_k \G + \blind_k \H$.
**Step 5: Witness or Relation.** The extractor reads a candidate witness $\nvec{W}$ off the Step-1 representations at a fixed reference $(\y, \z)$ (the first $\y$- and $\z$-children): $\aL$ from the $\bpG$-block at degree $n'/2$ minus the public $\wR \circ \yinv$; $\aO$ at degree $n'$; $\aCi{k}$ and $\blind^{(k)}$ from the $\bpG$- and $\H$-blocks at degree $n'{-}k$; $\aR$ from the $\bpH^{\yinv}$-block at degree $n'/2$, minus the public $\wL$ and rescaled by $\yinv$; $\aux{k}$ from the $\bpH^{\yinv}$-block at degree $n'{-}k$, rescaled by $\yinv$; and $\vv, \{\blind_k\}$ from the degree-$n'$ first-check coefficients via the left inverse of $\WV$. It is computed by Lagrange-form Vandermonde inversion and Gaussian elimination — no discrete-log search. It also forms a list of candidate discrete-log relations: differences of two recovered representations of the same group element — the public coefficients $\Wt{O}, \Wt{k}$; the challenge-independent commitments $\ALR, \AO, \ACi{k}, \S$ across distinct nodes; the degree-$n'$ $(\G, \H)$-candidate of Step 2; and the high-degree coefficients, which open $\vzero$ directly. Each candidate $\nvec{c}$ satisfies $\ip{\nvec{c}}{\Gamma} = 0$ by construction, being a difference of two openings of the same commitment; it is *non-trivial* exactly when $\nvec{c} \neq \vzero$.
The extractor outputs $\nvec{W}$ if $\nvec{W} \in \relation_{\mathsf{GBP}}$, and otherwise the first non-zero candidate relation; we argue the contrapositive. If every candidate vanishes, the Step-1 read-offs hold and the degree-$n'$ identity of Step 2 holds at every node, so $(\star)$ holds on the reference row and column; Step 3 deaggregates it into the first two clauses, and Step 4 supplies the vector- and scalar-commitment clauses. All four clauses hold, so $\nvec{W} \in \relation_{\mathsf{GBP}}$, contradicting the assumption. Hence a failing $\nvec{W}$ yields a non-zero candidate, which the extractor returns as the discrete-log relation.
## Reduce $\RIP \to \RIPA{\numGates}$
The $\ht$ check above ties $\ht$ to the committed polynomial $t(X)$; the remaining verifier check is membership in a single inner-product relation $\RIP$, with statement $(\bpG, \bpH^{\yinv}, \H, P, \mu, \ht)$ and witness $(\nvec{a}, \nvec{b})$:
$$
\RIP = \left\{\ \big((\bpG, \bpH^{\yinv}, \H, P, \mu, \ht),\ (\nvec{a}, \nvec{b})\big) \ : \ P = \ip{\nvec{a}}{\bpG} + \ip{\nvec{b}}{\bpH^{\yinv}} + \mu \H \ \ \land \ \ \ht = \ip{\nvec{a}}{\nvec{b}} \ \right\}
$$
Here $\nvec{a}, \nvec{b} \in \FF^{\numGates}$ and $\bpH^{\yinv} = \yinv \circ \bpH$. The generators $\bpG, \bpH^{\yinv}, \H$ are public; the verifier derives the remaining statement components $P, \mu, \ht$ from the protocol transcript, and the prover holds the witness $(\nvec{a}, \nvec{b}) = (\fL(\x), \fR(\x))$. We abbreviate $\bpHt = \bpH^{\yinv}$.
To recursively fold this relation, we first want to reduce it to:
$$
\RIPA{\size} = \left\{\ \big((\bpG, \bpHt, U, P),\ (\nvec{a}, \nvec{b})\big) \ : \ \nvec{a}, \nvec{b} \in \FF^{\size} \ \ \land \ \ P = \ip{\nvec{a}}{\bpG} + \ip{\nvec{b}}{\bpHt} + \ip{\nvec{a}}{\nvec{b}} \cdot U \ \right\}
$$
The verifier samples a challenge $\chal_0 \sample \FF^{*}$; both parties set $U = \chal_0 \cdot \G$ (a generator independent of $\bpG, \bpHt$) and update the commitment:
$$
P \ \gets \ P - \mu \H + \ht \cdot U
$$
Subtracting $\mu \H$ removes the blinding term from the $\RIP$ commitment, and adding $\ht \cdot U$ encodes the claimed inner product in the $U$ component. Since $\ht = \ip{\nvec{a}}{\nvec{b}}$, the updated statement is an instance of $\RIPA{\numGates}$.
## Inner-Product Argument
The argument proves membership in $\RIPA{\size}$ on length-$\size$ vectors, initially $\size = \numGates$. In each round, the prover and verifier combine the left and right halves of each vector into vectors of half the length. After $\lceil \log_2 \numGates \rceil$ rounds, the prover has sent $2 \lceil \log_2 \numGates \rceil$ group elements and sends two final scalars.
#### Folding
Split each vector in half:
$$
\begin{align*}
\nvec{a} &= (\nvec{a}_1 \concat \nvec{a}_2) & \nvec{b} &= (\nvec{b}_1 \concat \nvec{b}_2) \\
\bpG &= (\bpG_1 \concat \bpG_2) & \bpHt &= (\bpHt_1 \concat \bpHt_2)
\end{align*}
$$
The prover sends the two cross terms:
$$
\begin{align*}
L &= \ip{\nvec{a}_1}{\bpG_2} + \ip{\nvec{b}_2}{\bpHt_1} + \ip{\nvec{a}_1}{\nvec{b}_2} \cdot U \\
R &= \ip{\nvec{a}_2}{\bpG_1} + \ip{\nvec{b}_1}{\bpHt_2} + \ip{\nvec{a}_2}{\nvec{b}_1} \cdot U
\end{align*}
$$
The verifier replies with a challenge $\chal \sample \FF^{*}$, and both sides fold the generators and statement to half length:
$$
\begin{align*}
\bpG' &= \chal^{-1} \cdot \bpG_1 + \chal \cdot \bpG_2 \\
\bpHt' &= \chal \cdot \bpHt_1 + \chal^{-1} \cdot \bpHt_2 \\
P' &= \chal^{2} \cdot L + P + \chal^{-2} \cdot R
\end{align*}
$$
While the prover folds the witness the same way:
$$
\begin{align*}
\nvec{a}' &= \chal \cdot \nvec{a}_1 + \chal^{-1} \cdot \nvec{a}_2 \\
\nvec{b}' &= \chal^{-1} \cdot \nvec{b}_1 + \chal \cdot \nvec{b}_2
\end{align*}
$$
A simple calculation shows the relation is preserved, $P' = \ip{\nvec{a}'}{\bpG'} +$ $\ip{\nvec{b}'}{\bpHt'} +$ $\ip{\nvec{a}'}{\nvec{b}'} \cdot U$. The folded statement and witness then form a smaller instance of the same relation, $\big((\bpG', \bpHt', U, P'), (\nvec{a}', \nvec{b}')\big) \in \RIPA{\size/2}$.
#### Base Case
After $\lceil \log_2 \numGates \rceil$ rounds the vectors have length one, leaving the base relation $\RIPA{1}$. The prover sends the two scalars $\nvec{a}, \nvec{b} \in \FF$, and the verifier accepts iff:
$$
P = \nvec{a} \cdot \bpG + \nvec{b} \cdot \bpHt + (\nvec{a} \cdot \nvec{b}) \cdot U
$$
The verifier never folds the generators one round at a time: the round challenges $\chal_1, \ldots, \chal_{\lceil \log_2 \numGates \rceil}$ assign each original generator a fixed coefficient (a product of the $\chal_j^{\pm 1}$), so the whole check collapses into a single multi-exponentiation, batched with the rest of verification.
# Improvements
We describe two improvements to the protocol above: a cheaper arithmetization, and an inversion-free inner-product argument with a tighter and simpler proof of computational special soundness.
## Arithmetization
Recall that the full arithmetization spreads $t(X)$ across degree $2(n'+1) = 4\numVecCom + 6$, so the prover commits to all $3\numVecCom + 5$ of its coefficients. Most of that degree is wasted: it exists only to park the two halves of $\ALR$ (and of $\S$) on a shared monomial, so that they can be jointly committed;
this is a bad 'optimization', that ends up hurting efficiency in the GBP setting.
If we give every vector its own monomial and $t(X)$ collapses to degree $2(\numVecCom + 2)$, the prover commits to $2\numVecCom + 4$ coefficients, a saving of $\numVecCom + 1$. We pay for this by splitting $\ALR$ into $(A_L, A_R)$ and $\S$ into $(S_L, S_R)$: two extra commitments, leaving a net saving of $\numVecCom - 1$ group elements. For 4 vector commitments the saving is 96 bytes: 3 fewer group elements.
The split buys something else: it tightens the relation. A vector commitment opens as:
$$
\ACi{k} = \ip{\aCi{k}}{\bpG} + \ip{\aux{k}}{\bpH} + \blind^{(k)} \H
$$
The $\ip{\aux{k}}{\bpH}$ term is slack the circuit cannot reach; the full arithmetization tolerates it, carrying it along in the $\vy \circ \aux{k}$ terms of $\fR(X)$. However, the improved protocol below can ensure that all those terms are zero. The verifier evaluates the $\bpG$- and $\bpH$-sides separately and recombines them with a binding challenge $\bind$, drawn after the evaluation point $\x$ and before the opening. The improved protocol then proves the tighter relation $\RGBPp$, identical to the generalized Bulletproofs relation except that the vector commitments carry no $\bpH$ component:
$$
\RGBPp = \left\{ \begin{array}{l}
\left(\aL, \aR, \aO, \vv, \{\aCi{i}, \blind^{(i)}\}_{i=1}^{\numVecCom}, \{\blind_k\}_{k=1}^{\numCom}\right) \ : \\
\vzero = \WL \cdot \aL + \WR \cdot \aR + \WO \cdot \aO + \sum_{i=1}^{\numVecCom} \WCi{i} \cdot \aCi{i} + \WV \cdot \vv + \vc \\
\vzero = \aL \circ \aR - \aO \\
\forall i.\ \ACi{i} = \ip{\aCi{i}}{\bpG} + \blind^{(i)} \cdot \H \\
\forall k.\ \comI{k} = v_k \cdot \G + \blind_k \cdot \H
\end{array} \right\}
$$
Public inputs are as in the arithmetization above; the target monomial is now $X^{\numVecCom+1}$.
- **Prover $\to$ Verifier.**
- Sample $\alpha_L, \alpha_R, \beta, \rho_L, \rho_R \sample \FF$ and $\nvec{s_L}, \nvec{s_R} \sample \FF^{\numGates}$.
- Commit:
$$
\begin{align*}
S_L &= \ip{\nvec{s_L}}{\bpG} + \rho_L \H
& S_R &= \ip{\nvec{s_R}}{\bpH} + \rho_R \H \\
A_L &= \ip{\aL}{\bpG} + \alpha_L \H
& A_R &= \ip{\aR}{\bpH} + \alpha_R \H \\
\AO &= \ip{\aO}{\bpG} + \beta \H
\end{align*}
$$
- Send $(A_L, A_R, \AO, S_L, S_R)$.
- **Verifier $\to$ Prover.**
- Sample $\y \sample \FF^{*}$ and $\z \sample \FF$.
- Send $(\y, \z)$.
- Both parties compute:
- The challenge vectors $\vy, \yinv, \vz$
- The weights $\wL, \wR, \wO, \{\wCi{k}\}, \wV, w_c$
- $\delta(\y, \z) = \ip{\yinv \circ \wR}{\wL}$
- **Prover $\to$ Verifier.**
- Recall that the inner products to batch are:
$$
\begin{align*}
t_{\numVecCom+1} &=
\ip{\aL + \wR \circ \yinv}{\vy \circ \aR + \wL}
+ \ip{\aO}{\wO - \vy}
+ \sum_{k=1}^{\numVecCom} \ip{\aCi{k}}{\wCi{k}} \\
&= \delta(\y, \z) - w_c - \ip{\wV}{\vv}.
\end{align*}
$$
- Build $\fL(X), \fR(X) \in \FF[X]^{\numGates}$ with nonzero coefficients:
- $\fL(X)$:
- $\aL + \wR \circ \yinv$ at $X^{0}$
- $\aO$ at $X^{1}$
- $\aCi{k}$ at $X^{k+1}$ for $k = 1, \ldots, \numVecCom$
- $\nvec{s_L} + \z^{\numCons+1} \cdot \nvec{1}$ at $X^{\numVecCom+2}$
- $\fR(X)$:
- $\wCi{k}$ at $X^{\numVecCom-k}$ for $k = 1, \ldots, \numVecCom$
- $\wO - \vy$ at $X^{\numVecCom}$
- $\vy \circ \aR + \wL$ at $X^{\numVecCom+1}$
- $\vy \circ \nvec{s_R}$ at $X^{\numVecCom+2}$
- Corresponding to generators in $\bpG$ and $\bpH$ respectively.
- $t(X) = \ip{\fL(X)}{\fR(X)} = \sum_{i=0}^{2(\numVecCom+2)} t_i X^i$; the target coefficient is $t_{\numVecCom+1}$.
- Sample $\tau_i \sample \FF$ for every $i \neq \numVecCom+1$ and set $T_i = t_i \G + \tau_i \H$.
- Send $\{T_i\}_{i \neq \numVecCom+1}$.
- **Verifier $\to$ Prover.**
- Sample $\x \sample \FF$, then $\bind \sample \FF^{*}$.
- Send $(\x, \bind)$.
- **Prover $\to$ Verifier.**
- Opening of $t(\x)$ (value $\ht$, blinding $\taux$):
$$
\begin{align*}
\ht &= \ip{\fL(\x)}{\fR(\x)} = t(\x) \\
\taux &= \sum_{i \neq \numVecCom+1} \tau_i \x^{i} - \x^{\numVecCom+1} \ip{\wV}{\blind_V}
\end{align*}
$$
- Opening of $P$ (vectors $\fL(\x), \fR(\x)$, blinding $\mu = \mu_L + \bind\,\mu_R$):
$$
\begin{align*}
\mu_L &= \alpha_L + \beta \x + \sum_{k=1}^{\numVecCom} \blind^{(k)} \x^{k+1} + \rho_L \x^{\numVecCom+2} \\
\mu_R &= \alpha_R \x^{\numVecCom+1} + \rho_R \x^{\numVecCom+2}
\end{align*}
$$
with $\blind_V$ the blinding factors of the $\comI{j}$ and $\blind^{(k)}$ the blinding factor of $\ACi{k}$.
- Send $(\taux, \ht, \mu, \fL(\x) \in \FF^{\numGates}, \fR(\x) \in \FF^{\numGates})$.
- **Verifier.**
- Set $\bpH^{\yinv} = \yinv \circ \bpH$.
- Define:
$$
\begin{align*}
\Wt{L} &= \ip{\wL}{\bpH^{\yinv}} \in \GG
& \Wt{R} &= \ip{\yinv \circ \wR}{\bpG} \in \GG \\
\Wt{O} &= \ip{\wO - \vy}{\bpH^{\yinv}} \in \GG
& \Wt{k} &= \ip{\wCi{k}}{\bpH^{\yinv}} \in \GG
\end{align*}
$$
- Compute:
$$
\begin{align*}
P &= \underbrace{\x^{0}\!\left(A_L + \Wt{R}\right) + \x^{1} \AO + \sum_{k=1}^{\numVecCom} \x^{k+1} \ACi{k} + \x^{\numVecCom+2}\!\left(S_L + \z^{\numCons+1} \cdot \ip{\nvec{1}}{\bpG}\right)}_{\ip{\fL(\x)}{\bpG} + \mu_L \H} \\ \\
&+ \bind \underbrace{\left( \sum_{k=1}^{\numVecCom} \x^{\numVecCom-k} \Wt{k} + \x^{\numVecCom} \Wt{O} + \x^{\numVecCom+1}\!\left(A_R + \Wt{L}\right) + \x^{\numVecCom+2} S_R \right)}_{\ip{\fR(\x)}{\bpH^{\yinv}} + \mu_R \H}
\end{align*}
$$
- Check:
$$
\ht\, \G + \taux \H = \x^{\numVecCom+1}\!\left(\left(\delta(\y, \z) - w_c\right)\G - \sum_{j=1}^{\numCom} (\wV)_j\, \comI{j}\right) + \sum_{i \neq \numVecCom+1} \x^{i} T_i
$$
- Check:
$$
\big((\bpG,\ \bind \cdot \bpH^{\yinv},\ \H,\ P,\ \mu,\ \ht),\ (\fL(\x), \fR(\x))\big) \in \RIP
$$
#### Computational Special Soundness
We prove that the protocol is an argument of knowledge for $\RGBPp$. The theorem below establishes $(\numGates, \numCons{+}2, 2\numVecCom{+}5, 3)$-computational special soundness; by [Attema, Fehr and Klooß (TCC 2022)](https://eprint.iacr.org/2021/1377) the Fiat-Shamir compiled argument then has tight security: under the hardness of discrete log over $\GG$ it is knowledge sound with knowledge error at most $(\numQueries + 1) \cdot (\numGates + \numCons + 2\numVecCom + 6)/(|\FF| - 1)$, where $\numQueries$ is the number of random-oracle queries.
**Theorem.** *Assume $\WV$ has full column rank $\numCom$, i.e. a left inverse. The improved arithmetization is $(\numGates, \numCons{+}2, 2\numVecCom{+}5, 3)$-computationally special sound for $\RGBPp$: from any $(\numGates, \numCons{+}2, 2\numVecCom{+}5, 3)$-tree of accepting transcripts a deterministic extractor returns either a witness for $\RGBPp$, or a non-trivial discrete-log relation among the generators $\Gamma = \bpG \concat \bpH \concat \G \concat \H \in \GG^{2\numGates+2}$, i.e. a non-zero $\nvec{v}$ with $\ip{\nvec{v}}{\Gamma} = 0$.*
**The Tree of Accepting Transcripts.** A $(\numGates, \numCons{+}2, 2\numVecCom{+}5, 3)$-tree fixes the first message $(A_L, A_R, \AO, S_L, S_R)$ at the root and branches on the four challenges, recording each verifier message at its node: $\numGates$ distinct children on $\y$; under each, $\numCons{+}2$ distinct children on $\z$, each with its $\{T_i\}$; under each, $2\numVecCom{+}5$ distinct children on $\x$; under each, $3$ distinct **leaves** on $\bind$. The opening $(\taux, \mu, \nvec{a}, \nvec{b}) = (\taux, \mu_L + \bind\,\mu_R, \fL(\x), \fR(\x))$ is the never-sent final message decorating the leaves; drawn after $\bind$, it may differ across the $\bind$-children. Every root-to-leaf path is an accepting transcript. Index a $(\y,\z,\x)$-node by $(\iy,\iz,\ix)$ and its $\bind$-leaves by $\leaf \in \{0,1,2\}$, with challenges $\bind_\leaf$ and leaf openings $(\tau_{x,\leaf}, \mu_\leaf, \nvec{a}_\leaf, \nvec{b}_\leaf)$. Write $P_L, P_R$ for the two bracketed sums of the verifier's $P$ (so $P = P_L + \bind P_R$) and $\bpH^{\yinv} = \yinv \circ \bpH$. The four arities are forced by the four interpolations below: $2\numVecCom{+}5 = \deg t + 1$ for $\x$; $\numCons{+}2$ for the constraints together with the fresh offset degree; $\numGates$ for the Hadamard rows; $3$ for the quadratic in $\bind$.
**Step 1: Interpolation in $\bind$.** Fix a node $(\iy,\iz,\ix)$. The second verifier check at leaf $\leaf$ reads:
$$
P_L + \bind_\leaf P_R = \ip{\nvec{a}_\leaf}{\bpG} + \bind_\leaf \ip{\nvec{b}_\leaf}{\bpH^{\yinv}} + \mu_\leaf \H
$$
with $\mu_\leaf$ the single blinding supplied at the leaf. The leaves $\leaf = 0, 1$ (with $\bind_0 \neq \bind_1$) form a $2 \times 2$ system whose unique solution pins both sides to four **quadrant** vectors and recovers the two blinders:
$$
\begin{align*}
P_L &= \ip{\nvec{a}^{\star}}{\bpG} + \ip{\nvec{\beta}}{\bpH^{\yinv}} + \mu_L \H \\
P_R &= \ip{\nvec{\alpha}}{\bpG} + \ip{\nvec{b}^{\star}}{\bpH^{\yinv}} + \mu_R \H
\end{align*}
$$
Where the quadrants are the interpolants:
$$
\begin{align*}
\nvec{a}^{\star} &= \frac{\bind_1 \nvec{a}_0 - \bind_0 \nvec{a}_1}{\bind_1 - \bind_0}
& \nvec{\beta} &= \frac{\bind_0\bind_1(\nvec{b}_0 - \nvec{b}_1)}{\bind_1 - \bind_0} \\
\nvec{\alpha} &= \frac{\nvec{a}_1 - \nvec{a}_0}{\bind_1 - \bind_0}
& \nvec{b}^{\star} &= \frac{\bind_1 \nvec{b}_1 - \bind_0 \nvec{b}_0}{\bind_1 - \bind_0}
\end{align*}
$$
And the blinding factors by the same interpolation, $\mu_L = \frac{\bind_1 \mu_0 - \bind_0 \mu_1}{\bind_1 - \bind_0}$ and $\mu_R = \frac{\mu_1 - \mu_0}{\bind_1 - \bind_0}$. Here $\nvec{\beta}$ is a $\bpH^{\yinv}$-mass sitting on the $\bpG$-side $P_L$, and $\nvec{\alpha}$ a $\bpG$-mass on the $\bpH$-side $P_R$. The opening is sent *after* $\bind$, so nothing yet forces $\nvec{\beta} = \nvec{\alpha} = \vzero$; this is the slack the offset must remove.
**Step 2: The $\ht$-Quadratic Forces the Cross Terms to Vanish.** On this family the $\leaf$-th leaf satisfies $\nvec{a}_\leaf = \nvec{a}^{\star} + \bind_\leaf \nvec{\alpha}$ and $\nvec{b}_\leaf = \bind_\leaf^{-1} \nvec{\beta} + \nvec{b}^{\star}$ (leaves $0, 1$ by construction; leaf $2$ either lies on the family — vectors and blinding alike — since its candidate below vanishes, or yields a relation). Hence:
$$
\ip{\nvec{a}_\leaf}{\nvec{b}_\leaf} = \ip{\nvec{a}^{\star}}{\nvec{\beta}} \bind_\leaf^{-1} + \bigl(\ip{\nvec{a}^{\star}}{\nvec{b}^{\star}} + \ip{\nvec{\alpha}}{\nvec{\beta}}\bigr) + \ip{\nvec{\alpha}}{\nvec{b}^{\star}} \bind_\leaf
$$
The *first* check at leaf $\leaf$ reads $\ip{\nvec{a}_\leaf}{\nvec{b}_\leaf}\,\G + \tau_{x,\leaf}\,\H = R$, with right-hand side $R = \sum_{i \neq \numVecCom+1}\x^i T_i + \x^{\numVecCom+1}\!\big((\delta(\y,\z) - w_c)\G - \sum_j (\wV)_j \comI{j}\big)$ determined before $\bind$ is drawn. Subtracting the leaf-$0$ instance, $\bigl(\ip{\nvec{a}_\leaf}{\nvec{b}_\leaf} - \ip{\nvec{a}_0}{\nvec{b}_0}\bigr)\G + (\tau_{x,\leaf} - \tau_{x,0})\H = 0$ is a discrete-log relation on $(\G, \H)$; unless it is trivial — both $\ip{\nvec{a}_\leaf}{\nvec{b}_\leaf}$ and $\tau_{x,\leaf}$ constant across the $\bind$-children — the extractor returns it. With $\ip{\nvec{a}_\leaf}{\nvec{b}_\leaf}$ pinned to a single value, a map $\bind \mapsto A \bind^{-1} + C + B \bind$ constant at the three distinct non-zero $\bind_0, \bind_1, \bind_2$ has $A = B = 0$; hence at every node:
$$
\ip{\nvec{a}^{\star}}{\nvec{\beta}} = 0, \qquad \ip{\nvec{\alpha}}{\nvec{b}^{\star}} = 0, \qquad \ip{\nvec{a}_\leaf}{\nvec{b}_\leaf} = \ip{\nvec{a}^{\star}}{\nvec{b}^{\star}} + \ip{\nvec{\alpha}}{\nvec{\beta}}
$$
Forcing both the $\bind^{-1}$- and $\bind$-terms to vanish requires three points, which fixes the $\bind$-arity at $3$.
**Step 3: $\x$-Vandermonde Extraction.** Fix $\y$ and $\z$. Across the $2\numVecCom{+}5$ accepting transcripts that share them and use distinct $\x$, each quadrant is the evaluation at $\x_{\ix}$ of a vector polynomial of degree $\le 2\numVecCom{+}4$ whose coefficients are the per-degree representations of $P_L(X)$ and $P_R(X)$. Inverting the Vandermonde in $\x$ recovers, for each degree $\xdeg$, a representation in three blocks:
$$
[\text{coeff}_\xdeg\, P_L] = \ip{\nvec{g}_\xdeg}{\bpG} + \ip{\nvec{h}_\xdeg}{\bpH^{\yinv}} + \eta_\xdeg \H
$$
And likewise for $P_R$. Matching the layout of $\fL$, the $\bpG$-blocks at degrees $0, 1, k{+}1, \numVecCom{+}2$ are $\aL + \wR\circ\yinv$, $\aO$, $\aCi{k}$, and $\nvec{s_L} + \z^{\numCons+1} \cdot \nvec{1}$ (the mask *with* offset); the $\bpH^{\yinv}$-blocks are the residual components $\nvec{\beta}$ at each degree.
**Step 4: The Offset Eliminates the Residual Components.** The residual $\bpH^{\yinv}$-block of each $P_L$-coefficient is the *same* fixed vector $\nvec{w}_\xdeg$ for every $(\y,\z)$ (up to the $\vy$-rescaling), a property of the fixed commitments $A_L, \AO, \ACi{k}, S_L$. We show every $\nvec{w}_\xdeg = \vzero$ by descending induction on $\xdeg$, from $\numVecCom{+}2$ down.
Step 2 gives $\ip{\nvec{a}^{\star}(\x)}{\nvec{\beta}(\x)} = 0$ at every $\x$-child; interpolating across the $2\numVecCom{+}5$ points, every convolution coefficient of the two degree-$(\numVecCom{+}2)$ quadrant polynomials vanishes. Take the coefficient at convolution degree $\xdeg_0 + \numVecCom + 2$. With the higher-degree residual components already zero by the induction hypothesis, the only nonzero term pairs the $\bpG$-block of the mask slot $\numVecCom{+}2$ with $\nvec{w}_{\xdeg_0}$; that block is $\nvec{u} + \z^{\numCons+1} \cdot \nvec{1}$, with $\nvec{u}$ the fixed representation of $S_L$, so the coefficient is:
$$
\ip{\nvec{u}}{\vy \circ \nvec{w}_{\xdeg_0}} + \z^{\numCons+1} \sum_{t} y^{t} (\nvec{w}_{\xdeg_0})_t = 0
$$
Fix $\y$. The summand $D = \ip{\nvec{u}}{\vy \circ \nvec{w}_{\xdeg_0}}$ and the coefficient $B = \sum_t y^t (\nvec{w}_{\xdeg_0})_t$ are independent of $\z$: the weights live at $\z^1, \ldots, \z^{\numCons}$, and $\nvec{u}$ is fixed before $\z$. The term $\z^{\numCons+1} B$ carries the fresh power, so $D + \z^{\numCons+1} B$ is a polynomial vanishing at the $\numCons{+}2$ distinct $\z$, and full-degree Vandermonde forces $B = 0$. (Pairwise differences would *not* suffice: distinct $\z$ can share a $(\numCons{+}1)$-th power, which is why the $\z$-arity is $\numCons{+}2$, not $\numCons{+}1$.) Finally $\sum_t y^t (\nvec{w}_{\xdeg_0})_t = 0$ across the $\numGates$ distinct $\y$ is a Vandermonde in $y$, so $\nvec{w}_{\xdeg_0} = \vzero$ coordinate-wise.
Since every $\nvec{w}_\xdeg = \vzero$, the residual quadrant $\nvec{\beta}$ vanishes at every node, and each leaf's inner product equals the honest convolution $\ip{\nvec{a}^{\star}}{\nvec{b}^{\star}}$.
**Step 5: Witness or Relation.** The extractor reads a candidate witness $\nvec{W}$ off the Step-3 representations at a fixed reference $(\y,\z)$ (the first $\y$- and $\z$-children): $\aL$ from the $\bpG$-block of $P_L$ at degree $0$, minus the public $\wR\circ\yinv$; $\aO$ at degree $1$; $\aCi{k}$ and its blinder $\blind^{(k)}$ from the $\bpG$- and $\H$-blocks of $P_L$ at degree $k{+}1$; $\aR$ from the $\bpH^{\yinv}$-block of $P_R$ at degree $\numVecCom{+}1$, minus the public $\wL$ and rescaled by $\yinv$; and $\vv, \{\blind_k\}$ from the first check's degree-$(\numVecCom{+}1)$ coefficient across the first $\numCons{+}1$ $\z$-children, via the precomputed left inverse of $\WV$. It also forms a list of candidate discrete-log relations: differences of two recovered representations of the same group element, e.g. the representation of $A_L$ at $(\y_{\iy},\z_{\iz})$ minus the one at the reference $(\y_0,\z_0)$, the high-degree coefficients, and the per-node consistency checks — the third $\bind$-child's opening and blinding against the family interpolated from the first two (Step 1), and the agreement of $\bigl(\ip{\nvec{a}_\leaf}{\nvec{b}_\leaf}, \tau_{x,\leaf}\bigr)$ across the $\bind$-children (Step 2). Each candidate $\nvec{c}$ satisfies $\ip{\nvec{c}}{\Gamma} = 0$ by construction, being the difference of two representations of the same commitment; it is therefore a discrete-log relation, *non-trivial* exactly when $\nvec{c} \neq \vzero$.
The extractor outputs $\nvec{W}$ if $\nvec{W} \in \RGBPp$, and otherwise the first non-zero candidate relation; we argue the contrapositive. If every candidate vanishes, the Step-3 representations and the per-node identities of Step 2 hold, and the residual components are pinned to the single family $\nvec{w}_\xdeg$, so Step 4 forces every $\nvec{w}_\xdeg$ to zero. With the leaf openings now honest, cancelling $\delta$ in the first-check identity $t_{\numVecCom+1} = \delta(\y,\z) - w_c - \ip{\wV}{\vv}$ gives, for each $(\y,\z)$:
$$
\ip{\vy}{\aL \circ \aR - \aO} + \sum_{\row=1}^{\numCons} \z^{\row} \bigl(\WL\aL + \WR\aR + \WO\aO + \textstyle\sum_k \WCi{k}\aCi{k} + \WV\vv + \vc\bigr)_\row = 0
$$
Deaggregating over the $\numGates$ distinct $\y$ and the $\numCons{+}1$ distinct $\z$ (two Vandermondes) splits this into the first two relation clauses:
$$
\WL\aL + \WR\aR + \WO\aO + \textstyle\sum_k \WCi{k}\aCi{k} + \WV\vv + \vc = \vzero, \qquad \aL \circ \aR - \aO = \vzero
$$
The vector-commitment clause is *tight*: since the residual components vanish, the degree-$(k{+}1)$ $\bpG$-block representation gives $\ACi{k} = \ip{\aCi{k}}{\bpG} + \blind^{(k)}\H$, with no $\bpH$-component. The scalar clause $\comI{k} = v_k\G + \blind_k\H$ follows from the degree-$(\numVecCom{+}1)$ recovery and the $\WV$ left inverse. All four clauses hold, so $\nvec{W} \in \RGBPp$, contradicting the assumption. Hence a failing $\nvec{W}$ yields a non-zero candidate, which the extractor returns as the discrete-log relation.
## Inner-Product Argument
The improved arithmetization reduces to the same inner-product relation $\RIP$, so it can reuse the inner-product argument above. Folding in the value yields the same relation $\RIPA{\size}$, and the base case is unchanged; we change only the folding round, replacing the Laurent fold with a *polynomial* fold. This removes every field inversion.
#### Folding
Split each vector in half:
$$
\begin{align*}
\nvec{a} &= (\nvec{a}_1 \concat \nvec{a}_2) & \nvec{b} &= (\nvec{b}_1 \concat \nvec{b}_2) \\
\bpG &= (\bpG_1 \concat \bpG_2) & \bpHt &= (\bpHt_1 \concat \bpHt_2)
\end{align*}
$$
The prover sends the two cross terms:
$$
\begin{align*}
L &= \ip{\nvec{a}_1}{\bpG_2} + \ip{\nvec{b}_2}{\bpHt_1} + \ip{\nvec{a}_1}{\nvec{b}_2} \cdot U \\
R &= \ip{\nvec{a}_2}{\bpG_1} + \ip{\nvec{b}_1}{\bpHt_2} + \ip{\nvec{a}_2}{\nvec{b}_1} \cdot U
\end{align*}
$$
The verifier replies with a challenge $\chal \sample \FF$, and both sides fold the generators and statement to half length:
$$
\begin{align*}
\bpG' &= \bpG_1 + \chal \cdot \bpG_2 \\
\bpHt' &= \chal \cdot \bpHt_1 + \bpHt_2 \\
P' &= \chal^{2} \cdot L + \chal \cdot P + R
\end{align*}
$$
While the prover folds the witness the same way:
$$
\begin{align*}
\nvec{a}' &= \chal \cdot \nvec{a}_1 + \nvec{a}_2 \\
\nvec{b}' &= \nvec{b}_1 + \chal \cdot \nvec{b}_2
\end{align*}
$$
A simple calculation shows the relation is preserved, $P' = \ip{\nvec{a}'}{\bpG'} +$ $\ip{\nvec{b}'}{\bpHt'} +$ $\ip{\nvec{a}'}{\nvec{b}'} \cdot U$. The folded statement and witness then form a smaller instance of the same relation, $\big((\bpG', \bpHt', U, P'), (\nvec{a}', \nvec{b}')\big) \in \RIPA{\size/2}$. Observe that, unlike the original version, the field element $\chal$ may take any value in $\FF$.
#### Base Case
After $\lceil \log_2 \numGates \rceil$ rounds the vectors have length one, leaving the base relation $\RIPA{1}$. The prover sends the two scalars $\nvec{a}, \nvec{b} \in \FF$, and the verifier accepts iff:
$$
P = \nvec{a} \cdot \bpG + \nvec{b} \cdot \bpHt + (\nvec{a} \cdot \nvec{b}) \cdot U
$$
## Findings
### Repeated `LinComb` Additions Can Grow the Sparse Weight Vectors Exponentially
- **Severity**: Low
- **Location**: generalized-bulletproofs/src/lincomb.rs
**Description**. `LinComb` stores its weights in sparse vectors (`WL`, `WR`, `WO`, `WV`) and a sparse map (`WCG`).
Addition concatenates the operand's entries onto these vectors rather than coalescing terms that share an index.
```rust
fn add(mut self, constraint: &Self) -> Self {
self.reconcile_for_merging(constraint);
self.WL.extend(&constraint.WL);
self.WR.extend(&constraint.WR);
self.WO.extend(&constraint.WO);
for (i, sparse_vec) in &constraint.WCG {
self
.WCG
.entry(*i)
.and_modify(|existing| existing.extend(sparse_vec))
.or_insert_with(|| sparse_vec.clone());
}
self.WV.extend(&constraint.WV);
self.c += constraint.c;
self
}
```
Observe that the size of the result is the sum of the sizes of the operands.
Adding a combination to itself doubles its length, so a loop that repeatedly accumulates a combination into itself grows the stored representation
exponentially in the number of iterations.
```rust
for _ in 0 .. n {
a = a + &a;
}
```
After `n` iterations the `WL`/`WR`/`WO`/`WV` vectors hold on the order of $2^n$ entries,
even though the combination is mathematically equivalent to a far smaller one.
**Impact**. This does not affect correctness or soundness; duplicated entries are accumulated additively when the constraint is evaluated, so the result is unchanged.
It's a potential denial of service concern *if* the library is used in a setting where the adversary can cause the verifier to try and verify a circuit of this form.
**Recommendation**. If linear combinations are built from programmatic or untrusted inputs,
coalesce terms sharing an index during `add`/`sub`, or document that the sparse representation is not reduced and that callers
should make sure that the constructed circuit does not trigger this behavior.
### Commitment Has Secret-Dependent Memory Access Patterns
- **Severity**: Low
- **Location**: generalized-bulletproofs/src/arithmetic_circuit_proof.rs
**Description**. The prover forms its commitments $A_I$, $A_O$, and $S$ with the constant-time `multiexp` over witness-derived scalars (`aL`, `aR`, `aO`, the blinding vectors `sL`, `sR`, and the masks `alpha`, `beta`, `rho`).
```rust
let AI = {
let alg = witness.aL.0.iter().enumerate().map(|(i, aL)| (*aL, self.generators.g_bold(i)));
let arh = witness.aR.0.iter().enumerate().map(|(i, aR)| (*aR, self.generators.h_bold(i)));
let ah = core::iter::once((alpha, self.generators.h()));
let mut AI_terms = alg.chain(arh).chain(ah).collect::>();
let AI = multiexp(&AI_terms);
AI_terms.zeroize();
AI
};
```
`multiexp` is the constant-time variant, but it is not constant time with respect to the scalars in the sense needed to hide the witness. It uses Pippenger's algorithm, whose bucket accumulation indexes memory using bits of the secret scalars. Memory accesses are not constant time in general, so the access pattern leaks information about the scalars and cache attacks such as flush-and-reload apply. A scan over all buckets would close this, but that is not what the algorithm does.
The issue is in the upstream `multiexp` dependency used by the `generalized-bulletproofs` library. The upstream project has already fixed the issue, but the fixed version has not yet been published to `crates.io`.
**Impact**. This is not a verifier-soundness issue and is not exploitable from the proof bytes. It is a local side-channel risk: an attacker who can observe the prover's memory access pattern, e.g. a co-tenant on the same machine, can learn information about the witness scalars. Whether this matters depends on whether the proofs are used in a witness-hiding setting and on the prover's execution environment.
**Recommendation**. Document that proof generation assumes no local microarchitectural side-channel adversary and that witness privacy is out of scope for that environment, or update to the fixed upstream `multiexp` version once it is available.
### Secret Data Not Zeroized After Vector Reallocation
- **Severity**: Low
- **Location**: generalized-bulletproofs/src/lib.rs
**Description**. `PedersenVectorCommitment::commit` builds the input to `multiexp` in a temporary `terms` vector. The vector contains `self.mask` and the committed witness values from `self.g_values`.
```rust
impl PedersenVectorCommitment {
/// Commit to the vectors of values.
///
/// This function returns `None` if the amount of generators is less than the amount of values
/// within the relevant vector.
pub fn commit(&self, g_bold: &[C::G], h: C::G) -> Option
where
C::G: ConditionallySelectable,
{
if g_bold.len() < self.g_values.len() {
None?;
}
let mut terms = vec![(self.mask, h)];
for pair in self.g_values.iter().copied().zip(g_bold.iter().copied()) {
terms.push(pair);
}
let res = multiexp(&terms);
terms.zeroize();
Some(res)
}
}
```
The `terms` vector is initialized with one element and then extended in the loop. Since the vector does not reserve space for all entries upfront, pushing witness pairs can force one or more reallocations. During a reallocation, Rust allocates a larger buffer, copies the existing elements into the new buffer, and releases the previous buffer. The old allocation is not zeroized before being released back to the allocator.
As a result, stale copies of `self.mask` and earlier `self.g_values` entries may remain in freed heap memory even though the final `terms` allocation is zeroized after `multiexp` returns. The explicit `terms.zeroize()` call is therefore incomplete for copies created by vector growth.
**Impact**. This does not affect the correctness, soundness, or hiding properties of the commitment scheme. It is a local secret-handling issue: witness scalars may remain in process memory longer than intended and could be recovered only if an attacker can read freed heap memory, inspect a memory dump, or otherwise obtain process memory. Zeroization is a best effort with Rust zeroize library, and the compiler or runtime may introduce other copies outside this function, but the vector reallocation pattern is a concrete and avoidable source of stale witness data.
**Recommendation**. It is recommended to pre-allocate enough space for `terms` before pushing witness values, so the vector does not reallocate during construction.
```rust
pub fn commit(&self, g_bold: &[C::G], h: C::G) -> Option
where
C::G: ConditionallySelectable,
{
if g_bold.len() < self.g_values.len() {
None?;
}
let mut terms = Vec::with_capacity(self.g_values.len() + 1);
terms.push((self.mask, h));
for pair in self.g_values.iter().copied().zip(g_bold.iter().copied()) {
terms.push(pair);
}
let res = multiexp(&terms);
terms.zeroize();
Some(res)
}
```
### Scalar Commitment Are Not Extractable for Rank-Deficient `W_V`
- **Severity**: Low
- **Location**: generalized-bulletproofs/src/arithmetic_circuit_proof.rs
**Description**. The fixed Generalized Bulletproofs relation treats the scalar-commitment weight matrix `W_V` as having full column rank, so each scalar commitment $V_k = v_k \cdot G + \gamma_k \cdot H$ is individually bound by the constraints. `ArithmeticCircuitStatement::new` does not enforce this; it only checks that the indices referenced by each constraint are in bounds.
```rust
for constraint in &constraints {
if Some(generators.len()) <= constraint.highest_a_index {
Err(AcStatementError::ConstrainedNonExistentTerm)?;
}
if Some(C.len()) <= constraint.highest_c_index {
Err(AcStatementError::ConstrainedNonExistentVectorCommitment)?;
}
if Some(V.len()) <= constraint.highest_v_index {
Err(AcStatementError::ConstrainedNonExistentCommitment)?;
}
}
```
Both the prover and the verifier access the scalar commitments only through the `z`-aggregated combination of the `W_V` rows, so the proof binds the single combination $\mathbf{z}^\top W_V \cdot \mathbf{V}$ rather than the individual commitments $V_k$.
Observe that if `W_V` is not full column rank, any commitment in the right kernel of `W_V` is invisible to the verifier. The only code that checks each witness opening against its public commitment is gated behind `#[cfg(debug_assertions)]`, so a release build does not catch a bogus opening for such a commitment.
This is a known restriction inherited from the original Bulletproofs relation, not specific to this implementation: a rank-deficient `W_V` binds only a linear combination of the commitments, so the individual openings cannot be extracted.
Consider two public commitments $V_1 = v_1 G + \gamma_1 H$ and $V_2 = v_2 G + \gamma_2 H$, with a single constraint asserting their values sum to some target, $v_1 + v_2 = v_3$. The weight row over $(V_1, V_2)$ is $\left[\,1, 1\,\right]$: rank one for two commitments, so $Q = 1 < m = 2$. The proof binds only $v_1 + v_2$ and $\gamma_1 + \gamma_2$, which is the opening of the sum $V_1 + V_2$; it says nothing about $V_1$ and $V_2$ individually.
A prover therefore need not know either opening. Pick $V_1$ to be an arbitrary point with no known opening, then set $V_2 = \left( v_3 G + \gamma_3 H \right) - V_1$ for a chosen opening $(v_3, \gamma_3)$. Now $V_1 + V_2 = v_3 G + \gamma_3 H$, so the prover proves $v_1 + v_2 = v_3$ from the opening of the sum alone, while knowing no opening of $V_1$ or $V_2$. The right kernel of `W_V` is spanned by $(1, -1)$: the prover can slide value and mask freely between the two commitments, including pushing $V_1$ onto a point it cannot open.
The extreme case is a self-cancelling column. The degenerate constraint `V(0) - V(0) = 0` zeroes the entire column for that commitment, dropping it from every verifier equation; since the per-opening check is `#[cfg(debug_assertions)]`-gated, a release build then accepts a proof whose witness does not open the public commitment at all.
**Impact**. This is a defense-in-depth issue at the statement-construction boundary; it does not affect a caller using fixed, full-rank constraints. An integration that passes externally supplied Pedersen commitments in `V` and relies on the proof to establish knowledge of each opening, without itself ensuring `W_V` has full column rank, does not get that guarantee: the extractor cannot recover the openings of commitments outside the column span of `W_V`.
In particular, such a proof cannot stand in for a Schnorr-style proof of knowledge of a commitment opening, for example to spend a commitment by proving the prover can open it. When `W_V` is rank-deficient the proof establishes knowledge of an aggregate opening only, not of the individual commitments the application believes were proven.
**Recommendation**. If `ArithmeticCircuitStatement::new` does not enforce that `W_V` has full column rank, this limitation must be documented clearly: the proof binds only the aggregated combination $W_V \cdot \mathbf{V}$, not the individual scalar commitment openings. Callers that rely on per-commitment binding, for example to prove knowledge of a commitment opening, must ensure `W_V` has full column rank themselves.
### Generator Validation for `g` Is Skipped in Release Builds
- **Severity**: Informational
- **Location**: generalized-bulletproofs/src/lib.rs
**Description**. `Generators::new` uses a local `add_generator` helper to reject identity points and track duplicate generators.
```rust
let mut set = HashSet::new();
let mut add_generator = |generator: &C::G| {
if bool::from(generator.is_identity()) {
return Err(GeneratorsError::IdentityPoint);
}
let bytes = generator.to_bytes();
Ok(!set.insert(bytes.as_ref().to_vec()))
};
debug_assert!(!add_generator(&g)?, "g was prior present in empty set");
if add_generator(&h)? {
Err(GeneratorsError::DuplicatedGenerator)?;
}
```
The call to `add_generator(&g)?` is placed inside `debug_assert!`. In release builds, `debug_assert!` expressions are compiled out, so this call is not evaluated. As a result, `g` is not checked for being the identity and is not inserted into the duplicate-detection set.
The following checks still validate `h`, `g_bold`, and `h_bold`, but they no longer compare those generators against `g` in release builds because `g` was never inserted into `set`. This makes the production validation weaker than the validation performed in debug builds.
**Impact**. Invalid generator sets involving `g` can be accepted in release builds even though they would be rejected in debug builds. The practical impact depends on how the library is integrated and whether generator inputs can be influenced by an untrusted party. At minimum, this creates a configuration validation mismatch.
**Recommendation**. Evaluate `add_generator(&g)?` unconditionally and return a normal error instead of relying on `debug_assert!`.
```rust
if add_generator(&g)? {
Err(GeneratorsError::DuplicatedGenerator)?;
}
```
The duplicate and identity checks are best-effort validation. They do not prove that the accepted bases are independently generated, or that no party knows discrete-log relations between them. It is recommended to document `Generators::new` as accepting only already-trusted independent bases, with these checks serving as additional defensive validation.
### Inner Product Prover Accepts Generator Vectors With Non-Canonical Length
- **Severity**: Informational
- **Location**: generalized-bulletproofs/src/inner_product.rs
**Description**. `IpStatement::prove` checks that the prover has at least enough generators for the witness length rounded up to the next power of two.
```rust
// Ensure we have the necessary amount of generators
if witness.a.len() > ((usize::MAX >> 1) + 1) {
Err(IpProveError::IncorrectAmountOfGenerators)?;
}
if generators.g_bold_slice().len() < witness.a.len().next_power_of_two() {
Err(IpProveError::IncorrectAmountOfGenerators)?;
}
```
This permits `generators.g_bold_slice().len()` to be larger than `witness.a.len().next_power_of_two()`. However, the folding loop later treats `g_bold.len()` as the inner product dimension, while it splits the witness vectors using `a.len().next_power_of_two() / 2`.
```rust
// This interprets `g_bold.len()` as `n`
while g_bold.len() > 1 {
// Split a, b, g_bold, h_bold as needed for lines 20-24
let split_at = a.len().next_power_of_two() / 2;
let (a1, a2) = a.split(split_at);
let (b1, b2) = b.split(split_at);
let (g_bold1, g_bold2) = g_bold.split();
let (h_bold1, h_bold2) = h_bold.split();
let n_hat = g_bold1.len();
// Sanity
debug_assert_eq!(a1.len(), n_hat);
debug_assert!(a2.len() <= n_hat);
debug_assert_eq!(b1.len(), n_hat);
debug_assert!(b2.len() <= n_hat);
debug_assert_eq!(g_bold1.len(), n_hat);
debug_assert_eq!(g_bold2.len(), n_hat);
debug_assert_eq!(h_bold1.len(), n_hat);
debug_assert_eq!(h_bold2.len(), n_hat);
[...]
}
```
The debug assertions show that the intended invariant is stronger than the initial check: the generator vector length should match the padded witness length. If extra generators are accepted, the witness vectors and generator vectors can be folded under different dimensions. In release builds, the debug assertions are not enforced.
**Impact**. This is an input validation issue in the prover. Under the expected canonical parameters, where the generator vector length equals the padded witness length, there is no impact. If `prove` is called with an oversized generator vector, it can operate on inconsistent dimensions and may produce an invalid proof or fail later in the folding process instead of returning `IpProveError::IncorrectAmountOfGenerators` at the boundary.
**Recommendation**. It is recommended to require the generator vector length to be exactly `witness.a.len().next_power_of_two()` before entering the folding loop.
```rust
if generators.g_bold_slice().len() != witness.a.len().next_power_of_two() {
Err(IpProveError::IncorrectAmountOfGenerators)?;
}
```
### Vector Commitment Tail Coordinates Are Unconstrained Unless Explicitly Restricted
- **Severity**: Informational
- **Location**: crypto/generalized-bulletproofs/src/lib.rs
**Description**. In the generalized Bulletproof construction, vector commitments are expressed over the same `G_bold` and `H_bold` generator vectors used by the proof. The length of these generator vectors is tied to the proof dimension, which is derived from the number of gates and padded to a power of two for the inner product argument.
This proof dimension can be larger than the logical vector length used by an application. For example, an application may intend to commit to a vector of length 3, while the generalized Bulletproof instance uses 4 generators after power-of-two padding.
The vector commitment API accepts an opening as long as there are enough generators for the provided values.
```rust
pub fn commit(&self, g_bold: &[C::G], h: C::G) -> Option
where
C::G: ConditionallySelectable,
{
if g_bold.len() < self.g_values.len() {
None?;
}
let mut terms = vec![(self.mask, h)];
for pair in self.g_values.iter().copied().zip(g_bold.iter().copied()) {
terms.push(pair);
}
let res = multiexp(&terms);
terms.zeroize();
Some(res)
}
```
The generalized Bulletproof circuit then constrains only the coordinates that appear in the arithmetic constraints. This is expected for the `H_bold` part of the vector commitment, which represents auxiliary opening data that is not accessible from the circuit. However, the same issue can affect the `G_bold` part when the proof dimension is larger than the application's intended vector length: tail coordinates past the logical vector length are not forced to be zero by default.
As a result, an application that reasons about only a fixed prefix of the vector commitment must ensure that every unused `G_bold` coordinate is either absent from the opening or explicitly constrained to zero. Otherwise, a prover can use non-zero values in the padded tail while still satisfying all constraints over the intended prefix.
**Impact**. This is an integration-level soundness concern. The proof remains valid for the generalized Bulletproof relation that was actually encoded, but that relation may be wider than the application intended. If an application treats a vector commitment as an exact-length commitment and does not constrain padded tail coordinates, the commitment can contain additional non-zero data outside the checked prefix.
**Recommendation**. It is recommended to document that generalized Bulletproof vector commitments are over the proof dimension, not necessarily the application-level vector length, and that callers are responsible for constraining unused tail coordinates.
Is is also recommended to make the logical vector length explicit wherever vector commitments are used in generalized Bulletproof statements. For exact-length vectors, add constraints forcing every padded `G_bold` coordinate beyond the logical length to be zero, or provide an API helper that automatically inserts these constraints.
---
This report was published on the [zkSecurity Audit Reports](https://reports.zksecurity.xyz) site by [ZK Security](https://www.zksecurity.xyz), a leading security firm specialized in zero-knowledge proofs, MPC, FHE, and advanced cryptography. For the full list of audit reports, see [llms.txt](https://reports.zksecurity.xyz/llms.txt).