Bulletproofs+: The Weighted Inner-Product Argument

Every Monero transaction carries one aggregated Bulletproof+ proving all output amounts are in range. It's the most compute-heavy part of verification, so understanding it — generators, transcript, the weighted inner product, batching, and the weight clawback — is essential for anyone touching consensus or performance.

What's Being Proven

For each output commitment C = aH + xG, prove a ∈ [0, 2⁶⁴) without revealing a. The trick: express the range claim as statements about the bit decomposition of a (each bit is 0 or 1, and the bits reconstruct a), then prove those with an inner-product relation whose proof is logarithmic in the bit-length. Multiple outputs are aggregated into one proof.

Generators and the Transcript

• Two scalar generators G, H (with unknown relative discrete log — same H as the commitments), plus vectors of generators G_i, H_i for the inner-product, all derived deterministically (nothing-up-my-sleeve, no trusted setup).
• The proof is made non-interactive with Fiat–Shamir: every verifier challenge is a hash of the transcript so far (the statement and all prior prover messages). Contributors must hash exactly the right transcript — a missing element is a soundness hole; an extra one breaks interop.

The Weighted Inner-Product Argument (the "+" )

Original Bulletproofs used an inner-product argument that proves ⟨a, b⟩ = c for committed vectors a, b, recursively halving the vector length each round (hence O(log n) size). Bulletproofs+ replaces this with a weighted inner-product argument (WIP): it proves a weighted form ⟨a, b⟩_y (a y-weighted inner product) and folds the range-proof's blinding into the same recursion, removing a separate aggregation/commitment step. Net effect for the same security and no trusted setup:

• Smaller proofs than Bulletproofs (fewer group elements).
• Faster verification — the dominant win, since nodes verify far more than they prove.

Batch Verification

The big performance lever: a node verifying many proofs doesn't check them one by one. It takes a random linear combination of all the proofs' verification equations (each weighted by a fresh random scalar) and checks the single combined multi-scalar multiplication. If any individual proof were invalid, the combined check fails with overwhelming probability. This turns N expensive checks into roughly one big multi-exponentiation, which is why initial block sync is feasible.

Transaction-Weight Clawback

Monero prices transactions by weight, not raw bytes, to reflect verification cost. Bulletproofs aggregate sub-linearly: a 2-output proof isn't twice a 1-output proof. If weight were charged purely by the proof's byte size, large aggregated proofs would be under-priced relative to the CPU they cost. Monero therefore applies a clawback: for transactions with many outputs, it adds back a weight term so the fee tracks actual verification cost rather than just serialized size. Contributors changing proof systems or output limits must keep this accounting honest or risk a DoS vector (cheap-to-make, expensive-to-verify transactions).

Audit Checklist

• Exact, complete Fiat–Shamir transcript (no missing/extra terms).
• Generators derived deterministically; reject malformed/non-canonical inputs.
• Batch verification uses fresh randomness per proof (a fixed weight breaks soundness).
• Weight/clawback accounting matches real verification cost.

Next: the human-facing cryptography that trips people up — Multisig, the Janus Attack & the Burning Bug.