Bulletproofs

Imagine you want to prove your bank balance is above zero — but you refuse to show anyone the actual number. Can you do it? In everyday life, you'd rely on a trusted bank to vouch for you. In cryptography, you can do it alone, with mathematics.

Bulletproofs are a family of zero-knowledge range proofs introduced by Bünz, Bootle, Boneh, Poelstra, Wuille, and Maxwell in 2017. They answer a precise question: given a commitment (a cryptographic lock that hides a number), can you convince a verifier that the hidden value lies in the range [0, $2^{n}$) — without revealing the value itself, and without needing any trusted party to set up the system?

The answer is yes, and the proof is remarkably short: only O(log n) elements, compared to the $O(n)$ you'd need naively. That brevity is what puts the "bullet" in Bulletproofs — small enough to fit inside a blockchain transaction.

The core building block is the Pedersen commitment: C = v·G + r·H, where G and H are public elliptic-curve points, v is the secret value, and r is a random blinding factor. C hides v perfectly (you can't learn v from C alone), yet it is binding — once you publish C, you cannot later claim it commits to a different value. The range proof then shows, without opening C, that 0 ≤ v < $2^{n}$.

Pick a secret value and a bit width. The demo will commit to it, then show the key step in a range proof: decomposing the value into bits and verifying each bit commitment is 0 or 1.

<p class="hint">
  {{hint}}
</p>
<div class="controls">
  <label>{{label_secret}} <input type="number" id="val" value="42" min="0" max="255"></label>
  <label>{{label_bits}} <select id="bits">
    <option value="4">{{opt_4}}</option>
    <option value="6">{{opt_6}}</option>
    <option value="8" selected>{{opt_8}}</option>
  </select></label>
  <button id="run" type="button">{{btn_generate}}</button>
</div>
<div id="out"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.controls { display: flex; flex-wrap: wrap; gap: .6rem; align-items: center; margin-bottom: 1rem; }
label { display: flex; align-items: center; gap: .4rem; font-weight: 600; font-size: .88rem; }
input[type=number] { width: 72px; padding: .3rem .5rem; border: 1px solid #adb1b8; border-radius: 6px; font-size: .88rem; }
select { padding: .3rem .5rem; border: 1px solid #adb1b8; border-radius: 6px; font-size: .88rem; }
button { font: 600 13px system-ui; padding: .4rem .9rem; background: #1d3557; color: #fff;
         border: 1px solid #1d3557; border-radius: 7px; cursor: pointer; }
#out { display: flex; flex-direction: column; gap: .5rem; }
.phase { background: #f0f4f8; border-radius: 8px; padding: .6rem .8rem; }
.phase h3 { margin: 0 0 .4rem; font-size: .9rem; color: #1d3557; }
.phase p  { margin: 0; line-height: 1.5; font-size: .84rem; }
.bit-row { display: flex; flex-wrap: wrap; gap: 4px; margin-top: .35rem; }
.bit { display: inline-flex; align-items: center; justify-content: center;
       width: 36px; height: 36px; border-radius: 6px; font: 700 13px ui-monospace, monospace;
       border: 1px solid #cdd9e3; }
.bit-0 { background: #e8eef3; color: #1d3557; }
.bit-1 { background: #1d3557; color: #fff; }
.commit-row { font: 12px ui-monospace,monospace; word-break: break-all; color: #444; margin-top:.3rem; }
.ok   { color: #0a7d33; font-weight: 700; }
.bad  { color: #c92f3c; font-weight: 700; }
.summary { background: #e6f4ea; border-radius: 8px; padding: .6rem .8rem; font-size: .88rem; }
.summary.fail { background: #fde8e8; }

// Code not found

Notice the two roles. The prover knows the secret; they produce bit commitments and prove each one is binary. The verifier only sees the commitments — they can check every claim without ever learning the hidden number. This asymmetry — easy to verify, hard to fake — is the engine of zero-knowledge proofs and connects directly to the hardness studied in factoring and discrete logarithms.

Bulletproofs are not magic — their security and efficiency come from a precise chain of ideas.

Status: proven secure under the discrete-logarithm assumption (Bünz et al., 2017). There is no trusted setup, no trapdoor that a ceremony participant could exploit.

• Naive range proof: to show v < $2^{n}$, commit to each of the n bits of v separately and prove each commitment is 0 or 1. That works, but produces n proof elements — too large for a blockchain.
• Inner product argument: the key insight is that the n bit-checks can be folded recursively into a single inner-product relation. Each folding step halves the problem, turning $O(n)$ proof elements into $O(\log n)$. The prover and verifier run a O(log n)-round interactive protocol, which is then made non-interactive via the Fiat–Shamir heuristic (replacing the verifier's random challenges with a hash).
• Proof size: for n = 64 bits, a Bulletproof is about 600 bytes — roughly 16× smaller than earlier range proofs. Aggregating m proofs costs only an extra $O(\log m)$ rather than $O(m \cdot n)$.
• Verification cost: $O(n)$ scalar multiplications on an elliptic curve. Slower than checking a simple signature, but fast enough for real transaction validation.
• Soundness: a cheating prover who commits to v ≥ $2^{n}$ cannot pass the verification without solving the discrete-logarithm problem on the chosen curve — believed to require exponential time with today's algorithms.

The construction is a beautiful example of recursive proof compression: a hard problem (prove a range) is transformed into a linear algebra relation, then squashed logarithmically with no loss of soundness.

A proof that a hidden number is non-negative turns out to be the missing piece in many privacy-preserving systems:

• Confidential transactions: Monero adopted Bulletproofs in 2018 (replacing earlier ring-CT range proofs), cutting average transaction size by ~80% and fees dramatically. The Mimblewimble protocol uses them in Grin and Beam for fully private payment channels.
• Verifiable computation: the inner-product argument at the heart of Bulletproofs generalizes to proving arbitrary arithmetic circuits, not just range checks. This makes Bulletproofs a building block for more expressive zero-knowledge virtual machines.
• Anonymous credentials: showing "my age is ≥ 18" without revealing your birthdate is a range proof. Bulletproofs make such credentials compact enough for real identity systems.
• Threshold signatures and MPC: range proofs prevent participants in a multi-party computation from contributing out-of-range inputs that could bias the result.
• Regulatory compliance: a company can prove a financial quantity (e.g., a reserve ratio) exceeds a threshold without publishing its exact books — auditability without full disclosure.

Bulletproofs sit in the broader family of succinct non-interactive proofs. Related schemes like Groth16 and PLONK offer constant-size proofs but require a trusted setup; SNARKs based on pairings trade setup cost for even shorter proofs. Bulletproofs occupy the sweet spot of no setup, logarithmic size — which is why they dominate in open, permissionless blockchains.

Bulletproofs crystallize a remarkable idea: you can convince a stranger that a hidden number satisfies a constraint, while revealing nothing else. The proof is short enough to live on a blockchain, secure under a standard cryptographic assumption, and requires no ceremony or trusted third party.

The technique — fold a big problem into a smaller one, repeat until trivial, then collapse the interaction with a hash — is a template that keeps reappearing in modern cryptography. Understanding Bulletproofs is a gateway to the richer world of zero-knowledge proofs and the computational hardness results that make privacy possible.

Privacy and verifiability, once thought to be opposites, turn out to coexist — as long as the discrete-logarithm problem stays hard.