With the Damgard-Fujisaki method, Peggy can provde to Victor that she can commit proofs that she has a value between \(a\) and \(b\), without revealing the value using secp256k1 curve.
Zero-knowledge proof (Damgard-Fujisaki method) for a range proof with ECC |
Method
In this case we will use the Damgard-Fujisaki method defined [here], and where Peggy has to prove to Victor that she has a postive value. First Victor and Peggy agree on two bases for their calculations (\(g\) and \(h\)) and a prime number (\(n\)). Victor then sends Peggy using a random number (\(r\)) as a challenge. Every positive value can be represented in the form:
\(x = x_0^2 + x_1^2 + x_2^2 + x_3^2\)
For example:
\(51 = 1^2 + 3^2 + 4^2 + 5^2\)
\(1451 = 1^2 +9^2 +12^2 +35^2\)
\(99999 = 1^2 +2^2 +313^2 +45^2\)
Peggy now creates four commitments from these four values, and takes four random numbers (\(r_0\), \(r_1\), \(r_2\) and \(r_3\)).
\(c_0=g^{x_0^2} h^{r_0} \pmod n\)
\(c_1=g^{x_1^2} h^{r_1} \pmod n\)
\(c_2=g^{x_2^2} h^{r_2} \pmod n\)
\(c_3=g^{x_3^2} h^{r_3} \pmod n\)
And:
\(r = r_0 + r_1 + r_2 + r_3\)
Victor then checks:
\(c = c_1 \times c_2 \times c_3 \times c_4\)
And this should be equal to:
\(g^x h^r \pmod n\)
Now to prove the range, we take \((x-a)\) and \((b-x)\) and which should be positive values. Next we compute a commitment of:
\(c_1=g^{(b-x)}.h^{-r} \pmod n\)
and:
\(c_2=g^{(x-a)}.h^{r} \pmod n\)
To prove the commitments we take:
\(p_1=\frac{g^b}{c1} \pmod n\)
and:
\(p_2=c_2.{g^a} \pmod n\)
and they should be equal to:
\(g^x.h^r \pmod n\)
Converting to ECC
We start with two points on the curve: \(G\) and \(H\). And then can compute:
\(c_0=({x_0}^2).G + (r_0).H\)
\(c_1=({x_1}^2).G + (r_1).H\)
\(c_2=({x_2}^2).G + (r_2).H\)
\(c_3=({x_3}^2).G + (r_3).H\)
and then:
\(r = r_0 + r_1 + r_2 + r_3\)
Victor then checks:
\(c = c_1 + c_2 + c_3 + c_4\)
and check than this equals:
\(x.G + r.H \)
We now get:
\(c_1=(b-x).G-r.H \)
\(c_2=(x-a).G+r.H \)
\(p_1=b.G-c_1 \)
\(p_2=c_2+a.G \)
We then check that \(p_1\) is equal to \(p_2\). The code is:
c1 := G.Mul(b.Sub(n)).Add(H.Mul(r.Neg())) c2 := G.Mul(n.Sub(a)).Add(H.Mul(r)) 1 := G.Mul(b).Sub(c1) p2 := c2.Add(G.Mul(a)) if p1.Equal(p2) { fmt.Printf("\n%d is in the range of %d and %d\n", nv, na, nb) } else { fmt.Printf("\n%d is NOT in the range of %d and %d\n", nv, na, nb) }
Coding
The following is some simple coding to prove the method:
package main import ( "crypto/rand" "fmt" "os" "strconv" "github.com/coinbase/kryptology/pkg/core/curves" ) func lipmaa(val int) (int, int, int, int) { if val < 0 { return 0, 0, 0, 0 } for i := 0; i < 100000; i++ { for j := 0; j < 1000; j++ { for k := 0; k < 100; k++ { for l := 0; l < 10; l++ { if ((i * i) + (j * j) + (k * k) + (l * l)) == val { return i, j, k, l } } } } } return 0, 0, 0, 0 } func proofPositive(G curves.Point, H curves.Point, nv int) (bool, curves.Scalar, curves.Point) { curve := curves.K256() n := curve.Scalar.New(nv) var r curves.Scalar var c curves.Point x0v, x1v, x2v, x3v := lipmaa(nv) if x0v == 0 && x1v == 0 && x2v == 0 && x3v == 0 { return false, r, c } r0 := curve.Scalar.Random(rand.Reader) r1 := curve.Scalar.Random(rand.Reader) r2 := curve.Scalar.Random(rand.Reader) r3 := curve.Scalar.Random(rand.Reader) x0 := curve.Scalar.New(x0v) x1 := curve.Scalar.New(x1v) x2 := curve.Scalar.New(x2v) x3 := curve.Scalar.New(x3v) c0 := G.Mul(x0.Mul(x0)).Add(H.Mul(r0)) c1 := G.Mul(x1.Mul(x1)).Add(H.Mul(r1)) c2 := G.Mul(x2.Mul(x2)).Add(H.Mul(r2)) c3 := G.Mul(x3.Mul(x3)).Add(H.Mul(r3)) r = r0.Add(r1).Add(r2).Add(r3) c = c0.Add(c1).Add(c2).Add(c3) val := G.Mul(n).Add(H.Mul(r)) if c.Equal(val) { return true, r, c } return false, r, c } func main() { nv := 6 na := 3 nb := 10 argCount := len(os.Args[1:]) if argCount > 0 { nv, _ = strconv.Atoi(os.Args[1]) } if argCount > 1 { na, _ = strconv.Atoi(os.Args[2]) } if argCount > 2 { nb, _ = strconv.Atoi(os.Args[3]) } curve := curves.K256() G := curve.Point.Generator() v := curve.Scalar.Random(rand.Reader) H := G.Mul(v) rtn1, r, _ := proofPositive(G, H, nv) rtn2, _, _ := proofPositive(G, H, nv-na) rtn3, _, _ := proofPositive(G, H, nb-nv) fmt.Printf("x=%d, a=%d, b=%d\n", nv, na, nb) if rtn1 { fmt.Printf("x positive\n") } if rtn2 { fmt.Printf("%d>%d\n", nv, na) } if rtn3 { fmt.Printf("%d<%d\n", nv, nb) } if rtn1 == false || rtn2 == false || rtn3 == false { fmt.Printf("Cannot prove") os.Exit(0) } n := curve.Scalar.New(nv) a := curve.Scalar.New(na) b := curve.Scalar.New(nb) c1 := G.Mul(b.Sub(n)).Add(H.Mul(r.Neg())) c2 := G.Mul(n.Sub(a)).Add(H.Mul(r)) p1 := G.Mul(b).Sub(c1) p2 := c2.Add(G.Mul(a)) // p2= (x-a).G + r.H + a.G = xG - aG + r.H + aG = xG + r.H fmt.Printf("\n\np1=%x\n", p1.ToAffineCompressed()) fmt.Printf("p2=%x\n", p2.ToAffineCompressed()) if p1.Equal(p2) { fmt.Printf("\n%d is in the range of %d and %d\n", nv, na, nb) } else { fmt.Printf("\n%d is NOT in the range of %d and %d\n", nv, na, nb) } }
A sample run is:
x=5, a=3, b=10 x positive 5>3 5<10 p1=03c40111b441bd1afd517a4df67309f012c33aa5e1c07733aa479bbc2144528412 p2=03c40111b441bd1afd517a4df67309f012c33aa5e1c07733aa479bbc2144528412 5 is in the range of 3 and 10
Reference
[1] Damgård, I., & Fujisaki, E. (2002, December). A statistically-hiding integer commitment scheme based on groups with hidden order. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 125-142). Springer, Berlin, Heidelberg.