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 [\(a\),\(b\)].
Range Proof for a range from \(a\) to \(b\) using CSS08 |
Method
The method involves:
With this, the Verifier creates a number of signatures for the values in the range. Peggy then just has to sign her value to show that she has a value in this range. This will be in the form of a blinded signature.
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.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:
Proof valid: 8 is in the range 2 to 10 Verifier proof: 3185f25e98e7a0088b1f80627aa3bce7cba5a599fb3fe8997e3bfcf5404872aa3d3efe7ed13b71e9402d35c6ebc36dda5df11d5dae3e78cefa7b3895369a45ac71789173223723f02a216028c98f2da4c6672288b2a22b0aa4aab51bc3ce276386c3b02c5c383a7d2242aaa81d55debfc7ebd6045647c323d50583f086f993856e3ac47d48f89e17045fad2129aa8228d66fee501aefe2b1e2cd77893b5b3dac672fa1415ab0331239cd94fa27fefd70cd4bc14cfe06c7611e9f262add19b355c801000000000000000002000000000000000000
and for:
Proof invalid: 60 is NOT in the range 2 to 10
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.