Confidential transactions for dummies pt 2 - Borromean Range Proofs
Why are range proofs important?
In the previous post, we discussed pedersen commitments and how they hide transaction amounts while still allowing balances to add up correctly. We then touched on the topic of how one can fake 2 outputs that cancel out to spend more money than they have. Range proofs are the patch for this. They let you prove that committed values stay within sane bounds without revealing the values themselves. Without range proofs, confidential transactions don’t work.
The high level details
The flavor of range proofs we’re using is borromean range proofs. Borromean range proofs bring in a new cryptographic construct called ring signatures. Ring signatures let a signer within a group of public keys sign on behalf of the group without exposing themself as the signer. If you like analogies, you can think of this as a police lineup: the verifier knows the real signer is in the lineup, but can’t tell which individual it was. To motivate its use within a range proof, let’s take a look at a somewhat naive solution.
Naive approach
Imagine we have a list of pedersen commitments where each commitment is a curve point C generated like so:
C = vG + bH
What’s cool about curve points is that any point can be treated as a public key in secp256k1, even C. To sign for C I would need to know its discrete log with respect to G, which means I’d need to find a value c such that C = cG. Unfortunately I don’t have a scalar c in C = cG so I can’t actually sign for C.
I can sign for the public keys derived from the terms of C though since I know the private keys are v and b respectively. We’ll use this to our advantage later on. Now let’s use this concept to make a rudimentary range proof where we’ll prove v is in the range of 1 to 2.
One way I can prove that the value v in my pedersen commitment is either ‘1’ or ‘2’ is to make a scheme with ring signatures using public keys where all of the public keys are derived from C.
Each public key is generated by taking C and subtracting a value pG where p is represents a possible value we’re trying to prove our value v might assume. So if I’m trying to prove v in C = v*G + b*H is either 1 or 2, I will make 2 public keys C - 1*G and C - 2*G.
What does this scheme do for us?
If I’m not lying about my value being 1 or 2, one of my derived public keys will subtract the correct value, allowing me to sign with the pure H multiple b*H.
For example, if my value v is 1, then the first term in the list of public keys would evaluate to bH. This is because C = 1*G + bH and if we replace C in C - (1*G), we get (1*G + bH) - 1*G = bH.
Meanwhile I could never sign for the public key X = C - 2*G because I don’t know the discrete log for the resulting point X. 2*G won’t cancel out one of the terms I know, and I’d need to solve the elliptic curve discrete log problem to find x in x*G = X.
Since we’re utilizing a ring signature scheme, I can sign for all the public keys as a group and not reveal to an outside observer which public key subtracted the correct value.
Thinking more broadly, we can use this strategy for an arbitrary number of values from 1 to n, instead of 1 to 2 like in our toy example. The downside to this scheme is that it requires additional data for every possible value added. The bigger the range, the bigger the signature size grows. This led researchers to the question of whether the size for this scheme could be shrunk down and, lucky for us, the answer was yes.
Binary decomposition
The path to reducing the data of the naive scheme in the last section is through arithmetic. Researchers figured the difficulty of mathematically identifying the signer in a ring signature doesn’t get reduced if we reduce the number of partipants. So lets do that.
Imagine we have a ring signature for a naive range proof where we’re trying to prove a pedersen commitment C contains a value v (in C = v*G + b*H), where v is either 0 or 1. The public keys for this would be C - 0*G or C - 1*G.
Now imagine we made a second ring for a pedersen commitment C2 where the possible values are 0 or 2. A cool way to link these 2 pedersen commitments, C and C2, is to think about the range of the sum of the vs in these 2 commitments. Since the first pedersen commitment has v = 0 or 1, and the second pedersen commitment has v = 0 or 2, the lowest the sum of these values (aka the v terms in the pedersen commitments) can be is 0, and the highest the sum of these values can be is 3.
Now think of the case where we can make each ring signature be a range proof for 0 or a power of 2. Then when we can break apart a pedersen commitment with a large value v into new pedersen commitments that have new vs that sum to the old v. Just to reiterate, the additional requirement is that the new commitments can only have v be a power of 2.
Now you can think of each ring signature as bits that can commit to a power of 2 being ‘on’ or ‘off’. For example, say we were signing a range proof proving a value in a pedersen commitment was between 0 and 3. In this case, we sign for the ‘on’ value of ring signatures that contain a v with a power of 2 present in the binary representation of 3. So instead of one ring proving “v is one of {0,1,2,3}”, we’re using 2 to prove the 2^0 bit is 0 or 1 and the 2^1 bit is 0 or 1.
We will also have to split b, but b doesn’t have to get split into its binary representation. We just need to make sure we split b up into n parts, where n is the number of rings we would like to use (n is log_2(v) because it also represent the number of bits needed to represent v). These bs should actually be chosen somewhat randomly with the method I previously described when choosing blinding coefficients for commitments on a transaction’s outputs (in part 1). We can make all numbers random except the last one, and the last number can be chosen to make the sum equal b.
For intuition about this multi-ring approach, we’re saving space because the number of values we’re able to prove exponentially scales with the number of rings (just like adding a bit to series of bits lets us represent twice the amount of numbers). The key observation is that it’s easier to represent bits than exhaustively represent every number.
With separate independent ring signatures, someone could mix-and-match valid signatures from different signing sessions. Borromean ring signatures bind the rings together so they’re all bound to a single signing event. With separate independent ring signatures, someone could mix-and-match valid signatures from different signing sessions (akin to vulnerabilities to CBC-style encryption).