Comparing Bulletproofs+ and Bulletproofs - Part II

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. We will try to highlight a small but crucial difference in the design of the two protocols and discuss its implications on their performance.

Logarithmic Range Proof Protocol

Suppose we wish to prove that a given quantity a∈Zqa \in \mathbb{Z}_q is in the range [0,2n−1][0,2^n - 1]. Let the bitwise representation of aa be aL∈{0,1}n\textbf{a}_L \in \{0,1\}^n and define vector aR∈Zqn\textbf{a}_R \in \mathbb{Z}_q^n as aR≔aL−1n \textbf{a}_R \coloneqq \textbf{a}_L - \textbf{1}^n

If we prove that aL\textbf{a}_L and aR\textbf{a}_R satisfy the following relations simultaneously, ⟨aL,2n⟩=a,aL∘aR=0n,aR=aL−1n, \langle \textbf{a}_L, \textbf{2}^n \rangle = a, \qquad \textbf{a}_L \circ \textbf{a}_R = \textbf{0}^n, \qquad \textbf{a}_R = \textbf{a}_L - \textbf{1}^n, then it implies that aa indeed lies in the range [0,2n−1][0,2^n - 1]. To use the inner product argument, we need to embed the above constraints in an inner product form as follows. ⟨aL,2n⟩=a,⟨aL,aR∘yn⟩=0,⟨aL−aR−1n,yn⟩=0.(1) \langle \textbf{a}_L, \textbf{2}^n \rangle = a, \qquad \langle \textbf{a}_L, \textbf{a}_R \circ \textbf{y}^n \rangle = 0, \qquad \langle \textbf{a}_L - \textbf{a}_R - \textbf{1}^n, \textbf{y}^n \rangle = 0. \hspace{2cm} (1)

Using a random scalar z∈Zqz \in \mathbb{Z}_q, we combine the above inner product relations to get a single inner product relation as follows. z2⋅⟨aL,2n⟩+z⋅⟨aL−aR−1n,yn⟩+⟨aL,aR∘yn⟩=z2⋅a,  ⟹  ⟨aL,z2⋅2n⟩+⟨aL−aR−1n,z⋅yn⟩+⟨aL,aR∘yn⟩=z2⋅a, z^2 \cdot \langle \textbf{a}_L, \textbf{2}^n \rangle + z \cdot \langle \textbf{a}_L - \textbf{a}_R - \textbf{1}^n, \textbf{y}^n \rangle + \langle \textbf{a}_L, \textbf{a}_R \circ \textbf{y}^n \rangle = z^2 \cdot a, \\[6pt] \implies \langle \textbf{a}_L, z^2 \cdot \textbf{2}^n \rangle + \langle \textbf{a}_L - \textbf{a}_R - \textbf{1}^n, z \cdot \textbf{y}^n \rangle + \langle \textbf{a}_L, \textbf{a}_R \circ \textbf{y}^n \rangle = z^2 \cdot a, Combining first and third terms, we get ⟨aL,aR∘yn+z2⋅2n⟩+⟨aL−aR−1n,z⋅yn⟩,=z2⋅a \langle \textbf{a}_L, \textbf{a}_R \circ \textbf{y}^n + z^2 \cdot \textbf{2}^n \rangle + \langle \textbf{a}_L - \textbf{a}_R - \textbf{1}^n, z \cdot \textbf{y}^n \rangle, = z^2 \cdot a Splitting the second inner product, ⟨aL,aR∘yn+z2⋅2n⟩+⟨aL,z⋅yn⟩+⟨aR,−z⋅yn⟩=z2⋅a+z⋅⟨yn,1n⟩, \langle \textbf{a}_L, \textbf{a}_R \circ \textbf{y}^n + z^2 \cdot \textbf{2}^n \rangle + \langle \textbf{a}_L, z \cdot \textbf{y}^n \rangle + \langle \textbf{a}_R, -z \cdot \textbf{y}^n \rangle = z^2 \cdot a + z \cdot \langle \textbf{y}^n, \textbf{1}^n \rangle, Combining first two terms and rewritting the third term, we get ⟨aL,aR∘yn+z2⋅2n+z⋅yn⟩+⟨aR∘yn,−z⋅1n⟩=z2⋅a+z⋅⟨yn,1n⟩, \langle \textbf{a}_L, \textbf{a}_R \circ \textbf{y}^n + z^2 \cdot \textbf{2}^n + z \cdot \textbf{y}^n \rangle + \langle \textbf{a}_R \circ \textbf{y}^n, -z \cdot \textbf{1}^n \rangle = z^2 \cdot a + z \cdot \langle \textbf{y}^n, \textbf{1}^n \rangle, Adding ⟨z2⋅2n+z⋅yn,−z⋅1n⟩=−z3⋅⟨2n,1n⟩−z2⋅⟨yn,1n⟩\langle z^2 \cdot \textbf{2}^n + z \cdot \textbf{y}^n, -z \cdot \textbf{1}^n \rangle = -z^3 \cdot \langle \textbf{2}^n,\textbf{1}^n \rangle - z^2 \cdot \langle \textbf{y}^n,\textbf{1}^n \rangle on both sides, ⟨aL,aR∘yn+z2⋅2n+z⋅yn⟩+⟨aR∘yn,−z⋅1n⟩+⟨z2⋅2n+z⋅yn,−z⋅1n⟩=z2⋅a+(z−z2)⋅⟨yn,1n⟩−z3⋅⟨2n,1n⟩, \langle \textbf{a}_L, \textbf{a}_R \circ \textbf{y}^n + z^2 \cdot \textbf{2}^n + z \cdot \textbf{y}^n \rangle + \langle \textbf{a}_R \circ \textbf{y}^n, -z \cdot \textbf{1}^n \rangle + \langle z^2 \cdot \textbf{2}^n + z \cdot \textbf{y}^n, -z \cdot \textbf{1}^n \rangle \\[4pt] = z^2 \cdot a + (z-z^2) \cdot \langle \textbf{y}^n, \textbf{1}^n \rangle - z^3 \cdot \langle \textbf{2}^n,\textbf{1}^n \rangle, Combining second and third terms and substituting δ(y,z)=z2⋅a+(z−z2)⋅⟨yn,1n⟩−z3⋅⟨2n,1n⟩,\delta(y,z) = z^2 \cdot a + (z-z^2) \cdot \langle \textbf{y}^n, \textbf{1}^n \rangle - z^3 \cdot \langle \textbf{2}^n,\textbf{1}^n \rangle, we get ⟨aL,aR∘yn+z2⋅2n+z⋅yn⟩+⟨aR∘yn+z2⋅2n+z⋅yn,−z⋅1n⟩=yn+1⋅a+δ(y,z), \langle \textbf{a}_L, \textbf{a}_R \circ \textbf{y}^n + z^2 \cdot \textbf{2}^n + z \cdot \textbf{y}^n \rangle + \langle \textbf{a}_R \circ \textbf{y}^n + z^2 \cdot \textbf{2}^n + z \cdot \textbf{y}^n, -z \cdot \textbf{1}^n \rangle = y^{n+1} \cdot a+ \delta(y,z), Combining the two terms on LHS, we get ⟨aL−z⋅1n,yn∘(aR+z⋅1n)+z2⋅2n⟩=yn+1⋅a+δ(y,z). \langle \textbf{a}_L -z \cdot \textbf{1}^n, \textbf{y}^n \circ (\textbf{a}_R + z \cdot \textbf{1}^n) + z^2 \cdot \textbf{2}^n \rangle = y^{n+1} \cdot a+ \delta(y,z).

Hereafter, the two vectors in the above inner product are our new embedded secrets and we can use the inner product argument to prove the knowledge of these vectors and in turn prove that a∈[0,2n−1]a \in [0, 2^n-1]. Before doing so, we need to blind the embedded secret vectors since they contain our original secrets. We do so by adding randomly chosen sL,sR∈Zqn\textbf{s}^L, \textbf{s}^R \in \mathbb{Z}_q^n to respective embedded vectors. Without going into the exact details of the protocol, such blinding makes the interaction between prover and verifier lengthy resulting in increased prover communication.

Bulletproofs+

The weighted WIP protocol (as described in previous blog) w.r.t. y→n\overrightarrow{y}^n is a tailored protocol for proving a product relation between two hidden vectors aL\textbf{a}_L and aR\textbf{a}_R and the challenge y→n\overrightarrow{y}^n with zero-knowledge. Therefore, the prover doesn’t need to blind the embedded secret vectors as in the case of Bulletproofs, saving significant prover communication.

Let us rewrite the inner product relation between embedded secret vectors in a weighted inner product form. Using scalars (yn+1,z⋅y→n,y→n)∈Zq2n+1(y^{n+1}, z \cdot \overrightarrow{y}^n, \overrightarrow{y}^n) \in \mathbb{Z}_q^{2n+1}, we combine the inner product relations in (1)(1) to get a single inner product relation as follows. yn+1⋅⟨aL,2n⟩+z⋅⟨aL−aR−1n,y→n⟩+⟨aL,aR∘y→n⟩=yn+1⋅a, y^{n+1} \cdot \langle \textbf{a}_L, \textbf{2}^n \rangle + z \cdot \langle \textbf{a}_L - \textbf{a}_R - \textbf{1}^n, \overrightarrow{y}^n \rangle + \langle \textbf{a}_L, \textbf{a}_R \circ \overrightarrow{y}^n \rangle = y^{n+1} \cdot a, Simplifying the above equation into a single inner product relation, we get ⟨aL−z⋅1n,y→n∘(aR+z⋅1n)+yn+1⋅2n⟩=yn+1⋅a−ζ(y,z), \langle \textbf{a}_L -z \cdot \textbf{1}^n, \overrightarrow{y}^n \circ (\textbf{a}_R + z \cdot \textbf{1}^n) + y^{n+1} \cdot \textbf{2}^n \rangle = y^{n+1} \cdot a - \zeta(y,z), where ζ(y,z)=zyn+1⋅⟨2n,1n⟩+(z2−z)⋅⟨1n,y→n⟩\zeta(y,z)= zy^{n+1} \cdot \langle \textbf{2}^n,\textbf{1}^n \rangle + (z^2-z) \cdot \langle \textbf{1}^n,\overrightarrow{y}^n \rangle. We can write the above expression in a weighted inner product form for a constant y∈Zqy \in \mathbb{Z}_q (aL−z⋅1n)⊙y(aR+z⋅1n+2n∘y←n)=yn+1⋅a−ζ(y,z). (\textbf{a}_L -z \cdot \textbf{1}^n) \odot_y (\textbf{a}_R + z \cdot \textbf{1}^n + \textbf{2}^n \circ \overleftarrow{y}^n) = y^{n+1} \cdot a - \zeta(y,z). Now, the prover can compute a Pedersen commitment to vectors aL\textbf{a}_L and aR\textbf{a}_R as A=gaLhaRhαA = \textbf{g}^{\textbf{a}_L} \textbf{h}^{\textbf{a}_R} h^{\alpha} for a random α∈Zq\alpha \in \mathbb{Z}_q and a Pedersen commitment to the amount V=gahγV = g^{a}h^{\gamma} for a random γ∈Zq\gamma \in \mathbb{Z}_q. Hereafter, the prover as well as the verifier can compute a Pedersen vector commitment to the vectors in the weighted inner product relation. Concretely, the prover computes the secrets a^L=(aL−z⋅1n)\hat{\textbf{a}}_L = (\textbf{a}_L -z \cdot \textbf{1}^n), a^R=(aR+z⋅1n+2n∘y←n)\hat{\textbf{a}}_R = (\textbf{a}_R + z \cdot \textbf{1}^n + \textbf{2}^n \circ \overleftarrow{y}^n) and α^=α+γ⋅yn+1\hat{\alpha} = \alpha + \gamma \cdot y^{n+1}. The verifier can compute Pedersen vector commitment to a^L,a^R\hat{\textbf{a}}_L, \hat{\textbf{a}}_R from publicly available information as A^=ga^L⋅ha^R⋅ga^L⊙ya^R⋅hyn+1⋅γ⏟Prover=A⋅g−z⋅1n⋅hz⋅1n+2n∘y←n⋅Vyn+1⋅g−ζ(y,z)⏟Verifier \hat{A} = \underbrace{\textbf{g}^{\hat{\textbf{a}}_L} \cdot \textbf{h}^{\hat{\textbf{a}}_R} \cdot g^{\hat{\textbf{a}}_L \odot_y \hat{\textbf{a}}_R} \cdot h^{y^{n+1} \cdot \gamma }}_{\textsf{Prover}} = \underbrace{A \cdot \textbf{g}^{-z \cdot \textbf{1}^n} \cdot \textbf{h}^{z \cdot \textbf{1}^n + \textbf{2}^n \circ \overleftarrow{y}^n} \cdot V^{y^{n+1}} \cdot g^{-\zeta(y,z)}}_{\textsf{Verifier}}

Hereafter, the prover can run zk-WIP(g,h,g,h,A^;g^,g^,α^)zk\textrm{-}\textsf{WIP}(\textbf{g}, \textbf{h}, g, h, \hat{A}; \hat{\textbf{g}}, \hat{\textbf{g}}, \hat{\alpha}).

Performance Comparison

Although the construction of Bulletproofs and Bulletproofs+ is very similar, we expect some differences in their performances. We will analyse the differences in proof sizes and running times.

Proof sizes

For secret vector size nn, the proof size of the inner product (IP) argument used in Bulletproofs is 2⌈log2(n)⌉2\lceil \text{log}_2(n) \rceil elements in G\mathbb{G} and 22 elements in Zq\mathbb{Z}_q. On the other hand, the proof size for the weighted inner product (WIP) argument is 2⌈log2(n)⌉+22\lceil \text{log}_2(n) \rceil + 2 elements in G\mathbb{G} and 33 elements in Zq\mathbb{Z}_q. The additional elements in the WIP argument as against IP argument is because WIP argument is zero-knowledge and IP argument is not zero-knowledge. We summarise the proof sizes of aggregated Bulletproofs and Bulletproofs+ protocols in the following table. Note that if mm is the number of proofs aggregated, the proof size increases by only 2⌈log2(m)⌉2\lceil \text{log}_2(m) \rceil group elements.

Table 1. Proof size comparison

  # Elements in G\mathbb{G} # Elements in Zq\mathbb{Z}_q
Inner Product 2⌈log2(n)⌉2\lceil \text{log}_2(n) \rceil 22
Bulletproofs (aggregated) 2⌈log2(n)+log2(m)⌉+42\lceil \text{log}_2(n) + \text{log}_2(m) \rceil + 4 55
Weighted Inner Product 2⌈log2(n)⌉+22\lceil \text{log}_2(n) \rceil + 2 33
Bulletproofs+ (aggregated) 2⌈log(n)+log2(m)⌉+32\lceil \text{log}(n) + \text{log}_2(m) \rceil + 3 33

Running Times

We have implemented Bulletproofs+ in the existing implementation of Bulletproofs in KZen-Networks’ bulletproofs library. The prover and verifier’s computation is O(n)\mathcal{O}(n) in both Bulletproofs and Bulletproofs+. However, verification can significantly boosted by using a single multi-exponentiation check (read this to briefly understand how multi-exponentiation works). Batching proofs together further improves generation and verification times. In most cryptocurrency systems, range proofs are required for proving that amounts hidden in Pederson commitments are 64-bit non-negative integers. Thus, we compare proof sizes 1 and running times for n=64n=64 and different batching configurations as shown in the following table. All simulations were performed on an Intel® Core™ i7-5500U CPU running at 2.40GHz.

Applicability to Grin

Grin is a cryptocurrency project built using the MimbleWimble protocol. It promises scalability, privacy and fungibility all at once. The amounts in Grin are hidden in outputs which are Pedersen commitments. Each output on the Grin blockchain is accompanied by a range proof proving that the amount hidden in it is in the range [0,264−1][0,2^{64}-1]. These range proofs constitute about 98% of the total blockchain size. Thus, range proofs with smaller proof sizes are very crucial. Grin currently employs Bulletproofs.

We can further improve the range proofs used in Grin by employing Bulletproofs+. For a March 2020 snapshot of the Grin blockchain, we have Nb=612,102N_b = 612,102 valid blocks. The total number of outputs on the Grin blockchain were No=3,185,556N_o = 3,185,556 out of which Nutxo=124,034N_{utxo} = 124,034 are UTXOs (unspent transaction outputs). The total number of transactions (equals to the number of kernels) in Grin were Ntx=1,765,941N_{tx} = 1,765,941. Thus, we have

  • Number of outputs per transactions: noptx=NoNtx=1.80≈2n_{optx} = \frac{N_o}{N_{tx}} = 1.80 \approx 2
  • Number of outputs per block: nopbl=NoNb=5.20≈6n_{opbl} = \frac{N_o}{N_{b}} = 5.20 \approx 6
  • Number of trasactions per block: ntxpbl=NtxNb=2.88≈3n_{txpbl} = \frac{N_{tx}}{N_{b}} = 2.88 \approx 3

Therefore, using Bulletproofs+, 200 bytes per transaction can be saved. Since we have 3 transactions per block on an average, 600 bytes per block can be saved. The typical number of Grin blocks mined in a day is 1500 (~1 block per minute). This implies that everyday, on an average, 1 MB of data can be saved from being added on to the blockchain, Further, if a transaction contains large number of outputs, the fees for inclusion of that transaction is higher because of its greater size. Thus, transaction fees also would be reduced slightly on employing Bulletproofs+. Further, currently the UTXO set contains ≈165,000\approx 165,000 outputs. If we were to employ Bulletproofs+, the UTXO set size would reduce by about 16 MB. Moreover, proof generation and verification can be faster by 20% and 16% respectively using Bulletproofs+ in place of Bulletproofs.

Applicability to Monero

Monero is one of the first privacy-centered cryptocurrency project built on the CryptoNote protocol. The amounts in Monero are also Pedersen commitments and the Bulletproofs is used to prove that they are in the range [0,264−1][0,2^{64}-1]. Thus, Bulletproofs+ could be used instead of Bulletproofs to improve performance.

More specifically, each Monero transaction contains 2.52.5 outputs on an average. This means that each transaction is accompanied by 2.52.5 range proofs (Bulletproofs as of now). As Monero uses the Ed25519\texttt{Ed25519} curve, the size of a single Bulletproofs proof is 676676 bytes 2. This could be reduced by 9696 bytes by using Bulletproofs+. In effect, about 240240 bytes per transaction could be saved. Average number of transactions on 16th July was 11,41711,417. This implies that about 2.72.7 MB of data can be saved everyday 3. From the start of 2020 till date, on an average 2828 MB of data is added daily to the blockchain 4. Therefore, Bulletproofs+ can save about 10%10\% of the data being added to the Monero blockchain!

The running times of Bulletproofs and Bulletproofs+ over Ed25519\texttt{Ed25519} curve are noted below in Table 3. Note that the underlying Edwards curve’s operations are used from cryptoxide library which is slower than the optimized operations in the more recent curve25519-dalek’s implementation. As we are interested only in comparison as of now, slower operations in the underlying curve library won’t matter 5. Bulletproofs+ shows a 21%21\% faster proof generation and 17%17\% faster proof verification than Bulletproofs. Although these numbers would slightly vary when the underlying library for group operations changes, they still look quite promising from a user (prover) as well as miner (verifier) point of view!

Table 2. Performance comparison of Bulletproofs and Bulletproofs+ over secp256k1\texttt{secp256k1} curve
mm
Proof size (B)Generation time (ms)Verification time (ms)
BPBP+BPBP+BPBP+
1 688591 75.059.3   20.9% 30.825.3   17.8%
4 820723 295.1234.1   20.7% 116.197.5   16%
8 886789 590.9473.5   19.8% 229.1197.5   13.8%
16 952855 1187.4978.0   17.6% 469.4406.3   13.5%
32 1018921 2344.92127.2   9.3% 927.7885.6   4.5%
Table 3. Performance comparison of Bulletproofs and Bulletproofs+ over Ed25519\texttt{Ed25519} curve
mm
Proof size (B)Generation time (ms)Verification time (ms)
BPBP+BPBP+BPBP+
1 672576 140.5109.8   21.8% 56.546.8   17.2%
4 800704 550.3431.6   21.5% 214.3179.4   16.3%
8 864768 1095.8864.8   21.0% 423.5359.0   15.2%
16 928832 2190.31772.0   19.0% 839.8730.0   13.0%
32 992896 4392.03687.4   14.8% 1702.41528.3   10.2%

  1. Grin uses secp256k1\texttt{secp256k1} curve in which private keys are 3232 bytes in size and public keys are 3333 bytes. Thus, the size of an element in G\mathbb{G} is 3333 bytes and that of an element in Zq\mathbb{Z}_q is 3232 bytes. ↩

  2. Monero uses the Edwards curve Ed25519\texttt{Ed25519} in which public and private keys are 3232 bytes each. ↩

  3. If we assume that the range proofs for outputs per block are aggregated (i.e. they are owned by a single entity), then Bulletproofs+ can save about 1.11.1 MB of data. ↩

  4. Monero Blockchain Growth, https://moneroblocks.info/stats/blockchain-growth ↩

  5. The differences in running times of BP and BP+ will of course vary for different underlying curve implementations. ↩