This page implements the CSS08 method, and which is defined in the "Efficient Protocols for Set Membership and Range Proofs" paper [1]. With this, the 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,\(u^l\)]. If we have \(2^3\), we will have a range [0,8].
Range Proof for a range from 0 to \(u^l\) using CSS08 |
Method
In discrete logs, the method involves:
Overall, Peggy creates a key pair, and signs of the values in the range with her private key.
With the BN256 curve we have base points of \(G_1\) and \(G_2\). For the Pedersen Commitment, Peggy computes a point of \(H\) and using a random value of \(h\) to give:
\(H=h.G_2\)
For a value of \(x\), Peggy then computes the commitment of \(C\):
\(C = x.G_2+r.h\)
Peggy can now generate the proof. First Peggy generates a random value (\(m\) and computes:
\(D=m.H\)
Coding
The following is some simple coding to prove the method:
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) cm, _ := ccs08.Commit(x, r, H) //Proof generated by prover proof, err := prover.ProveUL(x, r, cm) 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\n") } }
A sample run is:
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:
Proof invalid: 60 is NOT in the range 0 to 9
Reference
[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.