Range Proofs For Zero to u^l and for A to B
Range Proofs For Zero to u^l and for A to B
One of the most interesting interviews I have had was with Torben P Pedersen:
Overall, it was Torben who created the Pedersen Commitment, and which is a way of blinding a transaction to keep the value committed private. In this article, we will use the Pedersen Commitment to blind a data value so that we can prove a proof that something is in a given range.
Why might we need to blind a value? Well, why do we need to know how much someone has in their bank account before they purchase something? A more privacy-aware approach is to provide proof that you have enough money to pay for something. For example, if you were buying a Porche for $30,000, and you had $35,000 in your bank account, you could provide the seller with a proof that you had enough money in your account to pay for the car, but if the car cost $35,500, you could not provide a valid proof.
The Pedersen Commitment
In the Pedersen Commitment we take two large prime numbers (p and q) and we create a generator value (g) which is of the order of q and a subgroup of Z∗p. Then s becomes a secret from 0 to Zq, and we calculate h=g^s(mod p). The values of (p,q,g,h) are public values.
The sender now creates a commitment for a message (m) and with a random number (r):
The sender can then send c to the receiver. Next, the sender will then reveal m and r for the commitment, and the receiver verifies with:
If the values match, the sender has proven the commitment to the receiver. With the Pedersen Commitment we hide the message that is to be revealed, and where the recipient will not know the message until we reveal it.
These days, rather than discrete log methods, we use elliptic curve. In this case, we would define h as the point:
h=s.G
and where s is a secret scalar value, and G is a base point. The commitment would then be:
c = m.G + r.H
and where H is a point chosen on the curve.
Range Proof using the CSS08 method for 0 to u^l
In 2008, Camanish et al defined the CSS08 method in the “Efficient Protocols for Set Membership and Range Proofs” paper [1]. It is a classic paper, and outlines three main methods: how we can determine if an element is in a set, how we can determine if an element is in a range from 0 to u^l; and how we can determine if an element is in the range of a to b.
I have outlined the proof that an element is in a set here:
https://asecuritysite.com/bulletproof/go_bullet3
For the range proof, verifier (Victor) sends a Boneh-Boyen Signature (BBS) of every element in a set. The prover (Peggy) then gets the signature for the particular element for which C is a commitment. Peggy then blinds the required signature and gives a proof of knowledge that she has the signature on the committed element. In this case we will prove if x is in the range [0,ul]. If we have 23, we will have a range [0,8].
The following is some simple coding to prove the method [here]:
package main
import (
"crypto/rand"
"fmt"
"math/big"
"os"
"strconv"
"math"
"github.com/blockchain-research/crypto/bn256"
"github.com/blockchain-research/crypto/ccs08"
)
func GetBigInt(value string) *big.Int {
i := new(big.Int)
i.SetString(value, 10)
return i
}
func powInt(x, y int) int {
return int(math.Pow(float64(x), float64(y)))
}
func main() {
xval := 7
a := 2
b := 3
argCount := len(os.Args[1:])
if argCount > 0 {
xval, _ = strconv.Atoi(os.Args[1])
}
if argCount > 1 {
a, _ = strconv.Atoi(os.Args[2])
}
if argCount > 2 {
b, _ = strconv.Atoi(os.Args[3])
}
prover, verifier, err := ccs08.SetupUL(int64(a), int64(b))
if err != nil {
fmt.Printf("failed to setup")
}
//Pedersen commitment
r, _ := rand.Int(rand.Reader, bn256.Order)
x := new(big.Int).SetInt64(int64(xval))
h := GetBigInt("18560948149108576432482904553159745978835170526553990798435819795989606410925")
H := new(bn256.G2).ScalarBaseMult(h)
// Peggy and Victor share H
C, _ := ccs08.Commit(x, r, H)
//Proof generated by prover
proof, err := prover.ProveUL(x, r, C)
if err != nil {
fmt.Printf("failed to prove")
}
//verifier verify the proof
result, err := verifier.VerifyUL(proof)
if err != nil {
fmt.Printf("failed to verify")
}
if result == true {
fmt.Printf("Proof valid: %d is in the range 0 to %d\n\n", xval, powInt(a, b))
fmt.Printf("Proof C=%v\n", proof.C)
fmt.Printf("Proof D=%v\n", proof.D)
fmt.Printf("Proof V=%v\n", proof.V)
} else {
fmt.Printf("Proof invalid: %d is NOT in the range 0 to %d\n\n", xval, powInt(a, b))
}
}A sample run is [here]:
Proof valid: 6 is in the range 0 to 9
Proof C=bn256.G2((45001635625537763008373100672985197538285597967531765652162973880849352032135,51568007023113729868506346692476702014832924656832989008577036614733504737071), (25642161009006184649861088246124086434708190472698595987000955622597921959898,64102276988974997532363278487055762899741716202935842262865871333407847390504), (43584818605717687399522646942522158598839752524536701767511775210476460491309,48337318706700315213361038646509308391057426736449015571768998754536307576190))
Proof D=bn256.G2((20128913606613392177065237122119643717370792314225580482150949891681867054895,35777149824615328078951434000951068770818512403074754739437399092192455291129), (25406103321525952854870259816799199266532143816432118531016404738277498947711,58738052536763866806578399856858468989549153690182695169604936301300970375172), (0,1))
Proof V=[bn256.G2((41714914736301950691195562203981725731946673884268357395869035810685032753574,23033334209286927961228958876844704386945494634019403647268317828864105893172), (1751757070540710745945106418480795926649730127326848473555314062703265370488,33993446684112550616446748519057529380763016002020362536660689632219945427745), (29991367321984231788000039879611229779828585391414314154460424577626185551598,41414029805626670771269453851316296839704066067632267161861530045873690037968)) bn256.G2((62768732891846182772909623137787038836546060290913783419751456585598497357026,6795472473844742825982056017301147998480657383073677503950750454514789908838), (33410492274019416582235987837105270820384761390515038171898503683142367384483,54884912165453473447209452276880388254520907687169429093089223253758738111119), (13698274522448780201716413159476468372798515955912956605161073874118363490787,2384761159509989310882688039595417925082764895029399308927795203615959510751))]and for [here]:
Proof invalid: 60 is NOT in the range 0 to 9Range Proof using the CSS08 method for a to b
Camenicsh et al then showed that we can use the method to prove proof of a value between a and b. For this, we can use a modified version of the code [here]:
package main
import (
"crypto/rand"
"fmt"
"math/big"
"os"
"strconv"
"math"
"github.com/blockchain-research/crypto/bn256"
"github.com/blockchain-research/crypto/ccs08"
)
func GetBigInt(value string) *big.Int {
i := new(big.Int)
i.SetString(value, 10)
return i
}
func powInt(x, y int) int {
return int(math.Pow(float64(x), float64(y)))
}
func main() {
xval := 7
a := 2
b := 3
argCount := len(os.Args[1:])
if argCount > 0 {
xval, _ = strconv.Atoi(os.Args[1])
}
if argCount > 1 {
a, _ = strconv.Atoi(os.Args[2])
}
if argCount > 2 {
b, _ = strconv.Atoi(os.Args[3])
}
prover, verifier, err := ccs08.Setup(int64(a), int64(b))
if err != nil {
fmt.Printf("failed to setup")
}
//Pedersen commitment
r, _ := rand.Int(rand.Reader, bn256.Order)
x := new(big.Int).SetInt64(int64(xval))
//Proof generated by prover
proof, err := prover.Prove(x, r)
if err != nil {
fmt.Printf("failed to prove")
}
//verifier verify the proof
result, err := verifier.Verify(proof)
if err != nil {
fmt.Printf("failed to verify")
}
if result == true {
fmt.Printf("Proof valid: %d is in the range %d to %d\n\n", xval, a, b)
} else {
fmt.Printf("Proof invalid: %d is NOT in the range %d to %d\n\n", xval, a, b)
}
}A sample run is [here]:
Proof valid: 8 is in the range 2 to 10
Verifier proof: 3185f25e98e7a0088b1f80627aa3bce7cba5a599fb3fe8997e3bfcf5404872aa3d3efe7ed13b71e9402d35c6ebc36dda5df11d5dae3e78cefa7b3895369a45ac71789173223723f02a216028c98f2da4c6672288b2a22b0aa4aab51bc3ce276386c3b02c5c383a7d2242aaa81d55debfc7ebd6045647c323d50583f086f993856e3ac47d48f89e17045fad2129aa8228d66fee501aefe2b1e2cd77893b5b3dac672fa1415ab0331239cd94fa27fefd70cd4bc14cfe06c7611e9f262add19b355c801000000000000000002000000000000000000and for [here]:
Proof invalid: 60 is NOT in the range 2 to 10Conclusions
And, there you go, three core contributions in a single research paper … just genius!
References
[1] Camenisch, J., Chaabouni, R., & Shelat, A. (2008, December). Efficient protocols for set membership and range proofs. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 234–252). Berlin, Heidelberg: Springer Berlin Heidelberg.
[2] github.com/blockchain-research/crypto