Range proofs and Bulletproofs+
Proving a hidden number lies between 0 and 2⁶⁴ without revealing it
Every output proves its amount v is in [0, 2⁶⁴). That closes the "negative amounts" hole. Monero uses Bulletproofs+ (since August 2022): one aggregated proof per transaction whose size grows logarithmically — ~600 bytes for 2 outputs.
The idea: split the number into bits
A number in [0, 2⁶⁴) is 64 bits: v = b₀·1 + b₁·2 + b₂·4 + … + b₆₃·2⁶³, with each bᵢ ∈ {0, 1}. If you prove (1) each bᵢ really is 0 or 1 and (2) the weighted sum of bits equals v, then v is certainly in range.
The "is a bit" condition is algebraic: bᵢ·(bᵢ − 1) = 0. The task becomes proving a set of hidden numbers satisfies a set of equations without revealing the numbers.
Evolution in Monero
| Period | Scheme | Size (2 outputs) | How it works |
|---|---|---|---|
| 2017–2018 | Borromean | ~13 KB | Each bit is a separate commitment + a ring signature "this commits to 0 or 2ⁱ". Linear size. |
| Oct 2018 – Aug 2022 | Bulletproofs | ~700 bytes | Inner-product argument: logarithmic size, several outputs aggregated into one proof. |
| since Aug 2022 | Bulletproofs+ | ~600 bytes | Improved variant (weighted inner product): smaller and faster still. |
Switching to Bulletproofs in 2018 made transactions about 10× smaller and cut fees by as much. One of the most noticeable upgrades in Monero's history.
How Bulletproofs works (intuition)
- The prover commits to the bit vector
a_Land the vectora_R = a_L − 1with one vector Pedersen commitment. - The verifier (via a hash, Fiat–Shamir) sends random challenges
y, z. All 64 "is a bit" conditions and the "sum" condition are glued into one inner-product equation⟨l, r⟩ = t. Random challenges ensure you can't fake the glued equation without satisfying all the originals. - An inner product of length-n vectors is proven recursively: at each step the vectors are "folded in half" with a new challenge, and after
log₂ nsteps one number each remains. Each step sends 2 points — hence logarithmic size.
Aggregation: for m outputs the vectors have length 64·m, and size grows by only 2·log₂ m points. That's why Monero caps outputs per transaction at 16 and pads to a power of two.
Pros and cons
+
- No trusted setup (unlike zk-SNARKs in Zcash Sprout/Sapling).
- Relies only on discrete log hardness — the same assumption as the rest of Monero.
- Compact and aggregatable.
- Many proofs can be checked together (batch verification).
−
- Verification is linear in the number of bits — a sizable share of block verification time.
- Not quantum-resistant: a quantum computer would break Pedersen binding (it could print money), though hiding would remain.
FCMP++ uses a generalisation of the same technique — Generalized Bulletproofs — to prove a path in the tree of all outputs. Understanding Bulletproofs is a good foundation for FCMP++ proofs.