Comparing Bulletproofs+ and Bulletproofs - Part I

Bulletproofs+ is a recently proposed range proof which is similar in spirit to Bulletproofs. Both of these range proof protocols enable proof sizes logarithmic in the number of bits of the range using a recursive inner product protocol. Bulletproofs relies on the improved inner product protocol 1 while Bulletproofs+ uses a weighted inner product protocol 2.

Improved Inner Product Argument

The recursive inner product argument introduced in [1] gives an argument of knowledge for the language given by

LIP(σ)={g,h∈Gn,P∈G,c∈ Zq⏟statement; a,b∈Zqn⏟witness ∣ P=ga⋅hb⋅uc ∧ c=⟨a,b⟩⏟relation} \mathcal{L}_{\textsf{IP}}(\sigma) = \bigg\{ \underbrace{\textbf{g}, \textbf{h} \in \mathbb{G}^n, P \in \mathbb{G}, c \in \ \mathbb{Z}_q}_{\textsf{statement}}; \ \underbrace{\textbf{a}, \textbf{b} \in \mathbb{Z}_q^n}_{\textsf{witness}} \ \bigg| \ \underbrace{P = \textbf{g}^{\textbf{a}} \cdot \textbf{h}^{\textbf{b}} \cdot u^{c} \ \wedge \ c = \langle \textbf{a}, \textbf{b} \rangle}_{\textsf{relation}} \bigg\}

where σ=(G,q=∣G∣,u∈G)\sigma = (\mathbb{G}, q = |\mathbb{G}|, u \in \mathbb{G}) is the common reference string (crs). Note that PP is a Pedersen vector commitment to a,b∈Zqn\textbf{a}, \textbf{b} \in \mathbb{Z}_q^n. We can write the witness as a=(aL,aR)∈Zqn2×2\textbf{a} = (\textbf{a}_L, \textbf{a}_R) \in \mathbb{Z}_q^{\frac{n}{2} \times 2} and b=(bL,bR)∈Zqn2×2\textbf{b} = (\textbf{b}_L, \textbf{b}_R) \in \mathbb{Z}_q^{\frac{n}{2} \times 2}. Similarly, the base vectors can be written as g=(gL,gR)∈Gn2×2\textbf{g} = (\textbf{g}_L, \textbf{g}_R) \in \mathbb{G}^{\frac{n}{2} \times 2} and h=(hL,hR)∈Gn2×2\textbf{h} = (\textbf{h}_L, \textbf{h}_R) \in \mathbb{G}^{\frac{n}{2} \times 2}. Now, we compute Pedersen vector commitments to the vector tuples (aL,bR)(\textbf{a}_L, \textbf{b}_R) and aR,bL\textbf{a}_R, \textbf{b}_L as

L=gRaL⋅hLbR⋅u⟨aL,bR⟩,R=gLaR⋅hRbL⋅u⟨aR,bL⟩. L = \textbf{g}_R^{\textbf{a}_L} \cdot \textbf{h}_L^{\textbf{b}_R} \cdot u^{\langle \textbf{a}_L, \textbf{b}_R\rangle}, \quad R = \textbf{g}_L^{\textbf{a}_R} \cdot \textbf{h}_R^{\textbf{b}_L} \cdot u^{\langle \textbf{a}_R, \textbf{b}_L\rangle}.

Given a challenge scalar x∈Zqx \in \mathbb{Z}_q, we can blind the original witness to get

a^=xaL+x−1aR,b^=x−1bL+xbR. \hat{\textbf{a}} = x\textbf{a}_L + x^{-1}\textbf{a}_R, \quad \hat{\textbf{b}} = x^{-1}\textbf{b}_L + x\textbf{b}_R.

The 4-tuple (L,R,a^,b^)(L,R,\hat{\textbf{a}}, \hat{\textbf{b}}) becomes a valid proof of knowledge of the witness. This can be verified by checking the following

Lx2⋅P⋅Rx−2=(gLx−1∘gRx)a^⋅(hLx∘hRx−1)b^⋅u⟨a^,b^⟩ L^{x^2} \cdot P \cdot R^{x^{-2}} = (\textbf{g}_L^{x^{-1}} \circ \textbf{g}_R^x)^{\hat{\textbf{a}}} \cdot (\textbf{h}_L^{x} \circ \textbf{h}_R^{x^{-1}})^{\hat{\textbf{b}}} \cdot u^{\langle \hat{\textbf{a}}, \hat{\textbf{b}}\rangle}

Instead of publishing vectors (a^,b^)(\hat{\textbf{a}}, \hat{\textbf{b}}), we can further repeat the same process of dividing (a^,b^)(\hat{\textbf{a}}, \hat{\textbf{b}}) in halves and compute (L1,R1,a^1,b^1)(L_1,R_1,\hat{\textbf{a}}_1, \hat{\textbf{b}}_1) and so on until we are left with scalars (a^,b^)∈Zq(\hat{a},\hat{b}) \in \Z_q. This is the main idea of the log-sized inner product protocol and the proof is of the form

(L,R), (L1,R1), …, (L⌈log2n⌉−1,R⌈log2n⌉−1), (a^,b^). (L, R),\ (L_1, R_1), \ \ldots, \ (L_{\lceil \text{log}_2n \rceil - 1}, R_{\lceil \text{log}_2n \rceil - 1}), \ (\hat{a},\hat{b}).

Note that the above argument is perfectly complete and sound, but not zero-knowledge. This is because we cannot construct a PPT simulator who could generate a valid transcript given statement and the crs.

Weighted Inner Product Argument

The weighted inner product argument uses a weighted inner product operation ⊙y:Zqn×Zqn↦Zq\odot_y: \mathbb{Z}^{n}_q \times \mathbb{Z}^{n}_q \mapsto \mathbb{Z_q} defined as a⊙yb=⟨a,y→∘b⟩ \textbf{a} \odot_{y} \textbf{b} = \langle \textbf{a}, \overrightarrow{y} \circ \textbf{b} \rangle where y→=(y,y2,…,yn)∈Zqn\overrightarrow{y} = (y, y^2, \ldots, y^n) \in \mathbb{Z}_q^n and n=∣a∣=∣b∣n = |\textbf{a}| = |\textbf{b}|. The weighted inner product is essentially a way to combine multiple equations into a single equation. For instance, a∘b=c∈Zqn\textbf{a} \circ \textbf{b} = \textbf{c} \in \mathbb{Z}_q^n represent nn distinct equations. The weighted inner product combines these equations to give a single equation of the form ∑i=1nyi⋅(aibi)=a⊙yb=⟨c,y→⟩ \sum_{i=1}^{n} y^{i} \cdot (a_ib_i) = \textbf{a} \odot_{y} \textbf{b} = \langle \textbf{c}, \overrightarrow{y} \rangle

The weighted inner product protocol is also bilinear and satisfies the following property 3 a⊙yb=aL⊙ybL+(yn2⋅aR)⊙ybR. \textbf{a} \odot_{y} \textbf{b} = \textbf{a}_L \odot_{y} \textbf{b}_L + (y^{\frac{n}{2}} \cdot \textbf{a}_R) \odot_{y} \textbf{b}_R.

We now wish to design a proof system based on the weighted inner product. The language of the weighted inner product protocol becomes LWIP(σ)={g,h∈Gn,P∈G,c∈ Zq⏟statement; a,b∈Zqn⏟witness ∣ P=ga⋅hb⋅uc ∧ c=a⊙yb⏟relation} \mathcal{L}_{\textsf{WIP}}(\sigma) = \bigg\{ \underbrace{\textbf{g}, \textbf{h} \in \mathbb{G}^n, P \in \mathbb{G}, c \in \ \mathbb{Z}_q}_{\textsf{statement}}; \ \underbrace{\textbf{a}, \textbf{b} \in \mathbb{Z}_q^n}_{\textsf{witness}} \ \bigg| \ \underbrace{P = \textbf{g}^{\textbf{a}} \cdot \textbf{h}^{\textbf{b}} \cdot u^{c} \ \wedge \ c = \textbf{a} \odot_{y} \textbf{b}}_{\textsf{relation}} \bigg\}

Similar to the inner product protocol, suppose the prover commits to vectors (aL,bR)(\textbf{a}_L, \textbf{b}_R) and (aR,bL)(\textbf{a}_R, \textbf{b}_L) and the scalars cL=aL⊙ybR, cR=(yn2⋅aR)⊙ybLc_L = \textbf{a}_L \odot_{y} \textbf{b}_R, \ c_R = (y^{\frac{n}{2}} \cdot \textbf{a}_R) \odot_{y} \textbf{b}_L, the prover must convince the verifier of the relation c=a⊙ybc = \textbf{a} \odot_y \textbf{b}. For this, we blind the original witness vectors using a challenge scalar x∈Zqx \in \mathbb{Z}_q. a^=xaL+x−1(yn2⋅aR),b^=x−1bL+xbR.  ⟹  a^⊙yb^=x2cL+c+x−2cR. \hat{\textbf{a}} = x\textbf{a}_L + x^{-1}(y^{\frac{n}{2}} \cdot \textbf{a}_R), \quad \hat{\textbf{b}} = x^{-1}\textbf{b}_L + x\textbf{b}_R. \\[4pt] \implies \hat{\textbf{a}} \odot_y \hat{\textbf{b}} = x^2c_L + c + x^{-2}c_R.

Now, similar to the inner product argument, the 4-tuple (L,R,a^,b^)(L,R,\hat{\textbf{a}}, \hat{\textbf{b}}) becomes a valid proof of knowledge of the witness. We can shrink this argument too to logarithmic in the size of witness vectors. The WIP based argument presented in Bulletproofs+ paper is zero-knowledge as against the inner product argument. This is achieved by including randomly chosen blinding factors dL,dR∈Zqd_L, d_R \in \mathbb{Z}_q in computing the Pedersen vector commitments L,RL, R as

L=gRaL⋅hLbR⋅u⟨aL,bR⟩⋅hdL,R=gLaR⋅hRbL⋅u⟨aR,bL⟩⋅hdR. L = \textbf{g}_R^{\textbf{a}_L} \cdot \textbf{h}_L^{\textbf{b}_R} \cdot u^{\langle \textbf{a}_L, \textbf{b}_R\rangle} \cdot h^{d_L}, \quad R = \textbf{g}_L^{\textbf{a}_R} \cdot \textbf{h}_R^{\textbf{b}_L} \cdot u^{\langle \textbf{a}_R, \textbf{b}_L\rangle} \cdot h^{d_R}.

where h∈Gh \in \mathbb{G}. Further, in the last round of the protocol, instead of sending a^,b^∈Z\hat{a}, \hat{b} \in \mathbb{Z}, we use a sigma-like protocol yeilding constant communication and computation. This is the main difference in the inner product and the weighted inner product arguments. We will see in the next blog how this helps building Bulletproofs+ - a range proof protocol with proof size shorter than that of Bulletproofs.

References and Notes

  1. Benedikt Bünz et al, “Bulletproofs: Short Proofs for Confidential Transactions and More”, in Cryptology ePrint Archive, Report 2017/1066, Available at https://eprint.iacr.org/2017/1066.pdf ↩

  2. Chung H. et al, “Bulletproofs+: Shorter Proofs for Privacy-Enhanced Distributed Ledger”, in Cryptology ePrint Archive, Report 2020/735, Available at https://eprint.iacr.org/2020/735.pdf. ↩

  3. Note that aL⊙ybL=⟨aL,(y,y2,…,yn2)∘bL⟩\textbf{a}_L \odot_{y} \textbf{b}_L = \langle \textbf{a}_L, (y,y^2, \ldots, y^{\frac{n}{2}}) \circ \textbf{b}_L \rangle for aL,bL∈Zqn2\textbf{a}_L, \textbf{b}_L \in \mathbb{Z}_q^{\frac{n}{2}}. ↩