What are bulletproofs?

Question

I have heard that Monero transactions are relatively large, and that Bulletproofs will make Monero transactions smaller. Can someone give a high-level overview about what these are, and how they effect Monero?

Answer 1

Most of the information below is taken from this post on the GetMonero website.

To understand bulletproofs, you need to first understand what a range proof is. According to the post:

A range proof allows anyone to verify that a commitment represents an amount within a specified range, without revealing anything else about its value.

Monero uses the range proof in RingCT to secure the amount being sent in a transaction. Without range proofs, the amount sent could be hidden, but a sender could cheat by making coins out of thin air. Thankfully, range proofs prevent this from happening.

Bulletproofs are a more efficient type of range proofs. You can view a copy of the research paper for free here. The research paper defines Bulletproofs as follows:

...a new non-interactive zero-knowledge proof protocol with very short proofs and without a trusted setup; the proof size is only logarithmic in the witness size. Bulletproofs are especially well suited for efficient range proofs on committed values...

Bulletproofs offer substantial improvements when using multiple outputs. With current Monero range proof technology, transaction sizes scale mostly linearly depending on the number of outputs (eg: 1 output = 7kB, 2 outputs = 13kB). With bulletproofs, these scale logarithmically instead (eg: 1 output = 2kB, 2 outputs = 2.5kB).

As the post notes, there are two ways bulletproofs can be implemented in Monero:

This gives us two related types of bulletproofs: single-output and multiple-output. A transaction with multiple outputs can either include several single-output proofs or one multiple-output proof (which is smaller than the separate proofs).

The former brings substantial improvements, and the latter brings a little more than the former. The post estimates the following performance improvements:

With our current range proofs, the transaction is around 13.2 kB in size. If I used single-output bulletproofs, the transaction reduces in size to only around 2.5 kB! This is, approximately, an 80% reduction in transaction size, which then translates to an 80% reduction in fees as well. The space savings are even better with multiple-output proofs. This represents a significant decrease in transaction sizes. Further, our initial testing shows that the time to verify a bulletproof is lower than for the existing range proofs, meaning speedier blockchain validation.

Bulletproofs will be deployed in the October scheduled protocol upgrade. It has been live in testnet since the beginning of 2018.