Comparing Bulletproofs+ and Bulletproofs - Part III

In this third part on comparing Bulletproofs+ and Bulletproofs, we will delve into the math of aggregate verification of the range proofs. We compare the verification speeds of both of the protocols qualitatively as well as quantitatively. Please read blogs 1, 2 for a primer on Bulletproofs and Bulletproofs+.

Aggregated Range Proof Protocols

An aggregated range proof implies proving that each of the quantity ajZqa_j \in \mathbb{Z}_q for j=1,2,,mj=1,2,\dots,m is in the range [0,2n1][0,2^n - 1] using a single proof. An aggregated Bulletproofs and Bulletproofs+ proofs have the following structure. crsbp={g,hGnm, g,hG, V=(V1,V2,,Vm)Gm}witbp={a,fZqm}stmtbp={Vj=gajhfj and aj[0,2n1] j[m]}Πbp={A,S,T1,T2,(L, R)=(Li,Ri)j=1log2(nm)G2×log2(nm),τ,t^,μ,a,bZq} \begin{aligned} \texttt{crs}_{bp} &= \{ \textbf{g}, \textbf{h} \in \mathbb{G}^{n\cdot m}, \ g,h \in \mathbb{G}, \ \textbf{V}=(V_1,V_2, \dots, V_m) \in \mathbb{G}^m \} \\[6pt] \texttt{wit}_{bp} &= \{ \textbf{a}, \mathbf{f} \in \mathbb{Z}_q^m \} \\[6pt] \texttt{stmt}_{bp} &= \{ V_j = g^{a_j} h^{f_j} \text{ and } a_j \in [0,2^{n}-1] \ \forall j \in [m] \} \\[6pt] \Pi_{bp} &= \left\{ A,S,T_1,T_2, (\textbf{L,\ R}) = \big( L_i, R_i \big)_{j=1}^{\text{log}_2(nm)} \in \mathbb{G}^{2 \times \text{log}_2(nm)}, \tau, \hat{t}, \mu, a,b \in \mathbb{Z}_q \right\} \end{aligned}

Πbp+={A,(L, R)=(Li,Ri)j=1log2(nm)G2×log2(nm),r,s,δZq,A,BG} \Pi_{bp+} = \left\{ A,(\textbf{L,\ R}) = \big( L_i, R_i \big)_{j=1}^{\text{log}_2(nm)} \in \mathbb{G}^{2 \times \text{log}_2(nm)}, r',s',\delta' \in \mathbb{Z}_q, A',B' \in \mathbb{G} \right\}

Note that the crs, wit, stmt\texttt{crs, wit, stmt} remain unchanged for Bulletproofs+.

Bulletproofs Verification

Given an aggregated BP proof, a verifier needs to check the following: gt^hτ=?gδ(y,z)Vz2zmT1xT2x2(1) \tag{1} g^{\hat{t}} \cdot h^{\tau} \stackrel{?}{=} g^{\delta(y,z)} \cdot \textbf{V}^{z^2 \cdot \textbf{z}^m} \cdot T_1^x \cdot T_2^{x^2}

verify-ipp(g,h,gxu,Phμgxut^,t^)(2) \tag{2} \text{verify-ipp}(\textbf{g}, \textbf{h}', g^{x_u}, Ph^{-\mu}g^{x_u \cdot \hat{t}}, \hat{t})

where h=(h1,h2y1,,hmny1mn)\textbf{h}' = (h_1, h_2^{y^{-1}}, \dots, h_{mn}^{y^{1-mn}}). Note that the verifier can compute PP as

P=ASxgz1mn(h)zymn+d(3)\tag{3} P = A \cdot S^x \cdot \textbf{g}^{-z \cdot \textbf{1}^{mn}} \cdot (\textbf{h}')^{z \cdot \textbf{y}^{mn} + \textbf{d}}

where d=(z22n,z32n,,zm+12n)Zqmn\textbf{d} = (z^2 \cdot \textbf{2}^n, z^3 \cdot \textbf{2}^n, \dots, z^{m+1} \cdot \textbf{2}^n) \in \mathbb{Z}^{mn}_q from publicly available information. The inner product proof in (2)(2) can be verified in a single multi-exponentiation equation 1 as

gashbsgxuab=?(Phμ)j=1log2(nm)Ljxj2Rjxj2(4) \tag{4} \textbf{g}^{a \cdot \textbf{s}} \cdot \textbf{h}^{b \cdot \textbf{s}'} \cdot g^{x_u \cdot ab} \stackrel{?}{=} (Ph^{-\mu}) \cdot \prod_{j=1}^{\text{log}_2(nm)} L_j^{x_j^2} \cdot R_j^{x_j^{-2}}

where s=(s1,s2,,smn),s=(s11,s21,,smn1)Zqmn\textbf{s} = (s_1, s_2, \dots, s_{mn}), \textbf{s}' = (s_1^{-1}, s_2^{-1}, \dots, s_{mn}^{-1}) \in \mathbb{Z}_q^{mn} such that for all i[nm]i \in [nm]

si=j=1log2(nm)xjb(i,j) where b(i,j)={1if j-th bit of (i1) is 11otherwise s_i = \prod_{j=1}^{\text{log}_2(nm)} x_j^{b(i,j)} \quad \text{ where } \quad b(i,j) = \begin{cases} 1 &\text{if $j$-th bit of } (i-1) \text{ is 1} \\ -1 &\text{otherwise} \end{cases}

and (x1,x2,,xlog2(nm))(x_1, x_2, \dots, x_{\text{log}_2(nm)}) are the challenges using in log2(nm)\text{log}_2(nm) rounds of inner product protocol. Substituting (3)(3) in (4)(4) to get a single inner product proof check, we get

gashbsgxuab=?(ASxgz1mn(h)zymn+dhμgxut^)j=1log2(nm)Ljxj2Rjxj2 \textbf{g}^{a \cdot \textbf{s}} \cdot \textbf{h}^{b \cdot \textbf{s}'} \cdot g^{x_u \cdot ab} \stackrel{?}{=} \left( A \cdot S^x \cdot \textbf{g}^{-z \cdot \textbf{1}^{mn}} \cdot (\textbf{h}')^{z \cdot \textbf{y}^{mn} + \textbf{d}} \cdot h^{-\mu} \cdot g^{x_u \cdot \hat{t}} \right) \cdot \prod_{j=1}^{\text{log}_2(nm)} L_j^{x_j^2} \cdot R_j^{x_j^{-2}}

Bringing everything to the left, we have gas+z1mnhbsz1mn(y)mndgxu(abt^)hμA1Sxj=1log2(nm)Ljxj2Rjxj2=?1 \textbf{g}^{a \cdot \textbf{s} + z \cdot \textbf{1}^{mn}} \cdot \textbf{h}^{b \cdot \textbf{s}' - z \cdot \textbf{1}^{mn} - (\textbf{y}')^{mn} \circ \textbf{d}} \cdot g^{x_u (ab - \hat{t})} \cdot h^{\mu} \cdot A^{-1} \cdot S^{-x} \cdot \prod_{j=1}^{\text{log}_2(nm)} L_j^{-x_j^2} \cdot R_j^{-x_j^{-2}} \stackrel{?}{=} 1

where y=(1,y1,y2,,ymn+1)\textbf{y}' = (1, y^{-1}, y^{-2}, \dots, y^{-mn+1}). Substituting xL=(x12,x22,,xlog2(nm)2)xR=(x12,x22,,xlog2(nm)2), \begin{aligned} \textbf{x}_L &= (-x_1^2, -x_2^2, \dots, -x_{\text{log}_2(nm)}^2) \\ \textbf{x}_R &= (-x_1^{-2}, -x_2^{-2}, \dots, -x_{\text{log}_2(nm)}^{-2}), \end{aligned} we get

gas+z1mnhbsz1mn(y)mndgxu(abt^)hμA1SxLxLRxR=?1(5) \tag{5} \textbf{g}^{a \cdot \textbf{s} + z \cdot \textbf{1}^{mn}} \cdot \textbf{h}^{b \cdot \textbf{s}' - z \cdot \textbf{1}^{mn} - (\textbf{y}')^{mn} \circ \textbf{d}} \cdot g^{x_u (ab - \hat{t})} \cdot h^{\mu} \cdot A^{-1} \cdot S^{-x} \cdot \textbf{L}^{\textbf{x}_L} \cdot \textbf{R}^{\textbf{x}_R} \stackrel{?}{=} 1

A verifier, thus, has to verify equations (1),(5)(1), (5) to verify a BP range proof. We can re-write (1)(1) as gt^δ(y,z)hτVz2zmT1xT2x2=?1(6) \tag{6} g^{\hat{t} - \delta(y,z)} \cdot h^{\tau} \cdot \textbf{V}^{-z^2 \cdot \textbf{z}^m} \cdot \cdot T_1^{-x} \cdot T_2^{-x^2} \stackrel{?}{=} 1

Lastly, she can combine equations (5),(6)(5), (6) into a single multi-exponentiation check using a random scalar cZqc \in \mathbb{Z}_q as follows:

(gt^δ(y,z)hτVz2zmT1xT2x2)cgas+z1mnhbsz1mn(y)mndgxu(abt^)hμA1SxLxLRxR=?1 \left( g^{\hat{t} - \delta(y,z)} \cdot h^{\tau} \cdot \textbf{V}^{-z^2 \cdot \textbf{z}^m} \cdot \cdot T_1^{-x} \cdot T_2^{-x^2} \right)^c \cdot \textbf{g}^{a \cdot \textbf{s} + z \cdot \textbf{1}^{mn}} \cdot \textbf{h}^{b \cdot \textbf{s}' - z \cdot \textbf{1}^{mn} - (\textbf{y}')^{mn} \circ \textbf{d}} \cdot \\ g^{x_u (ab - \hat{t})} \cdot h^{\mu} \cdot A^{-1} \cdot S^{-x} \cdot \textbf{L}^{\textbf{x}_L} \cdot \textbf{R}^{\textbf{x}_R} \stackrel{?}{=} 1 \\

    gas+z1mnhbsz1mn(y)mndgxu(abt^)+c(t^δ(y,z))hμ+cτA1SxLxLRxRVcz2zmT1cxT2cx2=?1(7) \tag{7} \implies \textbf{g}^{a \cdot \textbf{s} + z \cdot \textbf{1}^{mn}} \cdot \textbf{h}^{b \cdot \textbf{s}' - z \cdot \textbf{1}^{mn} - (\textbf{y}')^{mn} \circ \textbf{d}} \cdot g^{x_u (ab - \hat{t}) + c(\hat{t} - \delta(y,z))} \cdot h^{\mu + c\tau} \cdot \\ A^{-1} \cdot S^{-x} \cdot \textbf{L}^{\textbf{x}_L} \cdot \textbf{R}^{\textbf{x}_R} \cdot \textbf{V}^{-c z^2 \cdot \textbf{z}^m} \cdot \cdot T_1^{-c x} \cdot T_2^{-c x^2} \stackrel{?}{=} 1

Thus, an aggregated BP range proof can be verified by a single multi-exponentiation check of size 2mn+2log2(mn)+m+62mn + 2\text{log}_2(mn) + m + 6.

Bulletproofs+ Verification

To verify an aggregated Bulletproofs+ range proof Πbp+\Pi_{bp+}, a verifier needs to compute A^\hat{A} and run the verify-zk-WIP\text{verify-}zk\text{-}\textsf{WIP}.

A^=Agz1mnhz1mn+dymnVymn+1z2zmgζ(y,z)verify-zk-WIPy(g,h,g,h,A^)(8) \tag{8} \hat{A} = A \cdot \textbf{g}^{-z \cdot \textbf{1}^{mn}} \cdot \textbf{h}^{z \cdot \textbf{1}^{mn} + \textbf{d} \circ \overleftarrow{y}^{mn}} \cdot \textbf{V}^{y^{mn+1} \cdot z^2 \cdot \textbf{z}^m} \cdot g^{\zeta(y,z)} \\[6pt] \text{verify-}zk\text{-}\textsf{WIP}_{y}(\textbf{g}, \textbf{h}, g,h, \hat{A})

where ζ(y,z)=(zz2)y1mn,ynmzymn+11mn,d\zeta(y,z) = (z - z^2) y \cdot \langle \textbf{1}^{mn},\textbf{y}^{nm} \rangle - zy^{mn+1} \cdot \langle \textbf{1}^{mn}, \textbf{d} \rangle and ynm=(ymn,ymn1,,y)\overleftarrow{y}^{nm} = (y^{mn}, y^{mn-1}, \dots, y). Similar to the inner product argument, the verification in weighted inner product argument too can be expressed as a single equation by unrolling recursion.

gershessgrshδ=?(A^)e2(j=1log2(nm)Lje2xj2Rje2xj2)(A)eB(9) \tag{9} \textbf{g}^{e \cdot r' \cdot \textbf{s}} \cdot \textbf{h}^{e \cdot s' \cdot \textbf{s}'} \cdot g^{r' \odot s'} \cdot h^{\delta'} \stackrel{?}{=} (\hat{A})^{e^2} \cdot \left( \prod_{j=1}^{\text{log}_2(nm)} L_j^{e^2 \cdot x_j^2} \cdot R_j^{e^2 \cdot x_j^{-2}} \right) \cdot (A')^{e} \cdot B

By substituting A^\hat{A}, the verification boils downs to a single multi-exponentiation check.

gershessgrshδ=?(Agz1mnhz1mn+dymnVymn+1z2zmgζ(y,z))e2(j=1log2(nm)Lje2xj2Rje2xj2)(A)eB \textbf{g}^{e \cdot r' \cdot \textbf{s}} \cdot \textbf{h}^{e \cdot s' \cdot \textbf{s}'} \cdot g^{r' \odot s'} \cdot h^{\delta'} \stackrel{?}{=} \left( A \cdot \textbf{g}^{-z \cdot \textbf{1}^{mn}} \cdot \textbf{h}^{z \cdot \textbf{1}^{mn} + \textbf{d} \circ \overleftarrow{y}^{mn}} \cdot \textbf{V}^{y^{mn+1} \cdot z^2 \cdot \textbf{z}^m} \cdot g^{\zeta(y,z)} \right)^{e^2} \cdot \\ \left( \prod_{j=1}^{\text{log}_2(nm)} L_j^{e^2 \cdot x_j^2} \cdot R_j^{e^2 \cdot x_j^{-2}} \right) \cdot (A')^{e} \cdot B

    gers+ze21mnhessze21mne2dymngrse2ζ(y,z)hδAe2Ve2ymn+1z2zmLxLRxR(A)eB1 \implies \textbf{g}^{e \cdot r' \cdot \textbf{s} + ze^2 \textbf{1}^{mn}} \cdot \textbf{h}^{e \cdot s' \cdot \textbf{s}' - ze^2 \cdot \textbf{1}^{mn} - e^2 \cdot \textbf{d} \circ \overleftarrow{y}^{mn}} \cdot g^{r' \odot s' - e^2\zeta(y,z)} \cdot h^{\delta'} \cdot A^{-e^2} \cdot \\ \textbf{V}^{-e^2 y^{mn+1} \cdot z^2 \cdot \textbf{z}^m} \cdot \textbf{L}^{\textbf{x}_L} \cdot \textbf{R}^{\textbf{x}_R} \cdot (A')^{-e} \cdot B^{-1}

Note here, we have xL=e2(x12,x22,,xlog2(nm)2)xR=e2(x12,x22,,xlog2(nm)2), \begin{aligned} \textbf{x}_L &= e^2 \cdot (-x_1^2, -x_2^2, \dots, -x_{\text{log}_2(nm)}^2) \\ \textbf{x}_R &= e^2 \cdot (-x_1^{-2}, -x_2^{-2}, \dots, -x_{\text{log}_2(nm)}^{-2}), \end{aligned}

Thus, an aggregated BP+ range proof can be verified by a single multi-exponentiation check of size 2mn+2log2(mn)+m+52mn + 2\text{log}_2(mn) + m + 5.

Comparison of Verification Times

The following plot shows verification times for BP and BP+ for 6464-bit range proofs over secp256k1\texttt{secp256k1} curve in Rust. The code can be found here. Note that the verification speed can be further improved using Pipenger’s exponentiation algorithm for computing a multi-exponentiation. All simulations were performed on an Intel® Core™ i7-5500U CPU running at 2.40GHz.

Plot of verification times of 6464-bit BP and BP+ range proofs for different aggregation sizes mm.
  1. The challenge xux_u is used to multiply the given inner product a,b\langle \textbf{a},\textbf{b} \rangle in the exponent of a generator gGg \in \mathbb{G}. BP paper uses uGu \in \mathbb{G} in Protocol 1, 2 instead of gg