Let's say we have two base points on an elliptic curve (\(G\) and \(M\)), and then have two random values (\(k\) and \(x\)). If we have \(Y=xG\) and \(Z=xM\), can we prove that \(Y\) and \(Z\) use the same scalar value (\(x\))? For this, we then use \(G,Y,M,Z\) within a Chaum-Pedersen proof [1] to provide a zero-knowledge proof that \(log_G(Y) == log_M(Z)\). This is defined as DLEQ(Z/M == Y/G) - discrete log equality. With this we can prove that the same private key has been used for \(xG\) and \(xM\). In this case, we will use the sepc256k1 elliptic curve (as used in Bitcoin) to perform the operations.
NIZK (Non-interactive Zero Knowledge) proofs of discrete - log equality with Golang |
Theory
Let's say we have two base points on an elliptic curve (\(G\) and \(M\)), and then have two random values (\(k\) and \(x\)). If we have \(Y=xG\) and \(Z=xM\), can we prove that \(Y\) and \(Z\) use the same scalar value (\(x\))? For this, we then use \(G,Y,M,Z\) within a Chaum-Pedersen proof [1] to provide a zero-knowledge proof that \(log_G(Y) == log_M(Z)\). This is defined as DLEQ(Z/M == Y/G) - discrete log equality. With this we can prove that the same private key has been used for \(xG\) and \(xM\).
Let say Peggy (the prover) needs to prove that two public keys use the same private key (\(x\)) but with different base points:
\(Y = xG\)
\(Z = xM\)
Peggy will generator a random value (\(k\)) and then computes two points (\(A\) and \(B\)) based on the generator points used (\(G\) and \(M\)):
\(A = kG\)
\(B = kM\)
With non-interactive proofs, Peggy then creates a challenge (\(c\)) of:
\(c=Hash(G,Y,M,Z,A,B)\)
And then calculates:
\(s=k - cx \pmod n\)
and where \(n\) is the order of the curve. As the proof, Peggy then sends the following to Victor:
\((c,s)\)
The verifier (Victor) then computes:
\(A'=sG + cY\)
\(B'=sM + cZ\)
\(c'=Hash(G,Y,M,Z,A',B')\)
If \(c==c'\), the proof has been proven.
This works because:
\( \begin{align} A'+B' &= sG + cY + sM + cZ = (k-cx)G + cY + (k-cx)M + cZ = kG + cxG + cY + kM - cxM + cZ\\ &= kG - cY + cY + kM -cZ + cZ = kG + kM = A + B \end{align} \)
Code
Here is the code:
package main import ( "crypto/rand" "crypto/sha256" "fmt" "github.com/coinbase/kryptology/pkg/core/curves" ) func main() { curve := curves.K256() G := curve.Point.Generator() x := curve.Scalar.Random(rand.Reader) M := G.Mul(x) x = curve.Scalar.Random(rand.Reader) Y := G.Mul(x) Z := M.Mul(x) k := curve.Scalar.Random(rand.Reader) A := G.Mul(k) B := M.Mul(k) h := sha256.New() h.Write(G.ToAffineCompressed()) h.Write(Y.ToAffineCompressed()) h.Write(M.ToAffineCompressed()) h.Write(Z.ToAffineCompressed()) h.Write(A.ToAffineCompressed()) h.Write(B.ToAffineCompressed()) c, _ := curve.Scalar.SetBytes(h.Sum(nil)) // s=k−h*x % o s := c.Mul(x).Sub(k) s = s.Neg() sG := G.Mul(s) cY := Y.Mul(c) A_ := sG.Add(cY) sM := M.Mul(s) cZ := Z.Mul(c) B_ := sM.Add(cZ) h = sha256.New() h.Write(G.ToAffineCompressed()) h.Write(Y.ToAffineCompressed()) h.Write(M.ToAffineCompressed()) h.Write(Z.ToAffineCompressed()) h.Write(A_.ToAffineCompressed()) h.Write(B_.ToAffineCompressed()) c2, _ := curve.Scalar.SetBytes(h.Sum(nil)) fmt.Print("Peggy's secret:\n") fmt.Printf("x= %s\n", x.BigInt()) fmt.Print("\nPeggy Computes):") fmt.Printf("\nxG %x\n", Y.ToAffineCompressed()) fmt.Printf("\nxM %x\n", Z.ToAffineCompressed()) fmt.Printf("A %x\n", A.ToAffineCompressed()) fmt.Printf("B %x\n", B.ToAffineCompressed()) fmt.Print("\nPeggy sends (s,c):") fmt.Printf("\ns %x\n", s.Bytes()) fmt.Printf("\nc %x\n", c.Bytes()) fmt.Print("\nVictor computes:") fmt.Printf("\nA_ %x\n", A_.ToAffineCompressed()) fmt.Printf("B_ %x\n", B_.ToAffineCompressed()) fmt.Printf("c2=%x", c2.Bytes()) if c.Cmp(c2) == 0 { fmt.Printf("\nProven") } }
A sample run is:
Peggy's secret: x= 10889955764090674601555275618893045918242493666570605562737959335763302674924 Peggy Computes: xG 03cab48ae98508ecb4d470536bffcbdcfd242d2e9ef2def04de9e96e94751ebd7c xM 031a8fd3145b618613245401f68adb157bd6506580ff9f427cf86ba3d3ecee7cc9 A 029fc4422a32333581d48e9764507b21534fb64aa257368c4ba8b5dd5dc53520d9 B 028d6df0be23c06503351a978c35ae9c9a6f465b2a605517ef773ac2c6fbc12fa7 Peggy sends (s,c): s 25ef0a77594d52d974d6874cdd7c3ab254ca7345ccb014f5e01e8193a07633a5 c 7ac65c58cabccd8476a3a3fbb428bf6549b2900471775040380326f98cbbba18 Victor computes: A_ 029fc4422a32333581d48e9764507b21534fb64aa257368c4ba8b5dd5dc53520d9 B_ 028d6df0be23c06503351a978c35ae9c9a6f465b2a605517ef773ac2c6fbc12fa7 c2=7ac65c58cabccd8476a3a3fbb428bf6549b2900471775040380326f98cbbba18 Proven
References
[1] Chaum, David, and Torben Pryds Pedersen. "Wallet databases with observers." Annual international cryptology conference. Springer, Berlin, Heidelberg, 1992 [paper].