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 is in the range . Let the bitwise representation of be and define vector as
If we prove that and satisfy the following relations simultaneously, then it implies that indeed lies in the range . To use the inner product argument, we need to embed the above constraints in an inner product form as follows.
Using a random scalar , we combine the above inner product relations to get a single inner product relation as follows. Combining first and third terms, we get Splitting the second inner product, Combining first two terms and rewritting the third term, we get Adding on both sides, Combining second and third terms and substituting we get Combining the two terms on LHS, we get
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 . Before doing so, we need to blind the embedded secret vectors since they contain our original secrets. We do so by adding randomly chosen 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.
The weighted WIP protocol (as described in previous blog) w.r.t. is a tailored protocol for proving a product relation between two hidden vectors and and the challenge 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 , we combine the inner product relations in to get a single inner product relation as follows. Simplifying the above equation into a single inner product relation, we get where . We can write the above expression in a weighted inner product form for a constant Now, the prover can compute a Pedersen commitment to vectors and as for a random and a Pedersen commitment to the amount for a random . 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 , and . The verifier can compute Pedersen vector commitment to from publicly available information as
Hereafter, the prover can run .
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.
For secret vector size , the proof size of the inner product (IP) argument used in Bulletproofs is elements in and elements in . On the other hand, the proof size for the weighted inner product (WIP) argument is elements in and elements in . 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 is the number of proofs aggregated, the proof size increases by only group elements.
Table 1. Proof size comparison
|# Elements in||# Elements in|
|Weighted Inner Product|
We have implemented Bulletproofs+ in the existing implementation of Bulletproofs in KZen-Networks’ bulletproofs library. The prover and verifier’s computation is 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 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 . 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 valid blocks. The total number of outputs on the Grin blockchain were out of which are UTXOs (unspent transaction outputs). The total number of transactions (equals to the number of kernels) in Grin were . Thus, we have
- Number of outputs per transactions:
- Number of outputs per block:
- Number of trasactions per block:
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 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 . Thus, Bulletproofs+ could be used instead of Bulletproofs to improve performance.
More specifically, each Monero transaction contains outputs on an average. This means that each transaction is accompanied by range proofs (Bulletproofs as of now). As Monero uses the curve, the size of a single Bulletproofs proof is bytes 2. This could be reduced by bytes by using Bulletproofs+. In effect, about bytes per transaction could be saved. Average number of transactions on 16th July was . This implies that about MB of data can be saved everyday 3. From the start of 2020 till date, on an average MB of data is added daily to the blockchain 4. Therefore, Bulletproofs+ can save about of the data being added to the Monero blockchain!
The running times of Bulletproofs and Bulletproofs+ over 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 faster proof generation and 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!
|Proof size (B)||Generation time (ms)||Verification time (ms)|
|1||688||591||75.0||59.3 20.9%||30.8||25.3 17.8%|
|4||820||723||295.1||234.1 20.7%||116.1||97.5 16%|
|8||886||789||590.9||473.5 19.8%||229.1||197.5 13.8%|
|16||952||855||1187.4||978.0 17.6%||469.4||406.3 13.5%|
|32||1018||921||2344.9||2127.2 9.3%||927.7||885.6 4.5%|
|Proof size (B)||Generation time (ms)||Verification time (ms)|
|1||672||576||140.5||109.8 21.8%||56.5||46.8 17.2%|
|4||800||704||550.3||431.6 21.5%||214.3||179.4 16.3%|
|8||864||768||1095.8||864.8 21.0%||423.5||359.0 15.2%|
|16||928||832||2190.3||1772.0 19.0%||839.8||730.0 13.0%|
|32||992||896||4392.0||3687.4 14.8%||1702.4||1528.3 10.2%|
Grin uses curve in which private keys are bytes in size and public keys are bytes. Thus, the size of an element in is bytes and that of an element in is bytes. ↩
Monero uses the Edwards curve in which public and private keys are bytes each. ↩
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 MB of data. ↩
Monero Blockchain Growth, https://moneroblocks.info/stats/blockchain-growth ↩
The differences in running times of BP and BP+ will of course vary for different underlying curve implementations. ↩