Implementing New Range Proof Technique Bulletproofs+ in Monero
Overview
Hello everyone! This CCS proposal is for implementing Bulletproofs+ for range proofs in Monero. Currently, Bulletproofs is employed for range proofs in Monero. Using Bulletproofs+, we aim to save about 10% of the data being pushed to Monero blockchain everyday. We already have a proof of concept implementation of Bulletproofs+ in Rust. Our simulations show that Bulletproofs+ could speed up proof generation and verification by 21% and 17% (Note: These improvements in timings will vary depending on how efficient the group operations over Ed25519 curve used in Monero are). In blogs 1 and 2 we cover in depth the techniques used in Bulletproofs+ and how they differ with Bulletproofs. Read below for more details on applicability of Bulletproofs+ to Monero.
Team and Scope
I am Suyash Bagad and I just graduated with B.Tech and M.Tech in Electrical Engineering from IIT Bombay (India). My thesis was primarily on designing and implementing novel proofs of reserves protocols for crypto exchanges mainly for Monero and Grin. I have also worked on a few other topics in cryptocurrency research.
This will be a joint project together with @omershlo who is experienced in implementing complex cryptographic systems. Our goal is to provide a full implementation of the protocol (aggregated version) from the Bulletproof+ paper while re-using as much of the existing code base utilized for Bulletproofs.
Funding Note
We estimate to complete the project in about 3 months in 3 steps as below:
- Working Proof of Concept
- Optimizations and Code quality
- Benchmarking
We need a funding equivalent to a standard researcher's salary of $10k per month amounting to ~450 XMR (for 3 months) according to the moving average on Kraken. The funding is proposed in 3 payouts of 50%, 30% and 20% respectively for the above 3 steps. This project will include both me and @omershlo working as well as academic advisory from Claudio Orlandi.
Details on how Bulletproofs+ can improve Monero
Security wise, Bulletproofs+ do not introduce any new assumptions on top of Bulletproofs. It uses the weighted inner product protocol while Bulletproofs uses inner product protocol. Each Monero transaction contains 2.5 outputs on an average. This means that each transaction is accompanied by 2.5 range proofs (Bulletproofs as of now). As Monero uses the Ed25519 curve, the size of a single Bulletproofs proof is 676 bytes [1]. This could be reduced by 96 bytes by using Bulletproofs+. In effect, about 240 bytes per transaction could be saved. Average number of transactions on July 16th was 11,417 [2]. This implies that about 2.7 MB of data can be saved everyday [3]. From the start of 2020 till this submission date, an average of 28 MB of data is added daily to the blockchain. Therefore, Bulletproofs+ can save about 10% of the data being added to the Monero blockchain!
The running times of Bulletproofs and Bulletproofs+ over Ed25519 curve are noted below in Table 1. 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, unoptimized operations in the underlying curve library won't matter. Bulletproofs+ shows a 21% faster proof generation and 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!
[1]: Monero uses the Edwards curve Ed25519 in which public and private keys are 32 bytes each.
[2]: Monero Block Explorer, https://moneroblocks.info/stats/
[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.1 MB of data.
| m | ||||||
|---|---|---|---|---|---|---|
| Proof size (B) | Generation time (ms) | Verification time (ms) | ||||
| BP | BP+ | BP | BP+ | BP | BP+ | |
| 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% |