Bulletproofs: range proofs without a trusted setup (2018)

Confidential transactions hide amounts in Pedersen commitments \(V = g^v h^\gamma\), which add: inputs balance outputs if the commitments’ product does. But the arithmetic is modulo the group order, so an output of \(-1000\) would mint coins unless every amount is proved to lie in \([0, 2^n)\). Bünz, Bootle, Boneh, Poelstra, Wuille and Maxwell reduced the range check to one inner product \(t = \langle l, r \rangle\), and proved the inner product by halving the vectors each round, sending two group elements per halving. The proof is

\[2 \log_2 n + 4 \text{ group elements and } 5 \text{ scalars},\]

with generators hashed into the group: no trusted setup. Monero adopted Bulletproofs in 2018, cutting its transaction sizes by about 80%.

from dataclasses import replace

import matplotlib.pyplot as plt

import blockchainkit as bk

A confidential transfer that balances

G = bk.crypto.TEACHING_GROUP
inputs = bk.proofs.range_commitment(500, 11)
outputs = [bk.proofs.range_commitment(320, 5), bk.proofs.range_commitment(180, 6)]
assert inputs == outputs[0] * outputs[1] % G.p  # Commitments multiply as amounts add.
proofs = [bk.proofs.range_proof(v, b, 32, seed=i) for i, (v, b) in enumerate([(320, 5), (180, 6)])]
assert all(bk.proofs.verify_range_proof(proof, 32) for proof in proofs)
print("both outputs proved in [0, 2**32) without revealing them")

both outputs proved in [0, 2**32) without revealing them

Minting from a negative output is impossible

500 = 1500 + (-1000): the commitments balance modulo q, but -1000 is q - 1000, far outside the range, and no proof exists for it.

negative = G.q - 1000
assert bk.proofs.range_commitment(1500, 5) * bk.proofs.range_commitment(negative, 6) % G.p == inputs
try:
    bk.proofs.range_proof(negative, 6, 32)
except ValueError as error:
    print("proving -1000:", error)
forged = bk.proofs.range_proof(1000, 6, 32)  # A proof for +1000 does not transfer.
assert not bk.proofs.verify_range_proof(
    replace(forged, commitment=bk.proofs.range_commitment(negative, 6)), 32
)

proving -1000: value must be below 2**32

Logarithmic size

bits = [2, 4, 8, 16, 32, 64]
sizes = []
for n in bits:
    proof = bk.proofs.range_proof(2**n - 1, 3, n)
    assert bk.proofs.verify_range_proof(proof, n)
    sizes.append(sum(proof.size))
print("elements sent:", dict(zip(bits, sizes, strict=True)))

fig, ax = plt.subplots(figsize=(7, 4.5))
ax.plot(
    bits, [4 * n for n in bits], "o-", color="#dc2626", label="one commitment and proof per bit"
)
ax.plot(bits, sizes, "o-", color="#2563eb", label="Bulletproofs")
ax.set_xscale("log", base=2)
ax.set(xlabel="range bits n", ylabel="group elements and scalars sent")
ax.set_title("Range proofs in 2 log2 n + 9 elements")
ax.legend()
fig.tight_layout()

plt.show()

elements sent: {2: 11, 4: 13, 8: 15, 16: 17, 32: 19, 64: 21}

Exercise

Prove that a value lies in [0, 1000) rather than a power-of-two range: prove that both v and v + 2**16 - 1000 lie in [0, 2**16). A worked solution is in Exercises: proof systems.