Bulletproofs and RangeproofsBulletproofs were created in 2017 by Stanford’s Applied Cryptography Group (ACG) [paper]. They define a zero-knowledge proof and where a value can be checked to see it lies within a given range. The name of "bulletproofs" is defined as they are short like a bullet, and with bulletproof security assumptions. In the following we define the size of the bit vector and then check to see if a value is in that range - a range proof. If the bit vector is 8 bits long, then we will prove that the value lies between 0 and 255. A value larger than this will fail. The test is thus whether \(x \in [0,2^{n} - 1]\), and where \(n\) is the number of bits in the bit vector. |
Method
A confidential transaction can be made private by using the Pedersen Commitment. If the value we want to keep secret is \(x\) then if we take a point on the elliptic curve (\(H\)), we get a public key point of:
\(T_x=xH\)
If \(x\) is a small value, then this will not hide the value of \(x\) as Eve could simply compute of the low values of \(x\) and brute force the value of \(T_x\).
The Pedersen Commit can then be used to hide the value of \(x\) by adding a random value (\(r\)). Now we pick another point (\(G\)) and a large random value (\(r\)). Now the commitment (\(C(x,r)\)) becomes:
\(C(x,r) = xH + rG\)
Now we cannot determine \(x\) as we would need \(r\). If Bob saves this transaction, he could keep \(r\) in his wallet, and then reveal to someone when required.
The value of \(x\) is thus know as the blinding value. Let’s say that we have a transaction value of \(v\), we can now define this as a point on the elliptic curve (H) as:
\(C = v \times H\)
If we have three transactions (\(v_1\), \(v_2\) and \(v_3\)), we can create a sum total of:
\(\text{Total} = v_1 \times H + v_2 \times H+ v_3 \times H= (v_1+v_2+v_3) \times H\)
We can thus determine the sum of the transactions. But we could eventually find-out the values of \(v_1\), \(v_2\) and \(v_3\), as they would always appear as the same value when multiplied by G. We can now add a blinding factor by adding a second point on another elliptic curve (H) and a private key (r).
A transaction value is then (as defined as a Pedersen Commitment):
\(v \times H + r \times G\)
Let’s say that Bob has two input values (v1 and v2) and one output value (v3), and where v3= v1+v2. We can then create a blinding factor for each transaction:
\((ri_1 \times G + vi_1 \times H) + (ri_2 \times G + vi_2 \times H) = (ro_3 \times G + vo_3 \times H)\)
Then:
\(ri_1 + ri_2 = ro_3\)
In this case if we can prove this, we have proven that the inputs are equal to the outputs.
Within Bulletproofs, we implement a range proof, and where we prove that \(x \in [0,2^{n} - 1]\), and where \(n\) is the number of bits in the bit vector.
Outline
The following is the code [taken from here]:
package main import ( "crypto/elliptic" "crypto/rand" "crypto/sha256" "encoding/binary" "math/big" "os" "fmt" "github.com/btcsuite/btcd/btcec" "math" "strconv" ) var EC CryptoParams var VecLength = 8 type ECPoint struct { X, Y *big.Int } // Equal returns true if points p (self) and p2 (arg) are the same. func (p ECPoint) Equal(p2 ECPoint) bool { if p.X.Cmp(p2.X) == 0 && p2.Y.Cmp(p2.Y) == 0 { return true } return false } // Mult multiplies point p by scalar s and returns the resulting point func (p ECPoint) Mult(s *big.Int) ECPoint { modS := new(big.Int).Mod(s, EC.N) X, Y := EC.C.ScalarMult(p.X, p.Y, modS.Bytes()) return ECPoint{X, Y} } // Add adds points p and p2 and returns the resulting point func (p ECPoint) Add(p2 ECPoint) ECPoint { X, Y := EC.C.Add(p.X, p.Y, p2.X, p2.Y) return ECPoint{X, Y} } // Neg returns the additive inverse of point p func (p ECPoint) Neg() ECPoint { negY := new(big.Int).Neg(p.Y) modValue := negY.Mod(negY, EC.C.Params().P) // mod P is fine here because we're describing a curve point return ECPoint{p.X, modValue} } type CryptoParams struct { C elliptic.Curve // curve KC *btcec.KoblitzCurve // curve BPG []ECPoint // slice of gen 1 for BP BPH []ECPoint // slice of gen 2 for BP N *big.Int // scalar prime U ECPoint // a point that is a fixed group element with an unknown discrete-log relative to g,h V int // Vector length G ECPoint // G value for commitments of a single value H ECPoint // H value for commitments of a single value } func (c CryptoParams) Zero() ECPoint { return ECPoint{big.NewInt(0), big.NewInt(0)} } func check(e error) { if e != nil { panic(e) } } /* Vector Pedersen Commitment Given an array of values, we commit the array with different generators for each element and for each randomness. */ /* Two Vector P Commit Given an array of values, we commit the array with different generators for each element and for each randomness. */ func TwoVectorPCommit(a []*big.Int, b []*big.Int) ECPoint { if len(a) != len(b) { fmt.Println("TwoVectorPCommit: Uh oh! Arrays not of the same length") fmt.Printf("len(a): %d\n", len(a)) fmt.Printf("len(b): %d\n", len(b)) } commitment := EC.Zero() for i := 0; i < EC.V; i++ { commitment = commitment.Add(EC.BPG[i].Mult(a[i])).Add(EC.BPH[i].Mult(b[i])) } return commitment } /* Vector Pedersen Commitment with Gens Given an array of values, we commit the array with different generators for each element and for each randomness. We also pass in the Generators we want to use */ func TwoVectorPCommitWithGens(G, H []ECPoint, a, b []*big.Int) ECPoint { if len(G) != len(H) || len(G) != len(a) || len(a) != len(b) { fmt.Println("TwoVectorPCommitWithGens: Uh oh! Arrays not of the same length") fmt.Printf("len(G): %d\n", len(G)) fmt.Printf("len(H): %d\n", len(H)) fmt.Printf("len(a): %d\n", len(a)) fmt.Printf("len(b): %d\n", len(b)) } commitment := EC.Zero() for i := 0; i < len(G); i++ { modA := new(big.Int).Mod(a[i], EC.N) modB := new(big.Int).Mod(b[i], EC.N) commitment = commitment.Add(G[i].Mult(modA)).Add(H[i].Mult(modB)) } return commitment } // The length here always has to be a power of two func InnerProduct(a []*big.Int, b []*big.Int) *big.Int { if len(a) != len(b) { fmt.Println("InnerProduct: Uh oh! Arrays not of the same length") fmt.Printf("len(a): %d\n", len(a)) fmt.Printf("len(b): %d\n", len(b)) } c := big.NewInt(0) for i := range a { tmp1 := new(big.Int).Mul(a[i], b[i]) c = new(big.Int).Add(c, new(big.Int).Mod(tmp1, EC.N)) } return new(big.Int).Mod(c, EC.N) } func VectorAdd(v []*big.Int, w []*big.Int) []*big.Int { if len(v) != len(w) { fmt.Println("VectorAdd: Uh oh! Arrays not of the same length") fmt.Printf("len(v): %d\n", len(v)) fmt.Printf("len(w): %d\n", len(w)) } result := make([]*big.Int, len(v)) for i := range v { result[i] = new(big.Int).Mod(new(big.Int).Add(v[i], w[i]), EC.N) } return result } func VectorHadamard(v, w []*big.Int) []*big.Int { if len(v) != len(w) { fmt.Println("VectorHadamard: Uh oh! Arrays not of the same length") fmt.Printf("len(v): %d\n", len(w)) fmt.Printf("len(w): %d\n", len(v)) } result := make([]*big.Int, len(v)) for i := range v { result[i] = new(big.Int).Mod(new(big.Int).Mul(v[i], w[i]), EC.N) } return result } func VectorAddScalar(v []*big.Int, s *big.Int) []*big.Int { result := make([]*big.Int, len(v)) for i := range v { result[i] = new(big.Int).Mod(new(big.Int).Add(v[i], s), EC.N) } return result } func ScalarVectorMul(v []*big.Int, s *big.Int) []*big.Int { result := make([]*big.Int, len(v)) for i := range v { result[i] = new(big.Int).Mod(new(big.Int).Mul(v[i], s), EC.N) } return result } /* InnerProd Proof This stores the argument values */ type InnerProdArg struct { L []ECPoint R []ECPoint A *big.Int B *big.Int Challenges []*big.Int } func GenerateNewParams(G, H []ECPoint, x *big.Int, L, R, P ECPoint) ([]ECPoint, []ECPoint, ECPoint) { nprime := len(G) / 2 Gprime := make([]ECPoint, nprime) Hprime := make([]ECPoint, nprime) xinv := new(big.Int).ModInverse(x, EC.N) // Gprime = xinv * G[:nprime] + x*G[nprime:] // Hprime = x * H[:nprime] + xinv*H[nprime:] for i := range Gprime { //fmt.Printf("i: %d && i+nprime: %d\n", i, i+nprime) Gprime[i] = G[i].Mult(xinv).Add(G[i+nprime].Mult(x)) Hprime[i] = H[i].Mult(x).Add(H[i+nprime].Mult(xinv)) } x2 := new(big.Int).Mod(new(big.Int).Mul(x, x), EC.N) xinv2 := new(big.Int).ModInverse(x2, EC.N) Pprime := L.Mult(x2).Add(P).Add(R.Mult(xinv2)) // x^2 * L + P + xinv^2 * R return Gprime, Hprime, Pprime } /* Inner Product Argument Proves that =c This is a building block for BulletProofs */ func InnerProductProveSub(proof InnerProdArg, G, H []ECPoint, a []*big.Int, b []*big.Int, u ECPoint, P ECPoint) InnerProdArg { //fmt.Printf("Proof so far: %s\n", proof) if len(a) == 1 { // Prover sends a & b //fmt.Printf("a: %d && b: %d\n", a[0], b[0]) proof.A = a[0] proof.B = b[0] return proof } curIt := int(math.Log2(float64(len(a)))) - 1 nprime := len(a) / 2 //fmt.Println(nprime) //fmt.Println(len(H)) cl := InnerProduct(a[:nprime], b[nprime:]) // either this line cr := InnerProduct(a[nprime:], b[:nprime]) // or this line L := TwoVectorPCommitWithGens(G[nprime:], H[:nprime], a[:nprime], b[nprime:]).Add(u.Mult(cl)) R := TwoVectorPCommitWithGens(G[:nprime], H[nprime:], a[nprime:], b[:nprime]).Add(u.Mult(cr)) proof.L[curIt] = L proof.R[curIt] = R // prover sends L & R and gets a challenge s256 := sha256.Sum256([]byte( L.X.String() + L.Y.String() + R.X.String() + R.Y.String())) x := new(big.Int).SetBytes(s256[:]) proof.Challenges[curIt] = x Gprime, Hprime, Pprime := GenerateNewParams(G, H, x, L, R, P) //fmt.Printf("Prover - Intermediate Pprime value: %s \n", Pprime) xinv := new(big.Int).ModInverse(x, EC.N) // or these two lines aprime := VectorAdd( ScalarVectorMul(a[:nprime], x), ScalarVectorMul(a[nprime:], xinv)) bprime := VectorAdd( ScalarVectorMul(b[:nprime], xinv), ScalarVectorMul(b[nprime:], x)) return InnerProductProveSub(proof, Gprime, Hprime, aprime, bprime, u, Pprime) } //rpresult.IPP = InnerProductProve(left, right, that, P, EC.U, EC.BPG, HPrime) func InnerProductProve(a []*big.Int, b []*big.Int, c *big.Int, P, U ECPoint, G, H []ECPoint) InnerProdArg { loglen := int(math.Log2(float64(len(a)))) challenges := make([]*big.Int, loglen+1) Lvals := make([]ECPoint, loglen) Rvals := make([]ECPoint, loglen) runningProof := InnerProdArg{ Lvals, Rvals, big.NewInt(0), big.NewInt(0), challenges} // randomly generate an x value from public data x := sha256.Sum256([]byte(P.X.String() + P.Y.String())) runningProof.Challenges[loglen] = new(big.Int).SetBytes(x[:]) Pprime := P.Add(U.Mult(new(big.Int).Mul(new(big.Int).SetBytes(x[:]), c))) ux := U.Mult(new(big.Int).SetBytes(x[:])) //fmt.Printf("Prover Pprime value to run sub off of: %s\n", Pprime) return InnerProductProveSub(runningProof, G, H, a, b, ux, Pprime) } /* Inner Product Verify Given a inner product proof, verifies the correctness of the proof Since we're using the Fiat-Shamir transform, we need to verify all x hash computations, all g' and h' computations P : the Pedersen commitment we are verifying is a commitment to the innner product ipp : the proof */ /* Inner Product Verify Fast Given a inner product proof, verifies the correctness of the proof. Does the same as above except we replace n separate exponentiations with a single multi-exponentiation. */ func InnerProductVerifyFast(c *big.Int, P, U ECPoint, G, H []ECPoint, ipp InnerProdArg) bool { //fmt.Println("Verifying Inner Product Argument") //fmt.Printf("Commitment Value: %s \n", P) s1 := sha256.Sum256([]byte(P.X.String() + P.Y.String())) chal1 := new(big.Int).SetBytes(s1[:]) ux := U.Mult(chal1) curIt := len(ipp.Challenges) - 1 // check all challenges if ipp.Challenges[curIt].Cmp(chal1) != 0 { fmt.Println("IPVerify - Initial Challenge Failed") return false } for j := curIt - 1; j >= 0; j-- { Lval := ipp.L[j] Rval := ipp.R[j] // prover sends L & R and gets a challenge s256 := sha256.Sum256([]byte( Lval.X.String() + Lval.Y.String() + Rval.X.String() + Rval.Y.String())) chal2 := new(big.Int).SetBytes(s256[:]) if ipp.Challenges[j].Cmp(chal2) != 0 { fmt.Println("IPVerify - Challenge verification failed at index " + strconv.Itoa(j)) return false } } // begin computing curIt -= 1 Pprime := P.Add(ux.Mult(c)) // line 6 from protocol 1 tmp1 := EC.Zero() for j := curIt; j >= 0; j-- { x2 := new(big.Int).Exp(ipp.Challenges[j], big.NewInt(2), EC.N) x2i := new(big.Int).ModInverse(x2, EC.N) //fmt.Println(tmp1) tmp1 = ipp.L[j].Mult(x2).Add(ipp.R[j].Mult(x2i)).Add(tmp1) //fmt.Println(tmp1) } rhs := Pprime.Add(tmp1) //rhs=P+c*ux + L*xw+R*x2i ??29 sScalars := make([]*big.Int, EC.V) invsScalars := make([]*big.Int, EC.V) for i := 0; i < EC.V; i++ { si := big.NewInt(1) for j := curIt; j >= 0; j-- { // original challenge if the jth bit of i is 1, inverse challenge otherwise chal := ipp.Challenges[j] if big.NewInt(int64(i)).Bit(j) == 0 { chal = new(big.Int).ModInverse(chal, EC.N) } // fmt.Printf("Challenge raised to value: %d\n", chal) si = new(big.Int).Mod(new(big.Int).Mul(si, chal), EC.N) } //fmt.Printf("Si value: %d\n", si) sScalars[i] = si invsScalars[i] = new(big.Int).ModInverse(si, EC.N) } ccalc := new(big.Int).Mod(new(big.Int).Mul(ipp.A, ipp.B), EC.N) lhs := TwoVectorPCommitWithGens(G, H, ScalarVectorMul(sScalars, ipp.A), ScalarVectorMul(invsScalars, ipp.B)).Add(ux.Mult(ccalc)) if !rhs.Equal(lhs) { fmt.Println("IPVerify - Final Commitment checking failed") fmt.Printf("Final rhs value: %s \n", rhs) fmt.Printf("Final lhs value: %s \n", lhs) return false } return true } // from here: https://play.golang.org/p/zciRZvD0Gr with a fix func PadLeft(str, pad string, l int) string { strCopy := str for len(strCopy) < l { strCopy = pad + strCopy } return strCopy } func STRNot(str string) string { result := "" for _, i := range str { if i == '0' { result += "1" } else { result += "0" } } return result } func StrToBigIntArray(str string) []*big.Int { result := make([]*big.Int, len(str)) for i := range str { t, success := new(big.Int).SetString(string(str[i]), 10) if success { result[i] = t } } return result } func reverse(l []*big.Int) []*big.Int { result := make([]*big.Int, len(l)) for i := range l { result[i] = l[len(l)-i-1] } return result } func PowerVector(l int, base *big.Int) []*big.Int { result := make([]*big.Int, l) for i := 0; i < l; i++ { result[i] = new(big.Int).Exp(base, big.NewInt(int64(i)), EC.N) } return result } func RandVector(l int) []*big.Int { result := make([]*big.Int, l) for i := 0; i < l; i++ { x, err := rand.Int(rand.Reader, EC.N) check(err) result[i] = x } return result } func VectorSum(y []*big.Int) *big.Int { result := big.NewInt(0) for _, j := range y { result = new(big.Int).Mod(new(big.Int).Add(result, j), EC.N) } return result } type RangeProof struct { Comm ECPoint A ECPoint S ECPoint T1 ECPoint T2 ECPoint Tau *big.Int Th *big.Int Mu *big.Int IPP InnerProdArg // challenges Cy *big.Int Cz *big.Int Cx *big.Int } /* Delta is a helper function that is used in the range proof \delta(y, z) = (z-z^2)<1^n, y^n> - z^3<1^n, 2^n> */ func Delta(y []*big.Int, z *big.Int) *big.Int { result := big.NewInt(0) // (z-z^2)<1^n, y^n> z2 := new(big.Int).Mod(new(big.Int).Mul(z, z), EC.N) t1 := new(big.Int).Mod(new(big.Int).Sub(z, z2), EC.N) t2 := new(big.Int).Mod(new(big.Int).Mul(t1, VectorSum(y)), EC.N) // z^3<1^n, 2^n> z3 := new(big.Int).Mod(new(big.Int).Mul(z2, z), EC.N) po2sum := new(big.Int).Sub(new(big.Int).Exp(big.NewInt(2), big.NewInt(int64(EC.V)), EC.N), big.NewInt(1)) t3 := new(big.Int).Mod(new(big.Int).Mul(z3, po2sum), EC.N) result = new(big.Int).Mod(new(big.Int).Sub(t2, t3), EC.N) return result } // Calculates (aL - z*1^n) + sL*x func CalculateL(aL, sL []*big.Int, z, x *big.Int) []*big.Int { result := make([]*big.Int, len(aL)) tmp1 := VectorAddScalar(aL, new(big.Int).Neg(z)) tmp2 := ScalarVectorMul(sL, x) result = VectorAdd(tmp1, tmp2) return result } func CalculateR(aR, sR, y, po2 []*big.Int, z, x *big.Int) []*big.Int { if len(aR) != len(sR) || len(aR) != len(y) || len(y) != len(po2) { fmt.Println("CalculateR: Uh oh! Arrays not of the same length") fmt.Printf("len(aR): %d\n", len(aR)) fmt.Printf("len(sR): %d\n", len(sR)) fmt.Printf("len(y): %d\n", len(y)) fmt.Printf("len(po2): %d\n", len(po2)) } result := make([]*big.Int, len(aR)) z2 := new(big.Int).Exp(z, big.NewInt(2), EC.N) tmp11 := VectorAddScalar(aR, z) tmp12 := ScalarVectorMul(sR, x) tmp1 := VectorHadamard(y, VectorAdd(tmp11, tmp12)) tmp2 := ScalarVectorMul(po2, z2) result = VectorAdd(tmp1, tmp2) return result } /* RPProver : Range Proof Prove Given a value v, provides a range proof that v is inside 0 to 2^64-1 */ func RPProve(v *big.Int) RangeProof { rpresult := RangeProof{} PowerOfTwos := PowerVector(EC.V, big.NewInt(2)) //??????? if v.Cmp(big.NewInt(0)) == -1 { fmt.Println("Value is below range! Not proving") os.Exit(1) } //??????? if v.Cmp(new(big.Int).Exp(big.NewInt(2), big.NewInt(int64(EC.V)), EC.N)) == 1 { fmt.Println("Value is above range! Not proving.") os.Exit(1) } // ????? gamma, err := rand.Int(rand.Reader, EC.N) check(err) comm := EC.G.Mult(v).Add(EC.H.Mult(gamma)) rpresult.Comm = comm //Comm = v*G + gamma*H // break up v into its bitwise representation //aL := 0 //?????? aL := reverse(StrToBigIntArray(PadLeft(fmt.Sprintf("%b", v), "0", EC.V))) //?? aR := VectorAddScalar(aL, big.NewInt(-1)) //????35 alpha, err := rand.Int(rand.Reader, EC.N) check(err) A := TwoVectorPCommitWithGens(EC.BPG, EC.BPH, aL, aR).Add(EC.H.Mult(alpha)) rpresult.A = A // ????? //A=(a*G + b*H) + alpha*H sL := RandVector(EC.V) sR := RandVector(EC.V) rho, err := rand.Int(rand.Reader, EC.N) check(err) S := TwoVectorPCommitWithGens(EC.BPG, EC.BPH, sL, sR).Add(EC.H.Mult(rho)) rpresult.S = S // ????? //S=(a*G + b*H) + rho*H chal1s256 := sha256.Sum256([]byte(A.X.String() + A.Y.String())) cy := new(big.Int).SetBytes(chal1s256[:]) rpresult.Cy = cy //???? //Cy = sha256(A) chal2s256 := sha256.Sum256([]byte(S.X.String() + S.Y.String())) cz := new(big.Int).SetBytes(chal2s256[:]) rpresult.Cz = cz //???? //Cz = sha256(S) z2 := new(big.Int).Exp(cz, big.NewInt(2), EC.N) // need to generate l(X), r(X), and t(X)= /* Java code on how to calculate t1 and t2 FieldVector ys = FieldVector.from(VectorX.iterate(n, BigInteger.ONE, y::multiply),q); //powers of y FieldVector l0 = aL.add(z.negate()); FieldVector l1 = sL; FieldVector twoTimesZSquared = twos.times(zSquared); FieldVector r0 = ys.hadamard(aR.add(z)).add(twoTimesZSquared); FieldVector r1 = sR.hadamard(ys); BigInteger k = ys.sum().multiply(z.subtract(zSquared)).subtract(zCubed.shiftLeft(n).subtract(zCubed)); BigInteger t0 = k.add(zSquared.multiply(number)); BigInteger t1 = l1.innerPoduct(r0).add(l0.innerPoduct(r1)); BigInteger t2 = l1.innerPoduct(r1); PolyCommitment polyCommitment = PolyCommitment.from(base, t0, VectorX.of(t1, t2)); */ PowerOfCY := PowerVector(EC.V, cy) // fmt.Println(PowerOfCY) l0 := VectorAddScalar(aL, new(big.Int).Neg(cz)) // l1 := sL r0 := VectorAdd( VectorHadamard( PowerOfCY, VectorAddScalar(aR, cz)), ScalarVectorMul( PowerOfTwos, z2)) r1 := VectorHadamard(sR, PowerOfCY) //calculate t0 t0 := new(big.Int).Mod(new(big.Int).Add(new(big.Int).Mul(v, z2), Delta(PowerOfCY, cz)), EC.N) t1 := new(big.Int).Mod(new(big.Int).Add(InnerProduct(sL, r0), InnerProduct(l0, r1)), EC.N) t2 := InnerProduct(sL, r1) // given the t_i values, we can generate commitments to them tau1, err := rand.Int(rand.Reader, EC.N) check(err) tau2, err := rand.Int(rand.Reader, EC.N) check(err) T1 := EC.G.Mult(t1).Add(EC.H.Mult(tau1)) //commitment to t1 T2 := EC.G.Mult(t2).Add(EC.H.Mult(tau2)) //commitment to t2 rpresult.T1 = T1 //????? //T1 = t1*G + tau1*H rpresult.T2 = T2 //????? //T2 = t2*G + tau2*H chal3s256 := sha256.Sum256([]byte(T1.X.String() + T1.Y.String() + T2.X.String() + T2.Y.String())) cx := new(big.Int).SetBytes(chal3s256[:]) rpresult.Cx = cx //Cx = sha256(T1 + T2) left := CalculateL(aL, sL, cz, cx) right := CalculateR(aR, sR, PowerOfCY, PowerOfTwos, cz, cx) //???????,?????? thatPrime := new(big.Int).Mod( // t(x) = t0 + t1*x + t2*x^2 new(big.Int).Add( t0, new(big.Int).Add( new(big.Int).Mul( t1, cx), new(big.Int).Mul( new(big.Int).Mul(cx, cx), t2))), EC.N) //????? t(x) = that := InnerProduct(left, right) // NOTE: BP Java implementation calculates this from the t_i // = t0 + t1*x + t2*x^2 // thatPrime and that should be equal if thatPrime.Cmp(that) != 0 { fmt.Println("Proving -- Uh oh! Two diff ways to compute same value not working") fmt.Printf("\tthatPrime = %s\n", thatPrime.String()) fmt.Printf("\tthat = %s \n", that.String()) } rpresult.Th = thatPrime //Th = t0 + t1*x + t2*x^2 taux1 := new(big.Int).Mod(new(big.Int).Mul(tau2, new(big.Int).Mul(cx, cx)), EC.N) //t2*x^2 taux2 := new(big.Int).Mod(new(big.Int).Mul(tau1, cx), EC.N) //t1*x taux3 := new(big.Int).Mod(new(big.Int).Mul(z2, gamma), EC.N) //z2*gamma taux := new(big.Int).Mod(new(big.Int).Add(taux1, new(big.Int).Add(taux2, taux3)), EC.N) //taux1+taux2+taux3 rpresult.Tau = taux //Tau = taux1 + taux2 + taux3 mu := new(big.Int).Mod(new(big.Int).Add(alpha, new(big.Int).Mul(rho, cx)), EC.N) rpresult.Mu = mu //Mu = alpha + rho*Cx HPrime := make([]ECPoint, len(EC.BPH)) for i := range HPrime { HPrime[i] = EC.BPH[i].Mult(new(big.Int).ModInverse(PowerOfCY[i], EC.N)) } // for testing tmp1 := EC.Zero() zneg := new(big.Int).Mod(new(big.Int).Neg(cz), EC.N) for i := range EC.BPG { tmp1 = tmp1.Add(EC.BPG[i].Mult(zneg)) } tmp2 := EC.Zero() for i := range HPrime { val1 := new(big.Int).Mul(cz, PowerOfCY[i]) val2 := new(big.Int).Mul(new(big.Int).Mul(cz, cz), PowerOfTwos[i]) tmp2 = tmp2.Add(HPrime[i].Mult(new(big.Int).Add(val1, val2))) } //P1 := A.Add(S.Mult(cx)).Add(tmp1).Add(tmp2).Add(EC.U.Mult(that)).Add(EC.H.Mult(mu).Neg()) P := TwoVectorPCommitWithGens(EC.BPG, HPrime, left, right) //fmt.Println(P1) //fmt.Println(P2) rpresult.IPP = InnerProductProve(left, right, that, P, EC.U, EC.BPG, HPrime) return rpresult } func RPVerify(rp RangeProof) bool { // verify the challenges chal1s256 := sha256.Sum256([]byte(rp.A.X.String() + rp.A.Y.String())) cy := new(big.Int).SetBytes(chal1s256[:]) if cy.Cmp(rp.Cy) != 0 { fmt.Println("RPVerify - Challenge Cy failing!") return false } chal2s256 := sha256.Sum256([]byte(rp.S.X.String() + rp.S.Y.String())) cz := new(big.Int).SetBytes(chal2s256[:]) if cz.Cmp(rp.Cz) != 0 { fmt.Println("RPVerify - Challenge Cz failing!") return false } chal3s256 := sha256.Sum256([]byte(rp.T1.X.String() + rp.T1.Y.String() + rp.T2.X.String() + rp.T2.Y.String())) cx := new(big.Int).SetBytes(chal3s256[:]) if cx.Cmp(rp.Cx) != 0 { fmt.Println("RPVerify - Challenge Cx failing!") return false } // given challenges are correct, very range proof PowersOfY := PowerVector(EC.V, cy) // t_hat * G + tau * H lhs := EC.G.Mult(rp.Th).Add(EC.H.Mult(rp.Tau)) // z^2 * V + delta(y,z) * G + x * T1 + x^2 * T2 rhs := rp.Comm.Mult(new(big.Int).Mul(cz, cz)).Add( EC.G.Mult(Delta(PowersOfY, cz))).Add( rp.T1.Mult(cx)).Add( rp.T2.Mult(new(big.Int).Mul(cx, cx))) if !lhs.Equal(rhs) { fmt.Println("RPVerify - Uh oh! Check line (63) of verification") fmt.Println(rhs) fmt.Println(lhs) return false } tmp1 := EC.Zero() zneg := new(big.Int).Mod(new(big.Int).Neg(cz), EC.N) for i := range EC.BPG { tmp1 = tmp1.Add(EC.BPG[i].Mult(zneg)) } //tmp1+=BPG*(-cz) PowerOfTwos := PowerVector(EC.V, big.NewInt(2)) tmp2 := EC.Zero() // generate h' HPrime := make([]ECPoint, len(EC.BPH)) for i := range HPrime { mi := new(big.Int).ModInverse(PowersOfY[i], EC.N) HPrime[i] = EC.BPH[i].Mult(mi) } for i := range HPrime { val1 := new(big.Int).Mul(cz, PowersOfY[i]) val2 := new(big.Int).Mul(new(big.Int).Mul(cz, cz), PowerOfTwos[i]) tmp2 = tmp2.Add(HPrime[i].Mult(new(big.Int).Add(val1, val2))) } //tmp2+=BPH*(val1+val2) // without subtracting this value should equal muCH + l[i]G[i] + r[i]H'[i] // we want to make sure that the innerproduct checks out, so we subtract it P := rp.A.Add(rp.S.Mult(cx)).Add(tmp1).Add(tmp2).Add(EC.H.Mult(rp.Mu).Neg()) //fmt.Println(P) //P=A+cx*S+tmp1+tmp2+(-Mu*H) if !InnerProductVerifyFast(rp.Th, P, EC.U, EC.BPG, HPrime, rp.IPP) { fmt.Println("RPVerify - Uh oh! Check line (65) of verification!") return false } return true } // Calculates (aL - z*1^n) + sL*x func CalculateLMRP(aL, sL []*big.Int, z, x *big.Int) []*big.Int { result := make([]*big.Int, len(aL)) tmp1 := VectorAddScalar(aL, new(big.Int).Neg(z)) tmp2 := ScalarVectorMul(sL, x) result = VectorAdd(tmp1, tmp2) return result } func CalculateRMRP(aR, sR, y, zTimesTwo []*big.Int, z, x *big.Int) []*big.Int { if len(aR) != len(sR) || len(aR) != len(y) || len(y) != len(zTimesTwo) { fmt.Println("CalculateR: Uh oh! Arrays not of the same length") fmt.Printf("len(aR): %d\n", len(aR)) fmt.Printf("len(sR): %d\n", len(sR)) fmt.Printf("len(y): %d\n", len(y)) fmt.Printf("len(po2): %d\n", len(zTimesTwo)) } result := make([]*big.Int, len(aR)) tmp11 := VectorAddScalar(aR, z) tmp12 := ScalarVectorMul(sR, x) tmp1 := VectorHadamard(y, VectorAdd(tmp11, tmp12)) result = VectorAdd(tmp1, zTimesTwo) return result } /* DeltaMRP is a helper function that is used in the multi range proof \delta(y, z) = (z-z^2)<1^n, y^n> - \sum_j z^3+j<1^n, 2^n> */ func DeltaMRP(y []*big.Int, z *big.Int, m int) *big.Int { result := big.NewInt(0) // (z-z^2)<1^n, y^n> z2 := new(big.Int).Mod(new(big.Int).Mul(z, z), EC.N) t1 := new(big.Int).Mod(new(big.Int).Sub(z, z2), EC.N) t2 := new(big.Int).Mod(new(big.Int).Mul(t1, VectorSum(y)), EC.N) // \sum_j z^3+j<1^n, 2^n> // <1^n, 2^n> = 2^n - 1 po2sum := new(big.Int).Sub(new(big.Int).Exp(big.NewInt(2), big.NewInt(int64(EC.V/m)), EC.N), big.NewInt(1)) t3 := big.NewInt(0) for j := 0; j < m; j++ { zp := new(big.Int).Exp(z, big.NewInt(3+int64(j)), EC.N) tmp1 := new(big.Int).Mod(new(big.Int).Mul(zp, po2sum), EC.N) t3 = new(big.Int).Mod(new(big.Int).Add(t3, tmp1), EC.N) } result = new(big.Int).Mod(new(big.Int).Sub(t2, t3), EC.N) return result } // NewECPrimeGroupKey returns the curve (field), // Generator 1 x&y, Generator 2 x&y, order of the generators func NewECPrimeGroupKey(n int) CryptoParams { curValue := btcec.S256().Gx s256 := sha256.New() gen1Vals := make([]ECPoint, n) gen2Vals := make([]ECPoint, n) u := ECPoint{big.NewInt(0), big.NewInt(0)} cg := ECPoint{} ch := ECPoint{} j := 0 confirmed := 0 for confirmed < (2*n + 3) { s256.Write(new(big.Int).Add(curValue, big.NewInt(int64(j))).Bytes()) potentialXValue := make([]byte, 33) binary.LittleEndian.PutUint32(potentialXValue, 2) for i, elem := range s256.Sum(nil) { potentialXValue[i+1] = elem } gen2, err := btcec.ParsePubKey(potentialXValue, btcec.S256()) if err == nil { if confirmed == 2*n { // once we've generated all g and h values then assign this to u u = ECPoint{gen2.X, gen2.Y} //fmt.Println("Got that U value") } else if confirmed == 2*n+1 { cg = ECPoint{gen2.X, gen2.Y} } else if confirmed == 2*n+2 { ch = ECPoint{gen2.X, gen2.Y} } else { if confirmed%2 == 0 { gen1Vals[confirmed/2] = ECPoint{gen2.X, gen2.Y} //fmt.Println("new G Value") } else { gen2Vals[confirmed/2] = ECPoint{gen2.X, gen2.Y} //fmt.Println("new H value") } } confirmed += 1 } j += 1 } return CryptoParams{ btcec.S256(), btcec.S256(), gen1Vals, gen2Vals, btcec.S256().N, u, n, cg, ch} } func init() { EC = NewECPrimeGroupKey(VecLength) } func main() { argCount := len(os.Args[1:]) val:="1" if (argCount>0) { val = string(os.Args[1]) } if (argCount>1) { VecLength,_ = strconv.Atoi((os.Args[2])) } EC = NewECPrimeGroupKey(VecLength) m,_ := new(big.Int).SetString(val, 10) rtn:=RPProve(m) r:=RPVerify(rtn) fmt.Printf("Value is : %s\n",val) fmt.Printf("Value is between 1 and 2^%d-1: %t\n",VecLength,r) fmt.Printf("=== Public parameters:\n") fmt.Printf(" Curve type:\tsecp256k1\n") fmt.Printf(" G:\t%s\n",EC.G) fmt.Printf(" H:\t%s\n",EC.H) fmt.Printf(" Curve b value:\t%s\n",EC.C.Params().B) fmt.Printf(" Curve prime value:\t%s\n",EC.C.Params().P) fmt.Printf(" Gi[0]:\t%s\n",EC.BPG[0]) fmt.Printf(" Hi[0]:\t%s\n",EC.BPH[0]) fmt.Printf(" Vector length:\t%d\n",EC.V) fmt.Printf("\n=== Proof\n") fmt.Printf("Challenge:\n") fmt.Printf(" Cx:\t%s\n",rtn.Cx) fmt.Printf(" Cy:\t%s\n",rtn.Cy) fmt.Printf(" Cz:\t%s\n",rtn.Cz) fmt.Printf("A:\t%s\n",rtn.A) fmt.Printf("S:\t%s\n",rtn.S) fmt.Printf("T1:\t%s\n",rtn.T1) fmt.Printf("T2:\t%s\n",rtn.T2) fmt.Printf("Tau:\t%s\n",rtn.Tau) fmt.Printf("Th:\t%s\n",rtn.Th) fmt.Printf("Mu:\t%s\n",rtn.Mu) fmt.Printf("\nIPP (Inner product proof):\n") fmt.Printf(" a:\t%s\n",rtn.IPP.A) fmt.Printf(" b:\t%s\n",rtn.IPP.B) fmt.Printf(" L[0]:\t%s\n",rtn.IPP.L[0]) fmt.Printf(" R[0]:\t%s\n",rtn.IPP.R[0]) fmt.Printf(" L[1]:\t%s\n",rtn.IPP.L[1]) fmt.Printf(" R[1]:\t%s\n",rtn.IPP.R[1]) }
A sample run is [details]:
Value is : 255 Value is between 1 and 2^8-1: true === Public parameters: Curve type: secp256k1 G: {19049299976918701640434378399416395322521814324735570823046957748159542780110 32970026245044992563886736445720684210429064727746262888414787291191552501274} H: {65902674721981107959526451160629142373497501987645733246213038919069206754027 11211914402750177729239671736547089198200305441898725665542549987877079109934} Curve b value: 7 Curve prime value: 115792089237316195423570985008687907853269984665640564039457584007908834671663 Gi[0]: {72242507303365076728861865557797731214902786606643414733580150814770869272593 27033601650718423694844620558628339447280369833685083662535239836251867410934} Hi[0]: {5585562941503279596474839515994484383064083005553472397059910728304658620745 77310285201950507048734835505325678526225389174038208505235173650760230890492} Vector length: 8 === Proof Challenge: Cx: 66873176456638195897075093943820216817246979642048211473051711611923467228895 Cy: 94074857772546105393432567127684826293641863216229224503445427122548233017721 Cz: 91671346013715555422665248380246271672435719609721904941373147691938060218262 A: {99151663132386421360826436734170381859123841654083969527633399460065061486436 111482165979079479057212408659821512649015060474221455405197742567550385897115} S: {24387856947604846374579509788424934668318630868248825224444381198936741547943 91597811734661403355672824800944939146866056684783543174275364115189273660156} T1: {50701721388410539432219502110285267682852029218476737003678322320819136719789 100165105171911445858733626563137723680935104359796425756337939880413561447551} T2: {790606333868662503386096381303248430313160991250374129788864023291738481436 76988700860812809559385401453275912208647775368392255937654377330591920379597} Tau: 82672454385139165066116662283889751136007676169056119223649069916753949048794 Th: 51521439334729587135285739526658412104300083857778012182400339436050545359344 Mu: 107321052306978628303630979996854527268548846141216344664377080735838067344915 IPP (Inner product proof): a: 108507359215445469625362809755510233879009465046384376071302252483567473805857 b: 55704077063196037722414059103854613624677335973528507264544408761416602693623 L[0]: {114512677526766969335542630484381031751539257942891280777452927194288458720950 51791897630964214328227726952034912012594454551218173333768556123862561210745} R[0]: {64572451821403647963119237130713972117313225054906284814354108403842082428724 19767350298049787570483059248801228110335064021067596332350582196982352199498} L[1]: {75306967628183584964594940304598890001841334825877625745872473027502537372848 88539102357437846679263632799148301286486928220698346592933528481079305656409} R[1]: {91586174703118349305711798800544605175603206581502496629809610785446690258254 46512665635955618974229266885074811509645919685052613413520612491966763789825}
The public parameters are [1]:
- l: cardinality of the subgroup of the elliptic curve used (Ed25519)
- N: bitsize of the elements whose range one wants to prove (N = 64)
- M: number of proofs to aggregate
- G: the base point of the subgroup of the elliptic curve used
- H: another generator of the subgroup of the elliptic curve used whose discrete log wrt G is not known and hard to find
- Gi: a list of M*N generators of the subgroup of the elliptic curve used whose discrete log wrt any other generator is not known and hard to find
- Hi: a list of M*N generators of the subgroup of the elliptic
The committed to values are [1]:
- v: the values to hide (and are in the range \(0 \le v_j \le 2^N\))
- gamma: hiding values
The bulletproof is [1]:
- V: a vector of curve points, Pedersen commitments to v[i] with hiding values gamma[i]
- A: a curve point, vector commitment to aL and aR with hiding value alpha
- S: a curve point, vector commitment to sL and sR with hiding value rho
- T1: a curve point, Pedersen commitment to t1 with hiding value tau1
- T2: a curve point, Pedersen commitment to t2 with hiding value tau2
- taux: a scalar, hiding value related to T1, T2, V and t
- mu: a scalar, hiding value related to A and S
- L: a vector of curve points of size log2(M*N) computed in the inner product protocol
- R: a vector of curve points of size log2(M*N) computed in the inner product protocol
- a: a scalar computed in the inner product protocol
- b: a scalar computed in the inner product protocol
- t: a scalar, inner product value to be verified