Intuitions Behind the Range Proofs of Bulletproof: Part 1

cryptography, security, and random thoughts

Hey! I'm David, cofounder of zkSecurity, research advisor at Archetype, and author of the Real-World Cryptography book. I was previously a cryptography architect of Mina at O(1) Labs, the security lead for Libra/Diem at Facebook, and a security engineer at the Cryptography Services of NCC Group. Welcome to my blog about cryptography, security, and other related topics.

In this video I quickly go over the amazing post from the dalek implementation of bulletproof, which itself goes over the range proof protocol of Bulletproofs: Short Proofs for Confidential Transactions and More.

Note that if you don’t know what bulletproof or IPA are, you can check my previous writing on the subject.

To summarize, the way I see the rangeproof protocol built on top of bulletproof/IPA is that you’re proving execution of a circuit with:

input $A$ := a (hiding) commitment $a_{L}$ to the bits of $v$ , and an intermediary value $a_{R} = a_{L} - 1$
expected output := something based on $V$ , the (hiding) commitment to $v$

if you can prove the execution of that circuit (which essentially checks that $a_{L}$ values are bits, and that they are the correct bit decomposition of $v$ ) correctly, then you convinced the verifier that $v$ is n-bit.

The circuit is written as a single inner product $⟨ l, r ⟩ = t$ where:

$l (x), r (x)$ are intermediary values in our circuit, computed from $a_{L}$ and $a_{R}$ respectively to embody the circuit logic (unlike other intermediary values, these can be computed by the verifier directly)
$t (x)$ is an intermediary value that contains the expected output, so we need to prove how it connects with the expected output

Then it is rewritten as blinded polynomials $⟨ l (x), r (x) ⟩ = t (x)$ where the blinding factors are hidden behind powers of $x$ in order to hide the real computation in the constant terms. That is we still have $⟨ l (0), r (0) ⟩ = t (0)$ .

The verifier samples a random evaluation point $x$ in order to check that $⟨ l (x), r (x) ⟩ = t (x)$ at a single point (which shows that it is most likely true everywhere, relying on our good old Schwartz-Zippel lemma).

the proof that the inner product $⟨ l (x), r (x) ⟩ = t (x)$ itself is delegated to the IPA proof system, so most of the complexity there is to understand:

how the intermediary variables $l (x), r (x)$ are calculated from the committed inputs ( $a_{L}$ and $a_{R}$ )
how the result of the inner product $t (0)$ matches what is expected

The blinding is what makes it more complicated, and we’ll talk about that in part2.

EDIT: part 2 is here.